進程的并發(fā)控制互斥與同步課件

第三章進程的并發(fā)控制

——互斥與同步與時間有關的錯誤問題進程協(xié)調(diào)的概念對臨界區(qū)管理的準則簡單的同步機制（標志法）信號量機制（實現(xiàn)進程互斥與同步的控制）第三章進程的并發(fā)控制

——互斥與同步與時間有關的錯誤問13.1程序的兩種執(zhí)行方式程序的順序執(zhí)行程序在運行的時獨占系統(tǒng)資源，且系統(tǒng)按照程序步驟順序執(zhí)行地執(zhí)行，在該程序執(zhí)行完之前，其他程序只能等待。程序的并發(fā)執(zhí)行多道程序設計的系統(tǒng)中，若干個作業(yè)可以同時執(zhí)行，這些進程輪流地占用CPU，即一個進程的工作沒有全部完成之前，另一個進程就可開始工作，我們說這些執(zhí)行的進程具有并發(fā)性。3.1程序的兩種執(zhí)行方式程序的順序執(zhí)行23.1與時間有關的錯誤問題(1)問題描述：設有一個游樂場設置了一個自動計算機系統(tǒng)，用一個變量count指示在場的人數(shù)，當有人進入，則PIN進程完成count++，當有人退出，則POUT進程完成count--進程PINProcessPIN{intR1;R1=count;R1=R1+1;count=R1;}進程POUTProcessPOUT{intR2;R2=count;R2=R2-1;count=R2;}3.1與時間有關的錯誤問題(1)問題描述：設有一個游樂場設33.1與時間有關的錯誤問題(1)兩個進程的順序執(zhí)行（不產(chǎn)生錯誤）假設某一時刻count=n

intR1;R1=count;R1=R1+1;count=R1;intR2;R2=count;R2=R2-1;count=R2;正確結果count=n不變假設某一時刻count=nintR2;R2=count;R2=R2-1;count=R2;intR1;R1=count;R1=R1+1;count=R1;正確結果count=n不變3.1與時間有關的錯誤問題(1)兩個進程的順序執(zhí)行（不產(chǎn)生43.1與時間有關的錯誤問題(1)并發(fā)執(zhí)行一種錯誤的可能結果：假設某一時刻count=n

R1=count;count=n

R1=R1+1;PIN進程被掛起R2=count;R2=R2-1;count=n-1

count=R2;POUT進程結束，PIN喚醒count=R1;錯誤的結果值count=n+1，實際該為n3.1與時間有關的錯誤問題(1)并發(fā)執(zhí)行一種錯誤的可能結果：53.1與時間有關的錯誤問題(1)并發(fā)執(zhí)行另一種錯誤的可能結果：假設某一時刻count=nR1=count;count=n

R1=R1+1;PIN進程被掛起;R1=n+1R2=count;count=n

R2=R2-1;POUT進程被掛起，PIN喚醒R2=n-1

count=R1;PIN進程結束，POUT喚醒count=n+1count=R2;POUT進程結束，count=n-1錯誤的結果值count=n-1，實際該為n3.1與時間有關的錯誤問題(1)并發(fā)執(zhí)行另一種錯誤的可能結果63.1與時間有關的錯誤問題(1)分析產(chǎn)生錯誤的可能原因一個進程運行時由于自身或外界的原因可能被中斷，且斷點是不固定的。進程執(zhí)行的相對速度不能由自己來控制兩個并發(fā)進程使用共享的變量count兩個進程在不同時間里訪問count變量，可能得到相同的count變量值。3.1與時間有關的錯誤問題(1)分析產(chǎn)生錯誤的可能原因73.1與時間有關的錯誤問題(2)問題描述：設一個飛機航班售票系統(tǒng)有n個售票處，每個售票處通過終端訪問系統(tǒng)公共數(shù)據(jù)區(qū)，假定公共數(shù)據(jù)區(qū)中的一些單元Aj（j=1，2，……）分別存放某年某月某日某次航班的剩余票數(shù)。設P1，P2，…，Pn表示各個售票處的處理進程，R1，R2，…，Rn表示各進程執(zhí)行時所用的工作單元，當各售票處有旅客買票時，進程工作如下：3.1與時間有關的錯誤問題(2)問題描述：設一個飛機航班售票83.1與時間有關的錯誤問題(2)可能產(chǎn)生的錯誤結果

可能有若干個旅客在幾乎相同的時間里到不同的售票處要求購買同一天同一航班的機票，于是若干進程都要訪問同一個Aj，則結果可能出現(xiàn)同一張票賣給幾個不同的旅客ProcessPi（i=1，2，…，n）{根據(jù)用戶需求找到Aj;

Ri=Aj;if(Ri>=1){Ri=Ri-1;Aj=Ri;提示已賣出一張票信息；}else輸出“票已售完”；}3.1與時間有關的錯誤問題(2)可能產(chǎn)生的錯誤結果Proce93.1與時間有關的錯誤問題(2)假設某一個時刻三個客戶在不同網(wǎng)點但幾乎同時到達購票訪問的情況進程t1t2t3t4t5P1R1=Aj……R1=R1-1Aj=R1P2R2=Aj……R2=R2-1Aj=R2P3R3=AjR3=R3-1……3.1與時間有關的錯誤問題(2)假設某一個時刻三個客戶在不同103.2進程的協(xié)調(diào)概念在os支持下，多個進程既獨立又并發(fā)執(zhí)行，然而進程之間可能合作完成一項任務，可能共享一種系統(tǒng)資源，可能相互支持和依賴，甚至制約對方，為了協(xié)調(diào)進程間的關系，os必須進行進程間的協(xié)調(diào)。

3.2進程的協(xié)調(diào)概念在os支持下，多個進程既獨立又并發(fā)執(zhí)行113.2進程的制約關系直接相互制約關系

源于進程的合作，同步關系如：A、B兩個進程通過緩沖區(qū)合作完成一項任務，A負責存數(shù)據(jù)到緩沖區(qū)，B負責從緩沖區(qū)中取數(shù)。間接相互制約關系

源于資源共享，互斥關系如：A、B兩個進程共享打印機，若分配給A，則當B需要打印機時被阻塞而等待3.2進程的制約關系直接相互制約關系123.2進程的互斥與同步進程間具有一種互斥關系也就是說對于某個系統(tǒng)資源，如果一個進程正在使用，其他進程就必須等待其用完，不能同時使用。進程間具有一種同步關系即多個相關的進程在執(zhí)行次序上需要協(xié)調(diào)，如當兩個進程或多個進程合作完成一個任務，在并發(fā)執(zhí)行中，一個進程需等待其合作伙伴發(fā)送消息或建立條件再向前執(zhí)行，這種制約關系通常稱為進程的同步。3.2進程的互斥與同步進程間具有一種互斥關系13幾個專業(yè)術語臨界資源一次只允許一個進程使用的資源廣義上，包括物理實體資源，如：打印機

