《操作系統(tǒng)第四版 課后習(xí)題答案.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《操作系統(tǒng)第四版 課后習(xí)題答案.doc（148頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

______________________________________________________________________________________________________________ 第一章 作者：佚名 來源：網(wǎng)絡(luò) 1、有一臺(tái)計(jì)算機(jī)，具有IMB 內(nèi)存，操作系統(tǒng)占用200KB ，每個(gè)用戶進(jìn)程各占200KB 。如果用戶進(jìn)程等待I/O 的時(shí)間為80 % ，若增加1MB 內(nèi)存，則CPU 的利用率提高多少？ 答：設(shè)每個(gè)進(jìn)程等待I/O 的百分比為P ，則n 個(gè)進(jìn)程同時(shí)等待刀O 的概率是Pn ，當(dāng)n 個(gè)進(jìn)程同時(shí)等待I/O 期間CPU 是空閑的，故CPU 的利用率為1-Pn。由題意可知，除去操作系統(tǒng)，內(nèi)存還能容納4 個(gè)用戶進(jìn)程，由于每個(gè)用戶進(jìn)程等待I/O的時(shí)間為80 % , 故： CPU利用率＝l-（80%)4 = 0.59 若再增加1MB 內(nèi)存，系統(tǒng)中可同時(shí)運(yùn)行9 個(gè)用戶進(jìn)程，此時(shí)：cPu 利用率＝l-（1-80%)9 = 0.87 故增加IMB 內(nèi)存使CPU 的利用率提高了47 % : 87 ％/59 ％=147 % 147 ％-100 % = 47 % 2 一個(gè)計(jì)算機(jī)系統(tǒng)，有一臺(tái)輸入機(jī)和一臺(tái)打印機(jī)，現(xiàn)有兩道程序投入運(yùn)行，且程序A 先開始做，程序B 后開始運(yùn)行。程序A 的運(yùn)行軌跡為：計(jì)算50ms 、打印100ms 、再計(jì)算50ms 、打印100ms ，結(jié)束。程序B 的運(yùn)行軌跡為：計(jì)算50ms 、輸入80ms 、再計(jì)算100ms ，結(jié)束。試說明（1 ）兩道程序運(yùn)行時(shí)，CPU有無空閑等待？若有，在哪段時(shí)間內(nèi)等待？為什么會(huì)等待？( 2 ）程序A 、B 有無等待CPU 的情況？若有，指出發(fā)生等待的時(shí)刻。 答：畫出兩道程序并發(fā)執(zhí)行圖如下： （1）兩道程序運(yùn)行期間，CPU存在空閑等待，時(shí)間為100 至150ms 之間（見圖中有色部分） （2）程序A 無等待現(xiàn)象，但程序B 有等待。程序B 有等待時(shí)間段為180rns 至200ms 間（見圖中有色部分） 3 設(shè)有三道程序，按A 、B 、C優(yōu)先次序運(yùn)行，其內(nèi)部計(jì)算和UO操作時(shí)間由圖給出。 試畫出按多道運(yùn)行的時(shí)間關(guān)系圖（忽略調(diào)度執(zhí)行時(shí)間）。完成三道程序共花多少時(shí)間？比單道運(yùn)行節(jié)省了多少時(shí)間？若處理器調(diào)度程序每次進(jìn)行程序轉(zhuǎn)換化時(shí)lms , 試畫出各程序狀態(tài)轉(zhuǎn)換的時(shí)間關(guān)系圖。 答： 1 ）忽略調(diào)度執(zhí)行時(shí)間,多道運(yùn)行方式（搶占式）: ? 搶占式共用去190ms ，單道完成需要260ms ，節(jié)省70ms 。 忽略調(diào)度執(zhí)行時(shí)間，多道運(yùn)行方式（非搶占式）: 非搶占式共用去180ms ，單道完成需要260ms ，節(jié)省80ms 。 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)行。它們的執(zhí)行軌跡如下： Jobl : I2 ( 30ms ）、CPU ( 10ms ）、I1 ( 30ms ）、CPU ( 10ms ）、I2 ( 20ms ) Job2 : I1 ( 20ms ）、CPU ( 20ms ）、I2 ( 40 ms ) JOb3 : CPU ( 30ms ）、I1 ( 20ms ）、CPU ( 10ms ）、I1 ( 10ms ) 如果CPU 、I1 和I2 都能并行工作，優(yōu)先級從高到低為Jobl 、Job2 和Job3 ，優(yōu)先級高的作業(yè)可以搶占優(yōu)先級低的作業(yè)的CPU ，但不搶占I1和I2 。試求：( l ）每個(gè)作業(yè)從投入到完成分別所需的時(shí)間。（2 ）從投入到完成CPU 的利用率。（3 ）I2設(shè)備利用率。 答：畫出三個(gè)作業(yè)并行工作圖如下（圖中著色部分為作業(yè)等待時(shí)間）: , ( 1 ) Job1 從投入到運(yùn)行完成需110ms , Job2 從投入到運(yùn)行完成需90ms , Job3 從投入到運(yùn)行完成需110ms. CPU 空閑時(shí)間段為：60ms 至70ms , 80ms 至90ms , 100ms 至110ms 。所以CPU 利用率為（110-30）/10 = 72.7 ％。 設(shè)備I1 空閑時(shí)間段為：20ms 至40ms , 90ms 至100ms,故I1的利用率為 (110-30)/l10 = 72 . 7 ％。 設(shè)備I2 空閑時(shí)間段為：30ms 至50ms，故I2的利用率為(110-20) / 110 = 81.8 ％。 5 在單CPU 和兩臺(tái)I/O( I1 , 12 ）設(shè)備的多道程序設(shè)計(jì)環(huán)境下，同時(shí)投入三個(gè)作業(yè)運(yùn)行。它們的執(zhí)行軌跡如下： Jobl : I2 ( 30ms ）、CPU ( 10rns ）、I1 ( 30ms ）、CPU ( 10ms ) Job2 : I1 ( 20ms ）、CPU ( 20ms ）、I2 ( 40ms ) Job3 : CPU ( 30ms ）、I1 ( 20ms ) 如果CPU 、I1和I2 都能并行工作，優(yōu)先級從高到低為Job1 、Job2和Job3 ，優(yōu)先級高的作業(yè)可以搶占優(yōu)先級低的作業(yè)的CPU 。 試求：( l ）每個(gè)作業(yè)從投入到完成分別所需的時(shí)間． ( 2 ）每個(gè)作業(yè)投入到完成CPU 的利用率。 （3 ）I/0設(shè)備利用率。 答：畫出三個(gè)作業(yè)并行工作圖如下（圖中著色部分為作業(yè)等待時(shí)間）: ( 1 ) Job1從投入到運(yùn)行完成需80ms , Job2 從投入到運(yùn)行完成需90ms , Job3 從投入到運(yùn)行完成需90ms 。 ( 2 ) CPU 空閑時(shí)間段為：60ms 至70ms , 80ms 至90ms 。所以CPU利用率為( 90-20 ) / 90 = 77.78 ％。 ( 3 ）設(shè)備I1 空閑時(shí)間段為：20ms 至40ms ，故I1 的利用率為（90-20 ) / 90 = 77 . 78 ％。設(shè)備I2 空閑時(shí)間段為：30ms 至50ms ，故I2 的利用率為（90-20 ) / 90=77.78 ％。 6 若內(nèi)存中有3 道程序A 、B 、C ，它們按A 、B 、C 優(yōu)先次序運(yù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ì)）。試分別畫出單道和多道運(yùn)行的時(shí)間關(guān)系圖。兩種情況下，CPU 的平均利用率各為多少？ 答：分別畫出單道和多道運(yùn)行的時(shí)間圖 ( 1 ）單道運(yùn)行時(shí)間關(guān)系圖 單道總運(yùn)行時(shí)間為190ms 。CPU 利用率為（190-80 ）/190 = 57.9 % 單道運(yùn)行時(shí)間關(guān)系圖 多道總運(yùn)行時(shí)間為140ms 。CPU 利用率為（140-30 ) / 140 = 78.6 % 7 若內(nèi)存中有3 道程序A 、B 、C ，優(yōu)先級從高到低為A 、B 和C ，它們單獨(dú)運(yùn)行時(shí)的CPU 和I/O 占用時(shí)間為： 如果三道程序同時(shí)并發(fā)執(zhí)行，調(diào)度開銷忽略不計(jì)，但優(yōu)先級高的程序可中斷優(yōu)先級低的程序，優(yōu)先級與I/O 設(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)镃 。 ( 2 ）程序A 為250ms 。程序B 為220ms 。程序C 為310ms 。 ( 3 ) CPU 利用率為（310 -120 ) / 310 = 61.3 % 有兩個(gè)程序，A 程序按順序使用：( CPU)10 秒、（設(shè)備甲）5 秒、（CPU）5 秒、（設(shè)備乙）10 秒、（CPU）10 秒。B程序按順序使用：（設(shè)備甲）10 秒、（CPU）10 秒、（設(shè)備乙）5 秒、( CPU)5 秒、（設(shè)備乙）10 秒。在順序環(huán)境下先執(zhí)行A ，再執(zhí)行B ，求出總的CPU 利用率為多少？ 答：程序A 執(zhí)行了40 秒，其中CPU 用了25 秒。程序B 執(zhí)行了40 秒，其中CPU 用了15 秒。兩個(gè)程序共用了80 秒，CPU 化 40 秒。故CPU 利用率為40/80 =50 ％。 9、在某計(jì)算機(jī)系統(tǒng)中，時(shí)鐘中斷處理程序每次執(zhí)行的時(shí)間為2ms （包括進(jìn)程切換開銷）。若時(shí)鐘中斷頻率為60HZ ，試問CPU用于時(shí)鐘中斷處理的時(shí)間比率為多少？ 答：因時(shí)鐘中斷頻率為60HZ ，所以，時(shí)鐘周期為：l / 60s = 50/3ms 。在每個(gè)時(shí)鐘周期中，CPU 花2ms 執(zhí)行中斷任務(wù)。所以，CPU 用于時(shí)鐘中斷處理的時(shí)間比率為：2(50/3)=6/50 = 12％。 首頁 入門學(xué)習(xí) 程序員 計(jì)算機(jī)考研 計(jì)算機(jī)電子書下載 硬件知識 網(wǎng)絡(luò)知識 專業(yè)課程答案下載 視頻教程下載 第二章 作者：佚名 來源：網(wǎng)絡(luò) 1.下列指令中哪些只能在核心態(tài)運(yùn)行？ (l）讀時(shí)鐘日期；(2）訪管指令；(3）設(shè)時(shí)鐘日期；(4）加載PSW; (5）置特殊寄存器：(6）改變存儲(chǔ)器映象圖；(7）啟動(dòng)I/O指令。 答：( 3 ) , ( 4 ) , ( 5 ) , ( 6 ) , ( 7 ) . 2 假設(shè)有一種低級調(diào)度算法是讓“最近使用處理器較少的進(jìn)程”運(yùn)行，試解釋這種算法對“I/O 繁重”型作業(yè)有利，但并不是永遠(yuǎn)不受理“處理器繁重”型作業(yè)。 答：因?yàn)镮/O繁忙型作業(yè)忙于I/O，所以它CPU 用得少，按調(diào)度策略能優(yōu)先執(zhí)行。同樣原因一個(gè)進(jìn)程等待CPU 足夠久時(shí)，由于它是“最近使用處理器較少的進(jìn)程”，就能被優(yōu)先調(diào)度，故不會(huì)饑餓。 3 并發(fā)進(jìn)程之間有什么樣的相互制約關(guān)系？下列日常生活中的活動(dòng)是屬哪種制約關(guān)系：(1）踢足球，(2）吃自助餐，(3）圖書館借書，(4）電視機(jī)生產(chǎn)流水線工序。 答：并發(fā)進(jìn)程之間的基本相互制約關(guān)系有互斥和同步兩種。其中（1）、（3）為互斥問題．(2）、(4）為同步問題。 4 在按動(dòng)態(tài)優(yōu)先數(shù)調(diào)度進(jìn)程的系統(tǒng)中，每個(gè)進(jìn)程的優(yōu)先數(shù)需定時(shí)重新計(jì)算。在處理器不斷地在進(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)程的賬上。 5 若后備作業(yè)隊(duì)列中等待運(yùn)行的同時(shí)有三個(gè)作業(yè)J1 、J2、J3 ，已知它們各自的運(yùn)行時(shí)間為a 、b 、c，且滿足a < b ＜c，試證明采用短作業(yè)優(yōu)先算法調(diào)度能獲得最小平均作業(yè)周轉(zhuǎn)時(shí)間。 答：采用短作業(yè)優(yōu)先算法調(diào)度時(shí)，三個(gè)作業(yè)的總周轉(zhuǎn)時(shí)間為： Tl = = a + ( a +b ) + ( a + b + c ) = 3a + 2b + c ① 若不按短作業(yè)優(yōu)先算法調(diào)度，不失一般性，設(shè)調(diào)度次序?yàn)椋篔2 、J1 、J3 。則三個(gè)作業(yè)的總周轉(zhuǎn)時(shí)間為： T2=b＋(b＋a ) ＋(b＋a + c ) = 3b + 2a + c ② 令②-① 式得到： T2 - Tl = b- a> 0 可見，采用短作業(yè)優(yōu)先算法調(diào)度才能獲得最小平均作業(yè)周轉(zhuǎn)時(shí)間。 6、若有一組作業(yè)J1 ，… ，Jn ，其執(zhí)行時(shí)間依次為S1 ，… , Sn 。如果這些作業(yè)同時(shí)到試找出一種作業(yè)調(diào)度算法到達(dá)系統(tǒng)，并在一臺(tái)單CPU 處理器上按單道方式執(zhí)行。使得平均作業(yè)周轉(zhuǎn)時(shí)間最短。 答：首先，對n 個(gè)作業(yè)按執(zhí)行時(shí)間從小到大重新進(jìn)行排序，則對n 個(gè)作業(yè)：J1 ' ，… ，Jn , 創(chuàng)門的運(yùn)行時(shí)間滿足：S1≤S2 ≤……≤S (n-l ) ≤ Sn ’。那么有： 由于任何調(diào)度方式下，S1' + S2' + S3'＋…＋Sn’為一個(gè)確定的數(shù)，而當(dāng)S1 ’≤S2 ’≤…≤ S( n - 1 ) ’≤Sn ’時(shí)才有：0*S1+1*S2+2*S3+…（n-1）Sn的值最大，也就是說，此時(shí)T 值最小。所以，按短作業(yè)優(yōu)先調(diào)度算法調(diào)度時(shí)，使得平均作業(yè)周轉(zhuǎn)時(shí)間最短。 7、 假定執(zhí)行表中所列作業(yè)，作業(yè)號即為到達(dá)順序，依次在時(shí)刻0 按次序1 、2 、3 、4 、5 進(jìn)入單處理器系統(tǒng)。 （1）分別用先來先服務(wù)調(diào)度算法、時(shí)間片輪轉(zhuǎn)算法、短作業(yè)優(yōu)先算法及非強(qiáng)占優(yōu)先權(quán)調(diào)度算法算出各作業(yè)的執(zhí)行先后次序（注意優(yōu)先權(quán)高的數(shù)值?。? （2）計(jì)算每種情況下作業(yè)的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(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 。 ( 3 ）采用SJF 算法調(diào)度作業(yè)，運(yùn)作情況： ( 4 ）采用非剝奪優(yōu)先權(quán)算法調(diào)度作業(yè)，運(yùn)作情況： 8 對某系統(tǒng)進(jìn)行監(jiān)測后表明平均每個(gè)進(jìn)程在I/O 阻塞之前的運(yùn)行時(shí)間為T 。一次進(jìn)程‘切換的系統(tǒng)開銷時(shí)間為S 。若采用時(shí)間片長度為Q 的時(shí)間片輪轉(zhuǎn)法，對下列各種情況算出CPU 利用率。 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í)間最短。x 取值不定，按照以下情況討論： 10.有5 個(gè)批處理作業(yè)A 到E 均己到達(dá)計(jì)算中心，其運(yùn)行時(shí)間分別2 、4 、6 、8 和10 分鐘：各自的優(yōu)先級分跳狠掀完為、、飛、飛、氏積5 、這里5 為最高級。對于1) 時(shí)間片輪轉(zhuǎn)算法、2）優(yōu)先數(shù)法、3）短作業(yè)優(yōu)先算法、4）先來先服務(wù)調(diào)度算法（按到達(dá)次序C 、D 、B 、E 、A) ，在忽略進(jìn)程切換時(shí)間的前提下，計(jì)算出平均作業(yè)周轉(zhuǎn)時(shí)間。(對l）每個(gè)作業(yè)獲得相同的2 分鐘長的時(shí)間片；對2）到4）采用單道運(yùn)行，直到結(jié)束。） 答：( l ) FCFS 調(diào)度算法 ( 2 ）優(yōu)先級調(diào)度算法 ( 3 ）時(shí)間片輪轉(zhuǎn)法 按次序ABCDEBCDECDEDEE 輪轉(zhuǎn)執(zhí)行。 ( 4 ) SJF調(diào)度算法 11、 有5 個(gè)批處理作業(yè)A 到E 均已到達(dá)計(jì)算中心，其運(yùn)行時(shí)間分別10 、6 、2 、4 和8 分鐘；各自的優(yōu)先級分別被規(guī)定為3 、5 、2 、1 和4 ，這里5 為最高級。若不考慮系統(tǒng)切換開銷，計(jì)算出平均作業(yè)周轉(zhuǎn)時(shí)間。（1) FCFs （按A 、B 、C 、D 、E ) ; (2) 優(yōu)先級調(diào)度算法，(3）時(shí)間片輪轉(zhuǎn)法（每個(gè)作業(yè)獲得相同的2 分鐘長的時(shí)間片）。 答： ( 1 ) FCFS 調(diào)度算法 ( 2 ）優(yōu)先級調(diào)度算法 ( 3 ）時(shí)間片輪轉(zhuǎn)法 按次序ABCDEABDEABEAEA 輪轉(zhuǎn)執(zhí)行。 作業(yè) 執(zhí)行時(shí)間 等待時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 ? ? ? ? ? A B C D E 10 6 2 4 8 20 l6 4 l2 20 30 22 6 16 28 3 3 .66 3 4 3. 5 作業(yè)平均周轉(zhuǎn)時(shí)間作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間 T = ( 30 + 22 + 6 + 16 + 28 ) / 5 = 20.4 W = ( 3 + 3.66 + 3 +4 + 3.5 ) / 5 = 3.43 ? ? ? ? 12 (l）假定一個(gè)處理器正在執(zhí)行兩道作業(yè)，一道以計(jì)算為主，另一道以輸入輸出為主，你將怎樣賦予它們占有處理器的優(yōu)先級？為什么？ (2）假定一個(gè)處理器正在執(zhí)行三道作業(yè)，一道以計(jì)算為主，第二道以輸入輸出為主，第三道為計(jì)算與輸入輸出均勻。應(yīng)該如何賦予它們占有處理器的優(yōu)先級使得系統(tǒng)效率較高？ 答：處理器調(diào)度算法會(huì)考慮以下因素：作業(yè)響應(yīng)時(shí)間要求；讓CPU 盡量和外圍設(shè)備并行工作；限制一個(gè)計(jì)算進(jìn)程長時(shí)間霸占處理器。因而，( 1 ) FO 為主作業(yè)優(yōu)先級高。（2 ) 輸入輸出為主作業(yè)優(yōu)先級最高，輸入輸出均勻的作業(yè)其次，而計(jì)算為主作業(yè)的優(yōu)先級最低。 13 請你設(shè)計(jì)一種先進(jìn)的計(jì)算機(jī)體系結(jié)構(gòu)，它使用硬件而不是中斷來完成進(jìn)程切換，則CPU 需要哪些信息？請描述用硬件完成進(jìn)程切換的工作過程。 答：該計(jì)算機(jī)有一個(gè)專用硬件寄存器，它始終存放指向當(dāng)前運(yùn)行進(jìn)程的PCB 的指針。當(dāng)系統(tǒng)中發(fā)生了一個(gè)事件，如FO 結(jié)束事件，CPU 便可把運(yùn)行進(jìn)程的上下文保存到專用硬件寄存器指針指向的PCB 中保護(hù)起來，然后，CPU 轉(zhuǎn)向中斷向量表，找到設(shè)備中斷處理程序入口，讓專用硬件寄存器指針指向（設(shè)備）中斷服務(wù)例程，于是，便可啟動(dòng)中斷服務(wù)例程工作。 14 設(shè)計(jì)一條機(jī)器指令和一種與信號量機(jī)制不同的算法，使得并發(fā)進(jìn)程對共享變量的使用不會(huì)出現(xiàn)與時(shí)間有關(guān)的錯(cuò)誤。 解： ( l ）設(shè)計(jì)機(jī)器指令。 設(shè)計(jì)一條如下的”測試、比較和交換”三地址指令，提供了一種硬件互斥解決方案： TC&S R1 R3 B2 D2 該指令的功能如下： l ) C 為一個(gè)共享變量，由地址2 、即變址（B2 ) + D2 給出， （2 ）（Rl ）與（C ）比較， （3 ）如果（Rl ) = ( C ）則（R3）→C ，并置條件碼為"00" , 如果（R1 ）≠（c ）則（C )→Rl ，并置條件碼為"01 " . ( 2 ）編寫進(jìn)程訪問共享變量的程序。 對每個(gè)訪問共享變量C 的進(jìn)程，編寫訪問共享變量的程序段為： 陸界區(qū)程序 說明 ( C ）→Rl ; loop2 : ( R1 ) → R3 ; Add /decrease R3 ; TC & S ; R( condition = 01 ) loop2 ; 共享變量C 的值保護(hù)到RI 中。 Rl 的值傳送到R3 中，進(jìn)程修改共享變量時(shí)，先對R3 操作（不是直接操作C ）。 R3 加1 ／減1 ，進(jìn)程歸還／申請由共享變量C 代表的共享資源（假定每次一個(gè)）。 執(zhí)行”測試、比較和交換”指令。 條件碼＝01 ，轉(zhuǎn)向循環(huán)loop2 ；否則離開臨界區(qū)。 ? ? ? ( 3 ）程序執(zhí)行說明。 此解與互斥使用共享變量的思路絕然不同，并發(fā)運(yùn)行的進(jìn)程可不互斥地訪問它們的共享變量。此方案認(rèn)為造成共享變量C 值錯(cuò)誤的原因在于：一個(gè)進(jìn)程（Pl ）在改變C 值的過程中，另一個(gè)進(jìn)程伊2 ）插進(jìn)來也改變了C 的值，而本進(jìn)程（Pl）卻不知道，造成了c 值結(jié)果不正確。如果有辦法使本進(jìn)程口1 ）能知道C 值是否改變，改變的話在繼承改變了的C 值的基礎(chǔ)上，再作自己的改變操作，則就不會(huì)導(dǎo)致共享變量C 值的錯(cuò)誤。為此，本解決方案中，當(dāng)一個(gè)進(jìn)程l）準(zhǔn)備改變C 值時(shí)，先把C 的值保護(hù)在Rl 中，然后，通過R3 來改變共享變量C 的值。當(dāng)要把新的值（即R3 內(nèi)的值）送C之前，先要判斷一下在本進(jìn)程（P1 ）工作期間是否有別的進(jìn)程口2 ）插進(jìn)來也改變了C 的值（并發(fā)進(jìn)程P1 、P2 的執(zhí)行完全會(huì)造成這種情況），方法是：將扭1 ）中被保護(hù)的C 的原來值，與C 的當(dāng)前值比較，若相等，說明C 值未被改變過，則將本進(jìn)程（Pl ）修改過的新值送C （即（R3 ) 一C ) ；若不相等，說明C 值在工作期間被改變過，則應(yīng)該繼承C 的新值（即（C ）一Rl ）并且返回到loop2 處重新對C值計(jì)數(shù)，以此保證C值的最終結(jié)果的正確性。這里提及”進(jìn)程工作期間”指的是一個(gè)進(jìn)程從開始至結(jié)束對共享變量C 值的操作的這段時(shí)間，也就是執(zhí)行進(jìn)程，' I 晦界區(qū)”這段程序的時(shí)間。此外，在進(jìn)程進(jìn)入臨界區(qū)之前，應(yīng)等待直到C 為非。（即有資源可用）為止。 ( 4 ）舉例。 假定系統(tǒng)中有靜態(tài)分配資源磁帶機(jī)共3 臺(tái)，被N 個(gè)進(jìn)程共享，由共享變量C 來代表可用磁帶機(jī)臺(tái)數(shù)，其初值為3 ?，F(xiàn)有并發(fā)進(jìn)程P1 和P2 均申請使用磁帶機(jī)，執(zhí)行臨界區(qū)程序。 進(jìn)程Pl 執(zhí)行臨界區(qū)程序 ( C ）→R1 ；因（C）=3 ，故（R1) = 3 。 loop2: ( Rl ）→R3 因（R1 ) = 3 ，故（R3 ）當(dāng)前也＝3 。 decrease R3 ：申請使用磁帶機(jī)，做減1 操作，故（R3 ）=2. TC & S 執(zhí)行”測試、比較和交換，, TC & S 指令。 如果R1=（C ）則（R3 ）→C，即（C）=2 ，并置條件碼為”00" , 跳出臨界區(qū)程序，去使用磁帶機(jī)。 如果(Rl ) ≠ (C) ，例如，( C ）=2 ，說明進(jìn)程P2 搶先申請了磁帶機(jī)，所以，C 與保護(hù)在R1 中的值不一樣了（C 的值必 小于Rl 的值），應(yīng)以C 的當(dāng)前值為準(zhǔn)，執(zhí)行（C ) Rl ( R1 此時(shí)變?yōu)? ) ，并置條件碼為”01 " ，轉(zhuǎn)向foopZ 。于是伍1 ) = 2 , 跟著（R3 卜2 。接著卿）減1 后應(yīng)＝l 了。再執(zhí)行TC & S 時(shí)，由于伍1 卜（C ) = 2 ，會(huì)使C 變?yōu)? 。 r ( conditio 二01 ) loop2 ; 巧單道批處理系統(tǒng)中，下列三個(gè)作業(yè)采用先來先服務(wù)調(diào)度算法和最高響應(yīng)比優(yōu)先算法進(jìn)行調(diào)度，哪一種算法性能較好？請完成下表： 作業(yè) 提交時(shí)間 運(yùn)行時(shí)間 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 1 2 3 10 : 00 10 : 10 10 : 25 2 : 00 1 : 00 0 : 25 ? ? ? ? 平均作業(yè)周轉(zhuǎn)時(shí)間= 平均作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間W = ? ? ? 答： 可見HRRF 比FIFO 要好 16 若有如表所示四個(gè)作業(yè)進(jìn)入系統(tǒng)，分別計(jì)算在FCFS 、S 開和HRR 衛(wèi)算法下的平均周轉(zhuǎn)時(shí)間與帶權(quán)平均周轉(zhuǎn)時(shí)間。（時(shí)間以十進(jìn)制表示） 答： 17 Kleinrock 提出一種動(dòng)態(tài)優(yōu)先權(quán)算法：進(jìn)程在就緒隊(duì)列等待時(shí)，其優(yōu)先權(quán)以速率a變化；當(dāng)進(jìn)程在處理器上運(yùn)行，時(shí)其優(yōu)先權(quán)以速率p 變化。給參數(shù)a,b 賦以不同值可得到不同算法。（l ）若a＞b＞c是什么算法？( 2 ）若a＜b＜c是什么算法 答：( l ）是先進(jìn)先出算法。因?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 ）是后進(jìn)先出算法。因?yàn)樵诰途w隊(duì)列中的進(jìn)程比在CPU 上運(yùn)行的進(jìn)程的優(yōu)先權(quán)下降得快，故后進(jìn)入就緒隊(duì)列的進(jìn)程此先進(jìn)入的進(jìn)程的優(yōu)先權(quán)高。 18 有一個(gè)四道作業(yè)的操作系統(tǒng)，若在一段時(shí)間內(nèi)先后到達(dá)6 個(gè)作業(yè)，它們的提交和估計(jì)運(yùn)行時(shí)間由下表給出： 系統(tǒng)采用SJF 調(diào)度算法，作業(yè)被調(diào)度進(jìn)入系統(tǒng)后中途不會(huì)退出，但作業(yè)運(yùn)行時(shí)可被更短作業(yè)搶占。（l ）分別給出6 個(gè)作業(yè)的執(zhí)行時(shí)間序列、即開始執(zhí)行時(shí)間、作業(yè)完成時(shí)間、作業(yè)周轉(zhuǎn)時(shí)間。（2 ）計(jì)算平均作業(yè)周轉(zhuǎn)時(shí)間。 答 說明： ( 1 ) J2 到達(dá)時(shí)搶占J1 ; J3 到達(dá)時(shí)搶占J2 。 ( 2 ）但J4 到達(dá)時(shí)，因不滿足SJF ，故J4 不能被運(yùn)行，J3 繼續(xù)執(zhí)行5 分鐘。 ( 3 ）由于是4 道的作業(yè)系統(tǒng)，故后面作業(yè)不能進(jìn)入主存而在后備隊(duì)列等待，直到有作業(yè)結(jié)束。 ( 4 ）根據(jù)進(jìn)程調(diào)度可搶占原則，J3 第一個(gè)做完。而這時(shí)J5 、J6 均己進(jìn)入后備隊(duì)列，而J5 可進(jìn)入主存。 ( 5 ）因J5 最短，故它第二個(gè)完成。這時(shí)J6 方可進(jìn)入主存。因J6 最短，故它第三個(gè)完成。 ( 6 ）然后是：J4 、J2和J1 ( 7 ) T =( 155 + 95 + 20 + 55 + 15 + 20 ) / 6 = 60 19、有一個(gè)具有兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進(jìn)程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度算法，在下表所示的作業(yè)序列，作業(yè)優(yōu)先數(shù)即為進(jìn)程優(yōu)先數(shù)，優(yōu)先數(shù)越小優(yōu)先級越高。 ( 1 ）列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間。 ( 2 ）計(jì)算平均周轉(zhuǎn)時(shí)間。 答：每個(gè)作業(yè)運(yùn)行將經(jīng)過兩個(gè)階段：作業(yè)調(diào)度（SJF 算法）和進(jìn)程調(diào)度（優(yōu)先數(shù)搶占式）。另外，批處理最多容納2 道作業(yè)，更多的作業(yè)將在后備隊(duì)列等待。 ( l ) 10 : 00 ，作業(yè)A 到達(dá)并投入運(yùn)行。 ( 3 ) 10 : 2O ，作業(yè)B 到達(dá)且優(yōu)先權(quán)高于作業(yè)A ，故作業(yè)B 投入運(yùn)行而作業(yè)A 在就緒隊(duì)列等待。 ( 4 ) 10 : 30 ，作業(yè)C 到達(dá)，因內(nèi)存中已有兩道作業(yè)，故作業(yè)C 進(jìn)入作業(yè)后備隊(duì)列等待。 ( 5 ) 10 : 50 ，作業(yè)B 運(yùn)行結(jié)束，作業(yè)D 到達(dá)，按SJF 短作業(yè)優(yōu)先算法，作業(yè)D 被裝入內(nèi)存進(jìn)入就緒隊(duì)列。而由于作業(yè)A 的優(yōu)先級高于作業(yè)D ，故作業(yè)A 投入運(yùn)行 ( 6 ) 11 : 10 ，作業(yè)A 運(yùn)行結(jié)束，作業(yè)C 被調(diào)入內(nèi)存，具作業(yè)c 的優(yōu)先級高于作業(yè)D , 故作業(yè)C 投入運(yùn)行。 ( 7 ) 12 : 00 ，作業(yè)c 運(yùn)行結(jié)束，作業(yè)D 投入運(yùn)行。 ( 8 ) 12 : 20 ，作業(yè)D 運(yùn)行結(jié)束。 各作業(yè)周轉(zhuǎn)時(shí)間為：作業(yè)A 70 ，作業(yè)B 30 ，作業(yè)C 90 ，作業(yè)D 90 。平均作業(yè)周轉(zhuǎn)時(shí)間為70 分鐘。 20 、某多道程序設(shè)計(jì)系統(tǒng)供用戶使用的主存為100K ，磁帶機(jī)2 臺(tái)，打印機(jī)1 臺(tái)。采用可變分區(qū)內(nèi)存管理，采用靜態(tài)方式分配外圍設(shè)備，忽略用戶作業(yè)FO 時(shí)間?，F(xiàn)有作業(yè)序列如下： 作業(yè)調(diào)度采用FCFS 策略，優(yōu)先分配主存低地址區(qū)且不準(zhǔn)移動(dòng)已在主存的作業(yè)，在主存中的各作業(yè)平分CPU 時(shí)間．現(xiàn)求：( l ）作業(yè)被調(diào)度的先后次序？( 2 ）全部作業(yè)運(yùn)行結(jié)束的時(shí)間？( 3 ）作業(yè)平均周轉(zhuǎn)時(shí)間為多少？( 4 ）最大作業(yè)周轉(zhuǎn)時(shí)間為多少？ 答：( l ）作業(yè)調(diào)度選擇的作業(yè)次序?yàn)椋鹤鳂I(yè)1 、作業(yè)3 、作業(yè)4 、作業(yè)2 和作業(yè)5 . ( 2 ）全部作業(yè)運(yùn)行結(jié)束的時(shí)間9 : 30 。 ( 3 ）周轉(zhuǎn)時(shí)間：作業(yè)1 為30 分鐘、作業(yè)2 為55 分鐘、作業(yè)3 為40 分鐘、作業(yè)4 為40 分鐘和作業(yè)5 為55 分鐘。 ( 4 ）平均作業(yè)周轉(zhuǎn)時(shí)間＝44 分鐘。 ( 5 )最大作業(yè)周轉(zhuǎn)時(shí)間為55 分鐘。 分析：本題綜合測試了作業(yè)調(diào)度、進(jìn)程調(diào)度、及對外設(shè)的競爭、主存的競爭。8 : oo 作業(yè)1 到達(dá)，占有資源并調(diào)入主存運(yùn)行。 8 : 20 作業(yè)2 和3 同時(shí)到達(dá)，但作業(yè)2 因分不到打印機(jī)，只能在后備隊(duì)列等待。作業(yè)3 資源滿足，可進(jìn)主存運(yùn)行，并與作業(yè)1 平分CPU 時(shí)間。 8 : 30 作業(yè)1 在8 : 30 結(jié)束，釋放磁帶與打印機(jī)。但作業(yè)2 仍不能執(zhí)行，因不能移動(dòng)而沒有30KB 的空閑區(qū)，繼續(xù)等待。作業(yè)4 在8 : 30 到達(dá)，并進(jìn)入主存執(zhí)行，與作業(yè)3 分享CPU 8 : 35 作業(yè)5 到達(dá)，因分不到磁帶/打印機(jī)，只能在后備隊(duì)列等待。 9 : 00 作業(yè)3 運(yùn)行結(jié)束，釋放磁帶機(jī)。此時(shí)作業(yè)2 的主存及打印機(jī)均可滿足，投入運(yùn)行。作業(yè)5 到達(dá)時(shí)間晚，只能等待。 9 : 10 作業(yè)4 運(yùn)行結(jié)束，作業(yè)5 因分不到打印機(jī)，只能在后備隊(duì)列繼續(xù)等待。 9：15巧作業(yè)2 運(yùn)行結(jié)束，作業(yè)5 投入運(yùn)行。 9 : 30 作業(yè)全部執(zhí)行結(jié)束。 21、某多道程序設(shè)計(jì)系統(tǒng)采用可變分區(qū)內(nèi)存管理，供用戶使用的主存為200K ，磁帶機(jī)5 臺(tái)。采用靜態(tài)方式分配外圍設(shè)備，且不能移動(dòng)在主存中的作業(yè)，忽略用戶作業(yè)I/O時(shí)間?，F(xiàn)有作業(yè)序列如下： 現(xiàn)求：( l ) FIFO 算法選中作業(yè)執(zhí)行的次序及作業(yè)平均周轉(zhuǎn)時(shí)間？( 2 ) SJF 算法選中作業(yè)執(zhí)行的次序及作業(yè)平均周轉(zhuǎn)時(shí)間？（進(jìn)程調(diào)度也采用FCFS ) 答：( 1 ) FIFO 算法選中作業(yè)執(zhí)行的次序?yàn)椋篈 、B 、D 、C 和E 作業(yè)平均周轉(zhuǎn)時(shí)間為63分鐘 ( 2 ) SJF 算法選中作業(yè)執(zhí)行的次序?yàn)椋篈 、B 、D 、E 和C 。作業(yè)平均周轉(zhuǎn)時(shí)間為58分鐘 詳細(xì)說明： 1 ．先來先服務(wù)算法。說明： ( 1 ) 8 : 30 作業(yè)A 到達(dá)并投入運(yùn)行。注意它所占用的資源。 ( 2 ) 8 : 50 作業(yè)B 到達(dá)，資源滿足進(jìn)主存就緒隊(duì)列等CPu 。 ( 3 ) 9 : 00 作業(yè)C 到達(dá)，主存和磁帶機(jī)均不夠，進(jìn)后備作業(yè)隊(duì)列等待。 ( 4 ) 9 : 05 作業(yè)D 到達(dá)，磁帶機(jī)不夠，進(jìn)后備作業(yè)隊(duì)列等待。后備作業(yè)隊(duì)列有C 、D 。( 5 ) 9 : 10 作業(yè)A 運(yùn)行結(jié)束，歸還資源磁帶，但注意主存不能移動(dòng)（即不能緊縮）。作業(yè)B 投入運(yùn)行。作業(yè)C 仍因主存不夠而等在后備隊(duì)列。這時(shí)作業(yè)E 也到達(dá)了，。也由于主存不夠進(jìn)入后備作業(yè)隊(duì)列。此時(shí)作業(yè)D 因資源滿足（主存磁帶均滿足），進(jìn)主存就緒隊(duì)列等待。后備作業(yè)隊(duì)列還有C 、E 。 ( 6 ) 9 : 35 作業(yè)B 運(yùn)行結(jié)束，作業(yè)D 投入運(yùn)行。這時(shí)作業(yè)C 因資源滿足而調(diào)入主存進(jìn)就緒隊(duì)列等CPU 。而作業(yè)E 因磁帶機(jī)不夠繼續(xù)在后備作業(yè)隊(duì)列等待。 ( 7 ) 9 : 55 作業(yè)D 運(yùn)行結(jié)束，作業(yè)C 投入運(yùn)行。這時(shí)作業(yè)E 因資源滿足而調(diào)入主存進(jìn)就緒隊(duì)列等CPU 。 ( 8 ) 10 : 30 作業(yè)C 運(yùn)行結(jié)束，、作業(yè)E 投入運(yùn)行。 ( 9 ) 10 : 40 作業(yè)E 運(yùn)行結(jié)束。 2 ．短作業(yè)優(yōu)先算法。說明： ( 1 ) 8 : 30 作業(yè)A 到達(dá)并投入運(yùn)行。注意它所占用的資源。 ( 2 ) 8 : 50 作業(yè)B 到達(dá)，資源滿足進(jìn)主存就緒隊(duì)列等CPU 。 ( 3 ) 9 : 00 作業(yè)C 到達(dá)，主存和磁帶機(jī)均不夠，進(jìn)后備作業(yè)隊(duì)列等待。 ( 4 ) 9 : 05 作業(yè)D 到達(dá)，磁帶機(jī)不夠，進(jìn)后備作業(yè)隊(duì)列等待。后備作業(yè)隊(duì)列有C 、D . ( 5 ) 9 : 10 作業(yè)A 運(yùn)行結(jié)束，歸還資源磁帶，但注意主存不能移動(dòng)（即不能緊縮）。作業(yè)B 投入運(yùn)行。作業(yè)C 仍因主存不夠而等在后備隊(duì)列。這時(shí)作業(yè)E 也到達(dá)了，雖然該作業(yè)最短，也由于主存不夠進(jìn)入后備作業(yè)隊(duì)列．此時(shí)作業(yè)D 因資源滿足（主存磁帶均滿腳，進(jìn)主存就緒隊(duì)列等待。后備作業(yè)隊(duì)列還有C 、E 。 ( 6 ) 9 : 35 作業(yè)B 運(yùn)行結(jié)束，作業(yè)D 投入運(yùn)行。這時(shí)作業(yè)C 和E 資源均滿足，但按SJF 應(yīng)把作業(yè)E 調(diào)入主存進(jìn)就緒隊(duì)列等CPU 。而作業(yè)C 因磁帶機(jī)不夠繼續(xù)在后備作業(yè)隊(duì)列等待。 ( 7 ) 9 : 55 作業(yè)D 運(yùn)行結(jié)束，作業(yè)C 調(diào)入主存進(jìn)就緒隊(duì)列等CPU . ( 8 ) 10 : 05 作業(yè)E 運(yùn)行結(jié)束，作業(yè)C 投入運(yùn)行． ( 9 ) 10 : 40 作業(yè)C 運(yùn)行結(jié)束。 上題中，若允許移動(dòng)己在主存中的作業(yè)，其他條件不變，現(xiàn)求：( l ) FIFO 算法選中作業(yè)執(zhí)行的次序及作業(yè)平均周轉(zhuǎn)時(shí)間？( 2 ) SJF 算法選中作業(yè)執(zhí)行的次序及作業(yè)平均周轉(zhuǎn)時(shí)間？ 答： FIFO 算法選中作業(yè)執(zhí)行的次序?yàn)椋篠JF 算法選中作業(yè)執(zhí)行的次序?yàn)椋? （l ) A 、B 、D 、E 和C。作業(yè)平均周轉(zhuǎn)時(shí)間為58 分鐘。 ( 2 ) A 、B 、E 、D 和C。作業(yè)平均周轉(zhuǎn)時(shí)間為56 分鐘。 與上題類同，詳細(xì)說明略。 23、設(shè)計(jì)一個(gè)進(jìn)程定時(shí)喚醒隊(duì)列和定時(shí)喚醒處理程序：( l ）說明一個(gè)等待喚醒進(jìn)程入隊(duì)v 的過程。（2 ）說明時(shí)鐘中斷時(shí)，定時(shí)喚醒處理程序的處理過程。（3 ）現(xiàn)有進(jìn)程P1 要求20 秒后運(yùn)行，經(jīng)過40 秒后再次運(yùn)行；PZ 要求25 秒后運(yùn)行；P3 要求35 秒后運(yùn)行，經(jīng)過35 秒后再次運(yùn)行；P4 要求60 秒后運(yùn)行。試建立相應(yīng)的進(jìn)程定時(shí)喚醒隊(duì)列。 答： 組織如下的定時(shí)喚醒隊(duì)列 。 ( l ）當(dāng)一個(gè)需定時(shí)喚醒的進(jìn)程要入隊(duì)時(shí)，根據(jù)它要喚醒的時(shí)間，被扦入隊(duì)列的適當(dāng)位置，注意，喚醒時(shí)間按增量方式存放。 ( 2 ）每當(dāng)時(shí)鐘中斷時(shí)，時(shí)鐘中斷例程判別把隊(duì)列中的第一個(gè)進(jìn)程的時(shí)間量減1 ，直到該值為時(shí)喚醒進(jìn)程工作。同時(shí)隊(duì)列中下一個(gè)進(jìn)程成為隊(duì)列頭。 24、一個(gè)實(shí)時(shí)系統(tǒng)有4 個(gè)周期性事件，周期分別為50 、100 、300 和250ms 。若假設(shè)其處理分別需要35 、20 、10 和X ms，則該系統(tǒng)可調(diào)度允許的X值最大為多少？ 實(shí)時(shí)任務(wù)可調(diào)度應(yīng)滿足： 35 / 50 +20/100 + 10/300 +X/250＜l X＜250(l-28/30) = 250×0.067 = 16.75ms 首頁 入門學(xué)習(xí) 程序員 計(jì)算機(jī)考研 計(jì)算機(jī)電子書下載 硬件知識 網(wǎng)絡(luò)知識 專業(yè)課程答案下載 視頻教程下載 第三章 作者：佚名 來源：網(wǎng)絡(luò) 1、 有三個(gè)并發(fā)進(jìn)程：R 負(fù)責(zé)從輸入設(shè)備讀入信息塊，M 負(fù)責(zé)對信息塊加工處理；P 負(fù)責(zé)打印輸出信息塊。今提供； l ）一個(gè)緩沖區(qū)，可放置K 個(gè)信息塊； 2 ）二個(gè)緩沖區(qū)，每個(gè)可放置K 個(gè)信息塊； 試用信號量和P 、V 操作寫出三個(gè)進(jìn)程正確工作的流程。 答： 1 ) var B : array [ 0 , k-1 ] of item ; sread : semaPhore : = k ; smanage : semaPhore : = 0 ; swrite : semaphore : = 0 ; rptr : integer : = O ; mptr : integer : = O ; wptr ：integer : = 0 ; x : item cobegin process reader ; process manager ; process writer ; begin begin begin LI : read a message intox ; L2 : P ( smanage ) ; L3 : P ( swnte ) ; P ( sread ) ; x:=B[mptr]; x:=B[swrite]; B[rptr]:=x; mptr:=(mptr+1) mod k; wptr:=(wptr+1) mod k; Rptr:=(rptr+1) mod k; manage the message in x; V(sread); V(smanage); B[mptr]:=x; print the message in x; Goto L1; V(swrite); goto L3; End; goto L2; end; End; coend 2 ) var A , B :array [ 0 , k -l ] of item ; sPut1 : semaphore:=k; SPut2: semaPhore:=k; sget1 : semaPhore : = 0 ; sget2 : semaphore : = 0 ; put1 ：integer ：=O ; put2：integer : = 0 ; get1 ：integer ：=O ; get2 : integer : = O ; cobegin process reader ; processn manager; process Writer ; begin begin begin Ll : read a message into x ; L2 : P ( sgetl ) ; L3 : P ( sgetZ ) ; P ( SPut1 ) ; x : = A [ get1] ; x : = B [get2]; A [put1]:=x ; get1 ：(get1+1 ) mod k ; get2:=（get2 + l ) mod k ; Put1:=(put1+1) mod k; V(sput1); V(sput2); V(sget1); manage the message into x; print the message in x; Goto L1; P(sput2); goto L3; Put2:=(put2+1) mod k; V(sget2); Goto L2; End; Coend 2 設(shè)有n 個(gè)進(jìn)程共享一個(gè)互斥段，如果： ( 1 ）每次只允許一個(gè)進(jìn)程進(jìn)入互斥段； ( 2 ）每次最多允許m 個(gè)進(jìn)程（m 簇n ）同時(shí)進(jìn)入互斥段。 試問：所采用的信號量初值是否相同？信號量值的變化范圍如何？ 答：所采用的互斥信號量初值不同。 1 ）互斥信號量初值為1 ，變化范圍為［-n＋l , 1 ］。 當(dāng)沒有進(jìn)程進(jìn)入互斥段時(shí)，信號量值為1 ；當(dāng)有1 個(gè)進(jìn)程進(jìn)入互斥段但沒有進(jìn)程等待進(jìn)入互斥段時(shí)，信號量值為O ；當(dāng)有1 個(gè)進(jìn)程進(jìn)入互斥段且有一個(gè)進(jìn)程等待進(jìn)入互斥段時(shí)，信號量值為-1 ；最多可能有n -1 個(gè)進(jìn)程等待進(jìn)入互斥段，故此時(shí)信號量的值應(yīng)為-（n - 1 ）也就是-n+1 。 2 ）互斥信號量初值為m ，變化范圍為［-n＋m , m ］。 當(dāng)沒有進(jìn)程進(jìn)入互斥段時(shí)，信號量值為m ；當(dāng)有1 個(gè)進(jìn)程進(jìn)入互斥段但沒有進(jìn)程等待進(jìn)入互斥段時(shí)，信號量值為m - 1 ：當(dāng)有m 個(gè)進(jìn)程進(jìn)入互斥段且沒有一個(gè)進(jìn)程等待進(jìn)入互斥段時(shí)，信號量值為0 ：當(dāng)有m 個(gè)進(jìn)程進(jìn)入互斥段且有一個(gè)進(jìn)程等待進(jìn)入互斥段時(shí)，信號量值為一l ；最多可能有n - m 個(gè)進(jìn)程等待進(jìn)入互斥段，故此時(shí)信號量的值應(yīng)為-(n-m)也就是-n+m. 3 有兩個(gè)優(yōu)先級相同的進(jìn)程P1和P2，各自執(zhí)行的操作如下，信號量S1和S2初值均為0。試問Pl 、P2 并發(fā)執(zhí)行后，x 、y 、z 的值各為多少？ P1: P2: Begin begin Y:=1; x:=1; Y:=y+3; x:=x+5; V(S1); P(S1); Z:=Y+1; X:X+Y; P(s2); V(S2); Y:=z+y; z:=z+x; End end 答：現(xiàn)對進(jìn)程語句進(jìn)行編號，以方便描述． P1 : P2 : begin begin y : = 1 ；① x :=1 ; ⑤ y :=y+3 ；② x ：x+5 ; ⑥ V(S1); P(S1); Z:Y+1 ；③ x ：X＋Y ;⑦ P(s2); V(S2); Y:=z+y; ④ z：=Z+X；⑧ End end ① 、② 、⑤ 和⑥ 是不相交語句，可以任何次序交錯(cuò)執(zhí)行，而結(jié)果是唯一的。接著無論系統(tǒng)如何調(diào)度進(jìn)程并發(fā)執(zhí)行，當(dāng)執(zhí)行到語句⑦ 時(shí)，可以得到x = 10 , y = 4 。按Bernstein 條件，語句③ 的執(zhí)行結(jié)果不受語句⑦ 的影響，故語句③ 執(zhí)行后得到z = 5 。最后，語句④ 和⑧ 并發(fā)執(zhí)行，這時(shí)得到了兩種結(jié)果為： 語句④ 先執(zhí)行：x =10 , y =9 , z= 150 語句⑧ 先執(zhí)行：x =10 , y =19 , z =15 此外，還有第三種情況，語句③ 被推遲，直至語句⑧ 后再執(zhí)行，于是依次執(zhí)行以下三個(gè)語句： 7 ：二z + X : z : = y + 1 ; y : ＝Z十y ; 這時(shí)z 的值只可能是y ＋1=5 ，故y =Z＋Y=5 + 4=9，而x = 10 。 第三種情況為：x = 10 ，Y=9 , Z = 5 。 4 有一閱覽室，讀者進(jìn)入時(shí)必須先在一張登記表上登記，該表為每一座位列出一個(gè)表目，包括座號、姓名，讀者離開時(shí)要注銷登記信息；假如閱覽室共有100 個(gè)座位。試用：l ）信號量和P 、V 操作；2 ）管程，來實(shí)現(xiàn)用戶進(jìn)程的同步算法。 答：1 ）使用信號量和P 、v 操作： var name ：array [ l …100]of A ; A = record number ：integer ; name：string ; end for i : = 1 to 100 do {A [ i ].number ：i；A [ i ].name :null;} mutex , seatcount : semaphore ; i : integer ；mutex : = l ; seatcount : = 100 ; cobegin { process readeri ( var readename：string ) （i=1 , 2 …) { P ( seatcount ) ; P （mutex ) ; for i : = 1 to 100 do i++ if A [ i ].name＝null then A [ i ].name：readername； reader get the seat number=i；/*A[I].number V ( mutex ) 進(jìn)入閱覽室，座位號i ，座下讀書； P ( mutex ) ; A[i]name：null ; V （mutex ) ; V(seatcount); 離開閱覽室； } } coend 2 ）使用管程操作： TYPE readbook=monitor VAR R: condition ; I,seatcount ：integer; name：array [ l:100] of string ; DEFINE rcadercome, readerleave ; USE check , wait , signal , release ; Procedure readercome ( readername ) begin check ( IM ) ; if seatcount≥100 wait ( R,IM ) seatcount : = seatcount + 1 ; for i=1 to 100 do i++ if name[i] ==null then name[i]:= readername; get the seat number = i ; release ( IM ) ; end procedure readerleave ( readername ) begin check ( IM ) ; seatcount--; for i = 1 to 1 00 do i++ if name［i ］readername then name［i］:null; release ( IM ) ; end begin seatcount : = 1OO ; name:＝null ; end cobegin { process readeri ( i = 1 , 2 ．… ） begin readercome ( readername）; read the book ; readerleave ( readername）; leave the readroom; end } coend. 5. 在一個(gè)盒子里，混裝了數(shù)量相等的黑白圍棋子· 現(xiàn)在用自動(dòng)分揀系統(tǒng)把黑子、白子分開，設(shè)分揀系統(tǒng)有二個(gè)進(jìn)程P1 和P2 ，其中P1 揀白子；P2 揀黑子。規(guī)定每個(gè)進(jìn)程每次揀一子；當(dāng)一個(gè)進(jìn)程在揀時(shí)，不允許另一個(gè)進(jìn)程去揀；當(dāng)一個(gè)進(jìn)程揀了一子時(shí)，必須讓另一個(gè)進(jìn)程去揀．試寫出兩進(jìn)程P1 和P2 能并發(fā)正確執(zhí)行的程序。 答1 ：實(shí)質(zhì)上是兩個(gè)進(jìn)程的同步問題，設(shè)信號量s1 和s2 分別表示可揀白子和黑子，不失一般性，若令先揀白子。 var S1 , S2 : semaphore; S1 : = l; S2 ：=0; cobegin { process P1 begin repeat P( S1 ) ; 揀白子 V ( S2 ) ; until false ; end process P2 begin repeat P ( S2 ) ; 揀黑子 V (S1 ) ; until false ; end } coend . 答2 : TYPE pickup-chess = MONITOR VAR flag : boolean ; S-black , s-white : codition ; DEFINE pickup-black , pickup-white ; USE wait,signal , check , release ; procedure pickup-black ; begin check(IM ) ; if flag then wait(s-black,IM ) ; flag : ＝true; pickup a black; signal(S-white,IM); release ( IM ) ; end procedure pickup-white ; begin check ( IM ) ; if not flag then wait(S-white,IM ); flag :=false ; pickup a white ; signal ( S-black,IM ) ; release ( IM ) ; end begin flag:=true ; end main ( ) { cobegin process -B ( ) ; process -W ( ) ; coend } process-B ( ) begin pickup-chess.pickup-black ( ) ; other ; end process-W ( ) begin pickup-chess.pickup-white( ) ; other ; end 6 管程的同步機(jī)制使用條件變量和wait 及signal ，嘗試為管程設(shè)計(jì)一種僅僅使用一個(gè)原語操作的同步機(jī)制。 答：可以采用形如waituntil ＜條件表達(dá)式＞的同步原語。如waituntil ( numbersum + number < K ) 表示進(jìn)程由于條件不滿足而應(yīng)等待，當(dāng)進(jìn)程號累加和小于K 時(shí)，系統(tǒng)應(yīng)喚醒該進(jìn)程工作． 7 設(shè)公共汽車上，司機(jī)和售票員的活動(dòng)分別如下： 司機(jī)的活動(dòng)：啟動(dòng)車輛：正常行車；到站停車。 售票員的活動(dòng)：關(guān)車門；售票；開車門。 在汽車不斷地到站、停車、行駛過程中，這兩個(gè)活動(dòng)有什么同步關(guān)系？用信號量和P 、V 操作實(shí)現(xiàn)它們的同步。 答：在汽車行駛過程中，司機(jī)活動(dòng)與售票員活動(dòng)之間的同步關(guān)系為：售票員關(guān)車門后，向司機(jī)發(fā)開車信號，司機(jī)接到開車信號后啟動(dòng)車輛，在汽車正常行駛過程中售票員售票，到站時(shí)司機(jī)停車，售票員在車停后開門讓乘客上下車。因此，司機(jī)啟動(dòng)車輛的動(dòng)作必須與售票員關(guān)車門的動(dòng)作取得同步；售票員開車門的動(dòng)作也必須與司機(jī)停車取得同步。應(yīng)設(shè)置兩個(gè)信號量：S1 、S2 ;S1 表示是否允許司機(jī)啟動(dòng)汽車（其初值為0 ) ;S2 表示是否允許售票員開門（其初值為0 ）。用P 、v 原語描述如下： var S1 , S2 : semaphore ; S1=0；S2=0； cobegin { driver ( ) ; busman ( ) ; } coend driver ( ) begin while ( 1 ) { P ( S1 ) 啟動(dòng)車輛；正常行車；到站停車； V ( S2 ) ; } end busman ( ) begin while ( 1 ) { 關(guān)車門； V ( 51 ) 售票; P ( S2 ) 開車門； 上下乘客； } end 8、一個(gè)快餐廳有4 類職員：( l ）領(lǐng)班：接受顧客點(diǎn)菜；( 2 ）廚師：準(zhǔn)備顧客的飯菜；( 3 ) 包工：將做好的飯菜打包；( 4 ）出納員：收款并提交食品。每個(gè)職員可被看作一個(gè)進(jìn)程，試用一種同步機(jī)制寫出能讓四類職員正確并發(fā)運(yùn)行的程序。 答：典型的進(jìn)程同步問題，可設(shè)四個(gè)信號量51 、S2 、S3 和S4 來協(xié)調(diào)進(jìn)程工作。 var S1 , S2 ,S3 ,