華聯(lián)學院《操作系統(tǒng)原理》課件06進程間的制約關(guān)系

1、第6章 進程間的制約關(guān)系6.16.26.3本章講述內(nèi)容：進程間的制約關(guān)系 ；信號量與P、V操作 ；死鎖、高級進程通信。 為輸出井設置一張 “輸出井文件目錄表”，它由若干目錄項組成。每個目錄項記錄一個要打印輸出的文件名以及該文件在磁盤的存放地址。6.1 進程間的制約關(guān)系6.1.1與時間有關(guān)的錯誤與時間有關(guān)的錯誤1. 進程的并發(fā)，使一個進程何時占有處理機、占有多長時間、執(zhí)行速度的快慢、以及外界對進程產(chǎn)生作用等都帶有隨機性。因此，一個進程對其他進程的影響無法預測。在操作系統(tǒng)里，把這種由于時間因素的影響而產(chǎn)生的錯誤，稱為“與時間有關(guān)的錯誤”。 例：對輸入井文件目錄的管理2.讀in的當前內(nèi)容 ;根據(jù)指點

2、，存入打印文件名 ;in的值加1 ;test . cgroup . probit . txt45674out7in輸入井文件目錄表“井管理寫” 程序. 為管理該目錄表，系統(tǒng)安排兩個指針：out和in?！熬忀敵龀绦颉备鶕?jù)out的指點進行打印，out總是指向下一個被打印的文件；井管理寫程序根據(jù)in的指點存放要求輸出的文件目錄信息，in總是指向下一個可用的目錄項位置。. 再次調(diào)度進程A運行，從斷點往下做。由于它已做讀in的操作，就把文件“games”存入輸出井文件目錄表中的第7個表目，把原來里面進程B的文件名刪去，并且把in更新為9（因為進程B已把in改為8了），然后做其他的操作。 若現(xiàn)在進程A要求

3、打印名為“games”的文件。為此調(diào)用“井管理寫”程序。在做了準備工作后，讀出in中當前的內(nèi)容為7。恰在此時，系統(tǒng)分配給進程A的時間片到，調(diào)度進程B運行。假定現(xiàn)在進程B要求打印文件“mail”，于是也去調(diào)用“井管理寫”程序。在做了準備工作后，它讀取in中的內(nèi)容。此時，in中的值沒改變，得到的仍為7。于是把它的文件“mail”存入輸出井文件目錄表中的第7個表目，并把in改為8，然后做其他的操作。. 這樣一來，進程B要輸出的文件信息全無，永遠也得不到任何打印輸出。另外，輸出井文件目錄表的表目8被跳過去了，它里面沒有記錄下任何要輸出的文件信息。從而產(chǎn)生了“與時間有關(guān)的錯誤”。 .3.例：通過雙緩沖區(qū)

4、復制文件. 編寫復制n個記錄的程序，它把文件F中的記錄依次讀到輸入緩沖區(qū)R，再從R拷貝到輸出緩沖區(qū)T，最后寫到文件G中。假定R和T正好存放一個記錄。寫下面三個子程序作為進程來完成整個工作： (1)GET：從文件F按照順序讀出一個記錄，然后送入輸入緩沖區(qū)R；(2)COPY：把輸入緩沖區(qū)R里的記錄拷貝到輸出緩沖區(qū)T里；(3)PUT：從輸出緩沖區(qū)T里讀出一個記錄，然后依照順序?qū)懭胛募礼。讀in的當前內(nèi)容 ;根據(jù)指點，存入打印文件名 ;in的值加1 ;test . cgroup . probit . txt45674out7in輸入井文件目錄表“井管理寫” 程序 復制時，若COPY已把R里的記錄拷貝到

5、了T中，那GET和PUT就可并發(fā)執(zhí)行了。即GET從F里讀下一個記錄送到R中的操作，與PUT從T中取出內(nèi)容寫入G的操作，誰先誰后都沒有關(guān)系，不會影響到復制結(jié)果的正確性。由于利用并發(fā)性，工作效率就會提高。記錄1記錄2記錄nGETCOPYPUT文件F記錄1記錄2記錄n文件G輸入緩沖區(qū)R輸出緩沖區(qū)T. 若不顧及這三者間執(zhí)行順序的內(nèi)在制約關(guān)系，隨意讓GET、COPY、PUT并發(fā)執(zhí)行，那么就會產(chǎn)生“與時間有關(guān)的錯誤”。. 不管GET、COPY、PUT的執(zhí)行關(guān)系，有六種可能的執(zhí)行順序：1）COPYPUTGET；2）COPYGETPUT；3）PUTCOPYGET；4）PUTGETCOPY；5）GETCOPYP

