第七章內(nèi)核中的同步臨界區(qū)和競爭狀態(tài)內(nèi)核同步措施并發(fā)控制什么是臨界區(qū)（criticalregions）?就是訪問和操作共享數(shù)據(jù)的代碼段,這段代碼必須被原子地執(zhí)行什么是競爭狀態(tài)?多個內(nèi)核任務同時訪問同一臨界區(qū)什么是同步?避免并發(fā)和防止競爭狀態(tài)稱為同步（synchronization）

<>7.1臨界區(qū)和競爭狀態(tài)考慮一個非常簡單的共享資源的例子：一個全局整型變量和一個簡單的臨界區(qū)，其中的操作僅僅是將整型變量的值增加1：

i++

該操作可以轉化成下面三條機器指令序列：(1)得到當前變量i的值并拷貝到一個寄存器中(2)將寄存器中的值加1(3)把i的新值寫回到內(nèi)存中

<>臨界區(qū)舉例內(nèi)核任務1內(nèi)核任務2獲得i(1)---增加i(1->2)---寫回i(2)---

獲得i(2)

增加i(2->3)

寫回i(3)<>臨界區(qū)舉例內(nèi)核任務1內(nèi)核任務2獲得i(1)------獲得i(1)

增加i(1->2)------增加i(1->2)

寫回i(2)------寫回i(2)

可能的實際執(zhí)行結果：期望的結果同步進程之間的一種通信方式，有時序上的制約關系，或者說是進程之間為了協(xié)同工作而存在的一種等待關系?；コ膺M程之間對臨界資源的一種競爭關系，排他性地對資源的訪問方式。同步與互斥

當共享資源是一個復雜的數(shù)據(jù)結構時，競爭狀態(tài)往往會使該數(shù)據(jù)結構遭到破壞。

對于這種情況，鎖機制可以避免競爭狀態(tài)正如門鎖和門一樣，門后的房間可想象成一個臨界區(qū)。

在一個指定時間內(nèi)，房間里只能有個一個內(nèi)核任務存在，當一個任務進入房間后，它會鎖住身后的房門；當它結束對共享數(shù)據(jù)的操作后，就會走出房間，打開門鎖。如果另一個任務在房門上鎖時來了,那么它就必須等待房間內(nèi)的任務出來并打開門鎖后，才能進入房間。

<>共享隊列和加鎖任何要訪問隊列的代碼首先都需要占住相應的鎖，這樣該鎖就能阻止來自其它內(nèi)核任務的并發(fā)訪問：

<>任務1

試圖鎖定隊列成功：獲得鎖訪問隊列…為隊列解除鎖…任務2試圖鎖定隊列失敗：等待…等待…等待…成功：獲得鎖

訪問隊列…

為隊列解除鎖共享隊列和加鎖

找出哪些數(shù)據(jù)需要保護是關鍵所在

內(nèi)核任務的局部數(shù)據(jù)僅僅被它本身訪問，顯然不需要保護

如果數(shù)據(jù)只會被特定的進程訪問，也不需加鎖

大多數(shù)內(nèi)核數(shù)據(jù)結構都需要加鎖：若有其它內(nèi)核任務可以訪問這些數(shù)據(jù)，那么就給這些數(shù)據(jù)加上某種形式的鎖；若任何其它東西能看到它，那么就要鎖住它

<>確定保護對象

死鎖產(chǎn)生的條件：有一個或多個并發(fā)執(zhí)行的內(nèi)核任務和一個或多個資源，每個任務都在等待其中的一個資源，但所有的資源都已經(jīng)被占用。所有任務都在相互等待，但它們永遠不會釋放已經(jīng)占有的資源，于是任何任務都無法繼續(xù)。

典型的死鎖：

四路交通堵塞

自死鎖：一個執(zhí)行任務試圖去獲得一個自己已經(jīng)持有的鎖

<>死鎖

加鎖的順序是關鍵。使用嵌套的鎖時必須保證以相同的順序獲取鎖，這樣可以阻止致命擁抱類型的死鎖

防止發(fā)生饑餓

不要重復請求同一個鎖。

越復雜的加鎖方案越有可能造成死鎖，因此設計應力求簡單

<>死鎖的避免

