進程間的制約關(guān)系退出6.1進程間的制約關(guān)系6.1.1與時間有關(guān)的錯誤 在第2章中，是通過圖2-2所給出的例子，來說明在多道程序設(shè)計環(huán)境下，程序執(zhí)行時“結(jié)果的再現(xiàn)性”被打破了。這就是說，在相同的前提條件下，兩次執(zhí)行的結(jié)果有可能不相同。這是因為在多道程序設(shè)計環(huán)境下，進程程序的執(zhí)行具有并發(fā)性。

進程的“并發(fā)”，使得一個進程何時占有處理機、占有處理機時間的長短、執(zhí)行速度的快慢以及外界對進程何時產(chǎn)生作用等都帶有隨機性，使得一個進程對另一個進程的影響無法預測。在操作系統(tǒng)里，把這種由于時間因素的影響而產(chǎn)生的錯誤，稱為“與時間有關(guān)的錯誤”。下面，再來看幾個這方面的例子。

在講虛擬設(shè)備時曾涉及到輸出井等概念?，F(xiàn)在假定是這樣進行管理的：為輸出井設(shè)置一張“輸出井文件目錄表”，它由若干個目錄項組成，每個目錄項記錄一個要打印輸出的文件名以及該文件在磁盤的存放地址。為了管理該目錄表，系統(tǒng)安排兩個指針：out和in。“緩輸出程序”根據(jù)out的指點進行打印，out總是指向下一個被打印的文件；井管理寫程序根據(jù)in的指點存放要求輸出的文件目錄信息，in總是指向下一個可用的目錄項位置，如圖6-1所示。

如果現(xiàn)在進程A要求打印自己名為“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，然后繼續(xù)做其他的操作。

調(diào)度程序再次調(diào)度進程A運行，從斷點往下執(zhí)行。由于它已讀過in中的內(nèi)容是7，就把文件“games”存入輸出井文件目錄表中的第7個表目，把原來里面進程B的文件名刪去，并且把in更新為9（因為進程B已經(jīng)把in改為8了），然后繼續(xù)做其他的操作。 這樣一來，進程B要輸出的文件信息蕩然無存，它永遠也得不到任何打印輸出。另外，輸出井文件目錄表的表目8被跳過去了，它的里面沒有記錄下任何要輸出的文件信息。

再來看一個例子。編寫一個復制n個記錄的程序，它把文件F中的每一個記錄依次先讀到輸入緩沖區(qū)R，再從R拷貝到輸出緩沖區(qū)T，最后寫到文件G中。假定R和T的大小正好存放一個記錄，如圖6-2所示。 可以編寫三個子程序來完成這一工作。

GET：負責從文件F中按照順序讀出一個記錄，然后送入輸入緩沖區(qū)R。

COPY：負責把輸入緩沖區(qū)R中的記錄拷貝到輸出緩沖區(qū)T中。

PUT：負責從輸出緩沖區(qū)T中讀出一個記錄，然后依照順序?qū)懭胛募礼。

用Gi、Ci、Pi分別表示讀出、拷貝、寫入第i個記錄的操作。如果這3個程序的工作順序是：G1→C1→P1→G2→C2→P2→…→Gi→Ci→Pi→…→Gn→Cn→Pn

也就是先由GET從F讀第1個記錄到R，接著由COPY把它拷貝到T，再由PUT取出并寫到G的第1個記錄。接著，GET從F讀第2個記錄到R，接著由COPY把它拷貝到T，再由PUT取出并寫到G的第2個記錄。如此循環(huán)，直到GET從F讀第n個記錄到R，接著由COPY把它拷貝到T，再由PUT取出并寫到G的第n個記錄為止。這樣的執(zhí)行序列，絕對保證拷貝的正確性。但是工作速度慢，效率低下。

其實不難看出，在復制過程中，如果COPY已經(jīng)把R中的記錄拷貝到了T中，那么GET和PUT就可以并發(fā)執(zhí)行了。即GET從F中讀出下一個記錄送到R中的操作，與PUT從T中取出里面的內(nèi)容寫入G的操作，誰先做誰后做都沒有關(guān)系，不會影響到復制結(jié)果的正確性。由于利用了并發(fā)性，工作效率就會提高。 但是，如果不去顧及這三者之間執(zhí)行順序的這種關(guān)系，隨意讓GET、COPY和PUT去并發(fā)執(zhí)行，那么就會產(chǎn)生“與時間有關(guān)的錯誤”。

假定現(xiàn)在處于圖6-3(a)的狀態(tài)，即文件F的第1個記錄已經(jīng)順利地復制到了文件G，文件F的第2個記錄也已由GET讀到了輸入緩沖區(qū)R中。要說明的是，為了表示文件F中的第1，2兩個記錄已經(jīng)被GET順序讀出，這里就沒有將它們標示出來。下面也這樣表示。 如果現(xiàn)在不去考慮GET、COPY和PUT的執(zhí)行關(guān)系，那么它們的執(zhí)行順序可以有6種可能： （1）COPY→PUT→GET

（2）COPY→GET→PUT

（3）PUT→COPY→GET

（4）PUT→GET→COPY

（5）GET→COPY→PUT

（6）GET→PUT→COPY

