操作系統(tǒng)習(xí)題解析

1、2022-4-251習(xí)題分析習(xí)題分析 習(xí)題一：進(jìn)程調(diào)度習(xí)題一：進(jìn)程調(diào)度 習(xí)題二：習(xí)題二：P/V操作例子操作例子 習(xí)題三：頁式存儲(chǔ)管理中的一級(jí)頁表地址計(jì)算習(xí)題三：頁式存儲(chǔ)管理中的一級(jí)頁表地址計(jì)算 習(xí)題四：磁盤調(diào)度習(xí)題四：磁盤調(diào)度SSTF存在的問題存在的問題 習(xí)題五：磁盤空閑塊的成組分配算法習(xí)題五：磁盤空閑塊的成組分配算法2022-4-252習(xí)題一：進(jìn)程調(diào)度習(xí)題一：進(jìn)程調(diào)度有有5個(gè)進(jìn)程如下表。時(shí)間從個(gè)進(jìn)程如下表。時(shí)間從0開始，單位為開始，單位為1，最高優(yōu)先級(jí)為，最高優(yōu)先級(jí)為0. 進(jìn)程進(jìn)程 到達(dá)時(shí)間到達(dá)時(shí)間 優(yōu)先級(jí)優(yōu)先級(jí) 所需運(yùn)行時(shí)間所需運(yùn)行時(shí)間A 0 2 3B 2 3 8C 4 4 6 D 6 1

2、 5E 8 0 4繪圖說明以下進(jìn)程調(diào)度過程：（繪圖說明以下進(jìn)程調(diào)度過程：（1 CPU系統(tǒng)，所有進(jìn)程只使用系統(tǒng)，所有進(jìn)程只使用CPU）。）。請(qǐng)使用時(shí)間為橫向坐標(biāo)軸，并請(qǐng)?jiān)趫D中標(biāo)明每個(gè)進(jìn)程的請(qǐng)使用時(shí)間為橫向坐標(biāo)軸，并請(qǐng)?jiān)趫D中標(biāo)明每個(gè)進(jìn)程的“等待等待”和和“運(yùn)運(yùn)行行”兩種狀態(tài)。兩種狀態(tài)。先來先服務(wù)（先來先服務(wù)（FCFS）。）。輪轉(zhuǎn)調(diào)度（輪轉(zhuǎn)調(diào)度（Round-Robin） 時(shí)間片時(shí)間片=2。優(yōu)先級(jí)輪轉(zhuǎn)法（優(yōu)先級(jí)輪轉(zhuǎn)法（Priority Round-Robin） 時(shí)間片時(shí)間片=2。最短進(jìn)程優(yōu)先算法（最短進(jìn)程優(yōu)先算法（Shortest Process Next）。）。2022-4-253答案答案新進(jìn)程出現(xiàn)

3、，重新調(diào)度，新進(jìn)新進(jìn)程出現(xiàn)，重新調(diào)度，新進(jìn)程的優(yōu)先級(jí)與當(dāng)前正運(yùn)行程的優(yōu)先級(jí)與當(dāng)前正運(yùn)行進(jìn)程比較，進(jìn)程比較，搶占發(fā)生搶占發(fā)生。時(shí)間片用完，進(jìn)程切換，就緒時(shí)間片用完，進(jìn)程切換，就緒隊(duì)列中的首進(jìn)程投入運(yùn)行，隊(duì)列中的首進(jìn)程投入運(yùn)行，換下來的進(jìn)程按其優(yōu)先級(jí)換下來的進(jìn)程按其優(yōu)先級(jí)插入到就緒隊(duì)列中，體現(xiàn)插入到就緒隊(duì)列中，體現(xiàn)輪轉(zhuǎn)與優(yōu)先級(jí)各自的特點(diǎn)輪轉(zhuǎn)與優(yōu)先級(jí)各自的特點(diǎn)可能引起調(diào)度可能引起調(diào)度CPU的時(shí)機(jī)：的時(shí)機(jī)：進(jìn)程運(yùn)行結(jié)束時(shí)進(jìn)程運(yùn)行結(jié)束時(shí)進(jìn)程的時(shí)間片用完時(shí)（進(jìn)程的時(shí)間片用完時(shí)（RR）進(jìn)程申請(qǐng)資源未得到滿足時(shí)進(jìn)程申請(qǐng)資源未得到滿足時(shí)(被阻塞被阻塞)擁有更高的優(yōu)先級(jí)的進(jìn)程到達(dá)時(shí)擁有更高的優(yōu)先級(jí)的進(jìn)程到達(dá)時(shí)可看

