《Linux原理與結(jié)構(gòu)》課件第9章

第九章互?斥?與?同?步9.1基礎(chǔ)操作9.2自旋鎖9.3序號(hào)鎖9.4RCU機(jī)制9.5信號(hào)量9.6信號(hào)量集合雖然進(jìn)程有各自獨(dú)立的虛擬地址空間，一般情況下不會(huì)出現(xiàn)交叉引用的問(wèn)題，但由于它們運(yùn)行在同一個(gè)計(jì)算環(huán)境中，共用同一個(gè)內(nèi)核，不可避免地會(huì)發(fā)生一些相互作用，如競(jìng)爭(zhēng)獨(dú)占資源、訪問(wèn)共享對(duì)象、協(xié)調(diào)多方動(dòng)作等。獨(dú)占資源(如處理器、外部設(shè)備等)同時(shí)只能由一個(gè)進(jìn)程使用，對(duì)獨(dú)占資源競(jìng)爭(zhēng)的結(jié)果是一個(gè)進(jìn)程獲得，其它進(jìn)程等待。共享對(duì)象(如共用的數(shù)據(jù)結(jié)構(gòu)等)允許多個(gè)進(jìn)程訪問(wèn)，但訪問(wèn)操作應(yīng)是原子的，不應(yīng)出現(xiàn)交叉重疊。相互協(xié)作的進(jìn)程(如生產(chǎn)者與消費(fèi)者進(jìn)程)之間需要協(xié)調(diào)動(dòng)作，以便保持步調(diào)一致。為了使進(jìn)程之間能夠和諧共處、有序競(jìng)爭(zhēng)，操作系統(tǒng)需要提供保證機(jī)制，大致包括互斥(MutualExclusion)與同步(Synchronization)?；コ馐且环N競(jìng)爭(zhēng)機(jī)制，用于保護(hù)共享的獨(dú)占資源。同步是一種協(xié)調(diào)機(jī)制，用于統(tǒng)一進(jìn)程的步調(diào)。互斥是排外的、封閉的，表示資源屬于自己，不許別的進(jìn)程再動(dòng)，因而多使用鎖(Lock)。同步是開(kāi)放的、合作的，在自己完成某個(gè)動(dòng)作或用完某個(gè)資源之后會(huì)主動(dòng)通知合作者或喚醒等待者，因而常使用信號(hào)燈或信號(hào)量(Semaphore)。

Linux內(nèi)核提供了多種互斥與同步機(jī)制，如自旋鎖、序號(hào)鎖、RCU、信號(hào)量、信號(hào)量集合等。除信號(hào)量集合之外，其余機(jī)制都是內(nèi)核自己使用的，用于保護(hù)被所有進(jìn)程共用的內(nèi)核資源、協(xié)調(diào)核內(nèi)進(jìn)程的動(dòng)作。可以說(shuō)沒(méi)有互斥與同步機(jī)制，就無(wú)法保證內(nèi)核的和諧與穩(wěn)定。

為了實(shí)現(xiàn)多處理器或并發(fā)環(huán)境中的互斥與同步機(jī)制，內(nèi)核需要提供一些基礎(chǔ)操作，如格柵操作、原子操作、搶占屏蔽操作、進(jìn)程等待操作等。格柵操作用于設(shè)定一些特殊的控制點(diǎn)，以保證點(diǎn)后指令不會(huì)在點(diǎn)前指令完全完成之前開(kāi)始執(zhí)行，從而控制指令的執(zhí)行順序。原子操作是對(duì)單個(gè)內(nèi)存變量的不可分割的基本操作(如變量加、減等)，用于保證某些特殊內(nèi)存操作的完整性。搶占屏蔽操作用于控制進(jìn)程的調(diào)度時(shí)機(jī)，如禁止某些場(chǎng)合下的進(jìn)程調(diào)度等。進(jìn)程睡眠與等待操作用于管理進(jìn)程等待隊(duì)列，以便在條件成熟時(shí)喚醒其中的進(jìn)程。9.1基礎(chǔ)操作9.1.1格柵操作

正常情況下，編譯或匯編器按序生成程序代碼，處理器也按序執(zhí)行程序代碼，不會(huì)出現(xiàn)亂序現(xiàn)象。然而，為了提高執(zhí)行速度，目前的匯編和編譯器通常會(huì)對(duì)程序進(jìn)行優(yōu)化，如調(diào)整指令順序等，處理器在執(zhí)行指令期間也會(huì)采取一些加速措施，如高速緩存、亂序發(fā)射、并行執(zhí)行等，因而進(jìn)程對(duì)內(nèi)存的實(shí)際訪問(wèn)順序可能與程序的預(yù)定順序不一致。大部分情況下，指令順序的調(diào)整不會(huì)改變程序的行為，但也有一些例外，如將臨界區(qū)內(nèi)的指令移到臨界區(qū)外執(zhí)行就可能產(chǎn)生難以預(yù)料的后果。為了保證程序行為的一致性，Intel處理器提供了特殊指令、GCC編譯器提供了優(yōu)化格柵、Linux操作系統(tǒng)提供了內(nèi)存格柵操作，用于控制指令的執(zhí)行順序。優(yōu)化格柵用于防止編譯器的過(guò)度優(yōu)化，以保證所生成代碼的正確性。Linux實(shí)現(xiàn)的優(yōu)化格式是宏barrier，定義如下：

#definebarrier()_asm__volatile_("":::"memory")

宏barrier告訴編譯器三件事：將要插入一段匯編代碼(_asm_)、不要將這段代碼與其它代碼重組(_volatile_)、所有的內(nèi)存位置都已改變(memory)，因而此前保存在寄存器中的所有內(nèi)存單元的內(nèi)容都已失效，此后對(duì)內(nèi)存的訪問(wèn)需要重新讀入，不能用已有的寄存器內(nèi)容對(duì)程序進(jìn)行優(yōu)化。內(nèi)存格柵用于保證指令的執(zhí)行順序。在Intel處理器中，有些指令是串行執(zhí)行的，可以作為內(nèi)存格柵，如I/O指令、帶lock前綴的指令、寫控制寄存器的指令等。另外，Intel處理器還專門引入了三條格柵指令，其中l(wèi)fence(讀格柵)保證其后的讀操作不會(huì)在其前的讀操作完全完成之前開(kāi)始，sfence(寫格柵)保證其后的寫操作不會(huì)在其前的寫操作完全完成之前開(kāi)始，mfence(讀寫格柵)保證其后的讀寫操作不會(huì)在其前的讀寫操作完全完成之前開(kāi)始。

Linux提供了多個(gè)內(nèi)存格柵宏，它們其實(shí)就是對(duì)上述三條指令的包裝，如下：

#definemb() asmvolatile("mfence":::"memory") //讀寫內(nèi)存格柵

#definermb() asmvolatile("lfence":::"memory") //讀內(nèi)存格柵

#definewmb() asmvolatile("sfence":::"memory") //寫內(nèi)存格柵

因而，格柵就是屏障，只有當(dāng)前面的指令完全執(zhí)行完之后其后的指令才會(huì)開(kāi)始執(zhí)行。在程序中插入格柵可以保證程序的執(zhí)行順序，雖然會(huì)影響程序的執(zhí)行性能。9.1.2原子操作

由于機(jī)器指令的功能過(guò)于簡(jiǎn)單，一個(gè)稍微復(fù)雜的操作通常都必須用多條指令完成。如操作x=x+3通常被翻譯成三條指令：將x的值讀入到某個(gè)寄存器、將寄存器的值加3、將寄存器的內(nèi)容寫回x。考慮如下情形：

(1)在第一條指令完成之后、第三條指令完成之前出現(xiàn)了中斷；

(2)在中斷返回之前處理器再次訪問(wèn)了變量x，如執(zhí)行了x=x+5。

此時(shí)，x值的變化會(huì)出現(xiàn)不一致性，其結(jié)果是x+3而不是x+8。出現(xiàn)上述問(wèn)題的原因是操作的原子性(不可分割)被破壞了。由于中斷的出現(xiàn)，一個(gè)完整操作的中間被隨機(jī)地插入了其它操作。這一問(wèn)題的解決方法比較簡(jiǎn)單，關(guān)閉中斷即可避免這種操作插入現(xiàn)象。

更復(fù)雜的情況出現(xiàn)在多處理器環(huán)境中，此時(shí)，一個(gè)變量可能被多個(gè)處理器同時(shí)訪問(wèn)。如兩個(gè)處理器同時(shí)執(zhí)行x

=

x

+

3操作，其結(jié)果將是x

+

3而不是x

+

6。引起這一問(wèn)題的原因仍然是操作的原子性被破壞了(在x上同時(shí)施加了兩個(gè)操作)。這一問(wèn)題的解決需要處理器的支持，并需要操作系統(tǒng)提供相應(yīng)的手段。

Intel處理器提供了lock前綴，用于將一條內(nèi)存訪問(wèn)指令(如add、sub、inc、dec等)轉(zhuǎn)化成原子指令。如果某條指令之前有l(wèi)ock前綴，那么在執(zhí)行該指令期間處理器會(huì)鎖住內(nèi)存總線，以保證不會(huì)出現(xiàn)多個(gè)處理器同時(shí)訪問(wèn)一個(gè)內(nèi)存變量的現(xiàn)象。

為了保證C語(yǔ)言操作的原子性，Linux定義了原子類型atomic_t并提供了一組該類型上的原子操作。原子類型實(shí)際就是整型，多被嵌入在其它結(jié)構(gòu)中，定義如下：

typedefstruct{

intcounter;

}atomic_t;

在Intel處理器上，原子加法操作由atomic_add實(shí)現(xiàn)，其實(shí)現(xiàn)代碼如下：

staticinlinevoidatomic_add(inti,atomic_t*v){

asmvolatile(LOCK_PREFIX"addl%1,%0"

:"+m"(v->counter)

:"ir"(i));

}在多處理器平臺(tái)上，宏LOCK_PREFIX就是lock前綴，用于保證加法操作的原子性，即保證在指令add執(zhí)行期間不會(huì)有其它處理器訪問(wèn)變量v。與原子加法操作的實(shí)現(xiàn)思路類似，Linux還實(shí)現(xiàn)了多個(gè)其它的原子操作，如表9.1所示。

表9.1Linux的原子操作9.1.3搶占屏蔽操作

