第七章 進(jìn)程同步

1、CHAPTER 7: PROCESS SYNCHRONIZATION (進(jìn)程同步進(jìn)程同步)n背景背景n臨界區(qū)問題臨界區(qū)問題n早期的軟件同步方法早期的軟件同步方法n硬件同步方法硬件同步方法n信號量信號量n管程管程n經(jīng)典同步問題經(jīng)典同步問題nSolaris 2 & Windows 2000的同步的同步背景背景進(jìn)程間的關(guān)系進(jìn)程間的關(guān)系n資源共享關(guān)系資源共享關(guān)系(間接相互作用間接相互作用,互斥關(guān)系互斥關(guān)系)共享共享CPU和和I/O設(shè)備設(shè)備共享變量共享變量l共享變量的修改沖突共享變量的修改沖突l操作順序沖突操作順序沖突n相互合作關(guān)系相互合作關(guān)系(直接相互作用直接相互作用,同步關(guān)系同步關(guān)系)輸入進(jìn)

2、程、計(jì)算進(jìn)程和打印進(jìn)程輸入進(jìn)程、計(jì)算進(jìn)程和打印進(jìn)程輸入進(jìn)程輸入進(jìn)程A通過單緩沖區(qū)向進(jìn)程通過單緩沖區(qū)向進(jìn)程B提供數(shù)據(jù)提供數(shù)據(jù) 有界緩沖區(qū)有界緩沖區(qū):共享數(shù)據(jù)共享數(shù)據(jù)n共享數(shù)據(jù)共享數(shù)據(jù)#define BUFFER_SIZE 10typedef struct . . . item;item bufferBUFFER_SIZE;int in = 0;int out = 0;int counter = 0;Bounded-Buffer: Producern生產(chǎn)進(jìn)程生產(chǎn)進(jìn)程item nextProduced;while (1) while (counter = BUFFER_SIZE); /* do no

3、thing */bufferin = nextProduced;in = (in + 1) % BUFFER_SIZE;counter+;Bounded-Buffer: Consumern消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程item nextConsumed;while (1) while (counter = 0); /* do nothing */nextConsumed = bufferout;out = (out + 1) % BUFFER_SIZE;counter-;Bounded-Buffer: 與時(shí)間有關(guān)的錯(cuò)誤與時(shí)間有關(guān)的錯(cuò)誤n語句語句“count+”可按如下方式實(shí)現(xiàn)可按如下方式實(shí)現(xiàn)regist

4、er1 = counterregister1 = register1 + 1counter = register1n語句語句“count-”可按如下方式實(shí)現(xiàn)可按如下方式實(shí)現(xiàn)register2 = counterregister2 = register2 1counter = register2Bounded-Buffer:與時(shí)間有關(guān)的錯(cuò)誤與時(shí)間有關(guān)的錯(cuò)誤n假定假定counter的值是的值是5.一個(gè)交叉執(zhí)行的序列一個(gè)交叉執(zhí)行的序列:p: register1 = counter /(p: register1 = counter /(register1 = 5register1 = 5) )p: r

5、egister1 = register1 + 1 /(p: register1 = register1 + 1 /(register1 = 6register1 = 6) )c: register2 = counter /(c: register2 = counter /(register2 = 5register2 = 5) )c: register2 = register2 1 /(c: register2 = register2 1 /(register2 = 4register2 = 4) )p: counter = register1 /(p: counter = register1

6、 /(counter = 6counter = 6) )c: counter = register2 /(c: counter = register2 /(counter = 4counter = 4) )nCounter值可能是值可能是 4 和和 6, 但現(xiàn)在正確的值應(yīng)該是但現(xiàn)在正確的值應(yīng)該是5.n進(jìn)程同步進(jìn)程同步臨界資源臨界資源n臨界資源（臨界資源（critical resouce）：一次只允許一個(gè)）：一次只允許一個(gè)進(jìn)程使用的共享資源進(jìn)程使用的共享資源 。n臨界區(qū)（臨界區(qū)（critical section） ：每個(gè)進(jìn)程中訪問臨：每個(gè)進(jìn)程中訪問臨界資源的那段代碼界資源的那段代碼 。臨界區(qū)的訪

7、問過程臨界區(qū)的訪問過程entry sectionexit section critical section remainder sectionn臨界區(qū)臨界區(qū)(critical section)：進(jìn)程中訪問臨界資源的：進(jìn)程中訪問臨界資源的一段代碼。一段代碼。n進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū)(entry section)：在進(jìn)入臨界區(qū)之前，檢查：在進(jìn)入臨界區(qū)之前，檢查可否進(jìn)入臨界區(qū)的一段代碼。如果可以進(jìn)入臨界可否進(jìn)入臨界區(qū)的一段代碼。如果可以進(jìn)入臨界區(qū)，通常設(shè)置相應(yīng)區(qū)，通常設(shè)置相應(yīng)正在訪問臨界區(qū)正在訪問臨界區(qū)標(biāo)志標(biāo)志n退出區(qū)退出區(qū)(exit section)：用于將：用于將正在訪問臨界區(qū)正在訪問臨界區(qū)標(biāo)標(biāo)志清除。志