4、成是可看成是搶占式的搶占式的FCFS2022-4-254PRR的其它應(yīng)用的其它應(yīng)用PRR應(yīng)用的參考文獻(xiàn)：應(yīng)用的參考文獻(xiàn)：題目：題目：Priority Ruond-Robin Scheduling for Very Large Virtual Environment作者：作者：Chris FaisstnauerDieter SchmalstiegWerner Purgathofer所屬單位：所屬單位：Vienna University of Technology, Austria奧地利維也納科技大學(xué) 郵件地址：郵件地址：faisstcg.tuwien.ac.at檢索網(wǎng)址：檢索網(wǎng)址：http:/i

5、/xpls/abs_all.jsp?arnumber=8404912022-4-255Basic Priority Round-RobinSelected elements: A,C,G - B,D,G - A,E,G - B,F,G循環(huán)計(jì)數(shù) = 每個(gè)級(jí)別上的進(jìn)程數(shù)目 * 優(yōu)先級(jí)層次總數(shù)本例中，優(yōu)先級(jí)分為3個(gè)層次，分別為：0級(jí)/1級(jí)/2級(jí)i=0i=1i=2優(yōu)先級(jí)2022-4-256習(xí)題二：習(xí)題二：P/V操作的應(yīng)用操作的應(yīng)用 某公司有兩個(gè)生產(chǎn)部門和一個(gè)裝配部門，兩個(gè)生某公司有兩個(gè)生產(chǎn)部門和一個(gè)裝配部門，兩個(gè)生產(chǎn)部門分別生產(chǎn)甲、乙兩種零件，裝配部門的任產(chǎn)部門分別

6、生產(chǎn)甲、乙兩種零件，裝配部門的任務(wù)是把甲、乙兩種零件組裝成產(chǎn)品。兩個(gè)生產(chǎn)部務(wù)是把甲、乙兩種零件組裝成產(chǎn)品。兩個(gè)生產(chǎn)部門每生產(chǎn)一個(gè)零件后都要分別把它們送到裝配部門每生產(chǎn)一個(gè)零件后都要分別把它們送到裝配部門的貨架門的貨架S1、S2上。上。S1存放零件甲，存放零件甲，S2存放零存放零件乙，件乙，S1和和S2均可容納均可容納20個(gè)零件。裝配人員每次個(gè)零件。裝配人員每次從貨架上取走一個(gè)甲零件和一個(gè)乙零件后，將其從貨架上取走一個(gè)甲零件和一個(gè)乙零件后，將其組裝成產(chǎn)品。請(qǐng)利用組裝成產(chǎn)品。請(qǐng)利用P、V操作控制各部門之間使操作控制各部門之間使用零件的貨架規(guī)則，保證零件入用零件的貨架規(guī)則，保證零件入/出貨架的正確性

7、。出貨架的正確性。2022-4-257算法描述算法描述Begin 信號(hào)量初值：信號(hào)量初值：mutex1:=1;mutex2:=1;empty1:=20;full1:=0;empty2:=20;full2:=0CobeginA部門：部門： begin Repeat 生產(chǎn)一個(gè)產(chǎn)品生產(chǎn)一個(gè)產(chǎn)品A; P(empty1); P(mutex1); 將產(chǎn)品將產(chǎn)品A放入放入S1; V(mutex1); V(full1); Until false EndB部門：部門：beginRepeat 生產(chǎn)一個(gè)產(chǎn)品生產(chǎn)一個(gè)產(chǎn)品B; P(empty2); P(mutex2); 將產(chǎn)品將產(chǎn)品B放入放入S2; V(mutex2)

8、; V(full2);Until falseEnd裝配人員：裝配人員：beginRepeat P(full1); P(full2); P(mutex1); 從從S1中取出產(chǎn)品中取出產(chǎn)品A; V(mutex1); V(empty1); P(mutex2); 從從S2中取出產(chǎn)品中取出產(chǎn)品B; V(mutex2); V(empty2); 把把A和和B組裝成產(chǎn)品組裝成產(chǎn)品Until false EndCoendEnd;2022-4-258習(xí)題三：確定頁表位置習(xí)題習(xí)題三：確定頁表位置習(xí)題 一個(gè)一個(gè)32位的虛擬存儲(chǔ)系統(tǒng)有兩級(jí)頁表，其邏輯地位的虛擬存儲(chǔ)系統(tǒng)有兩級(jí)頁表，其邏輯地址中，第址中，第22到到31位是