中斷——中斷幾乎可以在任何時刻異步發(fā)生，也可能隨時打斷正在執(zhí)行的代碼。

內(nèi)核搶占——若內(nèi)核具有搶占性，內(nèi)核中的任務就可能會被另一任務搶占。

睡眠及與用戶空間的同步——在內(nèi)核執(zhí)行的進程可能會睡眠，這將喚醒調(diào)度程序，導致調(diào)度一個新的用戶進程執(zhí)行。

對稱多處理——兩個或多個處理器可以同時執(zhí)行代碼。<>并發(fā)執(zhí)行的原因

為了避免并發(fā)，防止競爭。內(nèi)核提供了一組同步方法來提供對共享數(shù)據(jù)的保護

原子操作自旋鎖信號量

<>7.2內(nèi)核同步措施

原子操作可以保證指令以原子的方式被執(zhí)行。

兩個原子操作絕對不可能并發(fā)地訪問同一個變量。

Linux內(nèi)核提供了一個專門的atomic_t類型（一個24位原子訪問計數(shù)器）和一些專門的函數(shù)，這些函數(shù)作用于atomic_t類型的變量。

<>原子操作Linux中的原子操作，見表7.1。例子：atomic_tv=ATOMIC_INIT(0)；atomic_set(&v,4);atomic_add(2,&v);atomic_inc(&v);printk(“%d\n”,atomic_read(&v));打印結果為7。原子操作Why？大部分同步方案均采用某個物理實體（如鎖、信號燈等）實現(xiàn)通信，進程通信原語中關鎖（lock）和開鎖（unlock）是最簡單的原語。在這兩個原語中設置一個公共變量x代表某個臨界資源的狀態(tài)。如：x=0，表示資源可用，x=1，表示資源正在使用。關鎖原語1ock（x）：

L：ifx＝1thengotoLelsex：=1；開鎖原語unlock（x）：

x：=0；此兩步之間，X值不能被其他進程所改變lock和unlock開鎖和關鎖程序流程圖

自旋鎖是專為防止多處理器并發(fā)而引入的一種鎖，它在內(nèi)核中大量應用于中斷處理等部分，而對于單處理器來說，可簡單采用關閉中斷的方式防止中斷處理程序的并發(fā)執(zhí)行。

自旋鎖最多只能被一個內(nèi)核任務持有，若一個內(nèi)核任務試圖請求一個已被持有的自旋鎖，那么這個任務就會一直進行忙循環(huán)，也就是旋轉，等待鎖重新可用。<>自旋鎖

設計自旋鎖的初衷是在短期間內(nèi)進行輕量級的鎖定。一個被持有的自旋鎖使得請求它的任務在等待鎖重新可用期間進行自旋，所以自旋鎖不應該被持有時間過長。

自旋鎖在內(nèi)核中主要用來防止多處理器中并發(fā)訪問臨界區(qū)，防止內(nèi)核搶占造成的競爭。

自旋鎖不允許任務睡眠，持有自旋鎖的任務睡眠會造成自死鎖，因此自旋鎖能夠在中斷上下文中使用。<>自旋鎖定義：typedef

struct{volatileunsignedintlock;}spinlock_t;自旋鎖的使用：spinlock_t

mr_lock=SPIN_LOCK_UNLOCKED;spin_lock(&mr_lock);/*臨界區(qū)*/spin_unlock(&mr_lock);自旋鎖在內(nèi)核中有許多變種。自旋鎖信號量：僅能由P、V操作修改的整型變量。整型值S隊列指針Next信號量P操作：申請資源操作(1)

S:=S-1；(2)

如果S≥0，則表示有資源，該進程繼續(xù)執(zhí)行；如果S<0，則表示已無資源，執(zhí)行原語的進程被置成阻塞狀態(tài)，并使其在S信號量的隊列中等待，直至其他進程在S上執(zhí)行V操作釋放它為止。

P操作V操作V操作：釋放資源操作(1)

S:=S+1；(2)

如果S>0，則該進程繼續(xù)執(zhí)行；如果S≤0，則釋放S信號量隊列的排頭等待者并清除其阻塞狀態(tài)，即從阻塞狀態(tài)轉變到就緒狀態(tài)，執(zhí)行V(S)者繼續(xù)執(zhí)行。