比如現(xiàn)在在圖6-3(a)的基礎(chǔ)上，來看第6種可能的執(zhí)行順序。這時先執(zhí)行GET，把文件F中的第3個記錄讀入緩沖區(qū)R，致使原來R中的記錄2被刪去，由記錄3代替，如圖6-3(b)所示。然后，執(zhí)行PUT，把現(xiàn)在還在輸出緩沖區(qū)中的記錄1寫入到文件G中，成為它的第2個記錄，如圖6-3(c)所示。最后執(zhí)行COPY，把記錄3從輸入緩沖區(qū)R拷貝到輸出緩沖區(qū)T中，如圖6-3(d)所示。由于這種執(zhí)行順序沒有遵循這3個程序在執(zhí)行順序上的限制，因此導致了“與時間有關(guān)的錯誤”發(fā)生：復制過程中，把第2個記錄丟失了，第1個記錄在文件G里重復復制了兩次。

在這6種執(zhí)行順序中，只有第1和第2種執(zhí)行順序是正確的，其余的都不正確，都會導致“與時間有關(guān)的錯誤”。 下面將用兩小節(jié)，通過分析這兩個例子，得到進程間具有的兩種制約關(guān)系：互斥與同步。由于對共享資源的爭奪，導致進程之間出現(xiàn)互斥關(guān)系；由于對任務的協(xié)同工作，導致進程之間出現(xiàn)同步關(guān)系。只有很好地解決這些關(guān)系，才能避免“與時間有關(guān)的錯誤”的出現(xiàn)。6.1.2競爭資源—互斥 下面來分析第1個例子，看它為什么會導致“與時間有關(guān)的錯誤”的發(fā)生。 在這個例子中，進程A和進程B沒有任何直接的關(guān)系，各自做自己的事情。不過，當它們要求輸出時，都要訪問變量in。也就是說，in是它們的共享變量。如果在進程A使用完變量in（也就是取出in的值，把文件按它的指點存入輸出井目錄表，把in的值加1）后，進程B才去使用，那么是不會發(fā)生“與時間有關(guān)的錯誤”的。同樣地，如果在進程B使用完變量in（也就是取出in的值，把文件按它的指點存入輸出井目錄表，把in的值加1）后，進程A才去使用，那么也不會發(fā)生“與時間有關(guān)的錯誤”?？梢钥闯觯M程A和進程B誰先用in誰后用in的次序是無關(guān)緊要的。

但是，現(xiàn)在偏偏是在進程A取出變量in的值、還沒有按照其指點往目錄表中存放文件信息、沒有對in實行加1操作的情況下，進程B就去使用了變量in。這就是說，在進程A還沒有結(jié)束對變量in的使用的情況下，進程B就開始了對in的使用，從而導致了“與時間有關(guān)的錯誤”的出現(xiàn)。 很明顯，進程A和進程B誰先做誰后做都沒有關(guān)系，誰先使用變量in誰后使用變量in也都沒有關(guān)系，重要的是它們兩個不能同時使用變量in。這里，“不能同時”的含義是：在一個進程已經(jīng)開始使用變量in、但還沒有用完時，不允許另一個進程也使用變量in。即它們對變量in的使用必須保持“互斥”。

在操作系統(tǒng)中，凡是牽扯到數(shù)據(jù)、隊列、緩沖區(qū)、表格和變量等任何形式的共享資源時，都很容易出現(xiàn)類似的這種“與時間有關(guān)的錯誤”。為了避免錯誤的發(fā)生，關(guān)鍵是要找到一種途徑，來阻止多于一個進程同時使用它們。也就是說，要有一種辦法，保證對它們的使用是互斥進行的。 為了下面討論方便，在此把那些可以共享的資源（文件、隊列、緩沖區(qū)、表格、變量等）統(tǒng)稱為臨界資源或共享變量。于是，與一個共享變量（或臨界資源）交往的多個進程，為了保證它們各自運行結(jié)果的正確性，當其中的一個進程正在對該變量（或臨界資源）進行操作時，就不允許其他進程同時對它進行操作。進程間的這種制約關(guān)系被稱為“互斥”。

比如，上面的第1個例子中，進程A與進程B都要與變量in交往，因此變量in是它們的一個共享變量。進程A對in的操作與進程B對in的操作要互斥進行。 比如，進程調(diào)度程序要從就緒隊列中挑選進程投入運行，它要對就緒隊列做摘下某個進程PCB的操作；時間片用完時，時鐘中斷處理程序就要把當前運行進程的PCB插入到就緒隊列中去重新參與調(diào)度?？梢姡M程調(diào)度程序與時鐘中斷處理程序都要對系統(tǒng)中的就緒隊列進行操作，就緒隊列是它們的一個共享變量。因此，進程調(diào)度程序?qū)途w隊列所做的摘下某個進程PCB的操作，與時鐘中斷處理程序把當前運行進程的PCB插入到就緒隊列中去的操作必須互斥進行。

比如，飛機航班售票系統(tǒng)有n個售票處，每個售票處通過終端訪問系統(tǒng)的公共數(shù)據(jù)區(qū)，以便完成旅客提出的訂票請求。由于各售票處旅客訂票的時間以及要求購買的機票日期和航班都是隨機的，因此可能有若干個旅客在不同的售票處幾乎同時提出購買同一日期同一班次的要求。這樣，每一個售票處所運行的程序都要對公共數(shù)據(jù)區(qū)的這一信息進行訪問和操作，這一信息顯然是它們的共享變量。對它的訪問和操作必須互斥。6.1.3協(xié)同工作—同步 下面來分析第2個例子，看它為什么會導致“與時間有關(guān)的錯誤”的發(fā)生。 前面提及，系統(tǒng)中的進程在運行過程中，由于對資源的競爭而產(chǎn)生了相互制約的關(guān)系。具有這種關(guān)系的進程，在所完成的任務上都不以對方的工作為前提，互相沒有什么依賴，各自單獨運行都是正確的。因此，這是進程間的一種間接關(guān)系。

