教學(xué)課件PPT 同步、通信與死鎖

《教學(xué)課件PPT 同步、通信與死鎖》由會(huì)員分享，可在線閱讀，更多相關(guān)《教學(xué)課件PPT 同步、通信與死鎖（146頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

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

3、設(shè)計(jì)的缺點(diǎn)順序程序設(shè)計(jì)的缺點(diǎn)計(jì)算機(jī)系統(tǒng)效率不高。計(jì)算機(jī)系統(tǒng)效率不高。53.1.2 3.1.2 進(jìn)程的并發(fā)性進(jìn)程的并發(fā)性1 1、并發(fā)程序設(shè)計(jì)、并發(fā)程序設(shè)計(jì) 進(jìn)程執(zhí)行的并發(fā)性：一組進(jìn)程的執(zhí)行在時(shí)間上是進(jìn)程執(zhí)行的并發(fā)性：一組進(jìn)程的執(zhí)行在時(shí)間上是重疊的。重疊的。 并發(fā)性舉例：有兩個(gè)進(jìn)程并發(fā)性舉例：有兩個(gè)進(jìn)程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í)行 從宏觀上看，一個(gè)時(shí)間段中幾個(gè)進(jìn)

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

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

6、互的并發(fā)進(jìn)程交互的并發(fā)進(jìn)程0一組并發(fā)進(jìn)程共享某些變量，一個(gè)進(jìn)程的執(zhí)行一組并發(fā)進(jìn)程共享某些變量，一個(gè)進(jìn)程的執(zhí)行可能影響其他并發(fā)進(jìn)程的結(jié)果?？赡苡绊懫渌l(fā)進(jìn)程的結(jié)果。 10BernsteinBernstein條件條件 R(piR(pi)=a1,a2,)=a1,a2,anan，程序，程序pipi在執(zhí)行期間引用的在執(zhí)行期間引用的變量集變量集W(piW(pi)=b1,b2,)=b1,b2,bmbm ，程序，程序pipi在執(zhí)行期間改變的在執(zhí)行期間改變的變量集變量集若兩個(gè)程序的變量集交集之和為空集若兩個(gè)程序的變量集交集之和為空集： 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ā)進(jìn)程的執(zhí)行與時(shí)間無(wú)關(guān)。則并發(fā)進(jìn)程的執(zhí)行與時(shí)間無(wú)關(guān)。11BernsteinBernstein條件舉例條件舉例例如，有如下四條語(yǔ)句：例如，有如下四條語(yǔ)句： 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條件條件。其他語(yǔ)句并發(fā)執(zhí)行可能會(huì)產(chǎn)生與時(shí)間有。其他語(yǔ)句并發(fā)執(zhí)行可能會(huì)產(chǎn)生與時(shí)間有關(guān)的錯(cuò)誤。關(guān)的錯(cuò)誤。12并發(fā)程序設(shè)計(jì)的優(yōu)點(diǎn)并發(fā)程序設(shè)計(jì)的優(yōu)點(diǎn)l對(duì)于單處理器系統(tǒng)對(duì)于單處理器系統(tǒng), ,可讓處理器和各可讓處理器和各I/OI/O設(shè)設(shè)備同時(shí)工作備同時(shí)工作, ,發(fā)揮硬部件的并行能力。發(fā)揮硬部件的并行能力。l對(duì)于多處理器系統(tǒng)對(duì)于多處理器系統(tǒng), ,可讓各進(jìn)程在不同處可讓各進(jìn)程在不同處理器上物理地并行，

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

10、43 3、與時(shí)間有關(guān)的錯(cuò)誤、與時(shí)間有關(guān)的錯(cuò)誤 對(duì)于一組交互的并發(fā)進(jìn)程，執(zhí)行的相對(duì)速對(duì)于一組交互的并發(fā)進(jìn)程，執(zhí)行的相對(duì)速度無(wú)法相互控制，各種與時(shí)間有關(guān)的錯(cuò)誤度無(wú)法相互控制，各種與時(shí)間有關(guān)的錯(cuò)誤就可能出現(xiàn)。就可能出現(xiàn)。 與時(shí)間有關(guān)錯(cuò)誤的表現(xiàn)形式：與時(shí)間有關(guān)錯(cuò)誤的表現(xiàn)形式：0結(jié)果不唯一結(jié)果不唯一0永遠(yuǎn)等待永遠(yuǎn)等待15（結(jié)果不唯一）機(jī)票問(wèn)題（結(jié)果不唯一）機(jī)票問(wèn)題/飛機(jī)票售票問(wèn)題飛機(jī)票售票問(wèn)題 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（永遠(yuǎn)等待）主存管理問(wèn)題（永遠(yuǎn)等待）主存管理問(wèn)題申請(qǐng)和歸還主存資源問(wèn)題申請(qǐng)和歸還主存資源問(wèn)題 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; 進(jìn)程進(jìn)入等待主存資源隊(duì)列進(jìn)程進(jìn)入等待主存資源隊(duì)列; ; 修改主存分配表修改主存分配表; X=X-B ; X=X-B ; 釋放等主存資源進(jìn)程釋放等主存資源進(jìn)程; ; 修改主存分配表，修改主存分配表， 進(jìn)程獲得主存資源進(jìn)程獲得主存資源; ; 18若對(duì)若對(duì)borrowborrow和和returnreturn的并發(fā)執(zhí)行不加限制將會(huì)導(dǎo)致的并發(fā)執(zhí)行不加限制將會(huì)導(dǎo)致錯(cuò)誤，例如：錯(cuò)誤，例如：Borrow:while

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

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

