計(jì)算機(jī)操作系統(tǒng)專升本復(fù)習(xí)題-計(jì)算題課件

操作系統(tǒng)專升本復(fù)習(xí)----計(jì)算題操作系統(tǒng)專升本復(fù)習(xí)----計(jì)算題計(jì)算題類型1：作業(yè)調(diào)度、進(jìn)程調(diào)度算法根據(jù)先來先服務(wù)、短作業(yè)優(yōu)先、優(yōu)先級、高響應(yīng)比優(yōu)先、輪轉(zhuǎn)（RR）等調(diào)度算法求作業(yè)的執(zhí)行順序、作業(yè)的周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。2008年（8分）：短作業(yè)優(yōu)先、先來先服務(wù)調(diào)度算法2014年（7分）：短作業(yè)優(yōu)先調(diào)度算法2015年（8分）：先來先服務(wù)、短作業(yè)優(yōu)先調(diào)度算法2017年（10分）：先來先服務(wù)調(diào)度算法、搶占式優(yōu)先級調(diào)度算法；計(jì)算題類型1：作業(yè)調(diào)度、進(jìn)程調(diào)度算法根據(jù)先來先服務(wù)、短作業(yè)優(yōu)例1：在單機(jī)系統(tǒng)中，系統(tǒng)中各個(gè)進(jìn)程到達(dá)就緒隊(duì)列的時(shí)刻、執(zhí)行時(shí)間和優(yōu)先級（越小者越高）如下表所示。假設(shè)進(jìn)程的調(diào)度時(shí)間忽略不計(jì)。1、請給出采用FCFS、短作業(yè)優(yōu)先調(diào)度算法時(shí)各個(gè)進(jìn)程的調(diào)度順序，并計(jì)算平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。2、請計(jì)算采用搶占式優(yōu)先級調(diào)度算法時(shí)各個(gè)進(jìn)程的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。進(jìn)程到達(dá)時(shí)間執(zhí)行時(shí)間(ms)優(yōu)先級P1033P2265P3441P4652P5824例1：在單機(jī)系統(tǒng)中，系統(tǒng)中各個(gè)進(jìn)程到達(dá)就緒隊(duì)列的時(shí)刻、執(zhí)行時(shí)平均周轉(zhuǎn)時(shí)間：（3+7+9+12+12）/5=8.6平均帶權(quán)周轉(zhuǎn)時(shí)間：（1+1.17+2.25+2.4+6）/5=2.56進(jìn)程到達(dá)時(shí)間執(zhí)行時(shí)間(ms)優(yōu)先級完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P1033P2265P3441P4652P582431318209379121211.172.252.461、FCFS調(diào)度算法平均周轉(zhuǎn)時(shí)間：（3+7+9+12+12）/5=8.6進(jìn)程到達(dá)平均周轉(zhuǎn)時(shí)間：（3+7+3+11+14）/5=7.6平均帶權(quán)周轉(zhuǎn)時(shí)間：（1+1.17+2.25+2.4+6）/5=1.84進(jìn)程到達(dá)時(shí)間執(zhí)行時(shí)間(ms)優(yōu)先級完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P1033P2265P5824P3441P465231115209373111411.171.52.752.8短作業(yè)優(yōu)先調(diào)度算法平均周轉(zhuǎn)時(shí)間：（3+7+3+11+14）/5=7.6進(jìn)程到達(dá)平均周轉(zhuǎn)時(shí)間：（3+18+4+7+7）/5=7.8平均帶權(quán)周轉(zhuǎn)時(shí)間：（1+3+1+1.4+3.5）/5=1.98進(jìn)程到達(dá)時(shí)間執(zhí)行時(shí)間(ms)優(yōu)先級完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P1033P2265P3441P4652P5824381315203184771311.43.52、采用搶占式優(yōu)先級調(diào)度算法平均周轉(zhuǎn)時(shí)間：（3+18+4+7+7）/5=7.8進(jìn)程到達(dá)時(shí)作業(yè)進(jìn)入系統(tǒng)時(shí)間計(jì)算時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間19:0060分鐘9:0010:00⑴29:1045分鐘⑵⑶⑷39:1525分鐘⑸⑹⑺例2：在一個(gè)單道批處理系統(tǒng)中，采用響應(yīng)比高者優(yōu)先的作業(yè)調(diào)度算法。當(dāng)一個(gè)作業(yè)進(jìn)入系統(tǒng)后就可以開始調(diào)度，假定作業(yè)都是僅計(jì)算，忽略調(diào)度花費(fèi)的時(shí)間。現(xiàn)有三個(gè)作業(yè)，進(jìn)入系統(tǒng)的時(shí)間和需要計(jì)算的時(shí)間如下表所示。求出每個(gè)作業(yè)的開始時(shí)間、完成時(shí)間及周轉(zhuǎn)時(shí)間并填入表中。作業(yè)進(jìn)入系統(tǒng)時(shí)間計(jì)算時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間19:006作業(yè)進(jìn)入系統(tǒng)時(shí)間計(jì)算時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間（分鐘）19:0060分鐘9:0010:00⑴29:1045分鐘⑵⑶⑷39:1525分鐘⑸⑹⑺60響應(yīng)比=（服務(wù)時(shí)間+等待時(shí)間）/服務(wù)時(shí)間=1+等待時(shí)間/服務(wù)時(shí)間10:00計(jì)算作業(yè)2、3的響應(yīng)比，如下：作業(yè)2響應(yīng)比：1+50/45=2.11作業(yè)3響應(yīng)比：1+45/25=2.8作業(yè)3的響應(yīng)比高，因此10:00開始執(zhí)行作業(yè)3，10:25完成。最后執(zhí)行作業(yè)2。10:0010:257010:2511:10120作業(yè)進(jìn)入系統(tǒng)時(shí)間計(jì)算時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間19:006計(jì)算題類型2：銀行家算法如果判斷某時(shí)刻是否為安全狀態(tài)采用安全性算法（若安全，執(zhí)行安全性算法結(jié)束寫明安全序列和系統(tǒng)狀態(tài)是安全的）；如果某進(jìn)程提出資源請求采用銀行家算法（寫清1、2、3、4步）。2008年（8分）、2011年、2012年、2013年計(jì)算題類型2：銀行家算法如果判斷某時(shí)刻是否為安全狀態(tài)采用安全進(jìn)程最大需求已分配

