第六章作業(yè)(OS)答案

1、第六章 作業(yè)1存放在某個磁盤上的文件系統(tǒng)，采用混合索引分配方式，其FCB中共有13個地址項(xiàng)，第09個地址項(xiàng)為直接地址，第10個地址項(xiàng)為一次間接地址，第11個地址項(xiàng)為二次間接地址，第12個地址項(xiàng)為三次間接地址。如果每個盤塊的大小為512字節(jié)，若盤塊號需要用3個字節(jié)來描述，而每個盤塊最多存放170個盤塊地址：(1)該文件系統(tǒng)允許文件的最大長度是多少？(2)將文件的字節(jié)偏移量5000、15000、150000轉(zhuǎn)換為物理塊號和塊內(nèi)偏移量。答：（1）該文件系統(tǒng)中一個文件的最大長度可達(dá)：10+170+170*170+170*170*170=4942080塊=4942080*512字節(jié)=2471040KB（

2、2）5000/512得到商為9，余數(shù)為392，即字節(jié)偏移量5000對應(yīng)的邏輯塊號為9，塊內(nèi)偏移量為392。由于9<10，故可直接從該文件的FCB的第9個地址項(xiàng)處得到物理盤塊號，塊內(nèi)偏移量為392。15000/512得到商為29，余數(shù)為152，即字節(jié)偏移量15000對應(yīng)的邏輯塊號為29，塊內(nèi)偏移量為152。由于1029<10+170，而29-10=19，故可從FCB的第10個地址項(xiàng)，即一次間址項(xiàng)中得到一次間址的地址；并從一次間址塊的第19項(xiàng)（即該塊的第5759這3個字節(jié)）中獲得對應(yīng)的物理盤塊號，塊內(nèi)偏移量為152。150000/512得到商為292，余數(shù)為496，即字節(jié)偏移量1500

3、00對應(yīng)的邏輯塊號為292，塊內(nèi)偏移量為496。由于10+170292<10+170+170*170,而292-(10+170)=112，112/170得到商為0，余數(shù)為112，故可從FCB的第11個地址項(xiàng)，即二次間址項(xiàng)中得到二次間址塊的地址，并從二次間址塊的第0項(xiàng)中獲得一個一次間址塊的地址，再從該一次間址塊的第112項(xiàng)中獲得對應(yīng)的物理盤塊號，塊內(nèi)偏移量為496。（3）由于文件的FCB已在內(nèi)存，為了訪問文件中某個位置的內(nèi)容，最少需要1次訪問磁盤（即可通過直接地址直接讀文件盤塊），最多需要4次訪問磁盤（第一次是讀三次間址塊，第二次是讀二次間址塊，第三次是讀一次間址塊，第四次是讀文件盤塊）。

4、2.在某個文件系統(tǒng)中，每個盤塊為512個字節(jié)，文件控制塊占64個字節(jié)，其中文件名占8個字節(jié)。如果索引結(jié)點(diǎn)編號占2個字節(jié)，對于一個存放在磁盤上的256個目錄項(xiàng)的目錄，試比較引入索引結(jié)點(diǎn)前喉，為找到其中一個文件的FCB，平均啟動磁盤的次數(shù)？答：在引入索引結(jié)點(diǎn)前，每個目錄項(xiàng)中存放的是對應(yīng)文件的FCB，故256個目錄項(xiàng)的目錄總共需要占用256*64/512=32個盤塊。因此，在該項(xiàng)目錄中檢索到一個文件，平均啟動磁盤的次數(shù)為（1+32）/2=16.5。 在引入索引結(jié)點(diǎn)之后，每個目錄項(xiàng)中只需存放文件名和索引結(jié)點(diǎn)的編號，因此256個目錄項(xiàng)的目錄總共需要占用256*(8+2)/512=5個盤塊。因此，找到匹配