16、關(guān)系第二種是協(xié)作關(guān)系l某些進(jìn)程為完成同一任務(wù)需要分工協(xié)作。某些進(jìn)程為完成同一任務(wù)需要分工協(xié)作。l進(jìn)程進(jìn)程同步同步指為完成共同任務(wù)的并發(fā)進(jìn)程基于某個(gè)指為完成共同任務(wù)的并發(fā)進(jìn)程基于某個(gè)條件來(lái)協(xié)調(diào)它們的活動(dòng)，因?yàn)樾枰谀承┪恢蒙蠗l件來(lái)協(xié)調(diào)它們的活動(dòng)，因?yàn)樾枰谀承┪恢蒙吓哦▓?zhí)行的先后次序而等待、傳遞信號(hào)或消息所排定執(zhí)行的先后次序而等待、傳遞信號(hào)或消息所產(chǎn)生的協(xié)作制約關(guān)系。產(chǎn)生的協(xié)作制約關(guān)系。l進(jìn)程同步指兩個(gè)以上進(jìn)程基于某個(gè)條件來(lái)協(xié)調(diào)它們的進(jìn)程同步指兩個(gè)以上進(jìn)程基于某個(gè)條件來(lái)協(xié)調(diào)它們的活動(dòng)。一個(gè)進(jìn)程的執(zhí)行依賴于協(xié)作進(jìn)程的消息或信號(hào)活動(dòng)。一個(gè)進(jìn)程的執(zhí)行依賴于協(xié)作進(jìn)程的消息或信號(hào)，當(dāng)一個(gè)進(jìn)程沒(méi)有得到來(lái)自于

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

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

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

20、.2 3.2.2 臨界區(qū)管理的嘗試臨界區(qū)管理的嘗試 (1)(1) bool inside1=false; /P1bool inside1=false; /P1不在其臨界區(qū)內(nèi)不在其臨界區(qū)內(nèi) boolbool inside2=false; /P2 inside2=false; /P2不在其臨界區(qū)內(nèi)不在其臨界區(qū)內(nèi) cobegin /cobegin /* *cobegincobegin和和coendcoend表示括號(hào)中的進(jìn)程是一組并表示括號(hào)中的進(jìn)程是一組并發(fā)進(jìn)程發(fā)進(jìn)程* */ / 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ū)內(nèi)不在其臨界區(qū)內(nèi) boolbool inside2=false; /P2 inside2=false; /P2不在其臨界區(qū)內(nèi)不在其臨界區(qū)內(nèi) 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實(shí)現(xiàn)臨界區(qū)的軟件算法實(shí)現(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 實(shí)現(xiàn)臨界區(qū)管理的硬件設(shè)施實(shí)現(xiàn)臨界區(qū)管理的硬件設(shè)施 關(guān)中斷關(guān)中斷 測(cè)試并建立指令（刪）測(cè)試并建立指令（刪） 對(duì)換指令（刪）對(duì)換指令（刪）30關(guān)中斷關(guān)中斷 實(shí)現(xiàn)互斥的最簡(jiǎn)單方法實(shí)現(xiàn)互斥的最簡(jiǎn)單方法 關(guān)中斷適用場(chǎng)合關(guān)中斷適用場(chǎng)合0簡(jiǎn)單有效，對(duì)操作系統(tǒng)自身有用，可在更新共享變量簡(jiǎn)單有效，對(duì)操作系統(tǒng)自身有用，可在更新共享變量或列表的幾條指令期間禁止中斷?；蛄斜淼膸讞l指令期間禁止中斷。 關(guān)中斷方法的缺點(diǎn)關(guān)中斷方法的缺點(diǎn)0不適合作為通用的互斥機(jī)制，關(guān)中斷時(shí)間過(guò)長(zhǎng)會(huì)影響不適合作

26、為通用的互斥機(jī)制，關(guān)中斷時(shí)間過(guò)長(zhǎng)會(huì)影響性能和系統(tǒng)效率；性能和系統(tǒng)效率；0不適應(yīng)于多處理器計(jì)算機(jī)系統(tǒng)，因?yàn)橐粋€(gè)處理器關(guān)中不適應(yīng)于多處理器計(jì)算機(jī)系統(tǒng)，因?yàn)橐粋€(gè)處理器關(guān)中斷，并不能防止進(jìn)程在其它處理器上執(zhí)行相同的臨界斷，并不能防止進(jìn)程在其它處理器上執(zhí)行相同的臨界段代碼；段代碼；0若將這項(xiàng)權(quán)力賦予用戶會(huì)存在危險(xiǎn)，若用戶未開(kāi)中斷若將這項(xiàng)權(quán)力賦予用戶會(huì)存在危險(xiǎn)，若用戶未開(kāi)中斷，則系統(tǒng)可能因此而終止。，則系統(tǒng)可能因此而終止。313.3 3.3 信號(hào)量信號(hào)量與與PVPV操作操作3.3.1 3.3.1 同步與同步機(jī)制同步與同步機(jī)制3.3.2 3.3.2 信號(hào)量與信號(hào)量與PVPV操作操作3.3.3 3.3.3 信

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

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