在當(dāng)前進(jìn)程未主動(dòng)放棄處理器的情況下，如果系統(tǒng)中出現(xiàn)了更值得運(yùn)行的進(jìn)程，那么應(yīng)該將處理器從當(dāng)前進(jìn)程手中強(qiáng)行收回，以便讓新就緒的進(jìn)程盡快運(yùn)行，這一過(guò)程稱為搶占調(diào)度。搶占使處理器的分配更加合理，也可提升系統(tǒng)的反應(yīng)能力，但會(huì)增加設(shè)計(jì)的復(fù)雜性。

搶占條件通常由中斷處理程序創(chuàng)造，搶占時(shí)機(jī)通常在中斷返回之前。如果中斷之前的處理器運(yùn)行在用戶態(tài)，那么在從核心態(tài)返回用戶態(tài)之前進(jìn)行搶占調(diào)度不會(huì)引起不一致性問(wèn)題。但如果中斷之前的處理器運(yùn)行在核心態(tài)，那么在中斷返回之前進(jìn)行的搶占調(diào)度就有可能導(dǎo)致內(nèi)核數(shù)據(jù)的不一致性。如中斷之前處理器正在修改內(nèi)核中的某個(gè)鏈表，那么在修改完成之前的搶占調(diào)度有可能破壞該鏈表的一致性。早期的Linux禁止內(nèi)核態(tài)搶占。新版本的Linux允許內(nèi)核態(tài)搶占，但需要某種機(jī)制來(lái)控制搶占的時(shí)機(jī)。

控制內(nèi)核態(tài)搶占的一種方法是關(guān)、開(kāi)中斷。在修改某些關(guān)鍵數(shù)據(jù)結(jié)構(gòu)之前將中斷關(guān)閉，在修改完成之后再將中斷打開(kāi)。但關(guān)、開(kāi)中斷的代價(jià)較高，因而Linux又引入了搶占計(jì)數(shù)preempt_count(位于進(jìn)程的thread_info結(jié)構(gòu)中，如圖4.8所示)，每個(gè)進(jìn)程一個(gè)，表示該進(jìn)程當(dāng)前是否可被搶占。操作preempt_disable()將當(dāng)前進(jìn)程的搶占計(jì)數(shù)加1，從而禁止搶占該進(jìn)程。

操作preempt_enable()將當(dāng)前進(jìn)程的搶占計(jì)數(shù)減1，而后試圖進(jìn)行搶占調(diào)度。調(diào)度的條件是：當(dāng)前進(jìn)程上設(shè)置了TIF_NEED_RESCHED標(biāo)志且當(dāng)前進(jìn)程的搶占計(jì)數(shù)是0且當(dāng)前處理器的中斷未被屏蔽。

上述兩個(gè)操作都帶有優(yōu)化格柵，保證能使后面的程序看到它們的操作結(jié)果。由操作preempt_disable()和preempt_enable()括起來(lái)的區(qū)域允許中斷，但不可搶占。在從中斷返回到核心態(tài)之前，如果當(dāng)前進(jìn)程的搶占計(jì)數(shù)不是0，即使其上設(shè)置了TIF_NEED_RESCHED標(biāo)志，善后處理程序也不會(huì)進(jìn)行進(jìn)程調(diào)度(如圖4.3所示)。9.1.4睡眠與等待操作

正在運(yùn)行的進(jìn)程可以主動(dòng)請(qǐng)求睡眠(sleep_on())，從而進(jìn)入等待狀態(tài)。進(jìn)程可以在不可中斷等待狀態(tài)下睡眠，也可以在可中斷等待狀態(tài)下睡眠。進(jìn)程可以預(yù)定一個(gè)睡眠時(shí)間，也可以不預(yù)定睡眠時(shí)間(長(zhǎng)眠)。Linux將睡眠進(jìn)程掛在自己指定的等待隊(duì)列中。等待隊(duì)列由類型wait_queue_head_t定義，如下：

struct_

_wait_queue_head{

spinlock_t lock; //保護(hù)鎖

structlist_head task_list; //隊(duì)列

};

typedefstruct_

_wait_queue_head wait_queue_head_t;

睡眠者進(jìn)程先將自己包裝在一個(gè)_

_wait_queue結(jié)構(gòu)中，而后掛在指定的等待隊(duì)列上，最后請(qǐng)求調(diào)度(執(zhí)行函數(shù)schedule())，放棄處理器，進(jìn)入等待狀態(tài)。

struct_

_wait_queue{

unsignedint flags; //標(biāo)志，總是1

void *private; //指向睡眠者進(jìn)程的task_struct結(jié)構(gòu)

wait_queue_func_t func; //睡眠到期后的處理函數(shù)

structlist_head task_list; //隊(duì)列節(jié)點(diǎn)

};

typedefstruct_

_wait_queue wait_queue_t;

如果進(jìn)程預(yù)定了睡眠時(shí)間，Linux會(huì)為其啟動(dòng)一個(gè)定時(shí)器。當(dāng)定時(shí)器到期時(shí)，Linux會(huì)將睡眠的進(jìn)程喚醒(將其狀態(tài)改為TASK_RUNNING并加入就緒隊(duì)列)。如果進(jìn)程在到期之前被喚醒，睡眠操作會(huì)返回剩余的睡眠時(shí)間。

未預(yù)定睡眠時(shí)間的進(jìn)程只能被顯式喚醒(wake_up())。喚醒操作順序執(zhí)行等待隊(duì)列中各

_

_wait_queue結(jié)構(gòu)中的func操作，喚醒等待的進(jìn)程。喚醒者進(jìn)程可以指定被喚醒進(jìn)程的狀態(tài)和一次可喚醒的進(jìn)程數(shù)量。

除了睡眠之外，進(jìn)程還可以等待某個(gè)事件(又稱為條件變量)。等待者進(jìn)程可以將自己置于不可中斷等待狀態(tài)或可中斷等待狀態(tài)，且可以預(yù)定一個(gè)最長(zhǎng)等待時(shí)間。Linux用結(jié)構(gòu)completion描述這種條件等待隊(duì)列，如下：

structcompletion{

unsignedint done; //0表示等待的事件未發(fā)生，>0表示已發(fā)生

wait_queue_head_t wait; //等待隊(duì)列

};欲等待某事件的進(jìn)程通過(guò)wait_for_completion()類的操作將自己置為等待狀態(tài)并掛在等待隊(duì)列中，而后請(qǐng)求調(diào)度，放棄處理器。此后進(jìn)程將一直等待，直到自己等待的事件發(fā)生(done大于1并被喚醒)或等待了足夠長(zhǎng)的時(shí)間。

等待事件的進(jìn)程可被操作complete()或complete_all()喚醒。操作complete()將done加1并喚醒隊(duì)列中的第一個(gè)進(jìn)程，操作complete_all()將done加0x7FFFFFFF而后喚醒隊(duì)列中的所有進(jìn)程。

原子操作只能保證一條指令的原子性，因而僅能實(shí)現(xiàn)單個(gè)變量的互斥使用。若要實(shí)現(xiàn)一個(gè)數(shù)據(jù)結(jié)構(gòu)的互斥使用，就需要保證一個(gè)程序片段的原子性，需要更復(fù)雜的互斥手段。自旋鎖就是其中之一。9.2自旋鎖在操作系統(tǒng)中，一次只允許一個(gè)進(jìn)程使用的資源稱為獨(dú)占資源或臨界資源(Criticalresource)，訪問(wèn)臨界資源的程序片段稱為臨界區(qū)(Criticalsection)。自旋鎖的主要作用是保證對(duì)臨界資源的互斥使用，或者說(shuō)保證臨界區(qū)的原子性。9.2.1自旋鎖的概念

實(shí)現(xiàn)進(jìn)程互斥的方法很多，如純軟件方法(Peterson算法)、純硬件方法(開(kāi)關(guān)中斷)等，但最直觀、最簡(jiǎn)潔的方法是鎖(Lock)。鎖用于保護(hù)使用時(shí)間很短的臨界資源，每種臨界資源都需要一把保護(hù)鎖。進(jìn)程在使用臨界資源之前需要先申請(qǐng)到該資源的保護(hù)鎖。獲得鎖的進(jìn)程可以使用資源，但在用完之后應(yīng)盡快將鎖釋放。在一個(gè)特定的時(shí)間點(diǎn)上，最多只有一個(gè)進(jìn)程能獲得某個(gè)特定的鎖。在無(wú)法立刻獲得鎖時(shí)，進(jìn)程忙等測(cè)試，因而又將這種保護(hù)鎖稱為自旋鎖(spinlock)。由自旋鎖保護(hù)的臨界區(qū)的格式如下：

<加鎖(spin_lock)>

<臨界區(qū)(criticalsection)>

<解鎖(spin_unlock)>

如果加鎖操作成功，進(jìn)程可立刻進(jìn)入臨界區(qū)，否則將在加鎖操作中自旋等待。

自旋鎖一般用在多處理器環(huán)境中。申請(qǐng)鎖的進(jìn)程和持有鎖的進(jìn)程運(yùn)行在不同的處理器上，申請(qǐng)鎖的進(jìn)程通過(guò)簡(jiǎn)單的忙等測(cè)試等待持有鎖的進(jìn)程釋放自旋鎖。在單處理器環(huán)境中，自旋鎖退化成了空語(yǔ)句，或簡(jiǎn)單的開(kāi)、關(guān)中斷操作。

自旋鎖不能嵌套使用。持有自旋鎖的進(jìn)程再次申請(qǐng)同一個(gè)自旋鎖會(huì)使程序進(jìn)入死循環(huán)，導(dǎo)致死鎖(無(wú)限期地等待自己解鎖)。為了實(shí)現(xiàn)自旋鎖，至少需要定義一個(gè)鎖變量和一組鎖操作。鎖變量用于記錄鎖的狀態(tài)(忙、閑)，鎖操作用于測(cè)試和修改鎖的狀態(tài)，實(shí)現(xiàn)加鎖和解鎖語(yǔ)義。鎖變量必須是共享的，使用同一個(gè)自旋鎖的所有進(jìn)程或處理器看到的應(yīng)該是同一個(gè)鎖變量，因而鎖通常用在內(nèi)核中。當(dāng)然，對(duì)鎖狀態(tài)的修改操作必須是原子的。9.2.2經(jīng)典自旋鎖

Linux用類型spinlock_t(或結(jié)構(gòu)spinlock)描述自旋鎖。在Intel處理器上，結(jié)構(gòu)spinlock的定義如下：

typedefstructarch_spinlock{

unsignedint slock; //記錄鎖狀態(tài)

}arch_spinlock_t;

typedefstructraw_spinlock{

arch_spinlock_t raw_lock;

}raw_spinlock_t;

