操作系統教程孫鐘秀主編高等教育出社同步通信與死鎖ppt3.1.1順序程序設計進程的順序性一個進程在順序處理器上的執行是嚴格按序的，一個進程只有當一個操作結束后，才能開始后繼操作。順序程序設計是把一個程序設計成一個順序執行的程序模塊，順序的含義不但指一個程序模塊內部，也指兩個程序模塊之間。2順序程序設計特點程序執行的順序性程序環境的封閉性程序執行結果的確定性計算過程的可再現性順序程序設計的缺點計算機系統效率不高。33.1.2進程的并發性1、并發程序設計進程執行的并發性：一組進程的執行在時間上是重疊的。并發性舉例：有兩個進程A(a1、a2、a3)和B(b1、b2、b3)并發執行。a1、a2、a3、b1、b2、b3順序執行a1、b1、a2、b2、a3、b3并發執行從宏觀上看，并發性反映一個時間段中幾個進程都在同一處理器上，處于運行還未運行結束狀態。從微觀上看，任一時刻僅有一個進程在處理器上運行。4并行工作圖示進程i1p1ipoo1i2p2o2i3p3o3t1t2t3時間并行工作i4t4i5P4t55并發的實質并發的實質是一個處理器在幾個進程之間的多路復用，并發是對有限的物理資源強制行使多用戶共享，消除計算機部件之間的互等現象，以提高系統資源利用率。62、并發進程的特性無關的并發進程一組并發進程分別在不同的變量集合上操作，一個進程的執行與其他并發進程的進展無關。并發進程的無關性是進程的執行與時間無關的一個充分條件，又稱為Bernstein條件。交往的并發進程一組并發進程共享某些變量，一個進程的執行可能影響其他并發進程的結果。7Bernstein條件

R(pi)={a1,a2,…an}，程序pi在執行期間引用的變量集W(pi)={b1,b2,…bm}，程序pi在執行期間改變的變量集若兩個程序的變量集交集之和為空集：R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)={}則并發進程的執行與時間無關。8Bernstein條件舉例例如，有如下四條語句：

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)={b}，W(S3)={c}，W(S4)={w}。S1和S2可并發執行，滿足Bernstein條件。其他語句并發執行可能會產生與時間有關的錯誤。9并發程序設計的優點對于單處理器系統,可讓處理器和各I/O設備同時工作,發揮硬部件的并行能力。對于多處理器系統,可讓各進程在不同處理器上物理地并行，加快計算速度。簡化了程序設計任務。

10采用并發程序設計的目的充分發揮硬件的并行性，提高系統效率。硬件能并行工作僅有了提高效率的可能性，硬部件并行性的實現需要軟件技術去利用和發揮，這種軟件技術就是并發程序設計。并發程序設計是多道程序設計的基礎，多道程序的實質就是把并發程序設計引入到系統中。113、與時間有關的錯誤對于一組交往的并發進程，執行的相對速度無法相互控制，各種與時間有關的錯誤就可能出現。與時間有關錯誤的表現形式：結果不唯一永遠等待12（結果不唯一）機票問題//飛機票售票問題voidT1(){voidT2(){{按旅客訂票要求找到Aj};{按旅客訂票要求找到Aj};intX1=Aj;intX2=Aj;if(X1>=1){if(X2>=1){ X1--;X2--;Aj=X1;Aj=X2; {輸出一張票};{輸出一張票}; }} elseelse{輸出信息"票已售完"};{輸出信息"票已售完"};}}13T1、T2并發執行，可能出現如下交叉情況：T1:X1=Aj;//X1=mT2:X2=Aj;//X2=mT2:X2--;Aj=X2;{輸出一張票};//Aj=m-1T1:X1--;Aj=X1;{輸出一張票};//Aj=m-1同一張票賣給兩位旅客14（永遠等待）主存管理問題申請和歸還主存資源問題intX=memory;//memory為初始主存容量voidborrow(intB){voidreturn(intB){while(B>X)X=X+B;{進程進入等待主存資源隊列};{修改主存分配表};X=X-B;{釋放等主存資源進程};{修改主存分配表，進程獲得主存資源};}}15若對borrow和return的并發執行不加限制將會導致錯誤，例如：Borrow:while(B>X);Return:X=X+B;{修改主存分配表};{釋放等待主存資源的進程}；此時，因為borrow還沒有進入等待隊列，因此，return的釋放操作是空操作，當borrow進入等待隊列時，可能沒有進程再來歸還，處于永遠等待狀態。163.1.3進程的交互：競爭與協作(1)

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

