原子操作、信号量、讀寫信号量和自旋鎖

本系列文章分兩部分，第一部分詳細地介紹了 Linux 核心中的同步機制：原子操作、信号量、讀寫信号量和自旋鎖的API，使用要求以及一些典型示例。第二部分将詳細介紹在Linux核心中的另外一些同步機制，包括大核心鎖、讀寫鎖、大讀者鎖、RCU和順序鎖。

一、 引言

在現代作業系統裡，同一時間可能有多個核心執行流在執行，是以核心其實象多程序多線程程式設計一樣也需要一些同步機制來同步各執行單元對共享資料的訪 問。尤其是在多處理器系統上，更需要一些同步機制來同步不同處理器上的執行單元對共享的資料的通路。在主流的Linux核心中包含了幾乎所有現代的操作系 統具有的同步機制，這些同步機制包括：原子操作、信号量（semaphore）、讀寫信号量（rw_semaphore）、spinlock、 BKL(Big Kernel Lock)、rwlock、brlock（隻包含在2.4核心中）、RCU（隻包含在2.6核心中）和seqlock（隻包含在2.6核心中）。

本文的下面各章節将詳細講述每一種同步機制的原理、用途、API以及典型應用示例。

二、原子操作

所謂原子操作，就是該操作絕不會在執行完畢前被任何其他任務或事件打斷，也就說，它的最小的執行機關，不可能有比它更小的執行機關，是以這裡的原子實際是使用了實體學裡的物質微粒的概念。

原子操作需要硬體的支援，是以是架構相關的，其API和原子類型的定義都定義在核心源碼樹的include/asm/atomic.h檔案中，它們都使用彙編語言實作，因為C語言并不能實作這樣的操作。

原子操作主要用于實作資源計數，很多引用計數(refcnt)就是通過原子操作實作的。

原子類型定義如下：

typedef struct { volatile int counter; } atomic_t;

volatile修飾字段告訴gcc不要對該類型的資料做優化處理，對它的通路都是對記憶體的通路，而不是對寄存器的通路。

原子操作API包括：

atomic_read(atomic_t * v);

該函數對原子類型的變量進行原子讀操作，它傳回原子類型的變量v的值。

atomic_set(atomic_t * v, int i);

該函數設定原子類型的變量v的值為i。

void atomic_add(int i, atomic_t *v);

該函數給原子類型的變量v增加值i。

atomic_sub(int i, atomic_t *v);

該函數從原子類型的變量v中減去i。

int atomic_sub_and_test(int i, atomic_t *v);

該函數從原子類型的變量v中減去i，并判斷結果是否為0，如果為0，傳回真，否則傳回假。

void atomic_inc(atomic_t *v);

該函數對原子類型變量v原子地增加1。

void atomic_dec(atomic_t *v);

該函數對原子類型的變量v原子地減1。

int atomic_dec_and_test(atomic_t *v);

該函數對原子類型的變量v原子地減1，并判斷結果是否為0，如果為0，傳回真，否則傳回假。

int atomic_inc_and_test(atomic_t *v);

該函數對原子類型的變量v原子地增加1，并判斷結果是否為0，如果為0，傳回真，否則傳回假。

int atomic_add_negative(int i, atomic_t *v);

該函數對原子類型的變量v原子地增加I，并判斷結果是否為負數，如果是，傳回真，否則傳回假。

int atomic_add_return(int i, atomic_t *v);

該函數對原子類型的變量v原子地增加i，并且傳回指向v的指針。

int atomic_sub_return(int i, atomic_t *v);

該函數從原子類型的變量v中減去i，并且傳回指向v的指針。

int atomic_inc_return(atomic_t * v);

該函數對原子類型的變量v原子地增加1并且傳回指向v的指針。

int atomic_dec_return(atomic_t * v);

該函數對原子類型的變量v原子地減1并且傳回指向v的指針。