typedefstructspinlock{

structraw_spinlock rlock;

}spinlock_t;由此可見(jiàn)，自旋鎖實(shí)際是一個(gè)經(jīng)過(guò)多層包裝的無(wú)符號(hào)整型變量，其值的意義取決于加鎖與解鎖算法的設(shè)計(jì)。在Linux的演變過(guò)程中，自旋鎖的實(shí)現(xiàn)算法也在不斷演變。

(1)算法1把鎖狀態(tài)看成一個(gè)整數(shù)，1表示鎖閑，0表示鎖忙。加鎖操作將鎖狀態(tài)減1，如果減后的值不是負(fù)數(shù)，則獲得鎖，否則循環(huán)測(cè)試，直到鎖的狀態(tài)變成正數(shù)。解鎖操作將鎖狀態(tài)置1。減1與置1操作都是原子的。算法1的實(shí)現(xiàn)流程如圖9.1所示。圖9.1加鎖解鎖算法1

(2)算法2把鎖狀態(tài)看成一個(gè)位圖，只用它的第0位，0表示鎖閑，1表示鎖忙。加鎖操作在把第0位的值取出的同時(shí)將其置1。如果取出的值是0，則獲得鎖，否則循環(huán)測(cè)試，直到第0位變成0。解鎖操作將第0位清0。位的檢測(cè)與設(shè)置(清除)操作都是原子的，由帶lock前綴的指令BTS(位檢測(cè)與設(shè)置)和BTR(位檢測(cè)與清除)實(shí)現(xiàn)。

上述兩個(gè)算法實(shí)現(xiàn)了自旋鎖的語(yǔ)義，可以保證在一個(gè)特定的時(shí)刻最多只有一個(gè)進(jìn)程能獲得自旋鎖，但都存在著無(wú)序競(jìng)爭(zhēng)的問(wèn)題。假如在進(jìn)程1持有鎖sl期間，進(jìn)程2和進(jìn)程3先后申請(qǐng)了該鎖，那么當(dāng)進(jìn)程1釋放sl時(shí)，應(yīng)該是進(jìn)程2先獲得，進(jìn)程3后獲得。但上述兩種實(shí)現(xiàn)無(wú)法保證這一點(diǎn)。為此，Linux又給出了算法3。

(3)算法3把鎖狀態(tài)看成兩個(gè)無(wú)符號(hào)整數(shù)(8位或16位)，一個(gè)為申請(qǐng)序號(hào)req，一個(gè)為使用序號(hào)use，兩個(gè)序號(hào)的初值都是0。加鎖操作獲得鎖的當(dāng)前申請(qǐng)序號(hào)同時(shí)將其加1，而后比較自己獲得的申請(qǐng)序號(hào)和鎖的使用序號(hào)，如兩者相等，則獲得鎖，否則忙等測(cè)試，直到鎖的使用序號(hào)與自己的申請(qǐng)序號(hào)相等為止。解鎖操作將鎖的使用序號(hào)加1。算法3的實(shí)現(xiàn)流程如圖9.2所示。

圖9.2加鎖解鎖算法3當(dāng)申請(qǐng)序號(hào)等于使用序號(hào)時(shí)，鎖空閑。當(dāng)申請(qǐng)序號(hào)大于使用序號(hào)時(shí)，鎖繁忙(req-use-1是等待自旋鎖的進(jìn)程數(shù))。當(dāng)有多個(gè)進(jìn)程等待同一自旋鎖時(shí)，它們將按申請(qǐng)的順序獲得鎖，先申請(qǐng)者先得，后申請(qǐng)者后得，避免了無(wú)序競(jìng)爭(zhēng)。算法3優(yōu)于算法1和算法2。然而算法3不能避免持有鎖的進(jìn)程被搶占。一旦持有者進(jìn)程被搶占，它將停留在自己的臨界區(qū)中，無(wú)法及時(shí)執(zhí)行解鎖操作，會(huì)導(dǎo)致等待該鎖的其它進(jìn)程(或處理器)長(zhǎng)時(shí)間自旋。因而，完整的加、解鎖實(shí)現(xiàn)應(yīng)包括搶占屏蔽，在加鎖操作中屏蔽搶占，在解鎖操作中使能搶占，如下：

voidspin_lock(spinlock_t*lock){

preempt_disable(); //搶占屏蔽

arch_spin_lock(lock->rlock.raw_lock);

}

voidspin_unlock(spinlock_t*lock){

arch_spin_unlock(lock->rlock.raw_lock);

preempt_enable(); //搶占使能

}

即使進(jìn)程在持有鎖期間被設(shè)置了TIF_NEED_RESCHED標(biāo)志，搶占調(diào)度也不會(huì)立刻發(fā)生。事實(shí)上，搶占調(diào)度會(huì)被推遲到解鎖之時(shí)，此時(shí)進(jìn)程已退出了臨界區(qū)。9.2.3帶中斷屏蔽的自旋鎖

增加了搶占屏蔽的自旋鎖已經(jīng)比較可靠，但仍然可能讓等待鎖的進(jìn)程長(zhǎng)期自旋，原因是持有者進(jìn)程可能被中斷。若持有鎖的進(jìn)程被中斷，處理器將轉(zhuǎn)去執(zhí)行中斷處理程序，從而會(huì)延長(zhǎng)其它進(jìn)程的等待時(shí)間。更嚴(yán)重的是，如果中斷處理程序再次申請(qǐng)同一個(gè)自旋鎖，則會(huì)導(dǎo)致鎖的嵌套使用，使系統(tǒng)無(wú)法繼續(xù)運(yùn)行(死鎖)。為解決這一問(wèn)題，Linux又提供了帶中斷屏蔽的自旋鎖，如下：

voidspin_lock_irq(spinlock_t*lock){

local_irq_disable(); //關(guān)中斷

spin_lock(lock);

}

voidspin_unlock_irq(spinlock_t*lock){

spin_unlock(lock);

local_irq_enable(); //開(kāi)中斷

}增加了關(guān)、開(kāi)中斷操作之后，可以保證持有鎖的進(jìn)程不會(huì)被中斷，當(dāng)然也就不會(huì)被搶占。然而上述兩個(gè)操作對(duì)中斷的處理不夠精細(xì)。如果在spin_lock_irq執(zhí)行之前中斷已被關(guān)閉，那么在spin_unlock_irq之后無(wú)條件地打開(kāi)中斷就會(huì)帶來(lái)問(wèn)題。較好的做法是在加鎖操作中保存中斷狀態(tài)(在EFLAGS中)，在解鎖操作中恢復(fù)中斷狀態(tài)。為此，Linux又提供了spin_lock_irqsave(lock,flags)和spin_unlock_irqrestore(lock,flags)。操作spin_lock_irqsave(lock,flags)完成三件事，一是將EFLAGS中的中斷狀態(tài)保存在flags中，二是關(guān)閉中斷，三是執(zhí)行l(wèi)ock上的加鎖操作。

操作spin_unlock_irqrestore(lock,flags)完成兩件事，一是執(zhí)行l(wèi)ock上的解鎖操作，二是根據(jù)flags恢復(fù)EFLAGS中的中斷狀態(tài)。9.2.4讀寫自旋鎖

增加了關(guān)、開(kāi)中斷之后的自旋鎖已經(jīng)比較完善，但仍然不夠精細(xì)，因?yàn)樗鼪](méi)有考慮進(jìn)程對(duì)臨界資源的使用方式。事實(shí)上，進(jìn)程對(duì)臨界資源的使用方式大致可分為兩類，一是只讀使用，二是讀寫使用。為了保證對(duì)臨界資源的可靠使用，不應(yīng)該允許多個(gè)進(jìn)程同時(shí)修改(寫)臨界資源。當(dāng)一個(gè)進(jìn)程在寫臨界資源時(shí)，其它進(jìn)程不應(yīng)該寫，也不應(yīng)該讀。然而，為了提高臨界資源的利用率，應(yīng)該允許多個(gè)進(jìn)程同時(shí)讀臨界資源。當(dāng)有進(jìn)程在讀臨界資源時(shí)，其它進(jìn)程可以同時(shí)讀，但不應(yīng)該寫。區(qū)分了讀、寫操作的自旋鎖稱為讀寫自旋鎖。在同一時(shí)間段內(nèi)，讀寫自旋鎖保護(hù)的資源可能正在被一個(gè)進(jìn)程寫，也可能正在被多個(gè)進(jìn)程讀。讀寫自旋鎖同樣只適用于多處理器環(huán)境，在單處理器系統(tǒng)中，讀寫自旋鎖或者為空，或者就是關(guān)中斷和開(kāi)中斷。

Linux用類型rwlock_t表示讀寫自旋鎖。在Intel處理器上，rwlock_t的定義如下：

typedefstruct{

unsignedint rw;

}arch_rwlock_t;

typedefstruct{

arch_rwlock_t raw_lock;

}rwlock_t;

由此可見(jiàn)，讀寫自旋鎖實(shí)際是一個(gè)經(jīng)過(guò)多層包裝的無(wú)符號(hào)整數(shù)，其意義取決于加、解鎖算法的設(shè)計(jì)。在較早的版本中，Linux將rw分成兩部分，其中的第31位用于記錄寫鎖狀態(tài)(0為空閑、1為繁忙)，其余31位用于記錄讀者個(gè)數(shù)(0表示無(wú)讀者)，鎖的初值是0。讀加鎖、解鎖操作與寫加鎖、解鎖操作的實(shí)現(xiàn)流程如圖9.3所示。圖9.3老讀寫自旋鎖實(shí)現(xiàn)算法在新的實(shí)現(xiàn)中，讀寫自旋鎖的初值被設(shè)為0x01000000，讀加鎖與寫加鎖操作的實(shí)現(xiàn)算法基本相同，都是先將鎖的值減去一個(gè)常數(shù)，而后判斷結(jié)果的正負(fù)。非負(fù)則獲得鎖，負(fù)則循環(huán)等待。不同的是，寫加鎖操作減去的常數(shù)是0x01000000，讀加鎖操作減去的常數(shù)是1。寫解鎖操作將鎖的值加0x01000000，讀解鎖操作將鎖的值加1。

如果鎖是空閑的(既無(wú)讀者也無(wú)寫者)，讀加鎖與寫加鎖操作都會(huì)成功。如果有寫者，讀加鎖與寫加鎖都會(huì)失敗。如果有讀者，只要讀者個(gè)數(shù)不超過(guò)0x01000000，讀加鎖操作都會(huì)成功，但寫加鎖操作肯定失敗。讀加鎖操作成功的條件是沒(méi)有寫者，寫加鎖操作成功的條件是既無(wú)讀者也無(wú)寫者。新讀寫自旋鎖的實(shí)現(xiàn)流程如圖9.4所示。圖9.4新讀寫自旋鎖實(shí)現(xiàn)算法當(dāng)然，真正的讀寫自旋鎖操作還要照顧到搶占，實(shí)現(xiàn)的函數(shù)如下。