29、沖區(qū)不空，消費(fèi)者進(jìn)程cjcj就可從緩沖區(qū)取就可從緩沖區(qū)取走并消耗產(chǎn)品。走并消耗產(chǎn)品。34生產(chǎn)者生產(chǎn)者- -消費(fèi)者問(wèn)題算法描述消費(fèi)者問(wèn)題算法描述(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生產(chǎn)者生產(chǎn)者- -消費(fèi)者問(wèn)題算法描述消費(fèi)者問(wèn)題算法描述(2)(2) process producer(voidprocess producer(

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

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

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

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

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

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

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

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

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

39、號(hào)量隊(duì)列指針 ; ; 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一般信號(hào)量一般信號(hào)量(3)(3) 推論推論1 1：若信號(hào)量：若信號(hào)量s s為正值，則該值等于在封鎖進(jìn)為正值，則該值等于在封鎖進(jìn)

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

41、一定條件下，作意味著釋放一個(gè)資源。在一定條件下，P P操作操作代表掛起進(jìn)程操作，而代表掛起進(jìn)程操作，而V V操作代表喚醒被掛起進(jìn)操作代表喚醒被掛起進(jìn)程的操作程的操作453.3.3 3.3.3 信號(hào)量實(shí)現(xiàn)互斥信號(hào)量實(shí)現(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 信號(hào)量解決五個(gè)

42、哲學(xué)家吃通心面問(wèn)題信號(hào)量解決五個(gè)哲學(xué)家吃通心面問(wèn)題(1)(1) 有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤(pán)通有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤(pán)通心面，每人面前有一只空盤(pán)子，每?jī)扇酥g放一心面，每人面前有一只空盤(pán)子，每?jī)扇酥g放一把叉子。每個(gè)哲學(xué)家思考、饑餓、然后吃通心面把叉子。每個(gè)哲學(xué)家思考、饑餓、然后吃通心面。為了吃面，每個(gè)哲學(xué)家必須獲得兩把叉子，且。為了吃面，每個(gè)哲學(xué)家必須獲得兩把叉子，且每人只能直接從自己左邊或右邊去取叉子。每人只能直接從自己左邊或右邊去取叉子。47 信號(hào)量解決五個(gè)哲學(xué)家吃通心面問(wèn)題信號(hào)量解決五個(gè)哲學(xué)家吃通心面問(wèn)題(2)(2)48哲學(xué)哲學(xué)家吃家吃通通心心面問(wèn)面問(wèn)題題(

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)永遠(yuǎn)等待，有若干種辦上述解法可能出現(xiàn)永遠(yuǎn)等待，有若干種辦法可避免死法可避免死鎖：鎖：l至多允許四個(gè)哲學(xué)家同時(shí)吃；至多允許四個(gè)哲學(xué)家同時(shí)吃；l奇數(shù)號(hào)先取左手邊的叉子，偶數(shù)號(hào)先取右手邊奇數(shù)號(hào)先取左手邊的叉子，偶數(shù)號(hào)先取右手邊的叉子；的叉子；l每個(gè)哲學(xué)家取到手邊的兩把叉子才吃，否則一每個(gè)哲學(xué)家取到手邊的兩把叉子才吃，否則一把叉子也不取。把叉子也不取。503.3.5 3.3.5 信號(hào)量解決生產(chǎn)者消費(fèi)者問(wèn)題信

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

46、 /empty=1; /緩沖區(qū)內(nèi)允許放入一件產(chǎn)品緩沖區(qū)內(nèi)允許放入一件產(chǎn)品 full=0; /full=0; /緩沖區(qū)內(nèi)沒(méi)有產(chǎn)品緩沖區(qū)內(nèi)沒(méi)有產(chǎn)品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多個(gè)生產(chǎn)者多個(gè)生產(chǎn)者/ /消費(fèi)者、共享多個(gè)緩沖區(qū)的解消費(fèi)者、共享多個(gè)緩沖區(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ū)內(nèi)可以使用的產(chǎn)品數(shù)緩

48、沖區(qū)內(nèi)可以使用的產(chǎn)品數(shù) semaphore mutex;semaphore mutex;mutexmutex=1; /=1; /互斥信號(hào)量互斥信號(hào)量 intint in=0; in=0;/放入緩沖區(qū)指針?lè)湃刖彌_區(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 信號(hào)量解決讀者信號(hào)量解決讀者- -寫(xiě)者問(wèn)題寫(xiě)者問(wèn)題(1)(1) 有兩組并發(fā)進(jìn)程：讀者和寫(xiě)者，共享一個(gè)文件有兩組并發(fā)進(jìn)程：讀者和寫(xiě)者，共享一個(gè)文件F F，要求：，要求： 允許多個(gè)讀者同時(shí)執(zhí)行讀操作允許多個(gè)讀者同時(shí)執(zhí)行讀操作 任一寫(xiě)者在完成寫(xiě)操作之前不允許其它讀者或?qū)懭我粚?xiě)者在完成寫(xiě)操作之前不允許其它讀者或?qū)懻吖ぷ髡吖ぷ?寫(xiě)者執(zhí)行寫(xiě)操作前，應(yīng)讓已有的寫(xiě)者和讀者全部寫(xiě)者執(zhí)行寫(xiě)操作前，應(yīng)讓已有的寫(xiě)者和讀者全部退出退出56信號(hào)量解決讀者寫(xiě)者問(wèn)題信號(hào)量解決讀者寫(xiě)者問(wèn)題(2)(2) int readcountint

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

