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

1、第七章第七章 內(nèi)核中的同步內(nèi)核中的同步臨界區(qū)和競爭狀態(tài)內(nèi)核同步措施并發(fā)控制什么是什么是臨界區(qū)臨界區(qū)（critical regions）? 就是訪問和操作就是訪問和操作共享數(shù)據(jù)共享數(shù)據(jù)的的代碼段代碼段, ,這段代碼必須被這段代碼必須被原子地原子地執(zhí)行執(zhí)行什么是競爭狀態(tài)什么是競爭狀態(tài)? 多個內(nèi)核任務(wù)同時訪問同一臨界區(qū)多個內(nèi)核任務(wù)同時訪問同一臨界區(qū)什么是同步什么是同步? 避免并發(fā)和防止競爭狀態(tài)稱為避免并發(fā)和防止競爭狀態(tài)稱為同步（同步（synchronization） 7.1 臨界區(qū)和競爭狀態(tài)臨界區(qū)和競爭狀態(tài) 考慮一個非常簡單的共享資源的例子：一個全局整型變量和一個簡單的臨界區(qū)，其中的操作僅僅是將整型

2、變量的值增加1： i+ 該操作可以轉(zhuǎn)化成下面三條機器指令序列：(1) 得到當(dāng)前變量i的值并拷貝到一個寄存器中(2)將寄存器中的值加1(3) 把i的新值寫回到內(nèi)存中 臨界區(qū)舉例臨界區(qū)舉例 內(nèi)核任務(wù)內(nèi)核任務(wù)1 1 內(nèi)核任務(wù)內(nèi)核任務(wù)2 2獲得i(1) - 增加 i(1-2) - 寫回 i(2) - 獲得 i(2) 增加 i(2-3) 寫回 i(3)臨界區(qū)舉例臨界區(qū)舉例 內(nèi)核任務(wù)內(nèi)核任務(wù)1 1 內(nèi)核任務(wù)內(nèi)核任務(wù)2 2獲得 i(1) - - 獲得 i(1) 增加 i(1-2) - - 增加 i(1-2) 寫回 i(2) - - 寫回 i(2) 可能的實際執(zhí)行結(jié)果：期望的結(jié)果同步同步進程之間的一種通信方式

3、，有進程之間的一種通信方式，有時序上的制約關(guān)系時序上的制約關(guān)系，或者說是進程之間為了或者說是進程之間為了協(xié)同工作協(xié)同工作而存在的一種等而存在的一種等待關(guān)系。待關(guān)系。互斥互斥進程之間對臨界資源的一種競爭關(guān)系，進程之間對臨界資源的一種競爭關(guān)系，排他性排他性地地對資源的訪問方式。對資源的訪問方式。同步與互斥同步與互斥 v 當(dāng)共享資源是一個復(fù)雜的數(shù)據(jù)結(jié)構(gòu)時，競爭狀態(tài)往往會使該數(shù)據(jù)結(jié)構(gòu)遭到破壞。v 對于這種情況，鎖機制鎖機制可以避免競爭狀態(tài)正如門鎖和門一樣，門后的房間可想象成一個臨界區(qū)。v 在一個指定時間內(nèi)，房間里只能有個一個內(nèi)核任務(wù)存在，當(dāng)一個任務(wù)進入房間后，它會鎖住身后的房門；當(dāng)它結(jié)束對共享數(shù)據(jù)的操

4、作后，就會走出房間，打開門鎖。如果另一個任務(wù)在房門上鎖時來了,那么它就必須等待房間內(nèi)的任務(wù)出來并打開門鎖后，才能進入房間。 共享隊列和加鎖共享隊列和加鎖 任何要訪問隊列的代碼首先都需要占住相應(yīng)的鎖，這樣該鎖就能阻止來自其它內(nèi)核任務(wù)的并發(fā)訪問： 任務(wù)任務(wù) 1 1 試圖鎖定隊列 成功：獲得鎖 訪問隊列 為隊列解除鎖 任務(wù)任務(wù)2 2 試圖鎖定隊列失敗：等待 等待 等待 成功：獲得鎖 訪問隊列 為隊列解除鎖共享隊列和加鎖共享隊列和加鎖 v 找出哪些數(shù)據(jù)需要保護哪些數(shù)據(jù)需要保護是關(guān)鍵所在v 內(nèi)核任務(wù)的局部數(shù)據(jù)僅僅被它本身訪問，顯然不需要保護v 如果數(shù)據(jù)只會被特定的進程訪問，也不需加鎖 v 大多數(shù)內(nèi)核數(shù)據(jù)

