Linux的原子操作與同步機(jī)制

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

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

3、加讀取的值。3）將修改的值寫回count內(nèi)存。這又回到前面并發(fā)問題類似的情況，只不過此時(shí)并發(fā)的主題不再是進(jìn)程，而是處理器。Intel x86指令集提供了指令前綴lock用于鎖定前端串行總線（FSB），保證了指令執(zhí)行時(shí)不會(huì)受到其他處理器的干擾。使用lock指令前綴后，處理器間對(duì)count內(nèi)存的并發(fā)訪問（讀/寫）被禁止，從而保證了指令的原子性。x86原子操作實(shí)現(xiàn)Linux的源碼中x86體系結(jié)構(gòu)原子操作的定義文件為。linux2.6/include/asm-i386/atomic.h文件內(nèi)定義了原子類型atomic_t，其僅有一個(gè)字段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可見，在對(duì)稱多處理器架構(gòu)的情況下，LOCK被解釋為指令前綴lock。而對(duì)于單處理器架構(gòu)，LOCK不包含任何內(nèi)容。arm原子操作實(shí)現(xiàn)在arm的指令集中，不存在指令前綴lock，那如何完成原子操作呢？Linux的源碼中arm體系結(jié)構(gòu)原子操作的定義文件為。linux2.6/include/asm-arm/atomic.h其中自加原子操作由函數(shù)atomic_add_return實(shí)現(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;上述嵌入式匯編的實(shí)際形式為。1:ldrex  result, v->counteradd    result, result, istrex  temp, result, v->counterteq    temp, #0bne    1bldrex指令將v->counter的值傳送到result，并設(shè)置全局標(biāo)記“Exclusive”。add指令完成“result+i”的操作，并將加法結(jié)果保存

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

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

13、方式完成原子的數(shù)據(jù)交換，但是影響系統(tǒng)性能。ARMv6之后，一般使用ldrex和strex指令對(duì)代替swp指令的功能。自旋鎖中的原子操作Linux的源碼中x86體系結(jié)構(gòu)自旋鎖的定義文件為。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");上述代碼的實(shí)際匯編形式為。1：lock   decb lock->slockjns    32:rep    nopcmpb 

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

17、，這樣保證了其他進(jìn)程可以獲得自旋鎖。信號(hào)量中的原子操作Linux的源碼中x86體系結(jié)構(gòu)自旋鎖的定義文件為。linux2.6/include/asm-i386/.h信號(hào)量的申請操作由函數(shù)down實(shí)現(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");實(shí)際的匯編代碼形式為。lock   decl sem->countjs 21:<= another section =>2:lea    sem->count, eaxcall   _down_failedjmp 1信號(hào)量的sem->count一般初始化為一個(gè)正整數(shù)，申請信號(hào)量時(shí)執(zhí)行原子操作decl，將sem->count減1。如果該值減為負(fù)數(shù)（符號(hào)位為1）則跳轉(zhuǎn)到另一個(gè)段內(nèi)的標(biāo)簽2，否則申請信號(hào)量成功。標(biāo)簽2被編譯到另一個(gè)段內(nèi)，進(jìn)入標(biāo)簽2后，執(zhí)行l(wèi)ea指令取出

22、sem->count的地址，放到eax寄存器作為參數(shù)，然后調(diào)用函數(shù)_down_failed表示信號(hào)量申請失敗，進(jìn)程加入等待隊(duì)列。最后跳回標(biāo)簽1結(jié)束信號(hào)量申請。信號(hào)量的釋放操作由函數(shù)up實(shí)現(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