5、的目錄項(xiàng)平均需要啟動(1+5)/2，即3次磁盤；而得到索引結(jié)點(diǎn)編號后，還需啟動磁盤將對應(yīng)文件的索引結(jié)點(diǎn)讀入內(nèi)存，故平均需要啟動磁盤4次?？梢?，引入索引結(jié)點(diǎn)后，可大大減少啟動磁盤的次數(shù)，從而有效地提高檢索文件的速度。第五章 作業(yè)1有一移動臂磁盤，共100個磁道，每個磁道分8個扇區(qū)，磁盤轉(zhuǎn)速為500r/s（轉(zhuǎn)/秒），磁頭每移動一個磁道需要10ms,有一用戶請求訪問第25磁道第3扇區(qū)，并立即被系統(tǒng)響應(yīng)，假設(shè)磁頭當(dāng)時處于15道 上，磁頭到達(dá)第25道時正處于1扇區(qū)的開始位置，試計(jì)算該用戶至少需要等待多長時間？2. 若有磁盤共有200個柱面，其編號為199，假定磁頭剛完成56號磁道的訪問，磁頭正在98號磁

6、道上，并向磁道號增加的方向移動，現(xiàn)有一個請求隊(duì)列在等待訪問磁盤，訪問的磁道號分別為190，97，90，45，150，32，162，108，112，80。請寫出分別采用FCFS、SSTF、SCAN和CSCAN算法進(jìn)行調(diào)度磁盤時的請求次序，并計(jì)算出它們的平均尋道長度。3假定磁盤轉(zhuǎn)速為20ms/圈，磁盤格式化時每個磁道被劃分成10個扇區(qū)，今有10個邏輯記錄（每個記錄的大小剛好與扇區(qū)大小相等）存放在同一磁道上，處理程序每次從磁盤讀出一個記錄后要花費(fèi)4ms進(jìn)行處理，現(xiàn)要求順序處理這10個記錄，若磁頭現(xiàn)在正處于首個邏輯記錄的始點(diǎn)位置。請問：（1）按逆時針方向安排10個邏輯記錄（磁盤順時針方向轉(zhuǎn)），處理程序

7、處理完這10個記錄所花費(fèi)的時間是多少？（2）按最優(yōu)化分布重新安排這10個邏輯記錄，寫出記錄的安排，并計(jì)算出所需要處理的時間。1.某系統(tǒng)采用頁式存儲管理策略，擁有邏輯空間32頁，每頁2K，擁有物理空間1M。（1）請寫出邏輯地址的格式。（2）若不考慮訪問權(quán)限等，進(jìn)程的頁表有多少項(xiàng)？每項(xiàng)至少有多少位？（3）如果物理空間減少一半，頁表結(jié)構(gòu)應(yīng)相應(yīng)作怎樣的改變？答：（1）該系統(tǒng)擁有邏輯空間32頁，故邏輯地址中頁號必須用5位來描述；而每頁為2K，因此，頁內(nèi)地址必須用11位來描述，這樣可得到它的邏輯地址格式如下： 15 11 10 0頁號 頁內(nèi)地址（2）每個進(jìn)程最多有32個頁面，因此，進(jìn)程的頁表項(xiàng)最多為32項(xiàng)

8、；若不考慮訪問權(quán)限等，則頁表項(xiàng)中只需給出頁所對應(yīng)的物理塊號，1M的物理空間可分成29個內(nèi)存塊，故每個頁表項(xiàng)至少有9位。（3）如果物理空間減少一半，則頁表中頁表項(xiàng)數(shù)仍不變，但每項(xiàng)的長度可減少1位。2.對一個將頁表存放在內(nèi)存中的分頁系統(tǒng)：（1）如果訪問內(nèi)存需要0.2微秒，有效訪問時間為多少？（2）如果加一快表，且假定在快表中找到頁表項(xiàng)的幾率高達(dá)90，則有效訪問時間是多少？（假定查找快表需花的時間是0）答：（1）有效訪問時間為；2*0.2=0.4微秒(2)有效訪問時間為：0.9*0.2+(1-0.9)*2*0.2=0.22微秒3某分頁系統(tǒng)，主存容量為64K，頁面大小為1K，對一個4頁大的作業(yè)，其0、