第二種是協作關系某些進程為完成同一任務需要分工協作。進程同步指為完成共同任務的并發進程基于某個條件來協調它們的活動，因為需要在某些位置上排定執行的先后次序而等待、傳遞信號或消息所產生的協作制約關系。進程同步指兩個以上進程基于某個條件來協調它們的活動。一個進程的執行依賴于協作進程的消息或信號，當一個進程沒有得到來自于協作進程的消息或信號時需等待，直到消息或信號到達才被喚醒。進程互斥關系是一種特殊的進程同步關系，即逐次使用互斥共享資源，是對進程使用資源次序上的一種協調。183.2臨界區管理3.2.1互斥與臨界區3.2.2實現臨界區管理的幾種嘗試3.2.3實現臨界區管理的軟件方法3.2.4實現臨界區管理的硬件設施193.2.1互斥與臨界區(1)并發進程中與共享變量有關的程序段叫“臨界區”，共享變量代表的資源叫“臨界資源”。與同一變量有關的臨界區分散在各進程的程序段中，而各進程的執行速度不可預知。如果保證進程在臨界區執行時，不讓另一個進程進入臨界區，即各進程對共享變量的訪問是互斥的，就不會造成與時間有關的錯誤。20互斥與臨界區(2)臨界區調度原則：一次至多一個進程能夠進入臨界區內執行；如果已有進程在臨界區，其他試圖進入的進程應等待；進入臨界區內的進程應在有限時間內退出，以便讓等待進程中的一個進入。臨界區調度原則總結：互斥使用、有空讓進；忙則等待、有限等待；擇一而入，算法可行。213.2.2臨界區管理的嘗試(1)boolinside1=false;//P1不在其臨界區內boolinside2=false;//P2不在其臨界區內cobegin/*cobegin和coend表示括號中的進程是一組并發進程*/processP1(){processP2(){while(inside2);//等待while(inside1);//等待inside1=true;inside2=true;{臨界區};{臨界區};inside1=false;inside2=false;}}coend可能不滿足互斥條件22臨界區管理的嘗試(2)boolinside1=false;//P1不在其臨界區內boolinside2=false;//P2不在其臨界區內cobeginprocessP1(){processP2(){inside1=true;inside2=true;while(inside2);//等待while(inside1);//等待 {臨界區};{臨界區};inside1=false;inside2=false;}}coend可能出現死循環233.2.3實現臨界區的軟件算法Peterson算法(1)boolinside[2];inside[0]=false;inside[1]=false;enum{0,1}turn;24Peterson算法(2)cobeginprocessP0(){inside[0]=true;turn=1;while(inside[1]&&turn==1); {臨界區}; inside[0]=false;}25Peterson算法(3)processP1(){inside[1]=true;turn=0;while(inside[0]&&turn==0); {臨界區};inside[1]=false;}coend263.2.4實現臨界區管理的硬件設施關中斷測試并建立指令對換指令27關中斷實現互斥的最簡單方法關中斷適用場合簡單有效，對操作系統自身有用，可在更新共享變量或列表的幾條指令期間禁止中斷。關中斷方法的缺點不適合作為通用的互斥機制，關中斷時間過長會影響性能和系統效率；不適應于多處理器計算機系統，因為一個處理器關中斷，并不能防止進程在其它處理器上執行相同的臨界段代碼；若將這項權力賦予用戶會存在危險，若用戶未開中斷，則系統可能因此而終止。28測試并建立指令(1)TS指令的處理過程boolTS(bool&x){if(x){ x=false; returntrue; }else returnfalse;}TS指令管理臨界區時，可把一個臨區與一個布爾變量s相連，由于變量s代表了臨界資源的狀態，可把它看成一把鎖。29測試并建立指令(2)TS指令實現進程互斥bools=true;cobeginprocessPi(){//i=1,2,...,n while(!TS(s));//上鎖 {臨界區}; s=true;//開鎖}coend30對換指令(1)voidSWAP(bool&a,bool&b){ booltemp=a; a=b; b=temp; }31對換指令(2)對換指令實現進程互斥boollock=false;cobeginProcessPi(){//i=1,2,...,n boolkeyi=true; do{SWAP(keyi,lock);}while(keyi);//上鎖 {臨界區}; SWAP(keyi,lock);//開鎖}coend323.3信號量與PV操作3.3.1同步與同步機制3.3.2信號量與PV操作3.3.3信號量實現互斥3.3.4信號量解決五個哲學家吃通心面問題3.3.5信號量解決生產者-消費者問題3.3.6記錄型信號量解決讀者-寫者問題3.3.7記錄型信號量解決理發師問題333.3.1同步和同步機制著名的生產者--消費者問題是計算機操作系統中并發進程內在關系的一種抽象，是典型的進程同步問題。在操作系統中，生產者進程可以是計算進程、發送進程；而消費者進程可以是打印進程、接收進程等等。解決好生產者--消費者問題就解決好了一類并發進程的同步問題。34生產者--消費者問題表述有界緩沖問題有n個生產者和m個消費者，連接在一個有k個單位緩沖區的有界緩沖上。其中，pi和cj都是并發進程，只要緩沖區未滿，生產者pi生產的產品就可投入緩沖區；只要緩沖區不空，消費者進程cj就可從緩沖區取走并消耗產品。35生產者-消費者問題算法描述(1)intk;typedefanyitemitem;//item類型itembuffer[k];intin=0,out=0,counter=0;36生產者-消費者問題算法描述(2)processproducer(void){while(true){//無限循環{produceaniteminnextp};//生產一個產品 if(counter==k)//緩沖滿時，生產者睡眠 sleep(producer); buffer[in]=nextp;//將一個產品放入緩沖區 in=(in+1)%k;//指針推進 counter++;//緩沖內產品數加1 if(counter==1)//緩沖為空，加進一件產品wakeup(consumer);//并喚醒消費者 }}37生產者-消費者問題算法描述(3)processconsumer(void){ while(true){//無限循環 if(counter==0)//緩沖區空，消費者睡眠 sleep(consumer); nextc=buffer[out];//取一個產品到nextc out=(out+1)%k;//指針推進 counter--;//取走一個產品，計數減1 if(counter==k-1)//緩沖滿了，取走一件產品并喚wakeup(producer);//醒生產者 {consumetheiteminnextc};//消耗產品 }}38生產者-消費者問題的算法描述(4)生產者和消費者進程對counter的交替執行會使其結果不唯一生產者和消費者進程的交替執行會導致進程永遠等待393.3.2信號量與PV操作(1)前節種種方法解決臨界區調度問題的缺點:1)對不能進入臨界區的進程，采用忙式等待測試法，浪費CPU時間。2)將測試能否進入臨界區的責任推給各個競爭的進程會削弱系統的可靠性，加重了用戶編程負擔。1965年E.W.Dijkstra提出了新的同步工具--信號量和P、V操作。