9、第一級(jí)頁表，位是第一級(jí)頁表，12位到位到21位是位是第二級(jí)頁表，頁內(nèi)偏移占第二級(jí)頁表，頁內(nèi)偏移占0到到11位。一個(gè)進(jìn)程的位。一個(gè)進(jìn)程的地址空間為地址空間為4GB，如果從，如果從0XC0000000開始映射開始映射4MB大小頁表，請(qǐng)問第一級(jí)頁表所占的大小頁表，請(qǐng)問第一級(jí)頁表所占的4KB空間空間映射在什么位置，并說明理由。（注意映射在什么位置，并說明理由。（注意B代表字代表字節(jié)，一個(gè)節(jié)，一個(gè)32位地址占位地址占4字節(jié)）字節(jié)）第一級(jí)頁表項(xiàng)第一級(jí)頁表項(xiàng) 第二級(jí)頁表項(xiàng)第二級(jí)頁表項(xiàng) 頁內(nèi)相對(duì)位移頁內(nèi)相對(duì)位移31021112022-4-259習(xí)題三：續(xù)一習(xí)題三：續(xù)一虛擬地址空間虛擬地址空間0= 0X0000

10、00000= 0X000000003G= 3G= 0XC00000XC0000000000第第768K768K個(gè)頁面?zhèn)€頁面4G-1= 0XFFFFFFFF4G-1= 0XFFFFFFFF4MB頁表所在位置頁表所在位置（全部頁表占（全部頁表占1K個(gè)頁面）個(gè)頁面）二級(jí)頁表每塊1024項(xiàng)4KB大小每項(xiàng)代表1頁=4KB一級(jí)頁表4KB共有1024項(xiàng),每項(xiàng)代表1k個(gè)頁表項(xiàng)=1M頁=4MB7684MB=3G一級(jí)頁表所在位置第768塊頁表是3G虛擬地址映射位置共有1024個(gè)頁表塊(頁表頁面)1M個(gè)頁表項(xiàng)，總共占4MB大小內(nèi)存。1M個(gè)頁表項(xiàng)可表示1M 4K=4G內(nèi)存其中包括了一級(jí)頁表的4K區(qū)域。. . . .：

11、. . . . . . . . . .：一個(gè)32位的虛擬存儲(chǔ)系統(tǒng)有兩級(jí)頁表，其邏輯地址中，第22到31位是第一級(jí)頁表，12位到21位是第二級(jí)頁表，頁內(nèi)偏移占0到11位。一個(gè)進(jìn)程的地址空間為4GB，如果從0XC0000000開始映射4MB大小頁表，請(qǐng)問第一級(jí)頁表所占的4KB空間映射在什么位置，并說明理由。（注意B代表字節(jié)，一個(gè)32位地址占4字節(jié)）第一級(jí)頁表項(xiàng)第一級(jí)頁表項(xiàng) 第二級(jí)頁表項(xiàng)第二級(jí)頁表項(xiàng) 頁內(nèi)相對(duì)位移頁內(nèi)相對(duì)位移31021111頁=4KB,4GB虛擬空間共1M個(gè)頁面第768項(xiàng)第768項(xiàng)0頁1023頁1024頁2047頁第768塊7681024+768：2022-4-2510習(xí)題三習(xí)題三-

12、續(xù)二續(xù)二虛擬地址空間虛擬地址空間03G4MB頁表所在位置頁表所在位置（有（有1K個(gè)頁面）個(gè)頁面）二級(jí)頁表二級(jí)頁表一級(jí)頁表所在位置一級(jí)頁表所在位置768768頁表塊頁表塊即：即：76876810241024項(xiàng)開始項(xiàng)開始一級(jí)頁表一級(jí)頁表4KB共有共有1024項(xiàng)項(xiàng)每項(xiàng)占每項(xiàng)占4B共有共有1M1M個(gè)頁表項(xiàng)個(gè)頁表項(xiàng)1M1M4B4B大小大小=4MB=4MB大小大小.一個(gè)32位的虛擬存儲(chǔ)系統(tǒng)有兩級(jí)頁表，其邏輯地址中，第22到31位是第一級(jí)頁表，12位到21位是第二級(jí)頁表，頁內(nèi)偏移占0到11位。一個(gè)進(jìn)程的地址空間為4GB，如果從0XC0000000開始映射4MB大小頁表，請(qǐng)問第一級(jí)頁表所占的4KB空間映射在什

13、么位置，并說明理由。（注意B代表字節(jié)，一個(gè)32位地址占4字節(jié)）.第第0 0項(xiàng)項(xiàng)第第768768項(xiàng)項(xiàng)0 xC0000000+(0 xC000000012)2)= 0 xC0000000+0 x00300000=0 xC0300000第一級(jí)頁表所占的4KB空間的虛擬地址范圍是：0 xC03000000 xC300FFF2022-4-2511磁盤調(diào)度算法磁盤調(diào)度算法尋道時(shí)間尋道時(shí)間旋轉(zhuǎn)延遲時(shí)間旋轉(zhuǎn)延遲時(shí)間Ts= m n + s，尋道時(shí)間，尋道時(shí)間其中：其中：m為常數(shù)；為常數(shù)；n為移動(dòng)磁道數(shù)；為移動(dòng)磁道數(shù)；s為啟動(dòng)磁盤時(shí)間為啟動(dòng)磁盤時(shí)間Tr旋轉(zhuǎn)延遲時(shí)間：硬盤大約旋轉(zhuǎn)延遲時(shí)間：硬盤大約8.3ms，軟盤，

