操作系統(tǒng)計(jì)算題

1、操作系統(tǒng)計(jì)算題w=2148 mod 1024=100查頁(yè)表第2 頁(yè)在第 1 塊，所以物理地址為1124。對(duì)于邏輯地址 3000p=int(3000/1024)=2w=3000 mod 1024=928查頁(yè)表第 2 頁(yè)在第 1 塊, 所以物理地址為1796。對(duì)于邏輯地址 4000p=int(4000/1024)=3w=4000mod 1024=928查頁(yè)表第3 頁(yè)在第6 塊, 所以物理地址為7072。對(duì)于邏輯地址 5012p=int(5012/1024)=4w=5012mod1024=916因頁(yè)號(hào)超過頁(yè)表長(zhǎng)度，該邏輯地址非法。例 2：在一分頁(yè)存儲(chǔ)管理系統(tǒng)中 ,邏輯地址長(zhǎng)度為 16 位,頁(yè)面大小為

2、 4096 字節(jié),現(xiàn)有一邏輯地址為 2F6AH, 且第 0, 1, 2頁(yè)依次存放在物理塊 5, 10 ,11中,問相應(yīng)的物理地址為多少 ?解:由題目所給給條件可知 ,本頁(yè)式系統(tǒng)的邏輯地址結(jié)構(gòu)為 :邏輯地址 2F6AH 的二進(jìn)制表示如下 :由此可知邏輯地址 2F6AH 的頁(yè)號(hào)為 2,該頁(yè)存放在第 11 號(hào)物理塊中 ,用十六進(jìn)制表示志號(hào)為 B, 所以物理地址為 BF6AH. 一、 求文件最大長(zhǎng)度例：設(shè)文件索引節(jié)點(diǎn)中有 7 個(gè)地址項(xiàng)，其中 4 個(gè)地址項(xiàng)為直接地址索引， 2 個(gè)地址項(xiàng)是一級(jí)間接地址索引，1 個(gè)地址項(xiàng)是二級(jí)間接地址索引，每個(gè)地址項(xiàng)大小為 4 字節(jié)，若磁盤索引塊和盤塊大小均為256 字節(jié)，

3、則可表示的單個(gè)文件的最大長(zhǎng)度是多少？解答：本題的文件結(jié)構(gòu)屬混合索引分配方式。每個(gè)地址項(xiàng)大小為 4 字節(jié)，索引塊和盤塊大小為 256 字節(jié)，每個(gè)索引塊中的項(xiàng)目數(shù)=256B/4B=64 個(gè)。4 個(gè)地址項(xiàng)為直接地址索引，對(duì)應(yīng)的文件大小為 4×256B=1KB。2 個(gè)地址項(xiàng)是一級(jí)間接地址索引，對(duì)應(yīng)的文件大小是2×64×256B=32KB，一個(gè)地址項(xiàng)是二級(jí)間接地址索引，對(duì)應(yīng)的文件大小為 1×64× 64×256B=1024KB。所以單個(gè)文件的最大長(zhǎng)度=1KB+32KB+1024KB=1057KB 。二、 磁盤調(diào)度算法：1.先來(lái)先服務(wù) FCFS2

