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

1、習(xí)題：1. 進(jìn)程同步，信號(hào)量機(jī)制實(shí)現(xiàn)設(shè)有6個(gè)程序s,，s，它們?cè)诓l(fā)系統(tǒng)中執(zhí)行時(shí)如圖所示的制16約關(guān)系，試用wait和signal原語來實(shí)現(xiàn)它們之間的同步。（10分）Vara，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);en

2、d;beginwait(e);wait(f);wait(g);S6;end;parendend2. 進(jìn)程同步，信號(hào)量機(jī)制實(shí)現(xiàn)。詳見上課講的例題3. 有如下進(jìn)程，后一個(gè)依次比前一個(gè)晚一個(gè)時(shí)間單位到達(dá)作業(yè)運(yùn)行時(shí)間優(yōu)先級(jí)A33B11C25D14E56(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) 對(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è)ABCD

3、E平均到達(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í)間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í)間1324

4、1.62.32RR(r=1)完成時(shí)間728512周轉(zhuǎn)時(shí)間716284.8帶權(quán)周轉(zhuǎn)時(shí)間7/31321.61.924.作出頁式存儲(chǔ)管理系統(tǒng)中地址變換機(jī)構(gòu)圖。已知某作業(yè)頁表如下：試借助地址變換機(jī)構(gòu)圖求出邏輯地址對(duì)應(yīng)的物理地址（1頁為1024字節(jié)）（1）2968（2）4599（3）0FCCH解：分析邏輯地址除以頁面大小=商是頁號(hào)：余數(shù)是頁內(nèi)地址偏移根據(jù)頁號(hào)查找頁表中的頁號(hào)判斷是（缺頁中斷，越界中斷.）物理地址=塊號(hào)*塊大小+地址偏移其中十六進(jìn)制的直接轉(zhuǎn)換為四位二進(jìn)制計(jì)算1.2968/1024=2.920物理地址：9*1024+920=101362.4599/1024=4.503越界中斷3.0FCCH二

5、進(jìn)制為：111111001100/2八10=11.111001100物理地址：8*1024+972=91645. 有一虛擬存儲(chǔ)系統(tǒng)，某作業(yè)運(yùn)行中使用的操作數(shù)所在的頁號(hào)依次為：43214354325124253415在內(nèi)存中為該作業(yè)進(jìn)程開辟3個(gè)物理塊。分別采用FIFO.LRU頁面淘汰算法，圖示該作業(yè)運(yùn)行的置換情況，并計(jì)算相應(yīng)的缺頁率？1. 最佳置換算法是置換以后永不使用的頁面即“向后看”432143543251242534154441115554441333444222555222333111332. FIFO是淘汰最先進(jìn)入的頁面缺頁率：(7/20)*100%=35%LRU算法是淘汰選擇最近久未

6、使用的頁面就是“向前看”43543251242534224444333555511444111533344422233缺頁率：(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,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)向

7、高磁道號(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)到

8、最小柱面號(hào)(0)再移動(dòng)到130(199-143)+(199-0)+(130-0)=385例:假定某磁盤共有200個(gè)柱面，編號(hào)為0-199，如果在為訪問143號(hào)柱面的請(qǐng)求者服務(wù)后,當(dāng)前正在為訪問125號(hào)柱面的請(qǐng)求服務(wù)，同時(shí)有若干請(qǐng)求者在等待服務(wù)，它們每次要訪問的柱面號(hào)為86,147,91,177,94,150,102,175,1301、先來先服務(wù)算法(FCFS)FirstComeFirstService這是一種比較簡單的磁盤調(diào)度算法。它根據(jù)進(jìn)程請(qǐng)求訪問磁盤的先后次序進(jìn)行調(diào)度。此算法的優(yōu)點(diǎn)是公平、簡單，且每個(gè)進(jìn)程的請(qǐng)求都能依次得到處理，不會(huì)出現(xiàn)某一進(jìn)程的請(qǐng)求長期得不到滿足的情況。此算法由于未對(duì)尋道

