Linux操作系統第七章

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

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

i++

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

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

獲得i(2)

增加i(2->3)

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

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

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

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

當共享資源是一個復雜的數據結構時，競爭狀態往往會使該數據結構遭到破壞。

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

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

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

<>任務1

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

訪問隊列…

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

找出哪些數據需要保護是關鍵所在

內核任務的局部數據僅僅被它本身訪問，顯然不需要保護

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

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

<>確定保護對象

死鎖產生的條件：有一個或多個并發執行的內核任務和一個或多個資源，每個任務都在等待其中的一個資源，但所有的資源都已經被占用。所有任務都在相互等待，但它們永遠不會釋放已經占有的資源，于是任何任務都無法繼續。

典型的死鎖：

四路交通堵塞

自死鎖：一個執行任務試圖去獲得一個自己已經持有的鎖

<>死鎖

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

防止發生饑餓

不要重復請求同一個鎖。

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

<>死鎖的避免

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

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

睡眠及與用戶空間的同步——在內核執行的進程可能會睡眠，這將喚醒調度程序，導致調度一個新的用戶進程執行。

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

為了避免并發，防止競爭。內核提供了一組同步方法來提供對共享數據的保護

原子操作自旋鎖信號量

<>7.2內核同步措施

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

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

Linux內核提供了一個專門的atomic_t類型（一個24位原子訪問計數器）和一些專門的函數，這些函數作用于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？大部分同步方案均采用某個物理實體（如鎖、信號燈等）實現通信，進程通信原語中關鎖（lock）和開鎖（unlock）是最簡單的原語。在這兩個原語中設置一個公共變量x代表某個臨界資源的狀態。如：x=0，表示資源可用，x=1，表示資源正在使用。關鎖原語1ock（x）：

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

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

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

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

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

自旋鎖在內核中主要用來防止多處理器中并發訪問臨界區，防止內核搶占造成的競爭。

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

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

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

S:=S-1；(2)

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

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

S:=S+1；(2)

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

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

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

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

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

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

P(empty)；

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

V(mutex)；

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

beginwhiletruedobegin

P(full)；

P(mutex)；

goods：=buffer(j)；

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

V(mutex)；

V(empty)；

consumeproduct；

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

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

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

atomic_tcount;

intsleepers;

wait_queue_head_twait;

}

staticDECL