voidxx_lock(rwlock_t*lock){ //xx是read或write

preempt_disable(); //搶占屏蔽

arch_xx_lock(lock->raw_lock);

}

voidxx_unlock(rwlock_t*lock){ //xx是read或write

arch_xx_unlock(lock->raw_lock);

preempt_enable(); //搶占使能

}

為了照顧中斷，Linux還提供了xx_lock_irq()、xx_unlock_irq()、xx_lock_irqsave()、xx_unlock_irqrestore()等操作(其中的xx是read或write)。但Linux未解決讀寫自旋鎖的無(wú)序競(jìng)爭(zhēng)問(wèn)題。

由讀寫自旋鎖的實(shí)現(xiàn)可知，讀鎖是共享的，寫鎖是排他的。讀鎖允許嵌套使用，但寫鎖不能嵌套。讀鎖不會(huì)自動(dòng)升級(jí)到寫鎖。讀寫自旋鎖一般用于保護(hù)讀多、寫少的資源。

讀寫自旋鎖更偏愛(ài)讀者，在讀多寫少的情況下，寫者的等待時(shí)間會(huì)更長(zhǎng)。為了照顧寫者，Linux又引入了序號(hào)鎖。序號(hào)鎖是一種讀寫鎖，不過(guò)它更偏愛(ài)寫者。

序號(hào)鎖的寫者不需要等待讀者，只要沒(méi)有其它寫者，即可開(kāi)始修改資源。為了與其它寫者互斥，寫者在使用資源之前需要先申請(qǐng)序號(hào)寫鎖。寫者使用資源的過(guò)程如下：

write_seqlock(&seq_lock); //申請(qǐng)序號(hào)寫鎖

/*臨界區(qū)，讀、寫數(shù)據(jù)*/9.3序號(hào)鎖

write_sequnlock(&seq_lock); //釋放序號(hào)寫鎖

序號(hào)鎖的讀者不需要預(yù)先申請(qǐng)鎖，可直接對(duì)資源進(jìn)行讀操作，但讀出的數(shù)據(jù)可能不準(zhǔn)確(如正在被寫者修改)，因而需要對(duì)讀出的結(jié)果進(jìn)行測(cè)試，并在必要時(shí)重讀。讀者使用資源的過(guò)程如下：

unsignedlongseq;

do{

seq=read_seqbegin(&seq_lock); //先獲得序號(hào)

/*直接讀數(shù)據(jù)，但讀出的結(jié)果不一定正確，因而要測(cè)試*/

}while(read_seqretry(&seq_lock,seq)); //根據(jù)序號(hào)確定讀出的數(shù)據(jù)是否準(zhǔn)確

序號(hào)鎖由類型seqlock_t定義，其中包含一個(gè)序號(hào)和一個(gè)經(jīng)典自旋鎖，如下：

typedefstruct{

unsigned sequence; //序號(hào)

spinlock_t lock; //經(jīng)典自旋鎖

}seqlock_t;初始情況下，序號(hào)sequence是0，自旋鎖lock處于空閑狀態(tài)。

寫加鎖、解鎖算法的實(shí)現(xiàn)如下：

voidwrite_seqlock(seqlock_t*sl){

spin_lock(&sl->lock); //申請(qǐng)自旋鎖

++sl->sequence; //序號(hào)加1

wmb(); //內(nèi)存格柵，保證內(nèi)存中的數(shù)據(jù)確被修改

}

voidwrite_sequnlock(seqlock_t*sl){

wmb(); //內(nèi)存格柵，保證內(nèi)存中的數(shù)據(jù)確被修改

sl->sequence++; //序號(hào)加1

spin_unlock(&sl->lock); //釋放自旋鎖

}

由此可見(jiàn)，序號(hào)鎖中的序號(hào)是單調(diào)增長(zhǎng)的。如果序號(hào)鎖正被某個(gè)寫者持有，它的序號(hào)肯定是奇數(shù)，否則，序號(hào)是偶數(shù)。函數(shù)read_seqbegin()讀出序號(hào)鎖的當(dāng)前序號(hào)，并保證讀出的序號(hào)一定是偶數(shù)。

如果序號(hào)鎖的當(dāng)前序號(hào)與已讀出的序號(hào)相等，函數(shù)read_seqretry()的返回值是假，表示讀者讀出的數(shù)據(jù)是準(zhǔn)確的，可以直接使用。如果序號(hào)鎖的當(dāng)前序號(hào)與已讀出的序號(hào)不等，函數(shù)read_seqretry()的返回值是真，表示讀出的數(shù)據(jù)不準(zhǔn)，需要重讀。

當(dāng)然，以上述函數(shù)為基礎(chǔ)還可以實(shí)現(xiàn)帶中斷屏蔽的序號(hào)鎖等。

鎖的基本語(yǔ)義是互斥，即在一個(gè)特定的時(shí)間點(diǎn)上僅允許一個(gè)進(jìn)程使用資源。這種嚴(yán)格的互限制會(huì)使操作串行化，且會(huì)使等待者進(jìn)程空轉(zhuǎn)，影響系統(tǒng)的性能。因而，對(duì)鎖的改進(jìn)大都集中在提高系統(tǒng)的并發(fā)性上，即在保證數(shù)據(jù)一致性的前提下盡可能地允許多個(gè)進(jìn)程同時(shí)使用資源。

經(jīng)典自旋鎖所保護(hù)的資源不允許并發(fā)使用，只有鎖的持有者能夠使用資源，其它進(jìn)程只能空轉(zhuǎn)等待。讀寫自旋鎖所保護(hù)的資源允許多個(gè)讀者并發(fā)使用，但不允許寫者與讀者并發(fā)使用。9.4RCU機(jī)制序號(hào)鎖所保護(hù)的資源允許寫者與讀者并發(fā)使用，但并發(fā)的結(jié)果是寫者的工作有效而讀者的工作可能需要重做，是一種偽并發(fā)。RCU(read-copyupdate)機(jī)制所保護(hù)的資源允許寫者和讀者同時(shí)使用，并能保證讀者和寫者的工作同樣有效。9.4.1RCU實(shí)現(xiàn)思路

RCU不是嚴(yán)格意義上的鎖，它僅是一種使用資源的方法或機(jī)制。Linux在2.5版中首次引入了RCU機(jī)制，在隨后的發(fā)展中又對(duì)其進(jìn)行了多次改進(jìn)，形成了多個(gè)實(shí)現(xiàn)版本，如經(jīng)典RCU、層次(樹形)RCU、微型RCU等，目前缺省的實(shí)現(xiàn)是層次RCU。

RCU的基本思想是對(duì)讀者稍加限制，而對(duì)寫者嚴(yán)格要求，因而讀者的開(kāi)銷極小，而寫者的開(kāi)銷稍大。所以，RCU機(jī)制更適合保護(hù)讀多寫少的資源。

RCU的讀者不需要理會(huì)寫者，只要需要即可進(jìn)入臨界區(qū)執(zhí)行讀操作。RCU約定讀者只能在臨界區(qū)中使用資源，且在使用之前必須先獲得對(duì)資源的引用(指針)，而后再通過(guò)引用使用(讀)資源；在臨界區(qū)外，對(duì)資源的引用將失效，或者說(shuō)，讀者不能在臨界區(qū)外使用資源；在臨界區(qū)中的讀者不允許搶占。讀者使用資源的典型過(guò)程如下：

rcu_read_lock(); //進(jìn)入臨界區(qū)

p=rcu_dereference(gp); //獲得對(duì)資源gp的引用

if(p!=NULL){

do_something_with(p); //通過(guò)引用p使用資源，完成預(yù)定的工作

}

rcu_read_unlock(); //退出臨界區(qū)

由于RCU資源可能正在被讀者使用，因而寫者不能直接修改資源。對(duì)寫者來(lái)說(shuō)，修改資源就是更新資源，就是發(fā)布資源的新版本，其過(guò)程如下：

(1)創(chuàng)建老資源的一個(gè)拷貝，并對(duì)拷貝進(jìn)行必要的修改，形成新版本。

(2)用資源的新版本替換老資源，使更新生效。

(3)維護(hù)老資源直到所有的讀者都不再引用它，而后釋放(銷毀)老資源。

資源替換操作必須是原子的，因而替換完成之前的讀者獲得的是對(duì)老資源的引用，替換完成之后的讀者獲得的是對(duì)新資源的引用，新老版本并存，直到?jīng)]有讀者再使用老資源。寫者使用資源的典型過(guò)程如下：

p=gp;

q=kmalloc(sizeof(*p),GFP_KERNEL); //創(chuàng)建一個(gè)新資源

spin_lock(&gp_lock); //互斥寫者

*q=*p; //復(fù)制老資源

do_something_with(q); //在新資源上完成預(yù)定的修改操作

rcu_assign_pointer(gp,q); //替換老資源，發(fā)布新資源

spin_unlock(&gp_lock);

synchronize_rcu(); //等待所有讀者釋放老資源

kfree(p); //銷毀老資源

從讀者和寫者的典型使用過(guò)程可以看出，RCU的讀者進(jìn)程有臨界區(qū)(稱為讀方臨界區(qū))，而寫者進(jìn)程沒(méi)有臨界區(qū)。如果讀者進(jìn)程位于讀方臨界區(qū)之外，則稱它處于靜止態(tài)(quiescentstate)。如果處理器正在運(yùn)行靜止態(tài)的進(jìn)程，則說(shuō)該處理器處于靜止態(tài)。顯然，處于靜止態(tài)的讀者不再持有對(duì)RCU資源的引用，因而不會(huì)再使用RCU資源。如果在寫者進(jìn)程發(fā)布資源之時(shí)有n個(gè)讀者進(jìn)程(在n個(gè)處理器上)正在讀方臨界區(qū)中，那么當(dāng)這n個(gè)進(jìn)程(或處理器)都至少經(jīng)歷過(guò)一次靜止態(tài)之后，即可肯定已沒(méi)有進(jìn)程再使用老的資源，可以放心地將其釋放掉了。每個(gè)處理器都至少經(jīng)歷一次靜止態(tài)的時(shí)間間隔稱為寬限期(GracePeriod，GP)。寫者進(jìn)程在完成對(duì)資源的發(fā)布操作之后，至少需等待一個(gè)寬限期，然后才可放心地將老資源釋放掉，如圖9.5所示。在圖9.5中，運(yùn)行在處理器2上的寫者進(jìn)程在t1時(shí)刻完成了資源發(fā)布。此時(shí)，處理器0和3都在讀方臨界區(qū)中，可能正在引用老資源，但處理器1處于靜止態(tài)，未使用老資源。因此，處理器2在完成發(fā)布操作后必須等待，直到時(shí)刻t2(所有處理器都至少經(jīng)歷過(guò)一次靜止態(tài))之后才可以放心地釋放老資源。在t1之后新進(jìn)入讀方臨界區(qū)的處理器(如處理器1、0)引用的肯定是新資源，老資源的釋放不會(huì)對(duì)它們?cè)斐捎绊?，不需要等待它們退出臨界區(qū)。

