進(jìn)程管理四經(jīng)典進(jìn)程同步問題

1、復(fù)習(xí)1記錄型信號(hào)量及其wait、Signal操作意義；生產(chǎn)者-消費(fèi)者問題：信號(hào)量意義、初值生產(chǎn)者進(jìn)程中，兩個(gè)wait操作順序能否顛倒，為什么？什么情況下會(huì)產(chǎn)生死鎖現(xiàn)象？And型信號(hào)量機(jī)制及其Swait、Ssignal操作意義2經(jīng)典進(jìn)程同步問題 生產(chǎn)者消費(fèi)者問題 有界緩沖區(qū)問題的建模 哲學(xué)家進(jìn)餐問題 多進(jìn)程同步問題的建模 讀者寫者問題 數(shù)據(jù)庫互斥訪問問題的建模 理發(fā)師睡覺問題 CS模式進(jìn)程同步問題的建模進(jìn)程通信進(jìn)程通信34 用信號(hào)量實(shí)現(xiàn)進(jìn)程的同步- 生產(chǎn)者消費(fèi)者問題生產(chǎn)者消費(fèi)者問題 我們把前面面的例子擴(kuò) 充 ， 假 定 緩 沖 區(qū)buffer是一個(gè)有界緩沖區(qū)，可存放n個(gè)數(shù)據(jù)，同時(shí)假定有n個(gè)CP進(jìn)

2、程不斷地產(chǎn)生數(shù)據(jù)，并送buffer；有m個(gè)IOP進(jìn)程從緩沖區(qū)中取數(shù)據(jù)打印。 在我們生活中有很多這樣的例子。44 用信號(hào)量實(shí)現(xiàn)進(jìn)程的同步- 生產(chǎn)者消費(fèi)者問題生產(chǎn)者消費(fèi)者問題 互斥關(guān)系分析 任何時(shí)刻，只能有一個(gè)進(jìn)程在緩沖區(qū)中操作 引入互斥信號(hào)量（mutex） 信號(hào)量初值為1. 如果變?yōu)?，表明已有進(jìn)程進(jìn)入臨界區(qū)； 同步關(guān)系分析 對(duì)于“生產(chǎn)者”而言，緩沖區(qū)滿則應(yīng)等待 引入同步信號(hào)量“empty”，初值為n。為0表示緩沖區(qū)全滿 對(duì)于“消費(fèi)者”而言，緩沖區(qū)空則應(yīng)等待 引入同步信號(hào)量“full”，初值為0表示緩沖區(qū)全空54 用信號(hào)量實(shí)現(xiàn)進(jìn)程的同步- 生產(chǎn)者消費(fèi)者問題生產(chǎn)者消費(fèi)者問題64 用信號(hào)量實(shí)現(xiàn)進(jìn)程的

3、同步- 生產(chǎn)者消費(fèi)者問題生產(chǎn)者消費(fèi)者問題7 我們可利用一個(gè)數(shù)組來表示上述的具有n個(gè)(0，1，n-1)緩沖區(qū)的緩沖池緩沖池。用輸入指針輸入指針in來指示下一個(gè)可投放產(chǎn)品的緩沖區(qū)，每當(dāng)生產(chǎn)者進(jìn)程生產(chǎn)并投放一個(gè)產(chǎn)品后，輸入指針加1；用一個(gè)輸出指針輸出指針out來指示下一個(gè)可從中獲取產(chǎn)品的緩沖區(qū)，每當(dāng)消費(fèi)者進(jìn)程取走一個(gè)產(chǎn)品后，輸出指針加1。由于這里的緩沖池是組織成循環(huán)緩沖的，故應(yīng)把輸入指針加1表示成 in:= (in+1)mod n； 輸出指針加1表示成out:= (out+1) mod n。8在生產(chǎn)者進(jìn)程中使用一局部變量nextp，用于暫時(shí)存放每次剛生產(chǎn)出來的產(chǎn)品；而在消費(fèi)者進(jìn)程中，則使用一個(gè)局部變