9、進(jìn)行優(yōu)化，在對(duì)磁盤的訪問請(qǐng)求比較多的情況下,此算法將降低設(shè)備服務(wù)的吞吐量，致使平均尋道時(shí)間可能較長，但各進(jìn)程得到服務(wù)的響應(yīng)時(shí)間的變化幅度較小。先來先服務(wù)(125)86.147.91.177.94.150.102.175.1302、最短尋道時(shí)間優(yōu)先算法（SSTF）ShortestSeekTimeFirst該算法選擇這樣的進(jì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ì)無限期的被延遲，有

10、些請(qǐng)求的響應(yīng)時(shí)間將不可預(yù)期。最短尋道時(shí)間優(yōu)先（125）130.147.150.175.177.102.94.91.863、掃描算法（SCAN）電梯調(diào)度掃描算法不僅考慮到欲訪問的磁道與當(dāng)前磁道的距離，更優(yōu)先考慮的是磁頭的當(dāng)前移動(dòng)方向。例如，當(dāng)磁頭正在自里向外移動(dòng)時(shí)，掃描算法所選擇的下一個(gè)訪問對(duì)象應(yīng)是其欲訪問的磁道既在當(dāng)前磁道之外，又是距離最近的。這樣自里向外地訪問，直到再無更外的磁道需要訪問才將磁臂換向，自外向里移動(dòng)。這時(shí)，同樣也是每次選擇這樣的進(jìn)程來調(diào)度，即其要訪問的磁道，在當(dāng)前磁道之內(nèi)，從而避免了饑餓現(xiàn)象的出現(xiàn)。由于這種算法中磁頭移動(dòng)的規(guī)律頗似電梯的運(yùn)行，故又稱為電梯調(diào)度算法。此算法基本上克

11、服了最短尋道時(shí)間優(yōu)先算法的服務(wù)集中于中間磁道和響應(yīng)時(shí)間變化比較大的缺點(diǎn)，而具有最短尋道時(shí)間優(yōu)先算法的優(yōu)點(diǎn)即吞吐量較大，平均響應(yīng)時(shí)間較小，但由于是擺動(dòng)式的掃描方法，兩側(cè)磁道被訪問的頻率仍低于中間磁道。電梯調(diào)度（125）102.94.91.86.130.147.150.175.1774、循環(huán)掃描算法（CSCAN）循環(huán)掃描算法是對(duì)掃描算法的改進(jìn)。如果對(duì)磁道的訪問請(qǐng)求是均勻分布的，當(dāng)磁頭到達(dá)磁盤的一端，并反向運(yùn)動(dòng)時(shí)落在磁頭之后的訪問請(qǐng)求相對(duì)較少。這是由于這些磁道剛被處理，而磁盤另一端的請(qǐng)求密度相當(dāng)高，且這些訪問請(qǐng)求等待的時(shí)間較長，為了解決這種情況，循環(huán)掃描算法規(guī)定磁頭單向移動(dòng)。例如，只自里向外移動(dòng)，當(dāng)

12、磁頭移到最外的被訪問磁道時(shí)，磁頭立即返回到最里的欲訪磁道，即將最小磁道號(hào)緊接著最大磁道號(hào)構(gòu)成循環(huán)，進(jìn)行掃描。循環(huán)掃描（125）130.147.150.175.177.86.91.94.1027. 說明文件物理結(jié)構(gòu)中顯式鏈接的原理，并計(jì)算一個(gè)200M的硬盤（盤塊大小為ikb）其fat表的大小。解：盤塊二容量/盤塊大小200M/lKB=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解：由題目所給條件可知，硬盤大小為540M，磁盤塊的大小為1K,所以該硬盤共有盤塊：54

