操作系統(tǒng)-進(jìn)程互斥與同步

并發(fā)：互斥與同步1本章教學(xué)目標(biāo)理解進(jìn)程的并發(fā)性帶來的問題理解什么是臨界區(qū)管理掌握臨界區(qū)管理的軟、硬件方法掌握信號量及PV操作解決互斥與同步問題掌握管程的概念及用法掌握進(jìn)程間通信的方法2進(jìn)程的順序性一個進(jìn)程在順序處理器上的執(zhí)行是嚴(yán)格按序的，一個進(jìn)程只有當(dāng)一個操作結(jié)束后，才能開始后繼操作順序程序設(shè)計是把一個程序設(shè)計成一個順序執(zhí)行的程序模塊，順序的含義不但指一個程序模塊內(nèi)部，也指兩個程序模塊之間。3順序程序設(shè)計特點

程序執(zhí)行的順序性程序環(huán)境的封閉性程序執(zhí)行結(jié)果的確定性計算過程的可再現(xiàn)性4進(jìn)程的并發(fā)性(1)進(jìn)程執(zhí)行的并發(fā)性：一組進(jìn)程的執(zhí)行在時間上是重疊的。并發(fā)性舉例：有兩個進(jìn)程A(a1、a2、a3)和B(b1、b2、b3)并發(fā)執(zhí)行。a1,a2,a3,b1,b2,b3a1,b1,b2,a2,a3,b3從宏觀上看，并發(fā)性反映一個時間段中幾個進(jìn)程都在同一處理器上，處于運行還未運行結(jié)束狀態(tài)。從微觀上看，任一時刻僅有一個進(jìn)程在處理器上運行。5進(jìn)程的并發(fā)性(2)并發(fā)的實質(zhì)是一個處理器在幾個進(jìn)程之間的多路復(fù)用，并發(fā)是對有限的物理資源強(qiáng)制行使多用戶共享，消除計算機(jī)部件之間的互等現(xiàn)象，以提高系統(tǒng)資源利用率。6進(jìn)程的并發(fā)性(3)單處理機(jī)系統(tǒng)中，多道程序設(shè)計使得不同的進(jìn)程交錯執(zhí)行多處理機(jī)系統(tǒng)中，不同的進(jìn)程可以同時執(zhí)行。進(jìn)程執(zhí)行的速度不可預(yù)測，依賴于其它進(jìn)程的行為、操作系統(tǒng)處理中斷的方式以及操作系統(tǒng)的調(diào)度策略。并發(fā)性使程序的執(zhí)行失去了封閉性、順序性、確定性和可再現(xiàn)性78并發(fā)程序設(shè)計while(true){input;process;output;}while(true){input;send}while(true){receive;process;send;}while(true){receive;output；}程序1(i)程序2(p)程序3(o)9o1p1o2i2i1p2…i1p3p1i3p2o1i4i2o2i5p4o3(a)串行工作ipo(b)并行工作t1t5t4t3t210并發(fā)帶來的問題并發(fā)進(jìn)程可能是無關(guān)的，也可能是交互的無關(guān)的并發(fā)進(jìn)程是指它們分別在不同的變量集合上操作交互的并發(fā)進(jìn)程共享某些變量，之間具有制約關(guān)系，有可能產(chǎn)生時間相關(guān)的錯誤。11無關(guān)的并發(fā)進(jìn)程無關(guān)的并發(fā)進(jìn)程一組并發(fā)進(jìn)程分別在不同的變量集合上操作一個進(jìn)程的執(zhí)行與其他并發(fā)進(jìn)程的進(jìn)展無關(guān)。并發(fā)進(jìn)程的無關(guān)性是進(jìn)程的執(zhí)行與時間無關(guān)的一個充分條件，又稱為Bernstein條件。

12Bernstein條件設(shè)R(pi)={a1,a2,…,an}，表示程序pi在執(zhí)行期間引用的變量集；W(pi)={b1,b2,…,bn}，表示程序pi在執(zhí)行期間改變的變量集；兩個進(jìn)程的程序p1和p2滿足Bernstein條件是指引用變量集與改變變量集交集之并為空集，即：

