背景

由于在多處理器環境中某些資源的有限性，有時需要互斥訪問（mutual exclusion），這時候就需要引入鎖的概念，只有獲取了鎖的任務才能夠對資源進行訪問，由于多線程的核心是CPU的時間分片，所以同一時刻只能有一個任務獲取到鎖。

內核當發生訪問資源沖突的時候，通常有兩種處理方式：

一個是原地等待

一個是掛起當前進程，調度其他進程執行（睡眠）

自旋鎖

Spinlock 是內核中提供的一種比較常見的鎖機制，自旋鎖是“原地等待”的方式解決資源沖突的。即，一個線程獲取了一個自旋鎖后，另外一個線程期望獲取該自旋鎖，獲取不到，只能夠原地“打轉”（忙等待）。

由于自旋鎖的這個忙等待的特性，注定了它使用場景上的限制 —— 自旋鎖不應該被長時間的持有（消耗 CPU 資源）。

自旋鎖的優點

自旋鎖不會使線程狀態發生切換，一直處于用戶態，即線程一直都是active的；不會使線程進入阻塞狀態，減少了不必要的上下文切換，執行速度快。

非自旋鎖在獲取不到鎖的時候會進入阻塞狀態，從而進入內核態，當獲取到鎖的時候需要從內核態恢復，需要線程上下文切換。（線程被阻塞后便進入內核（Linux）調度狀態，這個會導致系統在用戶態與內核態之間來回切換，嚴重影響鎖的性能）。

自旋鎖的使用

在linux kernel的實現中，經常會遇到這樣的場景：共享數據被中斷上下文和進程上下文訪問，該如何保護呢？

如果只有進程上下文的訪問，那么可以考慮使用semaphore或者mutex的鎖機制，但是現在中斷上下文也摻和進來，那些可以導致睡眠的lock就不能使用了，這時候，可以考慮使用spin lock。

在中斷上下文，是不允許睡眠的，所以，這里需要的是一個不會導致睡眠的鎖——spinlock。

換言之，中斷上下文要用鎖，首選 spinlock。

使用自旋鎖，有兩種方式定義一個鎖：

動態的：

spinlock_t lock;spin_lock_init （&lock）;

靜態的：

DEFINE_SPINLOCK（lock）;

使用步驟

spinlock的使用很簡單：

我們要訪問臨界資源需要首先申請自旋鎖;

獲取不到鎖就自旋，如果能獲得鎖就進入臨界區;

當自旋鎖釋放后，自旋在這個鎖的任務即可獲得鎖并進入臨界區，退出臨界區的任務必須釋放自旋鎖。

使用實例

static spinlock_t lock;static int flage = 1;spin_lock_init（&lock）;static int hello_open （struct inode *inode， struct file *filep）{ spin_lock（&lock）; if（flage ！=1） { spin_unlock（&lock）; return -EBUSY; } flage =0; spin_unlock（&lock）; return 0;}static int hello_release （struct inode *inode， struct file *filep）{ flage = 1; return 0;}

補充

中斷上下文不能睡眠的原因是：

中斷處理的時候，不應該發生進程切換，因為在中斷context中，唯一能打斷當前中斷handler的只有更高優先級的中斷，它不會被進程打斷，如果在 中斷context中休眠，則沒有辦法喚醒它，因為所有的wake_up_xxx都是針對某個進程而言的，而在中斷context中，沒有進程的概念，沒 有一個task_struct（這點對于softirq和tasklet一樣），因此真的休眠了，比如調用了會導致block的例程，內核幾乎肯定會死。

schedule（）在切換進程時，保存當前的進程上下文（CPU寄存器的值、進程的狀態以及堆棧中的內容），以便以后恢復此進程運行。中斷發生后，內核會先保存當前被中斷的進程上下文（在調用中斷處理程序后恢復）；

但在中斷處理程序里，CPU寄存器的值肯定已經變化了吧（最重要的程序計數器PC、堆棧SP等），如果此時因為睡眠或阻塞操作調用了schedule（），則保存的進程上下文就不是當前的進程context了。所以不可以在中斷處理程序中調用schedule（）。

內核中schedule（）函數本身在進來的時候判斷是否處于中斷上下文：

if（unlikely（in_interrupt（））） BUG（）;

因此，強行調用schedule（）的結果就是內核BUG。

中斷handler會使用被中斷的進程內核堆棧，但不會對它有任何影響，因為handler使用完后會完全清除它使用的那部分堆棧，恢復被中斷前的原貌。

處于中斷context時候，內核是不可搶占的。因此，如果休眠，則內核一定掛起。

自旋鎖的死鎖

自旋鎖不可遞歸，自己等待自己已經獲取的鎖，會導致死鎖。