8、清除。n剩余區(qū)剩余區(qū)(remainder section)：代碼中的其余部分。：代碼中的其余部分。同步機(jī)制應(yīng)遵循的準(zhǔn)則同步機(jī)制應(yīng)遵循的準(zhǔn)則n有空讓進(jìn)：其他進(jìn)程均不處于臨界區(qū)；有空讓進(jìn)：其他進(jìn)程均不處于臨界區(qū)；n忙則等待（互斥）：已有進(jìn)程處于其臨界區(qū)；忙則等待（互斥）：已有進(jìn)程處于其臨界區(qū)；n有限等待：等待進(jìn)入臨界區(qū)的進(jìn)程不能有限等待：等待進(jìn)入臨界區(qū)的進(jìn)程不能死等死等；n讓權(quán)等待：不能進(jìn)入臨界區(qū)的進(jìn)程，應(yīng)釋放讓權(quán)等待：不能進(jìn)入臨界區(qū)的進(jìn)程，應(yīng)釋放CPU（如轉(zhuǎn)換到阻塞狀態(tài)（如轉(zhuǎn)換到阻塞狀態(tài),不不忙等忙等）進(jìn)程互斥的軟件方法進(jìn)程互斥的軟件方法n有兩個(gè)進(jìn)程有兩個(gè)進(jìn)程Pi, Pj，其中的，其中的Pi算法

9、1：單標(biāo)志n 設(shè)立一個(gè)公用整型變量設(shè)立一個(gè)公用整型變量 turn：描述允許進(jìn)入臨界：描述允許進(jìn)入臨界區(qū)的進(jìn)程標(biāo)識區(qū)的進(jìn)程標(biāo)識在進(jìn)入?yún)^(qū)循環(huán)檢查是否允許本進(jìn)程進(jìn)入：在進(jìn)入?yún)^(qū)循環(huán)檢查是否允許本進(jìn)程進(jìn)入：turn為為i時(shí)，進(jìn)時(shí)，進(jìn)程程Pi可進(jìn)入；可進(jìn)入；在退出區(qū)修改允許進(jìn)入進(jìn)程標(biāo)識：進(jìn)程在退出區(qū)修改允許進(jìn)入進(jìn)程標(biāo)識：進(jìn)程Pi退出時(shí)，改退出時(shí)，改turn為進(jìn)程為進(jìn)程Pj的標(biāo)識的標(biāo)識j；while (turn!=i) ;turn = j;critical sectionremainder sectionn缺點(diǎn)：缺點(diǎn)：強(qiáng)制輪流強(qiáng)制輪流進(jìn)入臨界區(qū)，沒有考慮進(jìn)程的進(jìn)入臨界區(qū)，沒有考慮進(jìn)程的實(shí)際需要。容易造成實(shí)際

10、需要。容易造成資源利用不充分資源利用不充分：在：在Pi出出讓臨界區(qū)之后，讓臨界區(qū)之后，Pj使用臨界區(qū)之前，使用臨界區(qū)之前，Pi不可能不可能再次使用臨界區(qū)；再次使用臨界區(qū)；n違背違背”空閑讓進(jìn)空閑讓進(jìn)”準(zhǔn)則準(zhǔn)則算法算法2：雙標(biāo)志、先檢查：雙標(biāo)志、先檢查n設(shè)立一個(gè)標(biāo)志數(shù)組設(shè)立一個(gè)標(biāo)志數(shù)組flag：描述進(jìn)程是否在臨界區(qū)：描述進(jìn)程是否在臨界區(qū)，初值均為，初值均為FALSE。先檢查，后修改：在進(jìn)入?yún)^(qū)檢查另一個(gè)進(jìn)程是否先檢查，后修改：在進(jìn)入?yún)^(qū)檢查另一個(gè)進(jìn)程是否在臨界區(qū)，不在時(shí)修改本進(jìn)程在臨界區(qū)的標(biāo)志；在臨界區(qū)，不在時(shí)修改本進(jìn)程在臨界區(qū)的標(biāo)志；在退出區(qū)修改本進(jìn)程在臨界區(qū)的標(biāo)志；在退出區(qū)修改本進(jìn)程在臨界區(qū)的標(biāo)

11、志；while (flagj);flagi = TRUE;flagi = FALSE;critical sectionremainder sectionVar flag: array0,1,n of boolean;n優(yōu)點(diǎn)：不用交替進(jìn)入，可連續(xù)使用；優(yōu)點(diǎn)：不用交替進(jìn)入，可連續(xù)使用；n缺點(diǎn)：缺點(diǎn)：Pi和和Pj可能同時(shí)進(jìn)入臨界區(qū)。按下面序可能同時(shí)進(jìn)入臨界區(qū)。按下面序列執(zhí)行時(shí)，會同時(shí)進(jìn)入：列執(zhí)行時(shí)，會同時(shí)進(jìn)入：“Pi Pj Pi Pj”。即在檢查對方。即在檢查對方flag之后和切換自己之后和切換自己flag之前有一段時(shí)間，結(jié)果都檢查通過。這里的問之前有一段時(shí)間，結(jié)果都檢查通過。這里的問題出在檢查和修

