教學課件PPT 同步、通信與死鎖

《教學課件PPT 同步、通信與死鎖》由會員分享，可在線閱讀，更多相關《教學課件PPT 同步、通信與死鎖（146頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、1第第3 3章章 同步、通信與死鎖同步、通信與死鎖 主要內容主要內容0并發(fā)進程并發(fā)進程0臨界區(qū)管理臨界區(qū)管理0信號量與信號量與PVPV操作操作0管程（刪）管程（刪）0進程通信進程通信0死鎖死鎖0LinuxLinux同步機制和通信機制同步機制和通信機制0Windows2003Windows2003同步機制和通信同步機制和通信23.1 3.1 并發(fā)進程并發(fā)進程3.1.1 3.1.1 順序程序設計順序程序設計 3.1.2 3.1.2 進程的并發(fā)性進程的并發(fā)性 3.1.3 3.1.3 進程的交互：協(xié)作和競爭進程的交互：協(xié)作和競爭 33.1.1 3.1.1 順序程序設計順序程序設計進程的順序性進程的順序

2、性 一個進程在順序處理器上的執(zhí)行是嚴格按一個進程在順序處理器上的執(zhí)行是嚴格按序的，一個進程只有當一個操作結束后，序的，一個進程只有當一個操作結束后，才能開始后繼操作。才能開始后繼操作。 順序程序設計是把一個程序設計成一個順順序程序設計是把一個程序設計成一個順序執(zhí)行的程序模塊，順序的含義不但指一序執(zhí)行的程序模塊，順序的含義不但指一個程序模塊內部，也指兩個程序模塊之間個程序模塊內部，也指兩個程序模塊之間。4順序程序設計的特性順序程序設計的特性 程序執(zhí)行的順序性程序執(zhí)行的順序性 程序環(huán)境的封閉性程序環(huán)境的封閉性 程序執(zhí)行結果的確定性程序執(zhí)行結果的確定性 計算過程的可再現(xiàn)性計算過程的可再現(xiàn)性l順序程序

3、設計的缺點順序程序設計的缺點計算機系統(tǒng)效率不高。計算機系統(tǒng)效率不高。53.1.2 3.1.2 進程的并發(fā)性進程的并發(fā)性1 1、并發(fā)程序設計、并發(fā)程序設計 進程執(zhí)行的并發(fā)性：一組進程的執(zhí)行在時間上是進程執(zhí)行的并發(fā)性：一組進程的執(zhí)行在時間上是重疊的。重疊的。 并發(fā)性舉例：有兩個進程并發(fā)性舉例：有兩個進程A(a1A(a1、a2a2、a3)a3)和和B(b1B(b1、b2b2、b3)b3)并發(fā)執(zhí)行。并發(fā)執(zhí)行。0 a1a1、a2a2、a3a3、b1b1、b2b2、b3 b3 順序執(zhí)行順序執(zhí)行0 a1a1、b1b1、a2a2、b2b2、a3a3、b3 b3 并發(fā)執(zhí)行并發(fā)執(zhí)行 從宏觀上看，一個時間段中幾個進

4、程都在同一處從宏觀上看，一個時間段中幾個進程都在同一處理器上，處于運行還未運行結束狀態(tài)。理器上，處于運行還未運行結束狀態(tài)。 從微觀上看，任一時刻僅有一個進程在處理器上從微觀上看，任一時刻僅有一個進程在處理器上運行。運行。6串行工作圖示串行工作圖示i1p1o1i2p2o27并行工作圖示并行工作圖示進程進程i1i1p1p1 i i p p o oo1o1i2i2p2p2o2o2i3i3p3p3o3o3t1t1t2t2t3t3時間時間并行工作并行工作i4i4t4t4i5i5P4P4t5t58并發(fā)的實質并發(fā)的實質 并發(fā)的實質是一個處理器在幾個進程之間并發(fā)的實質是一個處理器在幾個進程之間的多路復用，并發(fā)

5、是對有限的物理資源強的多路復用，并發(fā)是對有限的物理資源強制行使多用戶共享，消除計算機部件之間制行使多用戶共享，消除計算機部件之間的互等現(xiàn)象，以提高系統(tǒng)資源利用率。的互等現(xiàn)象，以提高系統(tǒng)資源利用率。92 2、并發(fā)進程的特性、并發(fā)進程的特性 無關的并發(fā)進程無關的并發(fā)進程0一組并發(fā)進程分別在不同的變量集合上操作，一組并發(fā)進程分別在不同的變量集合上操作，一個進程的執(zhí)行與其他并發(fā)進程的進展無關。一個進程的執(zhí)行與其他并發(fā)進程的進展無關。x并發(fā)進程的無關性是進程的執(zhí)行與時間無關的并發(fā)進程的無關性是進程的執(zhí)行與時間無關的一個充分條件，又稱為一個充分條件，又稱為BernsteinBernstein條件條件。 交

6、互的并發(fā)進程交互的并發(fā)進程0一組并發(fā)進程共享某些變量，一個進程的執(zhí)行一組并發(fā)進程共享某些變量，一個進程的執(zhí)行可能影響其他并發(fā)進程的結果?？赡苡绊懫渌l(fā)進程的結果。 10BernsteinBernstein條件條件 R(piR(pi)=a1,a2,)=a1,a2,anan，程序，程序pipi在執(zhí)行期間引用的在執(zhí)行期間引用的變量集變量集W(piW(pi)=b1,b2,)=b1,b2,bmbm ，程序，程序pipi在執(zhí)行期間改變的在執(zhí)行期間改變的變量集變量集若兩個程序的變量集交集之和為空集若兩個程序的變量集交集之和為空集： R(p1)W(p2)R(p2)W(p1)W(p1)W(p2)= R(p1)