4、量nextc，用于存放每次要消費(fèi)的產(chǎn)品。 9Var mutex，empty，full: semaphore:=1,n,0；buffer:array0，n-1 of item；in，out: integer:=0，0；beginparbeginproceducer: beginrepeat producer an item nextp； wait(empty)； wait(mutex)；buffer(in):=nextp；in:=(in+1) mod n；signal(mutex)；signal(full)；until false； endconsumer: beginrepeatwait(fu

5、ll)；wait(mutex)；nextc:=buffer(out)；out:=(out+1) mod n；signal(mutex)；signal(empty)；consumer the item in nextc；until false；endparendend 104 用信號(hào)量實(shí)現(xiàn)進(jìn)程的同步- 生產(chǎn)者消費(fèi)者問題總結(jié)生產(chǎn)者消費(fèi)者問題總結(jié)mutex：防止多個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)：防止多個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)empty和和full：保證事件發(fā)生的順序：保證事件發(fā)生的順序緩沖區(qū)滿時(shí)，緩沖區(qū)滿時(shí)，Producer停止運(yùn)行停止運(yùn)行緩沖區(qū)空時(shí)，緩沖區(qū)空時(shí)，Consumer停止運(yùn)行停止運(yùn)行互斥：保護(hù)臨界區(qū)，

6、防止多個(gè)進(jìn)程同時(shí)進(jìn)入互斥：保護(hù)臨界區(qū)，防止多個(gè)進(jìn)程同時(shí)進(jìn)入同步：保證進(jìn)程運(yùn)行的順序合理同步：保證進(jìn)程運(yùn)行的順序合理思考 生產(chǎn)者進(jìn)程中，兩個(gè)wait操作的順序能否互換？ 生產(chǎn)者進(jìn)程先執(zhí)行wait(mutex),再執(zhí)行wait(empty), 何時(shí)會(huì)出錯(cuò)？ 消費(fèi)者進(jìn)程中，先wait(mutex)，再wait(full)何時(shí)會(huì)出錯(cuò)？11如果某種原因使得生產(chǎn)者進(jìn)程執(zhí)行了多次，而消費(fèi)者進(jìn)程一次也沒執(zhí)行，從而全部緩沖區(qū)都存滿新數(shù)據(jù)時(shí)，再執(zhí)行一次生產(chǎn)者進(jìn)程就會(huì)死鎖。如果某種原因使得消費(fèi)者進(jìn)程執(zhí)行了多次，而生產(chǎn)者進(jìn)程一次也沒執(zhí)行，從而全部緩沖區(qū)都為空時(shí)，再執(zhí)行一次消費(fèi)者進(jìn)程就會(huì)死鎖。12同步/互斥信號(hào)量的使用

7、方法 互斥信號(hào)量 必定成對(duì)出現(xiàn)必定成對(duì)出現(xiàn)：進(jìn)入臨界區(qū)臨界區(qū)退出臨界區(qū) 同步信號(hào)量 未必成對(duì)出現(xiàn)，依賴于同步關(guān)系的性質(zhì) 同步信號(hào)量和互斥信號(hào)量的操作順序 基本原則：互斥信號(hào)量永遠(yuǎn)緊鄰臨界區(qū):同步在前，同步在前，互斥在后互斥在后。132.4.2 信號(hào)量集 問題：一段處理代碼需要同時(shí)獲取兩個(gè)或多個(gè)臨界資源可能死鎖：各進(jìn)程分別獲得部分臨界資源，然后等待其余的臨界資源，各不相讓 解決方法：在一個(gè)wait原語中，將一段代碼同時(shí)需要的多個(gè)臨界資源，要么全部分配給它，要么一個(gè)都不分配。稱為Swait(Simultaneous Wait)。 在Swait時(shí)，各個(gè)信號(hào)量的次序并不重要，雖然會(huì)影響進(jìn)程歸入哪個(gè)阻塞

8、隊(duì)列。由于是對(duì)資源全部分配或不分配，所以總有進(jìn)程獲得全部資源并在推進(jìn)之后釋放資源，因此不會(huì)死鎖。信號(hào)量集用于同時(shí)需要多個(gè)資源時(shí)的信號(hào)量操作；1. AND型信號(hào)量集AND型信號(hào)量集用于同時(shí)需要多種資源且每種占用一個(gè)時(shí)的信號(hào)量操作；14 Swait(S1, S2, , Sn)/同時(shí)的同時(shí)的P原語；原語； if (S1 =1 & S2 = 1 & & Sn = 1) /滿足資源要求時(shí)的處理；滿足資源要求時(shí)的處理； for (i = 1; i = n; +i) -Si; /注：與注：與wait的處理不同，這里是在確信可滿足的處理不同，這里是在確信可滿足 /資源要求時(shí)，才進(jìn)行減資

