《操作系統(tǒng)》習(xí)題課

1、計(jì)算題類型：1. 重定位地址計(jì)算：1) 給定邏輯地址，計(jì)算物理地址（分段或分頁，一級(jí)頁表或二級(jí)頁表）2) 給定邏輯地址LA，頁長度，計(jì)算邏輯地址的頁號(hào)和偏移3) 給定物理地址RA，頁幀長度，計(jì)算物理地址的頁幀號(hào)和偏移2. 有效內(nèi)存訪問時(shí)間計(jì)算：給定內(nèi)存訪問時(shí)間、快表訪問時(shí)間及快表命中率、調(diào)頁時(shí)間及缺頁率，計(jì)算有效內(nèi)存訪問時(shí)間3. 磁盤地址及容量計(jì)算：1) 給定一維的邏輯扇區(qū)編址A，柱面數(shù)C、磁頭數(shù)H、扇區(qū)數(shù)S，計(jì)算物理c、h、s2) 給定柱面數(shù)C、磁頭數(shù)H、扇區(qū)數(shù)S，計(jì)算磁盤容量4. 文件系統(tǒng)相關(guān)計(jì)算：1) 給定inode數(shù)據(jù)結(jié)構(gòu)，盤塊大小，地址長度，計(jì)算文件最大容量2) 給定卷的容量，簇大小

2、，F(xiàn)AT12/16/32分別需要多少個(gè)簇來存放FAT表3) 給定RAID5陣列的磁盤數(shù)量n，計(jì)算磁盤空間有效利用率5. 給定作業(yè)到達(dá)時(shí)刻、計(jì)算時(shí)間長度，調(diào)度策略，計(jì)算響應(yīng)時(shí)間、周轉(zhuǎn)時(shí)間例1：在某個(gè)采用分頁存儲(chǔ)管理的系統(tǒng)中，假定邏輯頁面和物理存儲(chǔ)塊的大小均為1KB，主存容量為10KB。某個(gè)用戶編寫的程序P共有4個(gè)頁面，被分別裝入到主存的第3、4、6、8存儲(chǔ)塊中。（1）寫出P對(duì)應(yīng)進(jìn)程的頁面映射表；（2）當(dāng)P在CPU運(yùn)行時(shí)，執(zhí)行了一條指令：MOV 2100，3100請(qǐng)計(jì)算指令中的兩個(gè)操作數(shù)的物理地址。解答：（1）由于頁大小為1KB，故頁內(nèi)地址為10bit長。頁表應(yīng)為：邏輯頁號(hào)物理塊號(hào)03142638

3、（2）先計(jì)算邏輯頁號(hào)及頁內(nèi)偏移量，再查頁表找到對(duì)應(yīng)物理塊號(hào)，最后計(jì)算物理地址：邏輯地址邏輯頁號(hào)頁內(nèi)偏移地址物理存儲(chǔ)塊號(hào)物理地址21002100/1024=22100-1024*2=5261024*6+52=619631003100/1024=33100-1024*3=2881024*8+28=8220例2：在請(qǐng)求分頁式存儲(chǔ)管理中，假設(shè)一次內(nèi)存訪問時(shí)間為100ns，一次快表(TLB)訪問時(shí)間為20ns，地址轉(zhuǎn)換計(jì)算時(shí)的快表命中率為80%，請(qǐng)計(jì)算平均有效內(nèi)存訪問時(shí)間為多少ns？若缺頁率為1，且每次缺頁中斷處理時(shí)間為20ms，請(qǐng)計(jì)算平均有效內(nèi)存訪問時(shí)間為多少ns？解答：如果快表命中（即頁號(hào)在快表中）

4、，則內(nèi)存訪問時(shí)間A1=20+100=120ns如果快表未命中，則內(nèi)存訪問時(shí)間A2=20+100+100=220ns【含一次訪問內(nèi)存中頁表】則平均有效內(nèi)存訪問時(shí)間A=A1×80%+A2×20%=120×0.8+220×0.2=140ns缺頁率p=1的含義是，每1000次內(nèi)存訪問中有1次需要調(diào)頁處理！因此，請(qǐng)求分頁式存儲(chǔ)管理過程中，平均有效內(nèi)存訪問時(shí)間： T = (1-p)×A+p×20(ms) =(1-0.001)×140 + 0.001×20000000(ns) =139.86+20000 =20139ns【注】1

