1、Linux的原子操作與同步機制 并發(fā)問題現(xiàn)代操作系統(tǒng)支持多任務的并發(fā)，并發(fā)在提高計算資源利用率的同時也帶來了資源競爭的問題。例如C語言語句“count+;”在未經(jīng)編譯器優(yōu)化時生成的匯編代碼為。當操作系統(tǒng)內(nèi)存在多個進程同時執(zhí)行這段代碼時，就可能帶來并發(fā)問題。假設count變量初始值為0。進程1執(zhí)行完“mov eax, count”后，寄存器eax內(nèi)保存了count的值0。此時，進程2被調(diào)度執(zhí)行，搶占了進程1的CPU的控制權。進程2執(zhí)行“count+;”的匯編代碼，將累加后的count值1寫回到內(nèi)存。然后，進程1再次被調(diào)度執(zhí)行，CPU控制權回到進程1。進程1接著執(zhí)行，計算count的累加

2、值仍為1，寫回到內(nèi)存。雖然進程1和進程2執(zhí)行了兩次“count+;”操作，但是count實際的內(nèi)存值為1，而不是2！單處理器原子操作解決這個問題的方法是，將“count+;”語句翻譯為單指令操作。Intel x86指令集支持內(nèi)存操作數(shù)的inc操作，這樣“count+;”操作可以在一條指令內(nèi)完成。因為進程的上下文切換是在總是在一條指令執(zhí)行完成后，所以不會出現(xiàn)上述的并發(fā)問題。對于單處理器來說，一條處理器指令就是一個原子操作。多處理器原子操作但是在多處理器的環(huán)境下，例如SMP架構，這個結論不再成立。我們知道“inc count”指令的執(zhí)行過程分為三步：1）從內(nèi)存將count的數(shù)據(jù)讀取到cpu。2）累

3、加讀取的值。3）將修改的值寫回count內(nèi)存。這又回到前面并發(fā)問題類似的情況，只不過此時并發(fā)的主題不再是進程，而是處理器。Intel x86指令集提供了指令前綴lock用于鎖定前端串行總線（FSB），保證了指令執(zhí)行時不會受到其他處理器的干擾。使用lock指令前綴后，處理器間對count內(nèi)存的并發(fā)訪問（讀/寫）被禁止，從而保證了指令的原子性。x86原子操作實現(xiàn)Linux的源碼中x86體系結構原子操作的定義文件為。linux2.6/include/asm-i386/atomic.h文件內(nèi)定義了原子類型atomic_t，其僅有一個字段counter，用于保存32位的數(shù)據(jù)。typedef struct