軟件資源，如：變量、文件等臨界區(qū)一個進程訪問這種臨界資源的那段程序代碼，稱為臨界區(qū)幾個專業(yè)術語臨界資源14幾個專業(yè)術語剩余區(qū)除臨界區(qū)外的其余代碼說明：進程互斥的再定義，就是兩個進程不能同時進入訪問同一臨界資源的臨界區(qū)操作系統(tǒng)中實現(xiàn)互斥和同步的機制統(tǒng)稱為同步機制幾個專業(yè)術語剩余區(qū)153.3臨界區(qū)的管理準則－P79操作系統(tǒng)的進程同步機制必須遵循如下準則空閑讓進忙則等待有限等待讓權等待3.3臨界區(qū)的管理準則－P79操作系統(tǒng)的進程同步機制必須遵163.3臨界區(qū)的管理準則空閑讓進當無進程處于臨界區(qū)時，允許一個進程進入忙則等待當有進程在臨界區(qū)，其他欲進入臨界區(qū)的進程須等待，否則無需等待（一次至多一個進程能夠進入臨界區(qū)）3.3臨界區(qū)的管理準則空閑讓進173.3臨界區(qū)的管理準則有限等待對要求進入臨界區(qū)的進程，應在有限時間內(nèi)讓其進入，避免“死等”（不能讓一個進程無限在臨界區(qū)執(zhí)行，任何進入臨界區(qū)的進程必須在有限時間內(nèi)退出）3.3臨界區(qū)的管理準則有限等待18臨界區(qū)的管理準則讓權等待臨界區(qū)讓出，必須立即釋放CPU，讓等待進程進入，避免“忙等”（不能讓一個進程無限等待進入，即有進程退出臨界區(qū)時，應讓等待進程進入臨界區(qū)執(zhí)行）臨界區(qū)的管理準則讓權等待193.4簡單的同步機制－標志位機制進程互斥問題的軟件解決方法輪流標志法（單標志法）雙標志法三標志法3.4簡單的同步機制－標志位機制進程互斥問題的軟件解決方法203.4簡單的同步機制－單標志位法算法的基本思想設置一個標志變量turn，兩個進程P0、P1要進入臨界區(qū)先要訪問該標志，根據(jù)標志值決定自己是否進入臨界區(qū)。例如當turn=0，表示允許P0進程進入，當P0退出臨界區(qū)后，置turn=1，P1才可進入臨界區(qū)；反之當turn＝1，表示允許P1進程進入，退出時置turn=0，則P0才可進入。3.4簡單的同步機制－單標志位法算法的基本思想213.4簡單的同步機制－單標志位法ProcessP0{do{

while(turn!=0);

臨界區(qū)turn=1;

剩余區(qū)}while(1);}ProcessP1{do{

while(turn!=1);

臨界區(qū)turn=0;

剩余區(qū)}while(1);}初始值turn=0;或者turn=1;3.4簡單的同步機制－單標志位法ProcessP0Pro223.4簡單的同步機制－單標志位法該算法的致命缺點要求進入臨界區(qū)執(zhí)行的兩個進程必須嚴格的交替運行。當進程A大于進程B時，將阻塞進程B再次進入臨界區(qū)（因為交替原則，B必須等待A執(zhí)行結束），即產(chǎn)生了長進程阻塞短進程的問題。不滿足臨界區(qū)管理的第一個準則，因為存在一個進程當它在剩余區(qū)時，也不允許另一個進程進入臨界區(qū)。3.4簡單的同步機制－單標志位法該算法的致命缺點233.4簡單的同步機制－雙標志位法算法的基本思想先修改后檢查算法為每個進程都設置一個標志位，引入數(shù)組flag[2]，初始化為false，表示臨界區(qū)中無進程，欲進入者可以進入。進程Pi欲進入時將自身標志flag[i]置為true，阻止另一個進程進入，接著判定對方的標志是否為false，若是才可以進入臨界區(qū)，否則必須等待；任一個進程退出臨界區(qū)后都將自身標志置為false，表示退出臨界區(qū)，允許對方進程進入臨界區(qū)。3.4簡單的同步機制－雙標志位法算法的基本思想243.4簡單的同步機制－雙標志位法(1)算法的主要偽代碼ProcessP0{do{flag[0]=true;

while(flag[1]);

臨界區(qū)

flag[0]=false;剩余區(qū)}while(1);}ProcessP1{do{flag[1]=true;

while(flag[0]);

臨界區(qū)

flag[1]=false;剩余區(qū)}while(1);}初始值flag[i]=false3.4簡單的同步機制－雙標志位法(1)算法的主要偽代碼Pr253.4簡單的同步機制－雙標志位法(1)算法的特點可以解決兩個進程嚴格交替的問題但當兩個進程幾乎同時到達時，結果兩個進程都不能進入臨界區(qū)執(zhí)行產(chǎn)生死鎖問題可能導致對方進程的“饑餓”問題，將永遠被阻塞不滿足管理準則中的“空閑讓進”3.4簡單的同步機制－雙標志位法(1)算法的特點263.4簡單的同步機制－雙標志位法(2)算法的基本思想先檢查算法交換修改與檢查語句的順序，先做while檢查，再做true值的設置修改3.4簡單的同步機制－雙標志位法(2)算法的基本思想273.4簡單的同步機制－雙標志位法(2)算法的主要偽代碼ProcessP0{do{while(flag[1]);flag[0]=true;

臨界區(qū)flag[0]=false;

剩余區(qū)}while(1);}ProcessP1{do{while(flag[0]);flag[1]=true;

臨界區(qū)flag[1]=false;

剩余區(qū)}while(1);}3.4簡單的同步機制－雙標志位法(2)算法的主要偽代碼Pr283.4簡單的同步機制－雙標志位法(2)算法的致命缺點比前兩種方法更差，不能解決互斥問題導致所有進程都可以進入臨界區(qū)不滿足管理準則中的“忙則等待”3.4簡單的同步機制－雙標志位法(2)算法的致命缺點293.4簡單的同步機制－三標志位法算法的基本思想先修改、后檢查、后修改者等待算法為了解決兩個進程的同時到達問題，將前兩者算法結合，在雙標志法的基礎上再引入turn變量，當兩個進程幾乎同時到達時，進程根據(jù)turn值決定哪一個進程進入臨界區(qū)，即保證任一個時刻，turn值為0或者為1，使得只有一個進程滿足條件而進入臨界區(qū)。3.4簡單的同步機制－三標志位法算法的基本思想303.4簡單的同步機制－三標志位法算法的主要偽代碼ProcessP0{do{flag[0]=true;turn=1;while(flag[1]&&turn==1);

臨界區(qū)flag[0]=false;

剩余區(qū)}while(1);}ProcessP1{do{flag[1]=true;turn=0;while(flag[0]&&turn==0);

臨界區(qū)flag[0]=false;

剩余區(qū)}while(1);}3.4簡單的同步機制－三標志位法算法的主要偽代碼Proce313.4簡單的同步機制－三標志位法兩個進程幾乎同時到達的情況flag[0]=true;