12、改操作不能連續(xù)進(jìn)行。題出在檢查和修改操作不能連續(xù)進(jìn)行。n違背了違背了”忙則等待忙則等待”的準(zhǔn)則的準(zhǔn)則算法算法3：雙標(biāo)志、后檢查：雙標(biāo)志、后檢查n類似于算法類似于算法2，與互斥算法，與互斥算法2的區(qū)別在于先修改的區(qū)別在于先修改后檢查。可防止兩個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)。后檢查?？煞乐箖蓚€(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)。flagi = TRUE;while (flagj);flagi = FALSE;critical sectionremainder sectionn缺點(diǎn)：缺點(diǎn)：Pi和和Pj可能都進(jìn)入不了臨界區(qū)可能都進(jìn)入不了臨界區(qū)。按下面。按下面序列執(zhí)行時(shí)，會都進(jìn)不了臨界區(qū)：序列執(zhí)行時(shí)，會都進(jìn)不了臨界區(qū)：“Pi P

13、j Pi Pj”。即在切換自己。即在切換自己flag之后和檢查對之后和檢查對方方flag之前有一段時(shí)間，結(jié)果都切換之前有一段時(shí)間，結(jié)果都切換flag，都檢，都檢查不通過。查不通過。n違背違背“有限等待有限等待”和和“有空讓進(jìn)有空讓進(jìn)”原則準(zhǔn)則原則準(zhǔn)則算法算法4(Petersons Algorithm)：先修改、后檢查、后修改者等待先修改、后檢查、后修改者等待n結(jié)合算法結(jié)合算法1和算法和算法3，是正確的算法，是正確的算法nturn=j;描述可進(jìn)入的進(jìn)程（同時(shí)修改標(biāo)志時(shí)）描述可進(jìn)入的進(jìn)程（同時(shí)修改標(biāo)志時(shí)）n在進(jìn)入?yún)^(qū)先修改后檢查，并檢查并發(fā)修改的先后：在進(jìn)入?yún)^(qū)先修改后檢查，并檢查并發(fā)修改的先后：檢查

14、對方檢查對方flag，如果不在臨界區(qū)則自己進(jìn)入空閑則入，如果不在臨界區(qū)則自己進(jìn)入空閑則入否則再檢查否則再檢查turn：保存的是較晚的一次賦值保存的是較晚的一次賦值，則較晚的進(jìn)，則較晚的進(jìn)程等待，較早的進(jìn)程進(jìn)入先到先入，后到等待程等待，較早的進(jìn)程進(jìn)入先到先入，后到等待n既保既保證證“忙忙則等待則等待”又實(shí)現(xiàn)又實(shí)現(xiàn)了了“有有空讓進(jìn)空讓進(jìn)”flagi = TRUE; turn = j;while (flagj & turn = j) ;flagi = FALSE;critical sectionremainder sectionN-進(jìn)程進(jìn)程: 面包師算法（面包師算法（Bakery Algor

15、ithm）面包師算法是面包師算法是n個(gè)進(jìn)程進(jìn)入臨界區(qū)問題的算法個(gè)進(jìn)程進(jìn)入臨界區(qū)問題的算法n進(jìn)入商店時(shí)，每個(gè)客戶（進(jìn)程）收到一個(gè)號碼進(jìn)入商店時(shí)，每個(gè)客戶（進(jìn)程）收到一個(gè)號碼 n具有最小號碼的客戶先得到服務(wù)（進(jìn)入臨界區(qū)）具有最小號碼的客戶先得到服務(wù)（進(jìn)入臨界區(qū)）n如果進(jìn)程如果進(jìn)程 Pi and Pj 收到相同的號碼收到相同的號碼,如果如果i j, 那么那么Pi 先得到服務(wù)先得到服務(wù);否則否則Pj 先等到服務(wù)先等到服務(wù)n泛函序列泛函序列 (號碼號碼, 進(jìn)程進(jìn)程id)(a,b) (c,d) if a c or if a = c and b dmax (a0, an-1) 是數(shù)是數(shù)k,從而從而k ai

16、對對 i = 0, 1, 2, , n 1 成立成立n共享數(shù)據(jù)結(jié)構(gòu)共享數(shù)據(jù)結(jié)構(gòu) boolean choosingn;int numbern;面包師算法（面包師算法（Bakery Algorithm）do choosingi = true;numberi = max(number0, number1, , number n 1)+1;choosingi = false;for (j = 0; j n; j+) while (choosingj) ; while (numberj != 0) & ( (numberj,j) (numberi,i) ) ) ;critical section

17、numberi = 0;remainder section while (1);抓號面包師算法（面包師算法（Bakery Algorithm）n如果如果Pi 在臨界區(qū)內(nèi)，在臨界區(qū)內(nèi)，Pj (j!=i) 已經(jīng)選擇了已經(jīng)選擇了 numberj != 0, 那么那么(numberi,i) (numberj, j)或或 (numberi,i) 是最小號碼是最小號碼(number0, 0), (number1, 1), (number2, 2), n互斥互斥只有進(jìn)程有最小的只有進(jìn)程有最小的(numberi,i) 才能進(jìn)入臨界才能進(jìn)入臨界區(qū)區(qū) n進(jìn)程推進(jìn)和有限等待進(jìn)程推進(jìn)和有限等待 FCFS SYNCHR

