復習1記錄型信號量及其wait、Signal操作意義；生產者--消費者問題：信號量意義、初值生產者進程中，兩個wait操作順序能否顛倒，為什么？什么情況下會產生死鎖現(xiàn)象？And型信號量機制及其Swait、Ssignal操作意義

2經典進程同步問題生產者－消費者問題有界緩沖區(qū)問題的建模哲學家進餐問題多進程同步問題的建模讀者－寫者問題數(shù)據庫互斥訪問問題的建模理發(fā)師睡覺問題CS模式進程同步問題的建模進程通信34用信號量實現(xiàn)進程的同步---

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

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

生產者－消費者問題64用信號量實現(xiàn)進程的同步---

生產者－消費者問題7我們可利用一個數(shù)組來表示上述的具有n個(0，1，…，n-1)緩沖區(qū)的緩沖池。用輸入指針in來指示下一個可投放產品的緩沖區(qū)，每當生產者進程生產并投放一個產品后，輸入指針加1；用一個輸出指針out來指示下一個可從中獲取產品的緩沖區(qū)，每當消費者進程取走一個產品后，輸出指針加1。由于這里的緩沖池是組織成循環(huán)緩沖的，故應把輸入指針加1表示成in:=(in+1)modn；輸出指針加1表示成out:=(out+1)modn。8在生產者進程中使用一局部變量nextp，用于暫時存放每次剛生產出來的產品；而在消費者進程中，則使用一個局部變量nextc，用于存放每次要消費的產品。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用信號量實現(xiàn)進程的同步---

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

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

{

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

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

//資源要求時，才進行減1操作；

}else{ //某些資源不夠時的處理；調用進程進入第一個小于1信號量的等待隊列Sj.queue;

阻塞調用進程;將調用進程的PC置為swait操作開頭

}}15

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

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

{

從等待隊列Si.queue中取出進程P;

進程P進入就緒隊列;}}

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

－AND型信號量機制若不愿意考慮wait操作的先后順序，也可用AND型信號量來實現(xiàn)。生產者進程中：用Swait(empty,mutex)代替wait(empty)和wait(mutex),用Ssignal(mutex,full)代替signal(mutex)和signal(full)消費者進程中用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個某類臨界資源時，就要進行N次wait操作－－低效又可能死鎖方法：在AND型信號量集的基礎上進行擴充：進程對信號量Si的測試值為ti（用于信號量的判斷，即當Si>=ti時，表示可用資源數(shù)量大于ti，才分配資源，否則便不予分配），占用值為di（用于信號量的增減，即分配資源時Si=Si–di釋放資源時Si=Si+di）Swait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,d1;...;Sn,dn);一般信號量集用于同時需要多種資源、每種占用的數(shù)目不同、且可分配的資源還存在一個臨界值時的處理；19

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

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

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

//資源要求時，才進行減1操作；

break;}else{ //某些資源不夠時的處理；調用進程進入第一個小于1信號量的等待隊列Sj.L;

阻塞調用進程;將調用進程的PC置為swait操作開頭}}}20

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

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

{

從等待隊列Si.L中取出進程P;

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

一般"信號量集"機制讀者：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.哲學家進餐問題

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