原子操作通常用于實作資源的引用計數，在TCP/IP協定棧的IP碎片進行中，就使用了引用計數，碎片隊列結構struct ipq描述了一個IP碎片，字段refcnt就是引用計數器，它的類型為atomic_t，當建立IP碎片時（在函數ip_frag_create中）， 使用atomic_set函數把它設定為1，當引用該IP碎片時，就使用函數atomic_inc把引用計數加1，當不需要引用該IP碎片時，就使用函數 ipq_put來釋放該IP碎片，ipq_put使用函數atomic_dec_and_test把引用計數減1并判斷引用計數是否為0，如果是就釋放 IP碎片。函數ipq_kill把IP碎片從ipq隊列中删除，并把該删除的IP碎片的引用計數減1（通過使用函數atomic_dec實作）。

三、信号量（semaphore）

Linux核心的信号量在概念和原理上與使用者态的System V的IPC機制信号量是一樣的，但是它絕不可能在核心之外使用，是以它與System V的IPC機制信号量毫不相幹。

信号量在建立時需要設定一個初始值，表示同時可以有幾個任務可以通路該信号量保護的共享資源，初始值為1就變成互斥鎖（Mutex），即同時隻能有 一個任務可以通路信号量保護的共享資源。一個任務要想通路共享資源，首先必須得到信号量，擷取信号量的操作将把信号量的值減1，若目前信号量的值為負數， 表明無法獲得信号量，該任務必須挂起在該信号量的等待隊列等待該信号量可用；若目前信号量的值為非負數，表示可以獲得信号量，因而可以立刻通路被該信号量 保護的共享資源。當任務通路完被信号量保護的共享資源後，必須釋放信号量，釋放信号量通過把信号量的值加1實作，如果信号量的值為非正數，表明有任務等待 目前信号量，是以它也喚醒所有等待該信号量的任務。

信号量的API有：

DECLARE_MUTEX(name)

該宏聲明一個信号量name并初始化它的值為0，即聲明一個互斥鎖。

DECLARE_MUTEX_LOCKED(name)

該宏聲明一個互斥鎖name，但把它的初始值設定為0，即鎖在建立時就處在已鎖狀态。是以對于這種鎖，一般是先釋放後獲得。

void sema_init (struct semaphore *sem, int val);

該函用于數初始化設定信号量的初值，它設定信号量sem的值為val。

void init_MUTEX (struct semaphore *sem);

該函數用于初始化一個互斥鎖，即它把信号量sem的值設定為1。

void init_MUTEX_LOCKED (struct semaphore *sem);

該函數也用于初始化一個互斥鎖，但它把信号量sem的值設定為0，即一開始就處在已鎖狀态。

void down(struct semaphore * sem);

該函數用于獲得信号量sem，它會導緻睡眠，是以不能在中斷上下文（包括IRQ上下文和softirq上下文）使用該函數。該函數将把sem的值減1，如果信号量sem的值非負，就直接傳回，否則調用者将被挂起，直到别的任務釋放該信号量才能繼續運作。

int down_interruptible(struct semaphore * sem);

該函數功能與down類似，不同之處為，down不會被信号（signal）打斷，但down_interruptible能被信号打斷，是以該函數有傳回值來區分是正常傳回還是被信号中斷，如果傳回0，表示獲得信号量正常傳回，如果被信号打斷，傳回-EINTR。

int down_trylock(struct semaphore * sem);

該函數試着獲得信号量sem，如果能夠立刻獲得，它就獲得該信号量并傳回0，否則，表示不能獲得信号量sem，傳回值為非0值。是以，它不會導緻調用者睡眠，可以在中斷上下文使用。

void up(struct semaphore * sem);

該函數釋放信号量sem，即把sem的值加1，如果sem的值為非正數，表明有任務等待該信号量，是以喚醒這些等待者。

信号量在絕大部分情況下作為互斥鎖使用，下面以console驅動系統為例說明信号量的使用。

