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

復(fù)習(xí)1記錄型信號量及其wait、Signal操作意義；生產(chǎn)者--消費(fèi)者問題：信號量意義、初值生產(chǎn)者進(jìn)程中，兩個(gè)wait操作順序能否顛倒，為什么？什么情況下會(huì)產(chǎn)生死鎖現(xiàn)象？And型信號量機(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)程通信34用信號量實(shí)現(xiàn)進(jìn)程的同步---

生產(chǎn)者－消費(fèi)者問題我們把前面面的例子擴(kuò)充，假定緩沖區(qū)buffer是一個(gè)有界緩沖區(qū)，可存放n個(gè)數(shù)據(jù)，同時(shí)假定有n個(gè)CP進(jìn)程不斷地產(chǎn)生數(shù)據(jù)，并送buffer；有m個(gè)IOP進(jìn)程從緩沖區(qū)中取數(shù)據(jù)打印。在我們生活中有很多這樣的例子。44用信號量實(shí)現(xiàn)進(jìn)程的同步---

生產(chǎn)者－消費(fèi)者問題互斥關(guān)系分析任何時(shí)刻，只能有一個(gè)進(jìn)程在緩沖區(qū)中操作引入互斥信號量（mutex）信號量初值為1.如果變?yōu)?，表明已有進(jìn)程進(jìn)入臨界區(qū)；同步關(guān)系分析對于“生產(chǎn)者”而言，緩沖區(qū)滿則應(yīng)等待引入同步信號量“empty”，初值為n。為0表示緩沖區(qū)全滿對于“消費(fèi)者”而言，緩沖區(qū)空則應(yīng)等待引入同步信號量“full”，初值為0表示緩沖區(qū)全空54用信號量實(shí)現(xiàn)進(jìn)程的同步---

生產(chǎn)者－消費(fèi)者問題64用信號量實(shí)現(xiàn)進(jìn)程的同步---

生產(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)modn；輸出指針加1表示成out:=(out+1)modn。8在生產(chǎn)者進(jìn)程中使用一局部變量nextp，用于暫時(shí)存放每次剛生產(chǎn)出來的產(chǎn)品；而在消費(fèi)者進(jìn)程中，則使用一個(gè)局部變量nextc，用于存放每次要消費(fèi)的產(chǎn)品。9Varmutex，empty，full:semaphore:=1,n,0；

buffer:array[0，…，n-1]ofitem；

in，out:integer:=0，0；

begin

parbegin

proceducer:begin

repeatproduceranitemnextp；wait(empty)；wait(mutex)；

buffer(in):=nextp；

in:=(in+1)modn；

signal(mutex)；

signal(full)；

untilfalse；

end

consumer:begin

repeat

wait(full)；

wait(mutex)；

nextc:=buffer(out)；out:=(out+1)modn；

signal(mutex)；signal(empty)；consumertheiteminnextc；untilfalse；end

parend

end104用信號量實(shí)現(xiàn)進(jìn)程的同步---