7、W(p2)R(p2)W(p1)W(p1)W(p2)= 則并發(fā)進程的執(zhí)行與時間無關。則并發(fā)進程的執(zhí)行與時間無關。11BernsteinBernstein條件舉例條件舉例例如，有如下四條語句：例如，有如下四條語句： S1: a := x + y S2: b := z + 1S1: a := x + y S2: b := z + 1 S3: c := a b S4: w := c + 1 S3: c := a b S4: w := c + 1于是有于是有：R(S1)=x,y ,R(S2)=zR(S1)=x,y ,R(S2)=z，R(S3)=a,bR(S3)=a,b，R(S4)=cR(S4)=c；W(

8、S1)=a, W(S1)=a, W(S2)=bW(S2)=b，W(S3)=cW(S3)=c，W(S4)=wW(S4)=w。 S1S1和和S2S2可并發(fā)執(zhí)行，滿足可并發(fā)執(zhí)行，滿足BernsteinBernstein條件條件。其他語句并發(fā)執(zhí)行可能會產生與時間有。其他語句并發(fā)執(zhí)行可能會產生與時間有關的錯誤。關的錯誤。12并發(fā)程序設計的優(yōu)點并發(fā)程序設計的優(yōu)點l對于單處理器系統(tǒng)對于單處理器系統(tǒng), ,可讓處理器和各可讓處理器和各I/OI/O設設備同時工作備同時工作, ,發(fā)揮硬部件的并行能力。發(fā)揮硬部件的并行能力。l對于多處理器系統(tǒng)對于多處理器系統(tǒng), ,可讓各進程在不同處可讓各進程在不同處理器上物理地并行，

9、加快計算速度。理器上物理地并行，加快計算速度。l簡化了程序設計任務。簡化了程序設計任務。 13采用并發(fā)程序設計的目的采用并發(fā)程序設計的目的 充分發(fā)揮硬件的并行性，提高系統(tǒng)效率。充分發(fā)揮硬件的并行性，提高系統(tǒng)效率。硬件能并行工作僅有了提高效率的可能性硬件能并行工作僅有了提高效率的可能性，硬部件并行性的實現(xiàn)需要軟件技術去利，硬部件并行性的實現(xiàn)需要軟件技術去利用和發(fā)揮，這種軟件技術就是并發(fā)程序設用和發(fā)揮，這種軟件技術就是并發(fā)程序設計。計。 并發(fā)程序設計是多道程序設計的基礎，多并發(fā)程序設計是多道程序設計的基礎，多道程序的實質就是把并發(fā)程序設計引入到道程序的實質就是把并發(fā)程序設計引入到系統(tǒng)中。系統(tǒng)中。1

10、43 3、與時間有關的錯誤、與時間有關的錯誤 對于一組交互的并發(fā)進程，執(zhí)行的相對速對于一組交互的并發(fā)進程，執(zhí)行的相對速度無法相互控制，各種與時間有關的錯誤度無法相互控制，各種與時間有關的錯誤就可能出現(xiàn)。就可能出現(xiàn)。 與時間有關錯誤的表現(xiàn)形式：與時間有關錯誤的表現(xiàn)形式：0結果不唯一結果不唯一0永遠等待永遠等待15（結果不唯一）機票問題（結果不唯一）機票問題/飛機票售票問題飛機票售票問題 void T1( ) void T2( ) void T1( ) void T2( ) 按旅客訂票要求找到按旅客訂票要求找到AjAj; ; 按旅客訂票要求找到按旅客訂票要求找到AjAj; int X1=Aj; i

11、nt X2=Aj int X1=Aj; int X2=Aj; ; if(X1=1) if(X2=1) if(X1=1) if(X2=1) X1-; X2-; X1-; X2-; Aj=X1; Aj Aj=X1; Aj=X2;=X2; 輸出一張票輸出一張票; ; 輸出一張票輸出一張票; else elseelse else 輸出信息輸出信息 票已售完票已售完; ; 輸出信息輸出信息 票已售完票已售完; 16T1T1、T2T2并發(fā)執(zhí)行，可能出現(xiàn)如下交叉情況：并發(fā)執(zhí)行，可能出現(xiàn)如下交叉情況：T1:X1=AjT1:X1=Aj; /X1=m; /X1=mT2:X2=AjT2:X2=Aj; /X2=m;

12、/X2=mT2:X2-;Aj=X2;T2:X2-;Aj=X2;輸出一張票輸出一張票; /Aj; /Aj=m-1=m-1T1:X1-;Aj=X1;T1:X1-;Aj=X1;輸出一張票輸出一張票; /Aj; /Aj=m-1=m-1同一張票賣給兩位旅客（若只有一張余票）或者余同一張票賣給兩位旅客（若只有一張余票）或者余票數(shù)不正確（若有多張余票）。票數(shù)不正確（若有多張余票）。17（永遠等待）主存管理問題（永遠等待）主存管理問題申請和歸還主存資源問題申請和歸還主存資源問題 intint X=memory; /memory X=memory; /memory為初始主存容量為初始主存容量 voidvoid

13、borrow(int B) void return(intborrow(int B) void return(int B) B) while(B while(BX) X=X+B;X) X=X+B; 進程進入等待主存資源隊列進程進入等待主存資源隊列; ; 修改主存分配表修改主存分配表; X=X-B ; X=X-B ; 釋放等主存資源進程釋放等主存資源進程; ; 修改主存分配表，修改主存分配表， 進程獲得主存資源進程獲得主存資源; ; 18若對若對borrowborrow和和returnreturn的并發(fā)執(zhí)行不加限制將會導致的并發(fā)執(zhí)行不加限制將會導致錯誤，例如：錯誤，例如：Borrow:while

14、(BBorrow:while(BX);X);Return:XReturn:X=X+B;=X+B;修改主存分配表修改主存分配表;釋放等待主存釋放等待主存資源的進程資源的進程 ；此時，因為此時，因為borrowborrow還沒有進入等待隊列，因此，還沒有進入等待隊列，因此，returnreturn的釋放操作是空操作，當?shù)尼尫挪僮魇强詹僮?，當borrowborrow進入等待隊進入等待隊列時，可能沒有進程再來歸還，處于永遠等待狀態(tài)列時，可能沒有進程再來歸還，處于永遠等待狀態(tài)。193.1.3 3.1.3 進程的交互：競爭與協(xié)作進程的交互：競爭與協(xié)作(1)(1)第一種是競爭關系第一種是競爭關系 系統(tǒng)中的多

