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

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

程序執(zhí)行的順序性程序環(huán)境的封閉性程序執(zhí)行結(jié)果的確定性計(jì)算過程的可再現(xiàn)性4進(jìn)程的并發(fā)性(1)進(jìn)程執(zhí)行的并發(fā)性：一組進(jìn)程的執(zhí)行在時(shí)間上是重疊的。并發(fā)性舉例：有兩個(gè)進(jìn)程A(a1、a2、a3)和B(b1、b2、b3)并發(fā)執(zhí)行。a1,a2,a3,b1,b2,b3a1,b1,b2,a2,a3,b3從宏觀上看，并發(fā)性反映一個(gè)時(shí)間段中幾個(gè)進(jìn)程都在同一處理器上，處于運(yùn)行還未運(yùn)行結(jié)束狀態(tài)。從微觀上看，任一時(shí)刻僅有一個(gè)進(jìn)程在處理器上運(yùn)行。5進(jìn)程的并發(fā)性(2)并發(fā)的實(shí)質(zhì)是一個(gè)處理器在幾個(gè)進(jìn)程之間的多路復(fù)用，并發(fā)是對(duì)有限的物理資源強(qiáng)制行使多用戶共享，消除計(jì)算機(jī)部件之間的互等現(xiàn)象，以提高系統(tǒng)資源利用率。6進(jìn)程的并發(fā)性(3)單處理機(jī)系統(tǒng)中，多道程序設(shè)計(jì)使得不同的進(jìn)程交錯(cuò)執(zhí)行多處理機(jī)系統(tǒng)中，不同的進(jìn)程可以同時(shí)執(zhí)行。進(jìn)程執(zhí)行的速度不可預(yù)測(cè)，依賴于其它進(jìn)程的行為、操作系統(tǒng)處理中斷的方式以及操作系統(tǒng)的調(diào)度策略。并發(fā)性使程序的執(zhí)行失去了封閉性、順序性、確定性和可再現(xiàn)性78并發(fā)程序設(shè)計(jì)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)生時(shí)間相關(guān)的錯(cuò)誤。11無關(guān)的并發(fā)進(jìn)程無關(guān)的并發(fā)進(jìn)程一組并發(fā)進(jìn)程分別在不同的變量集合上操作一個(gè)進(jìn)程的執(zhí)行與其他并發(fā)進(jìn)程的進(jìn)展無關(guān)。并發(fā)進(jìn)程的無關(guān)性是進(jìn)程的執(zhí)行與時(shí)間無關(guān)的一個(gè)充分條件，又稱為Bernstein條件。