40信號量與PV操作(2)信號量：一種軟件資源原語：內核中執行時不可被中斷的過程P操作原語和V操作原語一個進程在某一特殊點上被迫停止執行直到接收到一個對應的特殊變量值，這種特殊變量就是信號量(semaphore)，復雜的進程合作需求都可以通過適當的信號結構得到滿足。41信號量與PV操作(3)操作系統中，信號量表示物理資源的實體，它是一個與隊列有關的整型變量。實現時，信號量是一種記錄型數據結構，有兩個分量：一個是信號量的值，另一個是信號量隊列的隊列指針。信號量的值(-2)

信號量隊列指針42信號量分類信號量按其用途分為公用信號量：用戶實現進程互斥，初值為1，相關進程均可在此信號量上執行PV操作；私有信號量：多用于并發進程同步，初值為0或正整數，僅允許此信號量所擁有的進程執行P操作，而其它相關進程可執行V操作。信號量按其取值分為二元信號量：僅允許取值為0或1，主要用于解決互斥問題；一般信號量：允許取大于1的整型值，主要用于解決同步問題。43一般信號量(1)

設s為一個記錄型數據結構,一個分量為整形量value,另一個為信號量隊列queue,P和V操作原語定義：P(s)；將信號量s減去l，若結果小于0，則調用P(s)的進程被置成等待信號量s的狀態。V(s)：將信號量s加1，若結果不大于0，則釋放一個等待信號量s的進程。44一般信號量(2)typedefstructsemaphore{ intvalue;//信號量值 structpcb*list;//信號量隊列指針};voidP(semaphore&s){ s.value--; if(s.value<0)W(s.list);}voidV(semaphore&s){ s.value++;if(s.value<=0)R(s.list);

}45一般信號量(3)推論1：若信號量s為正值，則該值等于在封鎖進程之前對信號量s可施行的P操作數、亦等于s所代表的實際還可以使用的物理資源數推論2：若信號量s為負值，則其絕對值等于登記排列在該信號量s隊列之中等待的進程個數、亦即恰好等于對信號量s實施P操作而被封鎖起來并進入信號量s隊列的進程數推論3：通常，P操作意味著請求一個資源，V操作意味著釋放一個資源。在一定條件下，P操作代表掛起進程操作，而V操作代表喚醒被掛起進程的操作46二元信號量(1)設s為一個記錄型數據結構,一個分量為value,它僅能取值0和1,另一個分量為信號量隊列queue,把二元信號量上的P、V操作記為BP和BV,BP和BV操作原語的定義如下：47二元信號量(2)

