操作系統(tǒng)經(jīng)典習(xí)題

-.z.習(xí)題：進(jìn)程同步，信號(hào)量機(jī)制實(shí)現(xiàn)設(shè)有6個(gè)程序s1,…,s6，它們?cè)诓l(fā)系統(tǒng)中執(zhí)行時(shí)如圖所示的制約關(guān)系，試用wait和signal原語(yǔ)來(lái)實(shí)現(xiàn)它們之間的同步。（10分）S1S1S2S2S5S3S4S5S3S4S6S6Vara,b,c,d,e,f,g,h;semaphore:=0,0,0,0,0,0,0;beginparbeginbeginS1;signal(a);signal(b);signal(c);end;beginwait(a);S2;signal(d);end;beginwait(b);S3;signal(f);end;beginwait(c);S4;signal(g);end;beginwait(d);S5;signal(e);end;beginwait(e);wait(f);wait(g);S6;end;parendend進(jìn)程同步，信號(hào)量機(jī)制實(shí)現(xiàn)。詳見(jiàn)上課講的例題有如下進(jìn)程，后一個(gè)依次比前一個(gè)晚一個(gè)時(shí)間單位到達(dá)，作業(yè)運(yùn)行時(shí)間優(yōu)先級(jí)A33B11C25D14E56（1）畫(huà)出下列調(diào)度算法下的調(diào)度時(shí)間圖：FCFS、搶占式\非搶占式SPF、搶占式\非搶占式HPF、HRRN和RR（q=1,q=2）（2）對(duì)于上述每種算法，各個(gè)作業(yè)的周轉(zhuǎn)時(shí)間是多少？平均周轉(zhuǎn)時(shí)間是多少？（3）對(duì)于上述每種算法，各個(gè)作業(yè)的帶權(quán)周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間各是多少？相應(yīng)比=【(等待時(shí)間=現(xiàn)在時(shí)刻減去到達(dá)時(shí)間)+服務(wù)時(shí)間】/服務(wù)時(shí)間算法作業(yè)ABCDE平均到達(dá)時(shí)間01234服務(wù)時(shí)間31215FCFS完成時(shí)間346712周轉(zhuǎn)時(shí)間33448=average(C5:G5)4.4帶權(quán)周轉(zhuǎn)時(shí)間13241.6=average(C6:G6)2.32SPF(非)完成時(shí)間347512周轉(zhuǎn)時(shí)間33528=average(C8:G8)4.2帶權(quán)周轉(zhuǎn)時(shí)間132.521.6=average(C9:G9)2.02SPF(搶)完成時(shí)間31151210周轉(zhuǎn)時(shí)間310396=average(C11:G11)6.2帶權(quán)周轉(zhuǎn)時(shí)間1101.591.2=average(C12:G12)4.54HPF（非)完成時(shí)間31151210周轉(zhuǎn)時(shí)間310396=average(C14:G14)6.2帶權(quán)周轉(zhuǎn)時(shí)間1101.591.2=average(C15:G15)4.54HPF（搶)完成時(shí)間11124109周轉(zhuǎn)時(shí)間1111275=average(C17:G17)7.2帶權(quán)周轉(zhuǎn)時(shí)間11/311171=average(C18:G18)4.72HRRN完成時(shí)間346712周轉(zhuǎn)時(shí)間33448=average(C20:G20)4.4帶權(quán)周轉(zhuǎn)時(shí)間13241.6=average(C21:G21)2.32RR（r=1）完成時(shí)間728512周轉(zhuǎn)時(shí)間71628=average(C23:G23)4.8帶權(quán)周轉(zhuǎn)時(shí)間7/31321.6=average(C24:G24)1.92作出頁(yè)式存儲(chǔ)管理系統(tǒng)中地址變換機(jī)構(gòu)圖。已知*作業(yè)頁(yè)表如下：02152938試借助地址變換機(jī)構(gòu)圖求出邏輯地址對(duì)應(yīng)的物理地址（1頁(yè)為1024字節(jié)）(1)2968（2）4599（3）0FCCH解：分析邏輯地址除以頁(yè)面大小=商是頁(yè)號(hào)：余數(shù)是頁(yè)內(nèi)地址偏移根據(jù)頁(yè)號(hào)查找頁(yè)表中的頁(yè)號(hào)判斷是（缺頁(yè)中斷，越界中斷...）物理地址=塊號(hào)*塊大小+地址偏移其中十六進(jìn)制的直接轉(zhuǎn)換為四位二進(jìn)制計(jì)算1.2968/1024=2...920物理地址：9*1024+920=101362.4599/1024=4...503越界中斷3.0FCCH二進(jìn)制為：0/2^10=11...111001100物理地址：8*1024+972=9164有一虛擬存儲(chǔ)系統(tǒng)，*作業(yè)運(yùn)行中使用的操作數(shù)所在的頁(yè)號(hào)依次為：43214354325124253415在內(nèi)存中為該作業(yè)進(jìn)程開(kāi)辟3個(gè)物理塊。分別采用FIFO、LRU頁(yè)面淘汰算法，圖示該作業(yè)運(yùn)行的置換情況，并計(jì)算相應(yīng)的缺頁(yè)率？1.最佳置換算法是置換以后永不使用的頁(yè)面即“向后看”432143543251242534154441115554441333444222555222333111332.FIFO是淘汰最先進(jìn)入的頁(yè)面缺頁(yè)率：(7/20)*100%=35%LRU算法是淘汰選擇最近久未使用的頁(yè)面就是“向前看”43214354325124253415444111522222244433344445544333522233331155511缺頁(yè)率：(4/20)*100%=20%假設(shè)磁盤(pán)有200個(gè)磁道（編號(hào)為0～199）的移動(dòng)頭磁盤(pán)，在完成了磁道125處的請(qǐng)求后，當(dāng)前正在磁道號(hào)為143的磁道處為一個(gè)請(qǐng)求服務(wù)。若請(qǐng)求隊(duì)列以FIFO次序存放，即86，147，91，177，94，150，102，175，130。對(duì)下列每一中磁盤(pán)調(diào)度算法，若要滿足這些要求，則總的磁頭移動(dòng)次數(shù)為多少(后兩種要求，讀寫(xiě)頭朝著磁道號(hào)增大的方向移動(dòng))？（1）FCFS(2)SSTF(3)SCAN(4)CSCAN首先根據(jù)題意可知：磁頭正由低磁道號(hào)向高磁道號(hào)方向移動(dòng)。fcfs:順序是：143--86--147--91--177--94--150--102--175--130(143-86)+(147-86)+(147-91)+(177-91)+(177-94)+(150-94)+(150-102)+(175-102)+(175-130)=565sstf:順序是：143--147--150--130--102--94--91--86--175--177(147-143)+(150-147)+(150-130)+(130-102)+(102-94)+(94-91)+(91-86)+(175-86)+(177-175)=162scan:順序是：先移動(dòng)到最大柱面號(hào)(199)再移動(dòng)到最小柱面號(hào)(0)再移動(dòng)到130(199-143)+(199-0)+(130-0)=385例:假定*磁盤(pán)共有200個(gè)柱面，編號(hào)為0-199，如果在為訪問(wèn)143號(hào)柱面的請(qǐng)求者服務(wù)后，當(dāng)前正在為訪問(wèn)125號(hào)柱面的請(qǐng)求服務(wù)，同時(shí)有若干請(qǐng)求者在等待服務(wù)，它們每次要訪問(wèn)的柱面號(hào)為86，147，91，177，94，150，102，175，1301、先來(lái)先服務(wù)算法（FCFS）FirsteFirstService這是一種比較簡(jiǎn)單的磁盤(pán)調(diào)度算法。它根據(jù)進(jìn)程請(qǐng)求訪問(wèn)磁盤(pán)的先后次序進(jìn)行調(diào)度。此算法的優(yōu)點(diǎn)是公平、簡(jiǎn)單，且每個(gè)進(jìn)程的請(qǐng)求都能依次得到處理，不會(huì)出現(xiàn)*一進(jìn)程的請(qǐng)求長(zhǎng)期得不到滿足的情況。此算法由于未對(duì)尋道進(jìn)行優(yōu)化，在對(duì)磁盤(pán)的訪問(wèn)請(qǐng)求比較多的情況下，此算法將降低設(shè)備服務(wù)的吞吐量，致使平均尋道時(shí)間可能較長(zhǎng)，但各進(jìn)程得到服務(wù)的響應(yīng)時(shí)間的變化幅度較小。先來(lái)先服務(wù)（125）2、最短尋道時(shí)間優(yōu)先算法（SSTF）ShortestSeekTimeFirst該算法選擇這樣的進(jìn)程，其要求訪問(wèn)的磁道與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時(shí)間最短，該算法可以得到比較好的吞吐量，但卻不能保證平均尋道時(shí)間最短。其缺點(diǎn)是對(duì)用戶的服務(wù)請(qǐng)求的響應(yīng)機(jī)會(huì)不是均等的，因而導(dǎo)致響應(yīng)時(shí)間的變化幅度很大。在服務(wù)請(qǐng)求很多的情況下，對(duì)內(nèi)外邊緣磁道的請(qǐng)求將會(huì)無(wú)限期的被延遲，有些請(qǐng)求的響應(yīng)時(shí)間將不可預(yù)期。最短尋道時(shí)間優(yōu)先（125）3、掃描算法（SCAN）電梯調(diào)度掃描算法不僅考慮到欲訪問(wèn)的磁道與當(dāng)前磁道的距離，更優(yōu)先考慮的是磁頭的當(dāng)前移動(dòng)方向。例如，當(dāng)磁頭正在自里向外移動(dòng)時(shí)，掃描算法所選擇的下一個(gè)訪問(wèn)對(duì)象應(yīng)是其欲訪問(wèn)的磁道既在當(dāng)前磁道之外，又是距離最近的。這樣自里向外地訪問(wèn)，直到再無(wú)更外的磁道需要訪問(wèn)才將磁臂換向，自外向里移動(dòng)。這時(shí)，同樣也是每次選擇這樣的進(jìn)程來(lái)調(diào)度，即其要訪問(wèn)的磁道，在當(dāng)前磁道之內(nèi)，從而避免了饑餓現(xiàn)象的出現(xiàn)。由于這種算法中磁頭移動(dòng)的規(guī)律頗似電梯的運(yùn)行，故又稱(chēng)為電梯調(diào)度算法。此算法基本上克服了最短尋道時(shí)間優(yōu)先算法的服務(wù)集中于中間磁道和響應(yīng)時(shí)間變化比較大的缺點(diǎn)，而具有最短尋道時(shí)間優(yōu)先算法的優(yōu)點(diǎn)即吞吐量較大，平均響應(yīng)時(shí)間較小，但由于是擺動(dòng)式的掃描方法，兩側(cè)磁道被訪問(wèn)的頻率仍低于中間磁道。電梯調(diào)度（125）4、循環(huán)掃描算法（CSCAN）循環(huán)掃描算法是對(duì)掃描算法的改進(jìn)。如果對(duì)磁道的訪問(wèn)請(qǐng)求是均勻分布的，當(dāng)磁頭到達(dá)磁盤(pán)的一端，并反向運(yùn)動(dòng)時(shí)落在磁頭之后的訪問(wèn)請(qǐng)求相對(duì)較少。這是由于這些磁道剛被處理，而磁盤(pán)另一端的請(qǐng)求密度相當(dāng)高，且這些訪問(wèn)請(qǐng)求等待的時(shí)間較長(zhǎng)，為了解決這種情況，循環(huán)掃描算法規(guī)定磁頭單向移動(dòng)。例如，只自里向外移動(dòng)，當(dāng)磁頭移到最外的被訪問(wèn)磁道時(shí)，磁頭立即返回到最里的欲訪磁道，即將最小磁道號(hào)緊接著最大磁道號(hào)構(gòu)成循環(huán)，進(jìn)行掃描。循環(huán)掃描（125）說(shuō)明文件物理結(jié)構(gòu)中顯式的原理，并計(jì)算一個(gè)200M的硬盤(pán)（盤(pán)塊大小為1KB）其FAT表的大小。解：盤(pán)塊=容量/盤(pán)塊大小200M/1KB=200K（個(gè))表項(xiàng)大小滿足為四位二進(jìn)制的整數(shù)倍又因?yàn)椋?28K<200K<256K故表項(xiàng)大小為2.5個(gè)字節(jié)FAT表的大小=表項(xiàng)大小*表項(xiàng)數(shù)=200*2.5=500KB解：由題目所給條件可知，硬盤(pán)大小為540M，磁盤(pán)塊的大小為1K，所以該硬盤(pán)共有盤(pán)塊：