但是，在第2個例子中，GET、COPY、PUT三者之間呈現(xiàn)的卻是另外一種關(guān)系。拿GET和COPY來說，當GET還沒有把記錄從文件F讀到輸入緩沖區(qū)R之前，COPY不能做把輸入緩沖區(qū)R中的內(nèi)容拷貝到輸出緩沖區(qū)T中的操作。同樣地，在COPY還沒有把輸入緩沖區(qū)R中的內(nèi)容拷貝到輸出緩沖區(qū)T之前，GET不得把下一個記錄從文件F讀到輸入緩沖區(qū)R中。這就是說，只有GET先于COPY工作，COPY的工作才有意義；只有COPY取走了R中的內(nèi)容，GET進入下一步工作才有意義。COPY與PUT之間也有這種類似的關(guān)系，這是進程之間由于協(xié)同工作而產(chǎn)生的一種直接關(guān)系。 GET和COPY如何才能協(xié)調(diào)一致地工作呢，圖6-4描述了它們之間應該具有的安排。在GET讀了一個記錄到輸入緩沖區(qū)R后，就給COPY發(fā)送一個消息，告訴它R中已經(jīng)有記錄可以拷貝了，然后自己暫停下來，等待COPY發(fā)來“拷貝結(jié)束”的消息。只有接到這個消息，GET才能去做下一步的工作。對COPY而言，一直處于等待。只有在接收到GET發(fā)送來的“可以拷貝”的消息后，才能工作，將R中的記錄拷貝到輸出緩沖區(qū)T中。然后就向GET發(fā)送“拷貝結(jié)束”的消息，隨之又等待GET發(fā)來消息。6.2信號量與P、V操作 1968年，荷蘭人Dijkstra給出了一種解決并發(fā)進程間互斥與同步關(guān)系的通用方法。他定義了一種名為“信號量”的變量，并且規(guī)定在這種變量上只能做所謂的P操作和V操作。這樣，通過信號量取不同的初值以及在其上做P、V操作，就能夠?qū)崿F(xiàn)進程間的互斥、同步，甚至用來管理資源的分配。6.2.1信號量與P、V操作的定義 所謂“信號量”，是一個具有非負初值的整型變量，并且有一個隊列與它關(guān)聯(lián)。因此，定義一個信號量S時，要給出它的初值Vs，給出與它相關(guān)的隊列指針Vq。 在一個信號量S上，只能做規(guī)定的兩種操作：P操作，記為P（S）；和V操作，記為V（S）。P、V操作的具體定義如下。

（1）信號量S上的P操作定義。 當一個進程調(diào)用P（S）時，應該順序做下面不可分割的兩個動作。

Vs=Vs-1，即把當前信號量S的取值減1。

若Vs>=0，則調(diào)用進程繼續(xù)運行；若Vs<0，則調(diào)用進程由運行狀態(tài)變?yōu)樽枞麪顟B(tài)，到與該信號量有關(guān)的隊列Vq上排隊等待，直到其他進程在S上執(zhí)行V操作將其釋放為止。

（2）信號量S上的V操作定義。 當一個進程調(diào)用V（S）時，應該順序做下面不可分割的兩個動作。

Vs=Vs+1，即把當前信號量S的取值加1。

若Vs>0，則調(diào)用進程繼續(xù)運行；若Vs<=0，則先從與該信號量有關(guān)的隊列Vq上摘下一個等待進程，讓它從阻塞狀態(tài)變?yōu)榫途w狀態(tài)，到就緒隊列里排隊，然后調(diào)用進程繼續(xù)運行。

關(guān)于信號量及其P、V操作，有如下幾點說明。 （1）設(shè)置的信號量初值，一定是一個非負的整數(shù)。比如，它可以是0，可以是1，也可以是8，等等。但不能是-1、-3等。不過，由于P操作會在信號量的當前值上進行減1操作，而V操作會在信號量的當前值上進行加1操作，因此運行過程中，信號量的取值就不再受“非負”所限了。 （2）定義在信號量上的P操作和V操作，都由兩個不可分割的動作組成，也就是說，只要進入了P（S）或V（S），這兩個動作就必須順序地做完，中間不能被打斷。所以，信號量上的P、V操作，實際都是原語，如前面在原語時所說的，為了保證執(zhí)行時的不可分割性，常采用關(guān)、開中斷的辦法來具體實現(xiàn)信號量上的P、V操作。

