【正文】 （+）==25%（2）采用以5個邏輯記錄為一組的成組技術進行存放，表示存放5個邏輯記錄后，有一個記錄間隙。5個邏輯記錄占用的磁帶長度是： 5=1（英寸）。所以，這時磁帶存儲空間的利用率是： 1/（1+）==%（3）若希望磁帶存儲空間的利用率大于50%，假定應該x個邏輯記錄為一組。這就是說，存放x個邏輯記錄后，有一個記錄間隙。x個邏輯記錄占用的磁帶長度是：x（英寸）；。所以，磁帶存儲空間的利用率是： x/（x+）=解這個一元一次方程式，x=3。也就是說，當把3個以上的邏輯記錄組成一組時，磁帶存儲空間的利用率將大于50%。3．假定有一個名為MYFILE的文件，共有10個邏輯記錄，每個邏輯記錄長為250個字節(jié)。磁盤塊尺寸為512字節(jié)，磁盤地址需要2個字節(jié)表示。把MYFILE采用鏈接結構存儲在磁盤上。（1）畫出該文件在磁盤上的鏈接結構圖（磁盤塊號自定）。（2）現(xiàn)在用戶要讀文件上包含第1425個字符的邏輯記錄。給出完成這一請求的主要工作步驟。解：（1）由于每個邏輯記錄長為250個字節(jié)，磁盤塊尺寸為512字節(jié)。所以，每個磁盤塊里可以存放兩個邏輯記錄，余下的字節(jié)用于存放指針，文件總共需要5塊。假定系統(tǒng)分配給該文件的磁盤塊號是：2354。于是，該文件在磁盤上的鏈接結構圖如圖51所示。圖51 計算題3的圖示（2）首先要知道包含第1425字節(jié)的邏輯記錄應該放在鏈接結構的第幾塊。因為一個邏輯記錄是250個字節(jié)，2個邏輯記錄放在一個磁盤塊里。所以 1425/（2502）=2（“/”表示整除運算）即包含第1425字節(jié)的邏輯記錄應該放在鏈接結構的第3塊（注意，由于是用整除，所以第1塊應該是0）。其次，文件系統(tǒng)沿著指針，把第3塊（也就是塊號為56的塊）讀入內(nèi)存緩沖區(qū)中。最后，由 1425%（2502）=425 （“%”表示求余運算）且 25014252502所以把緩沖區(qū)里的第2個記錄讀到用戶指定的內(nèi)存區(qū)里。第6章習題解答一、填空1．信號量的物理意義是當信號量值大于零時表示 可分配資源的個數(shù) ；當信號量值小于零時，其絕對值為 等待使用該資源的進程的個數(shù) 。2．所謂臨界區(qū)是指進程程序中 需要互斥執(zhí)行的程序段 。3．用P、V操作管理臨界區(qū)時，一個進程在進入臨界區(qū)前應對信號量執(zhí)行 P 操作，退出臨界區(qū)時應對信號量執(zhí)行 V 操作。4．有m個進程共享一個臨界資源。若使用信號量機制實現(xiàn)對臨界資源的互斥訪問，則該信號量取值最大為 1 ，最小為 ?（m?1）。注意，無論有多少個進程，只要它們需要互斥訪問同一個臨界資源，那么管理該臨界資源的信號量初值就是1。當有一個進程進入臨界區(qū)時，信號量的值就變?yōu)?。隨后再想進入的進程只能等待。最多的情況是讓一個進程進入后，其余（m?1）個進程都在等待進入。于是這時信號量取到最小值：?（m?1）。5．對信號量S的P操作原語中，使進程進入相應信號量隊列等待的條件是Vs0 。6．死鎖是指系統(tǒng)中多個 進程 無休止地等待永遠不會發(fā)生的事件出現(xiàn)。7．產(chǎn)生死鎖的4個必要條件是互斥、非剝奪、部分分配和 循環(huán)等待 。8．在銀行家算法中，如果一個進程對資源提出的請求將會導致系統(tǒng)從 安全 的狀態(tài)進入到 不安全 的狀態(tài)時，就暫時拒絕這一請求。9．信箱在邏輯上被分為 信箱頭 和 信箱體 兩部分。10．在操作系統(tǒng)中進程間的通信可以分為 低級 通信與 高級 通信兩種。二、選擇1．P、V操作是 A 。A．兩條低級進程通信原語 B．兩條高級進程通信原語C．兩條系統(tǒng)調(diào)用命令 D．兩條特權指令2．進程的并發(fā)執(zhí)行是指若干個進程 B 。A．共享系統(tǒng)資源 B．在執(zhí)行的時間上是重疊的C．順序執(zhí)行 D．相互制約3．若信號量S初值為2，當前值為?1，則表示有 B 個進程在與S相關的隊列上等待。A．0 B．1 C．2 D．34．用P、V操作管理相關進程的臨界區(qū)時，信號量的初值應定義為 C 。A．?1 B．0 C．1 D．隨意5．用V操作喚醒一個等待進程時，被喚醒進程的狀態(tài)變?yōu)?B 。A．等待 B．就緒 C．運行 D．完成6．若兩個并發(fā)進程相關臨界區(qū)的互斥信號量MUTEX現(xiàn)在取值為0，則正確的描述應該是 B 。A．沒有進程進入臨界區(qū)B．有一個進程進入臨界區(qū)C．有一個進程進入臨界區(qū)，另一個在等待進入臨界區(qū)D．不定7．在系統(tǒng)中采用按序分配資源的策略，將破壞產(chǎn)生死鎖的 D 條件。A．互斥 B．占有并等待 C．不可搶奪 D．循環(huán)等待8．某系統(tǒng)中有3個并發(fā)進程，都需要4個同類資源。試問該系統(tǒng)不會產(chǎn)生死鎖的最少資源總數(shù)應該是 B 。A．9 B．10 C．11 D．129．銀行家算法是一種 A 算法。A．死鎖避免 B．死鎖防止 C．死鎖檢測 D．死鎖解除10．信箱通信是進程間的一種 B 通信方式。A．直接 B．間接 C．低級 D．信號量三、問答1．試說出圖61（即教材中第2章的圖22）所給出的監(jiān)視程序A和計數(shù)程序B之間體現(xiàn)出一種什么關系，是“互斥”還是“同步”？為什么？圖61 對兩個程序的描述答：圖61（即教材中第2章的圖22）所給出的監(jiān)視程序A和計數(shù)程序B之間體現(xiàn)出的是一種互斥關系，因為在監(jiān)視程序A里，要對共享變量COUNT進行操作： COUNT=COUNT+1。在計數(shù)程序B里要對共享變量COUNT進行操作： 打印COUNT的值。 COUNT=0。這兩段程序是不能交叉進行的，不然就會出現(xiàn)與時間有關的錯誤。2．模仿教材中的圖64，畫出COPY和PUT之間的直接依賴關系。然后把兩個圖匯集在一起，體會它們?nèi)咧g正確的同步關系。再模仿教材中的圖68，能用信號量及P、V操作來正確處理GET、COPY和PUT三者之間的協(xié)同工作關系嗎？答：圖62給出了GET、COPY和PUT三者間正確的同步關系：GET在向COPY發(fā)“可以拷貝”的消息后，要等待COPY發(fā)來“拷貝結束”的消息。因為這個消息意味著輸入緩沖區(qū)R已經(jīng)被COPY騰空，GET可以再次向里面存放從文件F里取出的記錄了；COPY在等到GET發(fā)來的“可以拷貝”的消息后，才能夠把輸入緩沖區(qū)R里的記錄拷貝到輸出緩沖區(qū)T中。完成這個動作后，表示輸入緩沖區(qū)R已經(jīng)被COPY騰空，因此應該立即向GET發(fā)消息，告訴它輸入緩沖區(qū)R又可以使用了。隨后，向PUT發(fā)送“可以打印”的消息，等待PUT發(fā)來“打印結束”的消息；PUT在等到COPY發(fā)來“可以打印”的消息后，才能夠從輸出緩沖區(qū)T里取出記錄打印。打印完畢后，向COPY發(fā)送“打印完畢”的消息。這個消息意味著輸出緩沖區(qū)T已經(jīng)被PUT騰空，COPY又可以再次去等待GET發(fā)送的“可以拷貝”的消息，從輸入緩沖區(qū)R里取出記錄存入輸出緩沖區(qū)T了。圖62 GET、COPY和PUT三者間的工作關系于是，GET、COPY和PUT三者間有4個同步問題：在GET的標號為3的地方是一個同步點；在COPY的標號為1和5的地方是兩個同步點；在PUT的標號為1的地方是一個同步點。因此，共要設置4個同步信號量：S1——控制COPY與GET取得同步，初值=0；S2——控制GET與COPY取得同步，初值=0；S3——控制PUT與COPY取得同步，初值=0；S4——控制COPY與PUT取得同步，初值=0。圖63表述了用信號量及P、V操作來正確處理GET、COPY和PUT三者之間的協(xié)同工作關系。圖63 用P、V操作保證GET、COPY和PUT三者的正確協(xié)作3．在圖64（a）（即教材中圖68）GET里，是先安放V(S1)，再安放P(S2)的。能把它們兩個的安放順序顛倒過來變成圖64（b）嗎？為什么？圖64 安放V(S1)和P(S2)的兩種方法答：圖64（b）里是先安放P(S2), 再安放V(S1)。這種安放順序是不行的。因為安放P(S2)，表示要在此等待COPY發(fā)來的消息（即希望COPY執(zhí)行V(S2)操作），在接到了COPY的消息后，才執(zhí)行V(S1)（即向COPY發(fā)消息）。但是，根據(jù)COPY的安排，不接到GET發(fā)來的消息（即執(zhí)行P(S1)操作），是不會向COPY發(fā)消息的（即執(zhí)行V(S2)操作）。于是，GET和COPY就陷入了循環(huán)等待：GET等待COPY發(fā)消息，COPY等待GET發(fā)消息。產(chǎn)生兩個死鎖了。4．進程A和B共享一個變量，因此在各自的程序里都有自己的臨界區(qū)?，F(xiàn)在進程A在臨界區(qū)里。試問進程A的執(zhí)行能夠被別的進程打斷嗎？能夠被進程B打斷嗎（這里，“打斷”的含義是調(diào)度新進程運行，使進程A暫停執(zhí)行）？答：當進程A在自己的臨界區(qū)里執(zhí)行時，能夠被別的進程打斷，沒有任何的限制。當進程A在自己的臨界區(qū)里執(zhí)行時，也能夠被進程B打斷，不過這種打斷是有限制的。即當進程B執(zhí)行到要求進入自己的臨界區(qū)時，就會被阻塞。這是因為在它打斷進程A時，A正在臨界區(qū)里還沒有出來，既然A在臨界區(qū)，B當然就無法進入自己的臨界區(qū)。5．信號量上的P、V操作只是對信號量的值進行加1或減1操作嗎？在信號量上還能夠執(zhí)行除P、V操作外的其他操作嗎？答：根據(jù)信號量的定義可知，P、V操作并非只是對信號量進行減1或加1操作，更重要的是在減1或加1后，還要判斷運算的結果。對于P操作，判定后調(diào)用進程自己有可能繼續(xù)運行，也可能阻塞等待。對于V操作，判定后調(diào)用進程自己最后總是繼續(xù)運行，但之前可能會喚醒在信號量隊列上等待的進程。在信號量上除了能執(zhí)行P、V操作外，不能執(zhí)行其他任何操作。6．系統(tǒng)有輸入機和打印機各一臺，均采用PV操作來實現(xiàn)分配和釋放?，F(xiàn)在有兩個進程都要使用它們。這會發(fā)生死鎖嗎？試說明理由。答：采用信號量上的P、V操作，只能正確地完成對設備的申請與釋放，但不能控制進程對設備的申請、釋放順序。因此，當進程申請和釋放設備的順序不當時，仍會發(fā)生死鎖。例如，進程A使用輸入機和打印機的順序是：請求打印機（Ar1）→請求輸入機（Ar2）→釋放打印機（Ar3）→釋放輸入機（Ar4）進程B使用輸入機和打印機的順序是：請求輸入機（Br1）→請求打印機（Br2）→釋放輸入機（Br3）→釋放打印機（Br4）其中圓括號里標注的字母，表示某進程對設備的某種使用。例如，Ar1表示進程A請求打印機。由于A和B都是進程，它們的執(zhí)行可以交叉進行。執(zhí)行順序： Ar1→Ar2→Ar3→Ar4→Br1→Br2→Br3→Br4 或 Ar1→Ar2→Br1→Ar3→Ar4→Br2→Br3→Br4都是合理的交叉。但是，以Ar1→Br1開始的執(zhí)行就無法再往下進行了。因為進程A執(zhí)行了Ar1，表明它占用了打印機。接著進程B執(zhí)行了Br1，表明它占用了輸入機。這樣一來，不管后面是執(zhí)行Ar2（進程A申請輸入機）還是執(zhí)行Br2（進程B申請打印機），都不可能得到滿足，兩個進程先后被阻塞：進程A占據(jù)著打印機而等待輸入機，進程B占據(jù)著輸入機而等待打印機。這就產(chǎn)生了死鎖。7．現(xiàn)有4個進程A、B、C、D，共享10個單位的某種資源?；緮?shù)據(jù)如圖65（即教材中的圖628）所示。試問如果進程D再多請求一個資源單位，所導致的是安全狀態(tài)還是不安全狀態(tài)？如果是進程C提出同樣的請求，情況又會是怎樣呢？答：若進程D多請求一個資源，資源的使用情況如圖66（a）所示。這時，系統(tǒng)剩余1個資源，4個進程各自還需要的資源數(shù)是2，資源剩余數(shù)無法保證任何一個進程運行結束。所以D多請求一個資源單位，會導致不安全狀態(tài)。若是進程C提出同樣的請求，那么系統(tǒng)資源的使用情況如圖66（b）所示。這時，整個系統(tǒng)雖然也只剩余1個資源，但卻能夠保證4個進程都完成。所以，C再多請求一個資源單位，系統(tǒng)將處于安全狀態(tài)。圖65 第7題的基本數(shù)據(jù)圖66 不安全與安全狀態(tài)示意圖8．假定圖67（即教材中的圖621）里的進程A申請最后一臺磁帶機，會引起死鎖嗎？圖67 多種資源的銀行家算法答：進程A申請了最后一臺磁帶機后，系統(tǒng)資源的使用情況由圖67變?yōu)閳D68。按照多種資源的銀行家算法，這時系統(tǒng)資源的剩余數(shù)可以滿足進程D的要求，于是系統(tǒng)資源剩余數(shù)矩陣A變?yōu)锳 [1 1 2 1]；這樣的剩余數(shù)，可以滿足進程A的要求，于是系統(tǒng)資源剩余數(shù)矩陣A變?yōu)锳 [5 1 3 2]；這樣的剩余數(shù)，可以滿足進程B、C、E三個進程中任何一個的需要，例如給E。在E完成后，系統(tǒng)資源剩余數(shù)矩陣A仍為A [5 1 3 2]；再給C，C完成后系統(tǒng)資源剩余數(shù)矩陣A變?yōu)锳 [6 2 4 2]；再給B，B完成后系統(tǒng)資源剩余數(shù)矩陣A變?yōu)锳 [6 3 4 2]，系統(tǒng)收回了所有資源。由此可知，進程A申請最后一臺磁帶機，不會引起死鎖。9．一個計算機有6臺磁帶機，有n個進程競爭使用，每個進程最多需要兩臺。那么n為多少時，系統(tǒng)才不存在死鎖的危險？答：由于每個進程最多需要兩臺磁帶機，考慮極端情況：每個進程已經(jīng)都申請了一臺。那么只要還有一臺空閑，就可以保證所有進程都可以完成。也就是說當有條件：n+1=6（即n=5）時，系統(tǒng)就不存在死鎖的危險。圖68 進程A申請了最后一臺磁帶機后10．考慮教材中的圖616（d）。如果進程C需要的是資源S，而不是資源R，這會引起死鎖嗎？如果是既要求資源R又要求資源S，情況會怎樣？答：這時的資源使用序列為：（1）A申請R，C申請T，A申請S，C申請S，A釋放R，A釋放S；（2）A申請R，C申請T，A申請S，C申請S，C申請R，A釋放R，A釋放S。分別畫出它們的資源分配圖，可知，它們都不會引起死鎖。四、計算1．在公共汽車上，司機和售票員的工作流程如圖69（即教材上的圖629）所示。為了確保行車安全，試用信號量及其P、V操作來協(xié)調(diào)司機和售票員的工作。圖69 司機與售票員解：從日常生活知識知道，司機和售票員之間的工作有如下的制約關系存在。（1）司機必須在得到售票員的