AB

AB

P1

32

11P2

64

40P3

31

212013年真題例3：已知系統(tǒng)內(nèi)有三個(gè)進(jìn)程P1、P2、P3共享A、B兩類資源，A類資源的數(shù)量為8，B類資源的數(shù)量為5。設(shè)在T時(shí)刻資源分配情況如下表所示:（1）問T時(shí)刻A、B的可利用資源數(shù)分別是多少?（2）T時(shí)刻系統(tǒng)是否處于安全狀態(tài)?為什么?

計(jì)算題類型3：地址變換1.動態(tài)可重定位分區(qū)分配的地址變換2.分頁存儲管理方式的地址變換3.分段存儲管理方式的地址變換2012年（選擇題1分）、2016年（10分）例4：（2012年真題）一個(gè)32位的虛擬地址分為4個(gè)域，每個(gè)域的長度分別為a、b、c、d位，其中d為頁內(nèi)地址，則系統(tǒng)最多可有（B）個(gè)虛擬頁面。A.a+b+cB.2a+b+cC.dD.2d計(jì)算題類型3：地址變換1.動態(tài)可重定位分區(qū)分配的地址變換1.動態(tài)可重定位分區(qū)分配的地址變換例5：在分區(qū)存儲管理中，已知某作業(yè)空間如圖所示，采用動態(tài)重定位進(jìn)行地址映射。假設(shè)分給該作業(yè)的主存空間起始地址為4000。

（1）指出在圖中的地址1和地址2中，哪個(gè)是邏輯地址，哪個(gè)是物理地址？（2）在圖中填寫出執(zhí)行指令MOVL1，[2000]時(shí)，所取數(shù)據(jù)“100”的邏輯地址、物理地址以及動態(tài)重定位寄存器的內(nèi)容（用十進(jìn)制表示）。（3）在圖中填寫出指令“MOVL1，[2000]”的主存地址。+動態(tài)重定位寄存器

0MOVL1[2000]100作業(yè)空間500200049990MOVL1[2000]100內(nèi)存空間4000

9999地址1地址2