生產(chǎn)者－消費(fèi)者問題總結(jié)思考1：mutex和empty兩個(gè)信號量之間有什么區(qū)別嗎？思考2：多信號量的操作順序有要求嗎？互斥信號量mutex：防止多個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)同步信號量empty和full：保證事件發(fā)生的順序緩沖區(qū)滿時(shí)，Producer停止運(yùn)行緩沖區(qū)空時(shí)，Consumer停止運(yùn)行概念差別——互斥與同步（并發(fā)的兩個(gè)要素）互斥：保護(hù)臨界區(qū)，防止多個(gè)進(jìn)程同時(shí)進(jì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同步/互斥信號量的使用方法互斥信號量必定成對出現(xiàn)：進(jìn)入臨界區(qū)——臨界區(qū)——退出臨界區(qū)同步信號量未必成對出現(xiàn)，依賴于同步關(guān)系的性質(zhì)同步信號量和互斥信號量的操作順序基本原則：互斥信號量永遠(yuǎn)緊鄰臨界區(qū):同步在前，互斥在后。132.4.2信號量集問題：一段處理代碼需要同時(shí)獲取兩個(gè)或多個(gè)臨界資源――可能死鎖：各進(jìn)程分別獲得部分臨界資源，然后等待其余的臨界資源，"各不相讓"解決方法：在一個(gè)wait原語中，將一段代碼同時(shí)需要的多個(gè)臨界資源，要么全部分配給它，要么一個(gè)都不分配。稱為Swait(SimultaneousWait)。在Swait時(shí)，各個(gè)信號量的次序并不重要，雖然會(huì)影響進(jìn)程歸入哪個(gè)阻塞隊(duì)列。由于是對資源全部分配或不分配，所以總有進(jìn)程獲得全部資源并在推進(jìn)之后釋放資源，因此不會(huì)死鎖。信號量集用于同時(shí)需要多個(gè)資源時(shí)的信號量操作；1.AND型信號量集AND型信號量集用于同時(shí)需要多種資源且每種占用一個(gè)時(shí)的信號量操作；14

Swait(S1,S2,…,Sn) //同時(shí)的P原語；

{

if(S1>=1&&S2>=1&&…&&Sn>=1){ //滿足資源要求時(shí)的處理；

for(i=1;i<=n;++i)--Si; //注：與wait的處理不同，這里是在確信可滿足

//資源要求時(shí)，才進(jìn)行減1操作；

}else{ //某些資源不夠時(shí)的處理；調(diào)用進(jìn)程進(jìn)入第一個(gè)小于1信號量的等待隊(duì)列Sj.queue;

阻塞調(diào)用進(jìn)程;將調(diào)用進(jìn)程的PC置為swait操作開頭

}}15

Ssignal(S1,S2,…,Sn){for(i=1;i<=n;++i){++Si; //釋放占用的資源；

for(eachprocessPwaitinginSi.queue)//檢查每種資源的等待隊(duì)列的所有進(jìn)程；

{

從等待隊(duì)列Si.queue中取出進(jìn)程P;

進(jìn)程P進(jìn)入就緒隊(duì)列;}}

}需要注意：原先處于阻塞狀態(tài)的進(jìn)程，被喚醒后，從何處開始執(zhí)行？與記錄型信號量機(jī)制有何不同？16生產(chǎn)者－消費(fèi)者問題

－AND型信號量機(jī)制若不愿意考慮wait操作的先后順序，也可用AND型信號量來實(shí)現(xiàn)。生產(chǎn)者進(jìn)程中：用Swait(empty,mutex)代替wait(empty)和wait(mutex),用Ssignal(mutex,full)代替signal(mutex)和signal(full)消費(fèi)者進(jìn)程中用Swait(full,mutex)代替wait(full)和wait(mutex),用Ssignal(mutex,empty)代替signal(mutex)和signal(empty)17producer:beginrepeatproduceaniteminnextp；Swait(empty，mutex)；buffer(in):=nextp；in:=(in+1)modn；Ssignal(mutex，full)；untilfalse；endconsumer:beginrepeatSwait(full，mutex)；Nextc:=buffer(out)；Out:=(out+1)modn；Ssignal(mutex，empty)；consumertheiteminnextc；untilfalse；end182.一般“信號量集”問題：一次需要N個(gè)某類臨界資源時(shí)，就要進(jìn)行N次wait操作－－低效又可能死鎖方法：在AND型信號量集的基礎(chǔ)上進(jìn)行擴(kuò)充：進(jìn)程對信號量Si的測試值為ti（用于信號量的判斷，即當(dāng)Si>=ti時(shí)，表示可用資源數(shù)量大于ti，才分配資源，否則便不予分配），占用值為di（用于信號量的增減，即分配資源時(shí)Si=Si–di釋放資源時(shí)Si=Si+di）Swait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,d1;...;Sn,dn);一般信號量集用于同時(shí)需要多種資源、每種占用的數(shù)目不同、且可分配的資源還存在一個(gè)臨界值時(shí)的處理；19