18、ONIZATION HARDWAREn軟件方法解決臨界區(qū)問題時(shí)，修改變量通過禁止軟件方法解決臨界區(qū)問題時(shí)，修改變量通過禁止中斷來實(shí)現(xiàn)中斷來實(shí)現(xiàn)適合應(yīng)用于單處理機(jī)適合應(yīng)用于單處理機(jī)不適合于多處理機(jī)系統(tǒng)不適合于多處理機(jī)系統(tǒng)n可以利用某些硬件指令其讀寫操作由一條指可以利用某些硬件指令其讀寫操作由一條指令完成，因而保證讀操作與寫操作不被打斷（原令完成，因而保證讀操作與寫操作不被打斷（原子指令）子指令）TestAndSetSwapTestAndSetn測試和修改都包含在一個(gè)原子指令中測試和修改都包含在一個(gè)原子指令中boolean TestAndSet(boolean &target) boole

19、an rv = ⌖&target = true;return rv;TestAndSet: 互斥互斥 n共享數(shù)據(jù)共享數(shù)據(jù) boolean lock = false;n進(jìn)程進(jìn)程Pido while (TestAndSet(&lock) ;critical sectionlock = false;remainder sectionwhile(1);SwapnSwap 操作兩個(gè)變量（原子操作）操作兩個(gè)變量（原子操作）void Swap(boolean &a, boolean &b) boolean temp = &a;&a = &

20、amp;b;&b = temp;Swap: 互斥互斥n共享數(shù)據(jù)共享數(shù)據(jù)(初始化為初始化為false): boolean lock;boolean waitingn;n進(jìn)程進(jìn)程 Pido key = true;while (key = true) Swap(&lock,&key);critical sectionlock = false;remainder section用用TestAndSet指令實(shí)現(xiàn)有限等待的算法指令實(shí)現(xiàn)有限等待的算法n定義如下全局變量，初始值均為定義如下全局變量，初始值均為0Int waitingn;Int lockn每一進(jìn)程定義如下局部變量每一進(jìn)程

21、定義如下局部變量Int j;Int key;用用TestAndSet指令實(shí)現(xiàn)有限等待的算法指令實(shí)現(xiàn)有限等待的算法do waitingi = true; key = true; while (waitingi & key) key = TestAndSet(lock); waitingi = false; critical section j = (i+1)%n; while (j != i) & !waitingj ) j = (j+1) % n; if (j=i) lock = false; else waitingj = false; remainder section w

22、hile (1);用用TestAndSet指令實(shí)現(xiàn)有限等待的算法指令實(shí)現(xiàn)有限等待的算法n互斥互斥:只有在只有在waitingi = false or key = false時(shí)，時(shí)，進(jìn)程進(jìn)程Pi可以進(jìn)入它的臨界區(qū)可以進(jìn)入它的臨界區(qū)key = false: 第一個(gè)執(zhí)行第一個(gè)執(zhí)行TestAndSet指令的進(jìn)程指令的進(jìn)程 waitingi = false: 其它所有進(jìn)程都不在臨界區(qū)其它所有進(jìn)程都不在臨界區(qū) n 進(jìn)程推進(jìn)和有限等待進(jìn)程推進(jìn)和有限等待: 當(dāng)一個(gè)進(jìn)程離開它的臨界區(qū)時(shí)，會按順序掃描數(shù)組當(dāng)一個(gè)進(jìn)程離開它的臨界區(qū)時(shí)，會按順序掃描數(shù)組waiting它指定第一個(gè)進(jìn)入進(jìn)入?yún)^(qū)的進(jìn)程進(jìn)入臨界區(qū)它指定第一個(gè)進(jìn)

23、入進(jìn)入?yún)^(qū)的進(jìn)程進(jìn)入臨界區(qū)任何等待進(jìn)程最多只需等待任何等待進(jìn)程最多只需等待n-1次次多處理機(jī)多處理機(jī)n兩個(gè)處理機(jī)可能會同時(shí)執(zhí)行兩個(gè)處理機(jī)可能會同時(shí)執(zhí)行swap指令或指令或Test_and_setn鎖總線鎖總線n忙式等待稱之為忙式等待稱之為自旋鎖自旋鎖n自旋鎖低效自旋鎖低效但在多處理機(jī)中但在多處理機(jī)中經(jīng)常采用經(jīng)常采用 b=1;while(b) lock(bus); b = test_and_set(&lock); unlock(bus);Lock=0;critical sectionremainder section信號量信號量n信號量信號量(semaphore): 1965年，由荷蘭學(xué)者