(R(p1)∩W(p2))∪(R(p2)∩W(p1))∪(W(p1)∩W(p2))={}13Bernstein條件舉例例如，有如下四條語句：S1:a:=x+yS2:b:=z+1S3:c:=a–bS4:w:=c+1于是有：R(S1)={x,y},R(S2)={z}，R(S3)={a,b}，R(S4)={c}；W(S1)={a},W(S2)=，W(S3)={c}，W(S4)={w}。S1和S2可并發(fā)執(zhí)行，滿足Bernstein條件。14并發(fā)程序帶來的好處單處理器系統(tǒng)上，可有效利用資源，讓處理器和I/O設(shè)備，I/O設(shè)備和I/O設(shè)備同時工作，充分發(fā)揮機(jī)器部件的并行能力；硬件能并行工作僅有了提高效率的可能性，硬部件并行性的實現(xiàn)需要軟件技術(shù)去利用和發(fā)揮，這種軟件技術(shù)就是并發(fā)程序設(shè)計。在多處理器系統(tǒng)上，可讓進(jìn)程在不同處理器上物理地并行工作并發(fā)程序設(shè)計是多道程序設(shè)計的基礎(chǔ)，多道程序的實質(zhì)就是把并發(fā)程序設(shè)計引入到系統(tǒng)中。15與時間有關(guān)的錯誤并發(fā)進(jìn)程使得進(jìn)程的執(zhí)行不可預(yù)測，甚至無法再現(xiàn)。進(jìn)程間的相互影響和制約導(dǎo)致對資源的共享充滿了危險，各種與時間有關(guān)的錯誤就可能出現(xiàn)結(jié)果不唯一結(jié)果與進(jìn)程執(zhí)行的速度相關(guān)永遠(yuǎn)等待進(jìn)程相互等待產(chǎn)生死鎖，或進(jìn)程一直得不到資源產(chǎn)生餓死現(xiàn)象16結(jié)果不唯一（例1）生產(chǎn)者while(true){/*produceaniteminnextProduced;*/while(counter==BUFFER_SIZE);/*donothing*/buffer[in]=nextProduced;in=(in+1)%BUFFER_SIZE;

counter++;}消費者while(true){while(counter==0);/*donothing*/nextConsumed=buffer[out];out=(out+1)%BUFFER_SIZE;

counter--;/*consumetheitermnextConsumed*/}register2=counter;register2=register2-1;counter=register2;register1=counter;register1=register1+1;counter=register1;17T0:生產(chǎn)者執(zhí)行register1=counter;[register1=5]T1:生產(chǎn)者執(zhí)行register1=register1+1;[register1=6]T2:消費者執(zhí)行register2=counter;[register2=5]T3:消費者執(zhí)行register2=register2-1;[register2=4]T4:生產(chǎn)者執(zhí)行counter=register1;[counter=6]T5:消費者執(zhí)行counter=register2;[counter=4]T0:生產(chǎn)者執(zhí)行register1=counter;[register1=5]T1:生產(chǎn)者執(zhí)行register1=register1+1;[register1=6]T2:消費者執(zhí)行register2=counter;[register2=5]T3:消費者執(zhí)行register2=register2-1;[register2=4]T4:消費者執(zhí)行counter=register2;[counter=4]T5:生產(chǎn)者執(zhí)行counter=register1;[counter=6]執(zhí)行序列1執(zhí)行序列2T0:生產(chǎn)者執(zhí)行register1=counter;[register1=5]T1:生產(chǎn)者執(zhí)行register1=register1+1;[register1=6]T2:生產(chǎn)者執(zhí)行counter=register1;[counter=6]T3:消費者執(zhí)行register2=counter;[register2=6]T4:消費者執(zhí)行register2=register2-1;[register2=5]T5:消費者執(zhí)行counter=register2;[counter=5]執(zhí)行序列318結(jié)果不唯一（例2）P1:a=a+1;b=b+1;P2:b=2*b;a=2*a;線性執(zhí)行a=2b=2;b=4;a=4;并發(fā)執(zhí)行a=a+1;//a=2;b=2*b;//b=2;b=b+1;//b=3;a=2*a;//a=4;a=b=1;a!=ba==b19結(jié)果不唯一（例3）voidT1(){//按旅客訂票要求找到AjintX1=Aj；if(X1>=1){X1--;Aj=X1;//輸出一張票；}else{//輸出票已售完}voidT2(){//按旅客訂票要求找到AjintX2=Aj；if(X2>=1){X2--;Aj=X2;//輸出一張票；}else{//輸出票已售完}20永遠(yuǎn)等待intX=memory;voidborrow(intB){while(B>X){進(jìn)程進(jìn)入等待主存資源隊列;}X=X-B;修改主存分配表，進(jìn)程獲得主存資源；}voidreturn(intB){X=X+B;修改主存分配表；釋放等待主存資源的進(jìn)程；}可能永遠(yuǎn)不會被喚醒21進(jìn)程的交互競爭多個進(jìn)程之間并不知道其他進(jìn)程的存在，競爭共享硬設(shè)備、存儲器、處理器和文件資源等兩個控制問題死鎖問題饑餓問題操作系統(tǒng)應(yīng)該提供支持，合理分配資源，解決資源的競爭問題進(jìn)程的互斥訪問是解決進(jìn)程間競爭資源的手段進(jìn)程互斥是指若干進(jìn)程因相互爭奪獨占型資源而產(chǎn)生的競爭制約關(guān)系協(xié)作一組進(jìn)程之間相互知道對方的存在，協(xié)作完成同一任務(wù)。進(jìn)程的同步是解決進(jìn)程間協(xié)作關(guān)系的手段。進(jìn)程同步是指為完成共同任務(wù)的并發(fā)進(jìn)程基于某個條件來協(xié)調(diào)其活動，因為需要在某些位置上排定執(zhí)行的先后次序而等待、傳遞信號或消息所產(chǎn)生的協(xié)作制約關(guān)系進(jìn)程互斥關(guān)系是一種特殊的進(jìn)程同步關(guān)系。22臨界區(qū)管理互斥與臨界區(qū)實現(xiàn)臨界區(qū)管理的幾種嘗試實現(xiàn)臨界區(qū)管理的軟件方法實現(xiàn)臨界區(qū)管理的硬件設(shè)施23互斥與臨界區(qū)(1)并發(fā)進(jìn)程中與共享變量有關(guān)的程序段叫“臨界區(qū)”，共享變量代表的資源叫“臨界資源”。與同一變量有關(guān)的臨界區(qū)分散在各進(jìn)程的程序段中，而各進(jìn)程的執(zhí)行速度不可預(yù)知。如果保證進(jìn)程在臨界區(qū)執(zhí)行時，不讓另一個進(jìn)程進(jìn)入臨界區(qū)，即各進(jìn)程對共享變量的訪問是互斥的，就不會造成與時間有關(guān)的錯誤。24互斥與臨界區(qū)(2)一次至多一個進(jìn)程能夠進(jìn)入臨界區(qū)內(nèi)執(zhí)行；如果已有進(jìn)程在臨界區(qū)，其他試圖進(jìn)入的進(jìn)程應(yīng)等待；進(jìn)入臨界區(qū)內(nèi)的進(jìn)程應(yīng)在有限時間內(nèi)退出，以便讓等待進(jìn)程中的一個進(jìn)入。臨界區(qū)調(diào)度原則：

互斥使用、有空讓進(jìn)，忙則等待、有限等待，擇一而入，算法可行；25Booleaninside1=false;Booleaninside2=false;ProcessP1(){while(inside2);inside1=true;/*criticalsection*/inside1=false;/*remaindersection*/}ProcessP2(){while(inside1);inside2=true;/*criticalsection*/inside2=false;/*remaindersection*/}123臨界區(qū)管理的嘗試同時進(jìn)入！26Booleaninside1=false;Booleaninside2=false;ProcessP1(){inside1=true;while(inside2);/*criticalsection*/inside1=false;/*remaindersection*/}ProcessP2(){inside2=true;while(inside1);/*criticalsection*/inside2=false;/*remaindersection*/}12Blocked!Blocked!3臨界區(qū)管理的嘗試同時阻塞!27Peterson方法intturn;//表示現(xiàn)在輪到誰進(jìn)入booleanflag[2];////表示進(jìn)程希望進(jìn)入臨界區(qū)的意愿flag[0]=flag[1]=false;

ProcessP0(){flag[0]=true;turn=1;while(flag[1]&&turn==1);/*criticalsection*/

flag[0]=false;

/*remaindersection;*/}