9、源要求時(shí)，才進(jìn)行減1操作；操作； else /某些資源不夠時(shí)的處理；某些資源不夠時(shí)的處理； 調(diào)用進(jìn)程進(jìn)入第一個(gè)小于調(diào)用進(jìn)程進(jìn)入第一個(gè)小于1信號(hào)量的等待隊(duì)列信號(hào)量的等待隊(duì)列Sj.queue; 阻塞調(diào)用進(jìn)程阻塞調(diào)用進(jìn)程;將調(diào)用進(jìn)程的將調(diào)用進(jìn)程的PC置為置為swait操作開頭操作開頭 15 Ssignal(S1, S2, , Sn) for (i = 1; i = ti時(shí)，表示可用資源數(shù)量大于ti，才分配資源，否則便不予分配），占用值為di（用于信號(hào)量的增減，即 分配資源時(shí)Si = Si di 釋放資源時(shí)Si = Si + di） Swait(S1, t1, d1; .; Sn, tn, dn);

10、Ssignal(S1, d1; .; Sn, dn);一般信號(hào)量集用于同時(shí)需要多種資源、每種占用的數(shù)目不同、且可分配的資源還存在一個(gè)臨界值時(shí)的處理；19 Swait(S1, S2, , Sn)/P原語；原語； while (TRUE) if (S1 =1 & S2 = 1 & & Sn = 1) /滿足資源要求時(shí)的處理；滿足資源要求時(shí)的處理； for (i = 1; i = n; +i) -Si; /注：與注：與wait的處理不同，這里是在確信可滿足的處理不同，這里是在確信可滿足 /資源要求時(shí)，才進(jìn)行減資源要求時(shí)，才進(jìn)行減1操作；操作； break; else /某些資

11、源不夠時(shí)的處理；某些資源不夠時(shí)的處理； 調(diào)用進(jìn)程進(jìn)入第一個(gè)小于調(diào)用進(jìn)程進(jìn)入第一個(gè)小于1信號(hào)量的等待隊(duì)列信號(hào)量的等待隊(duì)列Sj.L; 阻塞調(diào)用進(jìn)程阻塞調(diào)用進(jìn)程;將調(diào)用進(jìn)程的將調(diào)用進(jìn)程的PC置為置為swait操作開頭操作開頭 20 Ssignal(S1, S2, , Sn) for (i = 1; i =1時(shí)，允許多個(gè)進(jìn)程進(jìn)入臨界區(qū)； 當(dāng)S=0時(shí)，禁止任何進(jìn)程進(jìn)入臨界區(qū)； 一般信號(hào)量集未必成對(duì)使用Swait和Ssignal：如：一起申請(qǐng)，但不一起釋放；222. 讀者寫者問題讀者寫者問題(the readers-writers problem) 問題描述 寫者向數(shù)據(jù)區(qū)放數(shù)據(jù)，讀者從數(shù)據(jù)區(qū)獲取數(shù)據(jù) 多個(gè)

12、讀者可同時(shí)讀取數(shù)據(jù) 多個(gè)寫者不能同時(shí)寫數(shù)據(jù) 讀者和寫者的控制策略變化多端23讀者寫者問題的信號(hào)量解法 互斥關(guān)系分析 讀者和寫者不能同時(shí)進(jìn)入共享數(shù)據(jù)區(qū) 多個(gè)寫者不能同時(shí)進(jìn)入共享數(shù)據(jù)區(qū) 多個(gè)讀者可以同時(shí)進(jìn)入共享數(shù)據(jù)區(qū) 同步關(guān)系分析 讀者進(jìn)入緩沖區(qū)，寫者必須等待 寫者進(jìn)入緩沖區(qū)，讀者必須等待 三種類型： 讀者優(yōu)先：一旦有讀者進(jìn)入，則后續(xù)讀者均可進(jìn)入 合理順序：讀者在先來的寫者之后 寫者優(yōu)先：只要有寫者等待，則后續(xù)讀者必須等待寫寫-寫互斥寫互斥讀讀-寫互斥寫互斥24 當(dāng)讀者進(jìn)程到來時(shí)，三種情況： 1）無讀者、寫者：新讀者可以讀 2）有寫者等待，但有其它讀者正在讀：新讀者也可以讀 3）有寫者寫：新讀者等

13、 當(dāng)寫者進(jìn)程到來時(shí)，三種情況： 1）無讀者、其他寫者：新寫者可以寫 2）有讀者：新寫者等待 3）有其它寫者：新寫者等待讀讀-寫互斥寫互斥讀讀-寫互斥寫互斥寫寫-寫互斥寫互斥讀讀-寫互斥寫互斥讀讀-寫互斥寫互斥寫寫寫互斥：寫互斥：互斥信號(hào)量互斥信號(hào)量Wmutex怎樣判斷有沒有讀者在讀？25增加一個(gè)公共變量Readcount，表示當(dāng)前有幾個(gè)讀者進(jìn)程在讀。新來一個(gè)讀者進(jìn)程，Readcount加1；撤銷一個(gè)讀者進(jìn)程，Readcount減1；第一個(gè)讀者：阻塞所有寫者進(jìn)程；允許其他讀者進(jìn)程執(zhí)行。最后一個(gè)讀者：喚醒可能的寫者進(jìn)程。Readcount成為臨界資源，必須互斥訪問：增加互斥信號(hào)量Rmutex26

14、采用信號(hào)量機(jī)制： 兩種進(jìn)程：Reader、Writer兩個(gè)信號(hào)量 Wmutex表示讀者和寫者之間互斥，初值是1。 公共變量Readcount表示“正在讀”的進(jìn)程數(shù)，初值是0； Rmutex表示讀者對(duì)Readcount的互斥操作，初值是1。Readcount0時(shí)允許寫分析小結(jié)27 wait(rmutex); If readcount=0 then wait(wmutex); Readcount:=readcount+1; signal(rmutex); 執(zhí)行讀取操作執(zhí)行讀取操作 wait(rmutex); Readcount:=readcount-1 if readcount=0 then si

15、gnal(wmutex); signal(rmutex);讀者-寫者問題讀者部分讀者部分第一個(gè)讀者要阻塞第一個(gè)讀者要阻塞所有后來的寫者所有后來的寫者最后一個(gè)讀者要喚最后一個(gè)讀者要喚醒所有阻塞的寫者醒所有阻塞的寫者28 wait(wmutex); 執(zhí)行寫操作執(zhí)行寫操作 signal(wmutex);寫者部分寫者部分29 增加限制條件，即同時(shí)讀取的讀者數(shù)不能超過RN L,mx:=RN,1 信號(hào)量集： Swait(S,d,t); Ssignal(S,d) S為信號(hào)量，d為需求量，t為下限值 寫者： Swait(mx,1,1;L,RN,0); 執(zhí)行寫操作 Ssignal(mx,1);讀者-寫者問題一般

16、信號(hào)量集機(jī)制 讀者： Swait(L,1,1); Swait(mx,1,0); 執(zhí)行讀取操作 Ssignal(L,1);If（L=1）L=L-1;If（mx=1）mx=mx;If（mx=1 & L=RN) mx=mx-1;L=L; 303. 哲學(xué)家進(jìn)餐問題(the dining philosophers problem) 問題描述：（由問題描述：（由Dijkstra首先提出并解決）首先提出并解決）5個(gè)個(gè)哲學(xué)家哲學(xué)家圍繞一張圍繞一張圓桌圓桌而坐，桌子上放著而坐，桌子上放著5支筷支筷子子，每兩個(gè)哲學(xué)家之間放一支；哲學(xué)家的動(dòng)作，每兩個(gè)哲學(xué)家之間放一支；哲學(xué)家的動(dòng)作包括包括思考思考和和進(jìn)餐進(jìn)餐

17、，進(jìn)餐時(shí)進(jìn)餐時(shí)需要同時(shí)拿起他左邊需要同時(shí)拿起他左邊和右邊的兩支筷子，和右邊的兩支筷子，思考時(shí)思考時(shí)則同時(shí)將兩支筷子則同時(shí)將兩支筷子放回原處。如何保證哲學(xué)家們的動(dòng)作有序進(jìn)行？放回原處。如何保證哲學(xué)家們的動(dòng)作有序進(jìn)行？如：不出現(xiàn)相鄰者同時(shí)要求進(jìn)餐；不出現(xiàn)有人如：不出現(xiàn)相鄰者同時(shí)要求進(jìn)餐；不出現(xiàn)有人永遠(yuǎn)拿不到筷子；永遠(yuǎn)拿不到筷子；3132 1.利用記錄型信號(hào)量機(jī)制解決 2.利用AND型信號(hào)量機(jī)制解決2.4.2哲學(xué)家就餐問題33哲學(xué)家就餐問題 問題分析： 筷子是臨界資源：每根有多于一個(gè)哲學(xué)家要用，而且同時(shí)只能有一個(gè)哲學(xué)家使用 5根筷子可以用5個(gè)信號(hào)量表示。形成信號(hào)量數(shù)組： var chopstick:

18、array0,4of semaphore； 所有信號(hào)量初值為1，表示未被使用。34哲學(xué)家就餐問題解決方法第第i位哲學(xué)家的活動(dòng)描述為：位哲學(xué)家的活動(dòng)描述為：Repeat wait(chopsticki); wait(chopstick(i+1)mod 5); eat; signal(chopsticki); signal(chopstick(i+1)mod 5); think;Until false;parbegin philosopher (0)；philosopher (1)；philosopher (2)；philosopher (3)；philosopher (4)；parend35不足

19、之處及改進(jìn)方法 可能產(chǎn)生死鎖： 五位哲學(xué)家同時(shí)饑餓，各自拿起左邊的筷子時(shí)，會(huì)使得所有信號(hào)量的值為0，再試圖拿起右邊的筷子時(shí)，都將拿不到筷子。 解決死鎖的方法解決死鎖的方法： 至多允許四個(gè)哲學(xué)家同時(shí)進(jìn)餐。至多允許四個(gè)哲學(xué)家同時(shí)進(jìn)餐。 僅當(dāng)哲學(xué)家的左右兩支筷子均可用時(shí)，才進(jìn)餐。（用僅當(dāng)哲學(xué)家的左右兩支筷子均可用時(shí)，才進(jìn)餐。（用AND信號(hào)量機(jī)制解決哲學(xué)家進(jìn)餐問題。）信號(hào)量機(jī)制解決哲學(xué)家進(jìn)餐問題。） 奇數(shù)號(hào)哲學(xué)家先拿左邊的筷子，偶數(shù)號(hào)哲學(xué)家先拿右奇數(shù)號(hào)哲學(xué)家先拿左邊的筷子，偶數(shù)號(hào)哲學(xué)家先拿右邊的筷子。邊的筷子。36AND型信號(hào)量機(jī)制解決哲學(xué)家就餐問題要求哲學(xué)家同時(shí)獲得兩根筷子，否則一根也不拿。var

20、chopstick:array0,4of semaphore:=(1,1,1,1,1);/第第i位哲學(xué)家進(jìn)程：位哲學(xué)家進(jìn)程：Repeat think; Sswait(chopstick(I+1)mod 5),chopstickI); Eats; Ssignal(chopstick(I+1)mod 5),chopstickI);until false;37 思考： 用其余兩種思路，怎樣解決哲學(xué)家就餐問題？3810. 有一閱覽室，讀者進(jìn)入時(shí)必須先在一張登記表上進(jìn)行登記，該表為每一座位列一表目，包括座號(hào)和讀者姓名。讀者離開時(shí)要消掉登記信號(hào)，閱覽室中共有100個(gè)座位，請(qǐng)問：(1) 為描述讀者的動(dòng)作，應(yīng)編寫幾個(gè)程序？設(shè)置幾個(gè)進(jìn)程？進(jìn)程與程序間的對(duì)應(yīng)關(guān)系如何？(2) 用類Pascal語言和Wait, Signal操作寫出這些進(jìn)程間的同步算法。39答：(1) 應(yīng)編寫1個(gè)程序；設(shè)置2個(gè)進(jìn)程；進(jìn)程與程序間的對(duì)應(yīng)關(guān)系是：多對(duì)多對(duì)1。(2) beginS1:=100 (有有100個(gè)座位個(gè)座位)S2:=0 (沒有閱讀者沒有閱讀者)mutex: =1c