24、年，由荷蘭學(xué)者Dijkstra提出，是一種卓有成效的進(jìn)程同步機(jī)制提出，是一種卓有成效的進(jìn)程同步機(jī)制。n可以把信號量看作一個(gè)具有整形數(shù)值的變量，可以把信號量看作一個(gè)具有整形數(shù)值的變量，在它之上定義三個(gè)操作：在它之上定義三個(gè)操作：一個(gè)信號量一個(gè)信號量S可以初始化為非負(fù)數(shù)?？梢猿跏蓟癁榉秦?fù)數(shù)。操作使信號量減操作使信號量減1。如果值變成負(fù)數(shù)，則。如果值變成負(fù)數(shù)，則執(zhí)行操作的進(jìn)程被阻塞。執(zhí)行操作的進(jìn)程被阻塞。操作使信號量加操作使信號量加1。如果值不是正數(shù)，則。如果值不是正數(shù)，則被操作阻塞的進(jìn)程被解除阻塞被操作阻塞的進(jìn)程被解除阻塞(喚醒喚醒)。nP、V分別是荷蘭語的分別是荷蘭語的test (probere

25、n)和和increment (verhogen)，P、V操作是兩個(gè)原子操操作是兩個(gè)原子操作。作。(wait,signal)利用信號量實(shí)現(xiàn)互斥利用信號量實(shí)現(xiàn)互斥 為臨界資源設(shè)置一個(gè)互斥信號量為臨界資源設(shè)置一個(gè)互斥信號量mutex (MUTual EXclusion)，其初值為，其初值為1；在每個(gè)；在每個(gè)進(jìn)程中將臨界區(qū)代碼置于進(jìn)程中將臨界區(qū)代碼置于P(mutex)和和V(mutex)原語之間原語之間V(mutex);critical sectionremainder sectionP(mutex);例例1：設(shè)進(jìn)程：設(shè)進(jìn)程A和進(jìn)程和進(jìn)程B，它們都要求進(jìn)入臨界段，它們都要求進(jìn)入臨界段CS，完成兩個(gè)進(jìn)程

26、互斥要求的設(shè)計(jì)。，完成兩個(gè)進(jìn)程互斥要求的設(shè)計(jì)。 信號量信號量 S1； 進(jìn)程進(jìn)程A： 進(jìn)程進(jìn)程B: P(S); P(S); 臨界區(qū)臨界區(qū)A； 臨界區(qū)臨界區(qū)B; V(S); V(S); n必須必須成對成對使用使用P和和V原語原語P、V原語不能次序錯(cuò)誤、重復(fù)或遺漏原語不能次序錯(cuò)誤、重復(fù)或遺漏利用信號量實(shí)現(xiàn)前趨利用信號量實(shí)現(xiàn)前趨(同步同步)關(guān)系關(guān)系n前趨關(guān)系：并發(fā)執(zhí)行的進(jìn)程前趨關(guān)系：并發(fā)執(zhí)行的進(jìn)程P1和和P2中，分別有中，分別有代碼代碼C1和和C2，要求，要求C1在在C2開始前完成；開始前完成；n為每個(gè)前趨關(guān)系設(shè)置一個(gè)互斥信號量為每個(gè)前趨關(guān)系設(shè)置一個(gè)互斥信號量S12，其初，其初值為值為0P2P1C1C

27、2V(S12);P(S12);記錄型信號量機(jī)制記錄型信號量機(jī)制n每個(gè)信號量每個(gè)信號量s除一個(gè)整數(shù)值除一個(gè)整數(shù)值s.value（計(jì)數(shù)）外，還（計(jì)數(shù)）外，還有一個(gè)進(jìn)程等待隊(duì)列有一個(gè)進(jìn)程等待隊(duì)列s.queue，其中是阻塞在該信，其中是阻塞在該信號量的各個(gè)進(jìn)程的標(biāo)識號量的各個(gè)進(jìn)程的標(biāo)識 Typedef semaphore struct int count; int *queue; n信號量只能通過初始化和兩個(gè)標(biāo)準(zhǔn)的原語來訪問信號量只能通過初始化和兩個(gè)標(biāo)準(zhǔn)的原語來訪問作為作為OS核心代碼執(zhí)行，不受進(jìn)程調(diào)度的打斷核心代碼執(zhí)行，不受進(jìn)程調(diào)度的打斷n初始化指定一個(gè)非負(fù)整數(shù)值，表示空閑資源總數(shù)初始化指定一個(gè)非負(fù)

28、整數(shù)值，表示空閑資源總數(shù)（又稱為（又稱為資源信號量資源信號量”) P原語原語wait(s)-s.value;/表示申請一個(gè)資源表示申請一個(gè)資源;if (s.value 0)/表示沒有空閑資源表示沒有空閑資源; 調(diào)用進(jìn)程進(jìn)入等待隊(duì)列調(diào)用進(jìn)程進(jìn)入等待隊(duì)列s.queue; 阻塞調(diào)用進(jìn)程阻塞調(diào)用進(jìn)程;V原語原語signal(s)+s.value;/表示釋放一個(gè)資源；表示釋放一個(gè)資源；if (s.value = 0)/表示有進(jìn)程處于阻塞狀態(tài)表示有進(jìn)程處于阻塞狀態(tài)； 從等待隊(duì)列從等待隊(duì)列s.queue中取出一個(gè)進(jìn)程中取出一個(gè)進(jìn)程P; 進(jìn)程進(jìn)程P進(jìn)入就緒隊(duì)列進(jìn)入就緒隊(duì)列;V原語通常喚醒進(jìn)程等待隊(duì)列中的頭一個(gè)

