1、習(xí)題：1. 進(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分）S1S2S5S3S4S6Var a, b, c, d, e, f, g, h; semaphore:= 0, 0, 0, 0, 0, 0, 0; begin parbegin begin S1; signal(a); signal(b);signal(c); end; begin wait(a); S2; signal(d); end; begin wait(b); S3; signal(f); end; begin wait(c

2、); S4; signal(g); end;begin wait(d); S5; signal(e); end;begin wait(e); wait(f); wait(g); S6; end; parend end2. 進(jìn)程同步，信號(hào)量機(jī)制實(shí)現(xiàn)。詳見上課講的例題3. 有如下進(jìn)程，后一個(gè)依次比前一個(gè)晚一個(gè)時(shí)間單位到達(dá)，作業(yè) 運(yùn)行時(shí)間 優(yōu)先級(jí) A 3 3 B 1 1 C 2 5D 1 4 E 5 6 （1）畫出下列調(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、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í)間334484.4帶權(quán)周轉(zhuǎn)時(shí)間13241.62.32SPF(非)完成時(shí)間347512周轉(zhuǎn)時(shí)間335284.2帶權(quán)周轉(zhuǎn)時(shí)間132.521.62.02SPF(搶)完成時(shí)間31151210周轉(zhuǎn)時(shí)間3103966.2帶權(quán)周轉(zhuǎn)時(shí)間1101.591.24.54HPF（非)完成時(shí)間31151210周轉(zhuǎn)時(shí)間3103966.2帶權(quán)周轉(zhuǎn)時(shí)間1101.591.24.54HPF（搶)完成時(shí)間

4、11124109周轉(zhuǎn)時(shí)間11112757.2帶權(quán)周轉(zhuǎn)時(shí)間11/3111714.72HRRN完成時(shí)間346712周轉(zhuǎn)時(shí)間334484.4帶權(quán)周轉(zhuǎn)時(shí)間13241.62.32RR（r=1）完成時(shí)間728512周轉(zhuǎn)時(shí)間716284.8帶權(quán)周轉(zhuǎn)時(shí)間7/31321.61.924. 作出頁(yè)式存儲(chǔ)管理系統(tǒng)中地址變換機(jī)構(gòu)圖。已知某作業(yè)頁(yè)表如下：0 2 1 5 2 9 3 8試借助地址變換機(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è)中斷，越界中斷.）物理地址=塊

5、號(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)制為：111111001100/210=11.111001100物理地址：8*1024+972=91645. 有一虛擬存儲(chǔ)系統(tǒng)，某作業(yè)運(yùn)行中使用的操作數(shù)所在的頁(yè)號(hào)依次為：4 3 2 1 4 3 5 4 3 2 5 1 2 4 2 5 3 4 1 5在內(nèi)存中為該作業(yè)進(jìn)程開辟3個(gè)物理塊。分別采用FIFO、LRU頁(yè)面淘汰算法，圖示該作業(yè)運(yùn)行的置換情況，并計(jì)算相應(yīng)的缺頁(yè)率？1.最佳置換算法是置換以后永不使用

6、的頁(yè)面即“向后看”432143543251242534154441115554441333444222555222333111332.FIFO是淘汰最先進(jìn)入的頁(yè)面缺頁(yè)率：(7/20)*100%=35%LRU算法是淘汰選擇最近久未使用的頁(yè)面就是“向前看”43214354325124253415444111522222244433344445544333522233331155511缺頁(yè)率：(4/20)*100%=20%6. 假設(shè)磁盤有200個(gè)磁道（編號(hào)為0199）的移動(dòng)頭磁盤，在完成了磁道125處的請(qǐng)求后，當(dāng)前正在磁道號(hào)為143的磁道處為一個(gè)請(qǐng)求服務(wù)。若請(qǐng)求隊(duì)列以FIFO次序存放，即86，147