ProcessP1(){flag[1]=true;turn=0;while(flag[0]&&turn==0);/*criticalsection*/

flag[1]=false;

/*remaindersection;*/}Q:如何將該算法擴(kuò)展到n個進(jìn)程？28Peterson方法的正確性互斥性若P0，P1同時進(jìn)入臨界區(qū)，則意味flag[0]=flag[1]=true;但turn只可能取值0或1，因此不可能同時進(jìn)入臨界區(qū)有空讓進(jìn)若P1不準(zhǔn)備竟?fàn)幣R界區(qū)資源，則flag[1]=false,因此，P0可以進(jìn)入臨界區(qū)有限等待若P0希望進(jìn)入臨界區(qū)而被阻塞，則表明turn=1,且flag[1]=true;此時，P1在臨界區(qū).當(dāng)P1執(zhí)行完以后，將設(shè)置flag[1]=false,若此時P0想進(jìn)入臨界區(qū)，則可以進(jìn)入如果P1執(zhí)行完flag[1]=false后，在P0被調(diào)度之前，P1又想進(jìn)入臨界區(qū)，則P1將執(zhí)行flag[1]=true,turn=0，此時P1將被阻塞，而P0將得以進(jìn)入臨界區(qū)因此，進(jìn)程最多等待另一個進(jìn)程執(zhí)行完臨界區(qū)代碼一次即可進(jìn)入臨界區(qū)29解決臨界區(qū)問題的硬件方法關(guān)中斷test_and_set指令Swap指令30關(guān)中斷關(guān)中斷使得當(dāng)前執(zhí)行的進(jìn)程不會被打斷，從而不會發(fā)生進(jìn)程切換關(guān)中斷時間過長會影響系統(tǒng)效率不適用多處理器系統(tǒng)。在一個CPU上關(guān)中斷，并不能防止其他處理器上也執(zhí)行相同的臨界區(qū)代碼while(true){/*disableinterrupts*/;/*criticalsection*/;/*enableinterrupts*/;/*remainder*/;}31test_and_setbooleantest_and_set(booleanx){if(x==true){x=false;returntrue;}elsereturnfalse;}此指令為原子操作，不可分割！32booleanlock=true;//資源初始可用ProcessPi(){while(true){/**若資源可用，則將其設(shè)為不可用，并返回true,從而通過測試進(jìn)入臨界區(qū)；若資源不可用，則lock為false,返回false，進(jìn)程忙等；*/while(test_and_set(lock)==false);/*criticalsection*/;lock=true;/*remainder*/;}}33test_and_set解決臨界區(qū)管理將臨界區(qū)與一個布爾變量lock相關(guān)聯(lián)lock代表臨界資源的狀態(tài)，可以看成一把鎖，lock為true/false表示臨界資源可用/不可用初始值為true,如有進(jìn)程要進(jìn)入臨界區(qū)，則對lock進(jìn)行測試和設(shè)置指令如果已有進(jìn)程在臨界區(qū)，則test_and_set返回false,將被阻止進(jìn)入臨界區(qū)如果沒有進(jìn)程在臨界區(qū)，則test_and_set返回true,同時將lock設(shè)為false,以阻止其它進(jìn)程進(jìn)入臨界區(qū)當(dāng)進(jìn)程離開臨界區(qū)時，將lock設(shè)置為true,表示臨界資源可用能實現(xiàn)進(jìn)程互斥訪問臨界區(qū)，但是可能會出現(xiàn)進(jìn)程餓死的情況如何避免進(jìn)程餓死？34booleanwaiting[n];booleanlock;lock=true;//表明臨界資源初始可用；waiting[0…n-1]=false;//當(dāng)前沒有進(jìn)程在等待Pi(){do{waiting[i]=true;//進(jìn)程i等待進(jìn)入臨界區(qū)；booleankey=false;while(waiting[i]&&!key)//若當(dāng)前l(fā)ock為false,表明有進(jìn)程在臨界區(qū)，則key為false;key=test_and_set(lock);//若當(dāng)前l(fā)ock為true,表明無進(jìn)程在臨界區(qū)，則key為true;waiting[i]=false;/*criticalsection*/j=(i+1)%n;while((j!=i)&&!waiting[j])//找到i后面第一個在等待進(jìn)入臨界區(qū)的進(jìn)程jj=(j+1)%n;if(j==i)//若無進(jìn)程，則臨界區(qū)資源標(biāo)為可用；lock=true;elsewaiting[j]=false;/*否則，并不將臨界區(qū)資源標(biāo)識為可用，而是將進(jìn)程j等待標(biāo)識置為false,使得進(jìn)程j可以進(jìn)入臨界區(qū)，而其它進(jìn)程則無法進(jìn)入；*//*remaindersection*/}while(true);}同時實現(xiàn)了互斥和有限等待35對換指令voidswap(booleana,booleanb){booleantemp;temp=b;b=a;a=temp;}例如，Pentium中的XCHG指令36booleanlock=false;//表示資源可用ProcessPi(){while(true){booleankeyi=true;

