《Linux Device Drivers》第五章 并發(fā)和競(jìng)態(tài)――note

• 并發(fā)及其管理
  • 競(jìng)態(tài)通常作為對(duì)資源的共享訪問(wèn)結(jié)果而產(chǎn)生
  • 當(dāng)兩個(gè)執(zhí)行線程需要訪問(wèn)相同的數(shù)據(jù)結(jié)構(gòu)（或硬件資源）時(shí)，并發(fā)的可能性就永遠(yuǎn)存在
  • 只要可能就應(yīng)該避免資源的共享，但共享通常是必須的，硬件本質(zhì)上就是共享的
  • 訪問(wèn)管理的常見(jiàn)技術(shù)稱為“鎖定”或者“互斥”
• 信號(hào)量和互斥體
  • 建立臨界區(qū)：在任意給定的時(shí)刻，代碼只能被一個(gè)線程執(zhí)行
  • 可以使用一種鎖定機(jī)制，當(dāng)進(jìn)程在等待對(duì)臨界區(qū)的訪問(wèn)時(shí)，此機(jī)制可讓進(jìn)程進(jìn)入休眠狀態(tài)
  • 一個(gè)信號(hào)量本質(zhì)上是一個(gè)整數(shù)值，它和一對(duì)函數(shù)聯(lián)合使用，這一對(duì)函數(shù)通常稱為P和V
  • 當(dāng)信號(hào)量用于互斥時(shí)，信號(hào)量的值應(yīng)初始化為1，這種信號(hào)量有時(shí)也稱為“互斥體（mutex）”
  • Linux信號(hào)量的實(shí)現(xiàn)
    • <asm/semaphore.h>
    • struct semaphore;
    • void sema_init(struct semaphore *sem, int val);
    • DECLARE_MUTEX(name);
      • 稱為name的信號(hào)量變量被初始化為1
    • DECLARE_MUTEX_LOCKED(name);
      • 稱為name的信號(hào)量變量被初始化為0
    • void init_MUTEX(struct semaphore *sem);
    • void init_MUTEX_LOCKED(struct semaphore *sem);
    • void down(struct semaphore *sem);
      • 一直等待
    • int down_interruptible(struct semaphore *sem);
      • 操作是可中斷的
      • 如果操作被中斷，該函數(shù)會(huì)返回非零值
      • 通常使用的是可中斷的down版本
        
    • int down_trylock(struct semaphore *sem);
      • 永遠(yuǎn)不會(huì)休眠
      • 如果信號(hào)量在調(diào)用時(shí)不可獲得，會(huì)立即返回一個(gè)非零值
    • void up(struct semaphore *sem);
  • 讀取者/寫(xiě)入者信號(hào)量
    • 一些任務(wù)只需要讀取受保護(hù)的數(shù)據(jù)結(jié)構(gòu)，而其他的則必須做出修改
    • <linux/rwsem.h>
    • struct rw_semaphore;
    • void init_rwsem(struct rw_semaphore *sem);
    • void down_read(struct rw_semaphore *sem);
      • 只讀訪問(wèn)，可和其他讀取者并發(fā)地訪問(wèn)
    • int down_read_trylock(struct rw_semaphore *sem);
      • 在授予訪問(wèn)時(shí)返回非零，其他情況下返回零
    • void up_read(struct rw_semaphore *sem);
    • void down_write(struct rw_semaphore *sem);
    • int down_write_trylock(struct rw_semaphore *sem);
    • void up_write(struct rw_semaphore *sem);
    • void downgrade_write(struct rw_semaphore *sem);
    • 最好在很少需要寫(xiě)訪問(wèn)且寫(xiě)入者只會(huì)短期擁有信號(hào)量的時(shí)候使用rwsem

• completion
  • 內(nèi)核編程中常見(jiàn)的一種模式是，在當(dāng)前線程之外初始化某個(gè)活動(dòng)，然后等待該活動(dòng)的結(jié)束
  • <linux/completion.h>
  • DECLARE_COMPLETION(my_completion);
  • init_completion(struct completion *c);
  • void wait_for_completion(struct completion *c);
    • 非中斷的等待
  • void complete(struct completion *c);
  • void complete_all(struct completion *c);
  • 一個(gè)completion通常是一個(gè)單次（one-shot）設(shè)備
  • 如果沒(méi)有使用complete_all，可以重復(fù)使用一個(gè)complete結(jié)構(gòu)
  • 如果使用了complete_all，則必須在重復(fù)使用該結(jié)構(gòu)之前重新初始化它
  • INIT_COMPLETE(struct completion c);
  • void complete_and_exit(struct completion *c, long retval);