flag[1]=true;

turn=1;

while(flag[1]&&turn==1);//P0被掛起turn=0;//后修改者即P1

while(flag[0]&&turn==0);//P1被掛起，P0被解除

臨界區(qū)//P0進入臨界區(qū)flag[0]=false;//P0退出，P1可被解除

剩余區(qū)//P0的剩余區(qū)

…………3.4簡單的同步機制－三標志位法兩個進程幾乎同時到達的情況323.4簡單的同步機制－三標志位法兩個進程幾乎同時到達的情況flag[0]=true;

flag[1]=true;

turn=1;turn=0;//后修改者P1

while(flag[0]&&turn==0);//P1被掛起

while(flag[1]&&turn==1);//P0被批準進入

臨界區(qū)//P0進入臨界區(qū)flag[0]=false;//P0退出，P1可被解除

剩余區(qū)//P0的剩余區(qū)

…………3.4簡單的同步機制－三標志位法兩個進程幾乎同時到達的情況333.4簡單的同步機制－三標志位法兩個進程幾乎同時到達的情況flag[0]=true;

flag[1]=true;

turn=0;turn=1;//后修改者P0

while(flag[1]&&turn==1);//P0被掛起

while(flag[0]&&turn==0);//P1被批準進入

臨界區(qū)//P1進入臨界區(qū)flag[1]=false;//P1退出，P0可被解除

剩余區(qū)//P1的剩余區(qū)