6、UT；6）GETPUTCOPY. 假定現(xiàn)在處于如圖所示的狀態(tài)，文件F的第1個記錄已順利地復制到了文件G，文件F的第2個記錄也已由GET讀到了輸入緩沖區(qū)R中。 記錄3記錄4記錄n文件F記錄2記錄1文件GRT記錄1.GETPUT記錄1記錄1文件GRT記錄3記錄4記錄n文件F記錄1記錄4記錄n文件F記錄3記錄1文件GRT記錄1COPY記錄1記錄4記錄n文件F記錄3記錄3文件GRT記錄1123比如在前圖基礎(chǔ)上，來看第6種可能“GETPUTCOPY”時導致的錯誤結(jié)果。 . 這時先執(zhí)行GET，把文件F中的第3個記錄讀入緩沖區(qū)R，致使原來R中的記錄2被刪去，由記錄3代替，如圖(a)所示。 (a). 然后，執(zhí)

7、行PUT，把現(xiàn)在還在輸出緩沖區(qū)中的記錄1寫入到文件G中，成為它的第2個記錄，如圖(b)所示。 .(b)(c) 最后做COPY，把記錄3從R拷貝到T中，如圖(c)所示。 . 由于沒有遵循三個程序在執(zhí)行順序上的限制，復制過程中，丟失了第2個記錄，第1個記錄在文件G里重復復制了兩次。導致了“與時間有關(guān)的錯誤”的發(fā)生。6.1.2 競爭資源互斥 若在進程A用完變量in（即取出in的值，把文件按其指點存入輸出井目錄表，把in的值加1）后，進程B才去用in ，那是不會發(fā)生“與時間有關(guān)的錯誤”的。同樣地，若在進程B用完變量in后，進程A才去用，那么也不會發(fā)生“與時間有關(guān)的錯誤”。1.輸入井文件目錄管理導致“與

8、時間有關(guān)的錯誤”的分析. 例子里進程A和B沒有任何直接的關(guān)系，各做各的事情。不過，當它們要輸出時，都要訪問變量in。也就是說，in是它們的共享變量。 . 現(xiàn)在是在A取出變量in的值、還沒按其指點往目錄表中存放文件信息、沒對in實行加1操作的情況下，B就去用了變量in，從而導致了“與時間有關(guān)的錯誤”。 . 很明顯，A和B誰先做或誰先用in都沒關(guān)系，重要的是它們不能同時用in。“不能同時”的含義是：在一個進程已開始用in、且還沒有用完時，不允許另一個進程也用in，即它們對in的使用必須“互斥”。 在操作系統(tǒng)中，凡牽扯到數(shù)據(jù)、隊列、緩沖區(qū)、表格和變量等任何形式的共享資源時，都容易出現(xiàn)這種“與時間有關(guān)

9、的錯誤”。為避免錯誤的發(fā)生，關(guān)鍵是要找到一種途徑，來阻止多于一個進程同時使用它們。 . 稱可以共享的資源（文件、隊列、變量等）為共享變量或臨界資源。為保證與一個共享變量交往的多個進程各自運行的正確性，當其中一個進程正在對該變量進行操作時，絕不允許其他進程同時對它進行操作。進程間的這種制約關(guān)系被稱為“互斥”。2.互斥與臨界區(qū).讀in的當前內(nèi)容 ;根據(jù)指點，存入打印文件名 ;in的值加1 ;test . cgroup . probit . txt45674out7in輸入井文件目錄表“井管理寫” 程序 一個進程在臨界區(qū)內(nèi)逗留有限時間后，就應該退出，以便給其他進程創(chuàng)造進入臨界區(qū)的機會。 如果有若干個