4、 volatile int counter; atomic_t;其中原子操作函數(shù)atomic_inc完成自加原子操作。/* * atomic_inc - increment atomic variable * v: pointer of type atomic_t *  * Atomically increments v by 1. */static _inline_ void atomic_inc(atomic_t *v)    _asm_ _volatile_(    &

5、#160;  LOCK "incl %0"       :"=m" (v->counter)       :"m" (v->counter);其中LOCK宏的定義為。#ifdef CONFIG_SMP    #define LOCK "lock ; "#else    #define LOCK ""

6、;#endif可見，在對稱多處理器架構的情況下，LOCK被解釋為指令前綴lock。而對于單處理器架構，LOCK不包含任何內(nèi)容。arm原子操作實現(xiàn)在arm的指令集中，不存在指令前綴lock，那如何完成原子操作呢？Linux的源碼中arm體系結構原子操作的定義文件為。linux2.6/include/asm-arm/atomic.h其中自加原子操作由函數(shù)atomic_add_return實現(xiàn)。static inline int atomic_add_return(int i, atomic_t *v)    unsigned long tmp;  

7、  int result;    _asm_ _volatile_(" atomic_add_returnn"       "1:     ldrex   %0, %2n"       "       add     %0, %0

8、, %3n"       "       strex   %1, %0, %2n"       "       teq     %1, #0n"       " 

9、0;     bne     1b"       : "=&r" (result), "=&r" (tmp)       : "r" (&v->counter), "Ir" (i)       : "cc&qu

10、ot;);    return result;上述嵌入式匯編的實際形式為。1:ldrex  result, v->counteradd    result, result, istrex  temp, result, v->counterteq    temp, #0bne    1bldrex指令將v->counter的值傳送到result，并設置全局標記“Exclusive”。add指令完成“result+i”的操作，并將加法結果保存

11、到result。strex指令首先檢測全局標記“Exclusive”是否存在，如果存在，則將result的值寫回counter->v，并將temp置為0，清除“Exclusive”標記，否則直接將temp置為1結束。teq指令測試temp值是否為0。bne指令temp不等于0時跳轉到標號1，其中字符b表示向后跳轉。整體看來，上述匯編代碼一直嘗試完成“v->counter+=i”的操作，直到temp為0時結束。使用ldrex和strex指令對是否可以保證add指令的原子性呢？假設兩個進程并發(fā)執(zhí)行“l(fā)drex+add+strex”操作，當進程1執(zhí)行l(wèi)drex后設定了全局標記“Exclu

12、sive”。此時切換到進程2，執(zhí)行l(wèi)drex前全局標記“Exclusive”已經(jīng)設定，ldrex執(zhí)行后重復設定了該標記。然后執(zhí)行add和strex指令，完成累加操作。再次切換回進程1，接著執(zhí)行add指令，當執(zhí)行strex指令時，由于“Exclusive”標記被進程2清除，因此不執(zhí)行傳送操作，將temp設置為1。后繼teq指令測定temp不等于0，則跳轉到起始位置重新執(zhí)行，最終完成累加操作！可見ldrex和strex指令對可以保證進程間的同步。多處理器的情況與此相同，因為arm的原子操作只關心“Exclusive”標記，而不在乎前端串行總線是否加鎖。在ARMv6之前，swp指令就是通過鎖定總線的

13、方式完成原子的數(shù)據(jù)交換，但是影響系統(tǒng)性能。ARMv6之后，一般使用ldrex和strex指令對代替swp指令的功能。自旋鎖中的原子操作Linux的源碼中x86體系結構自旋鎖的定義文件為。linux2.6/include/asm-i386/spinlock.h其中_raw_spin_lock完成自旋鎖的加鎖功能#define _raw_spin_lock_string     "n1:t"     "lock ; decb %0nt"     "jns 3f

14、n"     "2:t"     "rep;nopnt"     "cmpb $0,%0nt"     "jle 2bnt"     "jmp 1bn"     "3:nt"static inline void _raw_spin_lock(raw_spinlock_t *lock)

15、60;   _asm_ _volatile_(       _raw_spin_lock_string       :"=m" (lock->slock) : : "memory");上述代碼的實際匯編形式為。1：lock   decb lock->slockjns    32:rep    nopcmpb 

16、0; $0, lock->slockjle    2jmp    13:其中l(wèi)ock->slock字段初始值為1，執(zhí)行原子操作decb后值為0。符號位為0，執(zhí)行jns指令跳轉到3，完成自旋鎖的加鎖。當再次申請自旋鎖時，執(zhí)行原子操作decb后lock->slock值為-1。符號位為1，不執(zhí)行jns指令。進入標簽2，執(zhí)行一組nop指令后比較lock->slock是否小于等于0，如果小于等于0回到標簽2進行循環(huán)（自旋）。否則跳轉到標簽1重新申請自旋鎖，直到申請成功。自旋鎖釋放時會將lock->slock設置為1

17、，這樣保證了其他進程可以獲得自旋鎖。信號量中的原子操作Linux的源碼中x86體系結構自旋鎖的定義文件為。linux2.6/include/asm-i386/.h信號量的申請操作由函數(shù)down實現(xiàn)。/* * This is ugly, but we want the default case to fall through. * "_down_failed" is a special asm handler that calls the C * routine that actually waits. See arch/i386/kernel/

18、semaphore.c */static inline void down(struct semaphore * sem)    might_sleep();    _asm_ _volatile_(       "# atomic down operationnt"       LOCK "decl %0nt"     /*

19、-sem->count */       "js 2fn"       "1:n"       LOCK_SECTION_START("")       "2:tlea %0,%eaxnt"       "

20、;call _down_failednt"       "jmp 1bn"       LOCK_SECTION_END       :"=m" (sem->count)       :       :"memory",&q

21、uot;ax");實際的匯編代碼形式為。lock   decl sem->countjs 21:<= another section =>2:lea    sem->count, eaxcall   _down_failedjmp 1信號量的sem->count一般初始化為一個正整數(shù)，申請信號量時執(zhí)行原子操作decl，將sem->count減1。如果該值減為負數(shù)（符號位為1）則跳轉到另一個段內(nèi)的標簽2，否則申請信號量成功。標簽2被編譯到另一個段內(nèi)，進入標簽2后，執(zhí)行l(wèi)ea指令取出

22、sem->count的地址，放到eax寄存器作為參數(shù)，然后調(diào)用函數(shù)_down_failed表示信號量申請失敗，進程加入等待隊列。最后跳回標簽1結束信號量申請。信號量的釋放操作由函數(shù)up實現(xiàn)。/* * Note! This is subtle. We jump to wake people up only if * the semaphore was negative (= somebody was waiting on it). * The default case (no contention) will result in NO * jumps

23、 for both down() and up(). */static inline void up(struct semaphore * sem)    _asm_ _volatile_(       "# atomic up operationnt"       LOCK "incl %0nt"     /* +sem->count */       "jle 2fn"       "1:n"       LOCK_SECTION_START("")       "2:tlea %0,%eax