15、個進程之間彼此無關系統(tǒng)中的多個進程之間彼此無關 系統(tǒng)中的多個進程之間彼此相關系統(tǒng)中的多個進程之間彼此相關 l資源競爭的兩個控制問題：資源競爭的兩個控制問題：l 一個是死鎖一個是死鎖(Deadlock)(Deadlock)問題，問題， l 一個是饑餓一個是饑餓(Starvation) (Starvation) 問題問題l 既要解決饑餓問題，又要解決死鎖問題。既要解決饑餓問題，又要解決死鎖問題。l進程互斥是指若干個進程因相互爭奪獨占型資源進程互斥是指若干個進程因相互爭奪獨占型資源時所產生的競爭制約關系。時所產生的競爭制約關系。20進程的交往：競爭與協(xié)作進程的交往：競爭與協(xié)作(2)(2)第二種是協(xié)作

16、關系第二種是協(xié)作關系l某些進程為完成同一任務需要分工協(xié)作。某些進程為完成同一任務需要分工協(xié)作。l進程進程同步同步指為完成共同任務的并發(fā)進程基于某個指為完成共同任務的并發(fā)進程基于某個條件來協(xié)調它們的活動，因為需要在某些位置上條件來協(xié)調它們的活動，因為需要在某些位置上排定執(zhí)行的先后次序而等待、傳遞信號或消息所排定執(zhí)行的先后次序而等待、傳遞信號或消息所產生的協(xié)作制約關系。產生的協(xié)作制約關系。l進程同步指兩個以上進程基于某個條件來協(xié)調它們的進程同步指兩個以上進程基于某個條件來協(xié)調它們的活動。一個進程的執(zhí)行依賴于協(xié)作進程的消息或信號活動。一個進程的執(zhí)行依賴于協(xié)作進程的消息或信號，當一個進程沒有得到來自于

17、協(xié)作進程的消息或信號，當一個進程沒有得到來自于協(xié)作進程的消息或信號時需等待，直到消息或信號到達才被喚醒。時需等待，直到消息或信號到達才被喚醒。 進程進程互斥互斥關系是一種特殊的進程同步關系，即逐關系是一種特殊的進程同步關系，即逐次使用互斥共享資源，是對進程使用資源次序上次使用互斥共享資源，是對進程使用資源次序上的一種協(xié)調。的一種協(xié)調。213.2 3.2 臨界區(qū)管理臨界區(qū)管理3.2.1 3.2.1 互斥與臨界區(qū)互斥與臨界區(qū)3.2.2 3.2.2 實現(xiàn)臨界區(qū)管理的幾種嘗試實現(xiàn)臨界區(qū)管理的幾種嘗試3.2.3 3.2.3 實現(xiàn)臨界區(qū)管理的軟件方法實現(xiàn)臨界區(qū)管理的軟件方法3.2.4 3.2.4 實現(xiàn)臨界

18、區(qū)管理的硬件設施實現(xiàn)臨界區(qū)管理的硬件設施223.2.1 3.2.1 互斥與臨界區(qū)互斥與臨界區(qū)(1)(1) 并發(fā)進程中與共享變量有關的程序段叫并發(fā)進程中與共享變量有關的程序段叫“臨臨界區(qū)界區(qū)”， 共享變量代表的資源叫共享變量代表的資源叫“臨界資臨界資源源”。 與同一變量有關的臨界區(qū)分散在各進程的程與同一變量有關的臨界區(qū)分散在各進程的程序段中，而各進程的執(zhí)行速度不可預知。序段中，而各進程的執(zhí)行速度不可預知。 如果保證進程在臨界區(qū)執(zhí)行時，不讓另一個如果保證進程在臨界區(qū)執(zhí)行時，不讓另一個進程進入臨界區(qū)，即各進程對共享變量的訪進程進入臨界區(qū)，即各進程對共享變量的訪問是互斥的，就不會造成與時間有關的錯誤問

19、是互斥的，就不會造成與時間有關的錯誤。23互斥與臨界區(qū)互斥與臨界區(qū)(2)(2) 臨界區(qū)調度原則：臨界區(qū)調度原則：0一次至多一個進程能夠進入臨界區(qū)內執(zhí)行；一次至多一個進程能夠進入臨界區(qū)內執(zhí)行；0如果已有進程在臨界區(qū)，其他試圖進入的進程應等待；如果已有進程在臨界區(qū)，其他試圖進入的進程應等待；0進入臨界區(qū)內的進程應在有限時間內退出，以便讓等待進入臨界區(qū)內的進程應在有限時間內退出，以便讓等待進程中的一個進入。進程中的一個進入。 臨界區(qū)調度原則總結：臨界區(qū)調度原則總結：0互斥使用，有空讓進；互斥使用，有空讓進；0忙則等待，有限等待；忙則等待，有限等待；0擇一而入，算法可行。擇一而入，算法可行。243.2

20、.2 3.2.2 臨界區(qū)管理的嘗試臨界區(qū)管理的嘗試 (1)(1) bool inside1=false; /P1bool inside1=false; /P1不在其臨界區(qū)內不在其臨界區(qū)內 boolbool inside2=false; /P2 inside2=false; /P2不在其臨界區(qū)內不在其臨界區(qū)內 cobegin /cobegin /* *cobegincobegin和和coendcoend表示括號中的進程是一組并表示括號中的進程是一組并發(fā)進程發(fā)進程* */ / process P1( ) process P2( ) process P1( ) process P2( ) while

21、(inside2);/while(inside2);/等待等待 while(inside1);/while(inside1);/等待等待 inside1=true; inside2=true;inside1=true; inside2=true; 臨界區(qū)臨界區(qū); ; 臨界區(qū)臨界區(qū); inside1=false; inside2=false; inside1=false; inside2=false; coendcoend可能不滿足互斥條件可能不滿足互斥條件25臨界區(qū)管理的嘗試臨界區(qū)管理的嘗試 (2)(2) bool inside1=false; /P1bool inside1=false; /

22、P1不在其臨界區(qū)內不在其臨界區(qū)內 boolbool inside2=false; /P2 inside2=false; /P2不在其臨界區(qū)內不在其臨界區(qū)內 cobegincobegin process P1( ) process P2( ) process P1( ) process P2( ) inside1=true; inside2=true; inside1=true; inside2=true; while(inside2);/ while(inside2);/等待等待 while(inside1);/while(inside1);/等待等待 臨界區(qū)臨界區(qū); ; 臨界區(qū)臨界區(qū); in