7、，91，177，94，150，102，175，130。對(duì)下列每一中磁盤調(diào)度算法，若要滿足這些要求，則總的磁頭移動(dòng)次數(shù)為多少 (后兩種要求，讀寫頭朝著磁道號(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

8、-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例:假定某磁盤共有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，

9、175，1301、先來(lái)先服務(wù)算法（FCFS）First Come First Service這是一種比較簡(jiǎn)單的磁盤調(diào)度算法。它根據(jù)進(jìn)程請(qǐng)求訪問(wè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ì)磁盤的訪問(wèn)請(qǐng)求比較多的情況下，此算法將降低設(shè)備服務(wù)的吞吐量，致使平均尋道時(shí)間可能較長(zhǎng)，但各進(jìn)程得到服務(wù)的響應(yīng)時(shí)間的變化幅度較小。先來(lái)先服務(wù) （125）86.147.91.177.94.150.102.175.130 2、最短尋道時(shí)間優(yōu)先算法（SSTF） Shortest Seek Time Fir

10、st該算法選擇這樣的進(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）130.147.150.175.177.102.94.91.86 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)是

11、其欲訪問(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)行，故又稱為電梯調(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）102.94.91.86.130.147.150.175.177 4、循環(huán)掃描算法

12、（CSCAN）循環(huán)掃描算法是對(duì)掃描算法的改進(jìn)。如果對(duì)磁道的訪問(wèn)請(qǐng)求是均勻分布的，當(dāng)磁頭到達(dá)磁盤的一端，并反向運(yùn)動(dòng)時(shí)落在磁頭之后的訪問(wèn)請(qǐng)求相對(duì)較少。這是由于這些磁道剛被處理，而磁盤另一端的請(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）130.147.150.175.177.86.91.94.1027. 說(shuō)明文件物理結(jié)構(gòu)中顯式鏈接的原理，并計(jì)算一個(gè)200M的硬盤（盤塊大小為1KB）其FAT表的大小。解

13、：盤塊=容量/盤塊大小 200M/1KB=200K（個(gè))表項(xiàng)大小滿足為四位二進(jìn)制的整數(shù)倍又因?yàn)椋?28K200K256K 故 表項(xiàng)大小為2.5個(gè)字節(jié)FAT表的大小=表項(xiàng)大小*表項(xiàng)數(shù)=200*2.5=500KB解：由題目所給條件可知，硬盤大小為540M，磁盤塊的大小為1K，所以該硬盤共有盤塊：540M/1K=540K（個(gè)）又512K540K1024K故540K個(gè)盤塊號(hào)要用20位二進(jìn)制表示，即文件分配表的每個(gè)表目為2.5個(gè)字節(jié)。FAT要占用的存儲(chǔ)空間總數(shù)為：2.5540K=1350K當(dāng)硬盤大小為1.2G，硬盤共有盤塊：1.2G/1K=1.2M（個(gè)）又1M1.2M2M故1.2M個(gè)盤塊號(hào)要用31位二進(jìn)

14、制表示。為方便文件分配表的存取，每個(gè)表目用32位二進(jìn)制表示，即文件分配表的每個(gè)表目大小為4個(gè)字節(jié)。FAT要占用的存儲(chǔ)空間總數(shù)為：41.2M=4.8M這題關(guān)于1.2G的解答那個(gè)“1.2M個(gè)盤塊號(hào)要用31位二進(jìn)制表示”這個(gè)我怎么都想不明白，上面“540K個(gè)盤塊號(hào)要用20位二進(jìn)制表示”我是這樣理解540K介于512k（219）和1024k（220）之間，故用20位二進(jìn)制表示。8. 存放在某個(gè)磁盤上的文件系統(tǒng)采用混合索引分配方式，其FCB中共有6個(gè)地址項(xiàng)，第03個(gè)地址項(xiàng)為直接地址，第4個(gè)地址項(xiàng)為一次間接地址，第5個(gè)地址項(xiàng)為二次間接地址，。如果每個(gè)盤塊的大小為512字節(jié)，若盤塊號(hào)需要用4個(gè)字節(jié)來(lái)描述，而每個(gè)盤塊最多存放128個(gè)盤塊地址。則：（1）該文件系統(tǒng)允許文件的最大長(zhǎng)