簡單分析Linux信号量機制

說明：

1. Kernel版本：4.14
2. ARM64處理器，Contex-A53，雙核
3. 使用工具：Source Insight 3.5， Visio

1. 概述

• 信号量semaphore，是作業系統中一種常用的同步與互斥的機制；
• 信号量允許多個程序（計數值>1）同時進入臨界區；
• 如果信号量的計數值為1，一次隻允許一個程序進入臨界區，這種信号量叫二值信号量；
• 信号量可能會引起程序睡眠，開銷較大，适用于保護較長的臨界區；
• 與讀寫自旋鎖類似，linux核心也提供了讀寫信号量的機制；

本文将分析信号量與讀寫信号量的機制，開始吧。

2. 信号量

2.1 流程分析

• 可以将信号量比喻成一個盒子，初始化時在盒子裡放入N把鑰匙，鑰匙先到先得，當N把鑰匙都被拿走完後，再來拿鑰匙的人就需要等待了，隻有等到有人将鑰匙歸還了，等待的人才能拿到鑰匙；

信号量的實作很簡單，先看一下資料結構：

struct semaphore {
	raw_spinlock_t		lock;       //自旋鎖，用于count值的互斥通路
	unsigned int		count;      //計數值，能同時允許通路的數量，也就是上文中的N把鎖
	struct list_head	wait_list;      //不能立即擷取到信号量的通路者，都會加入到等待清單中
};


struct semaphore_waiter {
	struct list_head list;      //用于添加到信号量的等待清單中
	struct task_struct *task;   //用于指向等待的程序，在實際實作中，指向current
	bool up;                    //用于辨別是否已經釋放
};           

流程如下：

• down接口用于擷取信号量，up用于釋放信号量；
• 調用down時，如果sem->count > 0時，也就是盒子裡邊還有多餘的鎖，直接自減并傳回了，當sem->count == 0時，表明盒子裡邊的鎖被用完了，目前任務會加入信号量的等待清單中，設定程序的狀态，并調用schedule_timeout來睡眠指定時間，實際上這個時間設定的無限等待，也就是隻能等着被喚醒，目前任務才能繼續運作；
• 調用up時，如果等待清單為空，表明沒有多餘的任務在等待信号量，直接将sem->count自加即可。如果等待清單非空，表明有任務正在等待信号量，那就需要對等待清單中的第一個任務（等待時間最長）進行喚醒操作，并從等待清單中将需要被喚醒的任務進行删除操作；

更多linux核心視訊教程文檔資料免費領取背景私信【核心】自行擷取.

2.2 信号量缺點

• 對比下《Linux Mutex機制分析》說過的Mutex，Semaphore與Mutex在實作上有一個重大的差別：ownership。Mutex被持有後有一個明确的owner，而Semaphore并沒有owner，當一個程序阻塞在某個信号量上時，它沒法知道自己阻塞在哪個程序（線程）之上；
• 沒有ownership會帶來以下幾個問題：
• 在保護臨界區的時候，無法進行優先級反轉的處理；
• 系統無法對其進行跟蹤斷言處理，比如死鎖檢測等；
• 信号量的調試變得更加麻煩；

是以，在Mutex能滿足要求的情況下，優先使用Mutex。

2.3 其他接口

信号量提供了多種不同的信号量擷取的接口，介紹如下：

/* 未擷取信号量時，程序輕度睡眠：TASK_INTERRUPTIBLE */
int down_interruptible(struct semaphore *sem)
/* 未擷取到信号量時，程序中度睡眠：TASK_KILLABLE */
int down_killable(struct semaphore *sem)
/* 非等待的方式去擷取信号量 */
int down_trylock(struct semaphore *sem)
/* 擷取信号量，并指定等待時間 */
int down_timeout(struct semaphore *sem, long timeout)           

3. 讀寫信号量

《linux spinlock/rwlock/seqlock原理剖析（基于ARM64）》文章中，我們分析過讀寫自旋鎖，讀寫信号量的功能類似，它能有效提高并發性，我們先明确下它的特點：

• 允許多個讀者同時進入臨界區；
• 讀者與寫者不能同時進入臨界區（讀者與寫者互斥）；
• 寫者與寫者不能同時進入臨界區（寫者與寫者互斥）；

3.1 資料結構

讀寫信号量的資料結構與信号量的結構比較相似：