4、.最短尋道時(shí)間優(yōu)先SSTF3.SCAN 算法4.循環(huán)掃描(CSCAN)算法例：假設(shè)一個(gè)活動(dòng)頭磁盤有 200 道, 編號(hào)從 0-199. 當(dāng)前磁頭正在 143 道上服務(wù) , 并且剛剛完成了 125 道的請(qǐng)求 . 現(xiàn)有如下訪盤請(qǐng)求序列(磁道號(hào) ):86, 147, 91, 177, 94, 150, 102, 175,130試給出采用下列算法后磁頭移動(dòng)的順序和移動(dòng)總量 (總磁道數(shù) ).(1). 先來(lái)先服務(wù) (FCFS) 磁盤調(diào)度算法 .(2). 最短尋道時(shí)間優(yōu)先(SSTF) 磁盤調(diào)度算法 .(3). 掃描法 (SCAN) 磁盤調(diào)度算法 .(假設(shè)沿磁頭移動(dòng)方向不再有訪問請(qǐng)求時(shí) , 磁頭沿相反方向移動(dòng)

5、 .)答案：三、（1）86，147，91，177，94，150，102，175，130（2）當(dāng)前磁頭在 143 道上：147，150，130，102，94，91，86，175，177（ 3）當(dāng)前磁頭在 143 道上，并且剛剛完成 125 道的請(qǐng)求147，150，175，177，130，102，94，91，86三、 調(diào)度算法（求周轉(zhuǎn)時(shí)間，加權(quán)周轉(zhuǎn)時(shí)間）1先來(lái)先服務(wù)調(diào)度算法FCFS：該算法按照進(jìn)程進(jìn)入就緒隊(duì)列的先后順序選擇最先進(jìn)入該隊(duì)列的進(jìn)程，把處理機(jī)分配給它，使之投入運(yùn)行。例2優(yōu)先級(jí)調(diào)度算法：總是選擇具有 最高優(yōu)先級(jí)的進(jìn)程首先使用處理機(jī)。在這種算法中，首先考慮的問題是如何確定進(jìn)程的優(yōu)先數(shù)。 分為

6、：靜態(tài)優(yōu)先權(quán)：在創(chuàng)建進(jìn)程的時(shí)候便確定的，且在進(jìn)程的運(yùn)行期間保持不變。 （簡(jiǎn)單 易行，系統(tǒng)開銷小，但不夠精確， 很可能出現(xiàn)優(yōu)先權(quán)低的作業(yè)（進(jìn)程）長(zhǎng)期不被調(diào) 度的情況。所以，只在要求不太高的系統(tǒng)中， 才使用靜態(tài)優(yōu)先數(shù)（權(quán)）動(dòng)態(tài)優(yōu)先權(quán)：在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，可以隨進(jìn)程的推進(jìn)而改變，以便獲得更好的調(diào)度性能例：3.最短作業(yè) /進(jìn)程優(yōu)先法（ SJF/SPF）：SJF:從后備隊(duì)列中選擇估計(jì)運(yùn)行時(shí)間最短的作業(yè)，先調(diào)入內(nèi)存運(yùn)行。SPF:從就緒隊(duì)列中選擇估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，先將處理機(jī)分配給它，使它立即執(zhí)行。4.最高響應(yīng)比作業(yè)優(yōu)先算法（ HRN ）：是對(duì) FCFS 方式和 SJF 方式的一種綜合平衡響應(yīng)比

7、。 R(作業(yè)等待時(shí)間需運(yùn)行時(shí)間 )/ 需運(yùn)行時(shí)間 1已等待時(shí)間 / 需運(yùn)行時(shí)間 1W/T例：六：頁(yè)面置換算法先進(jìn)先出頁(yè)面淘汰算法（FIFO ）選擇在內(nèi)存中駐留時(shí)間最長(zhǎng)的頁(yè)并淘汰之理想淘汰算法 最佳頁(yè)面算法（ OPT ）淘汰以后不再需要的或最遠(yuǎn)的將來(lái)才會(huì)用到的頁(yè)面最近最久未使用頁(yè)面淘汰算法（ LRU ）選擇最后一次訪問時(shí)間距離當(dāng)前時(shí)間最長(zhǎng)的一頁(yè)并淘汰之即淘汰沒有使用的時(shí)間最長(zhǎng)的頁(yè)1 已知頁(yè)面走向?yàn)?、2、1、3、1、2、4、2、1、 3、4，且開始執(zhí)行時(shí)主存中沒有頁(yè)面。若只給該作業(yè)分配 2 個(gè)物理塊，當(dāng)采用 FIFO 頁(yè)面淘汰算法時(shí)缺頁(yè)率為多少？假定現(xiàn)有一種淘汰算法，該算法淘汰頁(yè)面的策略為當(dāng)需要