自旋鎖可以在中斷上下文中使用，但是試想一個場景：一個線程獲取了一個鎖，但是被中斷處理程序打斷，中斷處理程序也獲取了這個鎖（但是之前已經被鎖住了，無法獲取到，只能自旋），中斷無法退出，導致線程中后面釋放鎖的代碼無法被執行，導致死鎖。（如果確認中斷中不會訪問和線程中同一個鎖，其實無所謂）。

一、考慮下面的場景（內核搶占場景）：

（1）進程A在某個系統調用過程中訪問了共享資源 R

（2）進程B在某個系統調用過程中也訪問了共享資源 R

會不會造成沖突呢？

假設在A訪問共享資源R的過程中發生了中斷，中斷喚醒了沉睡中的，優先級更高的B，在中斷返回現場的時候，發生進程切換，B啟動執行，并通過系統調用訪問了R，如果沒有鎖保護，則會出現兩個thread進入臨界區，導致程序執行不正確。OK，我們加上spin lock看看如何：A在進入臨界區之前獲取了spin lock，同樣的，在A訪問共享資源R的過程中發生了中斷，中斷喚醒了沉睡中的，優先級更高的B，B在訪問臨界區之前仍然會試圖獲取spin lock，這時候由于A進程持有spin lock而導致B進程進入了永久的spin……怎么破？linux的kernel很簡單，在A進程獲取spin lock的時候，禁止本CPU上的搶占（上面的永久spin的場合僅僅在本CPU的進程搶占本CPU的當前進程這樣的場景中發生）。如果A和B運行在不同的CPU上，那么情況會簡單一些：A進程雖然持有spin lock而導致B進程進入spin狀態，不過由于運行在不同的CPU上，A進程會持續執行并會很快釋放spin lock，解除B進程的spin狀態。

二、再考慮下面的場景（中斷上下文場景）：

運行在CPU0上的進程A在某個系統調用過程中訪問了共享資源 R

運行在CPU1上的進程B在某個系統調用過程中也訪問了共享資源 R

外設P的中斷handler中也會訪問共享資源 R

在這樣的場景下，使用spin lock可以保護訪問共享資源R的臨界區嗎？

我們假設CPU0上的進程A持有spin lock進入臨界區，這時候，外設P發生了中斷事件，并且調度到了CPU1上執行，看起來沒有什么問題，執行在CPU1上的handler會稍微等待一會CPU0上的進程A，等它立刻臨界區就會釋放spin lock的，但是，如果外設P的中斷事件被調度到了CPU0上執行會怎么樣？CPU0上的進程A在持有spin lock的狀態下被中斷上下文搶占，而搶占它的CPU0上的handler在進入臨界區之前仍然會試圖獲取spin lock，悲劇發生了，CPU0上的P外設的中斷handler永遠的進入spin狀態，這時候，CPU1上的進程B也不可避免在試圖持有spin lock的時候失敗而導致進入spin狀態。為了解決這樣的問題，linux kernel采用了這樣的辦法：如果涉及到中斷上下文的訪問，spin lock需要和禁止本 CPU 上的中斷聯合使用。

三、再考慮下面的場景（底半部場景）

linux kernel中提供了豐富的bottom half的機制，雖然同屬中斷上下文，不過還是稍有不同。我們可以把上面的場景簡單修改一下：外設P不是中斷handler中訪問共享資源R，而是在的bottom half中訪問。使用spin lock+禁止本地中斷當然是可以達到保護共享資源的效果，但是使用牛刀來殺雞似乎有點小題大做，這時候disable bottom half就可以了。

四、中斷上下文之間的競爭

同一種中斷handler之間在uni core和multi core上都不會并行執行，這是linux kernel的特性。如果不同中斷handler需要使用spin lock保護共享資源，對于新的內核（不區分fast handler和slow handler），所有handler都是關閉中斷的，因此使用spin lock不需要關閉中斷的配合。bottom half又分成softirq和tasklet，同一種softirq會在不同的CPU上并發執行，因此如果某個驅動中的softirq的handler中會訪問某個全局變量，對該全局變量是需要使用spin lock保護的，不用配合disable CPU中斷或者bottom half。tasklet更簡單，因為同一種tasklet不會多個CPU上并發。

自旋鎖的實現原理

數據結構

首先定義一個 spinlock_t 的數據類型，其本質上是一個整數值（對該數值的操作需要保證原子性），該數值表示spin lock是否可用。初始化的時候被設定為1。當thread想要持有鎖的時候調用spin_lock函數，該函數將spin lock那個整數值減去1，然后進行判斷，如果等于0，表示可以獲取spin lock，如果是負數，則說明其他thread的持有該鎖，本thread需要spin。

內核中的spinlock_t的數據類型定義如下：

