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