9、1、2、3頁分別被分配到主存的2、4、6、7塊中。(1)將十進(jìn)制的邏輯地址1023、2500、3500、4500轉(zhuǎn)換為物理地址。(2)以十進(jìn)制的邏輯地址1023為例畫出地址變換過程圖。答：（1）對上述邏輯地址，可先計(jì)算出它們的頁號和頁內(nèi)地址（邏輯地址除以頁面大小，得到的商為頁號，余數(shù)為頁內(nèi)地址），然后通過頁表轉(zhuǎn)換成對應(yīng)的物理地址。邏輯地址1023:1023/1K，得到頁號為0，頁內(nèi)地址為1023，查頁表找到對應(yīng)的物理塊號為2，故物理地址為2*1K+1023=3071邏輯地址2500:2500/1K，得到頁號為2，頁內(nèi)地址為452，查頁表找到對應(yīng)的物理塊號為6，故物理地址為6*1K+452=65

10、96邏輯地址3500:3500/1K，得到頁號為3，頁內(nèi)地址為428，查頁表找到對應(yīng)的物理塊號為7，故物理地址為7*1K+428=7596邏輯地址為4500:4500/1K，得到頁號為4，頁內(nèi)地址為404，因頁號不小于頁表長度故產(chǎn)生越界中斷。 4某操作系統(tǒng)采用可變分區(qū)分配存儲管理方法，用戶區(qū)為512K且始址為0，用空閑分區(qū)表管理空閑分區(qū)。若分配時采用分配空閑區(qū)低地址部分的方案，且初始時用戶區(qū)的512K空間空閑，對下述申請序列：申請300K，申請100K，釋放300K，申請150K，申請30K，申請40K，申請60K，釋放30K回答下列問題：(1)采用首次適應(yīng)算法，空閑分區(qū)中有哪些空塊？(2)采

11、用最佳適應(yīng)算法，空閑分區(qū)中有哪些空塊？(3)如再申請100K，針對(1)和 (2)各有什么結(jié)果 ？5在一分頁存儲管理系統(tǒng)中，邏輯地址長度為16位，頁面大小為4096字節(jié)，現(xiàn)有一邏輯地址為2F6AH，且第0、1、2頁依次存放在物理塊5、10、11中，問相應(yīng)的物理地址為多少？答：由題目所給條件可知，該系統(tǒng)的邏輯地址為16位，其中高4位為頁號。頁面大小4096字節(jié)，共要占有二進(jìn)制12位，低12位為頁內(nèi)地址；另外，由于題目中給出的邏輯地址是十六進(jìn)制數(shù)，故可先將其轉(zhuǎn)換成二進(jìn)制數(shù)以直接獲得頁號和頁內(nèi)地址，再完成地址的轉(zhuǎn)換2F6AH為0010111101101010，由此看出，邏輯地址（2F6A）16的頁號

12、為（0010）2，即2，故頁號合法；從頁表中找到對應(yīng)的內(nèi)存塊號為11，即（1011）2；與頁內(nèi)地址（111101101010）2拼接形成物理地址（1011111101101010）2，即（BF6A）16。6.在一個段式存儲管理系統(tǒng)中，其段表如圖1段號 內(nèi)存起始地址 段長 0 210 500 1 2350 20 2 100 90 3 1350 590 4 1938 95 圖1試求圖2邏輯地址對應(yīng)的物理地址。段號 段內(nèi)位移 0 430 1 10 2 500 3 400 4 112 5 32 圖2答：（1）段號0小于段表長5，故段號合法；由段表的第0項(xiàng)可獲得段的內(nèi)存始址為210，段長為500;由于段

13、內(nèi)地址430，小于段長500，故段內(nèi)地址也是合法的，因此可得出對應(yīng)的物理地址為210+430=640。（2）段號1小于段表長5，故段號合法；由段表的第1項(xiàng)可獲得段的內(nèi)存始址為2350，段長為20;由于段內(nèi)地址10，小于段長20，故段內(nèi)地址也是合法的，因此可得出對應(yīng)的物理地址為2350+10=2360。（3）段號2小于段表長5，故段號合法；由段表的第2項(xiàng)可獲得段的內(nèi)存始址為100，段長為90;由于段內(nèi)地址500，超過段長90，故產(chǎn)生越界中斷。（5）段號5等于段表長，故段號不合法，產(chǎn)生越界中斷。7在一采取局部置換策略的請求分頁系統(tǒng)中，分配給某個作業(yè)的內(nèi)存塊數(shù)是4，其中存放的四個頁面的情況如表所示。