5、結(jié)構(gòu)都需要加鎖大多數(shù)內(nèi)核數(shù)據(jù)結(jié)構(gòu)都需要加鎖：若有其它內(nèi)核任務(wù)可以訪問這些數(shù)據(jù)，那么就給這些數(shù)據(jù)加上某種形式的鎖；若任何其它東西能看到它，那么就要鎖住它 確定保護對象確定保護對象 v 死鎖產(chǎn)生的條件死鎖產(chǎn)生的條件：有一個或多個并發(fā)執(zhí)行的內(nèi)核任務(wù)和一個或多個資源，每個任務(wù)都在等待其中的一個資源，但所有的資源都已經(jīng)被占用。所有任務(wù)都在相互等待，但它們永所有任務(wù)都在相互等待，但它們永遠不會釋放已經(jīng)占有的資源，于是任何任務(wù)遠不會釋放已經(jīng)占有的資源，于是任何任務(wù)都無法繼續(xù)。都無法繼續(xù)。v 典型的死鎖：v 四路交通堵塞v 自死鎖：一個執(zhí)行任務(wù)試圖去獲得一個自己已經(jīng)持有的鎖 死死 鎖鎖 v 加鎖的順序是關(guān)鍵加

6、鎖的順序是關(guān)鍵。使用嵌套的鎖時必須保證以相同的順序獲取鎖，這樣可以阻止致命擁抱類型的死鎖v 防止發(fā)生饑餓防止發(fā)生饑餓 v 不要重復(fù)請求同一個鎖不要重復(fù)請求同一個鎖。v 越復(fù)雜的加鎖方案越有可能造成死鎖，因此設(shè)計應(yīng)力求簡單設(shè)計應(yīng)力求簡單 死鎖的避免死鎖的避免 v 中斷中斷中斷幾乎可以在任何時刻異步發(fā)生，也可能隨時打斷正在執(zhí)行的代碼。v 內(nèi)核搶占內(nèi)核搶占若內(nèi)核具有搶占性，內(nèi)核中的任務(wù)就可能會被另一任務(wù)搶占。v 睡眠及與用戶空間的同步睡眠及與用戶空間的同步在內(nèi)核執(zhí)行的進程可能會睡眠，這將喚醒調(diào)度程序，導(dǎo)致調(diào)度一個新的用戶進程執(zhí)行。v 對稱多處理對稱多處理兩個或多個處理器可以同時執(zhí)行代碼 。并發(fā)執(zhí)行的