540M/1K=540K（個(gè)）

又

512K＜540K＜1024K

故540K個(gè)盤(pán)塊號(hào)要用20位二進(jìn)制表示，即文件分配表的每個(gè)表目為2.5個(gè)字節(jié)。

FAT要占用的存儲(chǔ)空間總數(shù)為：

2.5×540K=1350K

當(dāng)硬盤(pán)大小為1.2G，硬盤(pán)共有盤(pán)塊：

1.2G/1K=1.2M（個(gè)）

又

1M＜1.2M＜2M

故1.2M個(gè)盤(pán)塊號(hào)要用31位二進(jìn)制表示。為方便文件分配表的存取，每個(gè)表目用32位二進(jìn)制表示，即文件分配表的每個(gè)表目大小為4個(gè)字節(jié)。

FAT要占用的存儲(chǔ)空間總數(shù)為：

4×1.2M=4.8M這題關(guān)于1.2G的解答那個(gè)“1.2M個(gè)盤(pán)塊號(hào)要用31位二進(jìn)制表示”這個(gè)我怎么都想不明白，上面“540K個(gè)盤(pán)塊號(hào)要用20位二進(jìn)制表示”我是這樣理解540K介于512k（2^19）和1024k（2^20）之間，故用20位二進(jìn)制表示。存放在*個(gè)磁盤(pán)上的文件系統(tǒng)采用混合索引分配方式，其FCB中共有6個(gè)地址項(xiàng)，第0—3個(gè)地址項(xiàng)為直接地址，第4個(gè)地址項(xiàng)為一次間接地址，第5個(gè)地址項(xiàng)為二次間接地址，。如果每個(gè)盤(pán)塊的大小為512字節(jié)，若盤(pán)塊號(hào)需要用4個(gè)字節(jié)來(lái)描述，而每個(gè)盤(pán)塊最多存放128個(gè)盤(pán)塊地址。則：（1）