14、物理塊虛頁號裝入時間最后一次訪問時間訪問位修改位0260157011116016110202615800332016311上面的所有數(shù)字均為十進(jìn)制，所有時間都是從進(jìn)程開始運(yùn)行時從0開始計(jì)數(shù)的時鐘數(shù)。請問，如果系統(tǒng)采用下列置換算法，將選擇哪一頁進(jìn)行換出？（1）FIFO算法；（2）LRU算法；（3）改進(jìn)的Clock算法。答：（1）FIFO算法選擇的換出頁是物理塊3中的第3頁。（2）LRU算法選擇的換出頁是物理塊0中的第2頁。（3）改進(jìn)的Clock算法選擇的換出頁是物理塊2中的第0頁。8.在一個請求分頁系統(tǒng)中，假如一個作業(yè)的頁面走向?yàn)椋?，3，2，1，4，3，5，4，3，2，1，5，目前它還沒有任何

15、頁裝入內(nèi)存，當(dāng)分配給該作業(yè)的物理塊數(shù)目M分別為3和4時，請分別計(jì)算采用OPT、LRU和FIFO頁面淘汰算法時訪問過程中所發(fā)生的缺頁數(shù)和缺頁率，并比較所得的結(jié)果。M=3時，OPT算法頁面走向 432143543215以后最長時間不用 2111544/33/21/2 3334335 444434435559.某頁式虛擬存儲管理系統(tǒng)的物理空間共3k，頁面大小為1k，一進(jìn)程按下列地址順序引用內(nèi)存單元：3635，3632，1140，3584，2892，3640，0040，2148，1700，2145，3290，0000，1102，1100。如果上述數(shù)字均為十進(jìn)制數(shù)，而內(nèi)存中尚未裝入任何頁。給出使用LRU

16、算法時的缺頁率，并與FIFO時的情況進(jìn)行比較。答：（1）根據(jù)題意，分配給作業(yè)的內(nèi)存塊數(shù)為3，而頁面的引用次序?yàn)?、3、1、3、2、3、0、2、1、2、3、0、1、1。因此，可以計(jì)算出，采用LRU算法時，缺頁次數(shù)為8，采用FIFO算法時，缺頁次數(shù)為6。LRU算法用最近的過去來作為預(yù)測最近的將來的依據(jù)，一般認(rèn)為其有較好的性能，但實(shí)現(xiàn)時，要記錄最近在內(nèi)存的每個頁面的使用情況，比FIFO困難，其開銷也大。有時，因頁面的過去和未來的走向之間并無必然的聯(lián)系，如上面，LRU算法的性能就沒想象中那么好。第三章 作業(yè)1.假設(shè)有四個作業(yè),它們提交、運(yùn)行時間如下表所示。若采用先來先服務(wù)、短作業(yè)優(yōu)先、響應(yīng)比高者優(yōu)先調(diào)

17、度算法，試問平均周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間為多少？ （時間單位：小時，以十進(jìn)制進(jìn)行計(jì)算。）作業(yè)號到達(dá)時間運(yùn)行時間18.02.028.30.538.50.149.00.42.假如有四道作業(yè)，它們的提交時間及運(yùn)行時間如下表所示。作業(yè)號到達(dá)時間（時）運(yùn)行時間（時）開始時間（時）完成時間（時）周轉(zhuǎn)時間T（時）帶權(quán)周轉(zhuǎn)時間（時）18:002.028:500.539:000.149:500.2假設(shè)系統(tǒng)采用單道程序設(shè)計(jì)技術(shù)，請給出系統(tǒng)在分別采用FCFS（先來先服務(wù)）、SJT（短作業(yè)優(yōu)先）和HRN（響應(yīng)比高者優(yōu)先）作業(yè)調(diào)度算法時它們的調(diào)度作業(yè)順序、作業(yè)的平均周轉(zhuǎn)時間T和平均帶權(quán)周轉(zhuǎn)時間W，并相互比較之。解：（1）