10、進程要求進入自己的臨界區(qū)，那么它們不應互相排斥，致使誰也進不了臨界區(qū)。 . 在進程程序中，涉及到共享變量的那一部分程序，才真正需要保證互斥地執(zhí)行。在操作系統(tǒng)中，把進程程序中“真正需要保證互斥執(zhí)行”的那一段程序，稱為該進程的“臨界區(qū)（或臨界段）”。 3.設計互斥進程的注意事項.每次只允許一個進程進入臨界區(qū)。 具有互斥關(guān)系的進程，它的一部分程序可能用于內(nèi)部的計算，用于內(nèi)部的數(shù)據(jù)處理等。只有涉及共享變量的那一部分程序，才真正需要保證互斥地執(zhí)行。 . 有互斥關(guān)系的進程，并不關(guān)心對方的存在性。即使對方不存在，自己也能夠正確的運行，不會受到它存在與否的影響。 . 有互斥關(guān)系的那些進程程序中的臨界區(qū)，雖然都

11、是針對同一個共享變量的程序段，但在其上的操作可以相同也可以不相同。 . 進程的臨界區(qū)是相對于某個共享變量而言的，不同共享變量的臨界區(qū)之間，不存在互斥關(guān)系。 設計進程臨界區(qū)時必須遵循的準則 4.6.1.3 協(xié)同工作同步1.用雙緩沖區(qū)復制文件導致“與時間有關(guān)的錯誤”的分析. 在GET沒把記錄從F讀到R前，COPY不能把R中的內(nèi)容拷貝到T中去；在COPY沒把R中的內(nèi)容拷貝到T之前，GET不得把下一個記錄從F讀到R中。即只有GET先于COPY工作，COPY的工作才正確；只有COPY取走了R中的內(nèi)容，GET做下一步工作才正確。COPY與PUT之間也有這種關(guān)系，這是進程之間由于協(xié)同工作而產(chǎn)生的一種直接關(guān)系

12、。 2.保證GET和COPY間協(xié)調(diào)一致的作法從文件F取出一個記錄送至輸入緩沖區(qū)R向COPY發(fā)送“可以拷貝” 的消息等待COPY發(fā)來的“拷貝結(jié)束”的消息等待GET發(fā)來“可以拷貝” 的消息將輸入緩沖區(qū)R里的記錄拷貝到輸出緩沖區(qū)T里向GET發(fā)送“拷貝結(jié)束”的消息GETCOPY1.1.2.2.3.3. GET讀記錄到R后，給COPY發(fā)消息，告訴它R中已有記錄，然后暫停，等待COPY發(fā)來 “拷貝結(jié)束”的消息。只有接到這個消息，GET才能往下做。. COPY一直等待。只有接到GET發(fā)來 “可以拷貝”的消息才能工作，將R里的記錄拷到T里，然后向GET發(fā)“拷貝結(jié)束”的消息，隨之又等待GET發(fā)消息。 . 正是由

13、于例中的GET、COPY、PUT之間沒有保持這種關(guān)系，因此產(chǎn)生了所謂的“與時間有關(guān)的錯誤”。記錄1記錄2記錄nGETCOPYPUT文件F記錄1記錄2記錄n文件G輸入緩沖區(qū)R輸出緩沖區(qū)T一個進程需要等待另一個進程完成的操作或發(fā)送的信息，稱為“同步條件”。 一個進程運行到某點時，除非合作進程已經(jīng)完成了某種操作或發(fā)來了信息，否則就必須暫時等待那些操作的完成或信息的到來。進程間的這種關(guān)系被稱為“同步”。 .4.同步、同步點、同步條件.暫停等待以取得同步的那一點，稱為“同步點”。.3.設計有直接制約關(guān)系進程時應注意的問題. 具有這種關(guān)系的進程，需要在某些點上協(xié)調(diào)相互的動作，誰先到達誰后到達是有順序要求的

14、。比如，GET應先在R中為COPY準備好記錄，并向COPY發(fā)送“可拷貝”的消息。這樣，當COPY運行時就有數(shù)據(jù)可用了。如果COPY先于GET到達等待GET發(fā)來“可拷貝” 消息的地方，那么由于GET還沒有為它準備好數(shù)據(jù)，它就只能等待。 . 這些進程都應了解對方的工作，對方如果不存在，或任何一方單獨運行，就會出現(xiàn)差錯。比如，GET應知道COPY只有得到自己給它的數(shù)據(jù)后，才能往下運行。COPY應該知道GET只有在得到它發(fā)出的“拷貝結(jié)束”消息后，才能繼續(xù)做。只有這樣配合，才能保證它們處于正常的工作狀態(tài)。 一方或雙方的運行會直接地依賴于對方所產(chǎn)生的信息或發(fā)出的消息。比如，GET和COPY之間是雙方都依賴