1.動態(tài)可重定位分區(qū)分配的地址變換例5：在分區(qū)存儲管理中，例6：在一分頁存儲管理系統(tǒng)中，邏輯地址長度為16位，頁面大小為4096字節(jié)，現(xiàn)有一邏輯地址為2F6AH，且第0、1、2頁依次存放在物理塊5、10、11中，問相應(yīng)的物理地址為多少？2.分頁存儲管理方式的地址變換解析：方法1邏輯地址2F6AH的二進(jìn)制：0010111101101010由于邏輯地址長度為16位，頁面大小為4096字節(jié)，即212，所以低12為表示頁內(nèi)地址所以頁號為2，對應(yīng)塊號為11（二進(jìn)制1011），因?yàn)閴K內(nèi)地址=頁內(nèi)地址，所以物理地址表示如下：其二進(jìn)制1011111101101010，即BF6AH0010111101101010頁號頁內(nèi)地址1011111101101010塊號塊內(nèi)地址例6：在一分頁存儲管理系統(tǒng)中，邏輯地址長度為16位，頁面大小例6：在一分頁存儲管理系統(tǒng)中，邏輯地址長度為16位，頁面大小為4096字節(jié)，現(xiàn)有一邏輯地址為2F6AH，且第0、1、2頁依次存放在物理塊5、10、11中，問相應(yīng)的物理地址為多少？解析：方法2由于邏輯地址長度為16位，頁面大小為4096字節(jié)，即212，所以低12為表示頁內(nèi)地址所以頁號為2，對應(yīng)塊號為11（十六進(jìn)制B），因?yàn)閴K內(nèi)地址=頁內(nèi)地址，所以物理地址表示如下：所以，物理地址為BF6AH2F6A頁號頁內(nèi)地址BF6A塊號塊內(nèi)地址例6：在一分頁存儲管理系統(tǒng)中，邏輯地址長度為16位，頁面大小例7：某虛擬存儲器的用戶空間共有32個(gè)頁面，每頁1KB，內(nèi)存16KB。假定某時(shí)刻系統(tǒng)為用戶的第0、1、2、3頁分別分配的物理塊號為5、10、4、7，給定虛擬地址093CH，請將其變換為物埋地址。邏輯地址093CH的二進(jìn)制：0000100100111100有已知得邏輯地址長度為15位，頁面大小為1KB，即210，所以低10為表示頁內(nèi)地址所以頁號為2，對應(yīng)塊號為4（二進(jìn)制0100），因?yàn)閴K內(nèi)地址=頁內(nèi)地址，所以物理地址表示如下：其二進(jìn)制0001000100111100，即113CH0000100100111100頁號頁內(nèi)地址0001000100111100塊號塊內(nèi)地址解析：例7：某虛擬存儲器的用戶空間共有32個(gè)頁面，每頁1KB，內(nèi)存段號內(nèi)存起始地址段長02105001235020210090313505904193895段號段內(nèi)位移043011025003400例8：在一個(gè)段式存儲管理系統(tǒng)中，其段表為：試求下列邏輯地址對應(yīng)的物理地址是什么？3.分段存儲管理方式的地址變換物理地址210+430=6402350+10=2360段內(nèi)地址越界1350+400=1750解析：段號內(nèi)存起始地址段長02105001235020210090計(jì)算題類型4：分頁存儲的數(shù)據(jù)訪問時(shí)間例9：假定快表檢索時(shí)間為20ns，內(nèi)存訪問時(shí)間為100ns。1.若能在快表中找到CPU給出的頁號，CPU存取一個(gè)數(shù)據(jù)將需要的訪問時(shí)間是多少？2.若不能在快表中找到CPU給出的頁號，則為存取一個(gè)數(shù)據(jù)需要的訪問時(shí)間是多少？3.若假定快表查找命中率為80%，則其有效訪問時(shí)間為多少？解析：1.則若能在快表中找到CPU給出的頁號，CPU存取一個(gè)數(shù)據(jù)將需要(20+100)=120ns。2.若不能在快表中找到CPU給出的頁號，則為存取一個(gè)數(shù)據(jù)將需要(20+100+100)=220ns。3.若假定快表查找命中率為80%，則其有效訪問時(shí)間為120*80%+220*(1-80%)=140ns。計(jì)算題類型4：分頁存儲的數(shù)據(jù)訪問時(shí)間例9：假定快表檢索時(shí)間為計(jì)算題類型5：頁面置換算法根據(jù)最佳、先進(jìn)先出、最近最久未使用頁面置換算法計(jì)算缺頁次數(shù)和缺頁率。2012年、2014年（LRU(最近最久未使用)頁面置換算法）例10（2012年真題）：在請求分頁系統(tǒng)中，一個(gè)進(jìn)程初始執(zhí)行連續(xù)訪問頁面的次序?yàn)椋?、2、1、3、0、2、4、0、2、1、3、4，利用FIFO頁面淘汰算法，進(jìn)程內(nèi)存只能保存3個(gè)頁面，共發(fā)生的缺頁次數(shù)為（B）。A.8B.9C.7D.10計(jì)算題類型5：頁面置換算法根據(jù)最佳、先進(jìn)先出、最近最久未使用例11：假定分頁虛擬存儲系統(tǒng)中，某進(jìn)程的頁面訪問蹤跡為：4，3，2，1，4，3，5，4，3，2，1，5，分配給它的內(nèi)存物理塊數(shù)為3。1.按最佳頁面置換算法，計(jì)算缺頁率。2.按先進(jìn)先出頁面置換算法，計(jì)算缺頁率。3.按LRU頁面置換算法，計(jì)算缺頁率。例11：假定分頁虛擬存儲系統(tǒng)中，某進(jìn)程的頁面訪問蹤跡為：4，計(jì)算題類型6：磁盤調(diào)度算法根據(jù)先來先服務(wù)、最短尋道時(shí)間優(yōu)先、掃描算法、循環(huán)掃描算法，給出尋道順序，并計(jì)算尋道總數(shù)和平均尋道長度。2008年（8分）：最短尋道時(shí)間優(yōu)先、掃描算法計(jì)算題類型6：磁盤調(diào)度算法根據(jù)先來先服務(wù)、最短尋道時(shí)間優(yōu)先、例12：一個(gè)可移動磁頭的磁盤具有200個(gè)磁道，其編號為0--199，當(dāng)它剛剛結(jié)束了125道的存取后，現(xiàn)正在處理143道的請求，假設(shè)系統(tǒng)當(dāng)前I/0請求序列以FIFO順序排列如下：86，147，91，177，94，150，102，175，130。試問對以下幾種磁盤調(diào)度算法而言，滿足以上請求序列，磁頭將如何移動？平均尋道長度是多少？1.先來先服務(wù)算法2.最短尋道時(shí)間優(yōu)先算法SSTF3.掃描算法SCAN4.循環(huán)掃描算法例12：一個(gè)可移動磁頭的磁盤具有200個(gè)磁道，其編號為0--先來先服務(wù)算法FCFS從143號磁道開始被訪問的下一個(gè)磁道號移動距離（磁道數(shù)）865714761915617786948315056102481757313045平均尋道長度：565/9=最短尋道時(shí)間優(yōu)先算法SSTF從143號磁道開始被訪問的下一個(gè)磁道號移動距離（磁道數(shù)）147415031302010228948913865175891772平均尋道長度：162/9=先來先服務(wù)算法FCFS從143號磁道開始被訪問的下一個(gè)磁道號掃描算法SCAN從143號磁道開始被訪問的下一個(gè)磁道號移動距離（磁道數(shù)）147415031752517721304710228948913865平均尋道長度：125/9=循環(huán)掃描算法CSCAN從143號磁道開始被訪問的下一個(gè)磁道號移動距離（磁道數(shù)）147415031752517728691915943102813028平均尋道長度：169/9=掃描算法SCAN從143號磁道開始被訪問的下一個(gè)磁道號移動距計(jì)算題類型7：索引分配與文件最大長度計(jì)算索引文件最大長度、計(jì)算增量式文件最大長度。2011年例13（2011年真題）：簡述在UNIX系統(tǒng)中采用混合索引方式。

