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

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