23、side1=false; inside2=false; inside1=false; inside2=false; coendcoend可能出現(xiàn)死循環(huán)可能出現(xiàn)死循環(huán)263.2.33.2.3實現(xiàn)臨界區(qū)的軟件算法實現(xiàn)臨界區(qū)的軟件算法PetersonPeterson算法算法(1)(1) bool inside2;bool inside2; inside0=false;inside0=false; inside1=false;inside1=false; enumenum 0,1 turn; 0,1 turn;27PetersonPeterson算法算法(2)(2) cobegincobegin pr

24、ocess P0( ) process P0( ) inside0=true; inside0=true; turn=1; turn=1; while(inside1&turn=1); while(inside1&turn=1); 臨界區(qū)臨界區(qū); ; inside0=false; inside0=false; 28PetersonPeterson算法算法(3)(3) process P1( ) process P1( ) inside1=true; inside1=true; turn=0; turn=0; while(inside0&turn=0); while(inside0&turn=0

25、); 臨界區(qū)臨界區(qū); ; inside1=false; inside1=false; coendcoend293.2.4 3.2.4 實現(xiàn)臨界區(qū)管理的硬件設施實現(xiàn)臨界區(qū)管理的硬件設施 關中斷關中斷 測試并建立指令（刪）測試并建立指令（刪） 對換指令（刪）對換指令（刪）30關中斷關中斷 實現(xiàn)互斥的最簡單方法實現(xiàn)互斥的最簡單方法 關中斷適用場合關中斷適用場合0簡單有效，對操作系統(tǒng)自身有用，可在更新共享變量簡單有效，對操作系統(tǒng)自身有用，可在更新共享變量或列表的幾條指令期間禁止中斷?；蛄斜淼膸讞l指令期間禁止中斷。 關中斷方法的缺點關中斷方法的缺點0不適合作為通用的互斥機制，關中斷時間過長會影響不適合作

26、為通用的互斥機制，關中斷時間過長會影響性能和系統(tǒng)效率；性能和系統(tǒng)效率；0不適應于多處理器計算機系統(tǒng)，因為一個處理器關中不適應于多處理器計算機系統(tǒng)，因為一個處理器關中斷，并不能防止進程在其它處理器上執(zhí)行相同的臨界斷，并不能防止進程在其它處理器上執(zhí)行相同的臨界段代碼；段代碼；0若將這項權力賦予用戶會存在危險，若用戶未開中斷若將這項權力賦予用戶會存在危險，若用戶未開中斷，則系統(tǒng)可能因此而終止。，則系統(tǒng)可能因此而終止。313.3 3.3 信號量信號量與與PVPV操作操作3.3.1 3.3.1 同步與同步機制同步與同步機制3.3.2 3.3.2 信號量與信號量與PVPV操作操作3.3.3 3.3.3 信

27、號量實現(xiàn)互斥信號量實現(xiàn)互斥3.3.4 3.3.4 五個哲學家吃通心面問題五個哲學家吃通心面問題3.3.5 3.3.5 生產者生產者- -消費者問題消費者問題3.3.6 3.3.6 讀者讀者- -寫者問題寫者問題3.3.7 3.3.7 理發(fā)師問題理發(fā)師問題323.3.1 3.3.1 同步和同步機制同步和同步機制 著名的生產者著名的生產者-消費者問題是計算機操作系統(tǒng)中消費者問題是計算機操作系統(tǒng)中并發(fā)進程內在關系的一種抽象，是典型的進程同并發(fā)進程內在關系的一種抽象，是典型的進程同步問題。步問題。 在操作系統(tǒng)中，生產者進程可以是計算進程、發(fā)在操作系統(tǒng)中，生產者進程可以是計算進程、發(fā)送進程；而消費者進程

28、可以是打印進程、接收進送進程；而消費者進程可以是打印進程、接收進程等等。程等等。 解決好生產者解決好生產者-消費者問題就解決好了一類并發(fā)消費者問題就解決好了一類并發(fā)進程的同步問題。進程的同步問題。33生產者生產者-消費者問題表述消費者問題表述有界緩沖問題有界緩沖問題 有有n n個生產者和個生產者和m m個消費者，連接在一個有個消費者，連接在一個有k k個單位緩沖區(qū)的有界緩沖上。其中個單位緩沖區(qū)的有界緩沖上。其中，pipi和和cjcj都是并發(fā)進程，只要緩沖區(qū)未滿，生產都是并發(fā)進程，只要緩沖區(qū)未滿，生產者者pipi生產的產品就可投入緩沖區(qū)；只要緩生產的產品就可投入緩沖區(qū)；只要緩沖區(qū)不空，消費者進程

29、沖區(qū)不空，消費者進程cjcj就可從緩沖區(qū)取就可從緩沖區(qū)取走并消耗產品。走并消耗產品。34生產者生產者- -消費者問題算法描述消費者問題算法描述(1)(1) intint k; k; typedef anyitemtypedef anyitem item; /item item; /item類型類型 item bufferkitem bufferk; intint in=0,out=0,counter=0; in=0,out=0,counter=0;35生產者生產者- -消費者問題算法描述消費者問題算法描述(2)(2) process producer(voidprocess producer(

30、void) ) while (true) /while (true) /無限循環(huán)無限循環(huán) produce an item in nextpproduce an item in nextp;/;/生產一個產品生產一個產品 if (counter=k) /if (counter=k) /緩沖滿時，生產者睡眠緩沖滿時，生產者睡眠 sleep(producersleep(producer);); bufferin=nextp bufferin=nextp;/;/將一個產品放入緩沖區(qū)將一個產品放入緩沖區(qū) in=(in+1)%k; /in=(in+1)%k; /指針推進指針推進 counter+; /co