如果每個(gè)盤塊大小是4KB，每個(gè)盤的地址要用4個(gè)字節(jié)，那么在UNIX系統(tǒng)中文件最大是多少？給出步驟說明。計(jì)算題類型7：索引分配與文件最大長度計(jì)算索引文件最大長度、計(jì)例13（2011年真題）：簡述在UNIX系統(tǒng)中采用混合索引方式。

如果每個(gè)盤塊大小是4KB，每個(gè)盤的地址要用4個(gè)字節(jié)，那么在UNIX系統(tǒng)中文件最大是多少？給出步驟說明。解析：由已知得每個(gè)盤塊大小4KB，每個(gè)盤塊號占4B，因此一個(gè)盤塊內(nèi)可以存放4KB/4B=1K個(gè)盤塊。1.直接地址10項(xiàng)（i.add(0)-i.add(9)），可以存放10個(gè)盤塊號，文件大小為10*4KB=40KB；2.一級索引地址是i.add(10)，存放1個(gè)索引表，1個(gè)索引表內(nèi)含1K個(gè)盤塊，文件大小為：1K*4KB=4MB3.二級索引地址是i.add(11)，文件大小為：1K*1K*4KB=4GB4.二級索引地址是i.add(12)，文件大小為：1K*1K*1K*4KB=4TB所以文件的最大長度為：40KB+4MB+4GB+4TB例13（2011年真題）：簡述在UNIX系統(tǒng)中采用混合索引方例14：多級索引分配方式允許文件最大長度兩級索引，盤塊大小1KB、盤塊號占4B，允許文件最大長度為多少？

解析：由已知得一個(gè)索引塊可含1KB/4B=256個(gè)盤塊號，于是兩級索引最多可含256*256=64K個(gè)盤塊號，允許文件最大長度為64K*1KB=64MB

例14：多級索引分配方式允許文件最大長度兩級索引，盤塊大小1例15：已知某系統(tǒng)中磁盤的每個(gè)盤塊大小為1KB，外存分配方法采用中的混合索引結(jié)構(gòu)，其中索引節(jié)點(diǎn)中直接地址6項(xiàng)，一級索引地址2項(xiàng)，二級索引地址1項(xiàng)，每個(gè)盤塊號占用4個(gè)字節(jié)，請問該系統(tǒng)中允許的文件最大長度是多少？解析：由已知得每個(gè)盤塊大小1KB，每個(gè)盤塊號占4B，因此一個(gè)盤塊內(nèi)可以存放1KB/4B=256個(gè)盤塊。1.直接地址6項(xiàng)，可以存放6個(gè)盤塊號，文件大小為6*1KB=6KB；2.一級索引地址2項(xiàng)，每個(gè)存放1個(gè)索引表，1個(gè)索引表內(nèi)含256個(gè)盤塊，文件大小為：256*1KB*2=512KB3.二級索引地址1項(xiàng)，文件大小為：256*256*1KB=64MB所以文件的最大長度為：6KB+512KB+64MB例15：已知某系統(tǒng)中磁盤的每個(gè)盤塊大小為1KB，外存分配方法計(jì)算題類型8：計(jì)算FAT的大小例16：有一個(gè)大小為500M的硬盤，盤塊的大小為1KB,試計(jì)算其FAT的大小。計(jì)算步驟：1.求FAT中的表項(xiàng)數(shù)：

磁盤大小/盤塊大小2.求FAT中每個(gè)表項(xiàng)所占存儲空間(是半個(gè)字節(jié)的整數(shù)倍)3.求FAT的大小FAT所占存儲空間=FAT中的表項(xiàng)數(shù)*每個(gè)表項(xiàng)所占存儲空間1.求FAT中的表項(xiàng)數(shù)：500MB/1KB=500K2.求FAT中每個(gè)表項(xiàng)所占存儲空間256K<500K<=512K

所以每個(gè)表項(xiàng)所占19位，擴(kuò)展為20位，即2.5B3.求FAT的大小=500K*2.5B=1250KB計(jì)算題類型8：計(jì)算FAT的大小例16：有一個(gè)大小為500M的例17：假定盤塊的大小為1KB，硬盤的大小為10GB，采用顯示鏈接分配方式時(shí)，請問文件分配表只是占用多大空間？例17：假定盤塊的大小為1KB，硬盤的大小為10GB，采用顯計(jì)算題類型9：查找與磁盤啟動次數(shù)例18：假定每次啟動磁盤只裝入一個(gè)目錄盤塊

盤塊大小1KB，文件目錄共3200個(gè)FCB

引入索引結(jié)點(diǎn)前

FCB占64B，查找一個(gè)文件平均需啟動磁盤次數(shù)為多少？引入索引結(jié)點(diǎn)后

FCB占16B(文件名和索引結(jié)點(diǎn)指針分別占用14B和2B)，查找一個(gè)文件平均需啟動磁盤次數(shù)為多少？解析：1.由已知得每盤塊中包含1KB/64B=16個(gè)FCB，文件目錄共需占用3200/16=200個(gè)盤塊，故查找一個(gè)文件平均需啟動磁盤100.5次(順序查找).2.引入索引結(jié)點(diǎn)后