（3）從P（S）的定義可以看出，調(diào)用它的進程有兩個出路。如果對信號量當前值減1后，信號量值大于等于0，則該進程繼續(xù)運行下去；否則它就被阻塞，直到有別的進程通過做V（S）來喚醒它。但是從V（S）的定義可以看出，調(diào)用它的進程的狀態(tài)不會改變。無論對信號量當前值加1后的結(jié)果如何，調(diào)用它的進程最終都是繼續(xù)運行下去。 （4）注意，如果一個進程在做P操作后被阻塞，到關(guān)于信號量的隊列上去排隊等待，其含義是將進程的PCB到此隊列上排隊。6.2.2用P、V操作實現(xiàn)互斥 假定把進程A程序中的臨界區(qū)記為CSa，假定把進程B程序中的臨界區(qū)記為CSb，如圖6-5(a)所示。所謂“CSa和CSb互斥地執(zhí)行”，含義是：如果進程A已進入了CSa，那么進程B就只能在其CSb的進入點處等待，不能進入，只有等到進程A退出了CSa，進程B才能進入CSb。同樣地，如果進程B已進入了CSb，那么進程A就只能在其CSa的進入點處等待，不能進入。只有等到進程B退出了CSb，進程A才能進入CSa。 為了保證做到這一點，設(shè)置一個初值為1的信號量S，在進程A和B的進入點處安排關(guān)于信號量S的P操作，在進程A和B的退出點處安排關(guān)于信號量S的V操作。這樣，就能夠確保CSa和CSb互斥地執(zhí)行。如圖6-5(b)所示。

現(xiàn)在來分析一下為什么這樣的安排就能夠保證CSa和CSb的互斥執(zhí)行。在圖6-5(b)的情形下，不失其一般性，假定進程A先于進程B做P（S）。由于Vs初始時取值為1，做了P（S）后，Vs變?yōu)?。根據(jù)信號量上P操作的定義，在實施減1后如果Vs>=0，則調(diào)用進程繼續(xù)運行，因此進程A進入了它的臨界區(qū)。如果這時進程A的時間片到，則調(diào)度到進程B運行。當它調(diào)用信號量S的P操作時，由于現(xiàn)在的Vs=0，于是減1后Vs=-1<0。根據(jù)信號量上P操作的定義，在實施減1后如果Vs<0，那么調(diào)用進程由運行狀態(tài)變?yōu)樽枞麪顟B(tài)，并到與該信號量有關(guān)的隊列Vq上排隊等待，直到其他進程在S上執(zhí)行V操作將其釋放為止。因此進程B被阻塞（不能進入它的臨界區(qū)CSb），到關(guān)于信號量S的隊列Vq上去排隊，等候別的進程釋放它?？梢姡@樣安排P、V操作，可以保證只有一個進程進入它的臨界區(qū)。

這時進程A在它的臨界區(qū)里，進程B被阻擋在它的臨界區(qū)外等待進入。下面介紹進程B要等到什么時候才能有可能進入自己的臨界區(qū)。如果又一次調(diào)度到進程A運行，則它從臨界區(qū)里的斷點處往下做，退出臨界區(qū)時做S（V）。由于現(xiàn)在的Vs=-1，于是加1后Vs=0。根據(jù)信號量上V操作的定義，在實施加1后如果Vs<=0，則先從與該信號量有關(guān)的隊列Vq上摘下一個等待進程，讓它從阻塞狀態(tài)變?yōu)榫途w狀態(tài)，到就緒隊列中排隊，然后調(diào)用進程繼續(xù)運行?，F(xiàn)在，在隊列Vq上等待的正是進程B。于是將進程B的PCB從隊列上摘下，把狀態(tài)由阻塞改變成為就緒，讓它重新參與調(diào)度。而進程A在做完這些事情后，繼續(xù)運行下去。這里要注意，上次進程B已經(jīng)做了P操作，只是沒有能進入臨界區(qū)罷了，因此再調(diào)度到它運行時，就直接進入臨界區(qū)了。

通過這一分析可以看到，在這種安排下，哪個進程先對信號量S做P操作，就會使S的值由1變成為0，且它就獲得了進入臨界區(qū)的權(quán)利。當有一個進程在臨界區(qū)內(nèi)時，S的值肯定是0。因此，此時另一個進程想通過做P操作進入自己的臨界區(qū)時，就會因為使S的值由0變?yōu)?1而受到阻擋。只有等到在臨界區(qū)內(nèi)的那個進程退出臨界區(qū)、對S做V操作時，使S的值由-1變?yōu)?，才會解除阻擋，以此來保證進程間的互斥。

為了保證做到這一點，設(shè)置一個初值為0的信號量S，在進程A的X點處（即同步點），安排一個關(guān)于信號量S的P操作，在進程B的Y點處安排關(guān)于信號量S的V操作。這樣，就能夠確保進程A在X點處與進程B取得同步了，如圖6-7(b)所示。

現(xiàn)在來分析一下，為什么這樣的安排就能夠保證進程A在X點與進程B取得同步。首先假定在進程B未到達Y點之前，進程A先于進程B到達了X點。由于Vs初始時取值為0，做了P（S）后，Vs變?yōu)?1。根據(jù)信號量上P操作的定義，在實施減1后如果Vs<0，則調(diào)用進程由運行狀態(tài)變?yōu)樽枞麪顟B(tài)，到與該信號量有關(guān)的隊列Vq上排隊等待，直到其他進程在S上執(zhí)行V操作將其釋放為止。因此進程A被阻塞，到關(guān)于信號量S的隊列Vq上去排隊，等候別的進程釋放它。

