并發(fā)和競態(tài)實用教案

1、原子(yunz)操作 考慮將整數(shù)變量加1的操作i+怎么實現(xiàn)(shxin)？ 得到當(dāng)前變量i的值并且拷貝到一個寄存器中 將寄存器中的值加1 把i的新值寫回到內(nèi)存中 設(shè)i為全局變量，初始值為7，有兩個線程欲對其施行i+操作，結(jié)果會怎樣？期望(qwng)的結(jié)果！Thread 1get i (7)increment i (7-8)write back i (8)-Thread 2-get i (8)increment i (8-9)write back i (9)第1頁/共52頁第一頁，共53頁。可能(knng)出現(xiàn)的結(jié)果！若能把讀、加與寫回指令(zhlng)作為一個不可分割的整體執(zhí)行，也能得到正確結(jié)

2、果錯誤(cuw)的結(jié)果！原子操作原子操作Thread 1get i (7)increment i (7-8)-write back i (8)-Thread 2get i (7)-increment i (7-8)-write back i (8)Thread 1get &increment &store (7-8)-Thread 2-get& increment&store i (8-9)這種“不可分割”的操作即為“原子操作”一些處理器架構(gòu)提供了進(jìn)行讀、加與回寫操的單條指令第2頁/共52頁第二頁，共53頁。原子(yunz)操作 linux提供(tgng)了進(jìn)行

3、這類操作的方法，稱為原子操作，定義在中 原子操作是非?？斓? 因為它們在可能時會編譯成一條機(jī)器指令 Linux的原子操作包括原子整數(shù)操作與原子位操作，整數(shù)類型atomic_t，24位。因sparc沒有(mi yu)單條指令進(jìn)行這類操作，故用32位中的低8位來做鎖。為了兼容，其他架構(gòu)也如此。get i (7)increment i (7-8)write back i (8)lockunlock臨界區(qū)第3頁/共52頁第三頁，共53頁。原子(yunz)操作 原子操作不是指加一的操作，而是指不被中斷(zhngdun)的操作。即要么不做，一做就要做完，其間決不停頓。原子操作分為整數(shù)操作與位操作兩種類型

4、1. 原子整數(shù)操作 atomic_t v; /* define v */ atomic_t u = ATOMIC_INIT(0); /* define u and initialize it to zero */ atomic_set(&v, 4); /* v = 4 (atomically) */ atomic_add(2, &v); /* v = v + 2 = 6 (atomically) */ atomic_inc(&v); /* v = v + 1 = 7 (atomically) */ int atomic_dec_and_test(atomic_t *v)

5、 第4頁/共52頁第四頁，共53頁。原子(yunz)操作原子(yunz)操作接口列表第5頁/共52頁第五頁，共53頁。原子(yunz)操作第6頁/共52頁第六頁，共53頁。原子(yunz)操作2. 原子位操作atomic_t 類型在進(jìn)行整數(shù)算術(shù)操作時是不錯的. 但是當(dāng)你需要以原子方式操作單個位時, 它無法工作。 為此, 內(nèi)核提供了一套函數(shù)來原子地修改或測試(csh)單個位，整個操作發(fā)生在單步內(nèi), 沒有中斷(或者其他處理器)能干擾原子位操作執(zhí)行很快, 因為它們使用單條機(jī)器指令來進(jìn)行操作, 而在任何低層平臺做的時候不用禁止中斷位操作函數(shù)在 中聲明 位操作是對內(nèi)存地址進(jìn)行的操作，參數(shù)是一個指針和一個

6、位號，指針指向內(nèi)存地址，位號指明操作的位第7頁/共52頁第七頁，共53頁。原子(yunz)操作 位操作接口： void set_bit(nr, void *addr); 設(shè)置 addr 指向(zh xin)的數(shù)據(jù)項的第 nr 位. void clear_bit(nr, void *addr); 清除 addr 指向(zh xin)的數(shù)據(jù)項的第nr位. void change_bit(nr, void *addr); 翻轉(zhuǎn)指定的位. 第8頁/共52頁第八頁，共53頁。原子(yunz)操作 test_bit(nr, void *addr); 返回指定位的當(dāng)前值. int test_and_set_

