操作系統(tǒng)大題

1.這是一個(gè)從鍵盤輸入到打印機(jī)輸出的數(shù)據(jù)處理流圖，其中鍵盤輸入進(jìn)程通過緩沖區(qū)buf1把輸入數(shù)據(jù)傳送給計(jì)算進(jìn)程，計(jì)算進(jìn)程把處理結(jié)果通過緩沖buf2傳送給打印進(jìn)程。bufl和buf2為臨界資源，試寫出鍵盤輸入進(jìn)程，計(jì)算進(jìn)程及打印進(jìn)程間的同步算法。(10分)輸入進(jìn)程fbuflf計(jì)算進(jìn)程fbuf2f打印進(jìn)程解答：從鍵盤輸入到打印機(jī)輸出的數(shù)據(jù)傳送過程，可以看作是由鍵盤輸入進(jìn)程到計(jì)算進(jìn)程，以及由計(jì)算進(jìn)程到打印輸出進(jìn)程這兩個(gè)數(shù)據(jù)傳送進(jìn)程所組成。其中，對(duì)鍵盤輸入進(jìn)程而言，計(jì)算進(jìn)程是消費(fèi)者進(jìn)程；而對(duì)打印輸出進(jìn)程而言，計(jì)算進(jìn)程又是生產(chǎn)者進(jìn)程。據(jù)此可將它們之間的同步問題描述如下：var：mutexl，mutex2，emptyl，empty2，fulll，full2：=l，l，l，l，0，0；IP:beginrepeatP(empty);P(mutexl);inputacharcterfromkeyboard;Addtobuffer;V(mutexl);V(full);untilfalseendCP:beginrepeatP(full);P(mutexl);Takeacharactorformbufferl;Addtochl;V(mutexl);V(emptyl);P(empty2);P(mutex2);Takeacharactorformchl;Addtobuffer2;V(mutex2);V(full2);untilfalseendOP:beginrepeatp(full2);P(mutex2);Takeacharactorfrombuffer2;Addtoprintercontroler;startprinter;V(mutex2);