• 自旋鎖
  • 自旋鎖可在不能休眠的代碼中使用，比如中斷處理例程
  • 可提供比信號(hào)量更高的性能
  • 一個(gè)自旋鎖是一個(gè)互斥設(shè)備，它只能有兩個(gè)值：鎖定和解鎖
  • 通常實(shí)現(xiàn)為某個(gè)整數(shù)值中的單個(gè)位
  • 如果鎖可用，則“鎖定”位被設(shè)置，而代碼繼續(xù)進(jìn)入臨界區(qū)
  • 如果鎖被其他人獲得，則代碼進(jìn)入忙循環(huán)并重復(fù)檢查這個(gè)鎖，直到該鎖可用為止，這個(gè)循環(huán)就是自旋鎖的“自旋”部分
  • “測(cè)試并設(shè)置”的操作必須以原子方式完成
  • 在超線程處理器上，還必須仔細(xì)處理以避免死鎖，超線程處理器可實(shí)現(xiàn)多個(gè)虛擬的CPU，它們共享單個(gè)處理器核心及緩存
  • 自旋鎖API介紹
    • <linux/spinlock.h>
    • spinlock_t
    • spinlock_t my_lock = SPIN_LOCK_UNLOCKED;
    • void spin_lock_init(spinlock_t *lock);
    • void spin_lock(spinlock_t *lock);
      • 不可中斷
      • 在獲得鎖之前一直處于自旋狀態(tài)
    • void spin_unlock(spinlock_t *lock);
  • 自旋鎖和原子上下文
    • 任何擁有自旋鎖的代碼都必須是原子的，不能休眠，不能因?yàn)槿魏卧蚍艞壧幚砥鳎朔?wù)中斷之外
  • 自旋鎖函數(shù)
    • void spin_lock(spinlock_t *lock);
    • void spin_lock_irqsave(spinlock_t *lock, unsigned long flags);
      • 在獲得自旋鎖之前禁止中斷，而先前的中斷狀態(tài)保存在flags中
    • void spin_lock_irq(spinlock_t *lock);
    • void spin_lock_bh(spinlock_t *lock);
      • 在獲得鎖之前禁止軟件中斷
    • void spin_unlock(spinlock_t *lock);
    • void spin_unlock_irqrestore(spinlock_t *lock, unsigned long flags);
      • flags參數(shù)必須是傳遞給spin_lock_irqsave的同一個(gè)變量
    • void spin_unlock_irq(spinlock_t *lock);
    • void spin_unlock_bh(spinlock_t *lock);
    • int spin_trylock(spinlock_t *lock);
      • 成功時(shí)返回非零值，否則返回零
    • int spin_trylock_bh(spinlock_t *lock);
      • 成功時(shí)返回非零值，否則返回零
  • 讀取值/寫(xiě)入者自旋鎖
    • <linux/spinlock.h>
    • rwlock_t
    • rwlock_t my_rwlock = RW_LOCK_UNLOCKED;
    • void rwlock_init(rwlock_t * lock);
    • void read_lock(rwlock_t *lock);
    • void read_lock_irqsave(rwlock_t *lock, unsigned long flags);
    • void read_lock_irq(rwlock_t *lock);
    • void read_lock_bh(rwlock_t *lock);
    • void read_unlock(rwlock_t *lock);
    • void read_unlock_irqrestore(rwlock_t *lock, unsigned long flags);
    • void read_unlock_irq(rwlock_t *lock);
    • void read_unlock_bh(rwlock_t *lock);
    • void write_lock(rwlock_t *lock);
    • void write_lock_irqsave(rwlock_t *lock, unsigned long flags);
    • void write_lock_irq(rwlock_t *lock);
    • void write_lock_bh(rwlock_t *lock);
    • int write_trylock(rwlock_t *lock);
    • void write_unlock(rwlock_t *lock);
    • void write_unlock_irqrestore(rwlock_t *lock, unsigned long flags);
    • void write_unlock_irq(rwlock_t *lock);
    • void write_unlock_bh(rwlock_t *lock);
    • 讀取者/寫(xiě)入者鎖可能造成讀取者饑餓