5、s=1000ms=1000 000us=1000 000 000ns例3：假設(shè)一個(gè)磁盤共有2048個(gè)柱面，16個(gè)磁頭，每個(gè)磁道分為64個(gè)扇區(qū)，每個(gè)扇區(qū)容量為512字節(jié)，請(qǐng)計(jì)算該磁盤的總?cè)萘坑卸嗌貵B？假設(shè)磁盤的一個(gè)邏輯盤塊大小為2KB，則邏輯盤塊號(hào)513所對(duì)應(yīng)的首個(gè)扇區(qū)的三維物理地址（c，h，s）為多少？解答：（1）C=2048=2K個(gè)柱面（即每個(gè)盤面有2K個(gè)磁道） H=16個(gè)磁頭（即16個(gè)盤面） S=64個(gè)扇區(qū)/每個(gè)磁道 每個(gè)扇區(qū)的容量=512字節(jié)=0.5KB 則磁盤總?cè)萘?0.5KB×C×H×S = 0.5KB×2K×16×64

6、= 1GB（2）1個(gè)盤塊由2KB/0.5K=4個(gè)扇區(qū)構(gòu)成因此，513號(hào)盤塊的首塊扇區(qū)號(hào)A=4×513=2052s = A % S = 2052 % 64 = 4h = A / S % H = 2052 / 64 % 16 = 0c = A / (S×H) = 2052 / (64×16) = 2結(jié)果 =（2，0，4）例4-1：RAID5磁盤陣列共有8塊磁盤構(gòu)成，請(qǐng)計(jì)算磁盤空間有效利用率？解答： 磁盤空間有效利用率 = (n-1) / n = 7 / 8 = 87.5%例4-2：已知磁盤容量為256MB，簇大小為4KB，對(duì)FAT16格式的文件系統(tǒng)來說，文件分配表應(yīng)該

7、占用多大磁盤空間？（不考慮文件系統(tǒng)的空間開銷）解答： 整個(gè)磁盤邏輯盤塊（簇）個(gè)數(shù) = 256MB/4KB = 256×1024 / 4 = 64K個(gè) FAT16文件格式的文件分配表每項(xiàng)占用16bit即2B空間 因此，文件分配表占用空間 = 2B×64K = 128KB，即128KB/4KB=32個(gè)簇例4-3：MINIX文件系統(tǒng)1.0中，每個(gè)文件均有唯一的一個(gè)inode數(shù)據(jù)結(jié)構(gòu)，其中共有9個(gè)文件數(shù)據(jù)塊指針zone0.8，每個(gè)指針為short類型。前7個(gè)即zone0.6為直接數(shù)據(jù)塊指針，zone7為一級(jí)數(shù)據(jù)塊指針，zone8為二級(jí)數(shù)據(jù)塊指針。而每個(gè)數(shù)據(jù)塊大小為1KB。試計(jì)算該文

8、件系統(tǒng)能夠支持的最大文件是多大？解答：數(shù)據(jù)塊大小為1KB，而每個(gè)指針為short整型，占2B空間，因此1個(gè)數(shù)據(jù)塊可以有512個(gè)指針。 inode的直接數(shù)據(jù)塊有7個(gè)，即可以指出7KB的空間； inode的一級(jí)間接指針塊，共有512個(gè)指針，可以指出512×1KB = 0.5MB空間； inode的二級(jí)間接指針塊，共有512個(gè)指針，可以指出512個(gè)一級(jí)指針塊，共可以指出512×512個(gè)數(shù)據(jù)塊，即可以指出512×512×1KB = 0.25GB空間。 因此，MINIX文件系統(tǒng)1.0的單個(gè)文件最大容量為0.25GB+0.5MB+7KB例5：給定作業(yè)到達(dá)時(shí)刻、計(jì)算時(shí)

9、間長度，調(diào)度策略，計(jì)算響應(yīng)時(shí)間、周轉(zhuǎn)時(shí)間任務(wù)到達(dá)時(shí)刻(ms)CPU區(qū)間(ms)P1010P2029P353P457P53012采用SRFS(最少剩余時(shí)間作業(yè)優(yōu)先)調(diào)度策略調(diào)度執(zhí)行結(jié)果甘特圖：P1P3P15610813P420P2P230P542則響應(yīng)時(shí)間（提交到第1次執(zhí)行）： 周轉(zhuǎn)時(shí)間（提交到執(zhí)行完成）： 任務(wù)響應(yīng)時(shí)間(ms)周轉(zhuǎn)時(shí)間間(ms)P1013P22061P303P4815P5012平均5.620.8例6：在銀行家算法中，系統(tǒng)有5個(gè)進(jìn)程和3類資源。若出現(xiàn)以下資源分配情況：進(jìn)程資源最大需求已分配資源P07，5，30，1，0P13，2，22，1，0P29，0，23，0，2P32，2，22