V(empty2);untilfalseend2．設(shè)在一個(gè)頁(yè)面大小為1K的系統(tǒng)中，正在處理器上執(zhí)行的一個(gè)進(jìn)程的頁(yè)表如圖所示：頁(yè)號(hào)狀態(tài)位訪問位修改位物理塊號(hào)01104111172000-310024000-51010起始頁(yè)號(hào)和塊號(hào)均為0。1．詳述在設(shè)有快表的請(qǐng)求分頁(yè)存儲(chǔ)管理系統(tǒng)中，一個(gè)虛地址轉(zhuǎn)換成物理內(nèi)存地址的過程2．下列虛地址（十進(jìn)制）對(duì)應(yīng)與什么物理地址：5449，2221。解：（10分）HhiiarDtnPu解：（10分）HhiiarDtnPu辭19ia]1Figure8.SOperationofPaging TraitslaIfunIjookasicleBuIE^fITLB；[FljRH87]5449的物理地址為：3292221的物理地址為：22213．設(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)程需要等待,哪些資源被剝奪。(10分)解：(10分)分配策略為：當(dāng)進(jìn)程pi申請(qǐng)r類資源時(shí)，檢査r中有無(wú)可分配的資源：有則分配給與否則將氣占有的資源全部釋放而進(jìn)入等待狀態(tài)。i等待原占有的所有資源和新申請(qǐng)的資源)②資源分配過程：剩余資源進(jìn)程A：(3,2,1)(1,0,1)進(jìn)程B：(1,0,1)(0,0,0)進(jìn)程A：(0,1,0)(不滿足)(3,2,1)A的所有資源被剝奪，A處于等待進(jìn)程C：(2,0,0)(1,2,1)C,B完成之后，A可完成。4．設(shè)公共汽車上,司機(jī)和售票員的活動(dòng)分別是司機(jī)：?jiǎn)?dòng)車輛正常行車到站停車售票員：上乘客關(guān)車門售票開車門、下乘客在汽車不斷地到站，停車，行使過程中，這兩個(gè)活動(dòng)有什么同步關(guān)系？并用wait和signal原語(yǔ)操作實(shí)現(xiàn)它們的同步。Stop:=0;Run:=0;解：BEGINintegerstop,run;COBEGINDriver:BEGINL1:wait(run);啟動(dòng)車輛；正常行車到站停車signal(stop);GotoL1;ENDConductor:BEGINL2：上乘客；關(guān)車門；signal(run);售票；wait(stop);開車門；下乘客；GotoL2;ENDCOENDEND5、某虛擬存儲(chǔ)器的用戶編程空間共321KB,內(nèi)存為16KB。假定某時(shí)刻一用戶頁(yè)表中已調(diào)入內(nèi)存的頁(yè)面的頁(yè)號(hào)和物理塊號(hào)的對(duì)照表如下：頁(yè)號(hào)物理塊號(hào)152103447則邏輯地址0A5C（H）所對(duì)應(yīng)的物理地址是什么？答：邏輯地址0A5CH）所對(duì)應(yīng)的二進(jìn)制表示形式是：0000101001011100由于1K=21Q下劃線部分前的編碼為000010，表示該邏輯地址對(duì)應(yīng)的頁(yè)號(hào)為3査頁(yè)表，得到物理塊號(hào)是4（十進(jìn)制），即物理塊地址為：0001001000000000，拼接塊內(nèi)地址0000000001011100，得0001001001011100,即125C（H）。6、某段表內(nèi)容如下：段號(hào)段首地址段長(zhǎng)度0120K40K1760K30K2480K20K3370K20K一邏輯地址為（2，154）的實(shí)際物理地址為多少？答：邏輯地址（2154）表示段號(hào)為2，即段首地址為480K，154為單元號(hào)，則實(shí)際物理地址為480K+154。7、設(shè)系統(tǒng)中有三種類型的資源（A,B，C）和五個(gè)進(jìn)程（P1,P2,P3,P4,P5），A資源的數(shù)量為17,B資源的數(shù)量為5,C資源的數(shù)量為20。在T0時(shí)刻系統(tǒng)狀態(tài)如表1和表2所示。（共10分）系統(tǒng)采用銀行家算法實(shí)施死鎖避免策略。T0時(shí)刻是否為安全狀態(tài)？若是,請(qǐng)給出安全序列。在T0時(shí)刻若進(jìn)程P2請(qǐng)求資源（0,3,4）,是否能實(shí)施資源分配？為什么？在②的基礎(chǔ)上，若進(jìn)程P4請(qǐng)求資源（2,0,1）,是否能實(shí)施資源分配？為什么？在③的基礎(chǔ)上，若進(jìn)程P1請(qǐng)求資源（0,2,0）,是否能實(shí)施資源分配？為什么？