29、進(jìn)程原語通常喚醒進(jìn)程等待隊(duì)列中的頭一個(gè)進(jìn)程死鎖和饑餓死鎖和饑餓n死鎖：兩個(gè)或多個(gè)進(jìn)程無限等待一個(gè)事件，而這死鎖：兩個(gè)或多個(gè)進(jìn)程無限等待一個(gè)事件，而這個(gè)事件又只能由這些等待進(jìn)程之一來產(chǎn)生個(gè)事件又只能由這些等待進(jìn)程之一來產(chǎn)生 P0 P1wait(S);wait(Q);wait(Q);wait(S); signal(S);signal(Q);signal(Q)signal(S);n饑餓：無限期阻塞。饑餓：無限期阻塞。如果對于信號量鏈表按如果對于信號量鏈表按LIFO順序來操作。順序來操作。經(jīng)典進(jìn)程同步問題經(jīng)典進(jìn)程同步問題生產(chǎn)者生產(chǎn)者消費(fèi)者問題消費(fèi)者問題讀者讀者寫者問題寫者問題哲學(xué)家進(jìn)餐問題哲學(xué)家進(jìn)餐問

30、題1. 生產(chǎn)者消費(fèi)者問題生產(chǎn)者消費(fèi)者問題(the producer-consumer problem)問題描述：若干進(jìn)程通過有限的共享緩沖區(qū)交換數(shù)據(jù)。問題描述：若干進(jìn)程通過有限的共享緩沖區(qū)交換數(shù)據(jù)。其中，其中，生產(chǎn)者生產(chǎn)者進(jìn)程不斷寫入，而進(jìn)程不斷寫入，而消費(fèi)者消費(fèi)者進(jìn)程不斷進(jìn)程不斷讀出；共享緩沖區(qū)共有讀出；共享緩沖區(qū)共有N個(gè)；任何時(shí)刻只能有一個(gè)進(jìn)個(gè)；任何時(shí)刻只能有一個(gè)進(jìn)程可對共享緩沖區(qū)進(jìn)行操作。程可對共享緩沖區(qū)進(jìn)行操作。共享緩沖區(qū)共享緩沖區(qū)生產(chǎn)指針生產(chǎn)指針消費(fèi)指針消費(fèi)指針Producer 1Producer 2.Producer MConsumer 1Consumer 2.Consumer N

31、滿滿空空指針移動方向指針移動方向環(huán)形緩沖區(qū)10K-1in(in+1)mod kout(out+1)mod k問題分析問題分析生產(chǎn)者活動：生產(chǎn)者活動： 消費(fèi)者活動：消費(fèi)者活動： do do 加工一件物品加工一件物品 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 消耗這件物品消耗這件物品 while(1) while(1)資源：箱子（同種組合）資源：箱子（同種組合） 資源：物品（同種組合）資源：物品（同種組合） semaphore empty; semaphore full; empty.value=k; full.value=0;放前：放前：P（empty） 取前：取前：P（full）放后

32、：放后：V（full） 取后：取后：V（empty）同步同步生產(chǎn)者活動：生產(chǎn)者活動： 消費(fèi)者活動：消費(fèi)者活動： do do 加工一件物品加工一件物品 P(full) P(empty) 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(empty) V(full) 消耗這件物品消耗這件物品 while(1) while(1)對對buffer和和in,out的操作互斥：的操作互斥： semaphore mutex=1互斥互斥生產(chǎn)者活動：生產(chǎn)者活動： 消費(fèi)者活動：消費(fèi)者活動： do do 加工一件物品加工一件物品 P(full) P(empty) P(mutex) P(mutex) 箱中取一物

33、品箱中取一物品 物品放入箱中物品放入箱中 V(mutex) V(mutex) V(empty) V(full) 消耗這件物品消耗這件物品 while(1) while(1)程序程序共享數(shù)據(jù)共享數(shù)據(jù) item bufferk,item; semaphore empty=k; semaphore full=0; semaphore mutex=1; int in=0; int out=0;程序程序Fork(producer,0);Fork(producer,m-1);Fork(consumer,0);Fork(coonsuer,n-1); Process producer do produce a

34、 item P(empty); P(mutex); bufferin:=item; in:=(in+1)mod k; V(mutex); V(full) while(1);Process consumer do P(full); P(mutex); temp:=bufferout; out:=(out+1)mod k; V(mutex); V(empty); consume temp; while(1);2. 讀者寫者問題讀者寫者問題(the readers-writers problem)n問題描述：對共享資源的讀寫操作，任一時(shí)刻問題描述：對共享資源的讀寫操作，任一時(shí)刻“寫者寫者”最多只允許

35、一個(gè)，而最多只允許一個(gè)，而“讀者讀者”則允許則允許多個(gè)多個(gè)“讀寫讀寫”互斥，互斥，“寫寫寫寫”互斥，互斥，讀讀讀讀允允許許n讀者優(yōu)先讀者優(yōu)先除非一個(gè)作者已進(jìn)入臨界區(qū)，否則沒有讀者等待除非一個(gè)作者已進(jìn)入臨界區(qū)，否則沒有讀者等待n寫者優(yōu)先寫者優(yōu)先如果有一個(gè)作者等待進(jìn)入臨界區(qū)，那么就沒有新的如果有一個(gè)作者等待進(jìn)入臨界區(qū)，那么就沒有新的讀者進(jìn)入臨界區(qū)讀者進(jìn)入臨界區(qū)n采用信號量機(jī)采用信號量機(jī)制制n共享數(shù)據(jù)共享數(shù)據(jù) semaphore mutex,wrt;semaphore mutex,wrt; int readcount; int readcount;wrt表表示示允許寫允許寫，初值是，初值是1。rea

