中大實踐考核操作系統(tǒng)實驗筆試試題和答案

操作系統(tǒng)實驗筆試1.P1,P2,P3T1,T2,T3100,150,350;執(zhí)行時間分別為20,40,100.試計算后回答是否可以用頻率單調(diào)調(diào)度算法進行調(diào)度?基本原理是頻率越低(周期越長)的任務(wù)的優(yōu)先級越低。這時，設(shè)任務(wù)周期為TCC<=Tn(n≥1)同任務(wù)來說，設(shè)每個周期為，其相應(yīng)任務(wù)的執(zhí)行時間為Ci,條件是:.對于由3個周期組成的實時任務(wù)序列來說，其執(zhí)行時間與周期之比應(yīng)是：.由于:所以,可以用頻率單調(diào)調(diào)度算法進行調(diào)度.2.100K,2臺,1臺,用可變分區(qū)方式管理主存,采用靜態(tài)分配方式分配磁帶機與打印機.忽略用戶作業(yè)I/O時間現(xiàn)有如下作業(yè)序列:作業(yè)號進入輸入井時間要求計算時間主存需求量磁帶機需求打印機需求18:0025分鐘15K1臺1臺28:2010分鐘30K0臺1臺38:2020分鐘60K1臺0臺48:3020分鐘20K1臺0臺58:3515分鐘10K1臺1臺作業(yè)調(diào)度策略先來先服務(wù),優(yōu)先分配主存的低地址區(qū)域且不準(zhǔn)移動已在主存的作業(yè),在主存中的各作業(yè)平分CPU時間,問題如下:(1)作業(yè)調(diào)度選中各作業(yè)的次序是什么? (2)全部作業(yè)運行結(jié)束的時刻是什么?(3)如果把一個作業(yè)從進入輸入井到運行結(jié)束的時間定義為周轉(zhuǎn)時間,在忽略系統(tǒng)開銷時條件下,最大的作業(yè)周轉(zhuǎn)時間是多? (4)平均周轉(zhuǎn)時間是多少?答：作業(yè)號裝入主存時間開始執(zhí)行時間執(zhí)行結(jié)束時間周轉(zhuǎn)時間18:008:008:2525分鐘28:459:059:1555分鐘38:208:258:4525分鐘48:308:459:0535分鐘59:159:159:3055分鐘(1)1,3,4,2,5(2)9:30(3)55分鐘(4)(25+55+25+35+55)/5=39(分鐘)樣題3.設(shè)有n個緩沖區(qū)構(gòu)成的循環(huán)緩沖區(qū)池,每個緩沖區(qū)能容納一個整數(shù).寫進程Writer把整數(shù)逐個存入緩沖區(qū)池,讀進程Reader則逐個從緩沖區(qū)池中讀出并打印輸出,要求打印的與輸入的完全一樣,即個數(shù),次序,數(shù)值一樣.試問:寫進程與讀進程間具體的制約關(guān)系如何?(2)用PV操作寫出這兩個進程的同步算法程序.答：(1)寫進程要領(lǐng)先于讀進程,但當(dāng)緩沖區(qū)全填滿時,要等讀進程取數(shù);讀進程要后于寫進程,當(dāng)緩沖去中無待讀的整數(shù)時,要等待寫進程寫數(shù).程序:beginB:array[0…n-1]ofintegerW,R:integer;SW,SR:Semaphore;W:=0;R:=0;SW:=n;SR:=0;cobeginPROCESSbeginL1:produceaintegerintoX;P(SW);B[W]:=X;W:=(W+1)modV(SR);gotoL1;end;PROCESSReaderbeginL2:P(SR)Y:=B[R];R:=(R+1)modnV(SW);Printy;gotoL2;end;coend;end;樣題4.某系統(tǒng)對主存采用頁式管理,供用戶使用的主存區(qū)域共640K字節(jié),被分成160塊,塊號為0,1,2......159.現(xiàn)有一作業(yè)的地址空間共占4頁,其頁號為0,1,2,3,被分配到主存的第2,4,1,5塊中,回答:作業(yè)每一頁的長度為多少字節(jié)? (2)寫出該作業(yè)被裝入主存時,其對應(yīng)的頁表.(3)把該作業(yè)的每一頁在主存中的起始地址(用16進制表示)填在下表頁號 起始地址0 0020001 0040002 0010003 005000（1）每一頁的長度為640K/160=4K字節(jié)5邏輯頁號主存塊號02145邏輯頁號主存塊號021421350214213樣題5.作業(yè)的調(diào)度算法有幾種?簡述各自的優(yōu)缺點.答：1、先來先服務(wù)算法.先來先服務(wù)算法是最簡單的調(diào)度算法，它是按照作業(yè)進入“輸入井”的先后次序來挑選作業(yè)，先進入的作業(yè)優(yōu)先被挑選。作業(yè)等待時間過長。2、計算時間短的作業(yè)優(yōu)先算法.得到滿足的作業(yè)。時間，可能使計算時間長的作業(yè)等待太久。3、響應(yīng)比最高者優(yōu)先算法.高的作業(yè)優(yōu)先裝入主存儲器。響應(yīng)比高者優(yōu)先算法綜合考慮作業(yè)的等待時間和計算時間。4、優(yōu)先數(shù)調(diào)度算法優(yōu)先數(shù)時，對這些具有相同優(yōu)先數(shù)的作業(yè)再按照先來先服務(wù)原則進行調(diào)度。5、均衡調(diào)度法資源的作業(yè)同時執(zhí)行。這樣不僅可以使系統(tǒng)的各種資源都在被使用，而且可以減少作業(yè)等待使用相同資源的時間，從而加快作業(yè)的執(zhí)行。6.100磁道,磁頭正向磁道號增加的方向移動.求隊列:22,374,202,127,13,54,182,389,19,4,7,28.若采用先來先服務(wù),最短尋道時間優(yōu)先和掃瞄算法,試計算出三種算法中,?(列出尋道次序和移動道數(shù))答：1、先來先服務(wù)調(diào)度算法使移動臂移動的次序和移動的柱面數(shù)如下:100→22→374→202→127→13→54→182→389→19→4→7→(78) (352) (172) (75) (114) (41)(128) (207) (370)(15)(3)(21)移動磁道總數(shù)為:1576.平均尋道長度為:131.2、最短尋道時間優(yōu)先調(diào)度算法使移動臂移動的次序和移動的柱面數(shù)如下:100→127→182→202→54→28→22→19→13→7→4→374→(27) (55) (20) (148) (26) (6) (3) (6) (6)(3) (370) (15)移動磁道總數(shù)為:685.平均尋道長度為:57.3、掃瞄調(diào)度算法使移動臂移動的次序和移動的柱面數(shù)如下:100→127→182→202→374→389→54→28→22→19→13→7→(27) (55) (20) (172) (15) (335) (26) (6) (3) (6) (6) (3)移動磁道總數(shù)為:674.平均尋道長度為:56.樣題7.設(shè)系統(tǒng)有三種類型的資,數(shù)量為(4,2,2),系統(tǒng)中有進程A,B,C按如下順序請求資源進程A申請(3,2,1) 進程B申請(1,0,1)進程A申請(0,1,0) 進程C申請(2,0,0)請給出一種防止死鎖的資源剝奪分配策略,完成上述請求序列,并列出資源分配過程,些進程需要等待,哪些資源被剝奪.經(jīng)占有了某些資源而又要申請新資源，而新資源不能滿足(已被其他進程占用)必須等待時,系統(tǒng)可以搶奪該進程已占有的資源。以下是資源分配過程：A所申請的資源（3，2，1；B的申請(1,0,1)也能滿足；A再次申請資源(0,1,0)A等待;C申請(2,0,0)時,資源已不能滿足,A占用的資源(2,0,0)C所需的資源得到滿足。AA的永遠等待.8.,一程序的頁面走向(訪問串或引用串)2,3,4,5,2,3,6,2,3,4,5,6,0.M.M=3M=4FIFOLRU兩種方法的缺頁數(shù)?答：1、FIFO調(diào)度算法頁面裝入和調(diào)出的情況如下:M=3時:2345236234560222555666666033322222444444433333555缺頁缺頁缺頁缺頁缺頁缺頁缺頁 缺頁缺頁 缺共產(chǎn)生10次缺頁中斷M=4時:23452362345602222226666555333333222266444444333305555554444缺頁缺頁缺頁缺頁 缺頁缺頁缺頁缺頁缺頁缺頁缺共產(chǎn)生11次缺頁中斷2、LRU調(diào)度算法頁面裝入和調(diào)出的情況如下:M=3時:2345236234560452362345603345236234562223452362345缺頁缺頁缺頁缺頁缺頁缺頁缺頁 缺頁缺頁缺頁缺共產(chǎn)生11次缺頁中斷M=4時:545432254332546325263532654326543265430654缺頁缺頁缺頁缺頁 缺頁 缺頁缺頁缺頁缺共產(chǎn)生9次缺頁中斷結(jié)果說明:FIFO不是堆棧算法,增大M不一定降低缺頁中斷次數(shù);LRU是堆棧算法,增大M可以降低缺頁中斷次數(shù).樣題9.當(dāng)前磁盤讀寫位于柱面號20,此時有多個磁盤請求以下柱面號順序送至磁盤驅(qū)動器:10,22,20,2,40,6,38.尋道(track)時,移動一個柱面需6ms,(柱面移動順序及所需時間,總尋道時間;忽略最近指定柱面后所需尋道時間)先到先服務(wù) (2)下一個最鄰近柱面 (3)電梯算法(當(dāng)前狀態(tài);向上答：1、先到先服務(wù)：磁頭移動順序為：20→10→22→20→2→40→6→38(10) (12) (2) (18)(38) (34)(32)所需時間:60ms 72ms 12ms 108ms 228ms 204ms 192ms磁頭移動總量是：146柱面總尋道時間是：876ms.2、下一個最鄰近柱面：磁頭移動順序為：20→20→22→10→6→2→38→40(0) (2) (12) (4) (4) (36) (2)所需時間:0ms 12ms 72ms 24ms 24ms 216ms 12ms磁頭移動總量是：60柱面，總尋道時間是：360ms.3、電梯算法磁頭移動順序為：20→22→38→40→10→6→2(2) (16) (2) (30) (4) (4)所需時間:12ms 96ms 12ms 180ms 24ms 24ms磁頭移動總量是：58柱面，總尋道時間是：348ms.樣題10.汽車司機與售票員之間必須協(xié)同工作,一方面只有售票員把車門關(guān)好了司機才能開車,因此,售票員關(guān)好車門應(yīng)通知司機開車.另一方面,只有當(dāng)汽車已經(jīng)停下,售票員才能開門上下客,故司機停車后應(yīng)通知售票員,汽車當(dāng)前正在始發(fā)站停車上客,試設(shè)必要的信號燈及賦初值,寫出他們的同步過程.(用管程或信號燈機制均可)答：SP:表示是否可以開門上下客,初值為”1”,表示正在始發(fā)站停車上客;SD:表示是否可以開車,初值為”0”,表示還在始發(fā)站停車上客;beginSP,SD:Semaphore;SP:=1;SD:=0;cobeginPROCESSPaybeginL1:P(SP);{開門上客};{關(guān)車門};V(SD);gotoL1;end;PROCESSbeginL2:P(SD){開車};{停車};V(SP);gotoL2;end;coend;end;11.P1,P2P3并發(fā)工作.P1S3S1;P2S1S2;P3