最大資源需求量已分配資源數(shù)量ABCABCP1559212P2536402P34011405P4425204P5424314表2T0時(shí)刻系統(tǒng)狀態(tài)ABC剩余資源數(shù)2338?系統(tǒng)中有五個(gè)進(jìn)程P］、P2、P3、P4、P5,有三種類型的資源：R1、R2、和R3。在T0時(shí)刻系統(tǒng)狀態(tài)如表所示。若采用銀行家算法實(shí)施死鎖避免策略，回答下列問題：（共9分，每小題3分）1?T0時(shí)刻是否為安全狀態(tài)？為什么？若這時(shí)P4請(qǐng)求資源（1,2,0）,是否能實(shí)施資源分配？為什么？在上面的基礎(chǔ)上，若進(jìn)程P3請(qǐng)求資源（0,1,0），是否能實(shí)施資源分配？為什么？T0時(shí)刻系統(tǒng)狀態(tài)已分配資源數(shù)量最大資源需求量R1R2R3R1R2R3Pl001001P2200275P3003665P4115435P5033065R1R2R3剩余資源數(shù)330解：（共9分，每小題3分）T0時(shí)刻是安全的，安全序列為：P1,P4,P5,P2,P3P4請(qǐng)求資源（1，2，0），根據(jù)銀行家算法，預(yù)分配后系統(tǒng)是安全的，安全序列為：P1，P4，P5，P2，P3P3請(qǐng)求資源（1，1，0），根據(jù)銀行家算法，預(yù)分配后系統(tǒng)不安全，所以不能實(shí)施資源分配。9?一個(gè)進(jìn)程的大小占5個(gè)頁(yè)面，每頁(yè)的大小為1K,系統(tǒng)為它分配了3個(gè)物理塊。當(dāng)前進(jìn)程的頁(yè)表如圖所示：（共8分）塊號(hào)存在位P 訪問位R 修改位M0x1C1100x3F111■0000x5D100■0001． 有那些頁(yè)面不在內(nèi)存？（2分）2.請(qǐng)分別計(jì)算進(jìn)程中虛地址為0x3B7、0x12A5、0x1432單元的物理地址（用十六進(jìn)制表示），并說明理由。（6分）解：（共8分）不在內(nèi)存的是第2和4頁(yè)（按頁(yè)號(hào)），或第3和5頁(yè)（按序號(hào)）。（2分）Ox3B7的物理地址=0x73B7（2分）0x12A5的物理地址=0x176A5,缺頁(yè)，換出第三頁(yè)。（2分）0x1432地址越界，出錯(cuò)。（2分）10.系統(tǒng)運(yùn)行有三個(gè)進(jìn)程：輸入進(jìn)程、計(jì)算進(jìn)程和打印進(jìn)程，它們協(xié)同完成工作。輸入進(jìn)程和計(jì)算進(jìn)程之間共用緩沖區(qū)bufferl,計(jì)算進(jìn)程和打印進(jìn)程之間共用緩沖區(qū)buffer2。輸入進(jìn)程接收外部數(shù)據(jù)放入bufferl中;計(jì)算進(jìn)程從bufferl中取出數(shù)據(jù)進(jìn)行計(jì)算，然后將結(jié)果放入buffer2；打印進(jìn)程從buffer2取出數(shù)據(jù)打印輸出。用算法描述這三個(gè)進(jìn)程的工作情況，并用wait和signal原語(yǔ)實(shí)現(xiàn)其同步操作。（共8分）解：（共8分）解答：輸入進(jìn)程、計(jì)算進(jìn)程和打印進(jìn)程之間的同步問題描述如下：var：mutex1，mutex2，empty1，empty2，full1，full2：=1，1，1，1，0，0；InP:beginrepeatwait（empty1）;wait（mutex1）;inputadatafromkeyboard;Addtobuffer1;signal（mutex1）;signal（full1）;untilfalseendCalP:beginrepeatwait（full1）;wait（mutex1）;Takeadataformbuffer1;Addtoch1;signal（mutex1）;signal（empty1）;calculatech1;wait(empty2);wait(mutex2);Takeadataformch1;Addtobuffer2;signal(mutex2);signal(full2);untilfalseendOutP:beginrepeatwait(full2);wait(mutex2);Takeadatafrombuffer2;Addtoprintercontroler;signal(mutex2);signal(empty2);startprinter;untilfalseend（評(píng)分標(biāo)準(zhǔn)：信號(hào)量設(shè)置2分，輸入進(jìn)程、計(jì)算進(jìn)程、打印進(jìn)程各2分）11．在一個(gè)請(qǐng)求分頁(yè)系統(tǒng)中，有一個(gè)長(zhǎng)度為5頁(yè)的進(jìn)程，假如系統(tǒng)為它分配3個(gè)物理塊，并且此進(jìn)程的頁(yè)面走向?yàn)?，3，2，1，5，2，4，5，3，2，5，2。試用FIFO和LRU兩種算法分別計(jì)算出程序訪問過程中所發(fā)生的缺頁(yè)次數(shù)。（10分）解：FIFO：232152453252第1頁(yè)222555333第2頁(yè)33322255第3頁(yè)1114442缺頁(yè)中斷次數(shù)=6LUR：232152453252第1頁(yè)22225553第2頁(yè)3352335第3頁(yè)114422缺頁(yè)中斷次數(shù)=512.進(jìn)程A1，A2，?，An通過K個(gè)緩沖區(qū)向進(jìn)程B1，B2，?，Bm不斷地發(fā)送消息。發(fā)送和接收工作遵循如下規(guī)則：1．每個(gè)發(fā)送進(jìn)程一次發(fā)送一個(gè)消息，寫入緩沖區(qū)，緩沖區(qū)大小與消息長(zhǎng)度一致；2.對(duì)每個(gè)消息，B1,B2,…，Bm都需接收一次，讀入各自的數(shù)據(jù)區(qū)內(nèi)；3．K個(gè)緩沖區(qū)都滿時(shí)，發(fā)送進(jìn)程等待，沒有可讀的消息時(shí)，接收進(jìn)程等待。試用wait和signal原語(yǔ)操作組織正確的發(fā)送和接收操作。（10分）解：BEGINIntegerMutex,Avail[n],Full[m];IntegerI;Mutex:=1;FORi:=1TOmDOBEGINAvail[I]:=k;Full[I]:=0;ENDPROCEDURESend(K)IntegerI;BEGIN13．一個(gè)進(jìn)程的大小為5個(gè)頁(yè)面，為它分配了四個(gè)物理塊。當(dāng)前每個(gè)塊的情況如下表所示（都為十進(jìn)制數(shù)，且從0開始計(jì)數(shù)。）。當(dāng)虛頁(yè)4發(fā)生缺頁(yè)時(shí)，使用下列的頁(yè)面置換算法，哪一個(gè)物理塊將被換出？并解釋原因．（10分）頁(yè)號(hào)塊號(hào)加載時(shí)間訪問時(shí)間 訪問位R修改位M2060161011113016000022616210332016311IFO算法LRU算法CLOCK算法當(dāng)頁(yè)面的訪問串為：“4,0,0,0,2,4,2,1,0,3,2”的OPT算法解：1.換出第3號(hào)虛頁(yè)，因?yàn)樗虞d的時(shí)間最早；換出第1號(hào)虛頁(yè),因?yàn)樗罱罹脹]被訪問；換出第1號(hào)虛頁(yè),因?yàn)樗罱葲]被訪問,又沒被修改；換出第3號(hào)虛頁(yè),因?yàn)樗x訪問點(diǎn)最遠(yuǎn)。14.用整型信號(hào)量描述在哲學(xué)家進(jìn)餐問題中,至多允許4個(gè)哲學(xué)家同時(shí)進(jìn)餐的算法（。10分）解：publicclassdiningphilosophers{semaphore[]fork=newsemaphore[5]（1）;semaphoreroom=newsemaphore（4）;inti;voidphilosopher(inti){while(true)think();wait(room);wait(fork[i]);wait(fork[(i+1)%5]);eat();signal(fork[(i+1)%5]);signal(fork[i]);signal(room);}voidmain(){parbegin(philosopher(0),philosopher(1),philosopher(2),philosopher(3),philosopher(4));}}15．考慮一個(gè)有150個(gè)存儲(chǔ)器單元的系統(tǒng)，如下分配給三個(gè)進(jìn)程：進(jìn)程最大占有TOC\o"1-5"\h\z70 4560 4060 15使用銀行家算法，以確定下面的任何一個(gè)請(qǐng)求是否安全：第4個(gè)進(jìn)程到達(dá)，最多需要60個(gè)存儲(chǔ)單元，最初需要25個(gè)單元;第4個(gè)進(jìn)程到達(dá)，最多需要60個(gè)存儲(chǔ)單元，最初需要35個(gè)單元;如果安全給出安全序列；若不安全給出結(jié)果分配簡(jiǎn)表。（10分）解：進(jìn)程 最大 占有 尚需 可用