/**若資源可用，則lock為false,執(zhí)行swap后keyi為false,通過測試，進(jìn)入臨界區(qū)；若資源不可用，則lock=true,執(zhí)行swap后keyi仍然為true,進(jìn)程忙等；*/doswap(keyi,lock)while(keyi);/*criticalsection*/;lock=false;/*remainder*/;}}37為每個臨界區(qū)設(shè)置鎖變量lock，lock為false表示無進(jìn)程在臨界區(qū)內(nèi)當(dāng)進(jìn)程進(jìn)入臨界區(qū)時，lock設(shè)置為true,keyi變?yōu)閒alse,因此進(jìn)程得以通過測試，進(jìn)入臨界區(qū)當(dāng)另一個進(jìn)程希望進(jìn)入臨界區(qū)時,swap(keyi,lock)的結(jié)果是keyi=lock=true,因此，進(jìn)程被阻止進(jìn)入臨界區(qū)當(dāng)進(jìn)程退出臨界區(qū)時，將lock設(shè)為false,從而被阻止進(jìn)程得以進(jìn)入臨界區(qū)同樣，能實現(xiàn)進(jìn)程互斥訪問臨界區(qū)，但是可能會出現(xiàn)進(jìn)程餓死的情況38基于機(jī)器指令方法的優(yōu)缺點優(yōu)點適用于任意數(shù)目的進(jìn)程，適用于單處理機(jī)系統(tǒng)和多處理機(jī)系統(tǒng),只要共享內(nèi)存即可；簡單，易于驗證；可以用于支持多個臨界區(qū)，為每個臨界區(qū)定義一個變量即可缺點采用了忙等方式，浪費CPU資源可能會導(dǎo)致饑餓不滿足有限等待可能會導(dǎo)致死鎖例如，一個低優(yōu)先級的進(jìn)程P1先進(jìn)入臨界區(qū)，然后被處理器中斷，執(zhí)行高優(yōu)先級進(jìn)程P2，則P2處于忙等，P1因優(yōu)先級低而不會被處理器調(diào)度，從而產(chǎn)生死鎖。實際上，這個例子中臨界區(qū)是一個資源，而CPU是另一個資源。只能應(yīng)用于進(jìn)程競爭，不能解決進(jìn)程協(xié)作39信號量與PV操作1965年E.W.Dijkstra提出了新的同步工具--信號量和P、V操作。40EdsgerW.Dijkstra1930.5.11—2002.8.61972年獲得圖靈獎成就：提出“goto有害論”;提出信號量和PV原語;解決了有趣的“哲學(xué)家聚餐”問題;最短路徑算法(SPF)和銀行家算法的創(chuàng)造者;第一個Algol60編譯器的設(shè)計者和實現(xiàn)者;THE操作系統(tǒng)的設(shè)計者和開發(fā)者與D.E.Knuth(TheArtofComputerProgramming的作者)并稱為我們這個時代最偉大的計算機(jī)科學(xué)家的人41信號量與PV操作信號量：一種軟件資源原語：內(nèi)核中執(zhí)行時不可被中斷的過程P操作原語和V操作原語一個進(jìn)程在某一特殊點上被迫停止執(zhí)行直到接收到一個對應(yīng)的特殊變量值，這種特殊變量就是信號量(semaphore)，復(fù)雜的進(jìn)程合作需求都可以通過適當(dāng)?shù)男盘柦Y(jié)構(gòu)得到滿足。42信號量操作系統(tǒng)中，信號量表示物理資源的實體，它是一個與隊列有關(guān)的整型變量。實現(xiàn)時，信號量是一種記錄型數(shù)據(jù)結(jié)構(gòu)，有兩個分量：一個是信號量的值，另一個是信號量隊列的隊列指針。信號量的值(-2)

信號量隊列指針43信號量記錄型信號量的定義typedefstruct{intvalue;structprocess*list;}semaphore;其中，value為一個整型變量，系統(tǒng)初始化時為其賦值；list是等待使用此類資源的進(jìn)程隊列的頭指針，初始狀態(tài)為空隊列。44信號量的操作對信號量的操作包括兩個原子操作,P操作和V操作，也稱為wait()操作和signal()操作voidP(semaphores){s.value--;if(s.value<0){placethisprocessins.list;blockthisprocess;}}voidV(semaphores){s.value++;if(s.value<=0){removeaprocessPfroms.list;placeprocessPonreadylist;}}45PV操作的原子性保證PV操作本身的原子性是典型的臨界區(qū)問題，即任何時候，只有一個進(jìn)程能進(jìn)入P操作或V操作函數(shù)的內(nèi)部可以采用之前介紹過的軟件方法或硬件方法保證P操作或V操作本身的原子性Dekker’s算法Peterson’s算法關(guān)中斷(僅限于單處理器)Test_and_set指令swap指令…46信號量的含義若信號量s.value為正值，則此值等于在封鎖進(jìn)程之前對信號量s可施行的P操作數(shù)，也就是s所代表的實際可用的物理資源數(shù)；若信號量s.value為負(fù)值，則其絕對值等于登記排列在s.list中的等待進(jìn)程個數(shù)，即恰好等于對信號量s實施P操作而被阻塞并進(jìn)入信號量s的等待隊列的進(jìn)程數(shù)；P操作通常意味著請求一個資源，V操作意味著釋放一個資源。在一定條件下，P操作代表掛起進(jìn)程的操作，而V操作代表喚醒被掛起進(jìn)程的操作。47semWait=PsemSignal=V48二元信號量若信號量s的value取值只能為0或1，則稱s為二元信號量，其P,V操作定義如下：voidP(semaphores){if(s.value==1)s.value=0;else{placethisprocessins.list;blockthisprocess;}}voidV(semaphores){if(s.listisempty)s.value=1;else{removeaprocessPfroms.list;placeprocessPonreadylist;}}49信號量實現(xiàn)互斥semaphormutex;//定義一個信號量，代表臨界區(qū)鎖mutex.value=1;//初始值設(shè)為1ProcessPi(){P(mutex);//進(jìn)入臨界區(qū)之前執(zhí)行P(mutex)申請鎖資源/*criticalsection*/;V(mutex);//退出臨界區(qū)時執(zhí)行V(mutex)釋放鎖資源并喚//醒可能等待進(jìn)程；/*remaindersection*/;}50哲學(xué)家進(jìn)餐問題問題描述：5位哲學(xué)家圍在一張圓桌旁，桌子中央有一盤通心粉，每人面前有一只空盤子，每兩人之間有一只筷子；每位哲學(xué)家思考，饑餓，然后吃通心面；為了吃面，哲學(xué)家必須獲得兩把叉子，且每人只能直接從緊鄰自己的左邊或右邊去取叉子51哲學(xué)家進(jìn)餐問題每把叉子都必須互斥使用，因此，應(yīng)為每把叉子設(shè)置互斥信號量fork[i](i=0,1,2,3,4),其初始值均為1當(dāng)一位哲學(xué)家吃通心面之前必須執(zhí)行兩個P操作，獲得自己左邊和右邊的兩把叉子在吃完通心面后執(zhí)行兩個V操作，放下兩把叉子。52semaphorfork[5];for(inti=0;i<5;i++)fork[i]=1;Processphilosopher_i(){//i=0,1,2,3,4;while(true){think();P(fork[i]);//嘗試獲得左邊叉子P(fork[(i+1)%5]);//嘗試獲得右邊叉子eat();V(fork[i]);//釋放左邊叉子V(fork[(i+1)%5]);//釋放右手叉子}}注：若5個哲學(xué)家同時拿起自己左手邊（或右手邊)的筷子，則所有哲學(xué)家將處于等待狀態(tài)，出現(xiàn)死鎖。死鎖的避免將在后續(xù)章節(jié)介紹。利用互斥信號量解決哲學(xué)家進(jìn)餐問題53哲學(xué)家進(jìn)餐中死鎖的一種解決方案不允許哲學(xué)家拿起一把叉子等待另一把叉子要么兩把叉子一起獲得，要么一把都不持有54Processphilosopher_i(){//i=0,1,2,3,4;while(true){think();P(mutex);if(state[i]==0&&state[(i+1)%5]==0){//兩把叉子同時空閑state[i]=1;state[(i+1)%5]=1;P(fork[i]);//嘗試獲得左邊叉子P(fork[(i+1)%5]);//嘗試獲得右邊叉子}V(mutex);eat();P(mutex);state[i]=0;state[(i+1)%5]=0;V(fork[i]);//釋放左邊叉子V(fork[(i+1)%5]);//釋放右手叉子V(mutex);}}Semaphorfork[5],mutex;intstate[5];/*筷子狀態(tài)，0表示 /*空閑,1表示被占用*/for(inti=0;i<5;i++){fork[i]=1;state=0;}mutex=1;缺乏對一把叉子都未獲得的進(jìn)程阻塞功能55Processphilosopher_i(){//i=0,1,2,3,4;while(true){think();P(mutex);if(state[i]==0&&state[(i+1)%5]==0){state[i]=1;state[(i+1)%5]=1;P(fork[i]);//嘗試獲得左邊叉子P(fork[(i+1)%5]);//嘗試獲得右邊叉子}eat();state[i]=0;state[(i+1)%5]=0;V(fork[i]);//釋放左邊叉子V(fork[(i+1)%5]);//釋放右手叉子V(mutex);}}Semaphorfork[5],mutex;intstate[5];for(inti=0;i<5;i++){fork[i]=1;state=0;}mutex=1;降低了并發(fā)性同一時間僅有一個哲學(xué)家能吃通心面56#defineTHINKING0#defineHUNGRY1#defineEATING2semaphors[5];//用于阻塞哲學(xué)家的信號量semaphoremutex=1;intstate[5];//哲學(xué)家的狀態(tài)for(inti=0;i<5;i++){state[i]=THINKING;s[i]=0;}57voidtake_fork(inti){P(mutex);state[i]=HUNGRY;test(i);V(mutex);P(s[i]);/*若狀態(tài)不為EATING,則此處進(jìn)程將阻塞自己；變?yōu)镋ATING有兩種可能:（1）自己執(zhí)行test()時，已經(jīng)獲得兩把叉子，此時執(zhí)行了V(s[i])，再執(zhí)行P(s[i])不會阻塞;（2）鄰居放下叉子時發(fā)現(xiàn)本進(jìn)程等待的兩把叉子空，且處于饑餓狀態(tài)，因此決定將叉子都分配給該進(jìn)程；*/}voidput_fork(inti){P(mutex);state[i]=THINKING;//當(dāng)前進(jìn)程不再eat,表示歸還兩把叉子test((i+1)%5);//檢測右邊鄰居test((i+4)%5);//檢測左邊鄰居V(mutex);}voidtest(inti){if(state[i]==HUNGRY&&state[(i+1)%5]!=EATING&&state[(i+4)%5]!=EATING){//若左右手的鄰居均不在吃，則同時獲得兩把叉子；state[i]=EATING;//stae[i]=EATING表示同時獲得兩把叉子V(s[i]);}}58Philosopher_i{