12Bernstein條件設(shè)R(pi)={a1,a2,…,an}，表示程序pi在執(zhí)行期間引用的變量集；W(pi)={b1,b2,…,bn}，表示程序pi在執(zhí)行期間改變的變量集；兩個(gè)進(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è)備同時(shí)工作，充分發(fā)揮機(jī)器部件的并行能力；硬件能并行工作僅有了提高效率的可能性，硬部件并行性的實(shí)現(xiàn)需要軟件技術(shù)去利用和發(fā)揮，這種軟件技術(shù)就是并發(fā)程序設(shè)計(jì)。在多處理器系統(tǒng)上，可讓進(jìn)程在不同處理器上物理地并行工作并發(fā)程序設(shè)計(jì)是多道程序設(shè)計(jì)的基礎(chǔ)，多道程序的實(shí)質(zhì)就是把并發(fā)程序設(shè)計(jì)引入到系統(tǒng)中。15與時(shí)間有關(guān)的錯(cuò)誤并發(fā)進(jìn)程使得進(jìn)程的執(zhí)行不可預(yù)測(cè)，甚至無法再現(xiàn)。進(jìn)程間的相互影響和制約導(dǎo)致對(duì)資源的共享充滿了危險(xiǎn)，各種與時(shí)間有關(guān)的錯(cuò)誤就可能出現(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++;}消費(fèi)者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:消費(fèi)者執(zhí)行register2=counter;[register2=5]T3:消費(fèi)者執(zhí)行register2=register2-1;[register2=4]T4:生產(chǎn)者執(zhí)行counter=register1;[counter=6]T5:消費(fèi)者執(zhí)行counter=register2;[counter=4]T0:生產(chǎn)者執(zhí)行register1=counter;[register1=5]T1:生產(chǎn)者執(zhí)行register1=register1+1;[register1=6]T2:消費(fèi)者執(zhí)行register2=counter;[register2=5]T3:消費(fèi)者執(zhí)行register2=register2-1;[register2=4]T4:消費(fèi)者執(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:消費(fèi)者執(zhí)行register2=counter;[register2=6]T4:消費(fèi)者執(zhí)行register2=register2-1;[register2=5]T5:消費(fèi)者執(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)入等待主存資源隊(duì)列;}X=X-B;修改主存分配表，進(jìn)程獲得主存資源；}voidreturn(intB){X=X+B;修改主存分配表；釋放等待主存資源的進(jìn)程；}可能永遠(yuǎn)不會(huì)被喚醒21進(jìn)程的交互競(jìng)爭(zhēng)多個(gè)進(jìn)程之間并不知道其他進(jìn)程的存在，競(jìng)爭(zhēng)共享硬設(shè)備、存儲(chǔ)器、處理器和文件資源等兩個(gè)控制問題死鎖問題饑餓問題操作系統(tǒng)應(yīng)該提供支持，合理分配資源，解決資源的競(jìng)爭(zhēng)問題進(jìn)程的互斥訪問是解決進(jìn)程間競(jìng)爭(zhēng)資源的手段進(jìn)程互斥是指若干進(jìn)程因相互爭(zhēng)奪獨(dú)占型資源而產(chǎn)生的競(jìng)爭(zhēng)制約關(guān)系協(xié)作一組進(jìn)程之間相互知道對(duì)方的存在，協(xié)作完成同一任務(wù)。進(jìn)程的同步是解決進(jìn)程間協(xié)作關(guān)系的手段。進(jìn)程同步是指為完成共同任務(wù)的并發(fā)進(jìn)程基于某個(gè)條件來協(xié)調(diào)其活動(dòng)，因?yàn)樾枰谀承┪恢蒙吓哦▓?zhí)行的先后次序而等待、傳遞信號(hào)或消息所產(chǎn)生的協(xié)作制約關(guān)系進(jìn)程互斥關(guān)系是一種特殊的進(jìn)程同步關(guān)系。22臨界區(qū)管理互斥與臨界區(qū)實(shí)現(xiàn)臨界區(qū)管理的幾種嘗試實(shí)現(xiàn)臨界區(qū)管理的軟件方法實(shí)現(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í)行時(shí)，不讓另一個(gè)進(jìn)程進(jìn)入臨界區(qū)，即各進(jìn)程對(duì)共享變量的訪問是互斥的，就不會(huì)造成與時(shí)間有關(guān)的錯(cuò)誤。24互斥與臨界區(qū)(2)一次至多一個(gè)進(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)在有限時(shí)間內(nèi)退出，以便讓等待進(jìn)程中的一個(gè)進(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ū)管理的嘗試同時(shí)進(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ū)管理的嘗試同時(shí)阻塞!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個(gè)進(jìn)程？28Peterson方法的正確性互斥性若P0，P1同時(shí)進(jìn)入臨界區(qū)，則意味flag[0]=flag[1]=true;但turn只可能取值0或1，因此不可能同時(shí)進(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;此時(shí)，P1在臨界區(qū).當(dāng)P1執(zhí)行完以后，將設(shè)置flag[1]=false,若此時(shí)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，此時(shí)P1將被阻塞，而P0將得以進(jìn)入臨界區(qū)因此，進(jìn)程最多等待另一個(gè)進(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)程不會(huì)被打斷，從而不會(huì)發(fā)生進(jìn)程切換關(guān)中斷時(shí)間過長(zhǎng)會(huì)影響系統(tǒng)效率不適用多處理器系統(tǒng)。在一個(gè)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,從而通過測(cè)試進(jìn)入臨界區(qū)；若資源不可用，則lock為false,返回false，進(jìn)程忙等；*/while(test_and_set(lock)==false);/*criticalsection*/;lock=true;/*remainder*/;}}33test_and_set解決臨界區(qū)管理將臨界區(qū)與一個(gè)布爾變量lock相關(guān)聯(lián)lock代表臨界資源的狀態(tài)，可以看成一把鎖，lock為true/false表示臨界資源可用/不可用初始值為true,如有進(jìn)程要進(jìn)入臨界區(qū)，則對(duì)lock進(jìn)行測(cè)試和設(shè)置指令如果已有進(jìn)程在臨界區(qū)，則test_and_set返回false,將被阻止進(jìn)入臨界區(qū)如果沒有進(jìn)程在臨界區(qū)，則test_and_set返回true,同時(shí)將lock設(shè)為false,以阻止其它進(jìn)程進(jìn)入臨界區(qū)當(dāng)進(jìn)程離開臨界區(qū)時(shí)，將lock設(shè)置為true,表示臨界資源可用能實(shí)現(xiàn)進(jìn)程互斥訪問臨界區(qū)，但是可能會(huì)出現(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后面第一個(gè)在等待進(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)識(shí)為可用，而是將進(jìn)程j等待標(biāo)識(shí)置為false,使得進(jìn)程j可以進(jìn)入臨界區(qū)，而其它進(jìn)程則無法進(jìn)入；*//*remaindersection*/}while(true);}同時(shí)實(shí)現(xiàn)了互斥和有限等待35對(duì)換指令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,通過測(cè)試，進(jìn)入臨界區(qū)；若資源不可用，則lock=true,執(zhí)行swap后keyi仍然為true,進(jìn)程忙等；*/doswap(keyi,lock)while(keyi);/*criticalsection*/;lock=false;/*remainder*/;}}37為每個(gè)臨界區(qū)設(shè)置鎖變量lock，lock為false表示無進(jìn)程在臨界區(qū)內(nèi)當(dāng)進(jìn)程進(jìn)入臨界區(qū)時(shí)，lock設(shè)置為true,keyi變?yōu)閒alse,因此進(jìn)程得以通過測(cè)試，進(jìn)入臨界區(qū)當(dāng)另一個(gè)進(jìn)程希望進(jìn)入臨界區(qū)時(shí),swap(keyi,lock)的結(jié)果是keyi=lock=true,因此，進(jìn)程被阻止進(jìn)入臨界區(qū)當(dāng)進(jìn)程退出臨界區(qū)時(shí)，將lock設(shè)為false,從而被阻止進(jìn)程得以進(jìn)入臨界區(qū)同樣，能實(shí)現(xiàn)進(jìn)程互斥訪問臨界區(qū)，但是可能會(huì)出現(xiàn)進(jìn)程餓死的情況38基于機(jī)器指令方法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)適用于任意數(shù)目的進(jìn)程，適用于單處理機(jī)系統(tǒng)和多處理機(jī)系統(tǒng),只要共享內(nèi)存即可；簡(jiǎn)單，易于驗(yàn)證；可以用于支持多個(gè)臨界區(qū)，為每個(gè)臨界區(qū)定義一個(gè)變量即可缺點(diǎn)采用了忙等方式，浪費(fèi)CPU資源可能會(huì)導(dǎo)致饑餓不滿足有限等待可能會(huì)導(dǎo)致死鎖例如，一個(gè)低優(yōu)先級(jí)的進(jìn)程P1先進(jìn)入臨界區(qū)，然后被處理器中斷，執(zhí)行高優(yōu)先級(jí)進(jìn)程P2，則P2處于忙等，P1因優(yōu)先級(jí)低而不會(huì)被處理器調(diào)度，從而產(chǎn)生死鎖。實(shí)際上，這個(gè)例子中臨界區(qū)是一個(gè)資源，而CPU是另一個(gè)資源。只能應(yīng)用于進(jìn)程競(jìng)爭(zhēng)，不能解決進(jìn)程協(xié)作39信號(hào)量與PV操作1965年E.W.Dijkstra提出了新的同步工具--信號(hào)量和P、V操作。40EdsgerW.Dijkstra1930.5.11—2002.8.61972年獲得圖靈獎(jiǎng)成就：提出“goto有害論”;提出信號(hào)量和PV原語;解決了有趣的“哲學(xué)家聚餐”問題;最短路徑算法(SPF)和銀行家算法的創(chuàng)造者;第一個(gè)Algol60編譯器的設(shè)計(jì)者和實(shí)現(xiàn)者;THE操作系統(tǒng)的設(shè)計(jì)者和開發(fā)者與D.E.Knuth(TheArtofComputerProgramming的作者)并稱為我們這個(gè)時(shí)代最偉大的計(jì)算機(jī)科學(xué)家的人41信號(hào)量與PV操作信號(hào)量：一種軟件資源原語：內(nèi)核中執(zhí)行時(shí)不可被中斷的過程P操作原語和V操作原語一個(gè)進(jìn)程在某一特殊點(diǎn)上被迫停止執(zhí)行直到接收到一個(gè)對(duì)應(yīng)的特殊變量值，這種特殊變量就是信號(hào)量(semaphore)，復(fù)雜的進(jìn)程合作需求都可以通過適當(dāng)?shù)男盘?hào)結(jié)構(gòu)得到滿足。42信號(hào)量操作系統(tǒng)中，信號(hào)量表示物理資源的實(shí)體，它是一個(gè)與隊(duì)列有關(guān)的整型變量。實(shí)現(xiàn)時(shí)，信號(hào)量是一種記錄型數(shù)據(jù)結(jié)構(gòu)，有兩個(gè)分量：一個(gè)是信號(hào)量的值，另一個(gè)是信號(hào)量隊(duì)列的隊(duì)列指針。信號(hào)量的值(-2)

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

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

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

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

csignal(notfull);/*如果有進(jìn)程等待notfull條件，則喚醒其中的一個(gè)*/}}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]);//一把叉子都不占用時(shí)，在自身?xiàng)l件變量上阻塞自己}voidputdown(inti){state[i]=THINKING;test((i+4)%5);//看鄰居節(jié)點(diǎn)是否具備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)時(shí)，//拿起兩把叉子；