170452525260402036015454602535安全序列為：1、2、3、4所以系統(tǒng)是安全的，可以進(jìn)行分配。b．進(jìn)程最大占有尚需可用170452515260402036015454603525當(dāng)前可用的資源不夠任何一個(gè)進(jìn)程運(yùn)行完畢，所以不安全。16.Jruassic公園有一個(gè)恐龍博物館和一個(gè)公園?有m個(gè)旅客和n輛車，每輛車只能容納一個(gè)旅客。旅客在博物館逛了一會(huì)兒，然后排隊(duì)乘坐旅行車。當(dāng)一輛車可用時(shí)，它載入一個(gè)旅客，然后繞公園行駛?cè)我忾L(zhǎng)的時(shí)間。如果n輛車都已被旅客乘坐游玩，則想坐車的旅客需要等待；如果一輛車已經(jīng)就緒，但沒有旅客等待，那么這輛車等待。使用信號(hào)量同步m個(gè)旅客和n輛車的進(jìn)程。（10分）解：visitors=m; cars=n;mutex=1;Pvi()Pci(){repeat{repeatwait(cars);wait(visitors);wait(mutex);wait(mutex);geton;start;travell;run;getoff;stop;signal(cars);signal(visitors);wait(mutex);wait(mutex);untilfalse;untilfalse;}}17.讀者與寫者問題（reader--writerproblems） （10分）在計(jì)算機(jī)體系中，對(duì)一個(gè)共享文件進(jìn)行操作的進(jìn)程可分為兩類：讀操作和寫操作，它們分別被稱為讀者和寫者。訪問該文件時(shí)讀者和寫者，寫者和寫者間必須實(shí)現(xiàn)互斥。只有在沒有讀者訪問文件時(shí)，寫者才允許修改文件?；蛘邔懻咴谛薷奈募r(shí)不允許讀者去讀，否則會(huì)造成讀出的文件內(nèi)容不正確。試寫出算法描述讀者和寫者的問題。解：為了實(shí)現(xiàn)讀者與寫者的同步和互斥，我們?cè)O(shè)置一個(gè)信號(hào)量S，用于讀者與寫者之間或?qū)懻吲c讀者之間的互斥，初值為“1”用一個(gè)變量rc表示當(dāng)前正在讀的讀者個(gè)數(shù)，當(dāng)進(jìn)程可以去讀或讀結(jié)束后都要改變r(jià)c的值，因此rc又成為若干讀進(jìn)程的共享變量，它們必須互斥地修改rc。故必須定義另一個(gè)用于互斥的信號(hào)量Sr,初值也是“1”讀者--寫者問題可描述如下：S,Sr：semaphoreS,Sr：semaphore；intrc=0;processReaderI(i=1,2,...,m)S=Sr=1;processWriterj(j=1,2,...,k)beginP(S);beginP(S);WritefileF;V(S);endP(Sr);rc=rc+1;if(rc==1)P(S);V(Sr);readfileF;P(Sr); rc=tc-1;if(rc==0)V(S);V(Sr);end18、若干個(gè)等待訪問磁盤者依次要訪問的磁道為20，44，40，4，80，12，76，假設(shè)每移動(dòng)一個(gè)磁道需要3毫秒時(shí)間，移動(dòng)臂當(dāng)前位于40號(hào)柱面，請(qǐng)按下列算法分別寫出訪問序列并計(jì)算為完成上述各次訪問總共花費(fèi)的尋道時(shí)間。（1）先來先服務(wù)算法；（2）最短尋道時(shí)間優(yōu)先算法。（3）掃描算法（當(dāng)前磁頭移動(dòng)的方向?yàn)榇诺肋f增）（10分）解：（1）磁道訪問順序?yàn)椋?0，44，40，4，80，12，76尋道時(shí)間=（20+24+4+36+76+68+64）*3=292*3=876（2）磁道訪問順序?yàn)椋?0，44，20，12，4，76，80尋道時(shí)間=（0+4+24+8+8+72+4）*3=120*3=360（3）磁道訪問順序?yàn)椋?0，44，76，80，20，12，4尋道時(shí)間=（0+4+32+4+60+8+8）*3=116*3=34819、生產(chǎn)者和消費(fèi)者問題（10分）有一組生產(chǎn)者P1,P2,……,PM和一組消費(fèi)者C1,C2,……,CK,他們通過由n個(gè)環(huán)形緩沖區(qū)構(gòu)成的緩沖池進(jìn)行通信，生產(chǎn)者把產(chǎn)品放入緩沖區(qū)，消費(fèi)者從緩沖區(qū)取產(chǎn)品來消費(fèi)。請(qǐng)用wait和signal原語(yǔ)實(shí)現(xiàn)他們的同步操作。解：生產(chǎn)者和消費(fèi)者問題beginVarmutex,empty,full:semaphore:=1,n,0;buffer:array[O,??-mofitem;in,out:integer:=0,0;parbeginproducer:beginrepeatproducenextproduct;wait(empty);wait(mutex);buffer(in):=nextp;in:=(in+1)modn;signal(full);signal(mutex);untilfalse;endconsumer:beginrepeatwait(full);wait(mutex);nextc:=buffer(out);out:=(out+1)modn;signal(empty);signal(mutex);consumetheiteminnextc;untilfalse;endparendend20、請(qǐng)用信號(hào)量描述哲學(xué)家進(jìn)餐問題。(15分)解：哲學(xué)家進(jìn)餐問題(15分)publicvoidphilosopher(inti){while(true){think();wait(fork[i]);wait(fork[(i+1)%5]);eat();signal(fork[(i+1)%5]);signal(fork[i]);}}今有三個(gè)并發(fā)進(jìn)程R,M,P,它們共享了一個(gè)可循環(huán)使用的緩沖區(qū)B,緩沖區(qū)B共有N個(gè)單元。進(jìn)程R負(fù)責(zé)從輸入設(shè)備讀信息，每讀一個(gè)字符后，把它存放在緩沖區(qū)B的一個(gè)單元中；進(jìn)程M負(fù)責(zé)處理讀入的字符,若發(fā)現(xiàn)讀入的字符中有空格符,則把它改成“,”；進(jìn)程P負(fù)責(zé)把處理后的字符取出并打印輸出。當(dāng)緩沖區(qū)單元中的字符被進(jìn)程P取出后，則又可用來存放下一次讀入的字符。請(qǐng)用PV操作為同步機(jī)制寫出它們能正確并發(fā)執(zhí)行的程序。(10分)解：(10分)beginVarmutex,input,calculate,output:semaphore:=1,n,0,0;buffer:array[O,??-inofitem;in,mid,out:integer:=0,0,0;proR(){do{wait(input);wait(mutex);buffer(in):=inputdata;in:=(in+1)modn;signal(calculate);

signal(mutex);whiletrue;}proM(){do{wait(calculate);wait(mutex);buffer(middle):=calculatedata;mid:=(mid+1)modn;signal(output);signal(mutex);}whiletrue; }proP(){do{wait(output);wait(mutex);buffer(out):=calculatedata;out:=(out+1)modn;signal(input);signal(mutex);}whiletrue;}理發(fā)店里有一位理發(fā)師、一把理發(fā)椅子和五把供等候理發(fā)的顧客坐的椅子。如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺。當(dāng)一個(gè)顧客到來時(shí)，他必須先叫醒理發(fā)師，如果理發(fā)師正在理發(fā)時(shí)又有顧客來到，而如果有空椅子可坐，他們就坐下來等，如果沒有空椅子，他就離開。這里的問題是為理發(fā)師和顧客各編寫一段程序來描述他們行為，并用wat和signal原語(yǔ)操作實(shí)現(xiàn)其同步。(10分)解：理發(fā)師問題#defineCHAIRS5typedefintsemaphore;semphorecustomers=0;semaphorebarbers=0semaphoremutex=1;intwaiting=0;voidbarber(void){while(TRUE){wait(customers);wait(mutex);#defineCHAIRS5typedefintsemaphore;semphorecustomers=0;semaphorebarbers=0semaphoremutex=1;intwaiting=0;voidbarber(void){while(TRUE){wait(customers);wait(mutex);waiting=waiting-1;signal(barbers);signal(mutex);cut_hair();}voidcustomers(void){wait(mutex);if(waiting<CHAIRS){/*為等候的顧客準(zhǔn)備椅子數(shù)*//*運(yùn)用你的想像力*//*等候服務(wù)的顧客數(shù)*//*等候服務(wù)的理發(fā)師數(shù)*//*用于互斥*//*還沒理發(fā)的等候顧客*//*如果顧客數(shù)是0，則睡覺*//*要求進(jìn)程等候*//*等候顧客數(shù)減1*//*一個(gè)理發(fā)師現(xiàn)在開始理發(fā)*//*釋放等候*//*理發(fā)(非臨界區(qū)操作)*/waiting=waiting+1;signal(customers);signal(mutex);wait(barbers);}else{signal(mutex);}}23、根據(jù)如下的前趨圖寫出可并發(fā)執(zhí)行的程序：(10分)解：(10)評(píng)分：變量、進(jìn)程、程序主體每項(xiàng)一分。vara,b,c,d,e,f,g,h,i:semaphore:=0,0,0,0,0,0,0,0;beginparbeginbeginS1;signal(a);signal(b);endbeginwait(a);S2;signal(c);signal(d);endbeginwait(c);S3;signal(e);signal(f);endbeginwait(b);S4;signal(g);endbeginwait(d);wait(e)S5;signal(h);endbeginwait(f);wait(g);S6;signal(i);endbeginwait(h);wait(i);S7;endparendend24、在公共汽車上，乘客上完后，售票員關(guān)門，駕駛員開車，售票員售票，到站汽車停穩(wěn)后，售票員開門，乘客上下車，售票員和駕駛員之間密切配合，直到下班。請(qǐng)用信號(hào)量描述公共汽車上售票員與駕駛員的工作過程。(10分)解：建立駕駛員和售票員兩進(jìn)程，駕駛員進(jìn)程執(zhí)行過程如下：1)判售票員關(guān)門沒有2)開車3)到站后停車（4） 重復(fù)（1）－（3）售票員執(zhí)行過程如下：（1） 判斷乘客上完沒有（2） 關(guān)門（3） 售票（4） 判車停穩(wěn)沒有（5） 開門（6） 重復(fù)（1）－（5）評(píng)分標(biāo)準(zhǔn)：執(zhí)行過程完善3分，駕駛員與售票員合作消息正確3分售票員與駕駛員合作消息正確3分書寫格式1分25、設(shè)某作業(yè)占有7個(gè)頁(yè)面，如果在主存中只允許裝入4個(gè)工作頁(yè)面（即工作集為4），作業(yè)運(yùn)行時(shí)，實(shí)際訪問頁(yè)面的順序是：1，2，3，6，4，7，3，2，1，4，7，5，6，5，2，1。試用FIFO、LRU和CLOCK頁(yè)面置換算法，列出各自的頁(yè)面淘汰順序和頁(yè)面置換次數(shù)。（10分）解：FIFO：1，2，3，6，4，7，3，2，1，4，7，5，6，5，2，11111444455222277776333322226666111頁(yè)面置換次數(shù)為：6次LRU：1，2，3，6，4，7，3，2，1，4，7，5，6，5，2，111114441111666222277744442233333337777166622225555頁(yè)面置換次數(shù)為：10次CLOCK：1，2，3，6，4，7，3，2，1，4，7，5，6，5，2，111114441111666222277744442233333337777166622225555頁(yè)面置換次數(shù)為：10次26、某車站售票廳，任何時(shí)刻最多可容納20名購(gòu)票者進(jìn)入，當(dāng)售票廳中少于20名購(gòu)票者時(shí)，則廳外的購(gòu)票者可立即進(jìn)入，否則需在外面等待。若把一個(gè)購(gòu)票者看作一個(gè)進(jìn)程，請(qǐng)回答下列問題：（1）用wait和signal操作管理這些并發(fā)進(jìn)程時(shí)，應(yīng)怎樣定義信號(hào)量，寫出信號(hào)量的初值以及信號(hào)量各種取值的含義。⑵根據(jù)所定義的信號(hào)量，加上wait和signal原語(yǔ)，寫出購(gòu)票者進(jìn)程的算法，以保證進(jìn)程能夠正確地并發(fā)執(zhí)行。(3)若欲購(gòu)票者最多為n個(gè)人,寫出信號(hào)量可能的變化范圍(最大值和最小值)。解：(1)定義一信號(hào)量S,初始值為20。意義：S>0S的值表示可繼續(xù)進(jìn)入售 票廳的人數(shù)S=0表示售票廳中已有20名顧 客(購(gòu)票者)S<0|S|的值為等待進(jìn)入售票 廳的人數(shù)intS=20;COBEGINPROCESSPI(I=1,2,??)begin進(jìn)入售票廳；wait(S)；購(gòu)票；signal(S);退出；end；COENDS的最大值為20S的最小值為20－n設(shè)正在處理器上執(zhí)行的一個(gè)進(jìn)程的頁(yè)表如下表所示,表中的虛頁(yè)號(hào)和物理塊號(hào)是十進(jìn)制數(shù),起始頁(yè)號(hào)(塊號(hào))均為0。所有的地址均是存儲(chǔ)器字節(jié)地址。頁(yè)的大小為1024字節(jié)。(10分)詳述在設(shè)有快表的請(qǐng)求分頁(yè)存儲(chǔ)管理系統(tǒng)中，一個(gè)虛地址轉(zhuǎn)換成物理內(nèi)存地址的過程。下列虛地址對(duì)應(yīng)于什么物理地址：5499,2221。進(jìn)程的頁(yè)表解：4邏輯地址J44聯(lián)想存儲(chǔ)器P--7號(hào)*①」0r5499的物理地址為：3792221的物理地址為：3*1024+173=324528、假定系統(tǒng)有三個(gè)并發(fā)進(jìn)程read,move和print共享緩沖器B1和B2。進(jìn)程read負(fù)責(zé)從輸入設(shè)備上讀信息，每讀出一個(gè)記錄后把它存放到緩沖器B1中。進(jìn)程move從緩沖器B1中取出一記錄，加工后存入緩沖器B2。進(jìn)程print將B2中的記錄取出打印輸出。緩沖器B1和B2每次只能存放一個(gè)記錄。要求三個(gè)進(jìn)程協(xié)調(diào)完成任務(wù)，使打印出來的與讀入的記錄的個(gè)數(shù)，次序完全一樣。請(qǐng)用wait和signal原語(yǔ)寫出它們的并發(fā)程序。(10分)解：beginSR,SM1,SM2,SP:semaphore;B1,B2:record;SR:=1;SM1:=0;SM2:=1;SP:=0CobeginprocessreadX:record;beginR:(接收來自輸入設(shè)備上一個(gè)記錄)X:=接收的一個(gè)記錄；waiut(SR)；B1:=X;signal(SM1);gotoR;end;ProcessmoveY:record;Begi