36、dcountreadcount表表示示“正在讀正在讀”的進(jìn)程數(shù)，初值的進(jìn)程數(shù)，初值是是0；mutex表示表示對對readcount的互斥操作，初值的互斥操作，初值是是1。讀者寫者問題：讀者優(yōu)先讀者寫者問題：讀者優(yōu)先wait(mutex); readcount+; if (readcount = 1) wait(wrt);signal(mutex); reading is performedwait(mutex); readcount-; if (readcount = 0) signal(wrt);signal(mutex):Readerwait(wrt); writing is perfor

37、medsignal(wrt);Writer讀者寫者問題：讀者優(yōu)先讀者寫者問題：讀者優(yōu)先讀者寫者問題：寫者優(yōu)先讀者寫者問題：寫者優(yōu)先n共享變量共享變量: : semaphoresemaphorewSem = 1, / Semaphore for all writerswSem = 1, / Semaphore for all writersrSem = 1, / Semaphore for first readerrSem = 1, / Semaphore for first readerrsSem = 1, / Semaphore for other readersrsSem = 1, / S

38、emaphore for other readersmutexW = 1, mutexW = 1, mutexR = 1;mutexR = 1;int readCount = 0, writeCount = 0;int readCount = 0, writeCount = 0;讀者寫者問題：寫者優(yōu)先讀者寫者問題：寫者優(yōu)先Wwhile(1)while(1) wait(mutexW);wait(mutexW); if (+writeCount = 1) wait(rSem); if (+writeCount = 1) wait(rSem);signal(mutexW);signal(mutexW

39、);wait(wSem);wait(wSem); WRITEUNITWRITEUNIT; ;signal(wSem);signal(wSem);wait(mutexW);wait(mutexW); if (-writeCount = 0) signal(rSem); if (-writeCount = 0) signal(rSem);signal(mutexW);signal(mutexW); 讀者寫者問題：寫者優(yōu)先讀者寫者問題：寫者優(yōu)先Rwhile(1)while(1) wait(rsSem); wait(rsSem); wait(rSem); wait(rSem); wait(mutexR

40、); wait(mutexR); if (+readCount=1)wait(wSem); if (+readCount=1)wait(wSem); signal(mutexR); signal(mutexR); signal(rSem); signal(rSem); signal(rsSem); signal(rsSem); READUNITREADUNIT; ; wait(mutexR); wait(mutexR); if (-readCount = 0) signal(wSem); if (-readCount = 0) signal(wSem); signal(mutexR); sig

41、nal(mutexR); 讀者寫者問題：寫者優(yōu)先讀者寫者問題：寫者優(yōu)先n系統(tǒng)中只有讀者系統(tǒng)中只有讀者設(shè)置設(shè)置wSem ，沒有等待隊(duì)列沒有等待隊(duì)列n系統(tǒng)中只有寫者系統(tǒng)中只有寫者設(shè)置設(shè)置wSem 和和rSem; 其他寫者在其他寫者在wSem等待隊(duì)列等待隊(duì)列中中n同時(shí)有讀者和寫者，而讀者在先同時(shí)有讀者和寫者，而讀者在先讀者設(shè)置讀者設(shè)置wSem;寫者設(shè)置寫者設(shè)置rSem所有寫者都在所有寫者都在wSem的等待隊(duì)列中，一個(gè)讀者在的等待隊(duì)列中，一個(gè)讀者在rSem隊(duì)列中，而其它讀者都在隊(duì)列中，而其它讀者都在rsSem隊(duì)列中隊(duì)列中 n同時(shí)有讀者和寫者，而寫者在先同時(shí)有讀者和寫者，而寫者在先讀者設(shè)置讀者設(shè)置wSe

42、m和和rSem所有寫者都在所有寫者都在wSem的等待隊(duì)列中，一個(gè)讀者在的等待隊(duì)列中，一個(gè)讀者在rSem隊(duì)列中，而其它讀者都在隊(duì)列中，而其它讀者都在rsSem隊(duì)列中隊(duì)列中 3. 哲學(xué)家進(jìn)餐問題哲學(xué)家進(jìn)餐問題(the dining philosophers problem)n問題描述：（由問題描述：（由Dijkstra首先提出并解決）首先提出并解決）5個(gè)個(gè)哲學(xué)家哲學(xué)家圍繞一張圍繞一張圓桌圓桌而坐，桌子上放著而坐，桌子上放著5支筷支筷子子，每兩個(gè)哲學(xué)家之間放一支；哲學(xué)家的動作，每兩個(gè)哲學(xué)家之間放一支；哲學(xué)家的動作包括包括思考思考和和進(jìn)餐進(jìn)餐，進(jìn)餐時(shí)需要同時(shí)拿起他左邊，進(jìn)餐時(shí)需要同時(shí)拿起他左邊和右邊的