15、于對方發(fā)來的消息，接收不到對方的消息，自己就一直保持等待。 6.2.1 信號量與P、V操作的定義1.信號量的定義 所謂“信號量”，是一個具有非負初值的整型變量，并有一個隊列與它關(guān)聯(lián)。因此，定義一個信號量S時，要給出它的初值Vs，給出與它相關(guān)的隊列指針Vq。在一個信號量S上，只能做規(guī)定的兩種操作：P操作，記為P(S)；和V操作，記為V(S)。 2.信號量S上的P操作定義 6.2 信號量與P、V操作3.信號量S上的V操作定義 當一個進程調(diào)用P（S）時，應該順序做下面兩個不可分割的動作： (1) Vs=Vs-1，即把當前信號量S的取值減1； (2) 若Vs=0，則調(diào)用進程繼續(xù)運行；若Vs0，則調(diào)用進

16、程繼續(xù)運行；若Vs=0，則表示可給該進程分一個資源；若Vs0，表示現(xiàn)在已沒有資源可分配，進程只能阻塞，到隊列Vq上去等待，這時Vs的絕對值恰是提出資源請求、但沒有分配到資源的進程個數(shù)。某進程在S上做一次V操作后，若Vs0，表示原資源等待隊列上沒有進程等待，只是收回了一個資源。 2.簡單的“生產(chǎn)者-消費者”問題生產(chǎn)者：生產(chǎn)一個產(chǎn)品P(M)(申請一個緩沖區(qū))按in指點將物品存入緩沖區(qū)in=(in+1) mod 10(調(diào)整存入指針in)V(N)(向消費者發(fā)消息，緩沖區(qū)里已有物品)消費者：消費物品P(N)(等待生產(chǎn)者發(fā)來消息)按out指點從緩沖區(qū)取出物品out=(out+1) mod 10(調(diào)整取出指

17、針out)V(N)(向生產(chǎn)者發(fā)消息，已有空緩沖區(qū))Vm=10Vn=0(M,N初值) 若有一個生產(chǎn)者和一個消費者，他們共享10個緩沖區(qū)。生產(chǎn)者不斷地生產(chǎn)物品，并依次放入緩沖區(qū)中。消費者依次從緩沖區(qū)里取出物品進行消費。只有在緩沖區(qū)有空位時，生產(chǎn)者生產(chǎn)出來的物品才能往里存放；只有在緩沖區(qū)有物品時，消費者才能從里面取出物品消費。試用 P、V 操作來協(xié)調(diào)生產(chǎn)者和消費者間的工作。 設置4個信號量：m為空閑緩沖區(qū)的數(shù)目；n為已放物品緩沖區(qū)的數(shù)目；S1控制互斥進入in臨界區(qū)；S2控制互斥進入out臨界區(qū)。6.2.5 互斥/同步樣例分析1.“生產(chǎn)者-消費者”問題 若有 i 個生產(chǎn)者和j 個消費者，共享 k個緩沖

18、區(qū)。生產(chǎn)者不斷生產(chǎn)物品，并依次放入緩沖區(qū)中。消費者依次從緩沖區(qū)里取出物品進行消費。只有在緩沖區(qū)里有空位時，生產(chǎn)者生產(chǎn)出來的物品才能往里面放；只有在緩沖區(qū)里有物品時，消費者才能從里面取出物品進行消費。試用P、V操作協(xié)調(diào)生產(chǎn)者和消費者之間的工作。生產(chǎn)者：生產(chǎn)一個產(chǎn)品P(M)(申請一個緩沖區(qū))按in指點將物品存入緩沖區(qū)in=(in+1) mod k(調(diào)整存入指針in)V(N)(向消費者發(fā)消息，緩沖區(qū)里已有物品)消費者：消費物品P(N)(等待生產(chǎn)者發(fā)來消息)按out指點從緩沖區(qū)取出物品out=(out+1) mod k(調(diào)整取出指針out)V(N)(向生產(chǎn)者發(fā)消息，已有空緩沖區(qū))Vm=k,Vn=0Vs