7、原因并發(fā)執(zhí)行的原因 v 為了避免并發(fā)，防止競爭。內(nèi)核提供了一組同步方法來提供對共享數(shù)據(jù)的保護v 原子操作原子操作v 自旋鎖自旋鎖v 信號量信號量 7.2 7.2 內(nèi)核同步措施內(nèi)核同步措施 v 原子操作可以保證指令以原子的方式原子的方式 被執(zhí)行。 v 兩個原子操作絕對不可能并發(fā)地訪問同一個變量。v Linux內(nèi)核提供了一個專門的atomic_tatomic_t類型（一個24位原子訪問計數(shù)器）和一些專門的函數(shù) ，這些函數(shù)作用于atomic_t類型的變量。 原子操作原子操作 Linux中的原子操作，見表7.1。 例子：atomic_t v=ATOMIC_INIT(0)；atomic_set(&v,4

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

9、表示資源正在使用。 關(guān)鎖原語關(guān)鎖原語1ock（x）：）： L：if x1 then goto L else x：=1； 開鎖原語開鎖原語unlock（x）：）： x：=0；此兩步之間，此兩步之間，X值不能被值不能被其他進程所改變其他進程所改變lock和和unlock 開鎖和關(guān)鎖程序流程圖開鎖和關(guān)鎖程序流程圖v 自旋鎖是專為防止多處理器并發(fā)多處理器并發(fā)而引入的一種鎖，它在內(nèi)核中大量應(yīng)用于中斷處理等部分，而對于單處理器來說，可簡單采用關(guān)閉中斷的方式防止中斷處理程序的并發(fā)執(zhí)行 。v 自旋鎖最多只能被一個內(nèi)核任務(wù)持有最多只能被一個內(nèi)核任務(wù)持有，若一個內(nèi)核任務(wù)試圖請求一個已被持有的自旋鎖，那么這個任務(wù)就

10、會一直進行忙循環(huán)，也就是旋轉(zhuǎn)，等待鎖重新可用 。自旋鎖自旋鎖 v 設(shè)計自旋鎖的初衷是在短期間內(nèi)進行輕量級輕量級的鎖定的鎖定。一個被持有的自旋鎖使得請求它的任務(wù)在等待鎖重新可用期間進行自旋，所以自旋鎖不應(yīng)該被持有時間過長。v 自旋鎖在內(nèi)核中主要用來防止多處理器中并防止多處理器中并發(fā)訪問臨界區(qū)發(fā)訪問臨界區(qū)，防止內(nèi)核搶占造成的競爭。 v 自旋鎖不允許任務(wù)睡眠不允許任務(wù)睡眠，持有自旋鎖的任務(wù)睡眠會造成自死鎖睡眠會造成自死鎖，因此自旋鎖能夠在中斷上下文中使用。自旋鎖自旋鎖 l 定義：定義：typedef struct volatile unsigned int lock;spinlock_t;l 自旋鎖

11、的使用：自旋鎖的使用：spinlock_t mr_lock=SPIN_LOCK_UNLOCKED;spin_lock(&mr_lock);/*臨界區(qū)臨界區(qū)*/spin_unlock(&mr_lock);l 自旋鎖在內(nèi)核中有許多變種。自旋鎖在內(nèi)核中有許多變種。自旋鎖自旋鎖 信號量：僅能由P、V操作修改的整型變量。整型值整型值 S隊列指針隊列指針 Next信號量P操作：操作：申請資源操作申請資源操作(1)(1) S:=S-1S:=S-1；(2)(2) 如果如果S0，則表示有資源，該進程繼續(xù)，則表示有資源，該進程繼續(xù)執(zhí)行；如果執(zhí)行；如果S0，則該進程繼續(xù)執(zhí)行；如果，則該進程繼續(xù)執(zhí)行；如果S0，則釋放

12、則釋放S信號量隊列的排頭等待者并清信號量隊列的排頭等待者并清除其阻塞狀態(tài)，即從阻塞狀態(tài)轉(zhuǎn)變到就除其阻塞狀態(tài)，即從阻塞狀態(tài)轉(zhuǎn)變到就緒狀態(tài)，執(zhí)行緒狀態(tài)，執(zhí)行V(S)者繼續(xù)執(zhí)行。者繼續(xù)執(zhí)行。 信號量機制的應(yīng)用信號量機制的應(yīng)用 1。解決互斥問題。解決互斥問題 2。解決同步問題。解決同步問題解決互斥問題解決互斥問題 用信號量解決幾個進程互斥進入臨界區(qū)的問用信號量解決幾個進程互斥進入臨界區(qū)的問題，幾個進程共享一個公用信號量題，幾個進程共享一個公用信號量S（互斥（互斥信號量）。信號量）。 每個進程進入臨界區(qū)必須先執(zhí)行每個進程進入臨界區(qū)必須先執(zhí)行P（S），），退出臨界區(qū)后執(zhí)行退出臨界區(qū)后執(zhí)行V（S）。）。 P

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

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

15、個產(chǎn)品。每個生產(chǎn)者可不斷地每次往緩沖池中送一個生產(chǎn)產(chǎn)每個生產(chǎn)者可不斷地每次往緩沖池中送一個生產(chǎn)產(chǎn)品，而每個消費者則可不斷地每次從緩沖池中取出品，而每個消費者則可不斷地每次從緩沖池中取出一個產(chǎn)品。一個產(chǎn)品。 圖圖 環(huán)形緩沖池環(huán)形緩沖池生產(chǎn)者生產(chǎn)者進程進程臨界資源臨界資源消費者消費者進程進程下面給出基于環(huán)形緩沖區(qū)的生產(chǎn)者與消費者關(guān)系的下面給出基于環(huán)形緩沖區(qū)的生產(chǎn)者與消費者關(guān)系的形式描述，設(shè)：形式描述，設(shè)：（1）公用信號量）公用信號量mutex：初值為：初值為1，用于實現(xiàn)臨界區(qū)，用于實現(xiàn)臨界區(qū)互斥?；コ?。（2）生產(chǎn)者私用信號量）生產(chǎn)者私用信號量empty：初值為：初值為n，指示空緩，指示空緩沖塊數(shù)目

16、。沖塊數(shù)目。（3）消費者私用信號量）消費者私用信號量full：初值為：初值為0，指示滿緩沖，指示滿緩沖塊數(shù)目。塊數(shù)目。（4）整型量）整型量i和和j初值均為初值均為0，i指示首空緩沖塊序號，指示首空緩沖塊序號，j指示首滿緩沖塊序號。指示首滿緩沖塊序號。v模塊模塊 設(shè)計如下：設(shè)計如下： 生產(chǎn)者生產(chǎn)者/ /消費者算法描述消費者算法描述var mutexvar mutex，emptyempty，fullfull：psemaphorepsemaphore； i,ji,j，goodsgoods：integerinteger；bufferbuffer：array 0array 0n-1 of itemn-1

17、 of item；procedure producerprocedure producer； 生產(chǎn)者進程生產(chǎn)者進程 beginbegin while true do while true do begin begin produce next product produce next product； P(empty)P(empty)； P(mutexP(mutex) )； buffer(i):=productbuffer(i):=product； i:=(i+1) mod(n)i:=(i+1) mod(n)； V(mutexV(mutex) )； V(full)V(full)； endend

18、endend；滿滿空空ij圖圖3-8 環(huán)形緩沖區(qū)環(huán)形緩沖區(qū)l procedure consumerprocedure consumer； 消費者進消費者進程程l beginbeginl while true do while true dol begin beginl P(fullP(full) )；l P(mutexP(mutex) )；l goodsgoods：= buffer(j= buffer(j) )；l j:=(j+1) mod(nj:=(j+1) mod(n) )；l V(mutexV(mutex) )；l V(emptyV(empty) )；l consume productc

19、onsume product；l endendl end end；生產(chǎn)者生產(chǎn)者/ /消費者算法描述消費者算法描述beginbegin seminitial(mutex.v seminitial(mutex.v，1 1；empty.vempty.v，n n；full.vfull.v，0)0)； i i：=j=j：=0=0； cobegincobegin producer producer； consumerconsumer； coendcoendendend注注 意意 1 每 個 程 序 中 實 現(xiàn) 互 斥 的P(mutex),V(mutex)必須成對出現(xiàn)成對出現(xiàn)。 2Empty和full的P，V操作也必須成對出現(xiàn)，但它們處于不同的程序中。 3. 每個程序中的多個多個P操作不能顛倒順序操作不能顛倒順序，否則可能引起死鎖。 v Linux中的信號量是一種睡眠鎖睡眠鎖。若有一個任務(wù)試圖獲得一個已被持有的信號量時，信號量會將其推入等待隊列，然后讓其睡眠。這時處理器獲得自由而去執(zhí)行其它代碼。當(dāng)持有信號量的進程將信號量釋放后，在等待隊列中的一個任務(wù)將被喚醒，從而便可以獲得這個信號量。v 信號量具有睡眠特性，適用于鎖會被長時間持有的情況，只能在進程上下文中使用。信號量信號量 信號量的使用信號量的使用信號量的定信號量的