這時，調(diào)度程序調(diào)度到進程B運行。當它準備好了信息后，就在信號量S上做V操作。由于現(xiàn)在的Vs=-1，加1后是Vs=0，因此，根據(jù)信號量上V操作的定義，在實施加1后如果Vs<=0，則先從與該信號量有關(guān)的隊列Vq上摘下一個等待進程，讓它從阻塞狀態(tài)變?yōu)榫途w狀態(tài)，到就緒隊列中排隊，然后調(diào)用進程繼續(xù)運行?，F(xiàn)在，在隊列Vq上等待的正是進程A。于是將進程A的PCB從隊列上摘下，把狀態(tài)由阻塞改變成為就緒，讓它重新參與調(diào)度?？梢?，在進程A中這樣安排P操作，在進程B中這樣安排V操作，可以保證在進程B還沒有為進程A準備好所需要的信息時，進程A就在X點處等待，一直等到進程B準備好信息，解除進程A的等待。

再來看一下，如果在進程A到達X點之前（也就是在進程A還沒有做P操作之前），進程B已經(jīng)通過了Y點（即做了V操作），那么由于Vs的初值是0，V操作后Vs的值就變成為1。這樣，當進程A到達X點對信號量S做P操作時，是在Vs當前值1上做減1的操作，于是Vs變?yōu)?。根據(jù)信號量上P操作的定義，在實施減1后如果Vs>=0，則調(diào)用進程繼續(xù)運行。即現(xiàn)在進程A沒有受到阻擋，順利地通過了X點。

通過這一分析可以看到，在這種安排下，如果準備同步條件的進程把信息準備好了，先在信號量上做了V操作（這就是告訴對方，你所需要的信息已經(jīng)有了），那么求得同步的進程就不會受到任何阻擋地通過同步點。但如果準備同步條件的進程還沒有把信息準備好，那么要取得同步的進程在通過同步點時，就會受到阻擋，停下來等待對方提供信息。6.2.4用P、V操作實現(xiàn)資源分配 從前面可知，信號量初始時取非負整數(shù)值，P操作在信號量值的基礎(chǔ)上實行減1，V操作在信號量值的基礎(chǔ)上實行加1。因此，如果把信號量的初始值，比如n，理解為是系統(tǒng)中某種資源的數(shù)目，那么，在它的上面做P操作，即是申請一個資源；在它的上面做V操作，即是釋放一個用完的資源。與該信號量有關(guān)的隊列，是資源等待隊列。

某個進程在信號量S上做一次P操作后，如果Vs>=0，表示該進程分到了一個資源單位（注意，P操作完畢后Vs>=0，表示P操作前Vs>=1，即至少還有一個資源可以分配），現(xiàn)在Vs的值是這種資源的剩余數(shù)；如果Vs<0（P操作完畢后Vs<0，表示P操作前，Vs<=0），表示現(xiàn)在已經(jīng)沒有資源可以分配，申請資源的進程只能被阻塞，到資源等待隊列Vq上去排隊等待。在Vs<0的情況下，Vs的絕對值恰是提出資源請求、但沒有分配到資源的進程個數(shù)。

某個進程在信號量S上做一次V操作后，如果Vs<=0，表示申請資源的等待隊列上有進程在等待該資源（注意，V操作完畢后Vs<=0，表示V操作前Vs<=-1，即至少有一個進程在隊列上等待使用該資源），故將該隊列上的一個進程摘下，讓它到就緒隊列中排隊；如果V操作完畢后Vs>0，表示V操作前Vs>=0，即資源等待隊列上沒有進程在等待，只是收回了一個資源。

在真正用P、V操作實現(xiàn)資源分配時，把所設(shè)置的信號量初值設(shè)為資源的個數(shù)n。在進行資源分配的進程中對信號量做P操作。每做一次P操作，就分配一個資源。在進行資源回收的進程里對信號量做V操作。每做一次V操作，就收回一個資源。由于資源初啟時共有n個，因此如果對資源進行連續(xù)n次申請，都能夠立即得到滿足。但第n+1個提出申請的進程就不得不在資源等待隊列中等待了。6.2.5互斥/同步的樣例分析 利用信號量及其P、V操作解決實際問題時，必須從問題中提煉出各類同步問題，即哪個屬于互斥，哪個屬于資源分配。只有這樣，才能設(shè)置取不同初值的信號量，然后按照它們使用的固定模式，在程序里適當?shù)奈恢冒才臥、V操作。在這一小節(jié)，將通過幾個更復雜的例子，來進一步說明P、V操作的應用。6.3死鎖、高級進程通信6.3.1死鎖與產(chǎn)生死鎖的必要條件 在計算機系統(tǒng)中有很多獨享資源，在任何時刻它們只能被一個進程使用，比如打印機、磁帶機和文件等。另一方面，系統(tǒng)中的資源數(shù)是有限的，請求使用資源的進程數(shù)卻可能很多，從而產(chǎn)生“供-需”矛盾。如果分配不當，或諸進程推進速度巧合，就會使系統(tǒng)中的某些進程陷入相互等待無法繼續(xù)工作的地步。