…………3.4簡單的同步機制－三標志位法兩個進程幾乎同時到達的情況343.4簡單的同步機制－三標志位法算法的特點滿足管理準則，空閑讓進，忙則等待等解決進程的互斥與并發(fā)實現(xiàn)較復雜系統(tǒng)開銷大3.4簡單的同步機制－三標志位法算法的特點353.4簡單的同步機制四個算法的共同缺點只適合解決兩進程的互斥問題不能處理進程的同步問題3.4簡單的同步機制四個算法的共同缺點363.5信號量機制信號量協(xié)調(diào)機制可實現(xiàn)2個或2個以上的進程協(xié)調(diào)。既可用與互斥，也可用用于同步。信號量（semaphore）是由荷蘭計算機科學家E.W.Dijkstra于1965年提出的，它取自交通管理中的信號燈的概念。3.5信號量機制信號量協(xié)調(diào)機制可實現(xiàn)2個或2個以上的進程協(xié)373.5信號量機制信號量的基本概念信號量是用于控制進程互斥與同步的物理變量信號量S（通常用S表示）是一個整型變量，初始值為非負數(shù)每個信號量S對應設置了一個等待隊列對信號量的操作只能通過PV操作進行3.5信號量機制信號量的基本概念383.5信號量機制－－PV操作P操作和V操作都是不可分割的原子操作，也叫原語P操作可以記為P(S)，wait(S)或者down(S)V操作可以記為V(S)，signal(S)或者up(S)為減化，我們用P(S)和V(S)表示，教材采用wait()和signal()表示3.5信號量機制－－PV操作P操作和V操作都是不可分割的原393.5信號量機制－－PV操作Dijkstra把互斥和同步的關鍵含義抽象成信號量(semaphore)概念，并引入在信號量上的P、V操作作為同步原語(P和V分別是荷蘭文的“等待”和“發(fā)信號”兩詞的首字母)。PV操作對于每一個進程來說，都只能進行一次，而且必須成對使用。3.5信號量機制－－PV操作Dijkstra把互斥和同步的403.5信號量機制－－P操作P(S)操作的定義S值減一若S<0，阻塞當前進程，將其插入到等待S的隊列若S>=0，當前進程繼續(xù)運行(說明等待隊列無進程，當前進程可繼續(xù)不阻塞)P操作的偽代碼P(ints){s--;if(s<0)wait();//當前被掛起return;//當前繼續(xù)}3.5信號量機制－－P操作P(S)操作的定義P操作的偽代碼413.5信號量機制－－V操作V(S)操作的定義S值加一；若S<=0，從等待S的隊列中移出一個進程，由阻塞態(tài)轉(zhuǎn)為就緒態(tài)，插入就緒隊列若S>0，當前進程繼續(xù)執(zhí)行（說明等待隊列無進程，無需執(zhí)行喚醒操作）V操作的偽代碼V(ints){s++;if(s<=0)wakeup();

//移出一個進程，插入就緒隊列，相當喚醒return;//當前繼續(xù)}3.5信號量機制－－V操作V(S)操作的定義V操作的偽代碼423.5信號量機制－－解決互斥問題如果有若干個進程都調(diào)用P操作(提出申請)，則只有第一個調(diào)用P操作的進程不成為等待狀態(tài)而可以繼續(xù)執(zhí)行P操作第一次調(diào)用后，S的值成為“0”，以后的進程調(diào)用P操作時，S值總小于0（S<0,因為S--），進程被阻塞置為等待狀態(tài)而不能繼續(xù)執(zhí)行直到有一個進程退出臨界區(qū)，調(diào)用一次V操作后，才釋放一個等待者。設S=1;{P(S);臨界區(qū)V(S);}3.5信號量機制－－解決互斥問題如果有若干個進程都調(diào)用P操433.5信號量機制－－解決互斥問題能實現(xiàn)對臨界區(qū)管理的要求當無進程在臨界區(qū)時，若有進程要進入臨界區(qū)則允許一個進程立即進入它的臨界區(qū)；當有一個進程在臨界區(qū)執(zhí)行時，其他試圖進入臨界區(qū)的進程必須等待；當有一個進程離開臨界區(qū)時，若有等待進入臨界區(qū)的進程，則允許其中一個進程進入它的臨界區(qū)。系統(tǒng)中的共享資源均有一個信號量與之對應，OS按其狀態(tài)對進程和資源進行管理3.5信號量機制－－解決互斥問題能實現(xiàn)對臨界區(qū)管理的要求443.5信號量機制－－解決互斥問題實現(xiàn)互斥的方法首先判斷臨界資源其次判斷相關的代碼即臨界區(qū)定義信號量的個數(shù)設置信號量初始值在進入臨界區(qū)之前調(diào)用P操作，相當申請進入臨界區(qū)。在退出臨界區(qū)之后調(diào)用V操作，相當喚醒等待進程進入臨界區(qū)3.5信號量機制－－解決互斥問題實現(xiàn)互斥的方法453.5信號量機制－－游樂場問題游樂場關于計數(shù)的兩個進程進程P2Processp2{intR2;R2=count;R2=R2-1;count=R2;}進程P1Processp1{intR1;R1=count;R1=R1+1;count=R1;}3.5信號量機制－－游樂場問題游樂場關于計數(shù)的兩個進程進程463.5信號量機制－－游樂場問題分析上述進程，找到臨界資源即count這個全局共享變量分析有關對count變量進行操作的代碼即臨界區(qū)，包括三條語句一個共享資源count變量對應一個信號量，信號量S表示由于每次只能讓一個進程使用，且共享的資源個數(shù)為1，所以信號量S的初始值為13.5信號量機制－－游樂場問題分析上述進程，找到臨界資源即473.5信號量機制－－游樂場問題 互斥信號量S初值為1說明了任意時刻只允許一個進程進入臨界區(qū)，其他想進入的進程只能等待Processp2{intR2;

P(S);R2=count;R2=R2-1;count=R2;

V(S);}Processp1{intR1;

P(S);R1=count;R1=R1+1;count=R1;V(S);}SemaphoreS;S=1;3.5信號量機制－－游樂場問題 互斥信號量S初值為1說明了483.5信號量機制－－游樂場問題這是兩個進程互斥的問題對信號量S的分析S＝1，表示當前共享資源只有一個可供使用，一次只能允許一個進程使用。（且任何時刻只能一個進程進入臨界區(qū)，其他欲進入的進程必須等待——互斥概念）S＝0，表示有一個進程在臨界區(qū)，無可用資源，無等待進程3.5信號量機制－－游樂場問題這是兩個進程互斥的問題對信號493.5信號量機制－－游樂場問題這是兩個進程互斥的問題S＝-1，表示有一個等待的進程S的取值范圍：（1，0，-1）|S|的含義：表示有|S|個進程在等待3.5信號量機制－－游樂場問題這是兩個進程互斥的問題503.5信號量機制－－訂票系統(tǒng)問題飛機訂票系統(tǒng)關于聯(lián)網(wǎng)訂票的進程Processpi{intR;根據(jù)用戶需求找到Aj;if(Aj>=1){R=Aj;R=R-1;Aj=R;提示已賣出一張票信息；}else輸出票已售完；}3.5信號量機制－－訂票系統(tǒng)問題飛機訂票系統(tǒng)關于聯(lián)網(wǎng)訂票的513.5信號量機制－－訂票系統(tǒng)問題解決互斥方法一Processpi{intR;根據(jù)用戶需求找到Aj;if(Aj>=1){P(S);R=Aj;R=R-1;Aj=R;V(S);提示已賣出一張票信息；}else輸出票已售完；}SemaphoreS=1;思考：互斥問題是否得到解決？如果沒有，原因在哪？3.5信號量機制－－訂票系統(tǒng)問題解決互斥方法一Proces523.5信號量機制－－訂票系統(tǒng)問題法一的問題分析表面上看實現(xiàn)互斥的管理，實際上仍然存在讀取相同Aj值的情況分析判定共享資源應該是：Aj變量分析判定臨界區(qū)：包括所有對Aj變量操作的代碼區(qū)注意：若查詢結果是無票，雖不影響臨界區(qū)的使用，不產(chǎn)生錯誤，但存在潛在的錯誤3.5信號量機制－－訂票系統(tǒng)問題法一的問題分析533.5信號量機制－－訂票系統(tǒng)問題互斥解法二SemaphoreS=1;Processpi（修改進程的表示）{intR;根據(jù)用戶需求找到Aj；R=Aj;if(R>=1){R=R-1;Aj=R;提示已賣出一張票信息；}else輸出票已售完；}Processpi（I=1，2，……n）{intR;根據(jù)用戶需求找到Aj；

P(S);R=Aj;if(R>=1){R=R-1;Aj=R;

V(S);提示已賣出一張票信息；}else輸出票已售完；}3.5信號量機制－－訂票系統(tǒng)問題互斥解法二Semaphor543.5信號量機制－－訂票系統(tǒng)問題法二的問題分析PV操作沒有成對出現(xiàn)對第一個查詢結果無票的進程而言，能順利退出臨界區(qū)，但后續(xù)進程均被掛起，不能得到響應導致系統(tǒng)內(nèi)部存在“饑餓”進程3.5信號量機制－－訂票系統(tǒng)問題法二的問題分析553.5信號量機制－－訂票系統(tǒng)問題正確的解法SemaphoreS=1;Processpi{intR;

P(S);根據(jù)用戶需求找到Aj；R=Aj;if(R>=1){R=R-1;Aj=R;

V(S);提示已賣出一張票信息；}else{V(S);輸出票已售完}}說明：準確判斷臨界區(qū)是非常重要的，但要注意在退出臨界區(qū)是否執(zhí)行了V操作，要注意PV操作的成對性3.5信號量機制－－訂票系統(tǒng)問題正確的解法Semaphor563.5信號量機制－－訂票系統(tǒng)問題對信號量S的分析S＝1，表示當前共享資源只有一個可供使用。（且任何時刻只能一個進程進入臨界區(qū)，其他欲進入的進程必須等待——互斥概念）S＝0，表示有一個進程在臨界區(qū)，無可用資源S＝-1，-2……表示有1個、2個…等待的進程S的取值范圍：(-(n-1)～1)|S|的含義：表示有|S|個進程在等待這是n個進程的互斥問題3.5信號量機制－－訂票系統(tǒng)問題對信號量S的分析這是n個進573.5信號量機制－－同步問題假設緩沖區(qū)一次只能放一個物品緩沖區(qū)進程B（消費者）進程A（生產(chǎn)者）存取讀加工問題：如果兩個進程不相互制約的話會造成什么錯誤？3.5信號量機制－－同步問題假設緩沖區(qū)一次只能放一個物品緩583.5信號量機制－－同步問題問題分析在B還沒來得及從緩沖區(qū)中取走當前數(shù)據(jù)之前，A又存入一個新記錄，則引起數(shù)據(jù)被覆蓋的錯誤在A還沒來得及生產(chǎn)新的數(shù)據(jù)之前，B又從緩沖區(qū)中取走相同的數(shù)據(jù)，導致重復取記錄的錯誤3.5信號量機制－－同步問題問題分析593.5信號量機制－－同步問題錯誤的原因AB兩個進程的執(zhí)行速度不同步造成，A比B快，或B比A快，所以AB進程需同步，需要協(xié)調(diào)說明：進程的同步關系源于進程的合作（協(xié)作）3.5信號量機制－－同步問題錯誤的原因603.5信號量機制－－解決同步問題問題提出要實現(xiàn)進程同步就必須提供一種機制，該機制能測試進程所需的消息是否到達，也能把它所需的消息發(fā)送出去實現(xiàn)思想用一個信號量與一個消息聯(lián)系起來，當信號量的值為“0”時，表示期望的消息還沒有產(chǎn)生，當信號量的值為非“0”時表示期望的消息已經(jīng)存在。3.5信號量機制－－解決同步問題問題提出61實現(xiàn)方法通過調(diào)用P操作可以測試自己所期望的消息是否到達（相當申請進入臨界區(qū)）而任何進程要向其它進程發(fā)送消息時（相當喚醒下一個進程進入臨界區(qū)）可以調(diào)用V操作3.5信號量機制－－解決同步問題實現(xiàn)方法3.5信號量機制－－解決同步問題623.5信號量機制－－解決同步問題實現(xiàn)原理P操作的理解用信號量S表示一種消息，如果消息還沒有產(chǎn)生，則S＝0，調(diào)用P(S)操作后，調(diào)用者將成為等待狀態(tài)，申請進入臨界區(qū)失敗。如果消息已經(jīng)存在，則S>0,調(diào)用P(S)操作后，調(diào)用者不會成為等待狀態(tài)，即申請進入臨界區(qū)成功。3.5信號量機制－－解決同步問題實現(xiàn)原理633.5信號量機制－－解決同步問題實現(xiàn)原理V操作的理解若調(diào)用V(S)操作前S＝0，表示消息還沒有產(chǎn)生也沒有等待消息的進程，這時調(diào)用V(S)操作后，S!=0，調(diào)用V(S)后，意味著消息產(chǎn)生，即相當通知或者喚醒操作。若調(diào)用V操作前S<0，表示消息還沒有產(chǎn)生且有進程在等待該消息，這時調(diào)用V(S)操作后將釋放一個在等待消息的進程，即調(diào)用V(S)操作的進程把消息發(fā)給在等待消息的進程且允許它繼續(xù)進行，即相當通知或者喚醒操作。3.5信號量機制－－解決同步問題實現(xiàn)原理643.5經(jīng)典同步問題