，每盤塊包含1KB/16B=64個(gè)目錄項(xiàng)，文件目錄共需占用3200/64=50個(gè)盤塊，故查找一個(gè)文件平均需啟動磁盤25.5次(順序查找，讀索引結(jié)點(diǎn)取地址信息只需一次，因?yàn)樗饕Y(jié)點(diǎn)在外存上是連續(xù)存放的)計(jì)算題類型9：查找與磁盤啟動次數(shù)例18：假定每次啟動磁盤只裝計(jì)算題類型10：位示圖中盤塊的分配和回收教材276頁第14題

012345678910111213141501111111111111111111111111111111112110111111111111131111110111101111400000000000000005

6

例19：有一計(jì)算機(jī)系統(tǒng)采用如下圖所示的位示圖（行號、列號都從0開始編號）來管理空閑盤塊。如果盤塊從0開始編號，每個(gè)盤塊的大小為1KB。1.現(xiàn)要為文件分配兩個(gè)盤塊，試具體說明分配過程。2.若要釋放磁盤的第300塊，應(yīng)如何處理？計(jì)算題類型10：位示圖中盤塊的分配和回收教材276頁第14題

解析：

1.盤塊的分配過程

根據(jù)位示圖進(jìn)行盤塊分配時(shí)，可分三步進(jìn)行：

(1)順序掃描位示圖，從中找出兩個(gè)值為“0”的二進(jìn)制位分別為map[2,2]和map[3,6]。

(2)將所找到的兩個(gè)二進(jìn)制位轉(zhuǎn)換成與之相應(yīng)的盤塊號。其相應(yīng)的盤塊號應(yīng)按下式計(jì)算：

b?=16*i?+?j

map[2,2]對應(yīng)的盤塊號為：34

map[3,6]對應(yīng)的盤塊號為：54

(3)修改位示圖，令map[2,2]

=

1，map[3,6]?=?1。

解析：

1.盤塊的分配過程

根據(jù)位示圖進(jìn)行盤

2.盤塊回收的過程

盤塊的回收分兩步：

(1)將回收盤塊的盤塊號300轉(zhuǎn)換成位示圖中的行號和列號。轉(zhuǎn)換公式為：

i

=

b

DIV

16

j

=

b

MOD16

所以300號盤塊對應(yīng)的行號和列號分別是18和12。

(2)修改位示圖。令map[18,12]=?0。2.盤塊回收的過程

盤塊的回收分兩步：

(1)操作系統(tǒng)專升本復(fù)習(xí)----計(jì)算題操作系統(tǒng)專升本復(fù)習(xí)----計(jì)算題計(jì)算題類型1：作業(yè)調(diào)度、進(jìn)程調(diào)度算法根據(jù)先來先服務(wù)、短作業(yè)優(yōu)先、優(yōu)先級、高響應(yīng)比優(yōu)先、輪轉(zhuǎn)（RR）等調(diào)度算法求作業(yè)的執(zhí)行順序、作業(yè)的周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。2008年（8分）：短作業(yè)優(yōu)先、先來先服務(wù)調(diào)度算法2014年（7分）：短作業(yè)優(yōu)先調(diào)度算法2015年（8分）：先來先服務(wù)、短作業(yè)優(yōu)先調(diào)度算法2017年（10分）：先來先服務(wù)調(diào)度算法、搶占式優(yōu)先級調(diào)度算法；計(jì)算題類型1：作業(yè)調(diào)度、進(jìn)程調(diào)度算法根據(jù)先來先服務(wù)、短作業(yè)優(yōu)例1：在單機(jī)系統(tǒng)中，系統(tǒng)中各個(gè)進(jìn)程到達(dá)就緒隊(duì)列的時(shí)刻、執(zhí)行時(shí)間和優(yōu)先級（越小者越高）如下表所示。假設(shè)進(jìn)程的調(diào)度時(shí)間忽略不計(jì)。1、請給出采用FCFS、短作業(yè)優(yōu)先調(diào)度算法時(shí)各個(gè)進(jìn)程的調(diào)度順序，并計(jì)算平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。2、請計(jì)算采用搶占式優(yōu)先級調(diào)度算法時(shí)各個(gè)進(jìn)程的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。進(jìn)程到達(dá)時(shí)間執(zhí)行時(shí)間(ms)優(yōu)先級P1033P2265P3441P4652P5824例1：在單機(jī)系統(tǒng)中，系統(tǒng)中各個(gè)進(jìn)程到達(dá)就緒隊(duì)列的時(shí)刻、執(zhí)行時(shí)平均周轉(zhuǎn)時(shí)間：（3+7+9+12+12）/5=8.6平均帶權(quán)周轉(zhuǎn)時(shí)間：（1+1.17+2.25+2.4+6）/5=2.56進(jìn)程到達(dá)時(shí)間執(zhí)行時(shí)間(ms)優(yōu)先級完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P1033P2265P3441P4652P582431318209379121211.172.252.461、FCFS調(diào)度算法平均周轉(zhuǎn)時(shí)間：（3+7+9+12+12）/5=8.6進(jìn)程到達(dá)平均周轉(zhuǎn)時(shí)間：（3+7+3+11+14）/5=7.6平均帶權(quán)周轉(zhuǎn)時(shí)間：（1+1.17+2.25+2.4+6）/5=1.84進(jìn)程到達(dá)時(shí)間執(zhí)行時(shí)間(ms)優(yōu)先級完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P1033P2265P5824P3441P465231115209373111411.171.52.752.8短作業(yè)優(yōu)先調(diào)度算法平均周轉(zhuǎn)時(shí)間：（3+7+3+11+14）/5=7.6進(jìn)程到達(dá)平均周轉(zhuǎn)時(shí)間：（3+18+4+7+7）/5=7.8平均帶權(quán)周轉(zhuǎn)時(shí)間：（1+3+1+1.4+3.5）/5=1.98進(jìn)程到達(dá)時(shí)間執(zhí)行時(shí)間(ms)優(yōu)先級完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P1033P2265P3441P4652P5824381315203184771311.43.52、采用搶占式優(yōu)先級調(diào)度算法平均周轉(zhuǎn)時(shí)間：（3+18+4+7+7）/5=7.8進(jìn)程到達(dá)時(shí)作業(yè)進(jìn)入系統(tǒng)時(shí)間計(jì)算時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間19:0060分鐘9:0010:00⑴29:1045分鐘⑵⑶⑷39:1525分鐘⑸⑹⑺例2：在一個(gè)單道批處理系統(tǒng)中，采用響應(yīng)比高者優(yōu)先的作業(yè)調(diào)度算法。當(dāng)一個(gè)作業(yè)進(jìn)入系統(tǒng)后就可以開始調(diào)度，假定作業(yè)都是僅計(jì)算，忽略調(diào)度花費(fèi)的時(shí)間?，F(xiàn)有三個(gè)作業(yè)，進(jìn)入系統(tǒng)的時(shí)間和需要計(jì)算的時(shí)間如下表所示。求出每個(gè)作業(yè)的開始時(shí)間、完成時(shí)間及周轉(zhuǎn)時(shí)間并填入表中。作業(yè)進(jìn)入系統(tǒng)時(shí)間計(jì)算時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間19:006作業(yè)進(jìn)入系統(tǒng)時(shí)間計(jì)算時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間（分鐘）19:0060分鐘9:0010:00⑴29:1045分鐘⑵⑶⑷39:1525分鐘⑸⑹⑺60響應(yīng)比=（服務(wù)時(shí)間+等待時(shí)間）/服務(wù)時(shí)間=1+等待時(shí)間/服務(wù)時(shí)間10:00計(jì)算作業(yè)2、3的響應(yīng)比，如下：作業(yè)2響應(yīng)比：1+50/45=2.11作業(yè)3響應(yīng)比：1+45/25=2.8作業(yè)3的響應(yīng)比高，因此10:00開始執(zhí)行作業(yè)3，10:25完成。最后執(zhí)行作業(yè)2。10:0010:257010:2511:10120作業(yè)進(jìn)入系統(tǒng)時(shí)間計(jì)算時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間19:006計(jì)算題類型2：銀行家算法如果判斷某時(shí)刻是否為安全狀態(tài)采用安全性算法（若安全，執(zhí)行安全性算法結(jié)束寫明安全序列和系統(tǒng)狀態(tài)是安全的）；如果某進(jìn)程提出資源請求采用銀行家算法（寫清1、2、3、4步）。2008年（8分）、2011年、2012年、2013年計(jì)算題類型2：銀行家算法如果判斷某時(shí)刻是否為安全狀態(tài)采用安全進(jìn)程最大需求已分配