19、1=1,Vs2=1(信號量初值)P(S1)(要求進入in 臨界區(qū))V(S1)(退出in 臨界區(qū))P(S2)(要求進入out 臨界區(qū))V(S2)(退出out 臨界區(qū)). 設置兩個信號量：MUTEX控制讀者互斥進入reader臨界區(qū)，WRT控制讀者及寫者互斥進入讀/寫臨界區(qū)，初值都是1。reader=reader-1(讀者計數(shù)器減1)2.“讀者-寫者”問題讀者：reader=1?(是第1個讀者?)P(MUTEX)(進入reader臨界區(qū))讀者讀取所需信息reader=reader+1(讀者計數(shù)器加1)V(MUTEX)(退出reader臨界區(qū))P(WRT)(進入讀/寫臨界區(qū))P(MUTEX)(進入r

20、eader臨界區(qū))reader=0?(是最后一個讀者?)V(MUTEX)(退出reader臨界區(qū))V(WRT)(退出讀/寫臨界區(qū))NNYYP(WRT)(進入讀/寫臨界區(qū))寫者對數(shù)據(jù)進行修改V(WRT)(退出讀/寫臨界區(qū))寫者： 若一批數(shù)據(jù)被多個并發(fā)進程共享，其中一些進程只要求讀數(shù)據(jù)，稱為“讀者”；另一些會對數(shù)據(jù)進行修改，稱為 “寫者”。多個讀者同時工作時，訪問不會有問題。但是如果讀者和寫者或?qū)懻吆蛯懻咄瑫r工作時，就有可能導致錯誤訪問結(jié)果。假定在有讀者訪問時，到來寫者要求訪問，那么寫者只能等待，但到來的后續(xù)讀者仍可以進行訪問，這表示讀者比寫者有更高的訪問權(quán)。試用P、V操作來協(xié)調(diào)讀者和寫者之間的工

21、作。 . 設一個初值為0的變量reader，它不是信號量，而是用來隨時記錄當前有多少個讀者在同時使用數(shù)據(jù)。正因為允許多個讀者同時使用數(shù)據(jù)，reader成為各讀者共享的變量，所以要設置信號量MUTEX來控制讀者互斥地使用它。. 互斥條件：每個資源每次只能分配給一個進程使用。 循環(huán)等待條件：系統(tǒng)中存在兩個以上的進程，它們組成一個環(huán)路，該環(huán)路中的每個進程都在等待其相鄰進程占用的資源。 部分分配（占用并等待）條件：進程由于申請不到所需要的資源而等待時，仍然占據(jù)著已經(jīng)分配到的資源。 6.3 死鎖、高級進程通信6.3.1 死鎖與產(chǎn)生死鎖的必要條件資源分配圖1. 用方框代表資源，圓圈代表進程。畫一條由資源到

22、進程的有向邊，表示把該資源分配給這個進程；畫一條由進程到資源的有向邊，表示該進程要申請這個資源。這樣的圖就是所謂的 “ 資源分配圖 ”。 ARBSDCTU死鎖的定義2. 所謂“死鎖”，即指系統(tǒng)中若存在一組進程，它們中的每一個都占用了某種資源而又都在等待其中另一個所占用的資源，這種等待永遠不會結(jié)束。這就是死鎖，或說這一組進程處于死鎖狀態(tài)。 產(chǎn)生死鎖的四個必要條件3.非剝奪條件：已經(jīng)分配給進程的資源，別的進程不能強行奪取。 6.3.2 死鎖的預防1.死鎖預防的含義 所謂“死鎖的預防”，是指破壞產(chǎn)生死鎖四個必要條件中的一條或幾條，以使系統(tǒng)不會產(chǎn)生死鎖。在死鎖預防里，主要是破壞其他幾個必要條件，而不去

23、破壞“互斥條件”。 2.破壞“部分分配（占用并等待）條件” 采用的辦法是系統(tǒng)對進程實行一次性分配方案，即一個進程總是合盤提出總的資源需求，系統(tǒng)要么分配給它所需要的全部資源，要么一個也不給它。 3.破壞“非剝奪條件” 采用的辦法是允許別的進程從占用進程手中強搶所占用的資源。 4.破壞“循環(huán)等待條件” 采用的辦法是將系統(tǒng)中的所有資源進行統(tǒng)一編號，進程按編號的順序，由小到大提出對資源使用的申請。假定把不同編號的資源i和j分配給了進程A和B。那么如果ij，A就不允許再申請資源j；如果ij，B就不允許再申請資源 i 。這樣就形成不了資源申請的循環(huán)等待環(huán)路 。AiABijBj1.輸入機2.打印機3.繪圖儀