• 鎖陷阱
  • 不明確的規(guī)則
    • 不論是信號(hào)量還是自旋鎖，都不允許鎖擁有者第二次獲得這個(gè)相同的鎖，如果試圖這樣做，系統(tǒng)將掛起
  • 鎖的順序規(guī)則
    • 在必須獲取多個(gè)鎖時(shí)，應(yīng)該始終以相同的順序獲得
    • 如果必須獲得一個(gè)局部鎖以及一個(gè)屬于內(nèi)核更中心位置的鎖，則應(yīng)該首先獲取自己的局部鎖
    • 如果擁有信號(hào)量和自旋鎖的組合，則必須首先獲得信號(hào)量
  • 細(xì)粒度鎖和粗粒度鎖的對(duì)比
    • 細(xì)粒度鎖具有良好的伸縮性
    • 細(xì)粒度鎖將帶來(lái)某種程序的復(fù)雜性
    • 應(yīng)該在最初使用粗粒度的鎖
    • 使用lockmeter工具可度量?jī)?nèi)核花費(fèi)在鎖上的時(shí)間
      • http://oss.sgi.com/projects/lockmeter/
• 除了鎖之外的方法
  • 免鎖算法
    • 經(jīng)常用于免鎖的生產(chǎn)者/消費(fèi)者任務(wù)的數(shù)據(jù)結(jié)構(gòu)之一是循環(huán)緩沖區(qū)
  • 原子變量
    • <asm/atomic.h>
    • atomic_t
    • 一個(gè)atomic_t變量保存一個(gè)int值，但不能記錄大于24位的整數(shù)
    • void atomic_set(atomic_t *v, int i);
    • atomic_t v = ATOMIC_INIT(0);
    • int atomic_read(atomic_t *v);
    • void atomic_add(int i, atomic_t *v);
    • void atomic_sub(int i, atomic_t *v);
    • void atomic_inc(atomic_t *v);
    • void atomic_dec(atomic_t *v);
    • int atomic_inc_and_test(atomic_t *v);
    • int atomic_dec_and_test(atomic_t *v);
    • int atomic_sub_and_test(int i, atomic_t *v);
    • int atomic_add_negative(int i, atomic_t *v);
    • int atomic_add_return(int i, atomic_t *v);
    • int atomic_sub_return(int i, atomic_t *v);
    • int atomic_inc_return(atomic_t *v);
    • int atomic_dec_return(atomic_t *v);
    • 需要多個(gè)atomic_t變量的操作，仍然需要某種類型的鎖
  • 位操作
    • <asm/bitops.h>
    • nr參數(shù)通常被定義為int，但在少數(shù)架構(gòu)上被定義為unsigned long
    • void set_bit(nr, void *addr);
    • void clear_bit(nr, void *addr);
    • void change_bit(nr, void *addr);
    • test_bit(nr, void *addr);
    • int test_and_set_bit(nr, void *addr);
    • int test_add_clear_bit(nr, void *addr);
    • int test_and_change_bit(nr, void *addr);
  • seqlock
    • 允許讀取者對(duì)資源的自由訪問(wèn)，但需要讀取者檢查是否和寫(xiě)入者發(fā)生沖突
    • <linux/seqlock.h>
    • seqlock_t
    • seqlock_t lock1 = SEQLOCK_UNLOCKED;
    • void seqlock_init(seqlock_t *lock);
    • unsigned int read_seqbegin(seqlock_t *lock);
    • int read_seqretry(seqlock_t *lock, unsigned int seq);
    • unsigned int read_seqbegin_irqsave(seqlock_t *lock, unsigned long flags);
    • int read_seqretry_irqrestore(seqlock_t *lock, unsigned int seq, unsigned long flags);
    • void write_seqlock(seqlock_t *lock);
    • void write_sequnlock(seqlock_t *lock);
    • void write_seqlock_irqsave(seqlock_t *lock, unsigned long flags);
    • void write_seqlock_irq(seqlock_t *lock);
    • void write_seqlock_bh(seqlock_t *lock);
    • void write_sequnlock_irqrestore(seqlock_t *lock, unsigned long flags);
    • void write_sequnlock_irq(seqlock_t *lock);
    • void write_sequnlock_bh(seqlock_t *lock);
  • 讀取-復(fù)制-更新
    • read-copy-update（RCU）也是一種高級(jí)的互斥機(jī)制
    • 很少在驅(qū)動(dòng)程序中使用
    • http://www.rdrop.com/users/paulmck/rclock/intro/rclock_intro.html
    • 針對(duì)經(jīng)常發(fā)生讀取而很少寫(xiě)入的情形做了優(yōu)化
    • 被保護(hù)的資源應(yīng)該通過(guò)指針訪問(wèn)
    • 在需要修改該數(shù)據(jù)結(jié)構(gòu)時(shí)，寫(xiě)入線程首先復(fù)制，然后修改副本，之后用新的版本替代相關(guān)指針。當(dāng)確信老的版本沒(méi)有其他引用時(shí)，就可釋放老的版本
    • <linux/rcupdate.h>
    • rcu_read_lock
    • rcu_read_unlock
    • void call_rcu(struct rcu_head *head, void (*func)(void *arg), void *arg);

生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)