52、dcountreadcount+; +; 寫(xiě)文件寫(xiě)文件; 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 信號(hào)量解決理發(fā)

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

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

55、customersP(customers);); / /有顧客嗎？若無(wú)顧客，理發(fā)師睡眠有顧客嗎？若無(wú)顧客，理發(fā)師睡眠 P(mutexP(mutex);); / /若有顧客時(shí)，進(jìn)入臨界區(qū)若有顧客時(shí)，進(jìn)入臨界區(qū)waiting-; /waiting-; /等候顧客數(shù)少一個(gè)等候顧客數(shù)少一個(gè) V(barbersV(barbers);); / /理發(fā)師準(zhǔn)備為顧客理發(fā)理發(fā)師準(zhǔn)備為顧客理發(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);); / /進(jìn)入臨界區(qū)進(jìn)入臨界區(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總結(jié)補(bǔ)充總結(jié)補(bǔ)充 信號(hào)量小結(jié)信號(hào)量小結(jié) P P、V V操作小結(jié)操作小結(jié) 針對(duì)信號(hào)量問(wèn)題的補(bǔ)充練習(xí)針對(duì)信號(hào)量問(wèn)題的補(bǔ)充練習(xí)631 1、信號(hào)量小結(jié)、信號(hào)量小結(jié)v 一個(gè)信號(hào)量可用于一個(gè)信號(hào)量可用于n n個(gè)進(jìn)程的同步互斥；且只能由個(gè)進(jìn)程的同步互斥；且只能由P P、V V操操作修改。作修改。用于互斥時(shí)，用于互斥時(shí)，S S初值為初值為1 1，取值為，取值為1 - (n-1) 1 - (n-1) （相當(dāng)于臨界區(qū)的通行證，實(shí)際上也是資源個(gè)數(shù)）（相當(dāng)于臨界區(qū)的通行證，實(shí)際

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

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

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

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

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

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

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

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

66、常簡(jiǎn)單的同步分析：實(shí)際上是一個(gè)非常簡(jiǎn)單的同步- -互斥問(wèn)題，不要互斥問(wèn)題，不要想復(fù)雜了想復(fù)雜了 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)： structcharstructchar name10; name10; int int number; number; A100; A100; semaphore mutex, seatcountsemaphore mutex, seatcount; ; mutexmutex：用來(lái)互斥，初值為：用來(lái)互斥，初值為1 1 seatcountseatcount：對(duì)空座位計(jì)數(shù)，初值為：對(duì)空座位計(jì)數(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(