24、4.磁帶機5.CD-ROM.1.死鎖避免的含義 指允許系統(tǒng)存在產(chǎn)生死鎖的條件，但在接到一個進程的資源請求時，總是根據(jù)當時資源的使用情況，按照一定的算法去模擬分配，探測分配的結(jié)果。只有在探測結(jié)果表明絕對不會出現(xiàn)死鎖時，才真正接受進程的這次資源請求。 2.安全狀態(tài)和不安全狀態(tài). 若能在有限時間內(nèi)，保證所有進程得到自己需要的全部資源，那么稱系統(tǒng)此時處于“安全狀態(tài)”；否則稱系統(tǒng)處于“不安全狀態(tài)”。很明顯，在系統(tǒng)處于安全狀態(tài)時，絕對不會發(fā)生死鎖；在系統(tǒng)處于不安全狀態(tài)時，系統(tǒng)有可能發(fā)生死鎖。 3.銀行家算法對進程的要求.必須預先說明自己對資源的最大需求量； 只能一次一個地申請所需要的資源； . 若已獲得了

25、資源的最大需求量，那么應在有限時間內(nèi)使用完畢，并歸還系統(tǒng)。 4.實施銀行家算法時系統(tǒng)的承諾. 若進程對資源的最大需求量沒超過該資源的總量，應保證接納這個進程，不得拒絕它； 在接到一個進程對資源的請求時，有權(quán)根據(jù)當前資源的使用情況暫時加以拒絕（即阻塞該進程）。但應保證在有限的時間內(nèi)讓它得到所需要的資源。 6.3.2 死鎖的避免 如果所有進程的“能執(zhí)行完”均為1，表示接受這次請求是安全的；否則暫時不能接受進程的這次資源請求。 如果找到了，就假設它獲得了最大資源數(shù)，并運行結(jié)束。于是把它的“能執(zhí)行完”標志置為1。這樣就能假定收回它使用的所有資源，使系統(tǒng)剩余資源數(shù)增加。 在這一假設下，檢查每個進程對資源

26、的還需要數(shù)。看能否找到一個進程，其還需數(shù)目小于系統(tǒng)剩余資源數(shù)。如果找不到，那么系統(tǒng)就有可能死鎖，因為任何進程都無法運行結(jié)束。 在安全狀態(tài)下，系統(tǒng)接到進程的資源請求后，先假定接受這一請求，把需要的資源分配給這個進程。 5.單種資源銀行家算法的基本思想單種資源銀行家算法：將所有進程的“能執(zhí)行完”標志清0假定接受該請求,把資源分配給進程將系統(tǒng)當前所有剩余資源與”能執(zhí)行完”標志為0的進程還需資源數(shù)比較,找出一個能滿足其所有需求的進程找到了嗎？將該進程的”能執(zhí)行完”標志置為1,系統(tǒng)收回它所要求的全部資源數(shù)YN檢查所有進程的“能執(zhí)行完”標志還有” 能執(zhí)行完 ”標志為0的進程嗎？這一請求不安全,暫時不予接受

27、YN這一請求是安全的,可以分配. 在“能執(zhí)行完”標志為0的進程中重復以上兩步，直到找不到資源還需數(shù)小于系統(tǒng)剩余資源數(shù)的進程時為止。 如果存在這種進程，那么假定它已獲得需要的所有資源，并完成工作，把它的“能執(zhí)行完”標志設置成1。收回它占用的資源，更新向量A。 檢查還需資源表中是否有一個進程的行向量小于或等于向量A。如果沒有，那么系統(tǒng)就可能會死鎖，因為現(xiàn)在任何進程都無法完成了。 6.多種資源銀行家算法的執(zhí)行步驟 系統(tǒng)設兩張表：“分配資源表”，記錄已分配給各進程的資源數(shù)；“還需資源表” ，記錄各進程還需要的資源數(shù)。設3個向量：E記錄各種資源的總數(shù)，P記錄各種資源已分配數(shù)，A記錄各種資源的剩余數(shù)。 進