7、bit(nr, void *addr); 設(shè)置指定的位，并返回其原先(yunxin)的值 int test_and_clear_bit(nr, void *addr); 清除指定的位，并返回其原先(yunxin)的值 int test_and_change_bit(nr, void *addr); 翻轉(zhuǎn)指定的位，并返回其原先(yunxin)的值第9頁/共52頁第九頁，共53頁。原子(yunz)操作 例 可以(ky)使用位操作來管理一個鎖變量以控制對某個共享數(shù)據(jù)項的訪問。假定這個位是 0時鎖空閑,非零時鎖忙。while (test_and_set_bit(nr, addr) != 0) wait

8、_for_a_while(); if (test_and_clear_bit(nr, addr) = 0) something_went_wrong(); 共享數(shù)據(jù)項 第10頁/共52頁第十頁，共53頁。第第5 章章 并發(fā)并發(fā)(bngf)和競態(tài)和競態(tài)原子(yunz)操作 自旋(z xun)鎖 信號量scull的缺陷 在scull中使用信號量 第11頁/共52頁第十一頁，共53頁。自旋(z xun)鎖 自旋鎖是一個互斥設(shè)備, 它只能有 2 個值:“上鎖”和“解鎖”. 它通常實現(xiàn)(shxin)為某個整數(shù)值中的單個位. 希望獲取特定鎖的代碼測試相關(guān)的位， 如果鎖是可用的, 這個“上鎖”位被置位并且代

9、碼繼續(xù)進(jìn)入臨界區(qū)；相反, 如果這個鎖已經(jīng)被別人獲得, 代碼進(jìn)入一個忙循環(huán)中反復(fù)檢查這個鎖, 直到它變?yōu)榭捎? 這個循環(huán)就是自旋鎖的“自旋”部分。自旋意味著“抱著CPU空轉(zhuǎn)”也可不“自旋”,即讓出CPU,自已睡眠等待,鑰匙放出來時讓別人(birn)喚醒。此即為“信號量”,其可被稱為“睡眠鎖”自旋鎖與信號量孰優(yōu)孰劣？短時用自旋鎖，長時用信號量P5？第12頁/共52頁第十二頁，共53頁。自旋(z xun)鎖 在單處理器系統(tǒng)上，若停用內(nèi)核搶占，自旋鎖定義(dngy)為空操作，因為不存在幾個CPU同時進(jìn)入臨界區(qū)的情況；若啟用了內(nèi)核搶占，就跟SMP系統(tǒng)類似，可能存在多個內(nèi)核控制路徑同時進(jìn)入臨界區(qū)的情況，自

10、旋鎖不能定義(dngy)為空操作，但spin_lock(基本上）等價于preempt_disable，而spin_unlock則等價于preempt_enable 自旋鎖原語要求頭文件 . 數(shù)據(jù)類型為 spinlock_t，第13頁/共52頁第十三頁，共53頁。自旋(z xun)鎖 與其他數(shù)據(jù)結(jié)構(gòu)一樣, 自旋鎖必須初始化。 可以在編譯時完成（靜態(tài)(jngti)初如化）, 也可以在運行時完成（動態(tài)初始化）。 靜態(tài)(jngti)初始化 spinlock_t my_lock = SPIN_LOCK_UNLOCKED; 動態(tài)初始化 void spin_lock_init(spinlock_t *loc

11、k); 在進(jìn)入一個臨界區(qū)前, 你的代碼必須獲得需要的鎖: void spin_lock(spinlock_t *lock); 為釋放一個已獲得的鎖, 必須調(diào)用下面函數(shù): void spin_unlock(spinlock_t *lock);第14頁/共52頁第十四頁，共53頁。自旋(z xun)鎖 自旋鎖的使用 spinlock_t mr_lock = SPIN_LOCK_UNLOCKED; spin_lock(&mr_lock); /* critical region */ spin_unlock(&mr_lock); 自旋鎖使用規(guī)則 擁有自旋鎖的代碼必須(bx)是原子的 擁

12、有自旋鎖時不能夠睡眠 在中斷處理程序中可使用自旋鎖，但擁有前必須(bx)禁止本地中斷 擁有自旋鎖的時間必須(bx)盡可能短第15頁/共52頁第十五頁，共53頁。自旋(z xun)鎖 內(nèi)核(ni h)提供了獲取鎖前禁止中斷的接口 接口一，禁止中斷、保存中斷當(dāng)前狀態(tài)、獲取鎖 spinlock_t mr_lock = SPIN_LOCK_UNLOCKED; unsigned long flags; spin_lock_irqsave(&mr_lock, flags); /* critical region . */ spin_unlock_irqrestore(&mr_lock, f

13、lags); 接口二，禁止中斷、獲取鎖（適用于中斷打開的情況） spinlock_t mr_lock = SPIN_LOCK_UNLOCKED; spin_lock_irq(&mr_lock); /* critical section . */ spin_unlock_irq(&mr_lock); 第16頁/共52頁第十六頁，共53頁。自旋(z xun)鎖 自旋(z xun)鎖函 void spin_lock(spinlock_t *lock); void spin_lock_irqsave(spinlock_t *lock, unsigned long flags); voi

14、d 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); void spin_unlock_irq(spinlock_t *lock); void spin_unlock_bh(spinlock_t *lock);第17頁/共52頁第十七頁，共53頁。自旋(z xun)鎖 讀-