43、兩支筷子，思考時(shí)則同時(shí)將兩支筷子和右邊的兩支筷子，思考時(shí)則同時(shí)將兩支筷子放回原處。放回原處。n如何保證哲學(xué)家們的動作有序進(jìn)行？如：不出如何保證哲學(xué)家們的動作有序進(jìn)行？如：不出現(xiàn)相鄰者同時(shí)要求進(jìn)餐；不出現(xiàn)有人永遠(yuǎn)拿不現(xiàn)相鄰者同時(shí)要求進(jìn)餐；不出現(xiàn)有人永遠(yuǎn)拿不到筷子到筷子哲學(xué)家進(jìn)餐問題哲學(xué)家進(jìn)餐問題Roomph0ph4ph3ph2ph1f0f4f3f2f1死鎖預(yù)防策略死鎖預(yù)防策略死鎖解決方法：同時(shí)申請左、右兩把叉子（預(yù)先分配）。哲學(xué)家狀態(tài)描述（增加了hungry狀態(tài)）：State: Array0.4Of (thinking,hungry,eating);等待隊(duì)列設(shè)置（每個(gè)哲學(xué)家一個(gè)隊(duì)列）：Self:

44、 Array0.4Of semaphore; (initial value is 0);就餐條件測試就餐條件測試測試I號哲學(xué)家是否具備進(jìn)食條件：Procedure test(I:0.4) If (stateI=hungry) and (state(I-1)mod 5eating) and (state(I+1)mod 5eating) Then begin stateI:=eating; V(selfI) endRemark: 自測試不需要stateI=hungry, 但測試左鄰右舍需要此條件。未考慮互斥問題未考慮互斥問題 I號哲學(xué)家活動：1. Repeat2. 思考3. stateI:=hu

45、ngry;4. test(I);5. P(selfI);6. 取左叉，取右叉；7. 進(jìn)食8. 放左叉，放右叉；9. stateI:=thinking;10 test(I-1)mod 5);11. test(I+1)mod 5)12. Until false;共享變量：state;臨界區(qū)域：3-4, 9-11Var mutex:semaphore;考慮互斥問題考慮互斥問題I號哲學(xué)家活動：1. Repeat2. 思考3. P(mutex);4. stateI:=hungry;5. test(I);6. V(mutex); 7. P(selfI);8. 取左叉，取右叉；9. 進(jìn)食10. 放左叉，放右

46、叉；11. P(mutex);12. stateI:=thinking;13 test(I-1)mod 5);14. test(I+1)mod 5);15. V(mutex)16. Until false;問題問題餓死情況： 某哲學(xué)家左右鄰居至少有一個(gè)處于eating狀態(tài)。程序程序Program dining_philosophersvar state:array0.4of (thinking,hungry,eating); self:array0.4of semaphore; mutex:semaphore;procedure test(I:0.4)begin if (stateI=hung

47、ry)and (state(I-1)mod 5eating) and(state(I+1)mod 5eating) then begin stateI:=eating; V(selfI) endend;程序程序(Cont.)Procedure philosopher(I:0.4)begin cycle thinking P(mutex); stateI:=hungry; test(I); V(mutex); P(selfI); pick_up_fork(I);pick_up_fork(I+1)mod 5); Eating;put_down_fork(I);put_down_fork(I+1)m

48、od 5); P(mutex); stateI:=thinking; test(I-1)mod 5); test(I+1)mod 5); V(mutex); endend程序程序(Cont.)begin for I:=0 to 4 do begin stateI:=thinking; selfI.value:=0 end; mutex.value:=1; cobegin ph0: philosopher(0); . Ph4: philosopher(4); coendend.管程管程(monitor)n信號量機(jī)制功能強(qiáng)大，但使用時(shí)對信號量的操信號量機(jī)制功能強(qiáng)大，但使用時(shí)對信號量的操作分散，而且

49、難以控制，讀寫和維護(hù)都很困難作分散，而且難以控制，讀寫和維護(hù)都很困難 n1973年，年，Hoare和和Hanson所提出了一種集中式所提出了一種集中式同步進(jìn)程同步進(jìn)程管程。其基本思想是將共享變量管程。其基本思想是將共享變量和對它們的操作集中在一個(gè)模塊中，操作系統(tǒng)和對它們的操作集中在一個(gè)模塊中，操作系統(tǒng)或并發(fā)程序就由這樣的模塊構(gòu)成。這樣模塊之或并發(fā)程序就由這樣的模塊構(gòu)成。這樣模塊之間聯(lián)系清晰，便于維護(hù)和修改，易于保證正確間聯(lián)系清晰，便于維護(hù)和修改，易于保證正確性性n定義：管程是關(guān)于共享資源的數(shù)據(jù)結(jié)構(gòu)及一組定義：管程是關(guān)于共享資源的數(shù)據(jù)結(jié)構(gòu)及一組針對該資源的操作過程所構(gòu)成的軟件模塊。針對該資源的操作過程所構(gòu)成的軟件模塊。管程的組成管程的組成n名稱：為每個(gè)共享資源設(shè)立一個(gè)管程名稱：為每個(gè)共享資源設(shè)立一個(gè)管程n數(shù)據(jù)結(jié)構(gòu)說明：一組局部于管程的控制變量數(shù)據(jù)結(jié)構(gòu)說明