常用方框代表資源，圓圈代表進程，如果畫一條由資源到進程的有向邊，則表示把該資源分配給了這個進程；如果畫一條由進程到資源的有向邊，則表示該進程申請這個資源，這樣的圖就是所謂的“資源分配圖”。圖6-14(a)表示將資源R分配給了進程A使用，即進程A現(xiàn)在占用資源R；圖6-14(b)表示進程B要申請使用資源S。在圖6-14(c)中，表示現(xiàn)在已把資源T分配給了進程D，進程D申請使用資源U，資源U已經(jīng)分配給了進程C，進程C申請使用資源T。這表明在資源T、U與進程C、D之間出現(xiàn)了循環(huán)等待的情形：進程C占用著資源U，想要資源T；資源T已被進程D占用，它卻想要被進程C占用的資源U，這樣一來，進程C、D都無法運行下去。6.3.2死鎖的預防 所謂“死鎖的預防”，是指破壞產(chǎn)生死鎖四個必要條件中的一條或幾條，以使系統(tǒng)不會產(chǎn)生死鎖。

（1）破壞“互斥條件”。系統(tǒng)中互斥條件的產(chǎn)生，是由于資源本身的“獨享”特征引起的。比如，若允許兩個進程同時使用打印機，那么就會出現(xiàn)混亂，兩個進程的打印結(jié)果會交織在一起，讓用戶不能接受，因此，對于打印機等獨享資源，就必須維護“互斥條件”。設(shè)備管理中提及的SPOOL技術(shù)就是一種破壞互斥條件的方法。采用了SPOOL技術(shù)，使得原來獨享的設(shè)備具有了共享的性能，從而破壞了它的“互斥條件”。但SPOOL技術(shù)并不是對所有的獨享資源都適用，因此，在死鎖預防里，主要是破壞其他幾個必要條件，而不去涉及“互斥條件”。

（2）破壞“部分分配（占用并等待）條件”。只要系統(tǒng)對進程實行一次性分配的方案，就可以破壞部分分配條件。也就是說，一個進程總是合盤提出總的資源需求，系統(tǒng)要么分配給它所需要的全部資源，要么一個也不給它。于是，如果一個進程提出資源請求時，它所需要的資源中有幾個正在被別的進程使用，那么它得不到任何資源，只有被阻塞等待。既然系統(tǒng)中每個進程要得就得到它所需要的全部資源，那么系統(tǒng)中的每個進程都肯定能夠運行到結(jié)束。死鎖在這種系統(tǒng)中絕對不會出現(xiàn)。

（3）破壞“非剝奪條件”。資源使用的“非剝奪”性，就是已經(jīng)分配給進程的資源，即使暫時不用，別的進程也不能強行奪取。要破壞它，唯一的辦法就是允許別的進程從占用進程手中強搶所占用的資源。這種辦法顯然有些“粗野”，可能會造成混亂。 （4）破壞“循環(huán)等待條件”。為了破壞這個條件，常采用的辦法是將系統(tǒng)中的所有資源進行統(tǒng)一編號，進程按編號的順序，由小到大提出對資源使用的申請。這樣做就能保證系統(tǒng)不出現(xiàn)死鎖。

比如圖6-17(a)中對系統(tǒng)中的5種資源進行了統(tǒng)一編號，那么進程可以先申請打印機，再申請磁帶機，但不能先申請磁帶機，再申請打印機，因為那樣做申請順序就不對了。這樣做系統(tǒng)就不會出現(xiàn)死鎖的原因如圖6-17(b)所示，假定把不同編號的資源i和j分配給了進程A和B，那么如果i>j，A就不允許再申請資源j；如果i<j，B就不允許再申請資源i。于是就形成不了如圖6-17(c)所示的循環(huán)等待的環(huán)路，從而破壞了“循環(huán)等待”的條件。6.3.3死鎖的避免 為了實行銀行家算法，對系統(tǒng)中的每個進程提出如下要求： （1）必須預先說明自己對資源的最大需求量。 （2）只能一次一個地申請所需要的資源。 （3）如果已經(jīng)獲得了資源的最大需求量，那么應該在有限的時間內(nèi)使用完畢，并歸還給系統(tǒng)。 為了實行銀行家算法，系統(tǒng)的承諾如下：

（1）如果一個進程對資源的最大需求量沒有超過該資源的總量，則必須接納這個進程，不得拒絕它。 （2）在接到一個進程對資源的請求時，有權(quán)根據(jù)當前資源的使用情況暫時加以拒絕（即阻塞該進程），但保證在有限的時間內(nèi)讓它得到所需要的資源。 銀行家算法有單種資源和多種資源之分?！皢畏N資源”的銀行家算法，只針對一種資源的情況；“多種資源”的銀行家算法，針對多種資源的情況，下面分別進行介紹。 單種資源銀行家算法的基本思想（如圖6-18所示）如下： （1）在安全狀態(tài)下，系統(tǒng)接到一個進程的資源請求后，先假定接受這一請求，把需要的資源分配給這個進程。

（2）在這一假設(shè)下，檢查每一個進程對資源的的還需要數(shù)，看能否找到一個進程，其還需數(shù)目小于系統(tǒng)剩余資源數(shù)。如果找不到，那么系統(tǒng)就有可能死鎖，因為任何進程都無法運行結(jié)束。 （3）如果找到了，就假設(shè)它獲得了最大資源數(shù)，并能運行結(jié)束，把它的“能執(zhí)行完”標志設(shè)置為1。這樣就能假定收回它使用的所有資源，使系統(tǒng)剩余資源數(shù)增加。 （4）在“能執(zhí)行完”標志為0的進程中重復以上兩步，直到找不到資源還需數(shù)小于系統(tǒng)剩余資源數(shù)的進程時為止。 （5）如果所有進程的“能執(zhí)行完”均為1，表示接受這次請求是安全的；否則暫時不能接受這次的資源請求。