15、寫自旋鎖 對于讀、寫可分開的場合，內(nèi)核提供了讀-寫鎖，允許任意數(shù)量(shling)的讀者同時進(jìn)入臨界區(qū)，但寫者仍必須互斥訪問臨界區(qū)，類型為 rwlock_t，定義在 中。為何要造這種鎖？ 初始化 靜態(tài) rwlock_t my_rwlock = RW_LOCK_UNLOCKED; 動態(tài) rwlock_t my_rwlock; rwlock_init(&my_rwlock); 第18頁/共52頁第十八頁，共53頁。自旋(z xun)鎖 讀-寫自旋(z xun)鎖函數(shù) void read_lock(rwlock_t *lock); void read_lock_irqsave(rwlock_

16、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); 第19頁/共52頁第十九頁，共53頁。自旋(z

17、 xun)鎖 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 l

18、ong flags); void write_unlock_irq(rwlock_t *lock); void write_unlock_bh(rwlock_t *lock); 第20頁/共52頁第二十頁，共53頁。自旋(z xun)鎖 順序鎖seqlock 讀/寫鎖中，執(zhí)行read_lock的讀者與執(zhí)行write_lock的寫者具有相同的優(yōu)先級：讀者必須等待，直到寫操作完成；同樣，寫者也必須等待，直到讀操作完成。若讀者多，寫者得長時等待。 順序鎖中賦予寫者較高的優(yōu)先級：即使讀者正在讀的時候也允許(ynx)寫者繼續(xù)運行 順序鎖定義在 中，數(shù)據(jù)類型為seqlock_t，包括兩個字段：一個類型為s

19、pinlock_t的lock字段與一個整型的sequence字段順序計數(shù)器typedef struct unsigned sequence;spinlock_t lock; seqlock_t;第21頁/共52頁第二十一頁，共53頁。 寫者進(jìn)入臨界(ln ji)區(qū)時通過write_seqlock（）獲取鎖，同時使順序計數(shù)器加1；退出時通過write_seqlock()釋放鎖，同時再使順序計數(shù)器加1 讀者在進(jìn)入/退出臨界(ln ji)區(qū)時均要讀取順計器的值，若兩次讀到的值不同或為奇數(shù)，說明讀操作中有寫者進(jìn)入，因而數(shù)據(jù)無效，必須再次讀取 讀者代碼有如下面的形式: unsigned int seq;

20、 do seq = read_seqbegin(&the_lock); /* Do what you need to do */ while read_seqretry(&the_lock, seq);static _always_inline int read_seqretry(const seqlock_t *sl, unsigned start)smp_rmb();return (sl-sequence != start);第22頁/共52頁第二十二頁，共53頁。自旋(z xun)鎖 寫者必須獲取一個排他鎖來進(jìn)入由一個 seqlock 保護(hù)的臨界區(qū). 為此, 調(diào)用: vo

21、id write_seqlock(seqlock_t *lock); 寫鎖由一個自旋鎖實現(xiàn), 因此(ync)所有的通常的限制都適用調(diào)用下面函數(shù)來釋放鎖: void write_sequnlock(seqlock_t *lock); 第23頁/共52頁第二十三頁，共53頁。自旋(z xun)鎖 seqlock 適宜要保護(hù)的資源小、簡單、讀多、寫少的場合。 seqlock 用 2 種通常的方法(fngf)來初始化: 靜態(tài)初始化 seqlock_t lock1 = SEQLOCK_UNLOCKED; 動態(tài)初始化： seqlock_t lock2; seqlock_init(&lock2);

22、第24頁/共52頁第二十四頁，共53頁。自旋(z xun)鎖 其他(qt)順序鎖函數(shù) 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 *loc