AB

AB

P1

32

11P2

64

40P3

31

212013年真題例3：已知系統(tǒng)內(nèi)有三個(gè)進(jìn)程P1、P2、P3共享A、B兩類資源，A類資源的數(shù)量為8，B類資源的數(shù)量為5。設(shè)在T時(shí)刻資源分配情況如下表所示:（1）問T時(shí)刻A、B的可利用資源數(shù)分別是多少?（2）T時(shí)刻系統(tǒng)是否處于安全狀態(tài)?為什么?

計(jì)算題類型3：地址變換1.動態(tài)可重定位分區(qū)分配的地址變換2.分頁存儲管理方式的地址變換3.分段存儲管理方式的地址變換2012年（選擇題1分）、2016年（10分）例4：（2012年真題）一個(gè)32位的虛擬地址分為4個(gè)域，每個(gè)域的長度分別為a、b、c、d位，其中d為頁內(nèi)地址，則系統(tǒng)最多可有（B）個(gè)虛擬頁面。A.a+b+cB.2a+b+cC.dD.2d計(jì)算題類型3：地址變換1.動態(tài)可重定位分區(qū)分配的地址變換1.動態(tài)可重定位分區(qū)分配的地址變換例5：在分區(qū)存儲管理中，已知某作業(yè)空間如圖所示，采用動態(tài)重定位進(jìn)行地址映射。假設(shè)分給該作業(yè)的主存空間起始地址為4000。

（1）指出在圖中的地址1和地址2中，哪個(gè)是邏輯地址，哪個(gè)是物理地址？（2）在圖中填寫出執(zhí)行指令MOVL1，[2000]時(shí)，所取數(shù)據(jù)“100”的邏輯地址、物理地址以及動態(tài)重定位寄存器的內(nèi)容（用十進(jìn)制表示）。（3）在圖中填寫出指令“MOVL1，[2000]”的主存地址。+動態(tài)重定位寄存器

0MOVL1[2000]100作業(yè)空間500200049990MOVL1[2000]100內(nèi)存空間4000

9999地址1地址2

