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

1、計(jì)算題：一、 生產(chǎn)消費(fèi)者問(wèn)題為解決生產(chǎn)者消費(fèi)者問(wèn)題，應(yīng)該設(shè)兩個(gè)同步信號(hào)量，一個(gè)說(shuō)明空緩沖區(qū)的數(shù)目，用S1表示，初值為有界緩沖區(qū)的大小N，另一個(gè)說(shuō)明已用緩沖區(qū)的數(shù)目，用S2表示，初值為。由于在此問(wèn)題中有M個(gè)生產(chǎn)者和N個(gè)消費(fèi)者，它們?cè)趫?zhí)行生產(chǎn)活動(dòng)和消費(fèi)活動(dòng)中要對(duì)有界緩沖區(qū)進(jìn)行操作。由于有界緩沖區(qū)是一個(gè)臨界資源，必須互斥使用，所以，另外還需要設(shè)置一個(gè)互斥信號(hào)量mutex，其初值為。P：i = 0;while (1) 生產(chǎn)產(chǎn)品; P(S1); P(mutex); 往Buffer i放產(chǎn)品; i = (i+1) % n; V(mutex); V(S2); ;Q： j = 0; while (1) P(S

2、2); P(mutex); 從Bufferj取產(chǎn)品; j = (j+1) % n; V(mutex); V(S1); 消費(fèi)產(chǎn)品; ;二、 地址轉(zhuǎn)換例1：若在一分頁(yè)存儲(chǔ)管理系統(tǒng)中，某作業(yè)的頁(yè)表如下所示。已知頁(yè)面大小為1024字節(jié)，試將邏輯地址1011，2148，3000，4000，5012轉(zhuǎn)化為相應(yīng)的物理地址。頁(yè)號(hào) 塊號(hào)0 21 32 13 6解：本題中，為了描述方便，設(shè)頁(yè)號(hào)為P，頁(yè)內(nèi)位移為W，邏輯地址為A，頁(yè)面大小為L(zhǎng)，則： p=int(A/L)w=A mod L對(duì)于邏輯地址1011 p=int(1011/1024)=0 w=1011 mod 1024=1011查頁(yè)表第0頁(yè)在第二塊，所以物理地

3、址為3059。對(duì)于邏輯地址2148 p=int(2148/1024)=2 w=2148 mod 1024=100 查頁(yè)表第2頁(yè)在第1塊，所以物理地址為1124。對(duì)于邏輯地址3000 p=int(3000/1024)=2 w=3000 mod 1024=928 查頁(yè)表第2頁(yè)在第1塊, 所以物理地址為1796。對(duì)于邏輯地址4000 p=int(4000/1024)=3 w=4000mod 1024=928 查頁(yè)表第3頁(yè)在第6塊, 所以物理地址為7072。對(duì)于邏輯地址5012 p=int(5012/1024)=4 w=5012mod1024=916因頁(yè)號(hào)超過(guò)頁(yè)表長(zhǎng)度，該邏輯地址非法。例2：在一分頁(yè)存

4、儲(chǔ)管理系統(tǒng)中,邏輯地址長(zhǎng)度為16位,頁(yè)面大小為4096字節(jié),現(xiàn)有一邏輯地址為2F6AH,且第0, 1, 2頁(yè)依次存放在物理塊5, 10 ,11中,問(wèn)相應(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é)，若磁盤(pán)索引塊和盤(pán)塊大小均為256字節(jié)，則可表示的單個(gè)文件

5、的最大長(zhǎng)度是多少？解答：本題的文件結(jié)構(gòu)屬混合索引分配方式。每個(gè)地址項(xiàng)大小為4字節(jié)，索引塊和盤(pán)塊大小為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。四、 磁盤(pán)調(diào)度算法：1. 先來(lái)先服務(wù)FCFS 2. 最短尋道時(shí)間優(yōu)先SSTF 3. S

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

7、02，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ī)。在這種算法中，首先考慮的問(wèn)題是如何確定進(jìn)程的優(yōu)先數(shù)。 分為： 靜態(tài)優(yōu)先權(quán)：在創(chuàng)建進(jìn)程的時(shí)候便確定的，且在進(jìn)程的運(yùn)行期間保持不變。（簡(jiǎn)

8、單易行，系統(tǒng)開(kāi)銷(xiāo)小，但不夠精確，很可能出現(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)比。R(作業(yè)等待時(shí)間需運(yùn)行時(shí)間)/ 需運(yùn)行時(shí)間 1已等待時(shí)間 / 需運(yùn)行時(shí)間 1W/T例：六：頁(yè)面

9、置換算法先進(jìn)先出頁(yè)面淘汰算法（FIFO） 選擇在內(nèi)存中駐留時(shí)間最長(zhǎng)的頁(yè)并淘汰之理想淘汰算法最佳頁(yè)面算法（OPT） 淘汰以后不再需要的或最遠(yuǎn)的將來(lái)才會(huì)用到的頁(yè)面最近最久未使用頁(yè)面淘汰算法（LRU） 選擇最后一次訪(fǎng)問(wèn)時(shí)間距離當(dāng)前時(shí)間最長(zhǎng)的一頁(yè)并淘汰之即淘汰沒(méi)有使用的時(shí)間最長(zhǎng)的頁(yè)1 已知頁(yè)面走向?yàn)?、2、1、3、1、2、4、2、1、3、4，且開(kāi)始執(zhí)行時(shí)主存中沒(méi)有頁(yè)面。若只給該作業(yè)分配2個(gè)物理塊，當(dāng)采用FIFO頁(yè)面淘汰算法時(shí)缺頁(yè)率為多少？假定現(xiàn)有一種淘汰算法，該算法淘汰頁(yè)面的策略為當(dāng)需要淘汰頁(yè)面時(shí)，就把剛使用過(guò)的頁(yè)面作為淘汰對(duì)象，試問(wèn)就相同的頁(yè)面走向，缺頁(yè)率又為多少？分析及相關(guān)知識(shí) 在進(jìn)行內(nèi)存訪(fǎng)問(wèn)時(shí)，

10、若所訪(fǎng)問(wèn)的頁(yè)已在主存，則稱(chēng)此次訪(fǎng)問(wèn)成功；若所訪(fǎng)問(wèn)的頁(yè)不在主存，則稱(chēng)此次訪(fǎng)問(wèn)失敗，并產(chǎn)生缺頁(yè)中斷。若程序P在運(yùn)行過(guò)程中訪(fǎng)問(wèn)頁(yè)面的總次數(shù)為S,其中產(chǎn)生缺頁(yè)中斷的訪(fǎng)問(wèn)次數(shù)為F,則其缺頁(yè)率為：F/s. 解：根據(jù)所給頁(yè)面走向，采用FIFO淘汰算法的頁(yè)面置換情況如下：頁(yè)面走向 1 2 1 3 1 2 4 2 1 3 4物理塊1 1 1 3 3 2 2 1 1 4物理塊2 2 2 1 1 4 4 3 3缺頁(yè) 缺 缺 缺 缺 缺 缺 缺 缺 缺 從上述頁(yè)面置換圖可以看出：頁(yè)面引用次數(shù)為11次，缺頁(yè)次數(shù)為9次，所以缺頁(yè)率為9/11。若采用后一種頁(yè)面淘汰策略，其頁(yè)面置換情況如下：頁(yè)面走向 1 2 1 3 1 2

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

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