while(true){think();take_fork(i);eat();put_fork(i);}}59信號量實現(xiàn)同步生產(chǎn)者-消費者問題讀者-寫者問題理發(fā)師問題60生產(chǎn)者—消費者問題有限的大小為n的緩存空間，組織成環(huán)狀p個生產(chǎn)者和q個消費者每個生產(chǎn)者每次生產(chǎn)一件產(chǎn)品并放入緩存，如果緩存已滿，則等待消費者消費后再放入；每個消費者每次消費一個產(chǎn)品，如果緩存為空，則等待生產(chǎn)者放入產(chǎn)品61生產(chǎn)者-消費者問題分析互斥要求禁止兩個以上生產(chǎn)者同時將產(chǎn)品放入同一個位置禁止兩個以上的消費者同時消費同一個產(chǎn)品同步要求僅當(dāng)緩沖區(qū)產(chǎn)品數(shù)大于0時，消費者才能消費產(chǎn)品，否則消費者必須等待；當(dāng)生產(chǎn)者生產(chǎn)了一個產(chǎn)品時，將可用產(chǎn)品數(shù)加1，如果有消費者等待，則喚醒一個等待產(chǎn)品的消費者；僅當(dāng)空閑緩沖區(qū)數(shù)大于0時，生產(chǎn)者可以放入產(chǎn)品，否則生產(chǎn)者必須等待；當(dāng)消費者消費了一個產(chǎn)品后，將空閑緩沖區(qū)數(shù)加1，如果有消費者等待，則喚醒一個等待空閑緩沖區(qū)的生產(chǎn)者；62itemB[n];Semaphoreempty;/*可用的空緩沖區(qū)個數(shù)*/Semaphorefull;/*可用的產(chǎn)品數(shù)*/Semaphoremutex;/*互斥信號量*/empty=n;full=0;mutex=1;intin=0;out=0;/*in為放入緩沖區(qū)指針，out為取出緩沖區(qū)指針*/Processproducer_i(){while(true){itemproduct=produce();P(empty);P(mutex);B[in]=product;in=(in+1)%n;V(mutex);V(full);}}Processconsumer_i(){while(true){P(full);P(mutex);Itemproduct=B[out];out=(out+1)%n;V(mutex);V(empty);consume(product);}}如果將P操作的順序交換，會出現(xiàn)什么情況？P(mutex);P(empty);當(dāng)emtpy=0,即緩沖滿了時，可能會出現(xiàn)死鎖！63itemB[n];Semaphoreempty;/*可用的空緩沖區(qū)個數(shù)*/Semaphorefull;/*可用的產(chǎn)品數(shù)*/Semaphorepmutex,cmutex;/*互斥信號量*/empty=n;full=0;pmutex=1;cmutex=1;intin=0;out=0;/*in為放入緩沖區(qū)指針，out為取出緩沖區(qū)指針*/Processproducer_i(){while(true){itemproduct=produce();P(empty);P(pmutex);B[in]=product;in=(in+1)%n;V(pmutex);V(full);}}Processconsumer_i(){while(true){P(full);P(cmutex);Itemproduct=B[out];out=(out+1)%n;V(cmutex);V(empty);consume(product);}}僅當(dāng)in==out時，producer和consumer才共享buffer數(shù)據(jù)，但此時，要么empty=0,要么full=0;因此，該方法可行。在生產(chǎn)者放產(chǎn)品的同時，消費者可以消費產(chǎn)品，而若采用同一mutex則不行64讀者-寫者問題有兩組并發(fā)進(jìn)程，讀者和寫者，共享文件F，要求允許多個讀者同時對文件執(zhí)行讀操作；只允許一個寫者對文件執(zhí)行寫操作；任何寫者在完成寫操作之前不允許其他讀者或?qū)懻吖ぷ?；寫者在?zhí)行寫操作前，應(yīng)讓已有的寫者和讀者全部退出。65讀者寫者問題—讀者優(yōu)先當(dāng)存在讀者時，寫者將被延遲且只要有一個讀者活躍，隨后而來的讀者都將被允許訪問文件可能造成寫者的饑餓66讀者寫者問題—讀者優(yōu)先互斥需求禁止多個寫者同時對文件進(jìn)行寫操作禁止讀者和寫者同時工作引入寫鎖寫者必須獲得寫鎖才能進(jìn)行寫操作；第一個讀者也必須獲得寫鎖才能進(jìn)行讀操作，后續(xù)讀者無需獲得寫鎖可以直接讀；同步需求當(dāng)最后一個讀者結(jié)束后，釋放寫鎖，如果存在等待寫鎖的寫者，則喚醒之；當(dāng)寫者結(jié)束后，釋放寫鎖，如果存在等待寫鎖的用戶（其它寫者或第一個讀者），則喚醒之；67Intreadcount=0;/*讀進(jìn)程計數(shù)器*/Semaphorewritelock,mutex;/*writelock為寫鎖，mutex為互斥信號量*/Writelock=1;mutex=1;Processreader_i(){P(mutex);/*保證不同的讀者互斥訪問readcount共享變量；*/readcount++;/*讀進(jìn)程個數(shù)加1；*/if(readcount==1)/*當(dāng)只有一個讀進(jìn)程時，獲得寫鎖，阻塞寫嘗試*/P(writelock);V(mutex);/*釋放互斥信號量*/read();/*如為第一個讀進(jìn)程，則已經(jīng)獲得寫鎖，否則，表明已有讀進(jìn)程在讀，可以進(jìn)行讀操作*/P(mutex);/*保證不同的讀者互斥訪問readcount共享變量;*/readcount--;/*讀進(jìn)程個數(shù)減1*/if(readcount==0)/*若讀進(jìn)程個數(shù)為0，則可以喚醒寫進(jìn)程*/V(writelock);V(mutex);/*釋放互斥信號量*/}68Processwriter_i(){P(writelock);/*嘗試獲得寫鎖;*/write();/*寫操作*/V(writelock);/*釋放寫鎖*/}69mutex隊列writelock隊列當(dāng)系統(tǒng)中已有進(jìn)程在讀或?qū)憰r，寫進(jìn)程阻塞在writelock隊列當(dāng)系統(tǒng)中已有進(jìn)程在讀時，后續(xù)讀進(jìn)程不會被阻塞；當(dāng)系統(tǒng)中已有進(jìn)程在寫時，第一個讀進(jìn)程阻塞在writelock隊列，后續(xù)讀進(jìn)程阻塞在mutex隊列；70讀者寫者問題—寫者優(yōu)先當(dāng)一個寫進(jìn)程聲明想進(jìn)行寫操作時，不允許新的讀者訪問文件，即所有之后發(fā)生的讀請求將在該寫操作之后進(jìn)行當(dāng)后續(xù)寫者到達(dá)時，只要系統(tǒng)中有寫者在工作，則后續(xù)寫者也將優(yōu)先于系統(tǒng)中已到達(dá)的讀者被服務(wù)71Intreadcount=0;/*讀者計數(shù)器*/intwritecount=0;/*寫者計數(shù)器*/semaphorewritelock=1;/*寫鎖*/semaphorerdcntmutex=1;/*讀者計數(shù)器的互斥信號量*/semaphorewrtcntmutex=1;/*寫者計數(shù)器的互斥信號量*/semaphorequeue=1;