struct rw_semaphore {
	atomic_long_t count;        //用于表示讀寫信号量的計數
	struct list_head wait_list;     //等待清單，用于管理在該信号量上睡眠的任務
	raw_spinlock_t wait_lock;   //鎖，用于保護count值的操作
#ifdef CONFIG_RWSEM_SPIN_ON_OWNER
	struct optimistic_spin_queue osq; /* spinner MCS lock */    //MCS鎖，參考上一篇文章Mutex中的介紹
	/*
	 * Write owner. Used as a speculative check to see
	 * if the owner is running on the cpu.
	 */
	struct task_struct *owner;      //當寫者成功擷取鎖時，owner會指向鎖的持有者
#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC
	struct lockdep_map	dep_map;
#endif
};           

• 最關鍵的需要看一下count字段，掌握了這個字段的處理，才能比較好了解讀寫信号量的機制；
• 《inux spinlock/rwlock/seqlock原理剖析（基于ARM64）》文章中提到過讀寫自旋鎖，讀寫自旋鎖中的lock字段，bit[31]用于寫鎖的标記，bit[30:0]用于讀鎖的統計，而讀寫信号量的count字段也大體類似；

• 以32位的count值為例，高16bit代表的是waiting part，低16bit代表的是active part；
• RWSEM_UNLOCKED_VALUE：值為0，表示鎖未被持有，沒有讀者也沒有寫者；
• RWSEM_ACTIVE_BIAS：值為1，，該值用于定義RWSEM_ACTIVE_READ_BIAS和RWSEM_ACTIVE_WRITE_BIAS；
• RWSEM_WAITING_BIAS：值為-65536，當有任務需要加入到等待清單中時，count值需要加RWSEM_WAITING_BIAS，有任務需要從等待清單中移除時，count值需要減去RWSEM_WAITING_BIAS；
• RWSEM_ACTIVE_READ_BIAS：值為1，當有讀者去擷取鎖的時候，count值将加RWSEM_ACTIVE_READ_BIAS，釋放鎖的時候，count值将減去RWSEM_ACTIVE_READ_BIAS；
• RWSEM_ACTIVE_WRITE_BIAS，值為-65535，當有寫者去擷取鎖的時候，count值将加RWSEM_ACTIVE_WRITE_BIAS，釋放鎖的時候，count值需要減去RWSEM_ACTIVE_WRITE_BIAS；

在擷取釋放讀鎖和寫鎖的全過程中，count值伴随着上述這幾個宏定義的加減操作，用于辨別不同的狀态，可以羅列如下：

• 0x0000000X：活躍的讀者和正在申請讀鎖的讀者總共為X個，沒有寫者來幹擾；
• 0x00000000：沒有讀者和寫者來操作，初始化狀态；
• 0xFFFF000X：分為以下幾種情況：
• 0xFFFF000X = RWSEM_WAITING_BIAS + X * RWSEM_ACTIVE_READ_BIAS，表示活躍的讀者和正在申請讀鎖的讀者總共有X個，并且還有一個寫者在睡眠等待；
• 0xFFFF000X = RWSEM_ACTIVE_WRITE_BIAS + (X - 1)* RWSEM_ACTIVE_READ_BIAS，表示有一個寫者在嘗試擷取鎖，活躍的讀者和正在申請讀鎖的讀者總共有X-1個；
• 0xFFFF0001：分為以下幾種情況：
• 0xFFFF0001 = RWSEM_ACTIVE_WRITE_BIAS，有一個活躍的寫者，或者寫者正在嘗試擷取鎖，沒有讀者幹擾；
• 0xFFFF0001 = RWSEM_ACTIVE_READ_BIAS + RWSEM_WAITING_BIAS，有個寫者正在睡眠等待，還有一個活躍或嘗試擷取鎖的讀者；

3.1 讀信号量

3.1.1 讀者擷取鎖

• 特點：讀者與讀者可以并發執行，讀者與寫者互斥執行，是以當有寫者持有鎖的時候，讀者将進入睡眠狀态；
• 當sem->count加1後還是小于0，代表鎖已經被寫者持有了，讀者擷取鎖失敗，進入rwsem_down_read_failed函數；
• 如果sem->wait_list是空時，代表沒有任務在等待清單中，首次加入時，sem->count值需要加上RWSEM_WAITING_BIAS，表示有任務在等待清單中；
• 如果此時sem->count == RWSEM_WAITING_BIAS或者count > RWSEM_WAITING_BIAS && adjustment != RWSEM_ACTIVE_READ_BIAS，表示此時寫者将鎖釋放了，是以需要去喚醒在等待清單中的任務；
• 如果寫者沒有釋放鎖，那就進入循環，并調用schedule讓出CPU，直到鎖被釋放了，那麼從代碼流程中看，隻有!waiter.task時才會跳出循環，也就是waiter.task == NULL時，才是擷取成功，這個操作是在__rwsem_mark_wake中通過smp_store_release(&waiter->task, NULL)實作的；
• 在等待擷取鎖的循環中，需要對信号進行處理，如果對應的等待任務沒被喚醒，那麼直接跳轉到out_nolock處，接下來的處理就是一些逆操作了，包括從等待清單中删除，如果是等待清單中的首個任務，還需要減去RWSEM_WAITING_BIAS等；