1.動態(tài)可重定位分區(qū)分配的地址變換例5：在分區(qū)存儲管理中，例6：在一分頁存儲管理系統(tǒng)中，邏輯地址長度為16位，頁面大小為4096字節(jié)，現(xiàn)有一邏輯地址為2F6AH，且第0、1、2頁依次存放在物理塊5、10、11中，問相應(yīng)的物理地址為多少？2.分頁存儲管理方式的地址變換解析：方法1邏輯地址2F6AH的二進(jìn)制：0010111101101010由于邏輯地址長度為16位，頁面大小為4096字節(jié)，即212，所以低12為表示頁內(nèi)地址所以頁號為2，對應(yīng)塊號為11（二進(jìn)制1011），因?yàn)閴K內(nèi)地址=頁內(nèi)地址，所以物理地址表示如下：其二進(jìn)制1011111101101010，即BF6AH0010111101101010頁號頁內(nèi)地址1011111101101010塊號塊內(nèi)地址例6：在一分頁存儲管理系統(tǒng)中，邏輯地址長度為16位，頁面大小例6：在一分頁存儲管理系統(tǒng)中，邏輯地址長度為16位，頁面大小為4096字節(jié)，現(xiàn)有一邏輯地址為2F6AH，且第0、1、2頁依次存放在物理塊5、10、11中，問相應(yīng)的物理地址為多少？解析：方法2由于邏輯地址長度為16位，頁面大小為4096字節(jié)，即212，所以低12為表示頁內(nèi)地址所以頁號為2，對應(yīng)塊號為11（十六進(jìn)制B），因?yàn)閴K內(nèi)地址=頁內(nèi)地址，所以物理地址表示如下：所以，物理地址為BF6AH2F6A頁號頁內(nèi)地址BF6A塊號塊內(nèi)地址例6：在一分頁存儲管理系統(tǒng)中，邏輯地址長度為16位，頁面大小例7：某虛擬存儲器的用戶空間共有32個(gè)頁面，每頁1KB，內(nèi)存16KB。假定某時(shí)刻系統(tǒng)為用戶的第0、1、2、3頁分別分配的物理塊號為5、10、4、7，給定虛擬地址093CH，請將其變換為物埋地址。邏輯地址093CH的二進(jìn)制：0000100100111100有已知得邏輯地址長度為15位，頁面大小為1KB，即210，所以低10為表示頁內(nèi)地址所以頁號為2，對應(yīng)塊號為4（二進(jìn)制0100），因?yàn)閴K內(nèi)地址=頁內(nèi)地址，所以物理地址表示如下：其二進(jìn)制0001000100111100，即113CH0000100100111100頁號頁內(nèi)地址0001000100111100塊號塊內(nèi)地址解析：例7：某虛擬存儲器的用戶空間共有32個(gè)頁面，每頁1KB，內(nèi)存段號內(nèi)存起始地址段長02105001235020210090313505904193895段號段內(nèi)位移043011025003400例8：在一個(gè)段式存儲管理系統(tǒng)中，其段表為：試求下列邏輯地址對應(yīng)的物理地址是什么？3.分段存儲管理方式的地址變換物理地址210+430=6402350+10=2360段內(nèi)地址越界1350+400=1750解析：段號內(nèi)存起始地址段長02105001235020210090計(jì)算題類型4：分頁存儲的數(shù)據(jù)訪問時(shí)間例9：假定快表檢索時(shí)間為20ns，內(nèi)存訪問時(shí)間為100ns。1.若能在快表中找到CPU給出的頁號，CPU存取一個(gè)數(shù)據(jù)將需要的訪問時(shí)間是多少？2.若不能在快表中找到CPU給出的頁號，則為存取一個(gè)數(shù)據(jù)需要的訪問時(shí)間是多少？3.若假定快表查找命中率為80%，則其有效訪問時(shí)間為多少？解析：1.則若能在快表中找到CPU給出的頁號，CPU存取一個(gè)數(shù)據(jù)將需要(20+100)=120ns。2.若不能在快表中找到CPU給出的頁號，則為存取一個(gè)數(shù)據(jù)將需要(20+100+100)=220ns。3.若假定快表查找命中率為80%，則其有效訪問時(shí)間為120*80%+220*(1-80%)=140ns。計(jì)算題類型4：分頁存儲的數(shù)據(jù)訪問時(shí)間例9：假定快表檢索時(shí)間為計(jì)算題類型5：頁面置換算法根據(jù)最佳、先進(jìn)先出、最近最久未使用頁面置換算法計(jì)算缺頁次數(shù)和缺頁率。2012年、2014年（LRU(最近最久未使用)頁面置換算法）例10（2012年真題）：在請求分頁系統(tǒng)中，一個(gè)進(jìn)程初始執(zhí)行連續(xù)訪問頁面的次序?yàn)椋?、2、1、3、0、2、4、0、2、1、3、4，利用FIFO頁面淘汰算法，進(jìn)程內(nèi)存只能保存3個(gè)頁面，共發(fā)生的缺頁次數(shù)為（B）。A.8B.9C.7D.10計(jì)算題類型5：頁面置換算法根據(jù)最佳、先進(jìn)先出、最近最久未使用例11：假定分頁虛擬存儲系統(tǒng)中，某進(jìn)程的頁面訪問蹤跡為：4，3，2，1，4，3，5，4，3，2，1，5，分配給它的內(nèi)存物理塊數(shù)為3。1.按最佳頁面置換算法，計(jì)算缺頁率。2.按先進(jìn)先出頁面置換算法，計(jì)算缺頁率。3.按LRU頁面置換算法，計(jì)算缺頁率。例11：假定分頁虛擬存儲系統(tǒng)中，某進(jìn)程的頁面訪問蹤跡為：4，計(jì)算題類型6：磁盤調(diào)度算法根據(jù)先來先服務(wù)、最短尋道時(shí)間優(yōu)先、掃描算法、循環(huán)掃描算法，給出尋道順序，并計(jì)算尋道總數(shù)和平均尋道長度。2008年（8分）：最短尋道時(shí)間優(yōu)先、掃描算法計(jì)算題類型6：磁盤調(diào)度算法根據(jù)先來先服務(wù)、最短尋道時(shí)間優(yōu)先、例12：一個(gè)可移動磁頭的磁盤具有200個(gè)磁道，其編號為0--199，當(dāng)它剛剛結(jié)束了125道的存取后，現(xiàn)正在處理143道的請求，假設(shè)系統(tǒng)當(dāng)前I/0請求序列以FIFO順序排列如下：86，147，91，177，94，150，102，175，130。試問對以下幾種磁盤調(diào)度算法而言，滿足以上請求序列，磁頭將如何移動？平均尋道長度是多少？1.先來先服務(wù)算法2.最短尋道時(shí)間優(yōu)先算法SSTF3.掃描算法SCAN4.循環(huán)掃描算法例12：一個(gè)可移動磁頭的磁盤具有200個(gè)磁道，其編號為0--先來先服務(wù)算法FCFS從143號磁道開始被訪問的下一個(gè)磁道號移動距離（磁道數(shù)）865714761915617786948315056102481757313045平均尋道長度：565/9=最短尋道時(shí)間優(yōu)先算法SSTF從143號磁道開始被訪問的下一個(gè)磁道號移動距離（磁道數(shù)）147415031302010228948913865175891772平均尋道長度：162/9=先來先服務(wù)算法FCFS從143號磁道開始被訪問的下一個(gè)磁道號掃描算法SCAN從143號磁道開始被訪問的下一個(gè)磁道號移動距離（磁道數(shù)）147415031752517721304710228948913865平均尋道長度：125/9=循環(huán)掃描算法CSCAN從143號磁道開始被訪問的下一個(gè)磁道號移動距離（磁道數(shù)）147415031752517728691915943102813028平均尋道長度：169/9=掃描算法SCAN從143號磁道開始被訪問的下一個(gè)磁道號移動距計(jì)算題類型7：索引分配與文件最大長度計(jì)算索引文件最大長度、計(jì)算增量式文件最大長度。2011年例13（2011年真題）：簡述在UNIX系統(tǒng)中采用混合索引方式。

