背景
Read the fucking source code! --By 魯迅A picture is worth a thousand words. --By 高爾基
說(shuō)明：
- Kernel版本：4.14
- ARM64處理器,，Contex-A53,，雙核
- 使用工具：Source Insight 3.5， Visio
1. 概述
- 信號(hào)量
semaphore,，是操作系統(tǒng)中一種常用的同步與互斥的機(jī)制,；
- 信號(hào)量允許多個(gè)進(jìn)程（計(jì)數(shù)值>1）同時(shí)進(jìn)入臨界區(qū)；
- 如果信號(hào)量的計(jì)數(shù)值為1,，一次只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū),，這種信號(hào)量叫二值信號(hào)量,；
- 信號(hào)量可能會(huì)引起進(jìn)程睡眠，開(kāi)銷(xiāo)較大,，適用于保護(hù)較長(zhǎng)的臨界區(qū),；
- 與讀寫(xiě)自旋鎖類(lèi)似，linux內(nèi)核也提供了讀寫(xiě)信號(hào)量的機(jī)制,；
本文將分析信號(hào)量與讀寫(xiě)信號(hào)量的機(jī)制,，開(kāi)始吧。
2. 信號(hào)量
2.1 流程分析
- 可以將信號(hào)量比喻成一個(gè)盒子,，初始化時(shí)在盒子里放入N把鑰匙,，鑰匙先到先得，當(dāng)N把鑰匙都被拿走完后,，再來(lái)拿鑰匙的人就需要等待了,，只有等到有人將鑰匙歸還了，等待的人才能拿到鑰匙,；
信號(hào)量的實(shí)現(xiàn)很簡(jiǎn)單,，先看一下數(shù)據(jù)結(jié)構(gòu)：
struct semaphore {
raw_spinlock_t lock; //自旋鎖，用于count值的互斥訪問(wèn)
unsigned int count; //計(jì)數(shù)值,，能同時(shí)允許訪問(wèn)的數(shù)量,，也就是上文中的N把鎖
struct list_head wait_list; //不能立即獲取到信號(hào)量的訪問(wèn)者，都會(huì)加入到等待列表中
};
struct semaphore_waiter {
struct list_head list; //用于添加到信號(hào)量的等待列表中
struct task_struct *task; //用于指向等待的進(jìn)程,，在實(shí)際實(shí)現(xiàn)中,，指向current
bool up; //用于標(biāo)識(shí)是否已經(jīng)釋放
};
流程如下：
down接口用于獲取信號(hào)量，up用于釋放信號(hào)量,；- 調(diào)用
down時(shí),，如果sem->count > 0時(shí)，也就是盒子里邊還有多余的鎖,，直接自減并返回了,，當(dāng)sem->count == 0時(shí)，表明盒子里邊的鎖被用完了,，當(dāng)前任務(wù)會(huì)加入信號(hào)量的等待列表中,，設(shè)置進(jìn)程的狀態(tài)，并調(diào)用schedule_timeout來(lái)睡眠指定時(shí)間,，實(shí)際上這個(gè)時(shí)間設(shè)置的無(wú)限等待,，也就是只能等著被喚醒，當(dāng)前任務(wù)才能繼續(xù)運(yùn)行,；
- 調(diào)用
up時(shí),，如果等待列表為空，表明沒(méi)有多余的任務(wù)在等待信號(hào)量,，直接將sem->count自加即可,。如果等待列表非空,，表明有任務(wù)正在等待信號(hào)量，那就需要對(duì)等待列表中的第一個(gè)任務(wù)（等待時(shí)間最長(zhǎng)）進(jìn)行喚醒操作,，并從等待列表中將需要被喚醒的任務(wù)進(jìn)行刪除操作,；
2.2 信號(hào)量缺點(diǎn)
- 對(duì)比下
《Linux Mutex機(jī)制分析》說(shuō)過(guò)的Mutex，Semaphore與Mutex在實(shí)現(xiàn)上有一個(gè)重大的區(qū)別：ownership,。Mutex被持有后有一個(gè)明確的owner,，而Semaphore并沒(méi)有owner，當(dāng)一個(gè)進(jìn)程阻塞在某個(gè)信號(hào)量上時(shí),，它沒(méi)法知道自己阻塞在哪個(gè)進(jìn)程（線程）之上,；
- 沒(méi)有
ownership會(huì)帶來(lái)以下幾個(gè)問(wèn)題：
- 在保護(hù)臨界區(qū)的時(shí)候，無(wú)法進(jìn)行優(yōu)先級(jí)反轉(zhuǎn)的處理,；
- 系統(tǒng)無(wú)法對(duì)其進(jìn)行跟蹤斷言處理,，比如死鎖檢測(cè)等；
- 信號(hào)量的調(diào)試變得更加麻煩,；
因此,，在Mutex能滿(mǎn)足要求的情況下，優(yōu)先使用Mutex,。
2.3 其他接口
信號(hào)量提供了多種不同的信號(hào)量獲取的接口,，介紹如下：
/* 未獲取信號(hào)量時(shí)，進(jìn)程輕度睡眠： TASK_INTERRUPTIBLE */
int down_interruptible(struct semaphore *sem)
/* 未獲取到信號(hào)量時(shí),，進(jìn)程中度睡眠： TASK_KILLABLE */
int down_killable(struct semaphore *sem)
/* 非等待的方式去獲取信號(hào)量 */
int down_trylock(struct semaphore *sem)
/* 獲取信號(hào)量,，并指定等待時(shí)間 */
int down_timeout(struct semaphore *sem, long timeout)
3. 讀寫(xiě)信號(hào)量
【原創(chuàng)】linux spinlock/rwlock/seqlock原理剖析（基于ARM64）文章中，我們分析過(guò)讀寫(xiě)自旋鎖,，讀寫(xiě)信號(hào)量的功能類(lèi)似,，它能有效提高并發(fā)性，我們先明確下它的特點(diǎn)：
- 允許多個(gè)讀者同時(shí)進(jìn)入臨界區(qū),；
- 讀者與寫(xiě)者不能同時(shí)進(jìn)入臨界區(qū)（讀者與寫(xiě)者互斥）；
- 寫(xiě)者與寫(xiě)者不能同時(shí)進(jìn)入臨界區(qū)（寫(xiě)者與寫(xiě)者互斥）,；
3.1 數(shù)據(jù)結(jié)構(gòu)
讀寫(xiě)信號(hào)量的數(shù)據(jù)結(jié)構(gòu)與信號(hào)量的結(jié)構(gòu)比較相似：
struct rw_semaphore {
atomic_long_t count; //用于表示讀寫(xiě)信號(hào)量的計(jì)數(shù)
struct list_head wait_list; //等待列表,，用于管理在該信號(hào)量上睡眠的任務(wù)
raw_spinlock_t wait_lock; //鎖，用于保護(hù)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; //當(dāng)寫(xiě)者成功獲取鎖時(shí),，owner會(huì)指向鎖的持有者
#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC
struct lockdep_map dep_map;
#endif
};
- 以32位的count值為例,，高16bit代表的是
waiting part,，低16bit代表的是active part；
RWSEM_UNLOCKED_VALUE：值為0,，表示鎖未被持有,，沒(méi)有讀者也沒(méi)有寫(xiě)者；RWSEM_ACTIVE_BIAS：值為1,，,，該值用于定義RWSEM_ACTIVE_READ_BIAS和RWSEM_ACTIVE_WRITE_BIAS；RWSEM_WAITING_BIAS：值為-65536,，當(dāng)有任務(wù)需要加入到等待列表中時(shí),，count值需要加RWSEM_WAITING_BIAS，有任務(wù)需要從等待列表中移除時(shí),，count值需要減去RWSEM_WAITING_BIAS,；RWSEM_ACTIVE_READ_BIAS：值為1，當(dāng)有讀者去獲取鎖的時(shí)候,，count值將加RWSEM_ACTIVE_READ_BIAS,，釋放鎖的時(shí)候，count值將減去RWSEM_ACTIVE_READ_BIAS,；RWSEM_ACTIVE_WRITE_BIAS,，值為-65535，當(dāng)有寫(xiě)者去獲取鎖的時(shí)候,，count值將加RWSEM_ACTIVE_WRITE_BIAS,，釋放鎖的時(shí)候，count值需要減去RWSEM_ACTIVE_WRITE_BIAS,；
在獲取釋放讀鎖和寫(xiě)鎖的全過(guò)程中,，count值伴隨著上述這幾個(gè)宏定義的加減操作，用于標(biāo)識(shí)不同的狀態(tài),，可以羅列如下：
0x0000000X：活躍的讀者和正在申請(qǐng)讀鎖的讀者總共為X個(gè),，沒(méi)有寫(xiě)者來(lái)干擾；0x00000000：沒(méi)有讀者和寫(xiě)者來(lái)操作,，初始化狀態(tài),；0xFFFF000X：分為以下幾種情況：
0xFFFF000X = RWSEM_WAITING_BIAS + X * RWSEM_ACTIVE_READ_BIAS，表示活躍的讀者和正在申請(qǐng)讀鎖的讀者總共有X個(gè),，并且還有一個(gè)寫(xiě)者在睡眠等待,；0xFFFF000X = RWSEM_ACTIVE_WRITE_BIAS + (X - 1)* RWSEM_ACTIVE_READ_BIAS，表示有一個(gè)寫(xiě)者在嘗試獲取鎖，活躍的讀者和正在申請(qǐng)讀鎖的讀者總共有X-1個(gè),；
0xFFFF0001：分為以下幾種情況：
0xFFFF0001 = RWSEM_ACTIVE_WRITE_BIAS,，有一個(gè)活躍的寫(xiě)者，或者寫(xiě)者正在嘗試獲取鎖,，沒(méi)有讀者干擾,；0xFFFF0001 = RWSEM_ACTIVE_READ_BIAS + RWSEM_WAITING_BIAS，有個(gè)寫(xiě)者正在睡眠等待,，還有一個(gè)活躍或嘗試獲取鎖的讀者,；
3.1 讀信號(hào)量
3.1.1 讀者獲取鎖
- 特點(diǎn)：讀者與讀者可以并發(fā)執(zhí)行，讀者與寫(xiě)者互斥執(zhí)行,，因此當(dāng)有寫(xiě)者持有鎖的時(shí)候,，讀者將進(jìn)入睡眠狀態(tài)；
- 當(dāng)
sem->count加1后還是小于0,，代表鎖已經(jīng)被寫(xiě)者持有了,，讀者獲取鎖失敗，進(jìn)入rwsem_down_read_failed函數(shù),；
- 如果
sem->wait_list是空時(shí),，代表沒(méi)有任務(wù)在等待列表中，首次加入時(shí),，sem->count值需要加上RWSEM_WAITING_BIAS,，表示有任務(wù)在等待列表中；
- 如果此時(shí)
sem->count == RWSEM_WAITING_BIAS或者count > RWSEM_WAITING_BIAS && adjustment != RWSEM_ACTIVE_READ_BIAS,，表示此時(shí)寫(xiě)者將鎖釋放了,，因此需要去喚醒在等待列表中的任務(wù)；
- 如果寫(xiě)者沒(méi)有釋放鎖,，那就進(jìn)入循環(huán),，并調(diào)用
schedule讓出CPU，直到鎖被釋放了,，那么從代碼流程中看,，只有!waiter.task時(shí)才會(huì)跳出循環(huán)，也就是waiter.task == NULL時(shí),，才是獲取成功,，這個(gè)操作是在__rwsem_mark_wake中通過(guò)smp_store_release(&waiter->task, NULL)實(shí)現(xiàn)的；
- 在等待獲取鎖的循環(huán)中,，需要對(duì)信號(hào)進(jìn)行處理，如果對(duì)應(yīng)的等待任務(wù)沒(méi)被喚醒,，那么直接跳轉(zhuǎn)到
out_nolock處,，接下來(lái)的處理就是一些逆操作了，包括從等待列表中刪除，如果是等待列表中的首個(gè)任務(wù),，還需要減去RWSEM_WAITING_BIAS等,；
總結(jié)一下：
讀者獲取鎖的時(shí)候，如果沒(méi)有寫(xiě)者持有,，那就可以支持多個(gè)讀者直接獲?。欢绻藭r(shí)寫(xiě)者持有了鎖,，讀者獲取失敗,，它將把自己添加到等待列表中，（這個(gè)等待列表中可能已經(jīng)存放了其他來(lái)獲取鎖的讀者或者寫(xiě)者）,，在將讀者真正睡眠等待前,，還會(huì)再一次判斷此時(shí)是否有寫(xiě)者釋放了該鎖，釋放了的話(huà),，那就需要對(duì)睡眠等待在該鎖的任務(wù)進(jìn)行喚醒操作了
3.1.2 讀者釋放鎖
- 釋放鎖的時(shí)候
sem->count值進(jìn)行減1操作,；
- 減1操作之后得到的
count值小于-1，并且active part是全零,，代表等待列表中有寫(xiě)任務(wù)在睡眠等待,，因此需要進(jìn)行喚醒操作；
- 喚醒操作中,，如果有自旋等待的任務(wù),，那就可以直接返回了，畢竟人家在自旋呢,，又沒(méi)有睡眠,；
- 沒(méi)有自旋等待任務(wù)，那就去喚醒等待列表中的任務(wù)了,；
3.2 寫(xiě)信號(hào)量
3.2.1 寫(xiě)者獲取鎖
- 寫(xiě)者的特點(diǎn)：看誰(shuí)都不順眼,，跟誰(shuí)都互斥，有我沒(méi)你,。只要有一個(gè)寫(xiě)者在持有鎖,，其他的讀者與寫(xiě)者都無(wú)法獲取,；
- 在寫(xiě)者獲取鎖的時(shí)候,，將
sem->count值加上RWSEM_ACTIVE_WRITE_BIAS，如果這個(gè)值不等于RWSEM_ACTIVE_WRITE_BIAS,，表示有其他的讀者或?qū)懻叱钟墟i,，因此獲取鎖失敗，調(diào)用rwsem_down_write_failed來(lái)處理,；
- 調(diào)用
rwsem_optimistic_spin進(jìn)行樂(lè)觀自旋去嘗試獲取鎖,，獲取了的話(huà)，則直接返回，optimistic spin可以參考《Linux Mutex機(jī)制分析》文章中的分析,，它的作用也是性能的優(yōu)化,，認(rèn)為鎖的持有者會(huì)很快釋放，因此當(dāng)前進(jìn)程選擇自旋而不是讓出CPU,，減少上下文切換帶來(lái)的開(kāi)銷(xiāo),；
- 如果等待列表中有讀者任務(wù)在睡眠等待，此時(shí)假如寫(xiě)者釋放了鎖,，那么需要先將讀者任務(wù)都給喚醒了,；如果等待列表中沒(méi)有任務(wù)，也就意味著當(dāng)前的寫(xiě)者是第一個(gè)任務(wù),，因此將
sem->count值加上RWSEM_WAITING_BIAS,；
- 循環(huán)等待獲取鎖，這個(gè)過(guò)程與
down_read是類(lèi)似的,；
總結(jié)
寫(xiě)者獲取鎖時(shí),，只要鎖被其他讀者或者寫(xiě)者持有了，則獲取鎖失敗,，然后進(jìn)行失敗情況處理,。在失敗情況下，它本身會(huì)嘗試進(jìn)行optimistic spin去嘗試獲取鎖,，如果獲取成功了,，那就是皆大歡喜了，否則還是需要進(jìn)入慢速路徑,。慢速路徑中去判斷等待列表中是否有任務(wù)在睡眠等待,，并且會(huì)再次嘗試去查看是否已經(jīng)有寫(xiě)者釋放了鎖，寫(xiě)者釋放了鎖,，并且只有讀者在睡眠等待,，那么此時(shí)應(yīng)該優(yōu)先讓這些先等待的任務(wù)喚醒
3.2.2 寫(xiě)者釋放鎖
- 寫(xiě)者釋放鎖的時(shí)候，有一個(gè)關(guān)鍵的操作,，將
sem->owner進(jìn)行清零操作,，在寫(xiě)者獲取鎖的時(shí)候會(huì)將該值設(shè)置成持有鎖的進(jìn)程；
- 釋放鎖的時(shí)候,，需要減去
RWSEM_ACTIVE_WRITE_BIAS,，然后再去判斷值，如果此時(shí)還有任務(wù)在睡眠等待,，那就進(jìn)行喚醒操作,；
3.3 總結(jié)
理解讀寫(xiě)信號(hào)量有幾個(gè)關(guān)鍵點(diǎn)：
- 讀寫(xiě)信號(hào)量的特性可以與讀寫(xiě)自旋鎖進(jìn)行類(lèi)比（讀者與讀者并發(fā)、讀者與寫(xiě)者互斥,、寫(xiě)者與寫(xiě)者互斥）,，區(qū)別在于讀寫(xiě)信號(hào)量可能會(huì)發(fā)生睡眠,，進(jìn)而帶來(lái)進(jìn)程切換的開(kāi)銷(xiāo),；
- 為了優(yōu)化讀寫(xiě)信號(hào)量的性能,，引入了
MCS鎖機(jī)制，進(jìn)一步減少切換開(kāi)銷(xiāo),。第一個(gè)寫(xiě)者獲取了鎖后,，第二個(gè)寫(xiě)者去獲取時(shí)自旋等待，而讀者去獲取時(shí)則會(huì)進(jìn)入睡眠,；
- 讀寫(xiě)信號(hào)量的
count值很關(guān)鍵,，代表著讀寫(xiě)信號(hào)量不同狀態(tài)的切換，因此也決定了執(zhí)行流程,；
- 讀者或?qū)懻哚尫沛i的時(shí)候,，去喚醒等待列表中的任務(wù)，需要分情況處理,。等待列表中可能存放的是讀者與寫(xiě)者的組合,，如果第一個(gè)任務(wù)是寫(xiě)者，則直接喚醒該寫(xiě)者,，否則將喚醒排在前邊的連續(xù)幾個(gè)讀者,；
參考
Real-world Concurrency
|