—生產(chǎn)者/消費者問題生產(chǎn)者與消費者問題描述現(xiàn)假定有一個生產(chǎn)者和一個消費者，他們共用一個緩沖器，生產(chǎn)者不斷地生產(chǎn)物品，每生產(chǎn)一件物品就要存入緩沖器，但緩沖器中每次只能存入一件物品，只有當消費者把物品取走后，生產(chǎn)者才能把第二件物品存入緩沖器。同樣地，消費者不斷地取出物品去消費，當緩沖器中有物品時他就可以去取，每取走一件物品后必須等生產(chǎn)者放入一件物品才可再取。3.5經(jīng)典同步問題

653.5經(jīng)典同步問題

—生產(chǎn)者/消費者問題生產(chǎn)者進程和消費者進程（未采用同步機制前的主要代碼）Processproducer{L1:produceaproduct;

Buffer=product;gotoL1;}Processconsumer{L1:takeaproduct

fromBuffer;consume;gotoL1;}3.5經(jīng)典同步問題

663.5經(jīng)典同步問題

—生產(chǎn)者/消費者問題問題分析消息的個數(shù)：2個需要的信號量兩個，定義兩個變量SP、SG分別表示生產(chǎn)者和消費者的信號量(私有信號量)兩個進程生產(chǎn)和消費各自獨立，并發(fā)執(zhí)行兩個進程只在訪問公共的緩沖器把物品存入或取出時才要互通消息3.5經(jīng)典同步問題

673.5經(jīng)典同步問題

—生產(chǎn)者/消費者問題信號量初值的分析初始狀態(tài)，緩沖器為空，允許生產(chǎn)者生產(chǎn)的物品存入緩沖器，相當于通知消費者進程取物品的消息已經(jīng)到了，代表此消息的信號量SP初值應該為“1”。初始狀態(tài)，緩沖區(qū)為空，不能取數(shù)消費，也就不能通知再生產(chǎn)，所以對應信號量SG的初值應該為“0”。3.5經(jīng)典同步問題

683.5經(jīng)典同步問題

—生產(chǎn)者/消費者問題信號量的定義SemaphoreSP,SG;SP=1;SG=0;SP：表示是否可以把物品存入緩沖區(qū)，由于緩沖區(qū)每次只能放一個物品，所以初值為1。SG：表示緩沖區(qū)是否存在有物品，顯然初值為0，表示開始還沒有物品在緩沖區(qū)。3.5經(jīng)典同步問題

693.5經(jīng)典同步問題

—生產(chǎn)者/消費者問題實現(xiàn)的基本方法生產(chǎn)者進入緩沖區(qū)前調(diào)用P操作判斷消息是否到達，或者說申請進入的消息是否允許通過，退出緩沖區(qū)時，調(diào)用V操作發(fā)送消息通知消費者，相當喚醒消費者消費者在進入緩沖區(qū)前，首先調(diào)用P操作判斷是否可以取數(shù)，即通知取數(shù)的消息是否到達，當取數(shù)后退出緩沖區(qū)，調(diào)用V操作，發(fā)送消息，通知生產(chǎn)者3.5經(jīng)典同步問題

703.5經(jīng)典同步問題

—生產(chǎn)者/消費者問題將PV操作加入到原來的偽代碼中，結果如下SemaphoreSP,SG;SP=1;SG=0;intBuffer;Processproducer{L1:produceaproduct;

P(SP);

Buffer=product;

V(SG);gotoL1;}Processconsumer{L1:

P(SG);

takeaproduct

fromBuffer;

V(SP);

consume;gotoL1;}3.5經(jīng)典同步問題

713.5經(jīng)典同步問題

—生產(chǎn)者/消費者問題分析下列幾種情況，看PV操作是否能管理：先生產(chǎn)再消費，然后再生產(chǎn)再消費的同步過程(可以)先生產(chǎn)，然后想再生產(chǎn)，是否可行？（不行）如果再次生產(chǎn)失敗則轉(zhuǎn)為消費，消費后再生產(chǎn)，但如果消費后企圖再消費是否可行？（不行）一開始就要消費，是否可行？(不行)開始沒有產(chǎn)品，不能消費，結果必然轉(zhuǎn)為生產(chǎn)3.5經(jīng)典同步問題

723.5經(jīng)典同步問題

—生產(chǎn)者/消費者問題分析SP和SG的取值范圍緩沖器任何時候只允許一個進程使用。兩個進程，當生產(chǎn)者/消費者在緩沖器內(nèi)，消費者/生產(chǎn)者只能等待，所以等待的進程個數(shù)最多一個。取值范圍(-1，0,1)3.5經(jīng)典同步問題

733.5經(jīng)典同步問題