31、unter+; /緩沖內產品數(shù)加緩沖內產品數(shù)加1 1 if(counter if(counter=1) /=1) /緩沖為空，加進一件產品緩沖為空，加進一件產品 wakeup(consumerwakeup(consumer);); / /并喚醒消費者并喚醒消費者 36生產者生產者- -消費者問題算法描述消費者問題算法描述(3)(3) process consumer(voidprocess consumer(void) ) while (true) /while (true) /無限循環(huán)無限循環(huán)if (counter=0) /if (counter=0) /緩沖區(qū)空，消費者睡眠緩沖區(qū)空，消費者

32、睡眠 sleep(consumersleep(consumer);); nextc=bufferout nextc=bufferout;/;/取一個產品到取一個產品到nextcnextc out=(out+1)%k; / out=(out+1)%k; /指針推進指針推進 counter-; /counter-; /取走一個產品，計數(shù)減取走一個產品，計數(shù)減1 1if(counterif(counter=k-1) /=k-1) /緩沖滿了，取走一件產品并喚緩沖滿了，取走一件產品并喚 wakeup(producerwakeup(producer);); / /醒生產者醒生產者consume the

33、item in nextcconsume the item in nextc;/;/消耗產品消耗產品 37生產者生產者- -消費者問題的算法描述消費者問題的算法描述(4)(4) 生產者和消費者進程對生產者和消費者進程對countercounter的交替執(zhí)行的交替執(zhí)行會使其結果不唯一。會使其結果不唯一。 生產者和消費者進程的交替執(zhí)行會導致進生產者和消費者進程的交替執(zhí)行會導致進程永遠等待。程永遠等待。383.3.2 3.3.2 信號量與信號量與PVPV操作操作(1)(1) 前節(jié)種種方法解決臨界區(qū)調度問題的缺點前節(jié)種種方法解決臨界區(qū)調度問題的缺點: : 1) 1)對不能進入臨界區(qū)的進程，采用忙式等待

34、測試對不能進入臨界區(qū)的進程，采用忙式等待測試法，浪費法，浪費CPUCPU時間。時間。 2)2)將測試能否進入臨界區(qū)的責任推給各個競爭的將測試能否進入臨界區(qū)的責任推給各個競爭的進程會削弱系統(tǒng)的可靠性，加重了用戶編程負擔進程會削弱系統(tǒng)的可靠性，加重了用戶編程負擔。 19651965年年E.W.DijkstraE.W.Dijkstra提出了新的同步工具提出了新的同步工具-信號信號量和量和P P、V V操作。操作。 39信號量與信號量與PVPV操作操作(2)(2) 信號量：一種軟件資源信號量：一種軟件資源 原語：內核中執(zhí)行時不可被中斷的過程原語：內核中執(zhí)行時不可被中斷的過程 P P操作原語和操作原語和

35、V V操作操作原語原語 一個進程在某一特殊點上被迫停止執(zhí)行直到接收一個進程在某一特殊點上被迫停止執(zhí)行直到接收到一個對應的特殊變量值，這種特殊變量就是信到一個對應的特殊變量值，這種特殊變量就是信號量號量(semaphore)(semaphore)，復雜的進程合作需求都可以，復雜的進程合作需求都可以通過適當?shù)男盘柦Y構得到滿足。通過適當?shù)男盘柦Y構得到滿足。40信號量與信號量與PVPV操作操作(3)(3) 操作系統(tǒng)中，信號量表示物理資源的實體，它是操作系統(tǒng)中，信號量表示物理資源的實體，它是一個與隊列有關的整型變量。一個與隊列有關的整型變量。 實現(xiàn)時，信號量是一種記錄型數(shù)據(jù)結構，有兩個實現(xiàn)時，信號量是一

36、種記錄型數(shù)據(jù)結構，有兩個分量：一個是信號量的值，另一個是信號量隊列分量：一個是信號量的值，另一個是信號量隊列的隊列指針。的隊列指針。信號量的值信號量的值(-2)(-2) 信號量隊列指針信號量隊列指針41信號量分類信號量分類信號量按其用途分為信號量按其用途分為公用信號量：用戶實現(xiàn)進程互斥，初值為公用信號量：用戶實現(xiàn)進程互斥，初值為1 1，相，相關進程均可在此信號量上執(zhí)行關進程均可在此信號量上執(zhí)行PVPV操作；操作；私有信號量：多用于并發(fā)進程同步，初值為私有信號量：多用于并發(fā)進程同步，初值為0 0或或正整數(shù)，僅允許此信號量所擁有的進程執(zhí)行正整數(shù)，僅允許此信號量所擁有的進程執(zhí)行P P操操作，而其它相

37、關進程可執(zhí)行作，而其它相關進程可執(zhí)行V V操作。操作。信號量按其取值分為信號量按其取值分為二元信號量二元信號量：僅允許取值為：僅允許取值為0 0或或1 1，主要用于解，主要用于解決互斥問題；決互斥問題；一般信號量：允許取大于一般信號量：允許取大于1 1的整型值，主要用于的整型值，主要用于解決同步問題。解決同步問題。42一般信號量一般信號量(1)(1) 設設s s為一個記錄型數(shù)據(jù)結構為一個記錄型數(shù)據(jù)結構, ,一個分量為整一個分量為整形量形量value,value,另一個為信號量隊列另一個為信號量隊列queue, Pqueue, P和和V V操作原語定義：操作原語定義： P(s)P(s)；將信號量

38、；將信號量s s減去減去l l，若結果小于，若結果小于0 0，則調用則調用P(s)P(s)的進程被置成等待信號量的進程被置成等待信號量s s的狀的狀態(tài)。態(tài)。 V(s)V(s)：將信號量：將信號量s s加加1 1，若結果不大于，若結果不大于0 0，則釋放一個等待信號量則釋放一個等待信號量s s的進程。的進程。43一般信號量一般信號量(2)(2) typedef structtypedef struct semaphore semaphore intint value; / value; /信號量值信號量值struct pcbstruct pcb * *list; /list; /信號量隊列指針信

39、號量隊列指針 ; ; void P(semaphorevoid P(semaphore &s) &s) s.value s.value-; -; if(s.value if(s.value0) 0) W(s.list W(s.list); ); void V(semaphorevoid V(semaphore &s) &s) s.values.value+; +; if(s.value if(s.value=0) =0) R(s.list R(s.list);); 44一般信號量一般信號量(3)(3) 推論推論1 1：若信號量：若信號量s s為正值，則該值等于在封鎖進為正值，則該值等于在封鎖進