總結一下：讀者擷取鎖的時候，如果沒有寫者持有，那就可以支援多個讀者直接擷取；而如果此時寫者持有了鎖，讀者擷取失敗，它将把自己添加到等待清單中，（這個等待清單中可能已經存放了其他來擷取鎖的讀者或者寫者），在将讀者真正睡眠等待前，還會再一次判斷此時是否有寫者釋放了該鎖，釋放了的話，那就需要對睡眠等待在該鎖的任務進行喚醒操作了

3.1.2 讀者釋放鎖

• 釋放鎖的時候sem->count值進行減1操作；
• 減1操作之後得到的count值小于-1，并且active part是全零，代表等待清單中有寫任務在睡眠等待，是以需要進行喚醒操作；
• 喚醒操作中，如果有自旋等待的任務，那就可以直接傳回了，畢竟人家在自旋呢，又沒有睡眠；
• 沒有自旋等待任務，那就去喚醒等待清單中的任務了；

3.2 寫信号量

3.2.1 寫者擷取鎖

• 寫者的特點：看誰都不順眼，跟誰都互斥，有我沒你。隻要有一個寫者在持有鎖，其他的讀者與寫者都無法擷取；
• 在寫者擷取鎖的時候，将sem->count值加上RWSEM_ACTIVE_WRITE_BIAS，如果這個值不等于RWSEM_ACTIVE_WRITE_BIAS，表示有其他的讀者或寫者持有鎖，是以擷取鎖失敗，調用rwsem_down_write_failed來處理；
• 調用rwsem_optimistic_spin進行樂觀自旋去嘗試擷取鎖，擷取了的話，則直接傳回，optimistic spin可以參考《Linux Mutex機制分析》文章中的分析，它的作用也是性能的優化，認為鎖的持有者會很快釋放，是以目前程序選擇自旋而不是讓出CPU，減少上下文切換帶來的開銷；
• 如果等待清單中有讀者任務在睡眠等待，此時假如寫者釋放了鎖，那麼需要先将讀者任務都給喚醒了；如果等待清單中沒有任務，也就意味着目前的寫者是第一個任務，是以将sem->count值加上RWSEM_WAITING_BIAS；
• 循環等待擷取鎖，這個過程與down_read是類似的；

總結寫者擷取鎖時，隻要鎖被其他讀者或者寫者持有了，則擷取鎖失敗，然後進行失敗情況處理。在失敗情況下，它本身會嘗試進行optimistic spin去嘗試擷取鎖，如果擷取成功了，那就是皆大歡喜了，否則還是需要進入慢速路徑。慢速路徑中去判斷等待清單中是否有任務在睡眠等待，并且會再次嘗試去檢視是否已經有寫者釋放了鎖，寫者釋放了鎖，并且隻有讀者在睡眠等待，那麼此時應該優先讓這些先等待的任務喚醒

3.2.2 寫者釋放鎖

• 寫者釋放鎖的時候，有一個關鍵的操作，将sem->owner進行清零操作，在寫者擷取鎖的時候會将該值設定成持有鎖的程序；
• 釋放鎖的時候，需要減去RWSEM_ACTIVE_WRITE_BIAS，然後再去判斷值，如果此時還有任務在睡眠等待，那就進行喚醒操作；

3.3 總結

了解讀寫信号量有幾個關鍵點：

1. 讀寫信号量的特性可以與讀寫自旋鎖進行類比（讀者與讀者并發、讀者與寫者互斥、寫者與寫者互斥），差別在于讀寫信号量可能會發生睡眠，進而帶來程序切換的開銷；
2. 為了優化讀寫信号量的性能，引入了MCS鎖機制，進一步減少切換開銷。第一個寫者擷取了鎖後，第二個寫者去擷取時自旋等待，而讀者去擷取時則會進入睡眠；
3. 讀寫信号量的count值很關鍵，代表着讀寫信号量不同狀态的切換，是以也決定了執行流程；
4. 讀者或寫者釋放鎖的時候，去喚醒等待清單中的任務，需要分情況處理。等待清單中可能存放的是讀者與寫者的組合，如果第一個任務是寫者，則直接喚醒該寫者，否則将喚醒排在前邊的連續幾個讀者；

首頁 - 核心技術中文網 - 建構全國最權威的核心技術交流分享論壇

轉載位址：深入分析Linux信号量機制 - 圈點 - 核心技術中文網 - 建構全國最權威的核心技術交流分享論壇