18、FCFS （2）SJF（3）響應(yīng)比高者優(yōu)先第一個作業(yè)完成時間為10.0，此時其它作業(yè)的響應(yīng)比計(jì)算如下：R2=(0.5+10-8.5)/0.5=4R3=(0.1+10-9)/0.1=11R4=(0.2+10-9.5)/0.2=3.5根據(jù)響應(yīng)比高者優(yōu)先調(diào)度原則，應(yīng)先運(yùn)行作業(yè)3，作業(yè)3完成時間為10.1,此時作業(yè)2和作業(yè)4的響應(yīng)比計(jì)算如下：R2=(0.5+10.1-8.5)/0.5=4.2R4=(0.2+10.1-9.5)/0.2=4根據(jù)響應(yīng)比高者優(yōu)先調(diào)度原則，應(yīng)先運(yùn)行作業(yè)2，作業(yè)2完成時間為10.6,最后運(yùn)行作業(yè)4，作業(yè)4完成時間為10.8。作業(yè)號到達(dá)時間運(yùn)行時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間平均周

19、轉(zhuǎn)時間平均帶權(quán)周轉(zhuǎn)時間18.02.010.02.0128.50.510.62.14.239.00.110.11.11149.50.210.81.36.53. 假設(shè)一個系統(tǒng)中有5個進(jìn)程，它們的到達(dá)時間和服務(wù)時間如表所示，忽略I/O以及其他開銷時間，若分別按先來先服務(wù)(FCFS)、非搶占及搶占的短進(jìn)程優(yōu)先(SPF)高響應(yīng)比優(yōu)先(HRRN)、時間片輪轉(zhuǎn)(RR，時間片=1)調(diào)度算法進(jìn)行CPU調(diào)度，請給出各進(jìn)程的完成時間、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。進(jìn)程到達(dá)時間服務(wù)時間A03B26C44D65E82解：進(jìn)程ABCDE平均FCFS完成時間39131820周轉(zhuǎn)時間37912128

20、.6帶權(quán)周轉(zhuǎn)時間1.001.172.252.406.002.56SPF(非搶占)完成時間39152011周轉(zhuǎn)時間37111437.6帶權(quán)周轉(zhuǎn)時間1.001.172.752.801.501.84SPF（搶占）完成時間31582010周轉(zhuǎn)時間31341427.2帶權(quán)周轉(zhuǎn)時間1.002.161.0002.801.001.59HRRN完成時間39132015周轉(zhuǎn)時間3791478帶權(quán)周轉(zhuǎn)時間1.001.172.252.803.502.14RR（q=1）完成時間418172015周轉(zhuǎn)時間4161314710.8帶權(quán)周轉(zhuǎn)時間1.332.673.252.803.502.714對下面的5個非周期性實(shí)時任務(wù)，按

21、最早開始截止時間優(yōu)先權(quán)調(diào)度算法應(yīng)如何進(jìn)行CPU調(diào)度?進(jìn)程到達(dá)時間執(zhí)行時間開始截止時間A1020110B202020C402050D502090E602070提示:按搶占式和非搶占式分別計(jì)算解：西電參考書P665在一個實(shí)時系統(tǒng)中,有三個周期性實(shí)時任務(wù),任務(wù)A要求每20ms執(zhí)行一次,執(zhí)行時間為10ms;任務(wù)B要求50ms執(zhí)行一次,執(zhí)行時間為10ms;任務(wù)C要求50ms執(zhí)行一次,執(zhí)行時間為15ms,應(yīng)如何按最低松弛度優(yōu)先算法對它們進(jìn)行CPU調(diào)度?（選作）解：西電參考書P676設(shè)系統(tǒng)中有3種類型的資源（A，B，C）和5個進(jìn)程（P1，P2，P3，P4，P5），A資源的數(shù)量為17，B資源的數(shù)量為5，C資源