40、程之前對信號量程之前對信號量s s可施行的可施行的P P操作數(shù)、亦等于操作數(shù)、亦等于s s所所代表的實際還可以使用的物理資源數(shù)代表的實際還可以使用的物理資源數(shù) 推論推論2 2：若信號量：若信號量s s為負值，則其絕對值等于登記為負值，則其絕對值等于登記排列在該信號量排列在該信號量s s隊列之中等待的進程個數(shù)、亦隊列之中等待的進程個數(shù)、亦即恰好等于對信號量即恰好等于對信號量s s實施實施P P操作而被封鎖起來并操作而被封鎖起來并進入信號量進入信號量s s隊列的進程數(shù)隊列的進程數(shù) 推論推論3 3：通常，：通常，P P操作意味著請求一個資源，操作意味著請求一個資源，V V操操作意味著釋放一個資源。在

41、一定條件下，作意味著釋放一個資源。在一定條件下，P P操作操作代表掛起進程操作，而代表掛起進程操作，而V V操作代表喚醒被掛起進操作代表喚醒被掛起進程的操作程的操作453.3.3 3.3.3 信號量實現(xiàn)互斥信號量實現(xiàn)互斥 semaphore mutexsemaphore mutex; ; mutex mutex=1;=1; cobegin cobegin process Pi( ) /i=1, process Pi( ) /i=1,n,n P(mutexP(mutex);); 臨界區(qū)臨界區(qū); V(mutexV(mutex);); coend coend463.3.4 3.3.4 信號量解決五個

42、哲學家吃通心面問題信號量解決五個哲學家吃通心面問題(1)(1) 有五個哲學家圍坐在一圓桌旁，桌中央有一盤通有五個哲學家圍坐在一圓桌旁，桌中央有一盤通心面，每人面前有一只空盤子，每兩人之間放一心面，每人面前有一只空盤子，每兩人之間放一把叉子。每個哲學家思考、饑餓、然后吃通心面把叉子。每個哲學家思考、饑餓、然后吃通心面。為了吃面，每個哲學家必須獲得兩把叉子，且。為了吃面，每個哲學家必須獲得兩把叉子，且每人只能直接從自己左邊或右邊去取叉子。每人只能直接從自己左邊或右邊去取叉子。47 信號量解決五個哲學家吃通心面問題信號量解決五個哲學家吃通心面問題(2)(2)48哲學哲學家吃家吃通通心心面問面問題題(

43、3)(3)semaphore fork5;semaphore fork5;for (intfor (int i=0;i5;i+) i=0;i5;i+)forkiforki=1;=1;cobegincobeginprocess philosopher_iprocess philosopher_i( ) ( ) /i= 0,1,2,3,4 /i= 0,1,2,3,4while(truewhile(true) ) think( ); think( ); P(forkiP(forki);); P(fork(i+1)%5);P(fork(i+1)%5); eat( ); eat( ); V(forkiV

44、(forki);); V(fork(i+1)%5);V(fork(i+1)%5); coendcoend可能死鎖！可能死鎖！49有若干種辦法可避免這類死有若干種辦法可避免這類死鎖鎖l上述解法可能出現(xiàn)永遠等待，有若干種辦上述解法可能出現(xiàn)永遠等待，有若干種辦法可避免死法可避免死鎖：鎖：l至多允許四個哲學家同時吃；至多允許四個哲學家同時吃；l奇數(shù)號先取左手邊的叉子，偶數(shù)號先取右手邊奇數(shù)號先取左手邊的叉子，偶數(shù)號先取右手邊的叉子；的叉子；l每個哲學家取到手邊的兩把叉子才吃，否則一每個哲學家取到手邊的兩把叉子才吃，否則一把叉子也不取。把叉子也不取。503.3.5 3.3.5 信號量解決生產者消費者問題信

45、號量解決生產者消費者問題一個生產者、一個消費者共享一個緩沖區(qū)一個生產者、一個消費者共享一個緩沖區(qū)一個生產者、一個消費者共享多個緩沖區(qū)一個生產者、一個消費者共享多個緩沖區(qū)多個生產者、多個消費者共享多個緩沖區(qū)多個生產者、多個消費者共享多個緩沖區(qū)51一個生產者、一個消費者共享一個緩沖區(qū)的解一個生產者、一個消費者共享一個緩沖區(qū)的解 intint B; B; semaphore empty; /semaphore empty; /可以使用的空緩沖區(qū)數(shù)可以使用的空緩沖區(qū)數(shù) semaphore full; /semaphore full; /緩沖區(qū)內可以使用的產品數(shù)緩沖區(qū)內可以使用的產品數(shù) empty=1;

46、 /empty=1; /緩沖區(qū)內允許放入一件產品緩沖區(qū)內允許放入一件產品 full=0; /full=0; /緩沖區(qū)內沒有產品緩沖區(qū)內沒有產品52 cobegincobegin process producer() process consumer()process producer() process consumer() while(true while(true) while(true) while(true) ) produce( ); produce( ); P(fullP(full););P(empty);P(empty); take( ) from B; take( ) from

47、 B;append( ) to B; append( ) to B; V(emptyV(empty););V(full);V(full); consume( ); consume( ); coendcoend53多個生產者多個生產者/ /消費者、共享多個緩沖區(qū)的解消費者、共享多個緩沖區(qū)的解 item Bkitem Bk; semaphore empty;semaphore empty;empty=k; empty=k; / /可以使用的空緩沖區(qū)數(shù)可以使用的空緩沖區(qū)數(shù) semaphore full; full=0; semaphore full; full=0; / /緩沖區(qū)內可以使用的產品數(shù)緩

48、沖區(qū)內可以使用的產品數(shù) semaphore mutex;semaphore mutex;mutexmutex=1; /=1; /互斥信號量互斥信號量 intint in=0; in=0;/放入緩沖區(qū)指針放入緩沖區(qū)指針 intint out=0; / out=0; /取出緩沖區(qū)指針取出緩沖區(qū)指針54cobegincobeginprocess producer_i ( ) process consumer_j ( ) process producer_i ( ) process consumer_j ( ) while(true while(true) while(true) while(true

49、) ) produce( ); produce( ); P(fullP(full);); P(emptyP(empty);); P(mutexP(mutex);); P(mutexP(mutex);); take( ) from Bout take( ) from Bout; append to Bin append to Bin; out=(out+1)%k; out=(out+1)%k; in=(in+1)%k; in=(in+1)%k; V(mutexV(mutex);); V(mutexV(mutex);); V(emptyV(empty);); V(fullV(full);); co