13、0M/1K=540K（個(gè)）又512KV540KV1024K故540K個(gè)盤塊號(hào)要用20位二進(jìn)制表示，即文件分配表的每個(gè)表目為2.5個(gè)字節(jié)。FAT要占用的存儲(chǔ)空間總數(shù)為：2.5x540K=1350K當(dāng)硬盤大小為1.2G,硬盤共有盤塊：1.2G/1K=1.2M（個(gè)）又1MV1.2MV2M故1.2M個(gè)盤塊號(hào)要用31位二進(jìn)制表示。為方便文件分配表的存取，每個(gè)表目用32位二進(jìn)制表示，即文件分配表的每個(gè)表目大小為4個(gè)字節(jié)。FAT要占用的存儲(chǔ)空間總數(shù)為：4x1.2M=4.8M這題關(guān)于1.2G的解答那個(gè)“1.2M個(gè)盤塊號(hào)要用31位二進(jìn)制表示”這個(gè)我怎么都想不明白，上面“540K個(gè)盤塊號(hào)要用20位二進(jìn)制表示”我是

14、這樣理解540K介于512k（2人19）和1024k（2人20）之間，故用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è)盤塊的大小為5l2字節(jié)，若盤塊號(hào)需要用4個(gè)字節(jié)來描述，而每個(gè)盤塊最多存放128個(gè)盤塊地址。貝I：（1）該文件系統(tǒng)允許文件的最大長度是多少？（2）將文件的字節(jié)偏移量500，15000和150000轉(zhuǎn)換為物理塊號(hào)和塊內(nèi)偏移量。例題11存放在某個(gè)磁盤上的文件系統(tǒng)采用混合索引分配方式，其FCB屮共有13個(gè)地址項(xiàng)，第0至9個(gè)地址項(xiàng)為直接地址，第

15、10個(gè)地址項(xiàng)為一次間接地址，第11個(gè)地址項(xiàng)為二次間接地址，第12個(gè)地址項(xiàng)為三次間接地址口如果每個(gè)盤快的大小為512字節(jié)，若盤塊號(hào)需要用3個(gè)字節(jié)來描述，而每個(gè)盤塊最多存放170個(gè)盤塊地址，貝*X該文件系統(tǒng)允許文件的最大長度是多少？2. 將文件的字節(jié)偏移量5000.15000.150000轉(zhuǎn)換為物理塊號(hào)和塊內(nèi)偏移量。3、假設(shè)某個(gè)文件的FCB已經(jīng)在內(nèi)存，但其他信息均在外存，為了訪問該文件屮某個(gè)位置的內(nèi)容，最少需要幾次訪問磁盤？二分析：在混合索引分配方式中，文件FCB的直接地址中登記有分配給文件的前n塊的物理塊號(hào)（口大小由直接地址項(xiàng)數(shù)確定，本題為10）；一次間接地址中登記有一個(gè)一次間接地址塊的塊號(hào)，l

16、fJ在一次間址塊中登記有分配給文件的第口至第n+kl塊的塊號(hào)（k的大小由盤塊大小和盤塊號(hào)的長度決定，本題屮是170）；二次簡址中登記有一個(gè)二次間址塊的塊號(hào)，其中可給出k個(gè)一次間址塊的塊號(hào)，而這些一次間址塊被用來登記分配給文件的第口+k塊到第n+k+k2-l塊的塊號(hào)；三次間址中則登記有一個(gè)三次間址塊的塊號(hào)，其中可給出k個(gè)二次間址塊的塊號(hào)，這些二次間址塊又可給出k2個(gè)一次間址塊的塊號(hào)，而這些一次間址塊則被用來登記分配給文件的第n+k+k2塊到第n+k+k2+k3-l塊的物理塊號(hào)。1. 該文件系統(tǒng)中一個(gè)文件的最大長度：最大物理塊數(shù)：10+170+170*170+170170*170=4942080塊文件的字節(jié)數(shù)；4942080*512B-2471040KB2、將文件的字節(jié)偏移量轉(zhuǎn)換為物理塊號(hào)及塊內(nèi)偏移量5000/512得到商為9,余數(shù)為392,即字節(jié)偏移量5000對(duì)應(yīng)的邏輯塊號(hào)為9,塊內(nèi)偏移量為392口由于9<10,故可直接從該文件的FCB的第9個(gè)地址項(xiàng)處得到物理盤塊號(hào)，塊內(nèi)偏移量為392；15000/512得到商為29,余數(shù)為152,即字節(jié)偏移量15000對(duì)應(yīng)的邏輯塊號(hào)為29,塊內(nèi)偏移量為152。|±!J10<=29<10+170