Linux操作系統(tǒng)第七章

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

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

i++

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

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

獲得i(2)

增加i(2->3)

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

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

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

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

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

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

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

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

<>任務(wù)1

試圖鎖定隊列成功：獲得鎖訪問隊列…為隊列解除鎖…任務(wù)2試圖鎖定隊列失?。旱却却却晒Γ韩@得鎖

訪問隊列…

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

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

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

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

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

<>確定保護(hù)對象

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

典型的死鎖：

四路交通堵塞

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

<>死鎖

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

防止發(fā)生饑餓

不要重復(fù)請求同一個鎖。

越復(fù)雜的加鎖方案越有可能造成死鎖，因此設(shè)計應(yīng)力求簡單

<>死鎖的避免

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

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

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

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

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

原子操作自旋鎖信號量

<>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));打印結(jié)果為7。原子操作Why？大部分同步方案均采用某個物理實體（如鎖、信號燈等）實現(xiàn)通信，進(jìn)程通信原語中關(guān)鎖（lock）和開鎖（unlock）是最簡單的原語。在這兩個原語中設(shè)置一個公共變量x代表某個臨界資源的狀態(tài)。如：x=0，表示資源可用，x=1，表示資源正在使用。關(guān)鎖原語1ock（x）：

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

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

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

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

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

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

自旋鎖不允許任務(wù)睡眠，持有自旋鎖的任務(wù)睡眠會造成自死鎖，因此自旋鎖能夠在中斷上下文中使用。<>自旋鎖定義：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，則表示有資源，該進(jìn)程繼續(xù)執(zhí)行；如果S<0，則表示已無資源，執(zhí)行原語的進(jìn)程被置成阻塞狀態(tài)，并使其在S信號量的隊列中等待，直至其他進(jìn)程在S上執(zhí)行V操作釋放它為止。

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

S:=S+1；(2)

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

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

舉例：有1臺打印機(jī)，兩個并發(fā)執(zhí)行進(jìn)程p1、p2.求采用記錄型信號量機(jī)制，如何解決p1、p2互斥訪問打印機(jī)的問題。解決同步問題ICbuf設(shè)立與資源相關(guān)的私有信號量（資源信號量）。設(shè)緩沖區(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）的抽象模型。事實上，計算機(jī)系統(tǒng)中的許多問題都可歸結(jié)為生產(chǎn)者與消費者問題，生產(chǎn)者與消費者可以通過一個環(huán)形緩沖池（見圖）聯(lián)系起來，環(huán)形緩沖池由幾個大小相等的緩沖塊組成，每個緩沖塊容納一個產(chǎn)品。每個生產(chǎn)者可不斷地每次往緩沖池中送一個生產(chǎn)產(chǎn)品，而每個消費者則可不斷地每次從緩沖池中取出一個產(chǎn)品。

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

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

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中的信號量是一種睡眠鎖。若有一個任務(wù)試圖獲得一個已被持有的信號量時，信號量會將其推入等待隊列，然后讓其睡眠。這時處理器獲得自由而去執(zhí)行其它代碼。當(dāng)持有信號量的進(jìn)程將信號量釋放后，在等待隊列中的一個任務(wù)將被喚醒，從而便可以獲得這個信號量。

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

atomic_tcount;

intsleepers;

wait_queue_head_twait;

}

staticDECL