/*排隊信號量，用于實現(xiàn)寫者優(yōu)先*/72Processwriter_i(){P(wrtcntmutex);/*獲取寫者計數(shù)器的互斥信號量*/if(writecount==0)P(queue);/*若為第一個寫者，則嘗試獲取排隊信號量，從而后續(xù)讀者進(jìn)程將被阻塞在queue隊列，而后續(xù)寫者將被允許進(jìn)入*/writecount++;/*寫者計數(shù)器加1*/V(wrtcntmutex);/*釋放寫者計數(shù)器互斥信號量*/P(writelock);/*獲得寫鎖，當(dāng)存在讀者時等待現(xiàn)有讀者完成；當(dāng)存在寫者時，等待寫者完成；未獲得寫鎖的寫者將被阻塞在該信號量隊列；*//*write();*/V(writelock);/*釋放寫鎖*/P(wrtcntmutex);/*獲得寫者計數(shù)器互斥信號量*/writecount--;/*寫者計數(shù)器減1*/if(writecount==0)V(queue);/*如果不存在寫者，則從queue等待隊列中釋放一個讀者*/V(wrtcntmutex);/*釋放寫計數(shù)器互斥信號量*/}73Processreader_i(){P(queue);/*嘗試獲得排隊信號量，若已有寫者，則讀者將被阻塞在該信號量*/P(rcdcntmutex);/*獲取讀計數(shù)器互斥信號量*/readcount++;/*讀者計數(shù)器加1*/if(readcount==1)P(writelock);/*若為第一個讀者，則獲取寫鎖，以防止后續(xù)寫者和讀者同時工作；*/V(rcdcntmutex);/*釋放讀者計數(shù)器互斥信號量*/V(queue);/*釋放queue信號量，按先來先到的方式選擇queue信號量上等待的讀者或?qū)懻?//*read();*/P(rcdcntmutex);/*獲取讀者計數(shù)器互斥信號量*/readcount--;/*讀者計數(shù)器減1*/if(readcount==0)V(writelock);/*若為最后一個讀者，則釋放寫鎖*/V(rcdcntmutex);/*釋放讀者計數(shù)器互斥信號量*/}74queue隊列writelock隊列（1）當(dāng)系統(tǒng)中存在寫者時，所有之后來的讀者都被阻塞在queue隊列；（2）當(dāng)讀者進(jìn)程先于寫者到達(dá)，若在開始讀之前寫者到達(dá)，則寫者被臨時阻塞在queue隊列（一旦讀者開始讀，則寫者將被移到writelock隊列）；(3)若在讀者開始讀之后寫者到達(dá)，則寫者被阻塞在writelock隊列（4）當(dāng)系統(tǒng)中已有進(jìn)程在寫時，所有的寫者進(jìn)程將阻塞在writelock隊列75理發(fā)師問題理發(fā)店里有一位理發(fā)師、一把理發(fā)椅和n把供等候理發(fā)的顧客休憩的椅子；如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺，當(dāng)有顧客到來時，他喚醒理發(fā)師；如果理發(fā)師正在理發(fā)時又有新的顧客到來，那么如果還有空椅子，顧客就坐下來等待，否則就離開理發(fā)店。76Semaphorecustomer=0；/*等候理發(fā)的顧客數(shù)，用于阻塞理發(fā)師進(jìn)程，初始值為0*/Semaphorebarbers=0;/*正在等候顧客的理發(fā)師數(shù)*/Semaphoremutex=1;/*互斥信號量*/intwaiting=0;/*等待理發(fā)的顧客坐的椅子數(shù)*/intCHAIR=N;/*為顧客準(zhǔn)備的椅子數(shù)*/77processbarber(){while(true){P(customers);/*判斷是否有顧客,若沒有則理發(fā)師等待*/P(mutex);/*若有顧客，獲取互斥信號量*/waiting--;/*等待人數(shù)減1*/V(barbers);/*準(zhǔn)備為顧客理發(fā),解除一個阻塞顧客*/V(mutex);/*釋放互斥信號量*/cut_hair();/*理發(fā)*/}}processcustomer(){P(mutex);/*獲取互斥信號量*/if(waiting<CHAIRS){/*若等待人數(shù)小于N*/waiting++;/*等待人數(shù)加1*/V(customers);/*喚醒理發(fā)師*/V(mutex);/*釋放互斥信號量*/P(barbers);/*若理發(fā)師忙，則等待;否則，申請并占用理發(fā)師資源*/get_haircut();/*占用理發(fā)師資源，可以理發(fā)*/}elseV(mutex);/*釋放互斥信號量,人滿，顧客離開*/}78Posix信號量信號量包含在頭文件<semaphore.h>中無名信號量可用于共享內(nèi)存情況，如各個線程之間的互斥與同步命名信號量通常用于不共享內(nèi)存的情況下，如不共享內(nèi)存的進(jìn)程之間的互斥與同步79Posix無名信號量初始化：intsem_init(sem_t*sem,intpshared,unsignedvalue);銷毀：Intsem_destroy(sem_t*sem);PV操作P操作：intsem_wait(sem_t*sem);V操作：intsem_post(sem_t*sem);80Posix命名信號量創(chuàng)建或打開一個命名信號量：sem_t*sem_open(constchar*name,intoflag);關(guān)閉命名信號量：intsem_close(sem_t*sem);關(guān)閉信號量并不能將信號量從系統(tǒng)中刪除刪除信號量：intsem_unlink(constchar*name);81管程信號量提供了實現(xiàn)進(jìn)程間互斥和協(xié)同的強(qiáng)有力工具。但是，信號量分散在程序各個地方，采用信號量編寫正確的程序難度較大。管程：把分散在各個進(jìn)程中的臨界區(qū)集中起來管理，并把共享資源用數(shù)據(jù)結(jié)構(gòu)抽象地表示出來.由于臨界區(qū)是訪問共享資源的代碼段，建立一個管程來管理到來的訪問。管程每次只讓一個進(jìn)程來訪，這樣既便于對共享資源進(jìn)行管理，又能實現(xiàn)互斥訪問。82管程的表示管程是軟件模塊，包括：局部于自己的共享變量一組用于訪問共享變量的過程條件變量提供進(jìn)程間互斥提供進(jìn)程同步83管程管程實現(xiàn)互斥通過防止對一個資源的并發(fā)訪問，達(dá)到實現(xiàn)臨界區(qū)的效果，提供互斥機(jī)制管程實現(xiàn)同步需要引入同步工具使得進(jìn)程在資源不能滿足而無法繼續(xù)運行時被阻塞，同時還需開放管程采用條件變量，讓等待的進(jìn)程臨時放棄管程控制權(quán)，然后在適當(dāng)時刻再嘗試檢測管程內(nèi)的狀態(tài)變化84條件變量條件變量是出現(xiàn)在管程內(nèi)的一種數(shù)據(jù)結(jié)構(gòu)，只有在管程中才能被訪問，它對管程內(nèi)的所有過程是全局的，只能通過兩個原語操作來控制它條件變量的原語操作cwait(x)在條件變量x上掛起調(diào)用進(jìn)程并釋放管程，直到另一個進(jìn)程在條件變量上執(zhí)行csignal(x)csignal(x)如果有其它進(jìn)程因?qū)l件變量x執(zhí)行cwait(x)而被掛起，便釋放其中的一個等待進(jìn)程；如果沒有進(jìn)程在等待，則csignal()操作沒有任何效果，即x變量的狀態(tài)沒有改變注：與信號量中的V操作有區(qū)別，V操作總是會改變信號量的狀態(tài)85關(guān)于csignal()假設(shè)進(jìn)程P執(zhí)行csignal(x)，且存在進(jìn)程Q等待條件變量x，則如果阻塞進(jìn)程Q被允許立即執(zhí)行，則P必須等待，否則，P、Q將同時訪問管程，違反了管程的互斥訪問性。但概念上講，P和Q都應(yīng)該可以繼續(xù)執(zhí)行兩種方案P等待，直至Q離開管程或因等待另一個條件變量而開放管程Q等待，直至P離開管程或因等待另一個條件變量而開放管程86等待獲取管程進(jìn)入權(quán)的進(jìn)程阻塞隊列在條件變量ci上等待的進(jìn)程隊列調(diào)用csignal()函數(shù)的進(jìn)程阻塞隊列87/*管程解決生產(chǎn)者-消費者問題*/monitorboundedbuffer{/*sharedvariables*/charbuffer[N];intnextin=0,nextout=0;intcount=0;/*conditionvariables*/

conditionnotfull,notempty;voidappend(charx){

if(count==N)cwait(notfull);/*若緩沖已滿，則阻塞自己，等待notfull條件產(chǎn)生*/buffer[nextin]=x;nextin=(nextin+1)%N;count++;

csignal(notempty);/*如有進(jìn)程等待notempty條件，則喚醒其中的一個*/}voidtake(char&x){

if(count==0)cwait(notempty);/*如果緩沖為空，則阻塞自己，等待notempty條件產(chǎn)生*/x=buffer[nextout];nextout=(nextout+1)%N;count--;

csignal(notfull);/*如果有進(jìn)程等待notfull條件，則喚醒其中的一個*/}}88processproducer(){charx;while(true){x=produce();bd.append(x);}}processconsumer(){charx;while(true){bd.take(x);consume(x);}}boundedbufferbd;89/*管程解決哲學(xué)家進(jìn)餐問題*/monitordp{enum{THINKING,HUNGRY,EATING}state[5];

conditionself[5];//用于阻塞哲學(xué)家ivoidpickup(inti){state[i]=HUNGRY;test(i);if(state[i]!=EATING)//state[i]變?yōu)镋ATING,表示其占用兩把叉子，否則一把都不占用；

cwait(self[i]);//一把叉子都不占用時，在自身條件變量上阻塞自己}voidputdown(inti){state[i]=THINKING;test((i+4)%5);//看鄰居節(jié)點是否具備EATING的條件；test((i+1)%5);}voidtest(inti){if((state[(i+4)%5]!=EATING)&&(state[i]==HUNGRY)&&(state[(i+1)%5]!=EATING)){state[i]=EATING;//當(dāng)i想拿起兩把叉子，且鄰居都沒有處于EATING狀態(tài)時，//拿起兩把叉子；

csignal(self[i]);//喚醒一個在self[i]條件變量等待的哲學(xué)家}}initialization_code(){for(inti=0;i<5;i++)state[i]=THINKING;}}90Philosophy_i(){while(true){think();dp.pickup(i);eat();dp.putdown(i);}}91Java中的管程互斥訪問synchronized關(guān)鍵詞java為每個對象都設(shè)置一個monitorMonitor確保了關(guān)聯(lián)對象中synchronized方法的互斥訪問，即同一個對象，同一時刻只有一個線程可以執(zhí)行其上的synchronized方法若是在同一個類的不同對象上執(zhí)行相同的synchronized方法，則可以并發(fā)執(zhí)行同步：wait()：開放管程，在給定對象上等待；notify()：在給定對象的等待隊列中喚醒一個線程；notifyAll()：喚醒給定對象等待隊列中的所有線程，所有被喚醒的線程競爭管程的擁有權(quán)，即從條件變量的等待隊列移到了管程入口的等待隊列。一旦獲得管程擁有權(quán)，從wait()操作之后開始執(zhí)行。只有在獲得管程對象所有權(quán)時，才能執(zhí)行wait(),signal(),signalAll()操作,否則會拋出IllegalMonitorStateException92classCounter{privateintcount=0;publicvoidincrement(){intn=count;count=n+1;}}如果兩個線程共享一個對象Countercounter,且都希望執(zhí)行counter.increment()方法，則會導(dǎo)致運行結(jié)果不唯一。Thread1Thread2Countcounter.increment();---0n=count;

//0---0---counter.increment();0---n=count;

//00---count=n+1;

//11count=n+1;//1---193classCounter{privateintcount=0;publicvoidsynchronizedincrement(){intn=count;count=n+1;}}Thread1Thread2Countcounter.increment();---0(acquiresthemonitor)---0n=count;

//0---0---counter.increment();0---(can'tacquiremonitor)0count=n+1;//1---(blocked)1(releasesthemonitor)---(blocked)1---(acquiresthemonitor)1---n=count;

//11---count=n+1;

//22---(releasesthemonitor)294classBuffer{privatechar[]buffer;privateintcount=0,in=0,out=0;Buffer(intsize){buffer=newchar[size];}publicsynchronizedvoidPut(charc){

while(count==buffer.length){//如果改為if會如何？

try{wait();}catch(InterruptedExceptione){}finally{}

}System.out.println("Producing"+c+"...");buffer[in]=c;in=(in+1)%buffer.length;count++;

notify();}publicsynchronizedcharGet(){

while(count==0){

try{wait();}catch(InterruptedExceptione){}finally{}}charc=buffer[out];out=(out+1)%buffer.length;count--;System.out.println("Consuming"+c+"...");

notify();returnc;}}基于Java的管程機(jī)制解決生產(chǎn)者-消費者問題如果while改為if,則考慮下述情形：假如count=n;則可能存在多個生產(chǎn)者阻塞在Buffer類對象上當(dāng)一個消費者消費了一個產(chǎn)品后，喚醒某個生產(chǎn)者該生產(chǎn)者將產(chǎn)品放入后，調(diào)用notify()操作，則會喚醒其它等待的生產(chǎn)者被喚醒的生產(chǎn)者從wait()調(diào)用后開始執(zhí)行，將覆蓋未消費產(chǎn)品！95importjava.util.*;classWidget{staticintseq=0;privateintid;publicWidget(){id=++seq;}publicintgetID(){returnid;}}notify()vsnotifyAll()96publicclassWidgetUserextendsThread{privateWidgetMakermaker;publicWidgetUser(Stringname,WidgetMakermaker){super(name);this.maker=maker;}publicvoidrun(){while(true){Widgetw=maker.waitForWidget();System.out.println(getName()+"gotawidget"+w.getID());}}publicstaticvoidmain(String[]args){WidgetMakermaker=newWidgetMaker();maker.start();newWidgetUser("Lenny",maker).start();newWidgetUser("Moe",maker).start();newWidgetUser("Curly",maker).start();}}classWidgetMakerextendsThread{List<Widget>finishedWidgets=newArrayList<Widget>();publicvoidrun(){try{while(true){Thread.sleep(5000);Widgetw=newWidget();synchronized(finishedWidgets){finishedWidgets.add(w);finishedWidgets.notify();/*whataboutfinishedWidgets.notifyAll()?*/}}}catch(InterruptedExceptione){}}publicWidgetwaitForWidget(){