在核心源碼樹的kernel/printk.c中，使用宏DECLARE_MUTEX聲明了一個互斥鎖console_sem，它用于保護 console驅動清單console_drivers以及同步對整個console驅動系統的通路，其中定義了函數 acquire_console_sem來獲得互斥鎖console_sem，定義了release_console_sem來釋放互斥鎖 console_sem，定義了函數try_acquire_console_sem來盡力得到互斥鎖console_sem。這三個函數實際上是分别對 函數down，up和down_trylock的簡單包裝。需要通路console_drivers驅動清單時就需要使用 acquire_console_sem來保護console_drivers清單，當通路完該清單後，就調用release_console_sem釋 放信号量console_sem。函數 console_unblank，console_device，console_stop，console_start，register_console 和unregister_console都需要通路console_drivers，是以它們都使用函數對acquire_console_sem和 release_console_sem來對console_drivers進行保護。

四、讀寫信号量（rw_semaphore）

讀寫信号量對通路者進行了細分，或者為讀者，或者為寫者，讀者在保持讀寫信号量期間隻能對該讀寫信号量保護的共享資源進行讀通路，如果一個任務除了 需要讀，可能還需要寫，那麼它必須被歸類為寫者，它在對共享資源通路之前必須先獲得寫者身份，寫者在發現自己不需要寫通路的情況下可以降級為讀者。讀寫信 号量同時擁有的讀者數不受限制，也就說可以有任意多個讀者同時擁有一個讀寫信号量。如果一個讀寫信号量目前沒有被寫者擁有并且也沒有寫者等待讀者釋放信号 量，那麼任何讀者都可以成功獲得該讀寫信号量；否則，讀者必須被挂起直到寫者釋放該信号量。如果一個讀寫信号量目前沒有被讀者或寫者擁有并且也沒有寫者等 待該信号量，那麼一個寫者可以成功獲得該讀寫信号量，否則寫者将被挂起，直到沒有任何通路者。是以，寫者是排他性的，獨占性的。

讀寫信号量有兩種實作，一種是通用的，不依賴于硬體架構，是以，增加新的架構不需要重新實作它，但缺點是性能低，獲得和釋放讀寫信号量的開銷大；另 一種是架構相關的，是以性能高，擷取和釋放讀寫信号量的開銷小，但增加新的架構需要重新實作。在核心配置時，可以通過選項去控制使用哪一種實作。

讀寫信号量的相關API有：

DECLARE_RWSEM(name)

該宏聲明一個讀寫信号量name并對其進行初始化。

void init_rwsem(struct rw_semaphore *sem);

該函數對讀寫信号量sem進行初始化。

void down_read(struct rw_semaphore *sem);

讀者調用該函數來得到讀寫信号量sem。該函數會導緻調用者睡眠，是以隻能在程序上下文使用。

int down_read_trylock(struct rw_semaphore *sem);

該函數類似于down_read，隻是它不會導緻調用者睡眠。它盡力得到讀寫信号量sem，如果能夠立即得到，它就得到該讀寫信号量，并且傳回1，否則表示不能立刻得到該信号量，傳回0。是以，它也可以在中斷上下文使用。

void down_write(struct rw_semaphore *sem);

寫者使用該函數來得到讀寫信号量sem，它也會導緻調用者睡眠，是以隻能在程序上下文使用。

int down_write_trylock(struct rw_semaphore *sem);

該函數類似于down_write，隻是它不會導緻調用者睡眠。該函數盡力得到讀寫信号量，如果能夠立刻獲得，就獲得該讀寫信号量并且傳回1，否則表示無法立刻獲得，傳回0。它可以在中斷上下文使用。

void up_read(struct rw_semaphore *sem);

讀者使用該函數釋放讀寫信号量sem。它與down_read或down_read_trylock配對使用。如果down_read_trylock傳回0，不需要調用up_read來釋放讀寫信号量，因為根本就沒有獲得信号量。

void up_write(struct rw_semaphore *sem);

寫者調用該函數釋放信号量sem。它與down_write或down_write_trylock配對使用。如果down_write_trylock傳回0，不需要調用up_write，因為傳回0表示沒有獲得該讀寫信号量。

void downgrade_write(struct rw_semaphore *sem);