28、程磁帶機繪圖儀打印機CD-ROMA3011B0100C1110D1101E0000進程磁帶機繪圖儀打印機CD-ROMA1100B0112C3100D0010E2110已分配資源表還需資源表E 6 3 4 2 (資源總數(shù))P 5 3 2 2 (已分配數(shù))A 1 0 2 0 (剩余數(shù)).假定接受一個進程提出的資源請求，修改向量P和A。 .重復以上兩步，直至再也找不到行向量小于或等于向量A的進程。 檢查所有進程的 “能執(zhí)行完” 標志。若這個標志都是1，則表示都能順利地完成。因此，接受資源分配后導致的新狀態(tài)是安全的；如果仍存在“能執(zhí)行完”標志為0的進程，則說明這一請求所導致的狀態(tài)是不安全的，應暫時拒絕

29、該請求。 . 系統(tǒng)中有AG共7個進程，6個同類資源rw，當前的資源所屬關(guān)系如下：6.3.4 死鎖的檢測并恢復1.利用資源分配圖檢測死鎖rAsCDFwuGtBEv.A得到資源r，需要資源s；.B不占有資源，需要資源t；.C不占有資源，需要資源s；D得到資源u和s，需要資源t；.E得到資源t，需要資源v；F得到資源w，需要資源s；G得到資源v，需要資源u。2.利用表格檢測死鎖環(huán)路資源占用的進程進程等待的資源rAsCtBuBvAAt進程等待的資源AtBCsv 通過建立“資源分配表”和“進程等待表”，隨時檢測資源的分配是否構(gòu)成環(huán)路。假定現(xiàn)有3個進程AC，有5個同類型資源rv。 資源分配表進程等待表進程

30、等待表3.死鎖的恢復 一是刪除環(huán)中的若干進程，釋放占用的資源，使其他進程能繼續(xù)運行；二是臨時把某個資源從占用者手中剝奪，給另一個進程使用；三是周期地記錄各進執(zhí)行情況。一旦檢測到死鎖，就按記錄的文件進行回退，讓損失減到最小。 6.3.5 高級進程通信1.進程間的低級與高級通信.進程間的低級通信 信號量上的P、V操作是進程間的一種通信方式，它告訴對方緩沖區(qū)里是否可存數(shù)據(jù)，是否可取數(shù)據(jù)，是否可讀文件，是否可寫文件，等等。但通信雙方不交換信息，只是事先的一種約定。因此，用P、V操作實現(xiàn)的通信，是進程間的“低級通信”。 進程間的高級通信 為使進程間能交換數(shù)據(jù)，系統(tǒng)提供通信命令給用戶在程序中使用。用戶只要

31、準備好參數(shù)，調(diào)用這些命令就能在進程間傳遞數(shù)據(jù)，這就是進程間的“高級通信”。 2.直接通信.進程間直接通信的基本思想 發(fā)送者在自己的消息發(fā)送區(qū)里形成消息，然后申請一個消息緩沖區(qū)，把數(shù)據(jù)從消息發(fā)送區(qū)移入消息緩沖區(qū)中。通過發(fā)送命令，把這個消息緩沖區(qū)直接發(fā)送到接收者的消息隊列里。接收者從自己的消息隊列上摘下消息緩沖區(qū)，把里面的數(shù)據(jù)讀到自己的消息接收區(qū)里，然后釋放緩沖區(qū)。 提供發(fā)送消息和接收消息的系統(tǒng)調(diào)用命令，比如發(fā)送命令為Send，接收命令為Receive。 系統(tǒng)中開辟消息緩沖區(qū)，構(gòu)成是： name發(fā)送消息的進程名或標識； size發(fā)送消息的長度； text發(fā)送消息的正文內(nèi)容； nPtr下一個消息緩沖

32、區(qū)的指針。.進程間直接通信示意Send (消息發(fā)送區(qū)地址)接收進程名：B消息長度：size消息正文：text進程A的消息發(fā)送區(qū)Receive (消息接收區(qū)地址)發(fā)送進程名：A消息長度：size消息正文：text進程B的消息接收區(qū)進程A的程序進程B的程序進程B的PCBMUTEX (1)SM (0)hPtr發(fā)送進程名：A消息長度：size消息正文：textnPtr：發(fā)送進程名：A消息長度：size消息正文：textnPtr：-1消息緩沖區(qū)消息緩沖區(qū)(1)(2)(3) 在進程的PCB中，增設管理消息隊列的有關(guān)內(nèi)容，它們是： hPtr消息隊列的隊首指針（每個進程的消息隊列由其他進程發(fā)來的消息緩沖區(qū)組成，hPtr總是指向第1個消息緩沖區(qū)）； MUTEX