比如，系統(tǒng)中有一種資源總量為10。現(xiàn)在有3個進程，A的最大需求量為9，B的最大需求量為4，C的最大需求量為7，如圖6-19(a)所示。它們每個對資源的需求量都不超過10，但總需求量大于10。通過若干次資源請求后，資源的使用情況如圖6-19(b)所示。 現(xiàn)在進程B提出一個資源請求，系統(tǒng)應該接受這一請求嗎？用銀行家算法來測試一下。

假定接受它，這樣進程B已有資源3，系統(tǒng)的資源剩余數(shù)為2，如圖6-19(c)所示。這時，進程A還需資源6個，進程B還需資源1個，進程C還需資源5個。用當前系統(tǒng)剩余資源數(shù)2與6、1、5比較，可知現(xiàn)在系統(tǒng)能夠滿足進程B的所有需求。滿足它，資源的使用情況如圖6-19(d)所示。由于進程B已經(jīng)獲得它所需要的資源最大量，它肯定能夠完成。假定它已完成，收回它使用的資源，把它的“能執(zhí)行完”標志設(shè)置為1。這時，系統(tǒng)的資源剩余數(shù)變?yōu)?，如圖6-19(e)所示。再用當前系統(tǒng)剩余資源數(shù)5與進程A、C的還需資源數(shù)6、5比較，可知現(xiàn)在系統(tǒng)能夠滿足進程C的所有需求。

滿足它，資源的使用情況如圖6-19(f)所示。這樣，進程C也能最終完成，收回它使用的資源，把它的“能執(zhí)行完”標志設(shè)置為1。這時，系統(tǒng)的資源剩余數(shù)變?yōu)?，如圖6-19(g)所示。再用當前系統(tǒng)剩余資源數(shù)7與進程A的還需資源數(shù)6比較，可知現(xiàn)在系統(tǒng)能夠滿足進程A的所有需求。于是進程A也能夠最終完成。收回它使用的資源，把它的“能執(zhí)行完”標志設(shè)置為1。至此，A、B、C的“能執(zhí)行完”標志都被設(shè)置為1?？梢?，如果在圖6-19(b)時接受進程B的一個資源請求，它所導致的圖6-19(c)的狀態(tài)是安全的，系統(tǒng)可以放心地去做這一次資源分配。這就是用銀行家算法進行模擬預測的全過程。

在圖6-19(b)的情況下，進程A提出了一個資源請求，系統(tǒng)是否應該接受它，仍用銀行家算法來進行測試。 假定接受它，這樣進程A已有資源4，系統(tǒng)的資源剩余數(shù)為2，如圖6-20(b)所示。這時，進程A還需資源5個，進程B還需資源2個，進程C還需資源5個。用當前系統(tǒng)剩余資源數(shù)2與5、2、5比較，可知現(xiàn)在系統(tǒng)能夠滿足進程B的所有需求。滿足它，資源的使用情況如圖6-20(c)所示。由于進程B已經(jīng)獲得它所需要的資源最大量，它肯定能夠完成。假定它已完成，收回它使用的資源，把它的“能執(zhí)行完”標志設(shè)置為1。這時，系統(tǒng)的資源剩余數(shù)變?yōu)?，如圖6-20(d)所示。再用當前系統(tǒng)剩余資源數(shù)4，與進程A、C的還需資源數(shù)5、5比較。

此時，它既滿足不了進程A的還需資源量，也滿足不了進程C的還需資源量，因此，進程A和C都無法最終完成?？梢?，這時不能接受進程A的資源請求，只能暫時將進程A阻塞。這就是說，如果接受進程A的資源請求的話，所導致的圖6-20(b)的狀態(tài)是不安全的。 從安全的狀態(tài)出發(fā)，系統(tǒng)能夠保證所有進程都能完成；從不安全的狀態(tài)出發(fā)，系統(tǒng)就不存在這種保證，這就是安全狀態(tài)和不安全狀態(tài)的區(qū)別。但是，不要認為從不安全狀態(tài)出發(fā)，就一定會導致死鎖，只能說它是不安全的，可能會導致死鎖。這是因為運行中，系統(tǒng)千變?nèi)f化，銀行家算法都是從進程對資源的最大需求量考慮問題的。如果在運行中，某個進程對資源的使用沒有真正達到最大需求，那么情況就不會是這樣了。

銀行家算法可以推廣用于處理多種資源。此時，系統(tǒng)要為算法設(shè)置兩張表，一張記錄已分配給各進程的資源數(shù)，一張記錄各進程還需要的資源數(shù)。另外還要有3個向量：向量E記錄各種資源的總數(shù)，向量P記錄各種資源已分配數(shù)，向量A記錄各種資源的剩余數(shù)。比如，現(xiàn)在有A~E共5個進程，系統(tǒng)中有磁帶機6臺，繪圖儀3臺，打印機4臺，CD-ROM兩臺。當前的已分配資源表如圖6-21(a)所示，還需資源表如圖6-21(b)所示，3個向量如圖6-21(c)所示。