22、的數(shù)量為20。在T0時刻系統(tǒng)狀態(tài)如下表所示。進(jìn)程AllocationNeedAvailableABCABCABCP1212347233P2402134P3405006P4204221P5314110進(jìn)程 最大資源需求量 已分配資源數(shù)量 A B C A B CP1P2P3P4P55544453022961154244231000122544剩余資源數(shù)A B C2 3 3系統(tǒng)采用銀行家算法實(shí)施死鎖避免策略。（1）T0時刻是否為安全狀態(tài)？若是，請給出安全序列。（2）在T0時刻若進(jìn)程P2請求資源（0，3，4），是否能實(shí)施資源分配？為什么？（3）在（2）的基礎(chǔ)上，若進(jìn)程P4請求資源（2，0，1），是否能

23、實(shí)施資源分配？為什么？（4）在（3）的基礎(chǔ)上，若進(jìn)程P1請求資源（0，2，0），是否能實(shí)施資源分配？為什么？解：T0時刻資源分配圖（1）T0時刻是否安全(安全性檢查)進(jìn)進(jìn)程workneedallocationWork+allocationFfinish2A3B3CAABBCCAABBCCAABBCCPP5223333111100331144554477tTruePP44544772222112200447744111ttruePP3774411100006644005511144116ttruePP21114411611334444002211544118tTruePP111544118334

24、47722112211755220tTrue從表3所示可以看出，在T0時刻存在一個安全序列P5，P4，P3，P2，P1，故該狀態(tài)是安全的。（2）在T0時刻因進(jìn)程P2的請求資源（0，3，4）剩余資源數(shù)（2，3，3），所以不能分配（3）在（2）的基礎(chǔ)，若進(jìn)程P4的請求資源為（2，0，1），按銀行家算法進(jìn)行如下檢查：P4請求資源（2，0，1）P4資源需求量（2，2，1）；P4請求資源（2，0，1） 剩余資源數(shù)（2，3，3）；此時的資源分配情況如表4所示（已分配給P4（2，0，1）后的情況。表4 資源分配情況進(jìn)程AllocationNeedAvailableABCABCABCP1212347032P2

25、402134P3405006P4405020P5314110此時刻的安全性分析如表5所示。表5 安全性分析進(jìn)程workneedAllocationWork+allocationFinishABCABCABCABCP4032020405437TP54371103147411TP3741100640511416TP21141613440215418TP11541834721217520T從表5所示可以看出，此時刻存在一個安全序列P4，P5，P3，P2，P1，即可以將P4申請的資源分配給它。（4）在（3）的基礎(chǔ)上，若進(jìn)程P1請示資源（0，2，0），按銀行家算法進(jìn)行如下檢查：P1請求資源（0，2，0）

26、P1資源需求量（3，4，7）；P1請求資源（0，2，0） 剩余資源數(shù)（0，3，2）；此時的資源分配情況如表6所示（已分配給P1（0，2，0）后的情況）。表6 資源分配情況進(jìn)程AllocationNeedAvailableABCABCABCP1232327012P2402134   P3405006   P4405020   P5314110   此時，可用資源Available已不能滿足任何進(jìn)程的資源需求，因此不能將資源分配給P1。7假定某計(jì)算機(jī)系統(tǒng)有R1(2)、R2(1)兩

27、類可再使用資源,它們被進(jìn)程P1、P2所共享,兩個進(jìn)程均以下列順序使用資源:->申請R1->申請R2->申請R1->釋放R1->釋放R2->釋放R1 ->試求出系統(tǒng)可能到達(dá)的死鎖點(diǎn)，并畫出死鎖點(diǎn)的資源分配圖。P1R2R1P18. 化簡下圖中的資源分配圖（進(jìn)程-資源圖），并利用死鎖定理給出相應(yīng)的結(jié)論。P1P2(a)P1P2P3R1R2R1R2R3R4(b)1、桌上有一空盤，只允許存放一個水果。爸爸可向盤中放蘋果，也可向盤中放桔子。兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定當(dāng)盤中空時一次只能放一只水果供吃者取用，請用P、V原語實(shí)現(xiàn)爸爸、兒子、女兒三個并發(fā)進(jìn)程的同步。分析 在本題中，爸爸、兒子、女兒共用一個盤子，且盤中一次只能放一個水果。當(dāng)盤子為空時，爸爸可將一個水果放