—生產(chǎn)者/消費者共享容量n的緩沖區(qū)問題變?yōu)椋阂粋€生產(chǎn)者和一個消費者共享容量為n的緩沖區(qū)的同步問題0123456……n-2n-1生產(chǎn)k取數(shù)t3.5經(jīng)典同步問題

—生產(chǎn)743.5經(jīng)典同步問題

—生產(chǎn)者/消費者共享容量n的緩沖區(qū)變量k和t的理解 由于緩沖區(qū)的容量為n，則必須考慮：生產(chǎn)者生產(chǎn)的物品存入緩沖區(qū)的哪個位置，以及消費者取出的物品來自緩沖區(qū)的哪個位置，因此相應需要增加k和t兩個變量表示生產(chǎn)者往緩沖區(qū)存物品和消費者從緩沖區(qū)中取物品的相對位置，它們的初值為“0”。即定義intk=0,t=0;3.5經(jīng)典同步問題

—生產(chǎn)753.5經(jīng)典同步問題

—生產(chǎn)者/消費者共享容量n的緩沖區(qū)生產(chǎn)者和消費者的進程表示如下：

(還沒有實現(xiàn)同步機制前)Processproducer{L1：produceaproduct;B[k]=product;

k=(k+1)%n;gotoL1;}Processconsumer{L1：takeaproductfromB[t];t=(t+1)%n;gotoL1;}3.5經(jīng)典同步問題

—生產(chǎn)763.5經(jīng)典同步問題

—生產(chǎn)者/消費者共享容量n的緩沖區(qū)信號量的定義需要傳送的消息個數(shù)：2個（不變）定義2個信號量：分別用SP，SG表示信號量的初始化SP：初值為“n”，表示開始有n個空閑區(qū)可以放置物品SG：初值為“0”，表示開始沒有物品在緩沖區(qū)中3.5經(jīng)典同步問題

—生產(chǎn)773.5經(jīng)典同步問題

—生產(chǎn)者/消費者共享容量n的緩沖區(qū)問題提出：在PV操作之前必須準確判斷臨界區(qū)，這里的臨界區(qū)在哪？Processproducer{L1：produceaproduct;B[k]=product;

k=(k+1)%n;gotoL1;}Processconsumer{L1：takeaproductfromB[t];

t=(t+1)%n;gotoL1;}3.5經(jīng)典同步問題

—生產(chǎn)783.5經(jīng)典同步問題

—生產(chǎn)者/消費者共享容量n的緩沖區(qū)intB[n],k=0,t=0;SemaphoreSP=n,SG=0;Processproducer{L1：produceaproduct;

P(SP);

B[k]=product;k=(k+1)%n;

V(SG);gotoL1;}Processconsumer{L2：P(SG);

takeaproductfromB[t];t=(t+1)%n;

V(SP);gotoL2;}3.5經(jīng)典同步問題

—生產(chǎn)793.5經(jīng)典同步問題

—補充例子 例2：假定有三個進程R，W1，W2共享一個緩沖器B，而B中每次只能存放一個數(shù)。當緩沖器中無數(shù)時，進程R可將從輸入設備上讀入的數(shù)存放到緩沖器B中。若存放到緩沖器中的是奇數(shù)，則允許進程W1將其取出打??；若存放到緩沖器中的是偶數(shù)，則允許進程W2將其取出打印。同時規(guī)定：進程R必須等緩沖器中的數(shù)取出打印后才能再存放一個數(shù)；進程W1或W2對每次存入緩沖器中的數(shù)只能打印一次；W1和W2都不能從空的緩沖器中取數(shù)，寫出這三個并發(fā)進程能正確工作的程序。3.5經(jīng)典同步問題

803.5經(jīng)典同步問題