圖9.5靜止態(tài)與寬限期為了實(shí)現(xiàn)RCU機(jī)制，Linux定義了多個(gè)接口操作，大多數(shù)操作(可能是函數(shù)也可能是宏)的實(shí)現(xiàn)都比較簡(jiǎn)單，如下：

(1)函數(shù)rcu_read_lock()用于標(biāo)識(shí)讀方臨界區(qū)的入口，一般情況下就是一個(gè)搶占屏蔽操作preempt_disable()。

(2)函數(shù)rcu_read_unlock()用于標(biāo)識(shí)讀方臨界區(qū)的出口，一般情況下就是一個(gè)搶占使能操作preempt_enable()。

由rcu_read_lock()和rcu_read_unlock()界定的讀方臨界區(qū)可以被中斷，但不許被搶占。如果Linux內(nèi)核本身就不許搶占，上述兩個(gè)函數(shù)等價(jià)于空操作，沒(méi)有任何開(kāi)銷。

RCU未提供寫方臨界區(qū)的界定函數(shù)rcu_write_lock()和rcu_write_unlock()，因而不能定義寫方臨界區(qū)。在任何時(shí)候，RCU資源的寫者都不能阻止讀者讀資源。

(3)宏rcu_dereference(p)用于獲得一個(gè)被RCU保護(hù)的資源的指針，等價(jià)于參數(shù)p，在宏中所做的變換僅僅為了告訴編譯器不要對(duì)其進(jìn)行優(yōu)化。宏rcu_dereference()只能在讀方臨界區(qū)中使用，所獲得的指針也只能在讀方臨界區(qū)中使用且不能修改。

(4)宏rcu_assign_pointer(p,v)用于替換老資源或發(fā)布新資源，其結(jié)果是讓指針p指向資源v。宏rcu_assign_pointer()只能被寫者使用，在其定義中包含著一個(gè)優(yōu)化格柵barrier，用于保證此前對(duì)v的修改都已生效，此后對(duì)p的引用都是最新的。

(5)函數(shù)synchronize_rcu()僅能被寫者使用，用于等待此前位于讀方臨界區(qū)中的所有讀者都退出臨界區(qū)，或者說(shuō)等待當(dāng)前的寬限期終止。

(6)函數(shù)call_rcu()僅能被寫者使用，用于向RCU注冊(cè)一個(gè)回調(diào)函數(shù)。當(dāng)寬限期終止時(shí)，RCU會(huì)執(zhí)行此回調(diào)函數(shù)，完成寫者進(jìn)程預(yù)定的處理工作。與synchronize_rcu()不同，執(zhí)行call_rcu()的寫者進(jìn)程不需要等待，因而call_rcu()可以用在中斷處理程序中。9.4.2RCU管理結(jié)構(gòu)

顯然，RCU實(shí)現(xiàn)的關(guān)鍵是如何標(biāo)識(shí)寬限期的開(kāi)始和終止，或者說(shuō)如何追蹤各處理器的當(dāng)前狀態(tài)(靜止與否)。經(jīng)典RCU定義了一個(gè)全局位圖cpumask，其中的每一位對(duì)應(yīng)一個(gè)處理器。在寬限期開(kāi)始時(shí)，經(jīng)典RCU設(shè)置位圖cpumask，將各處理器的對(duì)應(yīng)位都置1。此后，各處理器分別監(jiān)視自己的狀態(tài)，并在進(jìn)入靜止態(tài)時(shí)將自己在cpumask中的位清0。一旦cpumask被清空，說(shuō)明所有處理器都至少經(jīng)歷了一次靜止態(tài)，一個(gè)寬限期也就隨之終止。當(dāng)然，位圖cpumask不能被多個(gè)處理器同時(shí)修改，因而需要一個(gè)自旋鎖的保護(hù)。然而不幸的是，隨著處理器數(shù)量的增加，保護(hù)位圖cpumask的自旋鎖會(huì)變成競(jìng)爭(zhēng)的焦點(diǎn)，限制了RCU的伸縮性。

為了提高RCU的伸縮性，新版本的Linux引入了層次RCU。層次RCU將處理器分成若干組，每組稱為一個(gè)節(jié)點(diǎn)。組中處理器的個(gè)數(shù)(FANOUT)可靜態(tài)配置，缺省值為64。層次RCU為每個(gè)節(jié)點(diǎn)定義了一個(gè)位圖和一個(gè)保護(hù)鎖。系統(tǒng)中所有的節(jié)點(diǎn)被組織成一個(gè)樹形結(jié)構(gòu)，每個(gè)下層節(jié)點(diǎn)在上層節(jié)點(diǎn)位圖中有一個(gè)對(duì)應(yīng)位。當(dāng)進(jìn)入靜止態(tài)時(shí)，處理器通常只需清除自己在所屬節(jié)點(diǎn)中的對(duì)應(yīng)位。只有將節(jié)點(diǎn)位圖清空的處理器才需要清除本節(jié)點(diǎn)在上層節(jié)點(diǎn)中的對(duì)應(yīng)位。當(dāng)根節(jié)點(diǎn)的位圖被清空時(shí)，說(shuō)明所有的處理器都至少經(jīng)歷了一個(gè)靜止態(tài)，寬限期隨之終止，如圖9.6所示。

圖9.6層次RCU管理結(jié)構(gòu)在圖9.6中，1024個(gè)處理器被分成16組，每組64個(gè)。CPU0～CPU63共用node1中的位圖qsmask和保護(hù)鎖，CPU64～CPU127共用node2中的位圖qsmask和保護(hù)鎖等等。節(jié)點(diǎn)node1～node16共用根節(jié)點(diǎn)node0中的位圖qsmask和保護(hù)鎖。當(dāng)進(jìn)入靜止態(tài)時(shí)，CPU0～CPU63僅需要清除node1中的位圖qsmask，CPU64～CPU127僅需要清除node2中的位圖qsmask，依此類推。只有將nodei(i

=

1～16)中的位圖清空的處理器才需要清除節(jié)點(diǎn)i在node0中的對(duì)應(yīng)位。對(duì)nodei(i

=

1～16)來(lái)說(shuō)，同時(shí)競(jìng)爭(zhēng)其中保護(hù)鎖的處理器數(shù)不會(huì)超過(guò)64個(gè)。對(duì)node0來(lái)說(shuō)，同時(shí)競(jìng)爭(zhēng)其中保護(hù)鎖的處理器數(shù)不會(huì)超過(guò)16個(gè)。因而，層次RCU增加了保護(hù)鎖的數(shù)量，減少了競(jìng)爭(zhēng)同一個(gè)保護(hù)鎖的處理器的個(gè)數(shù)，降低了保護(hù)鎖的競(jìng)爭(zhēng)壓力，提高了RCU的伸縮性。

經(jīng)典RCU的另一個(gè)問(wèn)題是必須由各處理器自己清除位圖cpumask，因而不得不經(jīng)常喚醒睡眠中的處理器，會(huì)影響節(jié)能效果。為解決這一問(wèn)題，層次RCU在PERCPU數(shù)據(jù)區(qū)中為每個(gè)處理器定義了一個(gè)狀態(tài)計(jì)數(shù)器dynticks，其初值為1。當(dāng)處理器進(jìn)入空閑狀態(tài)時(shí)，它的dynticks被加1，變成偶數(shù)；當(dāng)處理器退出空閑狀態(tài)時(shí)，它的dynticks被再次加1，又變成奇數(shù)。當(dāng)空閑狀態(tài)(dynticks為偶數(shù))的處理器被中斷時(shí)，它的dynticks被加1，變成奇數(shù)；當(dāng)中斷處理完畢再次進(jìn)入空閑狀態(tài)時(shí)，處理器的dynticks又被加1，變成偶數(shù)。因而，dynticks為偶數(shù)標(biāo)志著處理器處于空閑狀態(tài)。由于空閑處理器不會(huì)引用RCU資源，所以它在位圖qsmask中的狀態(tài)位可以不用檢查，處理器也不用被喚醒。

系統(tǒng)在運(yùn)行過(guò)程中會(huì)多次啟動(dòng)寬限期，但寬限期不能重疊，一個(gè)寬限期終止之后才能啟動(dòng)另一個(gè)寬限期。在一個(gè)特定的時(shí)刻，系統(tǒng)可能在寬限期內(nèi)，也可能在寬限期外。在完成資源發(fā)布需要等待寬限期時(shí)，如果系統(tǒng)在寬限期外，寫者進(jìn)程可以立刻啟動(dòng)一個(gè)新寬限期，并在該寬限期終止時(shí)釋放老資源；如果系統(tǒng)正在寬限期內(nèi)，那么當(dāng)前寬限期的終止并不代表使用老資源的進(jìn)程已全部離開(kāi)讀方臨界區(qū)，寫者進(jìn)程需啟動(dòng)下一個(gè)寬限期，并等待下一個(gè)寬限期終止，如圖9.7所示。

圖9.7重疊的寬限期在圖9.7中，處理器2在t1時(shí)刻啟動(dòng)了寬限期1(GP1)，該寬限期到t3時(shí)刻終止。假如處理器1在t2時(shí)刻完成了對(duì)資源s的替換，由于t2在寬限期1內(nèi)，不能立刻啟動(dòng)新寬限期，所以處理器1必須等待寬限期1終止之后才能啟動(dòng)寬限期2(GP2，從t4到t6)。雖然在t5時(shí)刻已沒(méi)有處理器再引用資源s，但對(duì)它的釋放卻被延遲到了t6時(shí)刻以后，因此寬限期的設(shè)定其實(shí)不夠精確。在t3到t4期間，系統(tǒng)不在任何寬限期內(nèi)。由于系統(tǒng)中不斷有寬限期啟動(dòng)和終止，為了描述的方便，Linux給每個(gè)寬限期指定了一個(gè)標(biāo)識(shí)號(hào)，稱為寬限期號(hào)gpnum。在系統(tǒng)運(yùn)行過(guò)程中，寬限期號(hào)單調(diào)增長(zhǎng)。

