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

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

12Bernstein條件設R(pi)={a1,a2,…,an}，表示程序pi在執行期間引用的變量集；W(pi)={b1,b2,…,bn}，表示程序pi在執行期間改變的變量集；兩個進程的程序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可并發執行，滿足Bernstein條件。14并發程序帶來的好處單處理器系統上，可有效利用資源，讓處理器和I/O設備，I/O設備和I/O設備同時工作，充分發揮機器部件的并行能力；硬件能并行工作僅有了提高效率的可能性，硬部件并行性的實現需要軟件技術去利用和發揮，這種軟件技術就是并發程序設計。在多處理器系統上，可讓進程在不同處理器上物理地并行工作并發程序設計是多道程序設計的基礎，多道程序的實質就是把并發程序設計引入到系統中。15與時間有關的錯誤并發進程使得進程的執行不可預測，甚至無法再現。進程間的相互影響和制約導致對資源的共享充滿了危險，各種與時間有關的錯誤就可能出現結果不唯一結果與進程執行的速度相關永遠等待進程相互等待產生死鎖，或進程一直得不到資源產生餓死現象16結果不唯一（例1）生產者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:生產者執行register1=counter;[register1=5]T1:生產者執行register1=register1+1;[register1=6]T2:消費者執行register2=counter;[register2=5]T3:消費者執行register2=register2-1;[register2=4]T4:生產者執行counter=register1;[counter=6]T5:消費者執行counter=register2;[counter=4]T0:生產者執行register1=counter;[register1=5]T1:生產者執行register1=register1+1;[register1=6]T2:消費者執行register2=counter;[register2=5]T3:消費者執行register2=register2-1;[register2=4]T4:消費者執行counter=register2;[counter=4]T5:生產者執行counter=register1;[counter=6]執行序列1執行序列2T0:生產者執行register1=counter;[register1=5]T1:生產者執行register1=register1+1;[register1=6]T2:生產者執行counter=register1;[counter=6]T3:消費者執行register2=counter;[register2=6]T4:消費者執行register2=register2-1;[register2=5]T5:消費者執行counter=register2;[counter=5]執行序列318結果不唯一（例2）P1:a=a+1;b=b+1;P2:b=2*b;a=2*a;線性執行a=2b=2;b=4;a=4;并發執行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結果不唯一（例3）voidT1(){//按旅客訂票要求找到AjintX1=Aj；if(X1>=1){X1--;Aj=X1;//輸出一張票；}else{//輸出票已售完}voidT2(){//按旅客訂票要求找到AjintX2=Aj；if(X2>=1){X2--;Aj=X2;//輸出一張票；}else{//輸出票已售完}20永遠等待intX=memory;voidborrow(intB){while(B>X){進程進入等待主存資源隊列;}X=X-B;修改主存分配表，進程獲得主存資源；}voidreturn(intB){X=X+B;修改主存分配表；釋放等待主存資源的進程；}可能永遠不會被喚醒21進程的交互競爭多個進程之間并不知道其他進程的存在，競爭共享硬設備、存儲器、處理器和文件資源等兩個控制問題死鎖問題饑餓問題操作系統應該提供支持，合理分配資源，解決資源的競爭問題進程的互斥訪問是解決進程間競爭資源的手段進程互斥是指若干進程因相互爭奪獨占型資源而產生的競爭制約關系協作一組進程之間相互知道對方的存在，協作完成同一任務。進程的同步是解決進程間協作關系的手段。進程同步是指為完成共同任務的并發進程基于某個條件來協調其活動，因為需要在某些位置上排定執行的先后次序而等待、傳遞信號或消息所產生的協作制約關系進程互斥關系是一種特殊的進程同步關系。22臨界區管理互斥與臨界區實現臨界區管理的幾種嘗試實現臨界區管理的軟件方法實現臨界區管理的硬件設施23互斥與臨界區(1)并發進程中與共享變量有關的程序段叫“臨界區”，共享變量代表的資源叫“臨界資源”。與同一變量有關的臨界區分散在各進程的程序段中，而各進程的執行速度不可預知。如果保證進程在臨界區執行時，不讓另一個進程進入臨界區，即各進程對共享變量的訪問是互斥的，就不會造成與時間有關的錯誤。24互斥與臨界區(2)一次至多一個進程能夠進入臨界區內執行；如果已有進程在臨界區，其他試圖進入的進程應等待；進入臨界區內的進程應在有限時間內退出，以便讓等待進程中的一個進入。臨界區調度原則：

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

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

信號量隊列指針43信號量記錄型信號量的定義typedefstruct{intvalue;structprocess*list;}semaphore;其中，value為一個整型變量，系統初始化時為其賦值；list是等待使用此類資源的進程隊列的頭指針，初始狀態為空隊列。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操作本身的原子性是典型的臨界區問題，即任何時候，只有一個進程能進入P操作或V操作函數的內部可以采用之前介紹過的軟件方法或硬件方法保證P操作或V操作本身的原子性Dekker’s算法Peterson’s算法關中斷(僅限于單處理器)Test_and_set指令swap指令…46信號量的含義若信號量s.value為正值，則此值等于在封鎖進程之前對信號量s可施行的P操作數，也就是s所代表的實際可用的物理資源數；若信號量s.value為負值，則其絕對值等于登記排列在s.list中的等待進程個數，即恰好等于對信號量s實施P操作而被阻塞并進入信號量s的等待隊列的進程數；P操作通常意味著請求一個資源，V操作意味著釋放一個資源。在一定條件下，P操作代表掛起進程的操作，而V操作代表喚醒被掛起進程的操作。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信號量實現互斥semaphormutex;//定義一個信號量，代表臨界區鎖mutex.value=1;//初始值設為1ProcessPi(){P(mutex);//進入臨界區之前執行P(mutex)申請鎖資源/*criticalsection*/;V(mutex);//退出臨界區時執行V(mutex)釋放鎖資源并喚//醒可能等待進程；/*remaindersection*/;}50哲學家進餐問題問題描述：5位哲學家圍在一張圓桌旁，桌子中央有一盤通心粉，每人面前有一只空盤子，每兩人之間有一只筷子；每位哲學家思考，饑餓，然后吃通心面；為了吃面，哲學家必須獲得兩把叉子，且每人只能直接從緊鄰自己的左邊或右邊去取叉子51哲學家進餐問題每把叉子都必須互斥使用，因此，應為每把叉子設置互斥信號量fork[i](i=0,1,2,3,4),其初始值均為1當一位哲學家吃通心面之前必須執行兩個P操作，獲得自己左邊和右邊的兩把叉子在吃完通心面后執行兩個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個哲學家同時拿起自己左手邊（或右手邊)的筷子，則所有哲學家將處于等待狀態，出現死鎖。死鎖的避免將在后續章節介紹。利用互斥信號量解決哲學家進餐問題53哲學家進餐中死鎖的一種解決方案不允許哲學家拿起一把叉子等待另一把叉子要么兩把叉子一起獲得，要么一把都不持有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];/*筷子狀態，0表示 /*空閑,1表示被占用*/for(inti=0;i<5;i++){fork[i]=1;state=0;}mutex=1;缺乏對一把叉子都未獲得的進程阻塞功能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;降低了并發性同一時間僅有一個哲學家能吃通心面56#defineTHINKING0#defineHUNGRY1#defineEATING2semaphors[5];//用于阻塞哲學家的信號量semaphoremutex=1;intstate[5];//哲學家的狀態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]);/*若狀態不為EATING,則此處進程將阻塞自己；變為EATING有兩種可能:（1）自己執行test()時，已經獲得兩把叉子，此時執行了V(s[i])，再執行P(s[i])不會阻塞;（2）鄰居放下叉子時發現本進程等待的兩把叉子空，且處于饑餓狀態，因此決定將叉子都分配給該進程；*/}voidput_fork(inti){P(mutex);state[i]=THINKING;//當前進程不再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信號量實現同步生產者-消費者問題讀者-寫者問題理發師問題60生產者—消費者問題有限的大小為n的緩存空間，組織成環狀p個生產者和q個消費者每個生產者每次生產一件產品并放入緩存，如果緩存已滿，則等待消費者消費后再放入；每個消費者每次消費一個產品，如果緩存為空，則等待生產者放入產品61生產者-消費者問題分析互斥要求禁止兩個以上生產者同時將產品放入同一個位置禁止兩個以上的消費者同時消費同一個產品同步要求僅當緩沖區產品數大于0時，消費者才能消費產品，否則消費者必須等待；當生產者生產了一個產品時，將可用產品數加1，如果有消費者等待，則喚醒一個等待產品的消費者；僅當空閑緩沖區數大于0時，生產者可以放入產品，否則生產者必須等待；當消費者消費了一個產品后，將空閑緩沖區數加1，如果有消費者等待，則喚醒一個等待空閑緩沖區的生產者；62itemB[n];Semaphoreempty;/*可用的空緩沖區個數*/Semaphorefull;/*可用的產品數*/Semaphoremutex;/*互斥信號量*/empty=n;full=0;mutex=1;intin=0;out=0;/*in為放入緩沖區指針，out為取出緩沖區指針*/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操作的順序交換，會出現什么情況？P(mutex);P(empty);當emtpy=0,即緩沖滿了時，可能會出現死鎖！63itemB[n];Semaphoreempty;/*可用的空緩沖區個數*/Semaphorefull;/*可用的產品數*/Semaphorepmutex,cmutex;/*互斥信號量*/empty=n;full=0;pmutex=1;cmutex=1;intin=0;out=0;/*in為放入緩沖區指針，out為取出緩沖區指針*/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);}}僅當in==out時，producer和consumer才共享buffer數據，但此時，要么empty=0,要么full=0;因此，該方法可行。在生產者放產品的同時，消費者可以消費產品，而若采用同一mutex則不行64讀者-寫者問題有兩組并發進程，讀者和寫者，共享文件F，要求允許多個讀者同時對文件執行讀操作；只允許一個寫者對文件執行寫操作；任何寫者在完成寫操作之前不允許其他讀者或寫者工作；寫者在執行寫操作前，應讓已有的寫者和讀者全部退出。65讀者寫者問題—讀者優先當存在讀者時，寫者將被延遲且只要有一個讀者活躍，隨后而來的讀者都將被允許訪問文件可能造成寫者的饑餓66讀者寫者問題—讀者優先互斥需求禁止多個寫者同時對文件進行寫操作禁止讀者和寫者同時工作引入寫鎖寫者必須獲得寫鎖才能進行寫操作；第一個讀者也必須獲得寫鎖才能進行讀操作，后續讀者無需獲得寫鎖可以直接讀；同步需求當最后一個讀者結束后，釋放寫鎖，如果存在等待寫鎖的寫者，則喚醒之；當寫者結束后，釋放寫鎖，如果存在等待寫鎖的用戶（其它寫者或第一個讀者），則喚醒之；67Intreadcount=0;/*讀進程計數器*/Semaphorewritelock,mutex;/*writelock為寫鎖，mutex為互斥信號量*/Writelock=1;mutex=1;Processreader_i(){P(mutex);/*保證不同的讀者互斥訪問readcount共享變量；*/readcount++;/*讀進程個數加1；*/if(readcount==1)/*當只有一個讀進程時，獲得寫鎖，阻塞寫嘗試*/P(writelock);V(mutex);/*釋放互斥信號量*/read();/*如為第一個讀進程，則已經獲得寫鎖，否則，表明已有讀進程在讀，可以進行讀操作*/P(mutex);/*保證不同的讀者互斥訪問readcount共享變量;*/readcount--;/*讀進程個數減1*/if(readcount==0)/*若讀進程個數為0，則可以喚醒寫進程*/V(writelock);V(mutex);/*釋放互斥信號量*/}68Processwriter_i(){P(writelock);/*嘗試獲得寫鎖;*/write();/*寫操作*/V(writelock);/*釋放寫鎖*/}69mutex隊列writelock隊列當系統中已有進程在讀或寫時，寫進程阻塞在writelock隊列當系統中已有進程在讀時，后續讀進程不會被阻塞；當系統中已有進程在寫時，第一個讀進程阻塞在writelock隊列，后續讀進程阻塞在mutex隊列；70讀者寫者問題—寫者優先當一個寫進程聲明想進行寫操作時，不允許新的讀者訪問文件，即所有之后發生的讀請求將在該寫操作之后進行當后續寫者到達時，只要系統中有寫者在工作，則后續寫者也將優先于系統中已到達的讀者被服務71Intreadcount=0;/*讀者計數器*/intwritecount=0;/*寫者計數器*/semaphorewritelock=1;/*寫鎖*/semaphorerdcntmutex=1;/*讀者計數器的互斥信號量*/semaphorewrtcntmutex=1;/*寫者計數器的互斥信號量*/semaphorequeue=1;

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

conditionnotfull,notempty;voidappend(charx){

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

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

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

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

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

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

csignal(self[i]);//喚醒一個在self[i]條件變量等待的哲學家}}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關鍵詞java為每個對象都設置一個monitorMonitor確保了關聯對象中synchronized方法的互斥訪問，即同一個對象，同一時刻只有一個線程可以執行其上的synchronized方法若是在同一個類的不同對象上執行相同的synchronized方法，則可以并發執行同步：wait()：開放管程，在給定對象上等待；notify()：在給定對象的等待隊列中喚醒一個線程；notifyAll()：喚醒給定對象等待隊列中的所有線程，所有被喚醒的線程競爭管程的擁有權，即從條件變量的等待隊列移到了管程入口的等待隊列。一旦獲得管程擁有權，從wait()操作之后開始執行。只有在獲得管程對象所有權時，才能執行wait(),signal(),signalAll()操作,否則會拋出IllegalMonitorStateException92classCounter{privateintcount=0;publicvoidincrement(){intn=count;count=n+1;}}如果兩個線程共享一個對象Countercounter,且都希望執行counter.increment()方法，則會導致運行結果不唯一。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的管程機制解決生產者-消費者問題如果while改為if,則考慮下述情形：假如count=n;則可能存在多個生產者阻塞在Buffer類對象上當一個消費者消費了一個產品后，喚醒某個生產者該生產者將產品放入后，調用notify()操作，則會喚醒其它等待的生產者被喚醒的生產者從wait()調用后開始執行，將覆蓋未消費產品！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(){