csignal(self[i]);//喚醒一個(gè)在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為每個(gè)對(duì)象都設(shè)置一個(gè)monitorMonitor確保了關(guān)聯(lián)對(duì)象中synchronized方法的互斥訪問，即同一個(gè)對(duì)象，同一時(shí)刻只有一個(gè)線程可以執(zhí)行其上的synchronized方法若是在同一個(gè)類的不同對(duì)象上執(zhí)行相同的synchronized方法，則可以并發(fā)執(zhí)行同步：wait()：開放管程，在給定對(duì)象上等待；notify()：在給定對(duì)象的等待隊(duì)列中喚醒一個(gè)線程；notifyAll()：?jiǎn)拘呀o定對(duì)象等待隊(duì)列中的所有線程，所有被喚醒的線程競(jìng)爭(zhēng)管程的擁有權(quán)，即從條件變量的等待隊(duì)列移到了管程入口的等待隊(duì)列。一旦獲得管程擁有權(quán)，從wait()操作之后開始執(zhí)行。只有在獲得管程對(duì)象所有權(quán)時(shí)，才能執(zhí)行wait(),signal(),signalAll()操作,否則會(huì)拋出IllegalMonitorStateException92classCounter{privateintcount=0;publicvoidincrement(){intn=count;count=n+1;}}如果兩個(gè)線程共享一個(gè)對(duì)象Countercounter,且都希望執(zhí)行counter.increment()方法，則會(huì)導(dǎo)致運(yùn)行結(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會(huì)如何？

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)者-消費(fèi)者問題如果while改為if,則考慮下述情形：假如count=n;則可能存在多個(gè)生產(chǎn)者阻塞在Buffer類對(duì)象上當(dāng)一個(gè)消費(fèi)者消費(fèi)了一個(gè)產(chǎn)品后，喚醒某個(gè)生產(chǎn)者該生產(chǎn)者將產(chǎn)品放入后，調(diào)用notify()操作，則會(huì)喚醒其它等待的生產(chǎn)者被喚醒的生產(chǎn)者從wait()調(diào)用后開始執(zhí)行，將覆蓋未消費(fèi)產(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(){