【正文】 程口1 ）能知道C 值是否改變，改變的話(huà)在繼承改變了的C 值的基礎(chǔ)上，再作自己的改變操作，則就不會(huì)導(dǎo)致共享變量C 值的錯(cuò)誤。 執(zhí)行”測(cè)試、比較和交換”指令。loop2 : ( R1 ) → R3 。 13 請(qǐng)你設(shè)計(jì)一種先進(jìn)的計(jì)算機(jī)體系結(jié)構(gòu)，它使用硬件而不是中斷來(lái)完成進(jìn)程切換，則CPU 需要哪些信息？請(qǐng)描述用硬件完成進(jìn)程切換的工作過(guò)程。ABCDE 10 6 2 48 20l64 l220 302261628 33 .6634 3. 5 作業(yè)平均周轉(zhuǎn)時(shí)間作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間 T = ( 30 + 22 + 6 + 16 + 28 ) / 5 = W = ( 3 + + 3 +4 + ) / 5 = （1) FCFs （按A 、B 、C 、D 、E ) 。若采用時(shí)間片長(zhǎng)度為Q 的時(shí)間片輪轉(zhuǎn)法，對(duì)下列各種情況算出CPU 利用率。＋…＋Sn’為一個(gè)確定的數(shù)，而當(dāng)S1 ’≤S2 ’≤…≤ S( n 1 ) ’≤Sn ’時(shí)才有：0*S1+1*S2+2*S3+…（n1）Sn的值最大，也就是說(shuō)，此時(shí)T 值最小。 若有一組作業(yè)J1 ，… ，Jn ，其執(zhí)行時(shí)間依次為S1 ，… , Sn 。3 并發(fā)進(jìn)程之間有什么樣的相互制約關(guān)系？下列日常生活中的活動(dòng)是屬哪種制約關(guān)系：(1）踢足球，(2）吃自助餐，(3）圖書(shū)館借書(shū)，(4）電視機(jī)生產(chǎn)流水線(xiàn)工序。若時(shí)鐘中斷頻率為60HZ ，試問(wèn)CPU用于時(shí)鐘中斷處理的時(shí)間比率為多少？答：因時(shí)鐘中斷頻率為60HZ ，所以，時(shí)鐘周期為：l / 60s = 50/3ms 。程序C 為310ms 。各程序的計(jì)算軌跡為：A ：計(jì)算（20 ）、I/O( 30 ）、計(jì)算（10 ) B ：計(jì)算（40 ）、I/O( 20 ）、計(jì)算（10 ) c ：計(jì)算（10 ）、I/O ( 30 ）、計(jì)算（20 ) 如果三道程序都使用相同設(shè)備進(jìn)行I/O（即程序用串行方式使用設(shè)備，調(diào)度開(kāi)銷(xiāo)忽略不計(jì)）。 試求：( l ）每個(gè)作業(yè)從投入到完成分別所需的時(shí)間． ( 2 ）每個(gè)作業(yè)投入到完成CPU 的利用率。（2 ）從投入到完成CPU 的利用率。程序B 有等待時(shí)間段為180rns 至200ms 間（見(jiàn)圖中有色部分）3 設(shè)有三道程序，按A 、B 、C優(yōu)先次序運(yùn)行，其內(nèi)部計(jì)算和UO操作時(shí)間由圖給出。第一章作者：佚名 來(lái)源：網(wǎng)絡(luò)有一臺(tái)計(jì)算機(jī)，具有IMB 內(nèi)存，操作系統(tǒng)占用200KB ，每個(gè)用戶(hù)進(jìn)程各占200KB 。 試畫(huà)出按多道運(yùn)行的時(shí)間關(guān)系圖（忽略調(diào)度執(zhí)行時(shí)間）。（3 ）I2設(shè)備利用率。 （3 ）I/0設(shè)備利用率。試分別畫(huà)出單道和多道運(yùn)行的時(shí)間關(guān)系圖。 ( 3 ) CPU 利用率為（310 120 ) / 310 = % 有兩個(gè)程序，A 程序按順序使用：( CPU)10 秒、（設(shè)備甲）5 秒、（CPU）5 秒、（設(shè)備乙）10 秒、（CPU）10 秒。在每個(gè)時(shí)鐘周期中，CPU 花2ms 執(zhí)行中斷任務(wù)。答：并發(fā)進(jìn)程之間的基本相互制約關(guān)系有互斥和同步兩種。如果這些作業(yè)同時(shí)到試找出一種作業(yè)調(diào)度算法到達(dá)系統(tǒng)，并在一臺(tái)單CPU 處理器上按單道方式執(zhí)行。所以，按短作業(yè)優(yōu)先調(diào)度算法調(diào)度時(shí)，使得平均作業(yè)周轉(zhuǎn)時(shí)間最短。9 有5 個(gè)待運(yùn)行的作業(yè)，各自預(yù)計(jì)運(yùn)行時(shí)間分別是：9 、6 、3 、5 和x ，采用哪種運(yùn)行次序使得平均響應(yīng)時(shí)間最短？答：按照最短作業(yè)優(yōu)先的算法可以使平均響應(yīng)時(shí)間最短。 (2) 優(yōu)先級(jí)調(diào)度算法，(3）時(shí)間片輪轉(zhuǎn)法（每個(gè)作業(yè)獲得相同的2 分鐘長(zhǎng)的時(shí)間片）。 答：該計(jì)算機(jī)有一個(gè)專(zhuān)用硬件寄存器，它始終存放指向當(dāng)前運(yùn)行進(jìn)程的PCB 的指針。 Add /decrease R3 。 條件碼＝01 ，轉(zhuǎn)向循環(huán)loop2 ；否則離開(kāi)臨界區(qū)。為此，本解決方案中，當(dāng)一個(gè)進(jìn)程l）準(zhǔn)備改變C 值時(shí)，先把C 的值保護(hù)在Rl 中，然后，通過(guò)R3 來(lái)改變共享變量C 的值?，F(xiàn)有并發(fā)進(jìn)程P1 和P2 均申請(qǐng)使用磁帶機(jī)，執(zhí)行臨界區(qū)程序。于是伍1 ) = 2 , 跟著（R3 卜2 。因?yàn)樵诰途w隊(duì)列中的進(jìn)程比在CPU 上運(yùn)行的進(jìn)程的優(yōu)先數(shù)提高得快，故進(jìn)程切換時(shí)，先進(jìn)入就緒隊(duì)列的進(jìn)程優(yōu)先權(quán)就越高。 ( 2 ）但J4 到達(dá)時(shí)，因不滿(mǎn)足SJF ，故J4 不能被運(yùn)行，J3 繼續(xù)執(zhí)行5 分鐘。( 1 ）列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間。而由于作業(yè)A 的優(yōu)先級(jí)高于作業(yè)D ，故作業(yè)A 投入運(yùn)行 ( 6 ) 11 : 10 ，作業(yè)A 運(yùn)行結(jié)束，作業(yè)C 被調(diào)入內(nèi)存，具作業(yè)c 的優(yōu)先級(jí)高于作業(yè)D , 故作業(yè)C 投入運(yùn)行。 ( 3 ）周轉(zhuǎn)時(shí)間：作業(yè)1 為30 分鐘、作業(yè)2 為55 分鐘、作業(yè)3 為40 分鐘、作業(yè)4 為40 分鐘和作業(yè)5 為55 分鐘。但作業(yè)2 仍不能執(zhí)行，因不能移動(dòng)而沒(méi)有30KB 的空閑區(qū)，繼續(xù)等待。 2某多道程序設(shè)計(jì)系統(tǒng)采用可變分區(qū)內(nèi)存管理，供用戶(hù)使用的主存為200K ，磁帶機(jī)5 臺(tái)。( 4 ) 9 : 05 作業(yè)D 到達(dá)，磁帶機(jī)不夠，進(jìn)后備作業(yè)隊(duì)列等待。后備作業(yè)隊(duì)列還有C 、E 。2 ．短作業(yè)優(yōu)先算法。作業(yè)C 仍因主存不夠而等在后備隊(duì)列。作業(yè)平均周轉(zhuǎn)時(shí)間為58 分鐘。答：組織如下的定時(shí)喚醒隊(duì)列 。 sread : semaPhore : = k 。 process writer 。 mptr:=(mptr+1) mod k。Goto L1。 sPut1 : semaphore:=k。 cobegin process reader 。 x : = B [get2]。 manage the message into x。End。 x:=1。 V(S2)。⑦P(s2)。 這時(shí)z 的值只可能是y ＋1=5 ，故y =Z＋Y=5 + 4=9，而x = 10 。} mutex , seatcount : semaphore 。 V(seatcount)。 for i=1 to 100 do i++if name[i] ==null then name[i]:= readername。 name:＝null 。答1 ：實(shí)質(zhì)上是兩個(gè)進(jìn)程的同步問(wèn)題，設(shè)信號(hào)量s1 和s2 分別表示可揀白子和黑子，不失一般性，若令先揀白子。 揀黑子V (S1 ) 。 if flag then wait(sblack,IM ) 。flag :=false 。other 。答：在汽車(chē)行駛過(guò)程中，司機(jī)活動(dòng)與售票員活動(dòng)之間的同步關(guān)系為：售票員關(guān)車(chē)門(mén)后，向司機(jī)發(fā)開(kāi)車(chē)信號(hào)，司機(jī)接到開(kāi)車(chē)信號(hào)后啟動(dòng)車(chē)輛，在汽車(chē)正常行駛過(guò)程中售票員售票，到站時(shí)司機(jī)停車(chē)，售票員在車(chē)停后開(kāi)門(mén)讓乘客上下車(chē)。 } coend driver ( ) begin while ( 1 ) { P ( S1 )啟動(dòng)車(chē)輛；正常行車(chē)；到站停車(chē)； V ( S2 ) 。cobegin { process P1begin repeat 有顧客到來(lái)；P ( S1 )； 接受顧客點(diǎn)菜；V ( 52 )；untile false； end process P2 begin repeat P (S2 ) 。 ufltile false 。 E 。 until false 。 D 、A 、B 、E 、C。11 證明信號(hào)量與管程的功能是等價(jià)的： ( l ）用信號(hào)量實(shí)現(xiàn)管程； ( 2 ）用管程實(shí)現(xiàn)信號(hào)量。 } void leavemonitornormally ( )/*不發(fā)信號(hào)退出管程{ V ( mutex ) 。 condition 。 if C≤0 then signal ( S,IM ) 。 full , empty:condition 。 if count = 1 then sighal ( empty , IM ) 。 end begin r:= 0 。庫(kù)過(guò)程的功能是：把應(yīng)用進(jìn)程封鎖起來(lái)，所執(zhí)行的P 、V 操作的信息組織成消息，執(zhí)行send 發(fā)送給與信號(hào)量對(duì)應(yīng)的同步管理進(jìn)程，之后，再執(zhí)行receive 操作以接收同步管理進(jìn)程的應(yīng)答。15 試?yán)糜涗浶托盘?hào)量和P 、V 操作寫(xiě)出一個(gè)不會(huì)出現(xiàn)死鎖的五個(gè)哲學(xué)家進(jìn)餐問(wèn)題的算法。 } coend 。 flag[i]:= ip_cs 。 答：為方便描述，把Dijkstra 程序的語(yǔ)句進(jìn)行編號(hào)：repeat flag[i]:=want_in ；① while turn≠i do ② if flag[trun]==idle then turn:=i ；③ flag[i]: = in_cs ；④ j:= O 。注意到flag[i]＝in_cs 并不意味著turn的值一定等于i 。而進(jìn)程Pk 發(fā)現(xiàn)最終除自身外的所有進(jìn)程Pj 的flag[j]≠in_cs ，并據(jù)此可進(jìn)入其臨界區(qū)。答：( 1 ）用信號(hào)量和P 、v 操作。 取兩樣香煙原料放桌上，由flagi標(biāo)記； / * nago1 、nage2 、nage3 代表煙草、紙、火柴if flag2 amp。 吸香煙；untile false 。TYPE mskesmoke=moonitor VAR S, S1 ,S2 ,S3 : condition 。 flag3 then signal ( S2 ,IM ) 。 release （IM）。做香煙，吸香煙； until false 。試以P 、V 為操作工具，寫(xiě)出Pi（i=0…3）的同步工作算法答：var mutexl , mutexZ , mutex3 ，mutex0 :semaphore。 full0:=3。 V(mutex0)。 untile false 。 P(mutex2 ) 。 從M2[out2]取一條消息； out2:=(out2 + l ) mod 2。 V(full3) 。 加工消息；P ( empty0 ) 。Qj、Rk凡構(gòu)成另一對(duì)生產(chǎn)者和消費(fèi)者，共享一個(gè)由M2 個(gè)緩沖區(qū)構(gòu)成的循環(huán)緩沖池buf2 。 buffer2:array[0…M21]of item 。 put an item into buffer [in1] 。 counter++。 empty:=M2。答：var mutex1 , mutex2 , mutex3 : semaphore。 消息己MO[in0]。 endprocess P3 begin repeat P(full3) 。 V(empty2) 。In2:=(in2+1) mod 2。 P ( mutex1 ) 。 加工消息；P(empty1) 。in0,in1,in2,in3,out0 ,out2,out3,。Empty0,empty1,empty2, empty3。 做香煙，吸香煙； until false 。else 取原料 signal ( S ,IM ) 。 release ( IM ) 。 USE check , wait , signal , release 。 取原料； 做香煙； V(S) 。 / ＊供紙和火柴else if flag1 amp。 semaphore 。三個(gè)吸煙者在一個(gè)房間內(nèi)，還有一個(gè)香煙供應(yīng)者。但是若干個(gè)其他進(jìn)程是可能同時(shí)交替執(zhí)行的，假設(shè)讓進(jìn)程Pj(j=l , 2 , …nl）交錯(cuò)執(zhí)行語(yǔ)句① 后（這時(shí)flag[j]=want_in），再做語(yǔ)句② （第一個(gè)while 語(yǔ)句），來(lái)查詢(xún)flag[turn]的狀態(tài)。 (j==1 or flag[j] ≠in_cs ）⑤ do j:=j + 1 。 while (j n ) amp。 turn:integer 。 forki:=1 。如果信號(hào)量的值為負(fù)的話(huà)，執(zhí)行P 操作的應(yīng)用進(jìn)程被阻塞，掛到等待進(jìn)程隊(duì)列，所以，不再要送回答消息。 count:=0 。 end procedure get ( m ) 。 USE check , wait , signal , release 。 end begin C:=初值。 DEFINE P , V 。｛注意這時(shí)沒(méi)有開(kāi)放管程，因?yàn)閯倓偙会尫诺倪M(jìn)程己在管程中。下面介紹另一種簡(jiǎn)單方法：每一個(gè)管程都對(duì)應(yīng)一個(gè)mutex ，其初值為1 ，用來(lái)控制進(jìn)程互斥調(diào)用管程。 D 、A 、E 、B 、C 。答： ( 1 ）共有10 種交錯(cuò)執(zhí)行的路徑：A 、B 、C 、D 、E。 end : end 。S 閱表示共享資源正被進(jìn)程使用但沒(méi)有進(jìn)程等待使用資源。 untile false 。P ( S2 ) 開(kāi)車(chē)門(mén)； 上下乘客； } end 一個(gè)快餐廳有4 類(lèi)職員：( l ）領(lǐng)班：接受顧客點(diǎn)菜；( 2 ）廚師：準(zhǔn)備顧客的飯菜；( 3 ) 包工：將做好的飯菜打包；( 4 ）出納員：收款并提交食品。應(yīng)設(shè)置兩個(gè)信號(hào)量：S1 、S2 。other 。 signal ( Sblack,IM ) 。pickup a black。 end } coend . 答2 : TYPE pickupchess = MONITOR VAR flag : boolean 。 S1 : = l。 read the book 。 release ( IM ) 。 I,seatcount ：integer。 seatcount : = 100 。4 有一閱覽室，讀者進(jìn)入時(shí)必須先在一張登記表上登記，該表為每一座位列出一個(gè)表目，包括座號(hào)、姓名，讀者離開(kāi)時(shí)要注銷(xiāo)登記信息；假如閱覽室共有100 個(gè)座位。Y:=z+y。 z:=z+x。 x:=x+5。試問(wèn)：所采用的信號(hào)量初值是否相同？信號(hào)量值的變化范圍如何？答：所采用的互斥信號(hào)量初值不同。Goto L1。 get1 ：(get1+1 ) mod k 。 pr