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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

=

x

+

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

+

3而不是x

+

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

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

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

typedefstruct{

intcounter;

}atomic_t;

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

staticinlinevoidatomic_add(inti,atomic_t*v){

asmvolatile(LOCK_PREFIX"addl%1,%0"

:"+m"(v->counter)

:"ir"(i));

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

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

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

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

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

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

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

正在運行的進程可以主動請求睡眠(sleep_on())，從而進入等待狀態(tài)。進程可以在不可中斷等待狀態(tài)下睡眠，也可以在可中斷等待狀態(tài)下睡眠。進程可以預定一個睡眠時間，也可以不預定睡眠時間(長眠)。Linux將睡眠進程掛在自己指定的等待隊列中。等待隊列由類型wait_queue_head_t定義，如下：

struct_

_wait_queue_head{

spinlock_t lock; //保護鎖

structlist_head task_list; //隊列

};

typedefstruct_

_wait_queue_head wait_queue_head_t;

睡眠者進程先將自己包裝在一個_

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

struct_

_wait_queue{

unsignedint flags; //標志，總是1

void *private; //指向睡眠者進程的task_struct結(jié)構

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

structlist_head task_list; //隊列節(jié)點

};

typedefstruct_

_wait_queue wait_queue_t;

如果進程預定了睡眠時間，Linux會為其啟動一個定時器。當定時器到期時，Linux會將睡眠的進程喚醒(將其狀態(tài)改為TASK_RUNNING并加入就緒隊列)。如果進程在到期之前被喚醒，睡眠操作會返回剩余的睡眠時間。

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

_

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

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

structcompletion{

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

wait_queue_head_t wait; //等待隊列

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

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

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

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

<加鎖(spin_lock)>

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

<解鎖(spin_unlock)>

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

自旋鎖一般用在多處理器環(huán)境中。申請鎖的進程和持有鎖的進程運行在不同的處理器上，申請鎖的進程通過簡單的忙等測試等待持有鎖的進程釋放自旋鎖。在單處理器環(huán)境中，自旋鎖退化成了空語句，或簡單的開、關中斷操作。

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

Linux用類型spinlock_t(或結(jié)構spinlock)描述自旋鎖。在Intel處理器上，結(jié)構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;由此可見，自旋鎖實際是一個經(jīng)過多層包裝的無符號整型變量，其值的意義取決于加鎖與解鎖算法的設計。在Linux的演變過程中，自旋鎖的實現(xiàn)算法也在不斷演變。

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

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

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

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

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

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(); //搶占使能

}

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

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

voidspin_lock_irq(spinlock_t*lock){

local_irq_disable(); //關中斷

spin_lock(lock);

}

voidspin_unlock_irq(spinlock_t*lock){

spin_unlock(lock);

local_irq_enable(); //開中斷

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

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

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

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

typedefstruct{

unsignedint rw;

}arch_rwlock_t;

typedefstruct{

arch_rwlock_t raw_lock;

}rwlock_t;

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

如果鎖是空閑的(既無讀者也無寫者)，讀加鎖與寫加鎖操作都會成功。如果有寫者，讀加鎖與寫加鎖都會失敗。如果有讀者，只要讀者個數(shù)不超過0x01000000，讀加鎖操作都會成功，但寫加鎖操作肯定失敗。讀加鎖操作成功的條件是沒有寫者，寫加鎖操作成功的條件是既無讀者也無寫者。新讀寫自旋鎖的實現(xiàn)流程如圖9.4所示。圖9.4新讀寫自旋鎖實現(xiàn)算法當然，真正的讀寫自旋鎖操作還要照顧到搶占，實現(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未解決讀寫自旋鎖的無序競爭問題。

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

讀寫自旋鎖更偏愛讀者，在讀多寫少的情況下，寫者的等待時間會更長。為了照顧寫者，Linux又引入了序號鎖。序號鎖是一種讀寫鎖，不過它更偏愛寫者。

序號鎖的寫者不需要等待讀者，只要沒有其它寫者，即可開始修改資源。為了與其它寫者互斥，寫者在使用資源之前需要先申請序號寫鎖。寫者使用資源的過程如下：

write_seqlock(&seq_lock); //申請序號寫鎖

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

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

序號鎖的讀者不需要預先申請鎖，可直接對資源進行讀操作，但讀出的數(shù)據(jù)可能不準確(如正在被寫者修改)，因而需要對讀出的結(jié)果進行測試，并在必要時重讀。讀者使用資源的過程如下：

unsignedlongseq;

do{

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

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

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

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

typedefstruct{

unsigned sequence; //序號

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

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

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

voidwrite_seqlock(seqlock_t*sl){

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

++sl->sequence; //序號加1

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

}

voidwrite_sequnlock(seqlock_t*sl){

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

sl->sequence++; //序號加1

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

}

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

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

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

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

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

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

RCU的基本思想是對讀者稍加限制，而對寫者嚴格要求，因而讀者的開銷極小，而寫者的開銷稍大。所以，RCU機制更適合保護讀多寫少的資源。

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

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

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

if(p!=NULL){

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

}

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

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

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

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

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

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

p=gp;

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

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

*q=*p; //復制老資源

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

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

spin_unlock(&gp_lock);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

=

1～16)中的位圖清空的處理器才需要清除節(jié)點i在node0中的對應位。對nodei(i

=

1～16)來說，同時競爭其中保護鎖的處理器數(shù)不會超過64個。對node0來說，同時競爭其中保護鎖的處理器數(shù)不會超過16個。因而，層次RCU增加了保護鎖的數(shù)量，減少了競爭同一個保護鎖的處理器的個數(shù)，降低了保護鎖的競爭壓力，提高了RCU的伸縮性。

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

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

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

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

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

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

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

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

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

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

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

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

(1)本處理器在層次RCU結(jié)構中所屬的節(jié)點mynode。

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

(3)本處理器當前等待的寬限期(簡稱GP)號gpnum。

(4)本處理器已處理過的寬限期號completed。

(5)本處理器進入靜止態(tài)時的寬限期號passed_quiesc_completed。

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

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

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

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

(1)節(jié)點在層次RCU結(jié)構中所處層次level。根節(jié)點所處層次是0。

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

(3)本節(jié)點在父節(jié)點中的序號，也就是在父節(jié)點位圖qsmask中的位置。

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

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

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

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

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

(9)本節(jié)點最近已處理過的寬限期號completed，初值是0。

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

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

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

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

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

(5)一個無符號長整數(shù)gpnum，記錄當前的寬限期號，初值是-300。

(6)一個無符號長整數(shù)completed，記錄最近已終止的寬限期號，初值是-300。

(7)一個無符號長整數(shù)jiffies_force_qs，記錄當前寬限期的預設終止時刻(比啟動時刻的jiffies大3個滴答)。

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

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

(1)將系統(tǒng)(全局結(jié)構rcu_state)中的gpnum號加1。

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

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

(4)將當前處理器的ready和next隊列中的回調(diào)函數(shù)都移到wait隊列中，讓它們在新寬限期終止時執(zhí)行。將當前處理器的gpnum設為節(jié)點的gpnum號(也就是系統(tǒng)當前的寬限期號)，并將passed_quiesc清0。

RCU的回調(diào)注冊函數(shù)call_rcu()由寫者進程在當前處理器上調(diào)用，其處理過程如下：

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

(2)如果當前處理器的gpnum號小于系統(tǒng)的gpnum號，說明當前處理器未注意到其它處理器又啟動了寬限期，則將當前處理器的gpnum號設為節(jié)點的gpnum號，并將它的passed_quiesc清0。

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

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

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

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

structrcu_synchronize{

structrcu_head head;

structcompletion completion; //其中包含一個等待隊列

};

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

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

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

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

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

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

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

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

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

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

①當前處理器的passed_quiesc標志是1。

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

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

④當前處理器還未對上一個寬限期的終止進行處理。

⑤當前處理器未注意到當前寬限期的啟動。

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

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

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

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

●如果當前處理器的ready隊列不空，則啟動一個新的寬限期。

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

(3)如果當前處理器的gpnum號小于系統(tǒng)的gpnum號，則將當前處理器的gpnum號設為節(jié)點的gpnum號，并將它的passed_quiesc清0。

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

①將當前處理器的next隊列移到ready隊列中。

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

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

●將系統(tǒng)的completed和所有節(jié)點的completed都設為系統(tǒng)的gpnum?！袢绻斍疤幚砥鞯膔eady隊列不空，則啟動一個新的寬限期；否則，將wait隊列移到nxtlist中。

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

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

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

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

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

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

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

早期的Linux遵循傳統(tǒng)的信號量語義，先對信號量進行加、減操作，再判斷其值的正負。在新的版本中，Linux先判斷信號量的當前值，再進行操作，信號量的值保持非負。當信號量的值大于0時，P操作將其減1；當信號量的值等于0時，P操作將進程掛起等待。當?shù)却犃袨榭諘r，V操作將信號量的值加1；當?shù)却犃胁豢諘r，V操作僅喚醒在隊頭等待的進程。新的實現(xiàn)能減少進程間的競爭。Linux用函數(shù)down()實現(xiàn)P操作，用函數(shù)up()實現(xiàn)V操作，所用經(jīng)典信號量的管理結(jié)構由semaphore描述，如下：

structsemaphore{

spinlock_t lock; //自旋鎖

unsignedint count; //信號量的當前值

structlist_head wait_list; //進程等待隊列

};

無法獲得信號量的進程被包裝在結(jié)構semaphore_waiter中，并被掛在隊列wait_list上等待，如圖9.9所示。

structsemaphore_waiter{

structlist_head list; //隊列節(jié)點

structtask_struct *task; //等待者進程的PCB結(jié)構

int up; //喚醒標志

};

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

WAKEKILL)，申請者進程還可以預定一個最長等待時間。

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

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

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

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

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

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

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

structmutex{

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

spinlock_t wait_lock; //保護用的自旋鎖

structlist_head wait_list; //進程等待隊列

structthread_info *owner; //信號量的持有者

};

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

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

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

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