信號量機制的應用1。解決互斥問題2。解決同步問題解決互斥問題用信號量解決幾個進程互斥進入臨界區(qū)的問題，幾個進程共享一個公用信號量S（互斥信號量）。每個進程進入臨界區(qū)必須先執(zhí)行P（S），退出臨界區(qū)后執(zhí)行V（S）。P（S）V（S）臨界區(qū)

舉例：有1臺打印機，兩個并發(fā)執(zhí)行進程p1、p2.求采用記錄型信號量機制，如何解決p1、p2互斥訪問打印機的問題。解決同步問題ICbuf設立與資源相關的私有信號量（資源信號量）。設緩沖區(qū)只有一個緩沖單元Empty=1表示空單元個數(shù)。Full=0表示裝滿信息的單元個數(shù)。IP(empty)V(full)P(full)V(empty)C放數(shù)據(jù)取數(shù)據(jù)經(jīng)典的同步/互斥問題生產(chǎn)者與消費者生產(chǎn)者與消費者問題

Dijkstra把廣義同步問題抽象成一種“生產(chǎn)者與消費者問題”（Producer-consumer-relationship）的抽象模型。事實上，計算機系統(tǒng)中的許多問題都可歸結為生產(chǎn)者與消費者問題，生產(chǎn)者與消費者可以通過一個環(huán)形緩沖池（見圖）聯(lián)系起來，環(huán)形緩沖池由幾個大小相等的緩沖塊組成，每個緩沖塊容納一個產(chǎn)品。每個生產(chǎn)者可不斷地每次往緩沖池中送一個生產(chǎn)產(chǎn)品，而每個消費者則可不斷地每次從緩沖池中取出一個產(chǎn)品。

圖環(huán)形緩沖池生產(chǎn)者進程臨界資源消費者進程下面給出基于環(huán)形緩沖區(qū)的生產(chǎn)者與消費者關系的形式描述，設：（1）公用信號量mutex：初值為1，用于實現(xiàn)臨界區(qū)互斥。（2）生產(chǎn)者私用信號量empty：初值為n，指示空緩沖塊數(shù)目。（3）消費者私用信號量full：初值為0，指示滿緩沖塊數(shù)目。（4）整型量i和j初值均為0，i指示首空緩沖塊序號，j指示首滿緩沖塊序號。模塊設計如下：

生產(chǎn)者/消費者算法描述varmutex，empty，full：psemaphore；i,j，goods：integer；buffer：array[0…n-1]ofitem；procedureproducer；生產(chǎn)者進程beginwhiletruedobeginproducenextproduct；

P(empty)；

P(mutex)；buffer(i):=product；i:=(i+1)mod(n)；

V(mutex)；

V(full)；endend；滿空ij圖3-8環(huán)形緩沖區(qū)procedureconsumer；消費者進程

beginwhiletruedobegin

P(full)；

P(mutex)；

goods：=buffer(j)；

j:=(j+1)mod(n)；

V(mutex)；

V(empty)；

consumeproduct；

endend；生產(chǎn)者/消費者算法描述beginseminitial(mutex.v，1；empty.v，n；full.v，0)；i：=j：=0；cobeginproducer；consumer；coendend注意1．每個程序中實現(xiàn)互斥的P(mutex),V(mutex)必須成對出現(xiàn)。2．Empty和full的P，V操作也必須成對出現(xiàn)，但它們處于不同的程序中。3.每個程序中的多個P操作不能顛倒順序，否則可能引起死鎖。

Linux中的信號量是一種睡眠鎖。若有一個任務試圖獲得一個已被持有的信號量時，信號量會將其推入等待隊列，然后讓其睡眠。這時處理器獲得自由而去執(zhí)行其它代碼。當持有信號量的進程將信號量釋放后，在等待隊列中的一個任務將被喚醒，從而便可以獲得這個信號量。

信號量具有睡眠特性，適用于鎖會被長時間持有的情況，只能在進程上下文中使用。<>信號量信號量的使用<>信號量的定義structsemaphore{

atomic_tcount;

intsleepers;

wait_queue_head_twait;

}

staticDECL