【正文】 導(dǎo)致共享變量C 值的錯(cuò)誤。 執(zhí)行”測試、比較和交換”指令。R( condition = 01 ) loop2 。loop2 : ( R1 ) → R3 。解：( l ）設(shè)計(jì)機(jī)器指令。 13 請(qǐng)你設(shè)計(jì)一種先進(jìn)的計(jì)算機(jī)體系結(jié)構(gòu)，它使用硬件而不是中斷來完成進(jìn)程切換，則CPU 需要哪些信息？請(qǐng)描述用硬件完成進(jìn)程切換的工作過程。12 (l）假定一個(gè)處理器正在執(zhí)行兩道作業(yè)，一道以計(jì)算為主，另一道以輸入輸出為主，你將怎樣賦予它們占有處理器的優(yōu)先級(jí)？為什么？(2）假定一個(gè)處理器正在執(zhí)行三道作業(yè)，一道以計(jì)算為主，第二道以輸入輸出為主，第三道為計(jì)算與輸入輸出均勻。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 ) 。(對(duì)l）每個(gè)作業(yè)獲得相同的2 分鐘長的時(shí)間片；對(duì)2）到4）采用單道運(yùn)行，直到結(jié)束。若采用時(shí)間片長度為Q 的時(shí)間片輪轉(zhuǎn)法，對(duì)下列各種情況算出CPU 利用率。 （2）計(jì)算每種情況下作業(yè)的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。＋…＋Sn’為一個(gè)確定的數(shù)，而當(dāng)S1 ’≤S2 ’≤…≤ S( n 1 ) ’≤Sn ’時(shí)才有：0*S1+1*S2+2*S3+…（n1）Sn的值最大，也就是說，此時(shí)T 值最小。 ，… ，Jn , 創(chuàng)門的運(yùn)行時(shí)間滿足：S1≤S2 ≤……≤S (nl ) ≤ Sn ’。 若有一組作業(yè)J1 ，… ，Jn ，其執(zhí)行時(shí)間依次為S1 ，… , Sn 。在處理器不斷地在進(jìn)程之間交替的情況下，重新計(jì)算進(jìn)程優(yōu)先數(shù)的時(shí)間從何而來？答：許多操作系統(tǒng)重新計(jì)算進(jìn)程的優(yōu)先數(shù)在時(shí)鐘中斷處理例程中進(jìn)行，由于中斷是隨機(jī)碰到哪個(gè)進(jìn)程，就插入哪個(gè)進(jìn)程中運(yùn)行處理程序，并把處理時(shí)間記在這個(gè)進(jìn)程的賬上。3 并發(fā)進(jìn)程之間有什么樣的相互制約關(guān)系？下列日常生活中的活動(dòng)是屬哪種制約關(guān)系：(1）踢足球，(2）吃自助餐，(3）圖書館借書，(4）電視機(jī)生產(chǎn)流水線工序。 (5）置特殊寄存器：(6）改變存儲(chǔ)器映象圖；(7）啟動(dòng)I/O指令。若時(shí)鐘中斷頻率為60HZ ，試問CPU用于時(shí)鐘中斷處理的時(shí)間比率為多少？答：因時(shí)鐘中斷頻率為60HZ ，所以，時(shí)鐘周期為：l / 60s = 50/3ms 。程序B 執(zhí)行了40 秒，其中CPU 用了15 秒。程序C 為310ms 。CPU 利用率為（14030 ) / 140 = % 7 若內(nèi)存中有3 道程序A 、B 、C ，優(yōu)先級(jí)從高到低為A 、B 和C ，它們單獨(dú)運(yùn)行時(shí)的CPU 和I/O 占用時(shí)間為：如果三道程序同時(shí)并發(fā)執(zhí)行，調(diào)度開銷忽略不計(jì)，但優(yōu)先級(jí)高的程序可中斷優(yōu)先級(jí)低的程序，優(yōu)先級(jí)與I/O 設(shè)備無關(guān)。各程序的計(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)度開銷忽略不計(jì)）。所以CPU利用率為( 9020 ) / 90 = ％。 試求：( l ）每個(gè)作業(yè)從投入到完成分別所需的時(shí)間． ( 2 ）每個(gè)作業(yè)投入到完成CPU 的利用率。設(shè)備I1 空閑時(shí)間段為：20ms 至40ms , 90ms 至100ms,故I1的利用率為 (11030)/l10 = 72 . 7 ％。（2 ）從投入到完成CPU 的利用率。忽略調(diào)度執(zhí)行時(shí)間，多道運(yùn)行方式（非搶占式）: 非搶占式共用去180ms ，單道完成需要260ms ，節(jié)省80ms 。程序B 有等待時(shí)間段為180rns 至200ms 間（見圖中有色部分）3 設(shè)有三道程序，按A 、B 、C優(yōu)先次序運(yùn)行，其內(nèi)部計(jì)算和UO操作時(shí)間由圖給出。程序A 的運(yùn)行軌跡為：計(jì)算50ms 、打印100ms 、再計(jì)算50ms 、打印100ms ，結(jié)束。第一章作者：佚名 來源：網(wǎng)絡(luò)有一臺(tái)計(jì)算機(jī)，具有IMB 內(nèi)存，操作系統(tǒng)占用200KB ，每個(gè)用戶進(jìn)程各占200KB 。程序B 的運(yùn)行軌跡為：計(jì)算50ms 、輸入80ms 、再計(jì)算100ms ，結(jié)束。 試畫出按多道運(yùn)行的時(shí)間關(guān)系圖（忽略調(diào)度執(zhí)行時(shí)間）。2 ）調(diào)度執(zhí)行時(shí)間1ms , 多道運(yùn)行方式（搶占式）: 調(diào)度執(zhí)行時(shí)間ITns ，多道運(yùn)行方式（非搶占式）: 4在單CPU 和兩臺(tái) I/O( I1 , 12 ）設(shè)備的多道程序設(shè)計(jì)環(huán)境下，同時(shí)投入三個(gè)作業(yè)運(yùn)行。（3 ）I2設(shè)備利用率。 設(shè)備I2 空閑時(shí)間段為：30ms 至50ms，故I2的利用率為(11020) / 110 = ％。 （3 ）I/0設(shè)備利用率。( 3 ）設(shè)備I1 空閑時(shí)間段為：20ms 至40ms ，故I1 的利用率為（9020 ) / 90 = 77 . 78 ％。試分別畫出單道和多道運(yùn)行的時(shí)間關(guān)系圖。試畫出多道運(yùn)行的時(shí)間關(guān)系圖，并問最早與最遲結(jié)束的程序是哪個(gè)？每道程序執(zhí)行到結(jié)束分別用了多少時(shí)間？計(jì)算三個(gè)程序全部運(yùn)算結(jié)束時(shí)的CPU 利用率？答：畫出三個(gè)作業(yè)并發(fā)執(zhí)行的時(shí)間圖： ( l ）最早結(jié)束的程序?yàn)锽 ，最后結(jié)束的程序?yàn)镃 。 ( 3 ) CPU 利用率為（310 120 ) / 310 = % 有兩個(gè)程序，A 程序按順序使用：( CPU)10 秒、（設(shè)備甲）5 秒、（CPU）5 秒、（設(shè)備乙）10 秒、（CPU）10 秒。兩個(gè)程序共用了80 秒，CPU 化 40 秒。在每個(gè)時(shí)鐘周期中，CPU 花2ms 執(zhí)行中斷任務(wù)。答：( 3 ) , ( 4 ) , ( 5 ) , ( 6 ) , ( 7 ) .2 假設(shè)有一種低級(jí)調(diào)度算法是讓“最近使用處理器較少的進(jìn)程”運(yùn)行，試解釋這種算法對(duì)“I/O 繁重”型作業(yè)有利，但并不是永遠(yuǎn)不受理“處理器繁重”型作業(yè)。答：并發(fā)進(jìn)程之間的基本相互制約關(guān)系有互斥和同步兩種。5 若后備作業(yè)隊(duì)列中等待運(yùn)行的同時(shí)有三個(gè)作業(yè)J1 、JJ3 ，已知它們各自的運(yùn)行時(shí)間為a 、b 、c，且滿足a b ＜c，試證明采用短作業(yè)優(yōu)先算法調(diào)度能獲得最小平均作業(yè)周轉(zhuǎn)時(shí)間。如果這些作業(yè)同時(shí)到試找出一種作業(yè)調(diào)度算法到達(dá)系統(tǒng)，并在一臺(tái)單CPU 處理器上按單道方式執(zhí)行。那么有：由于任何調(diào)度方式下，S139。所以，按短作業(yè)優(yōu)先調(diào)度算法調(diào)度時(shí)，使得平均作業(yè)周轉(zhuǎn)時(shí)間最短。 ( 1 ）采用FCFS 算法調(diào)度作業(yè)，運(yùn)作情況： ( 2 ）采用雙算法調(diào)度作業(yè)，若令時(shí)間片長＝l ，各作業(yè)執(zhí)行情況為：1 、2 、3 、4 、5 、l 、3 、5 、1 、5 、1 、5 、1 、5 、1 、l 、l 、1 、1 。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í)間最短。）答：( l ) FCFS 調(diào)度算法 ( 2 ）優(yōu)先級(jí)調(diào)度算法( 3 ）時(shí)間片輪轉(zhuǎn)法按次序ABCDEBCDECDEDEE 輪轉(zhuǎn)執(zhí)行。 (2) 優(yōu)先級(jí)調(diào)度算法，(3）時(shí)間片輪轉(zhuǎn)法（每個(gè)作業(yè)獲得相同的2 分鐘長的時(shí)間片）。應(yīng)該如何賦予它們占有處理器的優(yōu)先級(jí)使得系統(tǒng)效率較高？答：處理器調(diào)度算法會(huì)考慮以下因素：作業(yè)響應(yīng)時(shí)間要求；讓CPU 盡量和外圍設(shè)備并行工作；限制一個(gè)計(jì)算進(jìn)程長時(shí)間霸占處理器。 答：該計(jì)算機(jī)有一個(gè)專用硬件寄存器，它始終存放指向當(dāng)前運(yùn)行進(jìn)程的PCB 的指針。設(shè)計(jì)一條如下的”測試、比較和交換”三地址指令，提供了一種硬件互斥解決方案： TCamp。 Add /decrease R3 。 共享變量C 的值保護(hù)到RI 中。 條件碼＝01 ，轉(zhuǎn)向循環(huán)loop2 ；否則離開臨界區(qū)。( 3 ）程序執(zhí)行說明。為此，本解決方案中，當(dāng)一個(gè)進(jìn)程l）準(zhǔn)備改變C 值時(shí)，先把C 的值保護(hù)在Rl 中，然后，通過R3 來改變共享變量C 的值。此外，在進(jìn)程進(jìn)入臨界區(qū)之前，應(yīng)等待直到C 為非。現(xiàn)有并發(fā)進(jìn)程P1 和P2 均申請(qǐng)使用磁帶機(jī)，執(zhí)行臨界區(qū)程序。 S 執(zhí)行”測試、比較和交換，, TC amp。于是伍1 ) = 2 , 跟著（R3 卜2 。 r ( conditio 二01 ) loop2 。答： 可見HRRF 比FIFO 要好 16 若有如表所示四個(gè)作業(yè)進(jìn)入系統(tǒng)，分別計(jì)算在FCFS 、S 開和HRR 衛(wèi)算法下的平均周轉(zhuǎn)時(shí)間與帶權(quán)平均周轉(zhuǎn)時(shí)間。因?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)就越高。（l ）分別給出6 個(gè)作業(yè)的執(zhí)行時(shí)間序列、即開始執(zhí)行時(shí)間、作業(yè)完成時(shí)間、作業(yè)周轉(zhuǎn)時(shí)間。 ( 2 ）但J4 到達(dá)時(shí)，因不滿足SJF ，故J4 不能被運(yùn)行，J3 繼續(xù)執(zhí)行5 分鐘。 ( 5 ）因J5 最短，故它第二個(gè)完成。( 1 ）列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間。( l ) 10 : 00 ，作業(yè)A 到達(dá)并投入運(yùn)行。而由于作業(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)行。平均作業(yè)周轉(zhuǎn)時(shí)間為70 分鐘。 ( 3 ）周轉(zhuǎn)時(shí)間：作業(yè)1 為30 分鐘、作業(yè)2 為55 分鐘、作業(yè)3 為40 分鐘、作業(yè)4 為40 分鐘和作業(yè)5 為55 分鐘。8 : oo 作業(yè)1 到達(dá)，占有資源并調(diào)入主存運(yùn)行。但作業(yè)2 仍不能執(zhí)行，因不能移動(dòng)而沒有30KB 的空閑區(qū)，繼續(xù)等待。作業(yè)5 到達(dá)時(shí)間晚，只能等待。 2某多道程序設(shè)計(jì)系統(tǒng)采用可變分區(qū)內(nèi)存管理，供用戶使用的主存為200K ，磁帶機(jī)5 臺(tái)。說明：( 1 ) 8 : 30 作業(yè)A 到達(dá)并投入運(yùn)行。( 4 ) 9 : 05 作業(yè)D 到達(dá)，磁帶機(jī)不夠，進(jìn)后備作業(yè)隊(duì)列等待。作業(yè)C 仍因主存不夠而等在后備隊(duì)列。后備作業(yè)隊(duì)列還有C 、E 。( 7 ) 9 : 55 作業(yè)D 運(yùn)行結(jié)束，作業(yè)C 投入運(yùn)行。2 ．短作業(yè)優(yōu)先算法。 ( 3 ) 9 : 00 作業(yè)C 到達(dá)，主存和磁帶機(jī)均不夠，進(jìn)后備作業(yè)隊(duì)列等待。作業(yè)C 仍因主存不夠而等在后備隊(duì)列。這時(shí)作業(yè)C 和E 資源均滿足，但按SJF 應(yīng)把作業(yè)E 調(diào)入主存進(jìn)就緒隊(duì)列等CPU 。作業(yè)平均周轉(zhuǎn)時(shí)間為58 分鐘。 2設(shè)計(jì)一個(gè)進(jìn)程定時(shí)喚醒隊(duì)列和定時(shí)喚醒處理程序：( l ）說明一個(gè)等待喚醒進(jìn)程入隊(duì)v 的過程。答：組織如下的定時(shí)喚醒隊(duì)列 。2一個(gè)實(shí)時(shí)系統(tǒng)有4 個(gè)周期性事件，周期分別為50 、100 、300 和250ms 。 sread : semaPhore : = k 。 mptr : integer : = O 。 process writer 。P ( sread ) 。 mptr:=(mptr+1) mod k。 V(sread)。Goto L1。 goto L2。 sPut1 : semaphore:=k。 put1 ：integer ：=O 。 cobegin process reader 。 L2 : P ( sgetl ) 。 x : = B [get2]。Put1:=(put1+1) mod k。 manage the message into x。 goto L3。End。當(dāng)沒有進(jìn)程進(jìn)入互斥段時(shí)，信號(hào)量值為1 ；當(dāng)有1 個(gè)進(jìn)程進(jìn)入互斥段但沒有進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為O ；當(dāng)有1 個(gè)進(jìn)程進(jìn)入互斥段且有一個(gè)進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為1 ；最多可能有n 1 個(gè)進(jìn)程等待進(jìn)入互斥段，故此時(shí)信號(hào)量的值應(yīng)為（n 1 ）也就是n+1 。 x:=1。 P(S1)。 V(S2)。 ⑤ y :=y+3 ；② x ：x+5 。⑦P(s2)。接著無論系統(tǒng)如何調(diào)度進(jìn)程并發(fā)執(zhí)行，當(dāng)執(zhí)行到語句⑦ 時(shí)，可以得到x = 10 , y = 4 。 這時(shí)z 的值只可能是y ＋1=5 ，故y =Z＋Y=5 + 4=9，而x = 10 。答：1 ）使用信號(hào)量和P 、v 操作：var name ：array [ l …100]of A 。} mutex , seatcount : semaphore 。 P （mutex ) 。 V(seatcount)。 DEFINE rcadere, readerleave 。 for i=1 to 100 do i++if name[i] ==null then name[i]:= readername。 seatcount。 name:＝null 。 leave the readroom。答1 ：實(shí)質(zhì)上是兩個(gè)進(jìn)程的同步問題，設(shè)信號(hào)量s1 和s2 分別表示可揀白子和黑子，不失一般性，若令先揀白子。cobegin { process P1 begin repeat P( S1 ) 。 揀黑子V (S1 ) 。DEFINE pickupblack , pickupwhite 。 if flag then wait(sblack,IM ) 。 release ( IM ) 。flag :=false 。 end begin flag:=true 。other 。答：可以采用形如waituntil ＜條件表達(dá)式＞的同步原語。答：在汽車行駛過程中，司機(jī)活動(dòng)與售票員活動(dòng)之間的同步關(guān)系為：售票員關(guān)車門后，向司機(jī)發(fā)開車信號(hào)，司機(jī)接到開車信號(hào)后啟動(dòng)車輛，在汽車正常行駛過程中售票員售票，到站時(shí)司機(jī)停車，售票員在車停后開門讓乘客上下車。S2 表示是否允許售票員開門（其初值為0 ）。 } coend driver ( ) begin while ( 1 ) { P ( S1