50、nsume( ); consume( ); coendcoend553.3.6 3.3.6 信號量解決讀者信號量解決讀者- -寫者問題寫者問題(1)(1) 有兩組并發(fā)進程：讀者和寫者，共享一個文件有兩組并發(fā)進程：讀者和寫者，共享一個文件F F，要求：，要求： 允許多個讀者同時執(zhí)行讀操作允許多個讀者同時執(zhí)行讀操作 任一寫者在完成寫操作之前不允許其它讀者或寫任一寫者在完成寫操作之前不允許其它讀者或寫者工作者工作 寫者執(zhí)行寫操作前，應讓已有的寫者和讀者全部寫者執(zhí)行寫操作前，應讓已有的寫者和讀者全部退出退出56信號量解決讀者寫者問題信號量解決讀者寫者問題(2)(2) int readcountint

51、readcount=0;/=0;/讀進程計數(shù)讀進程計數(shù) semaphore semaphore writeblock,mutexwriteblock,mutex; ; writeblockwriteblock=1;mutex=1;=1;mutex=1;57信號量解決讀者寫者問題信號量解決讀者寫者問題(3)(3)cobegincobeginprocess reader_iprocess reader_i( ) ( ) process writer_jprocess writer_j( )( ) P(mutexP(mutex);); P(writeblockP(writeblock);); rea

52、dcountreadcount+; +; 寫文件寫文件; if(readcount if(readcount=1) =1) V(writeblockV(writeblock);); P(writeblockP(writeblock); ); V(mutexV(mutex); ); 讀文件讀文件; P(mutexP(mutex););readcountreadcount-;-;if(readcountif(readcount=0)=0) V(writeblockV(writeblock);); V(mutex V(mutex);); coendcoend583.3.7 3.3.7 信號量解決理發(fā)

53、師問題信號量解決理發(fā)師問題(1)(1) 理發(fā)店里有一位理發(fā)師、一把理發(fā)椅和理發(fā)店里有一位理發(fā)師、一把理發(fā)椅和n n把供等把供等候理發(fā)的顧客坐的椅子候理發(fā)的顧客坐的椅子 如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺 一個顧客到來時，它必須叫醒理發(fā)師一個顧客到來時，它必須叫醒理發(fā)師 如果理發(fā)師正在理發(fā)時又有顧客來到，則如果有如果理發(fā)師正在理發(fā)時又有顧客來到，則如果有空椅子可坐，就坐下來等待，否則就離開空椅子可坐，就坐下來等待，否則就離開59信號量解決理發(fā)師問題信號量解決理發(fā)師問題(2)(2) intint waiting=0;/ waiting=0;/等候理發(fā)顧客坐的椅

54、子等候理發(fā)顧客坐的椅子數(shù)數(shù) intint CHAIRS=N; / CHAIRS=N; /為顧客準備的椅子數(shù)為顧客準備的椅子數(shù) semaphore customers,barbers,mutexsemaphore customers,barbers,mutex; ; customers=0;barbers=0;mutex=1;customers=0;barbers=0;mutex=1;60信號量解決理發(fā)師問題信號量解決理發(fā)師問題(3)(3) cobegincobegin process barber( ) process barber( ) while(true while(true) ) P(

55、customersP(customers);); / /有顧客嗎？若無顧客，理發(fā)師睡眠有顧客嗎？若無顧客，理發(fā)師睡眠 P(mutexP(mutex);); / /若有顧客時，進入臨界區(qū)若有顧客時，進入臨界區(qū)waiting-; /waiting-; /等候顧客數(shù)少一個等候顧客數(shù)少一個 V(barbersV(barbers);); / /理發(fā)師準備為顧客理發(fā)理發(fā)師準備為顧客理發(fā) V(mutexV(mutex);); / /退出臨界區(qū)退出臨界區(qū)cut_haircut_hair(); /(); /理發(fā)師正在理發(fā)理發(fā)師正在理發(fā)( (非臨界區(qū)非臨界區(qū)) ) 61process customer_iproc

56、ess customer_i( ) ( ) P(mutexP(mutex);); / /進入臨界區(qū)進入臨界區(qū) if(waitingif(waitingCHAIRS) /CHAIRS) /有空椅子嗎有空椅子嗎waiting+; /waiting+; /等候顧客數(shù)加等候顧客數(shù)加1 1 V(customersV(customers);); / /喚醒理發(fā)師喚醒理發(fā)師 V(mutexV(mutex);); / /退出臨界區(qū)退出臨界區(qū) P(barbersP(barbers);); / /理發(fā)師忙，顧客坐下等待理發(fā)師忙，顧客坐下等待get_haircutget_haircut(); /(); /否則顧客坐

57、下理發(fā)否則顧客坐下理發(fā) else else V(mutexV(mutex);); / /人滿了，走吧！人滿了，走吧！ coendcoend62總結補充總結補充 信號量小結信號量小結 P P、V V操作小結操作小結 針對信號量問題的補充練習針對信號量問題的補充練習631 1、信號量小結、信號量小結v 一個信號量可用于一個信號量可用于n n個進程的同步互斥；且只能由個進程的同步互斥；且只能由P P、V V操操作修改。作修改。用于互斥時，用于互斥時，S S初值為初值為1 1，取值為，取值為1 - (n-1) 1 - (n-1) （相當于臨界區(qū)的通行證，實際上也是資源個數(shù)）（相當于臨界區(qū)的通行證，實際