23、k); void write_sequnlock_bh(seqlock_t *lock); unsigned int read_seqbegin_irqsave(seqlock_t *lock, unsigned long flags); int read_seqretry_irqrestore(seqlock_t *lock, unsigned int seq, unsigned long flags); 第25頁/共52頁第二十五頁，共53頁。第第5 章章 并發(fā)并發(fā)(bngf)和競態(tài)和競態(tài)原子(yunz)操作 自旋(z xun)鎖 信號量scull的缺陷 在scull中使用信號量 第26頁

24、/共52頁第二十六頁，共53頁。信號量 Linux 中的信號量是一種睡眠(shumin)鎖，如果一個任務(wù)試圖獲得一個已經(jīng)被占用的信號量時，信號量會將其推進(jìn)一個等待隊列，然后讓其睡眠(shumin) 中斷處理程序中不能使用信號量 信號量定義在，類型是 struct semaphore 信號量初始化 void sema_init(struct semaphore *sem, int val); val=1時為二值信號量、互斥體，類似鎖 val=0時同上，但初始狀態(tài)為鎖定 val1時，信號量數(shù)量第27頁/共52頁第二十七頁，共53頁。信號量 互斥體的另一種初始化（靜態(tài)( jngti)） DECLAR

25、E_MUTEX(name); 1 DECLARE_MUTEX_LOCKED(name);0 互斥體的動態(tài)初始化 void init_MUTEX(struct semaphore *sem); void init_MUTEX_LOCKED(struct semaphore *sem); 信號量的申請 void down(struct semaphore *sem); int down_interruptible(struct semaphore *sem);中斷返非0 int down_trylock(struct semaphore *sem); 不休眠,返非0第28頁/共52頁第二十八頁，共

26、53頁。信號量 信號量的釋放 void up(struct semaphore *sem); 信號量的使用 /* 定義并申明(shnmng)一個信號量，名為mr_sem,初始值為1 */ static DECLARE_MUTEX(mr_sem); if (down_interruptible(&mr_sem) /* signal received, semaphore not acquired . */ /* critical region . */ up(&mr_sem); 第29頁/共52頁第二十九頁，共53頁。信號量 讀-寫信號量 允許多個讀者擁有該信號量，但寫者有更高優(yōu)

27、先權(quán)：當(dāng)一個寫者進(jìn)入臨界區(qū)時, 就不會允許讀者進(jìn)入直到寫者完成了它們的工作。如果有大量的寫者競爭該信號量，則這種實現(xiàn)可能導(dǎo)致(dozh)讀者“餓死” ，長時間拒絕讀者訪問。 為此, 最好用在寫者少且占用時間短的場合。 定義在，數(shù)據(jù)類型struct rw_semaphore 初始化 void init_rwsem(struct rw_semaphore *sem); 第30頁/共52頁第三十頁，共53頁。信號量 只讀訪問(fngwn)接口 void down_read(struct rw_semaphore *sem); int down_read_trylock(struct rw_semap

28、hore *sem); void up_read(struct rw_semaphore *sem); 第31頁/共52頁第三十一頁，共53頁。信號量 寫者接口( ji ku) 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);第32頁/共52頁第三十二頁，共53頁。信號量 讀-寫信號量

29、使用(shyng) static DECLARE_RWSEM(mr_rwsem); down_read(&mr_rwsem); /* critical region (read only) . */ up_read(&mr_rwsem); /* . */ down_write(&mr_rwsem); /* critical region (read and write) . */ up_write(&mr_sem); 第33頁/共52頁第三十三頁，共53頁。完成(wn chng)變量completion 如果在內(nèi)核中一個任務(wù)需要發(fā)出信號通知另一個任務(wù)發(fā)生了某個特

30、定事件，利用完成變量是使兩個任務(wù)得以同步的簡單方法。如果一個任務(wù)要執(zhí)行一些工作時，另一個任務(wù)就會在完成變量上等待。當(dāng)這個(zh ge)任務(wù)完成工作后，會使用完成變量去喚醒在等待的任務(wù)。 定義在，類型struct completion 初始化 DECLARE_COMPLETION(mr_comp); init_completion() ;第34頁/共52頁第三十四頁，共53頁。第第5 章章 并發(fā)并發(fā)(bngf)和競態(tài)和競態(tài)原子(yunz)操作 自旋(z xun)鎖 信號量scull的缺陷 在scull中使用信號量 第35頁/共52頁第三十五頁，共53頁。Scull的缺陷(quxin) Scull