寬限期可能很長(zhǎng)，等待寬限期終止的處理器顯然不應(yīng)空轉(zhuǎn)(忙等測(cè)試)。為提高系統(tǒng)性能，Linux提供了兩種等待寬限期終止的方式，一是同步等待，二是異步等待。

需要同步等待的進(jìn)程調(diào)用函數(shù)synchronize_rcu()，先將自己掛在某個(gè)等待隊(duì)列中，而后請(qǐng)求調(diào)度，放棄處理器。此后進(jìn)程將一直等待，直到寬限期終止后被喚醒。在等待期間，處理器會(huì)轉(zhuǎn)去運(yùn)行其它進(jìn)程。需要異步等待的進(jìn)程調(diào)用函數(shù)call_rcu()，向RCU注冊(cè)一個(gè)回調(diào)函數(shù)，而后繼續(xù)運(yùn)行。在寬限期終止后，系統(tǒng)會(huì)在適當(dāng)?shù)臅r(shí)機(jī)調(diào)用回調(diào)函數(shù)，完成預(yù)定的善后處理工作，如釋放老資源等。

顯然，在一個(gè)處理器上可能會(huì)注冊(cè)多個(gè)回調(diào)函數(shù)，且它們等待的寬限期可能不同，因而應(yīng)為每個(gè)處理器準(zhǔn)備多個(gè)回調(diào)函數(shù)隊(duì)列。Linux對(duì)回調(diào)函數(shù)隊(duì)列進(jìn)行了簡(jiǎn)化，僅為每個(gè)處理器定義了一個(gè)隊(duì)列(由結(jié)構(gòu)rcu_head構(gòu)成)，但將其分成了四段，如下：

(1)隊(duì)頭部分稱為nxtlist隊(duì)列，其中的回調(diào)函數(shù)所等待的寬限期已經(jīng)終止。

(2)第二部分稱為wait隊(duì)列，其中的回調(diào)函數(shù)正在等待當(dāng)前寬限期的終止。

(3)第三部分稱為ready隊(duì)列，其中的回調(diào)函數(shù)在當(dāng)前寬限期終止之前注冊(cè)，正在等待下一個(gè)寬限期的終止。

(4)隊(duì)尾部分稱為next隊(duì)列，其中的回調(diào)函數(shù)是新注冊(cè)的。回調(diào)函數(shù)隊(duì)列由一個(gè)隊(duì)頭指針nxtlist和四個(gè)隊(duì)尾指針(由指針數(shù)組nxttail[]描述)組成，前一個(gè)隊(duì)列的隊(duì)尾就是后一個(gè)隊(duì)列的隊(duì)頭，如圖9.8所示。新注冊(cè)的回調(diào)函數(shù)被插入隊(duì)尾，并被逐漸移向隊(duì)頭。nxtlist隊(duì)列中的回調(diào)函數(shù)可以立刻執(zhí)行，也可以延遲后批量執(zhí)行。在每個(gè)寬限期終止時(shí)，通過(guò)調(diào)整隊(duì)尾指針即可向隊(duì)頭遷移回調(diào)函數(shù)。

圖9.8回調(diào)函數(shù)隊(duì)列

Linux用結(jié)構(gòu)rcu_data管理各處理器的RCU信息，每個(gè)處理器一個(gè)，定義在PERCPU數(shù)據(jù)區(qū)中。結(jié)構(gòu)rcu_data中主要包含如下內(nèi)容：

(1)本處理器在層次RCU結(jié)構(gòu)中所屬的節(jié)點(diǎn)mynode。

(2)本處理器在所屬節(jié)點(diǎn)中的序號(hào)，也就是在節(jié)點(diǎn)位圖qsmask中的位置。

(3)本處理器當(dāng)前等待的寬限期(簡(jiǎn)稱GP)號(hào)gpnum。

(4)本處理器已處理過(guò)的寬限期號(hào)completed。

(5)本處理器進(jìn)入靜止態(tài)時(shí)的寬限期號(hào)passed_quiesc_completed。

(6)本處理器是否已經(jīng)歷過(guò)寬限期passed_quiesc，0表示未經(jīng)歷。

(7)本處理器的空閑狀態(tài)計(jì)數(shù)器dynticks，偶數(shù)表示處理器在空閑狀態(tài)。

(8)在本處理器上注冊(cè)的回調(diào)函數(shù)隊(duì)列nxtlist和nxttail[]等。

系統(tǒng)中的每個(gè)處理器都屬于一個(gè)節(jié)點(diǎn)，所有的節(jié)點(diǎn)組成一個(gè)樹形結(jié)構(gòu)。直接管理處理器的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)，管理節(jié)點(diǎn)的節(jié)點(diǎn)稱為中間節(jié)點(diǎn)，最上層的中間節(jié)點(diǎn)稱為根節(jié)點(diǎn)。特別地，當(dāng)系統(tǒng)中的處理器數(shù)少于FANOUT時(shí)，只需要一個(gè)根節(jié)點(diǎn)即可。節(jié)點(diǎn)由結(jié)構(gòu)rcu_node描述，其中的主要內(nèi)容有如下幾個(gè)：

(1)節(jié)點(diǎn)在層次RCU結(jié)構(gòu)中所處層次level。根節(jié)點(diǎn)所處層次是0。

(2)父節(jié)點(diǎn)parent。根節(jié)點(diǎn)的parent是NULL。

(3)本節(jié)點(diǎn)在父節(jié)點(diǎn)中的序號(hào)，也就是在父節(jié)點(diǎn)位圖qsmask中的位置。

(4)本節(jié)點(diǎn)所管理的處理器范圍，從邏輯編號(hào)grplo到grphi。中間節(jié)點(diǎn)所管理的處理器是它的所有低層節(jié)點(diǎn)所管理處理器的總和。

(5)靜止態(tài)位圖qsmask。葉節(jié)點(diǎn)位圖qsmask中的一位描述一個(gè)處理器的狀態(tài)，0表示處理器已經(jīng)歷過(guò)靜止態(tài)。中間節(jié)點(diǎn)位圖qsmask中的一位描述一個(gè)低層節(jié)點(diǎn)的狀態(tài)，0表示低層節(jié)點(diǎn)管理的所有處理器都已經(jīng)歷過(guò)靜止態(tài)。

(6)靜止態(tài)位圖的初值qsmaskinit。在啟動(dòng)寬限期時(shí)，用qsmaskinit初始化qsmask。

(7)自旋鎖lock，用于保護(hù)位圖qsmask。

(8)本節(jié)點(diǎn)正在等待的寬限期號(hào)gpnum，初值是0。

(9)本節(jié)點(diǎn)最近已處理過(guò)的寬限期號(hào)completed，初值是0。

Linux用一個(gè)全局結(jié)構(gòu)rcu_state管理系統(tǒng)中所有的節(jié)點(diǎn)，稱為rcu_sched_state。結(jié)構(gòu)rcu_state中主要包含如下內(nèi)容：

(1)一個(gè)rcu_node結(jié)構(gòu)數(shù)組，其中包括所有的rcu_node結(jié)構(gòu)。

(2)一個(gè)整型數(shù)組levelcnt，記錄各層的節(jié)點(diǎn)數(shù)。

(3)一個(gè)整型數(shù)組levelspread，記錄各層中的節(jié)點(diǎn)扇出度數(shù)。

(4)一個(gè)指針數(shù)組rda，指向各處理器的rcu_data結(jié)構(gòu)。

(5)一個(gè)無(wú)符號(hào)長(zhǎng)整數(shù)gpnum，記錄當(dāng)前的寬限期號(hào)，初值是-300。

(6)一個(gè)無(wú)符號(hào)長(zhǎng)整數(shù)completed，記錄最近已終止的寬限期號(hào)，初值是-300。

(7)一個(gè)無(wú)符號(hào)長(zhǎng)整數(shù)jiffies_force_qs，記錄當(dāng)前寬限期的預(yù)設(shè)終止時(shí)刻(比啟動(dòng)時(shí)刻的jiffies大3個(gè)滴答)。

在系統(tǒng)初始化時(shí)，已設(shè)置了上述各結(jié)構(gòu)的初值。9.4.3寬限期啟動(dòng)

寬限期由寫者進(jìn)程在當(dāng)前處理器上啟動(dòng)。啟動(dòng)寬限期的條件是系統(tǒng)當(dāng)前不在寬限期內(nèi)(系統(tǒng)的completed號(hào)等于gpnum號(hào))。寬限期啟動(dòng)的過(guò)程如下：

(1)將系統(tǒng)(全局結(jié)構(gòu)rcu_state)中的gpnum號(hào)加1。

(2)將所有節(jié)點(diǎn)的qsmask都設(shè)為自己的qsmaskinit、gpnum設(shè)為系統(tǒng)的gpnum、completed設(shè)為系統(tǒng)的completed(比gpnum小1)。

(3)如果當(dāng)前處理器的completed號(hào)小于節(jié)點(diǎn)的completed號(hào)，說(shuō)明當(dāng)前處理器未注意到又過(guò)了一個(gè)寬限期，因而需將當(dāng)前處理器的completed號(hào)改為節(jié)點(diǎn)的completed號(hào)，并順序前移當(dāng)前處理器的回調(diào)函數(shù)隊(duì)列(wait到nxtlist、ready到wait、next到ready)。

(4)將當(dāng)前處理器的ready和next隊(duì)列中的回調(diào)函數(shù)都移到wait隊(duì)列中，讓它們?cè)谛聦捪奁诮K止時(shí)執(zhí)行。將當(dāng)前處理器的gpnum設(shè)為節(jié)點(diǎn)的gpnum號(hào)(也就是系統(tǒng)當(dāng)前的寬限期號(hào))，并將passed_quiesc清0。

RCU的回調(diào)注冊(cè)函數(shù)call_rcu()由寫者進(jìn)程在當(dāng)前處理器上調(diào)用，其處理過(guò)程如下：

(1)如果當(dāng)前處理器的completed號(hào)小于節(jié)點(diǎn)的completed號(hào)，說(shuō)明當(dāng)前處理器未注意到又過(guò)了一個(gè)寬限期，因而需將當(dāng)前處理器的completed號(hào)設(shè)為節(jié)點(diǎn)的completed號(hào)，并順序前移當(dāng)前處理器的回調(diào)函數(shù)隊(duì)列(wait到nxtlist、ready到wait、next到ready)。

