1. 對(duì)并發(fā)的管理是操作系統(tǒng)編程的核心的問題之一。
2. 早期并發(fā)的惟一原因是對(duì)硬件的中斷服務(wù),，沒有搶占和SMP,。

Scull的缺陷
1. 競(jìng)態(tài)會(huì)導(dǎo)致對(duì)共享數(shù)據(jù)的非控制訪問。
2. 競(jìng)態(tài)是一種極端可能性的事件,，因此程序員往往忽視競(jìng)態(tài),。但在計(jì)算機(jī)的世界里，百萬(wàn)分之一的事件可能在幾秒內(nèi)發(fā)生,，而且結(jié)果
是災(zāi)難性的,。

并發(fā)及其管理
1. SMP系統(tǒng)甚至可以在不同的處理器上同時(shí)執(zhí)行我們的代碼、內(nèi)核代碼是可以搶占的,、中斷隨時(shí)會(huì)發(fā)生,。因此我們的驅(qū)動(dòng)代碼可能
在任何時(shí)候丟失對(duì)處理器的獨(dú)占，而擁有處理器的進(jìn)程可能正在調(diào)用我們的驅(qū)動(dòng)程序代碼,。
內(nèi)核代碼中還提供了可延遲的代碼執(zhí)行機(jī)制比如workqueue(工作隊(duì)列）,、tasklet(小任務(wù)）、以及timer（定時(shí)器）等,，這些機(jī)制可以使
代碼可在任何時(shí)刻執(zhí)行,。
2. 在現(xiàn)代的熱拔插世界中，設(shè)備可能會(huì)在我們正在使用時(shí)消失,。
3. 竟態(tài)通常作為對(duì)資源的共享訪問的結(jié)果而產(chǎn)生。當(dāng)兩個(gè)執(zhí)行線程需要訪問相同的數(shù)據(jù)結(jié)構(gòu)（或硬件資源時(shí)）,，混合的可能性永遠(yuǎn)存在,。
第一個(gè)要記住的規(guī)則是，只要可能,，就應(yīng)該避免資源的共享,。仔細(xì)編寫的內(nèi)核代碼應(yīng)該具有最少的共享，這種思想明顯的就是避免使用
全局變量,。
4. 硬件的資源的本質(zhì)就是共享的,，而軟件資源經(jīng)常需要對(duì)其他線程可用,。我們還有清楚地是全局變量并不是共享資源的唯一途徑，只要我們
將一個(gè)指針傳遞給內(nèi)核的其他部分,，一個(gè)新的共享就可能建立,。
5. 管理常見的技術(shù)成為鎖定或者互斥-確保一次只要一個(gè)執(zhí)行線程可操作共享資源。
6. 當(dāng)內(nèi)核代碼創(chuàng)建了一個(gè)可能和其他內(nèi)核部分共享的對(duì)象時(shí),，該對(duì)象必須在還有其他組件引用自己時(shí)保持存在（并正確工作）,。
在對(duì)象尚不能正確工作時(shí)，不能將其對(duì)內(nèi)核可用,，也就是說,，對(duì)這類對(duì)象的應(yīng)用必須得到跟蹤。

信號(hào)量和互斥體
1. 對(duì)scull數(shù)據(jù)結(jié)構(gòu)操作是原子的,，這意味著在涉及到其他執(zhí)行線程之前,，整個(gè)操作就已經(jīng)結(jié)束。
2. 我們必須建立臨界區(qū)在任意給定代碼時(shí)刻,，代碼只能被一個(gè)線程執(zhí)行,。
3. scull并不擁有任何其他關(guān)鍵的系統(tǒng)資源，這一切意味著,，在scull驅(qū)動(dòng)程序在等待訪問數(shù)據(jù)結(jié)構(gòu)而進(jìn)入休眠時(shí),，不需要考慮其他
內(nèi)核組件。
4. kmalloc可在也可能休眠,，次休眠可能在任何時(shí)刻發(fā)生,。
5. 一個(gè)信號(hào)量本質(zhì)就是一個(gè)整數(shù)值，它和一對(duì)函數(shù)聯(lián)合使用,，這一對(duì)函數(shù)通常稱為P和V,。
6. 當(dāng)信號(hào)量用于互斥時(shí)（即避免多個(gè)進(jìn)程同時(shí)在一個(gè)臨界區(qū)使用運(yùn)行），信號(hào)量的值應(yīng)初始化為1,。

LINUX信號(hào)量的實(shí)現(xiàn)
1. 直接創(chuàng)建信號(hào)量,，這通過sema_init完成。
void sema_init(struct semaphore *sem, int val);
其中val是賦予一個(gè)信號(hào)量的初始值,。
2. 聲明和初始化一個(gè)互斥體,。
DECLARE_MUTEX(name);
DECLARE_MUTEX_LOCKED(name);
3. 如果互斥體必須在運(yùn)行時(shí)初始化。
void init_MUTEX(struct semaphore *sem);
void init_MUTEX_LOCKED(struct semaphore *sem);
4.在linux世界中P函數(shù)稱為down,down是指該函數(shù)減少了信號(hào)量的值,，它也許會(huì)至于調(diào)用者休眠狀態(tài),，然后等待信號(hào)量變得可用
之后授予調(diào)用者對(duì)保護(hù)資源的訪問。
   void down(struct semaphore *sem);
   int down_interruptible(struct semaphore *sem);
   int down_try_lock(struct semaphore *sem);
down減少信號(hào)量的值,，并在必要時(shí)等待,。down_interruptible完成相同的工作，但操作時(shí)可中斷的,?？芍袛嗟陌姹編缀跏俏覀兪冀K
要使用的版本,，它允許在等待某個(gè)信號(hào)量的用戶空間可被用戶中斷。
5. 非中斷操作是建立不可殺死進(jìn)程（ps輸出中的D state的好方法,，但會(huì)讓用戶感到懊惱,。使用時(shí)需要始終檢查返回值，并作出
相應(yīng)的響應(yīng),。
6. down_trylock永遠(yuǎn)不會(huì)休眠：如果信號(hào)量在調(diào)用不可獲得,，down_trylock返回一個(gè)非0值。
7. 當(dāng)獲取了信號(hào)量,，該線程就被賦予訪問由該信號(hào)量保護(hù)臨界區(qū)的權(quán)利,。互斥操作完成后,，必須返回該信號(hào)量,。
LINUX等價(jià)V的函數(shù)是up:
void up(struct semaphore *sem);

在scull中使用信號(hào)量
1. 正確使用鎖機(jī)制的關(guān)鍵是,，明確指明需要保護(hù)的資源，并確保每一個(gè)對(duì)這些資源的訪問使用正確的鎖定。
2. 信號(hào)量在使用前必須被鎖定,。信號(hào)量必須在使用前被初始化,。
3. 注意代碼中對(duì)down_interruptible返回值的檢查：如果它返回0,，則說明操作被中斷,。如果我們返回-ERESTARTSYS，則必須首先
撤銷已經(jīng)作出的任何用戶修改,，這樣系統(tǒng)調(diào)用可正確重試,，如果無(wú)法撤銷這些操作，則應(yīng)該返回-EINTR,。
     if(down_interruptible(&dev->sem)
      return -ERESTARTSYS;
  out:
    up(&dev->sem);
    return retval;

讀取者和寫入者信號(hào)量
1. 信號(hào)量對(duì)所有的調(diào)用者執(zhí)行互斥,，而不管每個(gè)線程到底做什么。但許多任務(wù)都劃分兩種不同的類型：一些任務(wù)只需要讀取
受保護(hù)的數(shù)據(jù)結(jié)構(gòu),，而其他的則必須做出修改,。
2. rwsem (或者reader/writer semaphore 讀取者/寫入者信號(hào)量。相關(guān)的數(shù)據(jù)類型是struct rw_semaphore.
初始化
void init_rwsem(struct rw_semaphore *sem);
對(duì)于只讀訪問可以用如下端口：
void down_read(struct rw_semaphore *sem);
int down_read_trylock(struct rw_semaphore *sem);
void up_read(struct rw_semaphore *sem);
對(duì)于寫入者接口類似：
void down_write(struct rw_semaphore *sem);
int down_write_trylock(struct rw_semaphore *sem);
void up_write(struct rw_semaphore *sem);
3. 一個(gè)rwsem可以允許一個(gè)寫入者或無(wú)限多個(gè)讀取者擁有該信號(hào)量,。寫入者具有更高的權(quán)限,。當(dāng)某個(gè)給定的寫入者試圖
進(jìn)入臨界區(qū)時(shí)，在所有的寫入者完成其工作之前,，不會(huì)允許其他讀取者訪問,。
4. 如果有大量的寫入者競(jìng)爭(zhēng)該信號(hào)量，則導(dǎo)致讀取者“餓死”,，即可能長(zhǎng)期拒絕讀取者的訪問。

Completion
1.  completion是一種輕量級(jí)的機(jī)制,，它允許一個(gè)線程告訴另一個(gè)線程某個(gè)工作已經(jīng)完成,。
2.  <linux/completion.h> 利用下面接口創(chuàng)建completion:
DECLARE_COMPLETION(my_completion)
或者,，動(dòng)態(tài)創(chuàng)建和初始化completion：
struct completion my_completion;
init_completion(&my_completion);
要等待completion，調(diào)用：
void wait_for_completion(struct completion *c);
該函數(shù)執(zhí)行了一個(gè)非中斷的等待,，產(chǎn)生一個(gè)不可殺死的進(jìn)程,。
觸發(fā)completion
void complete(struct completion *c); 喚醒一個(gè)等待線程
void complete_all(struct completion *c);喚醒所有的等待線程。
3. 一個(gè)completion通常是一個(gè)單次（one_shot)設(shè)備,；也就是說它只會(huì)使用一次后被丟棄,。
如果沒有使用complete_all，則我們可以重復(fù)使用completion結(jié)構(gòu),，只要那個(gè)觸發(fā)的事件是明確的而不含糊,。
如果使用了complete_all， 則需要使用
INIT_COMPLETION(struct completion c); 重新初始化,。

自旋鎖
1. 自旋鎖可以在可能休眠的代碼中使用,，在正確使用自旋鎖的情況下，自旋鎖可以提供比信號(hào)量更高的性能,。
2. 一個(gè)自旋鎖是一個(gè)互斥設(shè)備,，它只能有兩個(gè)值：鎖定 和 解鎖。 它通常實(shí)現(xiàn)某個(gè)整數(shù)值正的單個(gè)位,。如果鎖可用
則鎖定位被設(shè)置,，而代碼繼續(xù)進(jìn)入臨界區(qū)，相反,，如果鎖被其他人獲得,，則代碼進(jìn)入忙循環(huán)并重復(fù)檢查這個(gè)鎖。
這個(gè)鎖就是自旋鎖的自旋部分,。
3. 測(cè)試并設(shè)置必須以原子的方式完成,，這樣，即使是多個(gè)線程在給定時(shí)間自旋,，也只有一個(gè)線程可用獲得鎖,。
4. 如果非搶占式的單處理器進(jìn)入某個(gè)鎖上的自旋鎖，則永遠(yuǎn)會(huì)自旋下去,；也就是說沒有任何其他線程能夠獲取
CPU來釋放這個(gè)鎖,。

自旋鎖的API介紹
1. 初始化自旋鎖
spinlock_t my_lock=SPIN_LOCK_UNLOCKED;
或者
void spin_lock_init(spinlock_t *lock);
在進(jìn)入臨界區(qū)之前，我們的代碼必須調(diào)用以下函數(shù)獲取需要的鎖,。
void spin_lock(spinlock_t *lock);
注意,，所有的自旋鎖等待的本質(zhì)上都是不可中斷的。一旦調(diào)用了spin_lock,，在獲得鎖之前將一直處于自旋狀態(tài),。
要釋放已經(jīng)獲取的鎖，可以將鎖傳遞給下面函數(shù)：
void spin_unlock(spinlock_t *lock);

自旋鎖和原子上下文
1. 適用于自旋鎖的核心規(guī)則是：任何擁有自旋鎖的代碼都是原子的，它不能休眠,，它不能因?yàn)槿魏卧蚍艞壧幚砥?，除?br> 服務(wù)于中斷以外。
2. 內(nèi)核搶占的情況是自旋鎖代碼本身處理,，任何時(shí)候,，只要內(nèi)核代碼有自旋鎖，在相關(guān)的處理器上的搶占就會(huì)被禁止,。
3. 在中斷例程自旋時(shí),，非中斷代碼將沒有任何機(jī)會(huì)來釋放這個(gè)鎖，處理器將永遠(yuǎn)自旋下去,。
4. 自旋鎖使用上的最后一個(gè)重要的規(guī)則是：自旋鎖必須在可能最短的時(shí)間內(nèi)擁有,，擁有自旋鎖的時(shí)間越長(zhǎng)，其他處理器
不得不自旋等待釋放該鎖的實(shí)際就越長(zhǎng),，而它不得不自旋的時(shí)間可能性就越大,。

自旋鎖函數(shù)
1. 能鎖定一個(gè)自旋鎖的函數(shù)實(shí)際有4個(gè)：
void spin_lock(spinlock_t *lock);
void spin_lock_irqsave(spinlock_t *lock, unsigned long flags);
會(huì)獲得自旋鎖之前禁止中斷（只在本地處理器上），而先前的中斷狀態(tài)保持在flags中,。
void spin_lock_irq(spinlock_t *lock);
無(wú)需跟蹤標(biāo)志,。
void spin_lock_bh(spinlock_t *lock);
在獲得鎖之前，禁止軟件中斷,，但是會(huì)讓硬件中斷保持打開,。
2. 如果一個(gè)自旋鎖被運(yùn)行在了（硬件或軟件）中斷上下文中的代碼獲得，則必須使用某個(gè)禁止中斷形式的spin_lock,。
3. 釋放自旋鎖
void spin_unlock(spinlock_t *lock);
void spin_unlock_irqrestore(spinlock_t *lock, unsigned long flags);
void spin_unlock_irq(spinlock_t *lock);
void spin_unlock_bh(spinlock_t *lock);

4. 非阻塞的自旋操作
int spin_trylock(spinlock_t *lock);
int spin_trylock_bh(spinlock_t *lock);

讀取者和寫入者自旋鎖
1. 這種鎖允許任意數(shù)量的讀取者同時(shí)進(jìn)入臨界區(qū),，但寫入者必須互斥訪問。讀取者/寫入者具有rwlock_t類型
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);
這里沒有read_trylock函數(shù)可用,。

2. 寫入者的函數(shù)類似于讀取者
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);

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);
它們的與rwsem相似,，有可能造成讀取者饑餓。