8、淘汰頁(yè)面時(shí)，就把剛使用過的頁(yè)面作為淘汰對(duì)象，試問就相同的頁(yè)面走向，缺頁(yè)率又為多少？分析及相關(guān)知識(shí) 在進(jìn)行內(nèi)存訪問時(shí)，若所訪問的頁(yè)已在主存， 則稱此次訪問成功； 若所訪問的頁(yè)不在主存， 則稱此次訪問失敗， 并產(chǎn)生缺頁(yè)中斷。若程序 P 在運(yùn)行過程中訪問頁(yè)面的總次數(shù)為 S,其中產(chǎn)生缺頁(yè)中斷的訪問次數(shù)為 F,則其缺頁(yè)率為： F/s.解：根據(jù)所給頁(yè)面走向，采用 FIFO 淘汰算法的頁(yè)面置換情況如下：頁(yè)面走向12131242134物理塊 1113322114物理塊 222114433缺頁(yè)缺缺缺缺缺缺缺缺缺從上述頁(yè)面置換圖可以看出： 頁(yè)面引用次數(shù)為 11 次，缺頁(yè)次數(shù)為 9 次，所以缺頁(yè)率為 9/11。若采

9、用后一種頁(yè)面淘汰策略， 其頁(yè)面置換情況如下：頁(yè)面走向12131242134物理塊 111311134物理塊 22224222缺頁(yè)缺缺缺缺缺缺缺缺在一個(gè)請(qǐng)求分頁(yè)存儲(chǔ)管理系統(tǒng)中， 一個(gè)作業(yè)的頁(yè)面走向?yàn)?4，3，2，1，4，3，5， 4，3，2，1，5，當(dāng)分配給該作業(yè)的物理塊數(shù)分別為 3，4 時(shí)，試計(jì)算采用下述頁(yè)面淘汰算法時(shí)的缺頁(yè)率 （假設(shè)開始執(zhí)行時(shí)主存中沒有頁(yè)面） ，并比較所得結(jié)果。（1）最佳置換淘汰算法（2）先進(jìn)先出淘汰算法（3）最近最久未使用淘汰算法解：（ 1）根據(jù)所給頁(yè)面走向，使用最佳頁(yè)面淘汰 算法時(shí)，頁(yè)面置換情況如下：走向432143543215塊 14444422塊 2333331塊 3

10、21555缺頁(yè)缺缺缺 缺缺缺缺缺頁(yè)率為： 7/12走向432143543215塊 1444441塊 233333塊 32222塊 4155缺頁(yè)缺缺缺 缺缺缺缺缺頁(yè)率為： 6/12由上述結(jié)果可以看出， 增加分配 給作業(yè) 的內(nèi)存塊數(shù)可以降低缺頁(yè)率（ 2）根據(jù)所給頁(yè)面走向， 使用最佳頁(yè)面淘汰 算法時(shí)，頁(yè)面置換情況如下：走向432143543215塊 1444111555塊 233344432塊 32223321缺頁(yè)缺缺缺 缺缺缺缺缺頁(yè)率為： 9/12走向432143543215塊 2333344445塊 322223333塊 41111222缺頁(yè)缺缺缺 缺缺缺缺缺頁(yè)率為： 10/12由上述結(jié)果可以看出， 對(duì)先進(jìn)先出算法而言， 增加分配給作業(yè)的內(nèi)存塊數(shù)反而使缺頁(yè)率上升， 這種異常現(xiàn)象稱為 Belady 現(xiàn)象 。(3) 根據(jù)所給頁(yè)面走向，使用最佳頁(yè)面淘汰 算法時(shí)，頁(yè)面置換情況如下：走向432143543