圖6-21給出的狀態(tài)是安全的。如果這時進程B提出申請一臺打印機，那么此時的系統(tǒng)狀態(tài)將從圖6-21變?yōu)槿鐖D6-22(a)所示。它是安全的，因為這時系統(tǒng)的資源剩余數(shù)能滿足進程D的全部需要，于是進程D可以完成；收回D的資源后，向量A成為[2111]。它可以滿足進程A或進程E，最后所有進程都可以順利結(jié)束。 在圖6-22(a)所示的安全狀態(tài)下，如果進程E提出對打印機的請求時，系統(tǒng)能接受這一請求嗎？ 假定接受，那么系統(tǒng)的狀態(tài)就成為圖6-22(b)所示，此時系統(tǒng)資源剩余數(shù)為向量A[1000]。這個剩余數(shù)無法滿足任何進程還需的資源數(shù)，因此，這個請求暫時不能接受，即圖6-22(b)所表示的狀態(tài)是不安全的。6.3.4死鎖的檢測并恢復 死鎖的檢測也可以分為單種資源和多種資源兩種。這里只討論單種資源的死鎖檢測。 可以通過畫當前的資源分配圖，來檢測在某些進程間是否已經(jīng)構(gòu)成了死鎖。比如系統(tǒng)中有A~G共7個進程，有6個同類型的資源r~w。當前的資源所屬關(guān)系為：

進程A已得到資源r，需要資源s；

進程B不占有任何資源，需要資源t；

進程C不占有任何資源，需要資源s；

進程D已得到資源u和s，需要資源t；

進程E已得到資源t，需要資源v；

進程F已得到資源w，需要資源s；

進程G已得到資源v，需要資源u。 此時的資源分配圖如圖6-23(a)所示?？梢钥闯?，在進程D、E、G之間存在一個循環(huán)等待的環(huán)路，見圖6-23(b)，它們處于死鎖狀態(tài)。 也可以通過建立資源分配表和進程等待表，來隨時檢測系統(tǒng)對資源的分配是否構(gòu)成環(huán)路。假定系統(tǒng)有3個進程A~C，有同類型的資源5個r~v，在某一時刻，資源的分配情況如圖6-24(a)所示。由于這些分配都能夠立即滿足，因此不會出現(xiàn)進程等待資源的情形。

如果這時進程A提出申請資源t。由于資源t已經(jīng)分配出去了，若讓進程A等待，會造成環(huán)路而形成死鎖嗎？為此，系統(tǒng)通過t去查資源分配表，看誰占用了資源t。從資源分配表可知資源t分配給了進程B，而進程B現(xiàn)在并不等待任何資源，因此，讓進程A等待資源t不會構(gòu)成環(huán)路。于是把它填入進程等待表中，如圖6-24(b)所示。隨后，進程B提出對資源s的請求。仍然用相同的方法，反復查看資源分配表和進程等待表，結(jié)果是沒有出現(xiàn)循環(huán)等待，因此又把進程B等待資源s的情況記錄在進程等待表中，如圖6-24(c)所示。

現(xiàn)在進程C提出申請資源v。從資源分配表可知，資源v已經(jīng)分配給了進程A；查進程等待表可知，進程A在等待資源t；從資源分配表可知，資源t已經(jīng)分配給了進程B；查進程等待表可知，進程B在等待資源s；從資源分配表可知，資源s已經(jīng)分配給了進程C。至此，形成了一個環(huán)路，出現(xiàn)死鎖，并且這個死鎖涉及到進程A、B、C，以及資源s、t、v。如圖6-24(d)所示。

檢測出死鎖，就要將其消除，使系統(tǒng)得以恢復。最為簡單的解決辦法是刪除環(huán)中的一個或若干個進程，釋放它們占用的資源，使其他進程能夠繼續(xù)運行下去。第2種可取的方法是臨時把某個資源從它的占用者手中剝奪下來，給另一個進程使用。再有一種較為復雜的方法是周期性地把各個進程的執(zhí)行情況記錄在案，一旦檢測到死鎖發(fā)生，就可以按照這些記錄的文件進行回退，讓損失減到最小。6.3.5高級進程通信 在信號量上的P、V操作，可以看作是進程間的一種通信方式，它能告訴通信的對方，緩沖區(qū)里是否可存數(shù)據(jù)，是否可取數(shù)據(jù)，是否可以讀文件，是否可以對文件進行寫操作，等等。不過，這種通信并不在進程間真正交換信息，而只是雙方事先的一種約定。如果把這種通信方式直接提供給用戶使用，不僅無法傳遞數(shù)據(jù)，不好理解，而且容易出錯。因此，用P、V操作實現(xiàn)的通信，稱之為是進程間的一種低級通信。

為了使進程之間能夠真正交換數(shù)據(jù)，操作系統(tǒng)備有高級通信命令，提供給用戶在程序一級使用。用戶只要準備好參數(shù)，利用這些命令就能夠在進程之間傳遞數(shù)據(jù)，無須去考慮同步、互斥這樣一些讓人頭疼的問題。 高級進程通信分成直接通信和間接通信兩種方式。

1．直接通信 直接通信的基本思想是消息發(fā)送者在自己的消息發(fā)送區(qū)里形成消息，然后申請一個消息緩沖區(qū)，把數(shù)據(jù)從消息發(fā)送區(qū)移入消息緩沖區(qū)中。然后通過發(fā)送命令，把這個消息緩沖區(qū)直接發(fā)送到消息接收者的消息隊列里。接收者從自己的消息隊列上摘下消息緩沖區(qū)，把里面的數(shù)據(jù)讀到自己的消息接收區(qū)里，然后釋放緩沖區(qū)。

為