該函數用于把寫者降級為讀者，這有時是必要的。因為寫者是排他性的，是以在寫者保持讀寫信号量期間，任何讀者或寫者都将無法通路該讀寫信号量保護的 共享資源，對于那些目前條件下不需要寫通路的寫者，降級為讀者将，使得等待通路的讀者能夠立刻通路，進而增加了并發性，提高了效率。

讀寫信号量适于在讀多寫少的情況下使用，在linux核心中對程序的記憶體映像描述結構的通路就使用了讀寫信号量進行保護。在Linux中，每一個進 程都用一個類型為task_t或struct task_struct的結構來描述，該結構的類型為struct mm_struct的字段mm描述了程序的記憶體映像，特别是mm_struct結構的mmap字段維護了整個程序的記憶體塊清單，該清單将在程序生存期間被 大量地遍利或修改，是以mm_struct結構就有一個字段mmap_sem來對mmap的通路進行保護，mmap_sem就是一個讀寫信号量，在 proc檔案系統裡有很多程序記憶體使用情況的接口，通過它們能夠檢視某一程序的記憶體使用情況，指令free、ps和top都是通過proc來得到記憶體使用 資訊的，proc接口就使用down_read和up_read來讀取程序的mmap資訊。當程序動态地配置設定或釋放記憶體時，需要修改mmap來反映配置設定或 釋放後的記憶體映像，是以動态記憶體配置設定或釋放操作需要以寫者身份獲得讀寫信号量mmap_sem來對mmap進行更新。系統調用brk和munmap就使用 了down_write和up_write來保護對mmap的通路。

五、自旋鎖（spinlock）

自旋鎖與互斥鎖有點類似，隻是自旋鎖不會引起調用者睡眠，如果自旋鎖已經被别的執行單元保持，調用者就一直循環在那裡看是否該自旋鎖的保持者已經釋 放了鎖，"自旋"一詞就是是以而得名。由于自旋鎖使用者一般保持鎖時間非常短，是以選擇自旋而不是睡眠是非常必要的，自旋鎖的效率遠高于互斥鎖。

信号量和讀寫信号量适合于保持時間較長的情況，它們會導緻調用者睡眠，是以隻能在程序上下文使用（_trylock的變種能夠在中斷上下文使用）， 而自旋鎖适合于保持時間非常短的情況，它可以在任何上下文使用。如果被保護的共享資源隻在程序上下文通路，使用信号量保護該共享資源非常合适，如果對共巷 資源的通路時間非常短，自旋鎖也可以。但是如果被保護的共享資源需要在中斷上下文通路（包括底半部即中斷處理句柄和頂半部即軟中斷），就必須使用自旋鎖。

自旋鎖保持期間是搶占失效的，而信号量和讀寫信号量保持期間是可以被搶占的。自旋鎖隻有在核心可搶占或SMP的情況下才真正需要，在單CPU且不可搶占的核心下，自旋鎖的所有操作都是空操作。

跟互斥鎖一樣，一個執行單元要想通路被自旋鎖保護的共享資源，必須先得到鎖，在通路完共享資源後，必須釋放鎖。如果在擷取自旋鎖時，沒有任何執行單 元保持該鎖，那麼将立即得到鎖；如果在擷取自旋鎖時鎖已經有保持者，那麼擷取鎖操作将自旋在那裡，直到該自旋鎖的保持者釋放了鎖。

無論是互斥鎖，還是自旋鎖，在任何時刻，最多隻能有一個保持者，也就說，在任何時刻最多隻能有一個執行單元獲得鎖。

自旋鎖的API有：

spin_lock_init(x)

http://www.ibm.com/developerworks/cn/linux/l-synch/part1/

該宏用于初始化自旋鎖x。自旋鎖在真正使用前必須先初始化。該宏用于動态初始化。

DEFINE_SPINLOCK(x)

該宏聲明一個自旋鎖x并初始化它。該宏在2.6.11中第一次被定義，在先前的核心中并沒有該宏。

SPIN_LOCK_UNLOCKED