31、_write中設(shè)有A、B兩進(jìn)程同時(tngsh)到達(dá)下面的if語句 if (!dptr-datas_pos) dptr-datas_pos = kmalloc(quantum, GFP_KERNEL); if (!dptr-datas_pos) goto out; struct scull_qset void *data; struct scull_qset *next;l如果(rgu)dptr-datas_pos=NULL，兩者都會申請分配內(nèi)存，結(jié)果都賦給dptr，后者將覆蓋前者，前者分配到的內(nèi)存將丟失，造成內(nèi)存泄漏struct scull_qset *dptr第36頁/共52頁第三十六頁，

32、共53頁。Scull的缺陷(quxin) Scull中用什么工具來保護(hù)臨界區(qū)？ 信號量？ 自旋(z xun)鎖？ scull只適合用信號量 struct scull_dev struct scull_qset *data; /* Pointer to first quantum set */ int quantum; /* the current quantum size */ int qset; /* the current array size */ unsigned long size; /* amount of data stored here */ unsigned int acce

33、ss_key; /* used by sculluid and scullpriv */ struct semaphore sem; /* mutual exclusion semaphore */ struct cdev cdev; /* Char device structure */ ; 第37頁/共52頁第三十七頁，共53頁。第第5 章章 并發(fā)并發(fā)(bngf)和競態(tài)和競態(tài)原子(yunz)操作 自旋(z xun)鎖 信號量scull的缺陷 在scull中使用信號量 第38頁/共52頁第三十八頁，共53頁。在scull中使用(shyng)信號 信號量在使用前必須初始化。 scull 在加載

34、時進(jìn)行( jnxng)這個初始化: for (i = 0; i sem) return -ERESTARTSYS; if (!dptr-datas_pos) dptr-datas_pos = kmalloc(quantum, GFP_KERNEL); if (!dptr-datas_pos) goto out; out: up(&dev-sem); return retval;第40頁/共52頁第四十頁，共53頁?？焖?kui s)參考 #include DECLARE_MUTEX(name); DECLARE_MUTEX_LOCKED(name); void init_MUTEX(s

35、truct semaphore *sem); void init_MUTEX_LOCKED(struct semaphore *sem); void down(struct semaphore *sem); int down_interruptible(struct semaphore *sem); int down_trylock(struct semaphore *sem); void up(struct semaphore *sem); struct rw_semaphore; init_rwsem(struct rw_semaphore *sem); 第41頁/共52頁第四十一頁，共5

36、3頁。快速(kui s)參考 void down_read(struct rw_semaphore *sem); int down_read_trylock(struct rw_semaphore *sem); 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); #include DECLARE_COM

37、PLETION(name); init_completion(struct completion *c); INIT_COMPLETION(struct completion c); 第42頁/共52頁第四十二頁，共53頁?？焖?kui s)參考 void wait_for_completion(struct completion *c); void complete(struct completion *c); void complete_all(struct completion *c); void complete_and_exit(struct completion *c, long

38、retval); #include spinlock_t lock = SPIN_LOCK_UNLOCKED; spin_lock_init(spinlock_t *lock); void spin_lock(spinlock_t *lock); void spin_lock_irqsave(spinlock_t *lock, unsigned long flags); void spin_lock_irq(spinlock_t *lock); void spin_lock_bh(spinlock_t *lock); 第43頁/共52頁第四十三頁，共53頁?？焖?kui s)參考 int sp

39、in_trylock(spinlock_t *lock); int spin_trylock_bh(spinlock_t *lock); 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); rwlock_t lock = RW_LOCK_UNLOCKED rwlock_init(rwl

40、ock_t *lock); 第44頁/共52頁第四十四頁，共53頁?？焖?kui s)參考 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 lon

41、g flags); void read_unlock_irq(rwlock_t *lock); void read_unlock_bh(rwlock_t *lock); 第45頁/共52頁第四十五頁，共53頁?？焖?kui s)參考 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_unlo

42、ck(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); 第46頁/共52頁第四十六頁，共53頁?？焖?kui s)參考 #include atomic_t v = ATOMIC_INIT(value); void atomic_set(atomic_t *v, int i); int atomic_read(atomic_t

43、*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

44、*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); 第47頁/共52頁第四十七頁，共53頁?？焖?kui s)參考 #include 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_and_clear_bit(nr, void *addr); int test_and_change_bit(nr, void *addr); 第48頁/共52頁第四十八頁，共53頁?？焖?kui s)參考 #include seqlock_t lock = SEQLOCK_UNLOCKED; seqlock_ini