如果每個(gè)盤塊大小是4KB，每個(gè)盤的地址要用4個(gè)字節(jié)，那么在UNIX系統(tǒng)中文件最大是多少？給出步驟說明。計(jì)算題類型7：索引分配與文件最大長度計(jì)算索引文件最大長度、計(jì)例13（2011年真題）：簡述在UNIX系統(tǒng)中采用混合索引方式。

如果每個(gè)盤塊大小是4KB，每個(gè)盤的地址要用4個(gè)字節(jié)，那么在UNIX系統(tǒng)中文件最大是多少？給出步驟說明。解析：由已知得每個(gè)盤塊大小4KB，每個(gè)盤塊號占4B，因此一個(gè)盤塊內(nèi)可以存放4KB/4B=1K個(gè)盤塊。1.直接地址10項(xiàng)（i.add(0)-i.add(9)），可以存放10個(gè)盤塊號，文件大小為10*4KB=40KB；2.一級索引地址是i.add(10)，存放1個(gè)索引表，1個(gè)索引表內(nèi)含1K個(gè)盤塊，文件大小為：1K*4KB=4MB3.二級索引地址是i.add(11)，文件大小為：1K*1K*4KB=4GB4.二級索引地址是i.add(12)，文件大小為：1K*1K*1K*4KB=4TB所以文件的最大長度為：40KB+4MB+4GB+4TB例13（2011年真題）：簡述在UNIX系統(tǒng)中采用混合索引方例14：多級索引分配方式允許文件最大長度兩級索引，盤塊大小1KB、盤塊號占4B，允許文件最大長度為多少？

解析：由已知得一個(gè)索引塊可含1KB/4B=256個(gè)盤塊號，于是兩級索引最多可含256*256=64K個(gè)盤塊號，允許文件最大長度為64K*1KB=64MB

例14：多級索引分配方式允許文件最大長度兩級索引，盤塊大小1例15：已知某系統(tǒng)中磁盤的每個(gè)盤塊大小為1KB，外存分配方法采用中的混合索引結(jié)構(gòu)，其中索引節(jié)點(diǎn)中直接地址6項(xiàng)，一級索引地址2項(xiàng)，二級索引地址1項(xiàng)，每個(gè)盤塊號占用4個(gè)字節(jié)，請問該系統(tǒng)中允許的文件最大長度是多少？解析：由已知得每個(gè)盤塊大小1KB，每個(gè)盤塊號占4B，因此一個(gè)盤塊內(nèi)可以存放1KB/4B=256個(gè)盤塊。1.直接地址6項(xiàng)，可以存放6個(gè)盤塊號，文件大小為6*1KB=6KB；2.一級索引地址2項(xiàng)，每個(gè)存放1個(gè)索引表，1個(gè)索引表內(nèi)含256個(gè)盤塊，文件大小為：256*1KB*2=512KB3.二級索引地址1項(xiàng)，文件大小為：256*256*1KB=64MB所以文件的最大長度為：6KB+512KB+64MB例15：已知某系統(tǒng)中磁盤的每個(gè)盤塊大小為1KB，外存分配方法計(jì)算題類型8：計(jì)算FAT的大小例16：有一個(gè)