typedefstructbinary_semaphore{intvalue;//value取值0or1structpcb*list;};voidBP(binary_semaphore&s){ if(s.value==1) s.value=0; else W(s.list);}voidBV(binary_semaphore&s){ if(s.listisempty()) s.value=1; else R(s.list);}483.3.3信號量實現互斥semaphoremutex;mutex=1;cobeginprocessPi(){//i=1,…,n P(mutex); {臨界區}; V(mutex);}coend493.3.4信號量解決五個哲學家吃通心面問題(1)有五個哲學家圍坐在一圓桌旁，桌中央有一盤通心面，每人面前有一只空盤于，每兩人之間放一把叉子。每個哲學家思考、饑餓、然后吃通心面。為了吃面，每個哲學家必須獲得兩把叉子，且每人只能直接從自己左邊或右邊去取叉子。50

信號量解決五個哲學家吃通心面問題(2)51哲學家吃通心面問題(3)semaphorefork[5];for(inti=0;i<5;i++)fork[i]=1;cobeginprocessphilosopher_i(){//i=0,1,2,3,4while(true){think();P(fork[i]);P(fork[(i+1)%5]);eat();V(fork[i]);V(fork[(i+1)%5]);}}coend可能死鎖！52有若干種辦法可避免這類死鎖上述解法可能出現永遠等待，有若干種辦法可避免死鎖：至多允許四個哲學家同時吃；奇數號先取左手邊的叉子，偶數號先取右手邊的叉子；每個哲學家取到手邊的兩把叉子才吃，否則一把叉子也不取。53哲學家吃通心面問題的一種正確解

semaphorefork[5];for(inti=0;i<5;i++)fork[i]=1;cobeginprocessphilosopher_i(){/*i=0,1,2,3*/while(true){ think()； P(fork[i]；/*i=4,P(fork[0])*/ P(fork[(i+1)%5])；/*i=4,P(fork[4])*/ eat()； V(fork[i])； V(fork([i+1]%5)；}}coend543.3.5信號量解決生產者消費者問題①一個生產者、一個消費者共享一個緩沖區②一個生產者、一個消費者共享多個緩沖區③多個生產者、多個消費者共享多個緩沖區55一個生產者、一個消費者共享一個緩沖區的解intB;semaphoreempty;//可以使用的空緩沖區數semaphorefull;//緩沖區內可以使用的產品數empty=1;//緩沖區內允許放入一件產品full=0;//緩沖區內沒有產品56cobeginprocessproducer(){processconsumer(){while(true){while(true){ produce();P(full); P(empty);take()fromB; append()toB;V(empty); V(full);consume();}}}}coend

57多個生產者/消費者、共享多個緩沖區的解itemB[k];semaphoreempty; empty=k;//可以使用的空緩沖區數semaphorefull;full=0;//緩沖區內可以使用的產品數semaphoremutex; mutex=1;//互斥信號量intin=0; //放入緩沖區指針intout=0;//取出緩沖區指針

58cobeginprocessproducer_i(){processconsumer_j(){while(true){while(true){produce();P(full); P(empty);P(mutex); P(mutex);take()fromB[out]; appendtoB[in];out=(out+1)%k; in=(in+1)%k;V(mutex); V(mutex);V(empty); V(full);consume(); }}}}coend

593.3.6信號量解決讀者-寫者問題(1)有兩組并發進程：讀者和寫者，共享一個文件F，要求：允許多個讀者同時執行讀操作任一寫者在完成寫操作之前不允許其它讀者或寫者工作寫者執行寫操作前，應讓已有的寫者和讀者全部退出60信號量解決讀者寫者問題(2)intreadcount=0;//讀進程計數semaphorewriteblock,mutex;writeblock=1;mutex=1;61信號量解決讀者寫者問題(3)cobeginprocessreader_i(){processwriter_j(){P(mutex);P(writeblock);readcount++;{寫文件};if(readcount==1)V(writeblock);P(writeblock);}V(mutex); {讀文件};P(mutex); readcount--; if(readcount==0) V(writeblock);V(mutex);}coend623.3.7信號量解決理發師問題(1)理發店理有一位理發師、一把理發椅和n把供等候理發的顧客坐的椅子如果沒有顧客，理發師便在理發椅上睡覺一個顧客到來時，它必須叫醒理發師如果理發師正在理發時又有顧客來到，則如果有空椅子可坐，就坐下來等待，否則就離開63信號量解決理發師問題(2)intwaiting=0;//等候理發顧客坐的椅子數intCHAIRS=N;//為顧客準備的椅子數semaphorecustomers,barbers,mutex;customers=0;barbers=0;mutex=1;64信號量解決理發師問題(3)cobeginprocessbarber(){while(true){P(customers);//有顧客嗎？若無顧客，理發師睡眠P(mutex);//若有顧客時，進入臨界區 waiting--;//等候顧客數少一個V(barbers);//理發師準備為顧客理發V(mutex);//退出臨界區 cut_hair();//理發師正在理發(非臨界區) }}65processcustomer_i(){P(mutex);//進入臨界區if(waiting<CHAIRS){//有空椅子嗎 waiting++;//等候顧客數加1V(customers);//喚醒理發師V(mutex);//退出臨界區P(barbers);//理發師忙，顧客坐下等待 get_haircut();//否則顧客坐下理發 }elseV(mutex);//人滿了，走吧！}coend66總結補充信號量小結P、V操作小結前驅關系的信號量解答針對信號量問題的補充練習671、信號量小結一個信號量可用于n個進程的同步互斥；且只能由P、V操作修改。用于互斥時，S初值為1，取值為1~-(n-1)（相當于臨界區的通行證，實際上也是資源個數）S=1：臨界區可用S=0：已有一進程進入臨界區S<0：臨界區已被占用，|S|個進程正等待進入用于同步時，S初值>=0S>=0:表示可用資源個數S<0:表示該資源的等待隊列長度682、P、V操作小結P(S)：請求分配一個資源。V(S)：釋放一個資源。P、V操作必須成對出現。用于互斥時，位于同一進程內；用于同步時，交錯出現于兩個合作進程內。多個P操作的次序不能顛倒，否則可能導致死鎖。多個V操作的次序可任意。693、補充例題（前驅關系）如圖所示的優先圖，要求用信號量實現S1S3S4S5S6S7S270Semaphorea,b,c,d,e,f,g;//初值為0{{S1;V(a);V(b);}{P(a);S2;S4;V(c);V(d);}{P(b);S3;V(e);}{P(c);P(e);S5;V(f);}{P(d);S6;V(g);}{P(f);P(g);S7}}S1S3S4S5S6S7S271補充題目練習S1S3S4S5S6S272Semaphorea,b,c,d,e,f,g;//初值為0{{S1;V(a);V(b);}{P(a);S2;V(c);V(d);}{P(b);S3;V(e);}{P(c);S4;V(f);}{P(d);S5;V(g);}{P(e);P(f);P(g);S6;}}S1S3S4S5S6S2734、針對信號量問題的補充練習桌子上有一個盤子，可以存放一個水果。父親總是放蘋果到盤子中，而母親總是放香蕉到盤子中；兒子專等吃盤中的香蕉，而女兒專等吃盤中的蘋果。分析：生產者－消費者問題的一種變形，生產者、消費者以及放入緩沖區的產品都有兩類，但每類消費者只消費其中固定的一種產品。數據結構：semaphoredish，apple，banana;dish：表示盤子是否為空，初值為1apple：表示盤中是否有蘋果，初值為0banana：表示盤中是否有香蕉，初值為074father:do{P(dish);將蘋果放到盤中；V(apple);}while(1);mother:do{P(dish);將香蕉放到盤中；V(banana);}while(1);son:do{P(banana);從盤中取出香蕉；V(dish);}while(1);daughter:do{P(apple);從盤中取出蘋果；V(dish);}while(1);75哲學家甲請哲學家乙、丙、丁到某處討論問題，約定全體到齊后開始討論；在討論的間隙四位哲學家進餐，每人進餐時都需使用刀、叉各一把，餐桌上的布置如下圖所示。用信號量機制說明四位哲學家的同步互斥過程。食品乙丙丁甲刀2叉1刀1叉276分析標準的哲學家進餐問題，只是哲學家人數和餐具及分布與經典哲學家進餐問題略有不同數據結構semaphorefork1,fork2,knife1,knife2;frok表示叉，knife表示刀，初值均為177pa//哲學家甲do{P(knife1);P(fork1);進餐；V(knife1);V(fork1);討論問題；}while(1);pb//哲學家乙do{P(knife2);P(fork1);進餐；V(knife2);V(fork1);討論問題；}while(1);78pa//哲學家丙do{P(knife2);P(fork2);進餐；V(knife2);V(fork2);討論問題；}while(1);pb//哲學家丁do{P(knife1);P(fork2);進餐；V(knife1);V(fork2);討論問題；}while(1);793.4管程3.4.1管程和條件變量3.4.2管程的實現3.4.3管程解決進程同步問題803.4.1管程和條件變量為什么要引入管程把分散在各進程中的臨界區集中起來進行管理；防止進程有意或無意的違法同步操作;便于用高級語言來書寫程序，也便于程序正確性驗證。81管程定義和屬性管程的定義管程是由局部于自己的若干公共變量及其說明和所有訪問這些公共變量的過程所組成的軟件模塊。管程的屬性

共享性安全性互斥性82管程的形式type管程名=monitor{局部變量說明；條件變量說明；初始化語句；define管程內定義，管程外可調用的過程或函數名列表;use管程外定義，管程內將調用的過程或函數名列表；過程名/函數名(形式參數表){ <過程/函數體>;}...過程名/函數名(形式參數表){ <過程/函數體>;}}83管程的結構conditionwait(c1)…conditionwait(cn)局部數據條件變量過程/函數1過程/函數k出口初始化代碼入口管程等待調用過程的進程隊列管程等待區…84管程的條件變量條件變量-是出現在管程內的一種數據結構，且只有在管程中才能被訪問，它對管程內的所有過程是全局的，只能通過兩個原語操作來控制它。wait()-掛起調用進程并釋放管程，直到另一個進程在該條件變量上執行signal()。signal()-如果存在其他進程由于對條件變量執行wait()而被掛起，便釋放之；如果沒有進程在等待，那么，信號不被保存。條件變量與P、V操作中信號量的區別?條件變量僅起到維護等待進程隊列的作用，沒有與條件變量關聯的值，不能象信號量那樣積累供以后使用。85管程問題討論使用signal釋放等待進程時，可能出現兩個進程同時停留在管程內。解決方法：執行signal的進程等待，直到被釋放進程退出管程或等待另一個條件。被釋放進程等待，直到執行signal的進程退出管程或等待另一個條件。霍爾（Hoare）采用第一種辦法漢森（Hansen）選擇兩者的折衷，規定管程中的過程所執行的signal操作是過程體的最后一個操作。86管程與進程作比較管程定義的是公用數據結構，而進程定義的是私有數據結構；管程把共享變量上的同步操作集中起來，而臨界區卻分散在每個進程中；管程是為管理共享資源而建立的，進程主要是為占有系統資源和實現系統并發性而引入的；管程是被欲使用共享資源的進程所調用的，管程和調用它的進程不能并行工作，而進程之間能并行工作，并發性是其固有特性；管程是語言或操作系統的成分，不必創建或撤銷，而進程有生命周期，由創建而產生至撤銷便消亡。873.4.2管程的實現：Hoare方法霍爾方法使用P和V操作原語來實現對管程中過程的互斥調用，及實現對共享資源互斥使用的管理。不要求signal操作是過程體的最后一個操作，且wait和signal操作可被設計成可以中斷的過程。

88Hoare管程數據結構(1)對每個管程，使用用于管程中過程互斥調用的信號量mutex（初值為1）。進程調用管程中的任何過程時，應執行P(mutex)；進程退出管程時應執行V(mutex)開放管程，以便讓其他調用者進入。為了使進程在等待資源期間，其他進程能進入管程，故在wait操作中也必須執行V(mutex)，否則會妨礙其他進程進入管程，導致無法釋放資源。89Hoare管程數據結構(2)2.next和next-count對每個管程，引入信號量next（初值為0），凡發出signal操作的進程應該用P(next)掛起自己，直到被釋放進程退出管程或產生其他等待條件。進程在退出管程的過程前，須檢查是否有別的進程在信號量next上等待，若有，則用V(next)喚醒它。next-count（初值為0），用來記錄在next上等待的進程個數。

90Hoare管程數據結構(3)3.x-sem和x-count引入信號量x-sem（初值為0），申請資源得不到滿足時，執行P(x-sem)掛起。由于釋放資源時，需要知道是否有別的進程在等待資源，用計數器x-count（初值為0）記錄等待資源的進程數。執行signal操作時，應讓等待資源的諸進程中的某個進程立即恢復運行，而不讓其他進程搶先進入管程，這可以用V(x-sem)來實現。

91Hoare管程數據結構(4)每個管程定義如下數據結構：typedefstructInterfaceModule{//InterfaceModule是結構體的名字semaphoremutex;//進程調用管程過程前使用的互斥信號量semaphorenext;//發出signal的進程掛起自己的信號量intnext_count;//在next上等待的進程數};mutex=1;next=0;next_count=0;//初始化語句92Hoare管程的enter()操作voidenter(InterfaceModule&IM){P(IM.mutex);//互斥進入管程}93Hoare管程的leave()操作voidleave(InterfaceModule&IM){//判有否發出過signal的進程?if(IM.next_count>0)V(IM.next);//有就釋放一個發出過signal的進程else V(IM.mutex);//否則開放管程}94Hoare管程的wait()操作voidwait(semaphore&x_sem,int&x_count,InterfaceModule&IM){x_count++;//等資源進程個數加1，x_count初始化為0if(IM.next_count>0)//判有否發出過signal的進程V(IM.next);//有就釋放一個elseV(IM.mutex);//否則開放管程P(x_sem);//等資源進程阻塞自己，x_sem初始化為0x_count--;//等資源進程個數減1}95Hoare管程的signal()操作voidsignal(semaphore&x_sem,int&x_count,InterfaceModule&IM){if(x_count>0){//有等資源進程嗎? IM.next_count++;//發出signal進程個數加1V(x_sem);//釋放一個等資源的進程P(IM.next);//發出signal進程阻塞自己IM.next_count--;//發出signal進程個數減1 }}963.4.3使用管程解決進程同步問題1.霍爾管程解決五個哲學家吃通心面問題(1)typedining_philosophers=monitorenum{thinking,hungry,eating}state[5];semaphoreself[5];intself_count[5];InterfaceModuleIM;for(inti=0;i<5;i++)//初始化，i為進程號 state[i]=thinking;definepickup,putdown;useenter,leave,wait,signal；97霍爾管程解決五個哲學家吃通心面問題(2)voidpickup(inti){//i=0,1,...,4enter(IM); state[i]=hungry; test(i); if(state[i]!=eating) wait(self[i],self_count[i],IM);leave(IM);}voidputdown(inti){//i=0,1,2,..,4enter(IM);state[i]=thinking;test((i-1)%5);test((i+1)%5);leave(IM);}98霍爾管程實現五個哲學家吃通心面問題(3)voidtest(intk){//k=0,1,...,4 if((state[(k-)%5]!=eating)&&(state[k]==hungry) &&(state[(k+1)%5]!=eating)){ state[k]=eating; signal(self[k],self_count[k],IM); }}}992.管程解決生產者-消費者問題(1)typeproducer_consumer=monitoritemB[k];//緩沖區個數intin,out;//存取指針intcount;//緩沖中產品數semaphorenotfull,notempty;//條件變量intnotfull_count,notempty_count;InterfaceModuleIM;defineappend,take;useenter,leave,wait,signal；100管程解決生產者-消費者問題(2)voidappend(itemx){enter(IM); if(count==k)//緩沖已滿 wait(notfull,notfull_count,IM); B[in]=x; in=(in+1)%k; count++;//增加一個產品 signal(notempty,notempty_count,IM);//喚醒等待消費者leave(IM);}101管程解決生產者-消費者問題(3)voidtake(item&x){ enter(IM);if(count==0) wait(notempty,notempty_count,IM);//緩沖已空 x=B[out]; out=(out+1)%k; count--;//減少一個產品signal(notfull,notfull_count,IM);//喚醒等待生產者leave(IM);}1023.5進程通信3.5.1信號通信機制3.5.2管道通信機制3.5.3共享主存通信機制3.5.4消息傳遞通信機制103進程通信概念并發進程之間的交互必須滿足兩個基本要求：同步和通信。進程競爭資源時要實施互斥，互斥是一種特殊的同步，實質上需要解決好進程同步問題，進程同步是一種進程通信，通過修改信號量，進程之間建立起聯系，相互協調運行和協同工作。進程協同工作時，需互相交換信息，可能是少量信息，也可能交換大批數據。進程之間互相交換信息的工作稱為進程通信IPC（InterProcessCommunication）。104進程間通信的方式信號(signal)通信機制管道(pipeline)通信機制消息傳遞(messagepassing)通信機制信號量(semaphore)通信機制共享主存(sharedmemory)通信機制105進程間通信的方式發展UNIX發展中，AT&T的Bell與加大伯克利的BSD是兩大主力。Bell致力于改進傳統的進程IPC，形成了SYSTEMⅤIPC機制。BSD在改進IPC的同時，把網絡通信規程(TCP/IP)實現到UNIX內核中，考慮把同一計算機上的進程通信納入更廣的網絡范圍的進程間通信，這種努力結果出現了socket網絡通信機制。

1063.5.1信號通信機制信號機制又稱軟中斷，一種簡單的通信機制，通過發送一個指定信號通知進程某個異常事件發生。用戶、內核和進程都能生成信號請求：1)用戶--用戶能通過輸入ctrl+c，或終端驅動程序分配給信號控制字符的其他任何鍵來請求內核產生信號。2)內核--當進程執行出錯時，內核檢測到事件并給進程發送信號，例如，非法段存取、浮點數溢出、或非法操作碼，內核也利用信號通知進程種種特定事件發生。3)進程--進程可通過系統調用kill給另一個進程發送信號，一個進程可通過信號與另一個進程通信。107Linux系統信號分類與進程終止相關的信號與進程例外事件相關的信號與進程執行系統調用相關的信號與進程終端交互相關的信號用戶進程發信號跟蹤進程執行的信號108信號機制的實現信號有一個產生、傳送、捕獲和釋放的過程信號屏蔽位blocked信號發送工作由系統調用kill完成信號響應使用系統調用sigaction完成信號的處理過程109系統空間中斷或異常服務當前進程因中斷/異常而進入核心態在返回用戶態之前，調用do_signal()，handle_signal()轉向用戶空間執行信號處理程序陷入內核后執行善后工作從內核返回用戶空間用戶空間應用程序信號處理程序應用程序繼續執行發送信號執行信號處理程序斷點斷點返回信號處理程序執行結束，執行sigreturn()信號的檢測與處理流程1103.5.2管道通信機制管道(pipeline)是連接讀寫進程的一個特殊文件，允許進程按先進先出方式傳送數據,也能使進程同步執行操作。發送進程以字符流形式把大量數據送入管道，接收進程從管道中接收數據，所以叫管道通信。管道的實質是一個共享文件，基本上可借助于文件系統的機制實現，包括（管道）文件的創建、打開、關閉和讀寫。111共享文件通信機制讀寫進程相互協調，必須做到：?進程對通信機構的使用應該互斥，一個進程正在使用某個管道寫入或讀出數據時，另一個進程就必須等待。(write阻塞、read阻塞)?發送者和接收者雙方必須能夠知道對方是否存在，如果對方已經不存在，就沒有必要再發送信息。112pipe的數據結構系統打開文件表用戶打開文件表主存活動索引節點表外存fp讀進程寫進程fp文件節點指針文件節點指針索引節點pipe文件113父子進程通過管道傳送信息寫端讀端…進程A寫端讀端…進程B管道文件(緩沖區)進程A打開文件表進程B打開文件表114兄弟進程通過管道傳送信息寫端讀端…進程B管道文件(緩沖區)寫端讀端…進程A進程A打開文件表進程B打開文件表寫端讀端…進程C進程C打開文件表1153.5.3共享主存通信機制進程1的虛存空間虛存段進程2的虛存空間虛存段物理主存共享主存116與共享存儲有關的系統調用?

shmget(key,size,permflags)?

shmat(shm-id,daddr,shmflags)?

shmdt(memptr)?shmctl(shm-id,command,&shm-stat)1173.5.4消息傳遞(1)什么是消息傳遞（messagepassing）?消息和消息傳遞機制基本的消息傳遞原語send，receive118消息傳遞(2)采用消息傳遞機制后，一個正在執行的進程可在任何時刻向另一個正在執行的進程發送消息；一個正在執行的進程也可在任何時刻向正在執行的另一個進程請求消息。一個進程在某一時刻的執行依賴于另一進程的消息或等待其他進程對發出消息的回答，那么，消息傳遞機制緊密地與進程的阻塞和釋放相聯系。消息傳遞就進一步擴充了并發進程間對數據的共享，提供了進程同步的能力。119直接通信發送或接收消息的進程必須指出信件發給誰或從誰那里接收消息。原語send（P，消息）把一個消息發送給進程P原語receive（Q，消息）從進程Q接收一個消息120間接通信原語send（A，信件）把一封信件（消息）傳送到信箱A原語receive（A，信件）從信箱A接收一封信件（消息）信箱是存放信件的存儲區域，每個信箱可分成信箱特征和信箱體兩部分。信箱特征指出信箱容量、信件格式、指針等；信箱體用來存放信件121間接通信的實現發送信件：如果指定信箱未滿，則將信件送入信箱中由指針所指示的位置，并釋放等待該信箱中信件的等待者；否則發送信件者被置成等待信箱狀態接收信件：如果指定信箱中有信，則取出一封信件，并釋放等待信箱的等待者，否則接收信件者被置成等待信箱中信件的狀態122消息傳遞機制解決進程互斥問題create_mailbox(box);send(box,null);voidPi(){//i=1,2,…,nmessagemsg;while(true){receive(box,msg);{臨界區};send(box,msg);}}cobeginPi();coend123用消息傳遞機制解決生產者-消費者問(1)intcapacity,i;//緩沖大小creat-mailbox(producer);//創建信箱creat-mailbox(consumer);for(i=0;i<capacity;i++)send(producer,null);//發送空消息124用消息傳遞機制解決生產者-消費者問(2)voidproducer_i(){//i=1,…,nmessagepmsg;while(true){produce();//生產消息receive(producerer,null);//等待空消息build();//構造一條消息send(consumer,pmsg);//發送消息}}125用消息傳遞機制解決生產者-消費者問題(3)voidconsumer_j(){//j=1,…,mmessagecmsg;while(true){receive(consumer,cmsg);//接收消息extract();//取消息send(producer,null);//回送空消息consume(csmg);//消耗消息}}126用消息傳遞機制解決生產者-消費者問題(4)cobeginproducer_i();consumer_j();coend127信件的格式問題單機系統中信件的格式可以分直接信件（又叫定長格式）和間接信件（又叫變長格式）。網絡環境下的信件格式較為復雜，通常分成消息頭和消息體。消息頭包括了發送者、接收者、消息長度、消息類型、發送時間等各種控制信息；消息體包含了消息內容。128通信進程同步方式常用的組合有：阻塞型send和阻塞型receive非阻塞型send和阻塞型receive非阻塞型send和非阻塞型receive1293.6死鎖3.6.1死鎖產生3.6.2死鎖防止3.6.3死鎖避免3.6.4死鎖檢測和解除1303.6.1死鎖產生

若干死鎖的例子例１進程推進順序不當產生死鎖

設系統有打印機、讀卡機各一臺，被進程Ｐ和Ｑ共享。兩個進程并發執行，按下列次序請求和釋放資源：進程Ｐ進程Ｑ請求讀卡機請求打印機請求打印機請求讀卡機釋放讀卡機釋放讀卡機釋放打印機釋放打印機①②③④131PQ讀卡機打印機出現死鎖！132例２PV操作使用不當產生死鎖進程Q1進程Q2………………P(S1);P(s2);P(s2);P(s1);使用r1和r2;使用r1和r2V(S1); V(s2);V(S2);V(S1);

①②③④133Q1Q2S1S2出現死鎖！134

例３資源分配不當引起死鎖若系統中有m個資源被n個進程共享，每個進程都要求Ｋ個資源，而m<n·K時，即資源數小于進程所要求的總數時，如果分配不得當就可能引起死鎖。

135例４對臨時性資源使用不加限制引起死鎖進程通信使用的信件是一種臨時性資源，如果對信件的發送和接收不加限制，可能引起死鎖。進程P1等待進程P3的信件S3來到后再向進程P2發送信件S1；P2又要等待P1的信件S1來到后再向P3發送信件S2；而P3也要等待P2的信件S2來到后才能發出信件S3。這種情況下形成了循環等待，產生死鎖。

136死鎖定義操作系統中的死鎖：如果在一個進程集合中的每個進程都在等待只能由該集合中的其他一個進程才能引發的事件，則稱一組進程或系統此時發生死鎖。例如，n個進程P1、P2，…，Pn，Pi因為申請不到資源Rj而處于等待狀態，而Rj又被Pi+1占有，Pn欲申請的資源被P1占有，此時這n個進程的等待狀態永遠不能結束，則說這n個進程處于死鎖狀態。

137產生死鎖因素不僅與系統擁有的資源數量有關，而且與資源分配策略，進程對資源的使用要求以及并發進程的推進順序有關。1383.6.2死鎖防止(1)系統形成死鎖的四個必要條件互斥條件：進程互斥使用資源部分分配條件：申請新資源時不釋放已占有資源不剝奪條件：一個進程不能搶奪其他進程占有的資源環路條件：存在一組進程循環等待資源的139死鎖防止(2)破壞第一個條件使資源可同時訪問而不是互斥使用，破壞第三個條件采用剝奪式調度方法，當進程在申請資源未獲準許的情況下,如主動釋放資源(一種剝奪式),然后才去等待。

破壞第二個條件或第四個條件上述死鎖防止辦法造成資源利用率和吞吐率低。介紹兩種比較實用的死鎖防止方法。140死鎖的防止(3)采用層次分配策略（破壞條件2和4）資源被分成多個層次當進程得到某一層的一個資源后，它只能再申請較高層次的資源當進程要釋放某層的一個資源時，必須先釋放占有的較高層次的資源當進程得到某一層的一個資源后，它想申請該層的另一個資源時，必須先釋放該層中的已占資源141死鎖防止(4)層次策略的變種按序分配策略把系統的所有資源排一個順序，例如，系統若共有n個進程,共有m個資源，用ri表示第i個資源，于是這m個資源是：r1,r2……,rm規定如果進程不得在占用資源ri(1≤i≤m)后再申請rj(j<i)。不難證明，按這種策略分配資源時系統不會發生死鎖。1423.6.3死鎖避免主要思想：動態的檢測資源分配狀態以確保循環等待條件不可能成立。家算法家擁有一筆周轉資金客戶要求分期貸款，如果客戶能夠得到各期貸款，就一定能夠歸還貸款，否則就一定不能歸還貸款家應謹慎的貸款，防止出現壞帳用家算法避免死鎖操作系統（家）操作系統管理的資源(周轉資金)進程（要求貸款的客戶）1431、安全狀態

最大需求

當前占有P0105P142P292說明：某系統有12臺磁帶驅動器P0：最多要求10臺P1：最多要求4臺P2：最多要求9臺P1分配2；用完釋放4；則系統剩余5P0分配5；用完釋放10；則系統剩余10P2分配7；用完釋放9；則系統剩余12若存在一個安全序列，則系統處于安全狀態例<P1，P0，P2>144死鎖不安全安全安全、不安全和死鎖狀態空間結論：安全狀態不是死鎖狀態死鎖狀態是不安全狀態不是所有不安全狀態都是死鎖狀態1452、家算法數據結構Available：Available[j]=k資源類型Rj現有k個實例Max：Max[i,j]=k進程Pi最多可申請k個Rj的實例Allocation：Allocation[i,j]=k進程Pi現在已經分配了k個Rj的實例Need：Need[i,j]=k進程Pi還可能申請k個Rj的實例Need[i,j]=Max[i,j]-Allocation[i,j]146符號說明X<=Y（X和Y是長度為n的向量），當且僅當對所有i=1,2,…,n，X[i]<=Y[i]Allocationi

表示分配給進程Pi的資源（將Allocation每行作為向量）Need同Allocation147安全性算法用于確定計算機系統是否處于安全狀態設Work和Finish分別是長度為m和n的向量，初始化Work:=Available，Finish[i]=false(i=1,2,…,n)查找i使其滿足Finish[i]=falseNeedi<=Work若沒有這樣的i存在，轉到4）。Work:=Work+AllocationiFinish[i]:=true返回到2）如果對所有i，Finish[i]=true，則系統處于安全狀態148資源請求算法設Requesti為進程Pi的請求向量如果Requesti<=Needi，那么轉到第2）步。否則，產生出錯條件，因為進程已超過了其請求。如果Requesti<=Available，那么轉到第3）步。否則，Pi等待，因為沒有可用資源。假定系統可以分配給進程Pi所請求的資源，并按如下方式修改狀態：Available:=Available–Requesti;Allocationi:=Allocationi+Requesti;Needi:=Needi–Requesti;調用安全性算法確定新狀態是否安全安全—操作完成且進程Pi分配到其所需要的資源不安全—進程Pi必須等待，并將數據結構恢復到原狀態（即3）的逆操作）149家算法舉例說明：5個進程P0…P4，3種資源類型A、B、C，且實例個數分別為10、5、7T0時刻狀態如圖所示

Allocation

Max

AvailableABCABCABCP0010753332P1200322P2302902P3211222P4002433150問題：T0時刻是否為安全狀態？若是，給出安全序列若在T0時刻進程P1請求資源（1，0，2），是否能實施分配？為什么？在（2）的基礎上，若進程P4請求資源（3，3，0），是否能實施分配？為什么？在（3）的基礎上，若進程P0請求資源（0，2，0），是否能實施分配？為什么？151MaxABCAllocationABCNeedABCAvailableABCP0753010743332P1322200122P2902302600P3222211011P4433002431轉換（Need）152①、T0時刻是安全的，存在安全序列<P1，P3，P4，P2，P0>010True10577431047P0302True1047600745P2002True745431743P4211True743011