—補充例子進程R的偽代碼描述ProcessR{intx;L1:takeanumberfromdevice;//讀數(shù)x=number;

B=x;//讀數(shù)后存入緩沖區(qū)if(B==奇數(shù))通知w1進程else通知w2進程;gotoL1;}3.5經(jīng)典同步問題

813.5經(jīng)典同步問題

—補充例子進程w1,w2的偽代碼描述：ProcessW1{inty;L2:

y=B;//取數(shù)printthenumbery;gotoL2;}ProcessW2{intz;L3:

z=B;printthenumberz;gotoL3;}3.5經(jīng)典同步問題

823.5經(jīng)典同步問題

—補充例子分析問題哪個進程看成是生產(chǎn)者，哪個是消費者？把R看成是生產(chǎn)者，把進程W1和W2看成消費者。生產(chǎn)者(R進程)生產(chǎn)不同的產(chǎn)品(奇數(shù)或偶數(shù))，存入緩沖器B，供不同的消費者(W1和W2進程)取用。3.5經(jīng)典同步問題

833.5經(jīng)典同步問題

—補充例子需要發(fā)送的消息是什么以及消息個數(shù)?當進程R讀入的是奇數(shù)，則要把有奇數(shù)的消息發(fā)送給進程W1；當進程R讀入的是偶數(shù)，則要把有偶數(shù)的消息發(fā)送給W2。在進程W1和W2從緩沖器中取出數(shù)后，應把緩沖器中又可以存一個數(shù)的消息告訴給進程R。3.5經(jīng)典同步問題

843.5經(jīng)典同步問題

—補充例子分析信號量個數(shù)及其分別代表的含義 通過上述分析得知，需要發(fā)送三個消息，所以需要定義三個信號量，分別用S，SO，SE表示如下：S：表示是否可以把數(shù)存入緩沖器，由于緩沖器中每次只能存放一個數(shù)，初始緩沖區(qū)為空，所以它的初值為“1”SO：表示緩沖器中是否有奇數(shù)，初值為“0”，表示開始無奇數(shù)SE：表示緩沖器中是否有偶數(shù)，初值為“0”，表示開始無偶數(shù)3.5經(jīng)典同步問題

853.5經(jīng)典同步問題

—補充例子根據(jù)上面的分析，得出信號量的定義和變量定義如下：intB;SemaphoreS,SO,SE;S=1;SO=0;SE=0;ProcessR{intx;L1:takeanumberfromdevice;x=number;

P(S);B=x;if(B==奇數(shù))

V(SO);

elseV(SE);gotoL1;}3.5經(jīng)典同步問題

863.5經(jīng)典同步問題

—補充例子ProcessW1{inty;L2:

P(SO);y=B;

V(S);printthenumbery;gotoL2;}ProcessW2{intz;L3:

P(SE);z=B;

V(S);printthenumberz;gotoL3;}3.5經(jīng)典同步問題

873.5經(jīng)典同步問題

—總結總結進程的互斥實際上是進程同步的一種特殊情況，若干進程互斥使用資源時，一個等待使用資源的進程在等待占用資源的進程發(fā)出“歸還資源”的消息后，它就可去使用資源。因此互斥使用資源的進程實際上也存在一種一個進程依賴另一個進程發(fā)出消息的制約關系。把用來解決進程互斥與同步的機制（如PV操作）稱為同步機制3.5經(jīng)典同步問題

883.5經(jīng)典同步問題

—總結進程互斥與進程同步是有區(qū)別的進程的互斥是進程間競爭共享資源的使用權，這種競爭沒有固定的必然聯(lián)系。哪個進程競爭到使用權則共享資源就歸哪個進程使用，直到不需要使用時再歸還使用權任何進程可競爭使用空閑的共享資源，即使該進程剛剛使用過該共享資源。若此時無其它進程要使用這個共享資源，那么該進程仍可再次使用該共享資源。3.5經(jīng)典同步問題

893.5經(jīng)典同步問題

—總結進程互斥與進程同步是有區(qū)別的而進程的同步就不同了，涉及共享資源的并發(fā)之間有一種必然的依賴關系。當進程必須同步時，即使沒有進程在使用共享資源，還沒有得到同步消息的進程也不能去使用這個資源3.5經(jīng)典同步問題

903.5進程的同步與互斥混合

—生產(chǎn)者與消費者問題敘述 討論m個生產(chǎn)者和r個消費者怎樣共享容量為n的緩沖器，假定每個生產(chǎn)者都要把各自生產(chǎn)的物品存入緩沖器，而每個消費者也都要從緩沖器中取出物品去消費。得出結論 在這個問題中，不僅生產(chǎn)者與消費者之間存在同步，而且m個生產(chǎn)者之間，r個消費者之間還必須互斥的訪問緩沖器。3.5進程的同步與互斥混合

913.5進程的同步與互斥混合

—生產(chǎn)者與消費者問題提出 我們發(fā)現(xiàn)生產(chǎn)者和消費者之間應該同步這是顯而易見的，只有互通消息才能知道是否可以存放物品或者是否可以從緩沖器中取出物品。為什么生產(chǎn)者和消費者之間需要互斥訪問緩沖器呢？3.5進程的同步與互斥混合

923.5進程的同步與互斥混合

—生產(chǎn)者與消費者intB[n],k=0,t=0;SemaphoreSP=n,SG=0;Processproduceri(i=1,2…n){L1：produceaproduct;

P(SP);B[k]=product;k=(k+1)%n;

V(SG);gotoL1;}Processproducerj(j=1,2,…n){L2：P(SG);takeaproductfromB[t];t=(t+1)%n;

V(SP);gotoL2;}分析：如果不進行互斥，結果會產(chǎn)生什么樣的錯誤？3.5進程的同步與互斥混合

933.5進程的同步與互斥混合

—生產(chǎn)者與消費者分析理由－生產(chǎn)者如果m個生產(chǎn)者各自生產(chǎn)了物品都要存入緩沖器中，當?shù)谝粋€生產(chǎn)者按指針k指示的位置放入了一件物品，但在改變指針之前可能被打斷執(zhí)行，于是當?shù)诙€生產(chǎn)者要存放物品時將仍按原先的指針值所指的位置存放物品，這樣兩件物品被重復存放在同一位置上由于系統(tǒng)進程生產(chǎn)的物品往往是數(shù)據(jù)，當重復的在一個位置存放數(shù)據(jù)，必定是后者覆蓋了前者，造成數(shù)據(jù)的丟失，所以存放物品時必須互斥。3.5進程的同步與互斥混合

943.5進程的同步與互斥混合

—生產(chǎn)者與消費者分析理由－消費者同理，r個消費者都要取物品時，也可能出現(xiàn)從指針t相同的位置取物品，造成一件物品被重復多次取出，這也是錯的，因此取物品時也必須互斥。3.5進程的同步與互斥混合

953.5進程的同步與互斥混合

—生產(chǎn)者與消費者同步信號量分析m個生產(chǎn)者和r個消費者之間進行同步操作需要互通的消息還是兩個：即緩沖器中是否可以存放物品和緩沖器中是否已經(jīng)有物品。仍用SP和SG表示，SP的初值為“n”，(n表示緩沖區(qū)的空閑個數(shù))，SG的初值仍為“0”。3.5進程的同步與互斥混合

963.5進程的同步與互斥混合

—生產(chǎn)者與消費者互斥信號量分析共享變量k、t是臨界資源對共享變量k與t的操作必須互斥，所以定義兩個用于互斥的信號量S1和S2信號量S1用于m個生產(chǎn)者之間互斥的往緩沖器中存放物品信號量S2用于r個消費者之間互斥的從緩沖器中取物品S1、S2初值都為“1”，表示開始無進程進入臨界區(qū)。3.5進程的同步與互斥混合

973.5進程的同步與互斥混合

—生產(chǎn)者與消費者intB[n],k=0,t=0;SemaphoreSP=n,SG=0，S1＝1，S2＝1；Processproduceri(i=1,2…n){L1：produceaproduct;

P(SP);P(S1);B[k]=product;k=(k+1)%n;

V(S1);

V(SG);gotoL1;}Processproducerj(j=1,2,…n){L2：P(SG);P(S2);takeaproductfromB[t];t=(t+1)%n;

V(S2);V(SP);consume;gotoL2;}3.5進程的同步與互斥混合

983.5進程的同步與互斥混合

—生產(chǎn)者與消費者互斥信號量與同步信號量的位置可以交換Processproduceri(i=1,2…n){L1：produceaproduct;

P(S1);

P(SP);B[k]=product;k=(k+1)%n;

V(SG);V(S1);gotoL1;}Processproducerj(j=1,2,…n){L2：P(S2);

P(SG);takeaproductfromB[t];t=(t+1)%n;

V(SP);V(S2);consume;gotoL2;}3.5進程的同步與互斥混合

993.5讀者與寫者問題問題描述假定有某個共享文件F，系統(tǒng)允許進程對文件F讀和寫，規(guī)定讀者與寫者互斥，寫者與寫者互斥，多個讀者可以同時讀。讀者與寫者進程的偽代碼ProcessReader{readfileF;}ProcessWriter{writefileF;}3.5讀者與寫者問題問題描述ProcessReaderP1003.5讀者與寫者問題問題分析共享資源：文件F臨界區(qū)：讀、寫文件ProcessReader{

readfileF;}ProcessWriter{

writefileF;}3.5讀者與寫者問題問題分析ProcessReaderP1013.5讀者與寫者問題情況一不考慮多個讀者可以同時讀，或假設只有一個讀者，則問題轉(zhuǎn)為簡單的互斥問題實現(xiàn)讀者與寫者的互斥，讀者與讀者的互斥，寫者與寫者的互斥，即全互斥問題信號量的分析因只有一個共享資源F，定義一個互斥信號量即可，用S表示信號量S的初始值為”1”3.5讀者與寫者問題情況一1023.5讀者與寫者問題情況一的解決方法