58、上也是資源個數(shù)） S=1S=1：臨界區(qū)可用：臨界區(qū)可用 S=0S=0：已有一進程進入臨界區(qū)：已有一進程進入臨界區(qū) S0S=0=0 S=0:S=0:表示可用資源個數(shù)表示可用資源個數(shù) S0:S0: 表示該資源的等待隊列長度表示該資源的等待隊列長度642 2、P P、V V操作小結操作小結P(S)P(S)：請求分配一個資源。：請求分配一個資源。V(S)V(S)：釋放一個資源。：釋放一個資源。P P、V V操作必須成對出現(xiàn)。操作必須成對出現(xiàn)。 用于互斥時，位于同一進程內；用于互斥時，位于同一進程內； 用于同步時，交錯出現(xiàn)于兩個合作進程內。用于同步時，交錯出現(xiàn)于兩個合作進程內。多個多個P P操作的次序不

59、能顛倒，否則可能導致死鎖。操作的次序不能顛倒，否則可能導致死鎖。 多個多個V V操作的次序可任意。操作的次序可任意。653 3、針對信號量問題的補充練習、針對信號量問題的補充練習1)1) 桌子上有一個盤子，可以存放一個水果。父親總桌子上有一個盤子，可以存放一個水果。父親總是放蘋果到盤子中，而母親總是放香蕉到盤子中是放蘋果到盤子中，而母親總是放香蕉到盤子中；兒子專等吃盤中的香蕉，而女兒專等吃盤中的；兒子專等吃盤中的香蕉，而女兒專等吃盤中的蘋果。蘋果。 分析：生產者消費者問題的一種變形，生產者、消費分析：生產者消費者問題的一種變形，生產者、消費者以及放入緩沖區(qū)的產品都有兩類，但每類消費者只消者以及

60、放入緩沖區(qū)的產品都有兩類，但每類消費者只消費其中固定的一種產品。費其中固定的一種產品。 數(shù)據(jù)結構：數(shù)據(jù)結構：semaphore dishsemaphore dish， apple apple ， banana ;banana ; dishdish：表示盤子是否為空，初值為：表示盤子是否為空，初值為1 1 appleapple：表示盤中是否有蘋果，初值為：表示盤中是否有蘋果，初值為0 0 bananabanana：表示盤中是否有香蕉，初值為：表示盤中是否有香蕉，初值為0 066cobegincobeginprocess father()process father() P(dish P(dish

61、);); 將蘋果放到盤中；將蘋果放到盤中； V(appleV(apple);); process mother()process mother() P(dish P(dish);); 將香蕉放到盤中；將香蕉放到盤中； V(bananaV(banana);); process son()process son() P(banana P(banana);); 從盤中取出香蕉；從盤中取出香蕉； V(dishV(dish);); process daughter()process daughter() P(apple P(apple);); 從盤中取出蘋果；從盤中取出蘋果； V(dishV(dish)

62、;); coendcoend. .672) 哲學家甲請哲學家乙、丙、丁到某處討論問題，約定全哲學家甲請哲學家乙、丙、丁到某處討論問題，約定全體到齊后開始討論；在討論的間隙四位哲學家進餐，每體到齊后開始討論；在討論的間隙四位哲學家進餐，每人進餐時都需使用刀、叉各一把，餐桌上的布置如下圖人進餐時都需使用刀、叉各一把，餐桌上的布置如下圖所示。用信號量機制說明四位哲學家的同步互斥過程。所示。用信號量機制說明四位哲學家的同步互斥過程。食品食品乙乙丙丙丁丁甲甲刀刀2叉叉1刀刀1叉叉268 分析分析 標準的哲學家進餐問題，只是哲學家人數(shù)和標準的哲學家進餐問題，只是哲學家人數(shù)和餐具及分布與經(jīng)典哲學家進餐問題略

63、有不同餐具及分布與經(jīng)典哲學家進餐問題略有不同 數(shù)據(jù)結構數(shù)據(jù)結構 semaphore fork1,fork2,knife1,knife2;semaphore fork1,fork2,knife1,knife2; frokfrok表示叉，表示叉，knifeknife表示刀，初值均為表示刀，初值均為1 169cobegincobeginprocess pa() process pa() /哲學家甲哲學家甲 P(knife1);P(knife1); P(fork1); P(fork1); 進餐；進餐； V(knife1);V(knife1); V(fork1); V(fork1); 討論問題；討論問題

64、； process pb() /哲學家乙哲學家乙 P(knife2);P(knife2); P(fork1); P(fork1); 進餐；進餐； V(knife2);V(knife2); V(fork1); V(fork1); 討論問題；討論問題； 70process pc() /哲學家丙哲學家丙 P(knife2);P(knife2); P(fork2); P(fork2); 進餐；進餐； V(knife2);V(knife2); V(fork2); V(fork2); 討論問題；討論問題； process pd() /哲學家丁哲學家丁 P(knife1);P(knife1); P(fork

65、2); P(fork2); 進餐；進餐； V(knife1);V(knife1); V(fork2); V(fork2); 討論問題；討論問題； coend.713)3) 有一個閱覽室，讀者進入時必須先在一張登記有一個閱覽室，讀者進入時必須先在一張登記表上登記，此表為每個座位列出一個表目，包表上登記，此表為每個座位列出一個表目，包括座位號、姓名，讀者離開時要注意注銷登記括座位號、姓名，讀者離開時要注意注銷登記信息；假如閱覽室共有信息；假如閱覽室共有100100個座位，請用信號量個座位，請用信號量和和P P、V V操作實現(xiàn)用戶進程的同步算法。操作實現(xiàn)用戶進程的同步算法。72 分析：實際上是一個非

66、常簡單的同步分析：實際上是一個非常簡單的同步- -互斥問題，不要互斥問題，不要想復雜了想復雜了 數(shù)據(jù)結構：數(shù)據(jù)結構： structcharstructchar name10; name10; int int number; number; A100; A100; semaphore mutex, seatcountsemaphore mutex, seatcount; ; mutexmutex：用來互斥，初值為：用來互斥，初值為1 1 seatcountseatcount：對空座位計數(shù)，初值為：對空座位計數(shù)，初值為100100 for(intfor(int i=0;i100;i+) i=0;i100;i+) Ai.number=i; Ai.name Ai.number=i; Ai.name=null;=null;73cobegincobeginprocess readeri(char readernameprocess readeri(char readername) P(seatcount P(seatcount);); P(mutex P(mutex) )； for(intfor(