鎖陷阱
不明確的規(guī)則
1. 不論是信號(hào)量還是自旋鎖,，都不允許第二次獲得這個(gè)鎖,，如果試圖這么做，系統(tǒng)將掛起,。

鎖的順序獲取
1. 在必須獲取多個(gè)鎖時(shí),，應(yīng)該始終以相同的順序獲得。如果我們必須獲得一個(gè)局部鎖,，以及一個(gè)屬于內(nèi)核更中心的位置的鎖,，
則應(yīng)該首先獲取自己的局部鎖。

細(xì)粒度鎖和粗粒度鎖的對(duì)比

除了鎖之外的辦法
面鎖算法
1. 如果寫入者看到的數(shù)據(jù)和讀取者看到的數(shù)據(jù)始終一致,，就有可能構(gòu)造一種免鎖的數(shù)據(jù)結(jié)構(gòu),。經(jīng)常用于免鎖的生產(chǎn)者/消費(fèi)者任務(wù)的
數(shù)據(jù)結(jié)構(gòu)之一是循環(huán)緩沖區(qū)。
一個(gè)循環(huán)緩沖區(qū)需要一個(gè)數(shù)組以及兩個(gè)索引值，一個(gè)用于要寫入新值的位置,，另一個(gè)用于下一個(gè)從緩沖區(qū)移走值的位置,。
只要寫入者在更新寫入索引之前將新的值保存到緩沖區(qū)中，則讀取者將始終看到一致的數(shù)據(jù)結(jié)構(gòu),。將flag最后更新。