(2)如果當(dāng)前處理器的gpnum號(hào)小于系統(tǒng)的gpnum號(hào)，說(shuō)明當(dāng)前處理器未注意到其它處理器又啟動(dòng)了寬限期，則將當(dāng)前處理器的gpnum號(hào)設(shè)為節(jié)點(diǎn)的gpnum號(hào)，并將它的passed_quiesc清0。

(3)初始化一個(gè)rcu_head結(jié)構(gòu)(next為空、func指向新注冊(cè)的回調(diào)函數(shù))，將其插入到當(dāng)前處理器的next隊(duì)列中。

(4)如果系統(tǒng)目前不在寬限期內(nèi)(系統(tǒng)的completed等于gpnum)，則啟動(dòng)一個(gè)新寬限期。如果系統(tǒng)目前已在寬限期內(nèi)，則不用(也不能)啟動(dòng)新的寬限期。

RCU的同步等待函數(shù)synchronize_rcu()由寫者進(jìn)程在當(dāng)前處理器上調(diào)用，其處理過(guò)程如下：

(1)初始化一個(gè)類型為rcu_synchronize(定義如下)的局部變量。

structrcu_synchronize{

structrcu_head head;

structcompletion completion; //其中包含一個(gè)等待隊(duì)列

};

(2)調(diào)用函數(shù)call_rcu()注冊(cè)回調(diào)函數(shù)wakeme_after_rcu()，并試圖啟動(dòng)新寬限期。

(3)將寫者進(jìn)程掛在completion的等待隊(duì)列中，而后請(qǐng)求調(diào)度，放棄處理器，進(jìn)入等待狀態(tài)，直到被喚醒：

①如系統(tǒng)目前不在寬限期中，call_rcu()會(huì)啟動(dòng)一個(gè)新寬限期。當(dāng)新寬限期終止時(shí)，RCU會(huì)執(zhí)行函數(shù)wakeme_after_rcu()，將寫者進(jìn)程喚醒。②如果系統(tǒng)目前在寬限期中，call_rcu()不會(huì)啟動(dòng)新寬限期。RCU會(huì)在下一個(gè)寬限期終止時(shí)執(zhí)行函數(shù)wakeme_after_rcu()，將寫者進(jìn)程喚醒。9.4.4寬限期終止

寬限期終止的條件是所有處理器都至少經(jīng)歷過(guò)一次靜止態(tài)。由于在臨界區(qū)中的讀者進(jìn)程不允許搶占，因而只要某處理器上發(fā)生了進(jìn)程調(diào)度，即可肯定該處理器已退出了讀方臨界區(qū)，或者說(shuō)經(jīng)歷過(guò)了靜止態(tài)。

然而，若讓調(diào)度函數(shù)schedule()直接更新節(jié)點(diǎn)中的靜止態(tài)位圖qsmask，必然會(huì)延長(zhǎng)調(diào)度函數(shù)的執(zhí)行時(shí)間(需先獲得自旋鎖)，降低系統(tǒng)性能。所以，Linux僅讓調(diào)度函數(shù)在當(dāng)前處理器的rcu_data結(jié)構(gòu)上設(shè)置一個(gè)標(biāo)志passed_quiesc，表示該處理器已經(jīng)歷過(guò)靜止態(tài)，將位圖qsmask的更新工作延遲到周期性時(shí)鐘中斷處理中。如果處理器處于空閑狀態(tài)，那么它肯定在靜止態(tài)。雖然空閑處理器的周期性時(shí)鐘中斷可能被暫停，但它在位圖qsmask中的標(biāo)志位不會(huì)被檢查，因而不會(huì)影響寬限期的終止。如果空閑處理器被中斷，它會(huì)離開(kāi)空閑狀態(tài)。在中斷處理完后，如果有進(jìn)程就緒，處理器會(huì)進(jìn)行調(diào)度(經(jīng)歷了靜止態(tài))，否則會(huì)再次進(jìn)入空閑態(tài)，也經(jīng)歷了靜止態(tài)。

如果處理器處于活動(dòng)狀態(tài)，它會(huì)收到周期性的時(shí)鐘中斷。在周期性時(shí)鐘中斷處理中，RCU完成如下的工作：

(1)如果中斷之前處理器正在執(zhí)行用戶態(tài)程序，則可以肯定處理器正處于靜止態(tài)，設(shè)置它的passed_quiesc標(biāo)志。

(2)如果處理器正在運(yùn)行空閑進(jìn)程且中斷前不在中斷處理程序中，則可以肯定處理器正處于靜止態(tài)，設(shè)置它的passed_quiesc標(biāo)志。

(3)如果當(dāng)前寬限期已持續(xù)了太長(zhǎng)時(shí)間，說(shuō)明某些處理器可能出現(xiàn)了停頓現(xiàn)象(在活動(dòng)狀態(tài)但長(zhǎng)期未調(diào)度，如在關(guān)中斷或搶占屏蔽狀態(tài)下長(zhǎng)期循環(huán))，則應(yīng)報(bào)告停頓情況，并清除各空閑處理器在節(jié)點(diǎn)中的狀態(tài)位，試圖強(qiáng)行終止當(dāng)前寬限期。

(4)如果下列條件之一滿足，則激活當(dāng)前處理器的軟中斷RCU_SOFTIRQ：

①當(dāng)前處理器的passed_quiesc標(biāo)志是1。

②當(dāng)前處理器的nxtlist隊(duì)列不空(有就緒的RCU回調(diào)函數(shù))。

③當(dāng)前處理器的ready隊(duì)列不空且系統(tǒng)在寬限期外(需啟動(dòng)新的寬限期)。

④當(dāng)前處理器還未對(duì)上一個(gè)寬限期的終止進(jìn)行處理。

⑤當(dāng)前處理器未注意到當(dāng)前寬限期的啟動(dòng)。

⑥系統(tǒng)在當(dāng)前寬限期中滯留了太長(zhǎng)時(shí)間。顯然，實(shí)質(zhì)性的RCU處理工作被推遲到了軟中斷RCU_SOFTIRQ的處理程序中。

(1)如果當(dāng)前寬限期已經(jīng)持續(xù)了太長(zhǎng)時(shí)間(3個(gè)滴答以上)，則試圖強(qiáng)行終止它。方法是按如下方式處理位圖qsmask中非空的每一個(gè)葉節(jié)點(diǎn)：

①如果節(jié)點(diǎn)中的某處理器處于空閑狀態(tài)(dynticks為偶數(shù))，則清除它在qsmask中的狀態(tài)位。

②如果某節(jié)點(diǎn)的qsmask被清空，則清除它在上層節(jié)點(diǎn)中的狀態(tài)位。如果根節(jié)點(diǎn)的qsmask被清空，說(shuō)明當(dāng)前寬限期已經(jīng)終止，則：●將系統(tǒng)的completed和所有節(jié)點(diǎn)的completed都設(shè)為系統(tǒng)的gpnum。

●如果當(dāng)前處理器的ready隊(duì)列不空，則啟動(dòng)一個(gè)新的寬限期。

(2)如果當(dāng)前處理器的completed號(hào)小于節(jié)點(diǎn)的completed號(hào)，則將其completed號(hào)設(shè)為節(jié)點(diǎn)的completed號(hào)，并順序前移它的回調(diào)函數(shù)隊(duì)列。

(3)如果當(dāng)前處理器的gpnum號(hào)小于系統(tǒng)的gpnum號(hào)，則將當(dāng)前處理器的gpnum號(hào)設(shè)為節(jié)點(diǎn)的gpnum號(hào)，并將它的passed_quiesc清0。

(4)如果當(dāng)前處理器的passed_quiesc是1，說(shuō)明該處理器已經(jīng)歷過(guò)靜止態(tài)。如果該處理器在所屬節(jié)點(diǎn)中的狀態(tài)位還未清除，則：

①將當(dāng)前處理器的next隊(duì)列移到ready隊(duì)列中。

②清除當(dāng)前處理器在節(jié)點(diǎn)qsmask中的狀態(tài)位。

③如果節(jié)點(diǎn)的qsmask被清空，則清除它在上層節(jié)點(diǎn)中的狀態(tài)位。如果根節(jié)點(diǎn)的qsmask被清空，說(shuō)明當(dāng)前寬限期已經(jīng)終止，則：

●將系統(tǒng)的completed和所有節(jié)點(diǎn)的completed都設(shè)為系統(tǒng)的gpnum?！袢绻?dāng)前處理器的ready隊(duì)列不空，則啟動(dòng)一個(gè)新的寬限期；否則，將wait隊(duì)列移到nxtlist中。

(5)如果當(dāng)前處理器上的nxtlist隊(duì)列不空，則順序執(zhí)行其上的各個(gè)回調(diào)函數(shù)，并調(diào)整各回調(diào)函數(shù)隊(duì)列。

由此可見(jiàn)，Linux實(shí)現(xiàn)的寬限期是很不精確的，但它能夠保證RCU的語(yǔ)義。不精確的寬限期可能會(huì)延遲回調(diào)函數(shù)的執(zhí)行，也可能會(huì)延長(zhǎng)寫者進(jìn)程的等待時(shí)間，但不會(huì)造成RCU資源的不一致性。與自旋鎖或序號(hào)鎖不同，基于寬限期的RCU機(jī)制僅與處理器數(shù)有關(guān)而與資源數(shù)量無(wú)關(guān)，可用于保護(hù)更多的資源，具有更好的伸縮性。

RCU機(jī)制的大部分工作都由寫者進(jìn)程負(fù)責(zé)，讀者進(jìn)程的開(kāi)銷很小，因而通常僅用RCU保護(hù)讀多寫少的資源(對(duì)RCU資源的寫操作不應(yīng)超過(guò)10%)。另外，RCU的讀方臨界區(qū)可以嵌套，并可包含任意形式的代碼，只要不在臨界區(qū)中阻塞或睡眠即可。由于讀者不需要鎖，因而RCU機(jī)制的死鎖幾率極小。

雖然RCU常被用做互斥機(jī)制，但它實(shí)際上具有同步能力。使用synchronize_rcu()的進(jìn)程會(huì)掛起等待，直到所有的處理器都至少經(jīng)歷過(guò)一次靜止態(tài)。Linux還定義了一些擴(kuò)展接口函數(shù)，用于實(shí)現(xiàn)受RCU保護(hù)的鏈表操作、Hash表操作、數(shù)組變長(zhǎng)操作等。