14、軟盤50ms100msTt 傳輸時(shí)間：讀傳輸時(shí)間：讀/寫數(shù)據(jù)的實(shí)際時(shí)間寫數(shù)據(jù)的實(shí)際時(shí)間=b/(rN)b:讀寫字節(jié)數(shù)；讀寫字節(jié)數(shù)；r:磁盤轉(zhuǎn)速；磁盤轉(zhuǎn)速；N:每條磁道上的字節(jié)數(shù)。每條磁道上的字節(jié)數(shù)。磁盤訪問時(shí)間磁盤訪問時(shí)間 Ta = Ts + Tr + Tt 2022-4-2512習(xí)題四：習(xí)題四：SSTF磁盤調(diào)度存在的問題磁盤調(diào)度存在的問題應(yīng)用應(yīng)用SSTF (shortest-seek-time-first)調(diào)調(diào)度策略，某些進(jìn)程可度策略，某些進(jìn)程可能永遠(yuǎn)不能被調(diào)度到能永遠(yuǎn)不能被調(diào)度到假定每當(dāng)在滿足磁道假定每當(dāng)在滿足磁道376上的信息請(qǐng)求之上的信息請(qǐng)求之前，系統(tǒng)總會(huì)接收到前，系統(tǒng)總會(huì)接收到一個(gè)新的

15、請(qǐng)求流，而一個(gè)新的請(qǐng)求流，而且這些請(qǐng)求所要移動(dòng)且這些請(qǐng)求所要移動(dòng)磁頭的距離總小于達(dá)磁頭的距離總小于達(dá)到磁道到磁道376所移動(dòng)的所移動(dòng)的距離，因而，對(duì)于距離，因而，對(duì)于376磁道和磁道和396磁道磁道上的信息請(qǐng)求將永遠(yuǎn)上的信息請(qǐng)求將永遠(yuǎn)得不到滿足。得不到滿足。試設(shè)計(jì)一種磁盤訪問調(diào)試設(shè)計(jì)一種磁盤訪問調(diào)度算法，以確保不會(huì)度算法，以確保不會(huì)發(fā)生諸如上例的發(fā)生諸如上例的“饑饑餓餓”現(xiàn)象?，F(xiàn)象。進(jìn)程號(hào)進(jìn)程號(hào)磁道號(hào)磁道號(hào)移動(dòng)磁道數(shù)移動(dòng)磁道數(shù)713401419258232051322561492940163229114191012190341811731563763733339620設(shè)：磁頭當(dāng)前位置為134磁

16、道，現(xiàn)有一磁盤讀寫請(qǐng)求隊(duì)列為：3、18、19、19、29、40、56、134、192、205、376、396，若采用SSTF優(yōu)先磁盤調(diào)度算法進(jìn)行調(diào)度，給出調(diào)度的次序。磁盤請(qǐng)求序列：3、18、19、19、29、40、56、134、192、205、376、396答：無饑餓現(xiàn)象的磁盤調(diào)度算法有答：無饑餓現(xiàn)象的磁盤調(diào)度算法有FCFS、掃描算法等等。、掃描算法等等。2022-4-2513習(xí)題五：磁盤空閑塊的成組分配算法習(xí)題五：磁盤空閑塊的成組分配算法 參看下圖，現(xiàn)有某一進(jìn)程的文件要釋放三個(gè)物理塊，其塊參看下圖，現(xiàn)有某一進(jìn)程的文件要釋放三個(gè)物理塊，其塊號(hào)為號(hào)為150#，152#，160#，試給出其釋放過程和釋放后的，試給出其釋放過程和釋放后的卷資源表卷資源表filsys的狀況。其后，又有一個(gè)文件要求分配的狀況。其后，又有一個(gè)文件要求分配4個(gè)個(gè)空閑塊，試給出其分配過程和分配后的空閑塊，試給出其分配過程和分配后的filsys狀況：狀況：s-nfree：980 1201 121 96 14597 210 卷資源表卷資源表filsyss-nfree：990 1201 121 96 14597 21098 150 s-nfree：1000 1201 121 96 14597 21098 15099 152 160#s-nfree：10 160