該宏用于靜态初始化一個自旋鎖。

DEFINE_SPINLOCK(x)等同于spinlock_t x = SPIN_LOCK_UNLOCKED

spin_is_locked(x)

該宏用于判斷自旋鎖x是否已經被某執行單元保持（即被鎖），如果是，傳回真，否則傳回假。

spin_unlock_wait(x)

該宏用于等待自旋鎖x變得沒有被任何執行單元保持，如果沒有任何執行單元保持該自旋鎖，該宏立即傳回，否則将循環在那裡，直到該自旋鎖被保持者釋放。

spin_trylock(lock)

該宏盡力獲得自旋鎖lock，如果能立即獲得鎖，它獲得鎖并傳回真，否則不能立即獲得鎖，立即傳回假。它不會自旋等待lock被釋放。

spin_lock(lock)

該宏用于獲得自旋鎖lock，如果能夠立即獲得鎖，它就馬上傳回，否則，它将自旋在那裡，直到該自旋鎖的保持者釋放，這時，它獲得鎖并傳回。總之，隻有它獲得鎖才傳回。

spin_lock_irqsave(lock, flags)

該宏獲得自旋鎖的同時把标志寄存器的值儲存到變量flags中并失效本地中斷。

spin_lock_irq(lock)

該宏類似于spin_lock_irqsave，隻是該宏不儲存标志寄存器的值。

spin_lock_bh(lock)

該宏在得到自旋鎖的同時失效本地軟中斷。

spin_unlock(lock)

該宏釋放自旋鎖lock，它與spin_trylock或spin_lock配對使用。如果spin_trylock傳回假，表明沒有獲得自旋鎖，是以不必使用spin_unlock釋放。

spin_unlock_irqrestore(lock, flags)

該宏釋放自旋鎖lock的同時，也恢複标志寄存器的值為變量flags儲存的值。它與spin_lock_irqsave配對使用。

spin_unlock_irq(lock)

該宏釋放自旋鎖lock的同時，也使能本地中斷。它與spin_lock_irq配對應用。

spin_unlock_bh(lock)

該宏釋放自旋鎖lock的同時，也使能本地的軟中斷。它與spin_lock_bh配對使用。

spin_trylock_irqsave(lock, flags)

該宏如果獲得自旋鎖lock，它也将儲存标志寄存器的值到變量flags中，并且失效本地中斷，如果沒有獲得鎖，它什麼也不做。是以如果能夠立即獲 得鎖，它等同于spin_lock_irqsave，如果不能獲得鎖，它等同于spin_trylock。如果該宏獲得自旋鎖lock，那需要使用 spin_unlock_irqrestore來釋放。

spin_trylock_irq(lock)

該宏類似于spin_trylock_irqsave，隻是該宏不儲存标志寄存器。如果該宏獲得自旋鎖lock，需要使用spin_unlock_irq來釋放。

spin_trylock_bh(lock)

該宏如果獲得了自旋鎖，它也将失效本地軟中斷。如果得不到鎖，它什麼也不做。是以，如果得到了鎖，它等同于spin_lock_bh，如果得不到鎖，它等同于spin_trylock。如果該宏得到了自旋鎖，需要使用spin_unlock_bh來釋放。

spin_can_lock(lock)

該宏用于判斷自旋鎖lock是否能夠被鎖，它實際是spin_is_locked取反。如果lock沒有被鎖，它傳回真，否則，傳回假。該宏在2.6.11中第一次被定義，在先前的核心中并沒有該宏。

獲得自旋鎖和釋放自旋鎖有好幾個版本，是以讓讀者知道在什麼樣的情況下使用什麼版本的獲得和釋放鎖的宏是非常必要的。

如果被保護的共享資源隻在程序上下文通路和軟中斷上下文通路，那麼當在程序上下文通路共享資源時，可能被軟中斷打斷，進而可能進入軟中斷上下文來對 被保護的共享資源通路，是以對于這種情況，對共享資源的通路必須使用spin_lock_bh和spin_unlock_bh來保護。當然使用 spin_lock_irq和spin_unlock_irq以及spin_lock_irqsave和spin_unlock_irqrestore也 可以，它們失效了本地硬中斷，失效硬中斷隐式地也失效了軟中斷。但是使用spin_lock_bh和spin_unlock_bh是最恰當的，它比其他兩 個快。