SemaphoreS=1;ProcessReader{

P(S);readfileF;

V(S);}ProcessWriter(j=1,2,3…n){

P(S);writefileF;

V(S);}3.5讀者與寫者問題情況一的解決方法ProcessRea1033.5讀者與寫者問題情況二再考慮多個讀者允許同時讀，以及多個讀者與寫者的互斥情況則第一個讀者與寫者存在互斥關系，即只要有一個讀者正在讀文件，則寫者不能進行寫操作當沒有讀者的時候，允許寫者進程寫操作3.5讀者與寫者問題情況二1043.5讀者與寫者問題問題的分析讀者是否在讀決定寫進程是否可以寫，所以需要引入一個變量count來記錄讀者的個數(shù)當?shù)谝粋€讀者進行讀操作，寫進程就不能執(zhí)行，當讀者個數(shù)為“0”，寫進程才可以執(zhí)行當一個讀者進行讀文件操作，則讀者個數(shù)加一，當一個讀者退出，則個數(shù)減一3.5讀者與寫者問題問題的分析1053.5讀者與寫者問題修改后進程的偽代碼ProcessReader(i=1,2,3…n){

count++;P(S);readfileF;

count--;V(S);}ProcessWriter(j=1,2,3…n){

P(S);writefileF;

V(S);}讀寫進程的互斥關系不變存在問題：沒有實現(xiàn)多個讀者同時讀操作3.5讀者與寫者問題修改后進程的偽代碼ProcessRe1063.5讀者與寫者問題問題的提出對于讀者進程，第一個進程需要通過P操作來申請進入臨界區(qū)，而后續(xù)讀進程可以直接進入臨界區(qū)讀進程釋放臨界資源的條件是：所有讀進程都退出臨界區(qū)后V操作的執(zhí)行應該是讀者個數(shù)為0的時候3.5讀者與寫者問題問題的提出1073.5讀者與寫者問題修改后進程的偽代碼ProcessReader(i=1,2,3…n){

count++;

if(count==1)P(S);

readfileF;

count--;

if(count==0)V(S);}ProcessWriter(j=1,2,3…n){

P(S);writefileF;

V(S);}讀寫進程的互斥關系不變3.5讀者與寫者問題修改后進程的偽代碼ProcessRe1083.5讀者與寫者問題讀進程P(S)、V(S)操作的理解ProcessReader(i=1,2,3…n){

count++;

if(count==1)P(S);(申請進入臨界區(qū),相當阻 止寫進程)

readfileF;

count--;

if(count==0)V(S);(退出臨界區(qū)，相當歸還 資源，允許寫進程)}ProcessWriter(j=1,2,3…n){

P(S);writefileF;

V(S);}讀寫進程的互斥關系不變3.5讀者與寫者問題讀進程P(S)、V(S)操作的理解Pr1093.5讀者與寫者問題信號量的分析讀者進入與退出需要對count變量進行修改所以當多個讀者進程對count變量值進行修改時必須互斥，否則會一起count變量值的不確定性定義一個與共享變量count有關的互斥信號量用SC表示又讀者與寫者之間要互斥，信號量S不變3.5讀者與寫者問題信號量的分析1103.5讀者與寫者問題信號量初始值的分析兩個信號量主要用于控制互斥操作，所以SC和S的初始值都為1。SC初值為1，互斥的count變量一個，且初始讀者還沒有開始進行讀操作，可用Ｓ初值為１，表示一個可用資源(文件Ｆ)可以使用，表示初始讀寫進程都可以進入臨界區(qū)。3.5讀者與寫者問題信號量初始值的分析1113.5讀者與寫者問題考慮對讀進程的互斥處理ProcessReader(i=1,2,3…n){

count++;

if(count==1)P(S);

readfileF;

count--;

if(count==0)V(S);}ProcessWriter(j=1,2,3…n){

P(S);writefileF;

V(S);}Semaphore

Sc=1;S=1;3.5讀者與寫者問題考慮對讀進程的互斥處理Process1123.5讀者與寫者問題PV操作處理后進程的偽代碼ProcessReader(i=1,2,3…n){

P(SC);count++;if(count==1)P(S)；

V(SC);readfileF;

P(SC);count--;if(count==0)V(S);

V(SC);}ProcessWriter(j=1,2,3…n){

P(S);writefileF;

V(S);}Semaphore

Sc=1;S=1;3.5讀者與寫者問題PV操作處理后進程的偽代碼Proces1133.5讀者與寫者問題總結對每個共享資源（變量）都要設置相應的信號量對每個信號量的PV操作都要成對出現(xiàn)。讀者寫者問題，關鍵是理解第一個讀者與寫者的互斥關系，所以需要讀者個數(shù)的統(tǒng)計變量，從而產(chǎn)生對共享變量操作引起的互斥問題3.5讀者與寫者問題總結114第三章進程的并發(fā)控制

——互斥與同步與時間有關的錯誤問題進程協(xié)調(diào)的概念對臨界區(qū)管理的準則簡單的同步機制（標志法）信號量機制（實現(xiàn)進程互斥與同步的控制）第三章進程的并發(fā)控制

——互斥與同步與時間有關的錯誤問1153.1程序的兩種執(zhí)行方式程序的順序執(zhí)行程序在運行的時獨占系統(tǒng)資源，且系統(tǒng)按照程序步驟順序執(zhí)行地執(zhí)行，在該程序執(zhí)行完之前，其他程序只能等待。程序的并發(fā)執(zhí)行多道程序設計的系統(tǒng)中，若干個作業(yè)可以同時執(zhí)行，這些進程輪流地占用CPU，即一個進程的工作沒有全部完成之前，另一個進程就可開始工作，我們說這些執(zhí)行的進程具有并發(fā)性。3.1程序的兩種執(zhí)行方式程序的順序執(zhí)行1163.1與時間有關的錯誤問題(1)問題描述：設有一個游樂場設置了一個自動計算機系統(tǒng)，用一個變量count指示在場的人數(shù)，當有人進入，則PIN進程完成count++，當有人退出，則POUT進程完成count--進程PINProcessPIN{intR1;R1=count;R1=R1+1;count=R1;}進程POUTProcessPOUT{intR2;R2=count;R2=R2-1;count=R2;}3.1與時間有關的錯誤問題(1)問題描述：設有一個游樂場設1173.1與時間有關的錯誤問題(1)兩個進程的順序執(zhí)行（不產(chǎn)生錯誤）假設某一時刻count=n

intR1;R1=count;R1=R1+1;count=R1;intR2;R2=count;R2=R2-1;count=R2;正確結果count=n不變假設某一時刻count=nintR2;R2=count;R2=R2-1;count=R2;intR1;R1=count;R