操作系統(tǒng)計算題.doc

1. 這是一個從鍵盤輸入到打印機輸出的數(shù)據(jù)處理流圖,其中鍵盤輸入進程通過緩沖區(qū) buf1 把輸入數(shù)據(jù)傳送給計算進程,計算進程把處理結(jié)果通過緩沖 buf2 傳送給打印進程.buf1 和 buf2 為臨界資源,試寫出鍵盤輸入進程,計算進程及打印進程間的同步算法.(10分輸入進程 buf1 計算進程 buf2 打印進程從鍵盤輸入到打印機輸出的數(shù)據(jù)傳送過程,可以看作是由鍵盤輸入進程到計算進程,以及由計算進程到打印輸出進程這兩個數(shù)據(jù)傳送進程所組成.其中,對鍵盤輸入進程而言,計算進程是消費者進程。而對打印輸出進程而言,計算進程又是生產(chǎn)者進程.據(jù)此可將它們之間的同步問題描述如下:var:mutex1,mutex2,empty1,empty2,full1,full2:=1,1,1,1,0,0。IP:beginrepeatP(empty。P(mutex1。input a charcter from keyboard。Add to buffer。V(mutex1。V(full。until falseendCP:beginrepeatP(full。P(mutex1。Take a charactor form buffer1。Add to ch1。V(mutex1。V(empty1。P(empty2。P(mutex2。Take a charactor form ch1。Add to buffer2。V(mutex2。V(full2。until falseendOP:beginrepeat p(full2。P(mutex2。Take a charactor from buffer2。Add to printer controler。start printer。V(mutex2。V(empty2。until falseend2.設(shè)在一個頁面大小為 1K的系統(tǒng)中,正在處理器上執(zhí)行的一個進程的頁表如圖所示:起始頁號和塊號均為0.1.詳述在設(shè)有快表的請求分頁存儲管理系統(tǒng)中,一個虛地址轉(zhuǎn)換成物理內(nèi)存地址的過程.2.下列虛地址(十進制對應(yīng)與什么物理地址:5449,2221. b5E2RGbCAP解: (10分5449的物理地址為:3292221的物理地址為:22213.設(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請你給出一和防止死鎖的資源剝奪分配策略,完成上述請求序列,并列出資源分配過程,指明哪些進程需要等待,哪些資源被剝奪.(10分p1EanqFDPw 分配策略為:當進程Pi申請ri類資源時,檢查ri中有無可分配的資源:有則分配給Pi。否則將Pi占有的資源全部釋放而進入等待狀態(tài).(Pi等待原占有的所有資源和新申請的資源 DXDiTa9E3d 資源分配過程: 剩余資源進程A:(3,2,1 (1,0,1進程B:(1,0,1 (0,0,0進程A:(0,1,0(不滿足 (3,2,1RTCrpUDGiTA的所有資源被剝奪,A處于等待進程C:(2,0,0 (1,2,1C,B完成之后,A可完成.4.設(shè)公共汽車上,司機和售票員的活動分別是:司機: 啟動車輛 售票員: 上乘客正常行車 關(guān)車門到站停車 售票開車門下乘客5PCzVD7HxA在汽車不斷地到站,停車,行使過程中,這兩個活動有什么同步關(guān)系 并用 wait和signal 原語操作實現(xiàn)它們的同步. jLBHrnAILg解:BEGIN integer stop,run。Stop:=0。Run:=0。COBEGINDriver: BEGINL1: wait(run。啟動車輛。正常行車。到站停車。signal(stop。Goto L1。ENDConductor: BEGINL2: 上乘客。關(guān)車門。signal(run。售票。wait(stop。開車門。下乘客。Goto L2。ENDCOENDEND5,某虛擬存儲器的用戶編程空間共321KB,內(nèi)存為16KB.假定某時刻一用戶頁表中已調(diào)入內(nèi)存的頁面的頁號和物理塊號的對照表如下:xHAQX74J0X則邏輯地址0A5C(H所對應(yīng)的物理地址是什么 邏輯地址0A5CH所對應(yīng)的二進制表示形式是:0000 1010 0101 1100 ,由于1K=210,下劃線部分前的編碼為000010,表示該邏輯地址對應(yīng)的頁號為3查頁表,得到物理塊號是4(十進制,即物理塊地址為:0001 0010 0000 0000 ,拼接塊內(nèi)地址0000 0000 0101 1100,得0001 0010 0101 1100,即125C(H.LDAYtRyKfE6,某段表內(nèi)容如下:段號0123段首地址120K760K480K370K段長度40K30K20K20K一邏輯地址為(2,154的實際物理地址為多少 答:邏輯地址(2154表示段號為2,即段首地址為480K,154為單元號,則實際物理地址為480K+154.Zzz6ZB2Ltk10.系統(tǒng)運行有三個進程:輸入進程,計算進程和打印進程,它們協(xié)同完成工作.輸入進程和計算進程之間共用緩沖區(qū)buffer1,計算進程和打印進程之間共用緩沖區(qū)buffer2.輸入進程接收外部數(shù)據(jù)放入buffer1中。計算進程從buffer1中取出數(shù)據(jù)進行計算,然后將結(jié)果放入buffer2。打印進程從buffer2取出數(shù)據(jù)打印輸出.dvzfvkwMI1用算法描述這三個進程的工作情況,并用wait和signal原語實現(xiàn)其同步操作.(共8分解:(共8分解答:輸入進程,計算進程和打印進程之間的同步問題描述如下:var:mutex1,mutex2,empty1,empty2,full1,full2:=1,1,1,1,0,0。InP:beginrepeatwait(empty1。wait(mutex1。input a data from keyboard。Add to buffer1。signal(mutex1。signal(full1。until falseendCalP:beginrepeatwait(full1。wait(mutex1。Take a data form buffer1。Add to ch1。signal(mutex1。signal(empty1。calculate ch1。wait (empty2。wait(mutex2。Take a data form ch1。Add to buffer2。signal (mutex2。signal (full2。until falseendOutP:beginrepeat wait(full2。wait(mutex2。Take a data from buffer2。Add to printer controler。signal(mutex2。signal(empty2。start printer。until falseend11.在一個請求分頁系統(tǒng)中,有一個長度為 5 頁的進程,假如系統(tǒng)為它分配 3 個物理塊 ,并且此進程的頁面走向為 2,3,2,1,5,2,4,5,3,2,5,2.試用 FIFO 和 LRU 兩種算法分別計算出程序訪問過程中所發(fā)生的缺頁次數(shù).(10分rqyn14ZNXI解:FIFO:2 3 2 1 5 2 4 5 3 2 5 2第1頁 2 2 2 5 5 5 3 3 3第2頁 3 3 3 2 2 2 5 5第3頁 1 1 1 4 4 4 2缺頁中斷次數(shù) = 6LUR:2 3 2 1 5 2 4 5 3 2 5 2第1頁 2 2 2 2 5 5 5 3第2頁 3 3 5 2 3 3 5第3頁 1 1 4 4 2 2缺頁中斷次數(shù) = 512. 進程 A1,A2,An 通過 K 個緩沖區(qū)向進程 B1,B2,Bm 不斷地發(fā)送消息.發(fā)送和接收工作遵循如下規(guī)則:每個發(fā)送進程一次發(fā)送一個消息,寫入緩沖區(qū),緩沖區(qū)大小與消息長度一致。對每個消息,B1,B2,Bm 都需接收一次,讀入各自的數(shù)據(jù)區(qū)內(nèi)。K 個緩沖區(qū)都滿時,發(fā)送進程等待,沒有可讀的消息時,接收進程等待.試用 wait 和 signal 原語操作組織正確的發(fā)送和接收操作.(10分EmxvxOtOco解:BEGINInteger Mutex, Availn, Fullm。Integer I。Mutex:=1。FOR i:=1 TO m DOBEGINAvailI := k。FullI := 0。ENDPROCEDURE Send(KInteger I。BEGIN14. 用整型信號量描述在哲學(xué)家進餐問題中,至多允許4個哲學(xué)家同時進餐的算法.(10分解:public class diningphilosophers semaphore fork = new semaphore 5 (1。semaphore room = new semaphore (4。int i。void philosopher (int i while (truethink(。wait (room。wait (forki。wait (fork (i+1 % 5。eat(。signal (fork (i+1 % 5。signal (forki。signal (room。 void main( parbegin (philosopher (0,philosopher (1,philosopher (2SixE2yXPq5philosopher (3, philosopher (4。 16. Jruassic 公園有一個恐龍博物館和一個公園.有m個旅客和n輛車,每輛車只能容納一個旅客.旅客在博物館逛了一會兒,然后排隊乘坐旅行車.當一輛車可用時,它載入一個旅客,然后繞公園行駛?cè)我忾L的時間.如果n輛車都已被旅客乘坐游玩,則想坐車的旅客需要等待。如果一輛車已經(jīng)就緒,但沒有旅客等待,那么這輛車等待.使用信號量同步m個旅客和n輛車的進程.(10分6ewMyirQFL解:visitors=m。 cars=n。 mutex=1。Pvi( Pci( repeat repeat wait(cars。 wait(visitors。wait(mutex。 wait(mutex。get on。 start。travell。 run。get off。 stop。signal(cars。 signal(visitors。wait(mutex。 wait(mutex。until false。 until false。 17.讀者與寫者問題 (reader - writer problems (10分在計算機體系中,對一個共享文件進行操作的進程可分為兩類:讀操作和寫操作,它們分別被稱為讀者和寫者.訪問該文件時讀者和寫者,寫者和寫者間必須實現(xiàn)互斥.只有在沒有讀者訪問文件時,寫者才允許修改文件.或者寫者在修改文件時不允許讀者去讀,否則會造成讀出的文件內(nèi)容不正確.試寫出算法描述讀者和寫者的問題.kavU42VRUs解: 為了實現(xiàn)讀者與寫者的同步和互斥,我們設(shè)置一個信號量S,用于讀者與寫者之間或?qū)懻吲c讀者之間的互斥,初值為1.用一個變量rc 表示當前正在讀的讀者個數(shù),當進程可以去讀或讀結(jié)束后都要改變rc 的值,因此rc 又成為若干讀進程的共享變量,它們必須互斥地修改rc.故必須定義另一個用于互斥的信號量Sr,初值也是1.讀者-寫者問題可描述如下:y6v3ALoS89S, Sr:semaphore。 int rc = 0。 S=Sr=1。process Reader I (i=1,2,.,m process Writer j (j=1,2,.,kbegin beginP(Sr。 rc = rc+1。 P(S。if (rc=1 P(S。 Write file F。V(Sr。 V(S。read file F。 end P(Sr。 rc = tc-1。if (rc=0 V(S。V(Sr。end18,若干個等待訪問磁盤者依次要訪問的磁道為20,44,40,4,80,12,76,假設(shè)每移動一個磁道需要3毫秒時間,移動臂當前位于40號柱面,請按下列算法分別寫出訪問序列并計算為完成上述各次訪問總共花費的尋道時間.M2ub6vSTnP(1先來先服務(wù)算法。 (2最短尋道時間優(yōu)先算法.(3掃描算法(當前磁頭移動的方向為磁道遞增(10分0YujCfmUCw解:(1磁道訪問順序為:20,44,40,4,80,12,76尋道時間=(20+24+4+36+76+68+64*3=292*3=876eUts8ZQVRd(2磁道訪問順序為:40,44,20,12,4,76,80尋道時間=(0+4+24+8+8+72+4*3=120*3=360sQsAEJkW5T(3磁道訪問順序為:40,44,76,80,20,12,4尋道時間=(0+4+32+4+60+8+8*3=116*3=348GMsIasNXkA19,生產(chǎn)者和消費者問題 (10分有一組生產(chǎn)者P1,P2,PM和一組消費者C1,C2,CK,他們通過由n個環(huán)形緩沖區(qū)構(gòu)成的緩沖池進行通信,生產(chǎn)者把產(chǎn)品放入緩沖區(qū),消費者從緩沖區(qū)取產(chǎn)品來消費.請用wait和signal原語實現(xiàn)他們的同步操作.TIrRGchYzg解:生產(chǎn)者和消費者問題beginVar mutex,empty,full:semaphore:=1,n,0。buffer:array0,n-1 of item。in,out:integer := 0,0。parbeginproducer: beginrepeatproduce next product 。wait (empty。wait (mutex。buffer(in:=nextp 。in := (in+1 mod n 。signal (full。signal (mutex。until false 。endconsumer: beginrepeatwait (full。wait (mutex。nextc := buffer(out。out := (out+1 mod n。signal (empty。signal (mutex。consume the item in nextc。until false 。endparend end20,請用信號量描述哲學(xué)家進餐問題.(15分解:public void philosopher (int i while (true think(。wait (forki。wait (fork (i+1 % 5。eat(。signal(fork (i+1 % 5。signal(forki。 21.今有三個并發(fā)進程R,M,P,它們共享了一個可循環(huán)使用的緩沖區(qū)B,緩沖區(qū)B共有N個單元.進程R負責從輸入設(shè)備讀信息,每讀一個字符后,把它存放在緩沖區(qū)B的一個單元中。進程M負責處理讀入的字符,若發(fā)現(xiàn)讀入的字符中有空格符,則把它改成,。進程P負責把處理后的字符取出并打印輸出.當緩沖區(qū)單元中的字符被進程P取出后,則又可用來存放下一次讀入的字符.請用PV操作為同步機制寫出它們能正確并發(fā)執(zhí)行的程序. (10分7EqZcWLZNX解:beginVar mutex,input,calculate,output:semaphore:=1,n,0,0。buffer:array0,n-1 of item。in,mid,out:integer := 0,0,0。proR( do wait (input。wait (mutex。buffer(in:=input data。in := (in+1 mod n 。signal (calculate。signal (mutex。while true 。 proM( do wait (calculate。wait (mutex。buffer(middle:=calculate data 。mid := (mid+1 mod n 。signal (output。signal (mutex。 while true 。 proP( do wait (output。wait (mutex。buffer(out:=calculate data 。out := (out+1 mod n 。signal (input。signal (mutex。 while true 。 22.理發(fā)店里有一位理發(fā)師,一把理發(fā)椅子和五把供等候理發(fā)的顧客坐的椅子.如果沒有顧客,理發(fā)師便在理發(fā)椅上睡覺.當一個顧客到來時,他必須先叫醒理發(fā)師,如果理發(fā)師正在理發(fā)時又有顧客來到,而如果有空椅子可坐,他們就坐下來等,如果沒有空椅子,他就離開.這里的問題是為理發(fā)師和顧客各編寫一段程序來描述他們行為,并用wait和signal原語操作實現(xiàn)其同步.(10分lzq7IGf02E解:#define CHAIRS 5 /*為等候的顧客準備椅子數(shù)*/typedef int semaphore。 /* 運用你的想像力*/semphore customers=0。 /*等候服務(wù)的顧客數(shù)*/semaphore barbers=0 /*等候服務(wù)的理發(fā)師數(shù)*/semaphore mutex=1。 /*用于互斥*/int waiting=0。 /*還沒理發(fā)的等候顧客*/void barber (void while(TRUE wait(customers。 /*如果顧客數(shù)是0,則睡覺*/wait(mutex。 /*要求進程等候*/waiting=waiting-1。 /*等候顧客數(shù)減1*/ signal(barbers。 /*一個理發(fā)師現(xiàn)在開始理發(fā)*/signal(mutex。 /*釋放等候*/cut_hair(。 /*理發(fā)(非臨界區(qū)操作*/void customers (void wait(mutex。if (waiting0 S的值表示可繼續(xù)進入售 票廳的人數(shù) S=0 表示售票廳中已有20名顧 客(購票者 S int S=20。COBEGIN PROCESS PI(I=1,2,begin 進入售票廳。wait(S。購票。signal(S。退出。end。COEND(3S的最大值為20 S的最小值為20-n 28,假定系統(tǒng)有三個并發(fā)進程read, move和print共享緩沖器B1和B2.進程read負責從輸入設(shè)備上讀信息,每讀出一個記錄后把它存放到緩沖器B1中.進程move從緩沖器B1中取出一記錄,加工后存入緩沖器B2.進程print將B2中的記錄取出打印輸出.緩沖器B1和B2每次只能存放一個記錄.要求三個進程協(xié)調(diào)完成任務(wù),使打印出來的與讀入的記錄的個數(shù),次序完全一樣.請用wait和signal原語寫出它們的并發(fā)程序.(10分zvpgeqJ1hk解:begin SR,SM1,SM2,SP:semaphore。B1,B2:record。SR:=1。SM1:=0。SM2:=1。SP:=0Cobeginprocess readX:record。begin R:(接收來自輸入設(shè)備上一個記錄X:=接收的一個記錄。waiut(SR。B1:=X。signal(SM1。goto R。end。Process moveY:record。BeginM:wait(SM1。Y:=B1。signal(SR加工 Ywait(SM2。B2:=Y。signal(SP。goto M。end。Process printZ:record。BeginP:wait(SP。Z:=B2。signal(SM2打印Zgoto P。end。coend。end。29,考慮下述頁面走向:12,3,42,1,56,2,12,3,76,3,21,2,36當內(nèi)存塊數(shù)量分別為3時,試問FIFO,LRU,OPTNrpoJac3v1答:所有內(nèi)存塊最初都是空的,所以第一次用到的頁面都產(chǎn)生一次缺頁.FIFO 1,23,4,21,5,6,2,12,3,76,3,21,2,361 1 1 4 4 4 6 6 6 3 3 3 2 2 2 62 2 2 1 1 1 2 2 2 7 7 7 1 1 13 3 3 5 5 5 1 1 1 6 6 6 3 3發(fā)生缺頁中斷的次數(shù)為16在FIFO64,1,56之前調(diào)入的頁面,分別為5,1,24,可見4為最先進入內(nèi)存的,本次應(yīng)換出,然后把頁6 1nowfTG4KILRU 1,23,4,21,5,6,2,12,3,76,3,21,2,361 1 1 4 4 5 5 5 1 1 7 7 2 2 22 2 2 2 2 6 6 6 3 3 3 3 3 33 3 1 1 1 2 2 2 2 6 6 1 6發(fā)生缺頁中斷的次數(shù)為15在LRU65,2,16之前調(diào)入的頁面,分別為5,1,22為最近一段時間內(nèi)使用最少的,本次應(yīng)換出,然后把頁6調(diào)入內(nèi)存.fjnFLDa5ZoOPT 1,23,4,21,5,6,2,12,3,76,3,21,2,361 1 1 1 1 1 3 3 3 3 62 2 2 2 2 2 7 2 2 23 4 5 6 6 6 6 1 1發(fā)生缺頁中斷的次數(shù)為11在OPT61,2,56后面要調(diào)入的頁