10、，1，1P44，3，30，0，2目前系統(tǒng)中剩余資源數(shù)量為（3，2，2）。目前狀態(tài)是否為安全狀態(tài)？如果是安全狀態(tài)，給出一個(gè)安全序列，否則給出死鎖進(jìn)程集合。解答：各個(gè)進(jìn)程還需要的資源數(shù)量情況為：進(jìn)程已分配資源剩余資源請(qǐng)求P00，1，07，4，3P12，1，01，1，2P23，0，26，0，0P32，1，10，1，1P40，0，24，3，1剩余資源（3，2，2）分配給P1，則剩余資源（5，3，2）分配給P3，則剩余資源（5，3，3）P3，剩（7，4，3）P4，剩（5，3，4）P1，剩（7，4，3）P4，剩（5，3，5）P0P2P4P3P0P2P4P1P2P4P0P4P0P2P0P2P2P4P0P4P

11、0P2P0P2P4P2P4P0P2P0P2P0P4P2P4P0P2P0P2P0安全序列有14個(gè)：(1) P1、P3、P0、P2、P4(2) P1、P3、P0、P4、P2(3) P1、P3、P2、P0、P4(4) P1、P3、P2、P4、P0(5) P1、P3、P4、P0、P2(6) P1、P3、P4、P2、P0(7) P1、P4、P3、P0、P2(8) P1、P4、P3、P2、P0(9) P3、P1、P0、P2、P4(10) P3、P1、P0、P4、P2(11) P3、P1、P2、P0、P4(12) P3、P1、P2、P4、P0(13) P3、P1、P4、P0、P2(14) P3、P1、P4、

12、P2、P0(15) P3、P4、P1、P0、P2(16) P3、P4、P1、P2、P0調(diào)度策略：1. CPU調(diào)度（進(jìn)程調(diào)度）FCFS（先來先服務(wù)）、SJF（最短作業(yè)優(yōu)先）、SRJF（最短剩余時(shí)間作業(yè)優(yōu)先）、RR（時(shí)間片輪轉(zhuǎn)）四種方式的作業(yè)(任務(wù))調(diào)度執(zhí)行結(jié)果的甘特圖，并通過甘特圖計(jì)算響應(yīng)時(shí)間、周轉(zhuǎn)時(shí)間等2. 虛擬內(nèi)存的缺頁置換FIFO（先進(jìn)先出）；OPT(MIN)（最優(yōu)置換）；LRU（最近最少使用）；LRU的準(zhǔn)確實(shí)現(xiàn)算法（計(jì)數(shù)器算法、頁碼棧算法）；LRU的近似實(shí)現(xiàn)算法（CLOCK算法）針對(duì)各種具體置換策略或算法，計(jì)算缺頁數(shù)及缺頁率3. 磁盤調(diào)度FCFS（先來先服務(wù)）、SSTF（最短尋道時(shí)間優(yōu)先

13、）、SCAN（掃描/電梯法）、LOOK（查看掃描/電梯法）CSCAN（周期掃描法）CLOOK（周期查看掃描）六種調(diào)度策略的尋道移動(dòng)磁道數(shù)量計(jì)算進(jìn)程狀態(tài)變遷及條件三狀態(tài)、五狀態(tài)、七狀態(tài)算法：銀行家算法檢測(cè)死鎖 哲學(xué)家進(jìn)餐問題 信號(hào)量控制互斥、同步程序編寫簡答題例子：（1）解釋什么是并行和并發(fā)？答案：并行是指兩個(gè)或多個(gè)活動(dòng)在同一時(shí)刻同時(shí)執(zhí)行的情況； 并發(fā)是指系統(tǒng)中存在著若干個(gè)邏輯上相互獨(dú)立的程序或程序段，它們都已經(jīng)被啟動(dòng)執(zhí)行，在相對(duì)短的時(shí)間內(nèi)，它們交叉地在CPU上執(zhí)行的情況。給使用者一個(gè)并行的感覺。（2）進(jìn)程與程序之間的聯(lián)系與區(qū)別？答案：進(jìn)程是程序的一次執(zhí)行過程，沒有程序就沒有進(jìn)程； 程序是完成某個(gè)特定功能的一系列程序語句的集合，只要不被破壞，它就永遠(yuǎn)存在； 程序是一個(gè)靜態(tài)的概念，而進(jìn)程是一個(gè)動(dòng)態(tài)的概念，它由創(chuàng)建而產(chǎn)生，完成任務(wù)后因撤銷而消亡；進(jìn)程是系統(tǒng)進(jìn)行資源分配和調(diào)度的獨(dú)立單位，而程序不是。 選擇題例子：（1）如果分時(shí)系統(tǒng)的時(shí)間片一定，那么（ A ），則響應(yīng)時(shí)間越長。A 用戶數(shù)越多 B 用戶數(shù)越少 C 主存容量越大 D 主存容量越?。?）在分時(shí)系統(tǒng)中，當(dāng)用戶數(shù)為100時(shí)，為保證響應(yīng)時(shí)間不超過2s，系統(tǒng)設(shè)置的