鎖和RCU機(jī)制的互斥能力是受限的。由自旋鎖保護(hù)的資源不能長(zhǎng)期占有，由序號(hào)鎖和RCU保護(hù)的資源不能經(jīng)常修改。另外，鎖不具有同步能力，RCU無(wú)法實(shí)現(xiàn)特定進(jìn)程間的同步。因而在鎖和RCU之外，還需要提供其它的互斥與同步手段。9.5信號(hào)量可以兼顧互斥與同步的機(jī)制是由Dijkstra提出的信號(hào)量(Semaphore)。信號(hào)量上的P操作將信號(hào)量的值減1，若結(jié)果非負(fù)，進(jìn)程將獲得信號(hào)量，否則進(jìn)程將被掛起等待，直到被其它進(jìn)程的V操作喚醒。V操作將信號(hào)量的值加1，若結(jié)果為負(fù)，需要喚醒一個(gè)或全部的等待進(jìn)程。當(dāng)然，對(duì)信號(hào)量的加減操作必須是原子的。

信號(hào)量是一種十分靈活的機(jī)制，可以用做互斥，也可以用做同步。當(dāng)初值為1時(shí)，可以用信號(hào)量實(shí)現(xiàn)互斥，它所保護(hù)的資源僅有一個(gè)，不能被一個(gè)以上的進(jìn)程同時(shí)使用。當(dāng)初值為0時(shí)，可以用信號(hào)量實(shí)現(xiàn)同步，在其上執(zhí)行P操作的進(jìn)程會(huì)被阻塞，直到被其它進(jìn)程的V操作喚醒。當(dāng)初值大于1時(shí)，可以用信號(hào)量保護(hù)復(fù)合型資源(資源數(shù)由初值規(guī)定)，這類資源可以被多個(gè)進(jìn)程同時(shí)使用，但每個(gè)進(jìn)程只能使用其中的一個(gè)。

與自旋鎖不同，信號(hào)量的P、V操作可以用在同一個(gè)進(jìn)程中，也可以分開(kāi)用在不同的進(jìn)程中。如果同一個(gè)信號(hào)量的P、V操作位于不同的進(jìn)程中，那么被P操作阻塞的進(jìn)程就需要由其它進(jìn)程的V操作喚醒，因而信號(hào)量天生具有同步能力。9.5.1經(jīng)典信號(hào)量

早期的Linux遵循傳統(tǒng)的信號(hào)量語(yǔ)義，先對(duì)信號(hào)量進(jìn)行加、減操作，再判斷其值的正負(fù)。在新的版本中，Linux先判斷信號(hào)量的當(dāng)前值，再進(jìn)行操作，信號(hào)量的值保持非負(fù)。當(dāng)信號(hào)量的值大于0時(shí)，P操作將其減1；當(dāng)信號(hào)量的值等于0時(shí)，P操作將進(jìn)程掛起等待。當(dāng)?shù)却?duì)列為空時(shí)，V操作將信號(hào)量的值加1；當(dāng)?shù)却?duì)列不空時(shí)，V操作僅喚醒在隊(duì)頭等待的進(jìn)程。新的實(shí)現(xiàn)能減少進(jìn)程間的競(jìng)爭(zhēng)。Linux用函數(shù)down()實(shí)現(xiàn)P操作，用函數(shù)up()實(shí)現(xiàn)V操作，所用經(jīng)典信號(hào)量的管理結(jié)構(gòu)由semaphore描述，如下：

structsemaphore{

spinlock_t lock; //自旋鎖

unsignedint count; //信號(hào)量的當(dāng)前值

structlist_head wait_list; //進(jìn)程等待隊(duì)列

};

無(wú)法獲得信號(hào)量的進(jìn)程被包裝在結(jié)構(gòu)semaphore_waiter中，并被掛在隊(duì)列wait_list上等待，如圖9.9所示。

structsemaphore_waiter{

structlist_head list; //隊(duì)列節(jié)點(diǎn)

structtask_struct *task; //等待者進(jìn)程的PCB結(jié)構(gòu)

int up; //喚醒標(biāo)志

};

圖9.9信號(hào)量管理結(jié)構(gòu)在信號(hào)量上等待的進(jìn)程可能處于不可中斷等待狀態(tài)(TASK_UNINTERRUPTIBLE)、可中斷等待狀態(tài)(TASK_INTERRUPTIBLE)或可殺死狀態(tài)(TASK_UNINTERRUPTIBLE|TASK_

WAKEKILL)，申請(qǐng)者進(jìn)程還可以預(yù)定一個(gè)最長(zhǎng)等待時(shí)間。

在信號(hào)量上睡眠的進(jìn)程可能被up()或信號(hào)喚醒，也可能因?yàn)樗叱瑫r(shí)而自醒。當(dāng)進(jìn)程被up()喚醒時(shí)，其semaphore_waiter結(jié)構(gòu)中的up為1，其它情況下的up為0。被up()喚醒的進(jìn)程將獲得信號(hào)量，被信號(hào)喚醒或自醒的進(jìn)程可能未獲得信號(hào)量。為了兼顧信號(hào)量的不同使用場(chǎng)合，Linux實(shí)現(xiàn)了五種不同的down()函數(shù)。當(dāng)信號(hào)量的當(dāng)前值大于0時(shí)，這些函數(shù)的處理方法都相同，即將信號(hào)量的值減1。當(dāng)信號(hào)量的當(dāng)前值為0時(shí)，這五種函數(shù)的處理方法各有不同，如表9.2所示。

表9.2信號(hào)量為0時(shí)的五種down函數(shù)

Linux僅提供了一個(gè)up()函數(shù)，用于匹配不同形式的down()函數(shù)。如果信號(hào)量的wait_list隊(duì)列為空，函數(shù)up()僅將信號(hào)量的當(dāng)前值加1。如果信號(hào)量的wait_list隊(duì)列不空，說(shuō)明有進(jìn)程正在等待該信號(hào)量，函數(shù)up()會(huì)將隊(duì)頭的semaphore_waiter結(jié)構(gòu)從隊(duì)列中摘下，將其中的up置1，而后將它所指的進(jìn)程喚醒。

當(dāng)進(jìn)程從down()函數(shù)中醒來(lái)后，如發(fā)現(xiàn)自己的up標(biāo)志為1，即可肯定自己是被up操作喚醒的，且已經(jīng)獲得了信號(hào)量。

對(duì)信號(hào)量及其等待隊(duì)列的操作必須在自旋鎖lock的保護(hù)下進(jìn)行，且需要關(guān)閉中斷。當(dāng)然，在進(jìn)入等待狀態(tài)之前進(jìn)程必須釋放自旋鎖，在被喚醒之后還需再次獲得自旋鎖。9.5.2互斥信號(hào)量

在內(nèi)核中，雖然信號(hào)量可用于同步，但它最常見(jiàn)的用途仍然是互斥。用做互斥的信號(hào)量初值為1，需配對(duì)使用，不允許嵌套，且必須由持有者釋放。測(cè)試表明，互斥用的信號(hào)量通常都處于空閑狀態(tài)，即使忙碌，在一個(gè)信號(hào)量上等待的進(jìn)程數(shù)也不會(huì)太多。針對(duì)這一特殊情況，IngoMolnar給出了一種優(yōu)化設(shè)計(jì)，稱為互斥信號(hào)量(mutex)。

互斥信號(hào)量由結(jié)構(gòu)mutex描述，其定義與semaphore類似，如下：

structmutex{

atomic_t count; //1表示閑，<1表示忙

spinlock_t wait_lock; //保護(hù)用的自旋鎖

structlist_head wait_list; //進(jìn)程等待隊(duì)列

structthread_info *owner; //信號(hào)量的持有者

};

互斥信號(hào)量上的P操作由函數(shù)mutex_lock()實(shí)現(xiàn)，V操作由函數(shù)mutex_unlock()實(shí)現(xiàn)。

函數(shù)mutex_lock()的實(shí)現(xiàn)思路與down()相似，它首先將互斥信號(hào)量的當(dāng)前值(count)減1，而后判斷結(jié)果的正負(fù)。如果減1后的結(jié)果為0，則申請(qǐng)者進(jìn)程獲得互斥信號(hào)量；如果減1后的結(jié)果為負(fù)，則申請(qǐng)者進(jìn)程需要等待。與down()不同的是，在將申請(qǐng)者進(jìn)程插入等待隊(duì)列之前，函數(shù)mutex_lock()還對(duì)持有者進(jìn)程進(jìn)行了一個(gè)測(cè)試。如果互斥信號(hào)量的持有者正在某個(gè)處理器上運(yùn)行，那么一般情況下該信號(hào)量會(huì)在近期內(nèi)被釋放，因而申請(qǐng)者進(jìn)程可以進(jìn)行忙等測(cè)試，直到互斥信號(hào)量被持有者釋放且被當(dāng)前進(jìn)程獲得(等價(jià)于自旋鎖)、或持有者進(jìn)程被調(diào)離處理器、或當(dāng)前進(jìn)程需要調(diào)度。只有在忙等測(cè)試失敗(持有者未運(yùn)行或申請(qǐng)者需調(diào)度)時(shí)，函數(shù)mutex_lock()才將申請(qǐng)者進(jìn)程插入等待隊(duì)列wait_list的隊(duì)尾等待(等價(jià)于經(jīng)典信號(hào)量)。

函數(shù)mutex_unlock()的實(shí)現(xiàn)思路與up()相似，它首先將互斥信號(hào)量的當(dāng)前值(count)加1，而后判斷結(jié)果的正負(fù)。如果加1后的結(jié)果小于1，說(shuō)明有等待該互斥信號(hào)量的進(jìn)程，則喚醒隊(duì)列中的第一個(gè)等待者，否則無(wú)需進(jìn)行喚醒操作。

如果互斥信號(hào)量處于空閑狀態(tài)，那么函數(shù)mutex_lock()和mutex_unlock()都僅需要三條指令，其實(shí)現(xiàn)代碼中甚至不需要自旋鎖的保護(hù)，開(kāi)銷極小。如果互斥信號(hào)量不是太忙，申請(qǐng)者通過(guò)簡(jiǎn)單的忙等測(cè)試即可獲得信號(hào)量，實(shí)現(xiàn)的開(kāi)銷也不大。只有在很特殊的情況下，互斥信號(hào)量的申請(qǐng)者才會(huì)被迫進(jìn)入等待狀態(tài)。測(cè)試表明，互斥信號(hào)量比經(jīng)典信號(hào)量的速度更快、伸縮性更好。事實(shí)上，在目前的Linux內(nèi)核中，互斥信號(hào)量的應(yīng)用范圍已遠(yuǎn)遠(yuǎn)超過(guò)了經(jīng)典信號(hào)量。