原子變量
1. 一個(gè)atomic_t的變量在所有的內(nèi)核支持的架構(gòu)上保存一個(gè)int值,。

位操作
1,。
void set_bit(nr, void *addr)
void clear_bit(nr, void *addr)
void change_bit(nr, void *addr)
test_bit(nr, void *addr);該函數(shù)不必以原子方式實(shí)現(xiàn)的位操作。
int test_and_set_bit(nr, void *addr);
int test_and_clear_bit(nr, void *addr);
int test_and_change_bit(nr, void *addr);
設(shè)置同時(shí)返回這個(gè)位的先期值,。
2,。要以原子的方式獲得鎖并訪問某個(gè)共享數(shù)據(jù)的代碼，可以使用test_and_set_bit或者test_and_clear_bit,。

Seqlock
1.seqlock會(huì)允許讀取者對(duì)資源的自由訪問,，但需要讀取者堅(jiān)持是否和寫入者發(fā)生沖突，當(dāng)發(fā)生沖突時(shí),，就需要重試對(duì)資源的訪問,。
2. seqlock通常不能用于保護(hù)包含有指針的數(shù)據(jù)結(jié)構(gòu)，因?yàn)閷懭胝咝薷脑摂?shù)據(jù)的同時(shí),，讀取者可能會(huì)追隨一個(gè)無(wú)效的指針,。

讀取-復(fù)制-更新
1。讀取-復(fù)制-更新(read-copy-update RCU)也是一種高級(jí)的互斥機(jī)制,。
2,。 rcu_read_lock調(diào)用非常快,，它會(huì)禁止內(nèi)核搶占,，但不會(huì)等待任何東西。
3,。 寫入代碼必須等待直到能夠確信不存在這樣的引用,。