如果被保護的共享資源隻在程序上下文和tasklet或timer上下文通路，那麼應該使用與上面情況相同的獲得和釋放鎖的宏，因為tasklet和timer是用軟中斷實作的。

如果被保護的共享資源隻在一個tasklet或timer上下文通路，那麼不需要任何自旋鎖保護，因為同一個tasklet或timer隻能在一個 CPU上運作，即使是在SMP環境下也是如此。實際上tasklet在調用tasklet_schedule标記其需要被排程時已經把該tasklet綁 定到目前CPU，是以同一個tasklet決不可能同時在其他CPU上運作。timer也是在其被使用add_timer添加到timer隊列中時已經被 幫定到目前CPU，是以同一個timer絕不可能運作在其他CPU上。當然同一個tasklet有兩個執行個體同時運作在同一個CPU就更不可能了。

如果被保護的共享資源隻在兩個或多個tasklet或timer上下文通路，那麼對共享資源的通路僅需要用spin_lock和 spin_unlock來保護，不必使用_bh版本，因為當tasklet或timer運作時，不可能有其他tasklet或timer在目前CPU上運 行。 如果被保護的共享資源隻在一個軟中斷（tasklet和timer除外）上下文通路，那麼這個共享資源需要用spin_lock和spin_unlock 來保護，因為同樣的軟中斷可以同時在不同的CPU上運作。

如果被保護的共享資源在兩個或多個軟中斷上下文通路，那麼這個共享資源當然更需要用spin_lock和spin_unlock來保護，不同的軟中斷能夠同時在不同的CPU上運作。

如果被保護的共享資源在軟中斷（包括tasklet和timer）或程序上下文和硬中斷上下文通路，那麼在軟中斷或程序上下文通路期間，可能被硬中 斷打斷，進而進入硬中斷上下文對共享資源進行通路，是以，在程序或軟中斷上下文需要使用spin_lock_irq和spin_unlock_irq來保 護對共享資源的通路。而在中斷處理句柄中使用什麼版本，需依情況而定，如果隻有一個中斷處理句柄通路該共享資源，那麼在中斷處理句柄中僅需要 spin_lock和spin_unlock來保護對共享資源的通路就可以了。因為在執行中斷處理句柄期間，不可能被同一CPU上的軟中斷或程序打斷。但 是如果有不同的中斷處理句柄通路該共享資源，那麼需要在中斷處理句柄中使用spin_lock_irq和spin_unlock_irq來保護對共享資源 的通路。

在使用spin_lock_irq和spin_unlock_irq的情況下，完全可以用spin_lock_irqsave和 spin_unlock_irqrestore取代，那具體應該使用哪一個也需要依情況而定，如果可以确信在對共享資源通路前中斷是使能的，那麼使用 spin_lock_irq更好一些，因為它比spin_lock_irqsave要快一些，但是如果你不能确定是否中斷使能，那麼使用 spin_lock_irqsave和spin_unlock_irqrestore更好，因為它将恢複通路共享資源前的中斷标志而不是直接使能中斷。當 然，有些情況下需要在通路共享資源時必須中斷失效，而通路完後必須中斷使能，這樣的情形使用spin_lock_irq和spin_unlock_irq 最好。

需要特别提醒讀者，spin_lock用于阻止在不同CPU上的執行單元對共享資源的同時通路以及不同程序上下文互相搶占導緻的對共享資源的非同步通路，而中斷失效和軟中斷失效卻是為了阻止在同一CPU上軟中斷或中斷對共享資源的非同步通路。

本系列文章的第二部分将詳細介紹Linux核心中的其他一些同步機制，包括大核心鎖、讀寫鎖、大讀者鎖、RCU和順序鎖。