typedef struct spinlock { struct raw_spinlock rlock; } spinlock_t;typedef struct raw_spinlock { arch_spinlock_t raw_lock;} raw_spinlock_t;

通用（適用于各種arch）的spin lock使用spinlock_t這樣的type name，各種arch定義自己的struct raw_spinlock。聽起來不錯的主意和命名方式，直到linux realtime tree（PREEMPT_RT）提出對spinlock的挑戰。

spin lock的命名規范定義如下：

spinlock，在rt linux（配置了PREEMPT_RT）的時候可能會被搶占（實際底層可能是使用支持PI（優先級翻轉）的mutext）。

raw_spinlock，即便是配置了PREEMPT_RT也要頑強的spin

arch_spinlock，spin lock是和architecture相關的，

ARM 結構體系 arch_spin_lock 接口實現

加鎖

同樣的，這里也只是選擇一個典型的API來分析，其他的大家可以自行學習。我們選擇的是 arch_spin_lock，其ARM32的代碼如下：

static inline void arch_spin_lock（arch_spinlock_t *lock）{ unsigned long tmp; u32 newval; arch_spinlock_t lockval; prefetchw（&lock-》slock）;－－－－－－－－－（0） __asm__ __volatile__（“1： ldrex %0， ［%3］\n”－－－－－－－－－（1）“ add %1， %0， %4\n” －－－－－－－－－－（2）“ strex %2， %1，［%3］\n”－－－－－－－－－（3）“ teq %2， #0\n”－－－－－－－－－－－－－（4）“ bne 1b” ： “=&r” （lockval）， “=&r” （newval）， “=&r” （tmp） ： “r” （&lock-》slock）， “I” （1 《《 TICKET_SHIFT） ： “cc”）; while （lockval.tickets.next ！= lockval.tickets.owner） {－－－－（5） wfe（）;－－－－－－－－－－－－（6） lockval.tickets.owner = ACCESS_ONCE（lock-》tickets.owner）;－－－－（7） } smp_mb（）;－－－－－－－－－－－（8）}

（0）和preloading cache相關的操作，主要是為了性能考慮（1）lockval = lock-》slock （如果lock-》slock沒有被其他處理器獨占，則標記當前執行處理器對lock-》slock地址的獨占訪問；否則不影響）（2）newval = lockval + （1 《《 TICKET_SHIFT）（3）strex tmp， newval， ［&lock-》slock］ （如果當前執行處理器沒有獨占lock-》slock地址的訪問，不進行存儲，返回1給temp；如果當前處理器已經獨占lock-》slock內存訪問，則對內存進行寫，返回0給temp，清除獨占標記） lock-》tickets.next = lock-》tickets.next + 1（4）檢查是否寫入成功 lockval.tickets.next（5）初始化時lock-》tickets.owner、lock-》tickets.next都為0，假設第一次執行arch_spin_lock，lockval = *lock，lock-》tickets.next++，lockval.tickets.next 等于 lockval.tickets.owner，獲取到自旋鎖；自旋鎖未釋放，第二次執行的時候，lock-》tickets.owner = 0， lock-》tickets.next = 1，拷貝到lockval后，lockval.tickets.next ！= lockval.tickets.owner，會執行wfe等待被自旋鎖釋放被喚醒，自旋鎖釋放時會執行 lock-》tickets.owner++，lockval.tickets.owner重新賦值（6）暫時中斷掛起執行。如果當前spin lock的狀態是locked，那么調用wfe進入等待狀態。更具體的細節請參考ARM WFI和WFE指令中的描述。（7）其他的CPU喚醒了本cpu的執行，說明owner發生了變化，該新的own賦給lockval，然后繼續判斷spin lock的狀態，也就是回到step 5。（8）memory barrier的操作，具體可以參考memory barrier中的描述。

釋放鎖

static inline void arch_spin_unlock（arch_spinlock_t *lock）{ smp_mb（）; lock-》tickets.owner++; ---------------------- （0） dsb_sev（）; ---------------------------------- （1）}

（0）lock-》tickets.owner增加1，下一個被喚醒的處理器會檢查該值是否與自己的lockval.tickets.next相等，lock-》tickets.owner代表可以獲取的自旋鎖的處理器，lock-》tickets.next你一個可以獲取的自旋鎖的owner；處理器獲取自旋鎖時，會先讀取lock-》tickets.next用于與lock-》tickets.owner比較并且對lock-》tickets.next加1，下一個處理器獲取到的lock-》tickets.next就與當前處理器不一致了，兩個處理器都與lock-》tickets.owner比較，肯定只有一個處理器會相等，自旋鎖釋放時時對lock-》tickets.owner加1計算，因此，先申請自旋鎖多處理器lock-》tickets.next值更新，自然先獲取到自旋鎖

（1）執行sev指令，喚醒wfe等待的處理器

自旋鎖導致死鎖實例

死鎖的2種情況

1）擁有自旋鎖的進程A在內核態阻塞了，內核調度B進程，碰巧B進程也要獲得自旋鎖，此時B只能自旋轉。而此時搶占已經關閉，不會調度A進程了，B永遠自旋，產生死鎖。

2）進程A擁有自旋鎖，中斷到來，CPU執行中斷函數，中斷處理函數，中斷處理函數需要獲得自旋鎖，訪問共享資源，此時無法獲得鎖，只能自旋，產生死鎖。

如何避免死鎖

如果中斷處理函數中也要獲得自旋鎖，那么驅動程序需要在擁有自旋鎖時禁止中斷；

自旋鎖必須在可能的最短時間內擁有；

避免某個獲得鎖的函數調用其他同樣試圖獲取這個鎖的函數，否則代碼就會死鎖；不論是信號量還是自旋鎖，都不允許鎖擁有者第二次獲得這個鎖，如果試圖這么做，系統將掛起；

鎖的順序規則 按同樣的順序獲得鎖; 如果必須獲得一個局部鎖和一個屬于內核更中心位置的鎖，則應該首先獲取自己的局部鎖 ; 如果我們擁有信號量和自旋鎖的組合，則必須首先獲得信號量；在擁有自旋鎖時調用down（可導致休眠）是個嚴重的錯誤的。

死鎖舉例

因為自旋鎖持有時間非常短，沒有直觀的現象，下面舉一個會導致死鎖的實例。

運行條件

虛擬機：vmware

OS ：Ubuntu 14

配置 ：將虛擬機的處理個數設置為1，否則不會死鎖

原理

針對單CPU，擁有自旋鎖的任務不應該調度會引起休眠的函數，否則會導致死鎖。

步驟：

進程A在open（）字符設備后，對應的內核函數會申請自旋鎖，此時自旋鎖空閑，申請到自旋鎖，進程A隨即進入執行sleep（）函數進入休眠；

在進程A 處于sleep期間，自旋鎖一直屬于進程A所有；

運行進程B，進程B執行open函數，對應的內核函數也會申請自旋鎖，此時自旋鎖歸進程A所有，所以進程B進入自旋狀態；

因為此時搶占已經關閉，系統死鎖。

驅動代碼如下：

#include 《linux/init.h》#include 《linux/module.h》#include 《linux/kdev_t.h》#include 《linux/fs.h》#include 《linux/cdev.h》#include 《linux/device.h》#include 《linux/spinlock.h》static int major = 250;static int minor = 0;static dev_t devno;static struct cdev cdev;static struct class *cls;static struct device *test_device;static spinlock_t lock;static int flage = 1;#define DEAD 1static int hello_open （struct inode *inode， struct file *filep）{ spin_lock（&lock）; if（flage ！=1） { spin_unlock（&lock）; return -EBUSY; } flage =0; #if DEAD #elif spin_unlock（&lock）; #endif return 0;}static int hello_release （struct inode *inode， struct file *filep）{ flage = 1; #if DEAD spin_unlock（&lock）; #endif return 0;}static struct file_operations hello_ops ={ .open = hello_open， .release = hello_release，};static int hello_init（void）{ int result; int error; printk（“hello_init \n”）; result = register_chrdev（ major， “hello”， &hello_ops）; if（result 《 0） { printk（“register_chrdev fail \n”）; return result; } devno = MKDEV（major，minor）; cls = class_create（THIS_MODULE，“helloclass”）; if（IS_ERR（cls）） { unregister_chrdev（major，“hello”）; return result; } test_device = device_create（cls，NULL，devno，NULL，“test”）; if（IS_ERR（test_device ）） { class_destroy（cls）; unregister_chrdev（major，“hello”）; return result; } spin_lock_init（&lock）; return 0;}static void hello_exit（void）{ printk（“hello_exit \n”）; device_destroy（cls，devno）; class_destroy（cls）; unregister_chrdev（major，“hello”）; return;}module_init（hello_init）;module_exit（hello_exit）;MODULE_LICENSE（“GPL”）;

測試程序如下：

#include 《stdio.h》#include 《sys/types.h》#include 《sys/stat.h》#include 《fcntl.h》main（）{ int fd; fd = open（“/dev/test”，O_RDWR）; if（fd《0） { perror（“open fail \n”）; return; } sleep（20）; close（fd）; printf（“open ok \n ”）;}

測試步驟：

編譯加載內核

makeinsmod hello.ko

運行進程A

gcc test.c -o a./a

打開一個新的終端，運行進程B

gcc test.c -o b./b

注意，一定要在進程A沒有退出的時候運行進程B。