Swait(S1,S2,…,Sn) //P原語；

{while(TRUE){if(S1>=1&&S2>=1&&…&&Sn>=1){ //滿足資源要求時(shí)的處理；

for(i=1;i<=n;++i)--Si; //注：與wait的處理不同，這里是在確信可滿足

//資源要求時(shí)，才進(jìn)行減1操作；

break;}else{ //某些資源不夠時(shí)的處理；調(diào)用進(jìn)程進(jìn)入第一個(gè)小于1信號量的等待隊(duì)列Sj.L;

阻塞調(diào)用進(jìn)程;將調(diào)用進(jìn)程的PC置為swait操作開頭}}}20

Ssignal(S1,S2,…,Sn){for(i=1;i<=n;++i){++Si; //釋放占用的資源；

for(eachprocessPwaitinginSi.L)//檢查每種資源的等待隊(duì)列的所有進(jìn)程；

{

從等待隊(duì)列Si.L中取出進(jìn)程P;

進(jìn)程P進(jìn)入就緒隊(duì)列;}}}}需要注意：原先處于阻塞狀態(tài)的進(jìn)程，被喚醒后，從何處開始執(zhí)行？與記錄型信號量機(jī)制有何不同？21一般"信號量集"的幾種特定情況：Swait(S,d,d)表示每次申請d個(gè)資源，當(dāng)少于d個(gè)時(shí)，便不分配；Swait(S,1,1)表示互斥信號量；Swait(S,1,0)作為一個(gè)可控開關(guān)當(dāng)S>=1時(shí)，允許多個(gè)進(jìn)程進(jìn)入臨界區(qū)；當(dāng)S=0時(shí)，禁止任何進(jìn)程進(jìn)入臨界區(qū)；一般"信號量集"未必成對使用Swait和Ssignal：如：一起申請，但不一起釋放；222.讀者－寫者問題(thereaders-writersproblem)問題描述寫者向數(shù)據(jù)區(qū)放數(shù)據(jù)，讀者從數(shù)據(jù)區(qū)獲取數(shù)據(jù)多個(gè)讀者可同時(shí)讀取數(shù)據(jù)多個(gè)寫者不能同時(shí)寫數(shù)據(jù)讀者和寫者的控制策略變化多端23讀者－寫者問題的信號量解法互斥關(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）有寫者寫：新讀者等當(dāng)寫者進(jìn)程到來時(shí)，三種情況：1）無讀者、其他寫者：新寫者可以寫2）有讀者：新寫者等待3）有其它寫者：新寫者等待讀--寫互斥讀--寫互斥寫--寫互斥讀--寫互斥讀--寫互斥寫—寫互斥：互斥信號量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成為臨界資源，必須互斥訪問：增加互斥信號量Rmutex26采用信號量機(jī)制：兩種進(jìn)程：Reader、Writer兩個(gè)信號量Wmutex表示讀者和寫者之間互斥，初值是1。公共變量Readcount表示“正在讀”的進(jìn)程數(shù)，初值是0；Rmutex表示讀者對Readcount的互斥操作，初值是1。Readcount＝0時(shí)允許寫分析小結(jié)27wait(rmutex);Ifreadcount=0then wait(wmutex);Readcount:=readcount+1;signal(rmutex);……執(zhí)行讀取操作wait(rmutex);Readcount:=readcount-1ifreadcount=0then signal(wmutex);signal(rmutex);讀者-寫者問題讀者部分第一個(gè)讀者要阻塞所有后來的寫者最后一個(gè)讀者要喚醒所有阻塞的寫者28wait(wmutex);……執(zhí)行寫操作signal(wmutex);寫者部分29增加限制條件，即同時(shí)讀取的讀者數(shù)不能超過RNL,mx:=RN,1信號量集：Swait(S,d,t);Ssignal(S,d)S為信號量，d為需求量，t為下限值寫者：Swait(mx,1,1;L,RN,0);……執(zhí)行寫操作Ssignal(mx,1);讀者-寫者問題

一般"信號量集"機(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)餐問題

(thediningphilosophersproblem)問題描述：（由Dijkstra首先提出并解決）5個(gè)哲學(xué)家圍繞一張圓桌而坐，桌子上放著5支筷子，每兩個(gè)哲學(xué)家之間放一支；哲學(xué)家的動(dòng)作包括思考和進(jìn)餐，進(jìn)餐時(shí)需要同時(shí)拿起他左邊和右邊的兩支筷子，思考時(shí)則同時(shí)將兩支筷子放回原處。如何保證哲學(xué)家們的動(dòng)作有序進(jìn)行？如：不出現(xiàn)相鄰者同時(shí)要求進(jìn)餐；不出現(xiàn)有人永遠(yuǎn)拿不到筷子；31321.利用記錄型信號量機(jī)制解決2.利用AND型信號量機(jī)制解決2.4.2哲學(xué)家就餐問題33哲學(xué)家就餐問題問題分析：筷子是臨界資源：每根有多于一個(gè)哲學(xué)家要用，而且同時(shí)只能有一個(gè)哲學(xué)家使用5根筷子可以用5個(gè)信號量表示。形成信號量數(shù)組：varchopstick:array[0,…4]ofsemaphore；所有信號量初值為1，表示未被使用。34哲學(xué)家就餐問題—解決方法第i位哲學(xué)家的活動(dòng)描述為：Repeatwait(chopstick[i]);wait(chopstick[(i+1)mod5]);eat;signal(chopstick[i]);signal(chopstick[(i+1)mod5]);think;Untilfalse;parbeginphilosopher(0)；philosopher(1)；philosopher(2)；philosopher(3)；philosopher(4)；parend35不足之處及改進(jìn)方法可能產(chǎn)生死鎖：五位哲學(xué)家同時(shí)饑餓，各自拿起左邊的筷子時(shí)，會(huì)使得所有信號量的值為0，再試圖拿起右邊的筷子時(shí)，都將拿不到筷子。解決死鎖的方法：至多允許四個(gè)哲學(xué)家同時(shí)進(jìn)餐。僅當(dāng)哲學(xué)家的左右兩支筷子均可用時(shí)，才進(jìn)餐。（用AND信號量機(jī)制解決哲學(xué)家進(jìn)餐問題。）奇數(shù)號哲學(xué)家先拿左邊的筷子，偶數(shù)號哲學(xué)家先拿右邊的筷子。36AND型信號量機(jī)制解決哲學(xué)家就餐問題要求哲學(xué)家同時(shí)獲得兩根筷子，否則一根也不拿。varchopstick:array[0,…4]ofsemaphore:=(1,1,1,1,1);//第i位哲學(xué)家進(jìn)程：Repeatthink;Sswait(chopstick[(I+1)mod5]),chopstick[I]);Eats;Ssignal(chopstick[(I+1)mod5]),chopstick[I]);untilfalse;37思考：用其余兩種思路，怎樣解決哲學(xué)家就餐問題？3810.有一閱覽室，讀者進(jìn)入時(shí)必須先在一張登記表上進(jìn)行登記，該表為每一座位列一表目，包括座號和讀者姓名。讀者離開時(shí)要消掉登記信號，閱覽室中共有100個(gè)座位，請問：(1)為描述讀者的動(dòng)作，應(yīng)編寫幾個(gè)程序？設(shè)置幾個(gè)進(jìn)程？進(jìn)程與程序間的對應(yīng)關(guān)系如何？(2)用類Pascal語言和Wait,Signal操作寫出這些進(jìn)程間的同步算法。39答：(1)應(yīng)編寫1個(gè)程序；設(shè)置2個(gè)