（word完整版）操作系統(tǒng)第五版費(fèi)祥林一課后習(xí)題答案解析參考

第一章操作系統(tǒng)概論

1、有一臺(tái)計(jì)算機(jī)，具有IMB內(nèi)存，操作系統(tǒng)占用200KB,每個(gè)用戶進(jìn)程

各占200KBo如果用戶進(jìn)程等待I/O的時(shí)間為80%,若增加1MB內(nèi)存，

則CPU的利用率提高多少？

答：設(shè)每個(gè)進(jìn)程等待I/O的百分比為P,則n個(gè)進(jìn)程同時(shí)等待刀0的概

率是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利用率=1-（80%）4=0.59

若再增加1MB內(nèi)存，系統(tǒng)中可同時(shí)運(yùn)行9個(gè)用戶進(jìn)程，此時(shí)：cPu利用率

=1—（1-80%）9=0o87

故增加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有無(wú)空閑等待？若有，在哪段時(shí)間內(nèi)等待？為什么會(huì)

等待？（2）程序A、B有無(wú)等待CPU的情義？若有，指出發(fā)生等待的時(shí)

刻.

答：畫出兩道程序并發(fā)執(zhí)行圖如下:

（word完整版）操作系統(tǒng)第五版費(fèi)祥林」果后習(xí)題答案解析參考

IA計(jì)跳|R計(jì)，|[A計(jì)|R計(jì)置

處理器tII

III

iR檢入J

輸入機(jī)

打印機(jī)|A『印]|A打印

程序A|濟(jì)■:[打印|計(jì)鯉|打印

程序B[計(jì)址]給入蚓計(jì)，

時(shí)間（ms）

050100150】80200250300

（1）兩道程序運(yùn)行期間，CPU存在空閑等待，時(shí)間為100至150ms之間

（見圖中有色部分）

⑵程序A無(wú)等待現(xiàn)象,但程序B有等待。程序B有等待時(shí)間段為180rns

至200ms間（見圖中有色部分）

3設(shè)有三道程序，按A、B、C優(yōu)先次序運(yùn)行，其內(nèi)部計(jì)算和U0操作時(shí)間

由圖給出。

ABC

Cn=30msC2i=60msC3i=20ms

III

Ii2=40msl22-30ms132Koms

III

Ci3=10msCumlOmsC33aB20ms

試畫出按多道運(yùn)行的時(shí)間關(guān)系圖（忽略調(diào)度執(zhí)行時(shí)間）。完成三道程序共

花多少時(shí)間？比單道運(yùn)行節(jié)省了多少時(shí)間？若處理器調(diào)度程序每次進(jìn)行

程序轉(zhuǎn)換化時(shí)1ms,試畫出各程序狀態(tài)轉(zhuǎn)換的時(shí)間關(guān)系圖。

答：

1）忽略調(diào)度執(zhí)行時(shí)間，多道運(yùn)行方式（搶占式）：

時(shí)間0378101213141719單位10ms

I/O112122【32

CPUC13C21C31|

C11C21C23C33-|

搶占式共用去190ms,單道完成需要260ms,節(jié)省70ms。

(word完整版)操作系統(tǒng)第五版費(fèi)祥林一課后習(xí)題答案解析參考

調(diào)度執(zhí)行時(shí)間ITns,多道運(yùn)行方式(非搶占式):

4在單CPU和兩臺(tái)I/O(11,12)設(shè)備的多道程序設(shè)計(jì)環(huán)境下，同時(shí)

投入三個(gè)作業(yè)運(yùn)行。它們的執(zhí)行軌跡如下：

Jobl:I2(30ms)、CPU(10ms)、11(30ms),CPU(10ms)、

I2(20ms)

Job2:11(20ms)、CPU(20ms)、I2(40ms)

J0b3:CPU(30ms)、11(20ms),CPU(10ms)、11(10ms)

如果CPU、11和I2都能并行工作，優(yōu)先級(jí)從高到低為Jobl、Job2和

Job3，優(yōu)先級(jí)高的作業(yè)可以搶占優(yōu)先級(jí)低的作業(yè)的CPU,但不搶占11和

I2o試求：(I)每個(gè)作業(yè)從投入到完成分別所需的時(shí)間。(2)從投入

到完成CPU的利用率.(3)12設(shè)備利用率。

(word完整版)操作系統(tǒng)第五版費(fèi)祥林一課后習(xí)題答案解析參考

答：畫出三個(gè)作業(yè)并行工作圖如下(圖中著色部分為作業(yè)等待時(shí)間)：，

CPUL.Job3iJob21Jobl|Job21Job3|1JoblI1Job3I

IIL_Job2J1Jobl1Job3I|Job3I

121JoblJ［一Job21Jobl1

Jobl1121CPU1II1CPUF12I

Job21II1CPU|1CPU[121

Job31CPUL1CPUi—■^-1II1CPU[11|

時(shí)間|_11111111111

(ms)

0102030405060708090100110

(1)Job1從投入到運(yùn)行完成需110ms,Job2從投入到運(yùn)行完成需

90ms,Job3從投入到運(yùn)行完成需110ms.

CPU空閑時(shí)間段為：60ms至70nls,80ms至90ms,100ms至110ms。

所以CPU利用率為(110—30)/10=72.7%。

設(shè)備11空閑時(shí)間段為：20nls至40ms,90ms至100ms,故11的利用率

為(110—30)/I10=72o7%o

設(shè)備I2空閑時(shí)間段為：30ms至50ms,故I2的利用率為(110—20)/110

二81.8%。

5在單CPU和兩臺(tái)I/O(11,12)設(shè)備的多道程序設(shè)計(jì)環(huán)境下，同時(shí)

投入三個(gè)作業(yè)運(yùn)行。它們的執(zhí)行軌跡如下：

Jobl:I2(30ms)、CPU(10rns)、11(30ms),CPU(10ms)

Job2：11(20ms)、CPU(20ms)、I2(40ms)

Job3:CPU(30ms)、11(20ms)

如果CPU、11和I2都能并行工作，優(yōu)先級(jí)從高到低為Job1、Job2和

Job3,優(yōu)先級(jí)高的作業(yè)可以搶占優(yōu)先級(jí)低的作業(yè)的CPUo

(word完整版)操作系統(tǒng)第五版費(fèi)祥林」果后習(xí)題答案解析參考

試求：(I)每個(gè)作業(yè)從投入到完成分別所需的時(shí)間.

(2)每個(gè)作業(yè)投入到完成CPU的利用率。

(3)I/O設(shè)備利用率.

答：畫出三個(gè)作業(yè)并行工作圖如下(圖中著色部分為作業(yè)等待時(shí)間)：

CPU:Job31Job2|Jobl|Job2|Jjb3|1,Jobl|

11Job2|IJobl1Job31

12,Jdbl1IJob2______________|

Jobl1121CPU1II1CPU1

Job21II1CPUE"1CPU1121

Job31CPUI~~-CPUk卬TII1

時(shí)間1111111111

(ms)

0102030405060708090

(1)Job1從投入到運(yùn)行完成需80ms,Job2從投入到運(yùn)行完成需90ms,

Job3從投入到運(yùn)行完成需90mso

(2)CPU空閑時(shí)間段為：60ms至70ms,80ms至90ms。所以CPU利

用率為(90-20)/90=77.78%。

(3)設(shè)備11空閑時(shí)間段為：20ms至40ms,故11的利用率為(90

—20)/90=77.78%o設(shè)備I2空閑時(shí)間段為：30ms至50ms,故

I2的利用率為(90—20)/90=77o78%。

6若內(nèi)存中有3道程序A、B、C,它們按A、B、C優(yōu)先次序運(yùn)行.

各程序的計(jì)算軌跡為：

A：計(jì)算(20)、1/0(30)、計(jì)算(10)

B：計(jì)算(40)、1/0(20)、計(jì)算(10)

c:計(jì)算(10)、I/O(30)、計(jì)算(20

（word完整版）操作系統(tǒng)第五版費(fèi)祥林一課后習(xí)題答案解析參考

如果三道程序都使用相同設(shè)備進(jìn)行I/O（即程序用串行方式使用設(shè)備，調(diào)

度開銷忽略不計(jì)）。試分別畫出單道和多道運(yùn)行的時(shí)間關(guān)系圖。兩種情況

下，CPU的平均利用率各為多少？

答：分別畫出單道和多道運(yùn)行的時(shí)間圖

（1）單道運(yùn)行時(shí)間關(guān)系圖

I/O|A||B|[C|

I???I

III1?I

Ie!11J

ii?|}

CPU[AjiBijB[Cj]cI

???1?!

I?lit，!

?i?tit?

?ii11?

時(shí)間?ii，iii_______iII_______i!iI

（ms）

02040506080100120140160180190

單道總運(yùn)行時(shí)間為190nlsoCPU利用率為（190—80）/190=57.9%

單道運(yùn)行時(shí)間關(guān)系圖

多道總運(yùn)行時(shí)間為140msoCPU利用率為（140-30）/140=78.6%

7若內(nèi)存中有3道程序A、B、C,優(yōu)先級(jí)從高到低為A、B和C,它

們單獨(dú)運(yùn)行時(shí)的CPU和I/O占用時(shí)間為：

程序A：60203010402020(ms)

1/02CPU1/01CPUI/OlCPUI/O】

程序B：3040703030(ms)

1/01CPU1/02CPUI/O2

程序C：40603070(ms)

CPUVO1CPU1/02

如果三道程序同時(shí)并發(fā)執(zhí)行，調(diào)度開銷忽略不計(jì)，但優(yōu)先級(jí)高的程序可中

（word完整版）操作系統(tǒng)第五版費(fèi)祥林一課后習(xí)題答案解析參考

斷優(yōu)先級(jí)低的程序，優(yōu)先級(jí)與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í)間圖：

CPUIC1BIA|B|c|口ICIA|C|

101IB|IA|C|A|IAI

（I）最早結(jié)束的程序?yàn)锽,最后結(jié)束的程序?yàn)镃o

（2）程序A為250ms。程序B為220ms0程序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%o

9、在某計(jì)笄機(jī)系統(tǒng)中，時(shí)鐘中斷處理程序每次執(zhí)行的時(shí)間為2nls（包括進(jìn)

程切換開銷）.若時(shí)鐘中斷頻率為60Hz，試問CPU用于時(shí)鐘中斷處理的時(shí)

(word完整版)操作系統(tǒng)第五版費(fèi)祥林一課后習(xí)題答案解析參考

間比率為多少？

答：因時(shí)鐘中斷頻率為60Hz,所以，時(shí)鐘周期為：I/60s=50/3ms。在每個(gè)時(shí)

鐘周期中，CPU花2ms執(zhí)行中斷任務(wù)。所以，CPU用于時(shí)鐘中斷處理的時(shí)間比率為：

2(50/3)=6/50=12%.

第二章處理器管理

1o下列指令中哪些只能在核心態(tài)運(yùn)行？

(I)讀時(shí)鐘日期；(2)訪管指令；(3)設(shè)時(shí)鐘日期；(4)加載PSW;(5)

置特殊寄存器：(6)改變存儲(chǔ)器映象圖；(7)啟動(dòng)I/O指令.

答：(3),(4),(5),(6),(7).

2假設(shè)有一種低級(jí)調(diào)度算法是讓“最近使用處理器較少的進(jìn)程”運(yùn)行，試

解釋這種算法對(duì)“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)行，由

(word完整版)操作系統(tǒng)第五版費(fèi)祥林一課后習(xí)題答案解析參考

于中斷是隨機(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í)間為：

TI==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í)間C

6、若有一組作業(yè)J1，…，Jn,其執(zhí)行時(shí)間依次為S1,…，Sn.如

果這些作業(yè)同時(shí)到試找出一種作業(yè)調(diào)度算法到達(dá)系統(tǒng)，并在一臺(tái)單CPU處

理器上按單道方式執(zhí)行。使得平均作業(yè)周轉(zhuǎn)時(shí)間最短。

答：首先，對(duì)n個(gè)作業(yè)按執(zhí)行時(shí)間從小到大重新進(jìn)行排序，則對(duì)n個(gè)作

業(yè)：J1Jn,創(chuàng)門的運(yùn)行時(shí)間滿足：S1WS2W……WS(n-l)

WSn'。那么有：

+

T=[S|+(S|+S：)+(S|+S；+Sj)+…+(S]+S)+…+So)]/n

=[nXS|+(n-l)XS：+(n?3)XS3]+,??+SB]]/n

x,

+S2'+S3+—+S0)-(OS1+lXS：+2XS3+-+(n-l)Sj/n

由r任何調(diào)度方式下，S1'+S2'+S3'+…+Sn'為一個(gè)確定的數(shù)，而

當(dāng)S1'WS2'<S(n-1)'WSn'時(shí)才有：0*S1+1*S2+2*S3+-

(word完整版)操作系統(tǒng)第五版費(fèi)祥林—課后習(xí)題答案解析參考

(n—1)Sn的值最大，也就是說，此時(shí)T值最小。所以，按短作業(yè)優(yōu)先調(diào)

度算法調(diào)度時(shí)，使得平均作業(yè)周轉(zhuǎn)時(shí)間最短。

7、假定執(zhí)行表中所列作業(yè)，作業(yè)號(hào)即為到達(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í)間。

作業(yè)號(hào)執(zhí)行時(shí)間優(yōu)先權(quán)

1103

21\

323

414

552

(1)采用FCFS算法調(diào)度作業(yè)，運(yùn)作情況:

執(zhí)行次序執(zhí)行時(shí)間等待時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間

1100010101

211010111111

32111113136.5

411313141414

55141419193.8

作業(yè)平均冏轉(zhuǎn)時(shí)間T=(10+ll+13+]4+19)/5=13.4

作業(yè)平均帶權(quán)周轉(zhuǎn)酎問WHl+ll+6.5+14+3.8)/5=7.26

(2)采用雙算法調(diào)度作業(yè)，若令時(shí)間片長(zhǎng)=1,各作業(yè)執(zhí)行情況為：1、

2、3、4、5、1、3、5、1、5、1、5、1、5、1、1、1、

1、1.

(word完整版)操作系統(tǒng)第五版費(fèi)祥林J果后習(xí)題答案解析參考

作業(yè)執(zhí)行時(shí)間提交時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間

110019191.9

210222

320773.5

410444

55014142.8

作業(yè)平均周轉(zhuǎn)時(shí)間T-(19+2+7+4+l4)/5-9.2

作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間WY1.9+2+3.5+4+2.8)75=2.84

(3)采用SJF算法調(diào)度作業(yè)，運(yùn)作情況:

執(zhí)行次序執(zhí)行時(shí)間等待時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間

2100111

4111222

3222442

5544991.8

1109919191.9

作業(yè)平均周轉(zhuǎn)時(shí)間T?(l+2+4-h9+19)/5=7

作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間W?(1+2+2+1.8+1.9)/5-1.74

(4)采用非剝奪優(yōu)先權(quán)算法調(diào)度作業(yè)，運(yùn)作情況：

8對(duì)某系統(tǒng)進(jìn)行監(jiān)測(cè)后表明平均每個(gè)進(jìn)程在I/O阻塞之前的運(yùn)行時(shí)間為

T。一次進(jìn)程'切換的系統(tǒng)開銷時(shí)間為So若采用時(shí)間片長(zhǎng)度為Q的時(shí)

間片輪轉(zhuǎn)法，對(duì)下列各種情況算出CPU利用率。

1)Q=?2)Q>T3)S<Q<T4=Q=S5=Q接近于0

答：I)Q-ooCPU利用率=17(T+S)

2)Q>TCPU利用率=T/(T+S)

3)T>Q>SCPU利用率=Q/(Q+S)

4)Q-SCPU利用率=50%

5)Q-0CPU利用率一0

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取值不定，按照

（word完整版）操作系統(tǒng)第五版費(fèi)祥林」果后習(xí)題答案解析參考

以下情況討論:

1）xW3次序?yàn)?x.3,5.6,9

2）3<xW5次序?yàn)椋?,x,5,6,9

3）5<xW6次序?yàn)椋?.5,x,6.9

4）6<xW9次序?yàn)閟3,5.6,x,9

5）9<x次序?yàn)?3.5.6,9.x

10.有5個(gè)批處理作業(yè)A到E均己到達(dá)計(jì)算中心，其運(yùn)行時(shí)間分別2、4、

6、8和10分鐘：各自的優(yōu)先級(jí)分跳狠掀完為、、飛、飛、氏積5、這

里5為最高級(jí).對(duì)于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í)間。（對(duì)I）每個(gè)作業(yè)

獲得相同的2分鐘長(zhǎng)的時(shí)間片；對(duì)2）到4）采用單道運(yùn)行，直到結(jié)束。）

答：（I）FCFS調(diào)度算法

執(zhí)行次序執(zhí)行時(shí)間等待時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間

C6061

D86141.75

B414184.5

E1018282.8

A2283015

作業(yè)平均周轉(zhuǎn)時(shí)間T?(6+14+18+28+30)/5=19.2

作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間W=(l+1.75-M.5+2.8+15)/5-5.01

（2）優(yōu)先級(jí)調(diào)度算法

執(zhí)行飲序執(zhí)行時(shí)間等待時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)冏轉(zhuǎn)時(shí)間

E100101

D810182.25

C618244

B424287

A2283015

作業(yè)平均周轉(zhuǎn)時(shí)間T-(10+l8+24+28+30)/5=22

作業(yè)平均帶權(quán)周轉(zhuǎn)付問W-(l+2.25+4+7+15)/5-5.85

（3）時(shí)間片輪轉(zhuǎn)法

（word完整版）操作系統(tǒng)第五版費(fèi)祥林一課后習(xí)題答案解析參考

作業(yè)執(zhí)行時(shí)間等待時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間

A2021

B48123

C614203.33

D818263.25

E1020303

作業(yè)平均周轉(zhuǎn)時(shí)間TK2+12+20+26+30)/5=18

作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間W=(l+3+3.33+3.25+3)/5=2.71

按次序ABCDEBCDECDEDEE輪轉(zhuǎn)執(zhí)行。

（4）SJF調(diào)度算法

作業(yè)執(zhí)行時(shí)間等待時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間

A2021

B4261.5

C66122

D812202.5

E1020303

作業(yè)平均周轉(zhuǎn)時(shí)間T-(2+6+12+20+30)/5=14

作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間W=(l+L5+2+2.5+3y5=2

11、有5個(gè)批處理作業(yè)A到E均已到達(dá)計(jì)算中心，其運(yùn)行時(shí)間分別10、

6、2、4和8分鐘；各自的優(yōu)先級(jí)分別被規(guī)定為3、5、2、1和4,

這里5為最高級(jí).若不考慮系統(tǒng)切換開銷，計(jì)算出平均作業(yè)周轉(zhuǎn)時(shí)間。（1）

FCFs（按A、B、C、D、E）；（2）優(yōu)先級(jí)調(diào)度算法，（3）時(shí)間片

輪轉(zhuǎn)法（每個(gè)作業(yè)獲得相同的2分鐘長(zhǎng)的時(shí)間片）。

（1）FCFS調(diào)度算法

(word完整版)操作系統(tǒng)第五版費(fèi)祥林J果后習(xí)題答案解析參考

執(zhí)行次序執(zhí)行時(shí)間等待時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間

A100101

B610162.66

C216189

D4182255

E822303.75

作業(yè)平均周轉(zhuǎn)時(shí)間T?(10+16+l8+22+30)/5=】9.2

作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間W=(1+2.66+9+5.5+3.75)/5=4.38

(2)優(yōu)先級(jí)調(diào)度算法

執(zhí)行次序執(zhí)行時(shí)間等待時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間

B6061

E861.75

A10142.4

C22413

D4267.5

作業(yè)平均周轉(zhuǎn)時(shí)間T=(6+14+24+26+30)/5=20

作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間W=(1+1.75+2.4+13+7.5)/5=5.13

(3)時(shí)間片輪轉(zhuǎn)法

按次序ABCDEABDEABEAEA輪轉(zhuǎn)執(zhí)行。

帶權(quán)周轉(zhuǎn)時(shí)

執(zhí)行時(shí)間等待時(shí)間周轉(zhuǎn)時(shí)間

作業(yè)

間

A1020303

B6I6223.66

C2463

D4I2164

E820283.5

作業(yè)平均周轉(zhuǎn)時(shí)T=(30+22+6+16+28)/5=20o4

(w。rd完整版)操作系統(tǒng)第五版費(fèi)祥林—課后習(xí)題答案解析參考

間作業(yè)平均帶權(quán)W=(3+3,66+3+4+3.5)/5=3.43

周轉(zhuǎn)時(shí)間

12(I)假定一個(gè)處理器正在執(zhí)行兩道作業(yè)，一道以計(jì)算為主，另一道以輸

入輸出為主，你J等怎樣賦予它們占有處理器的優(yōu)先級(jí)？為什么？

(2)假定一個(gè)處理器正在執(zhí)行三道作業(yè)，一道以計(jì)算為主，第二道以輸入

輸出為主，第三道為計(jì)算與輸入輸出均勻。應(yīng)該如何賦予它們占有處理器

的優(yōu)先級(jí)使得系統(tǒng)效率較高？

答：處理器調(diào)度算法會(huì)考慮以下因素：作業(yè)響應(yīng)時(shí)間要求；讓CPU盡量和

外圍設(shè)備并行工作；限制一個(gè)計(jì)算進(jìn)程長(zhǎng)時(shí)間霸占處理器。因而，(1)

F0為主作業(yè)優(yōu)先級(jí)高。(2)輸入輸出為主作業(yè)優(yōu)先級(jí)最高，輸入輸出

均勻的作業(yè)其次，而計(jì)算為主作業(yè)的優(yōu)先級(jí)最低。

13請(qǐng)你設(shè)計(jì)一種先進(jìn)的計(jì)算機(jī)體系結(jié)構(gòu)，它使用硬件而不是中斷來完成

進(jìn)程切換，則CPU需要哪些信息？請(qǐng)描述用硬件完成進(jìn)程切換的工作過

程.

答：該計(jì)算機(jī)有一個(gè)專用硬件寄存器，它始終存放指向當(dāng)前運(yùn)行進(jìn)程的PCB

的指針。當(dāng)系統(tǒng)中發(fā)生了一個(gè)事件，如F0結(jié)束事件，CPU便可把運(yùn)行進(jìn)程

的上下文保存到專用硬件寄存器指針指向的PCB中保護(hù)起來，然后，CPU

轉(zhuǎn)向中斷向量表，找到設(shè)備中斷處理程序入口，讓專用硬件寄存器指針指

(word完整版)操作系統(tǒng)第五版費(fèi)祥林一課后習(xí)題答案解析參考

向(設(shè)備)中斷服務(wù)例程，于是，便可啟動(dòng)中斷服務(wù)例程工作。

14設(shè)計(jì)一條機(jī)器指令和一種與信號(hào)量機(jī)制不同的算法，使得并發(fā)進(jìn)程對(duì)

共享變量的使用不會(huì)出現(xiàn)與時(shí)間有關(guān)的錯(cuò)誤。

解：

(I)設(shè)計(jì)機(jī)器指令。

設(shè)計(jì)一條如下的”測(cè)試、比較和交換”三地址指令，提供了一種硬件互斥解

決方案：

R1R3B2D2

TC&S

該指令的功能如下：

I)C為一個(gè)共享變量，由地址2、即變址(B2)+D2給出，

(2)(RI)與(C)比較，

(3)如果(RI)二(C)則e3)TC,棄置條件碼為“00”,

如果(R1)手6)則(C)TRI,并置條件碼為“01”.

(2)編寫進(jìn)程訪問共享變量的程序.

對(duì)每個(gè)訪問共享變量C的進(jìn)程，編寫訪問共享變量的程序段為：

說明

(C)TRI；共享變量C的值保護(hù)到RI中。

Ioop2：(R1)TRI的值傳送到R3中，進(jìn)程修改共享變量時(shí)，先對(duì)

R3操作(不是直接操作C)。

/decreaseR3;R3加1/減1，進(jìn)程歸還/申請(qǐng)由共享變量C代

&S；表的共享資源(假定每次一個(gè))。

condition=01)執(zhí)行”測(cè)試、比較和交換”指令。

（word完整版）操作系統(tǒng)第五版費(fèi)祥林一課后習(xí)題答案解析參考

Ioop2；條件碼=01,轉(zhuǎn)向循環(huán)Ioop2；否則離開臨界區(qū)。

（3）程序執(zhí)行說明。

此解與互斥使用共享變量的思路絕然不同，并發(fā)運(yùn)行的進(jìn)程可不互斥地訪

問它們的共享變量。此方案認(rèn)為造成共享變量C值錯(cuò)誤的原因在于：一個(gè)

進(jìn)程（PI）在改變C值的過程中，另一個(gè)進(jìn)程伊2）插進(jìn)來也改變了C的

值，而本進(jìn)程（PI）卻不知道，造成了c值結(jié)果不正確。如果有辦法使本

進(jìn)程口1）能知道C值是否改變，改變的話在繼承改變了的C值的基礎(chǔ)

上，再作自己的改變操作，則就不會(huì)導(dǎo)致共享變量C值的錯(cuò)誤。為此，本

解決方案中，當(dāng)一個(gè)進(jìn)程I）準(zhǔn)備改變C值時(shí)，先把C的值保護(hù)在RI中，

然后，通過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)程（PI）修改過的新值送C（即（R3）一

C）；若不相等，說明C值在工作期間被改變過，則應(yīng)該繼承C的新值（即

（C）一RI）并且返回到Ioop2處重新對(duì)C值計(jì)數(shù)，以此保證C值的最

終結(jié)果的正確性。這里提及”進(jìn)程工作期間”指的是一個(gè)進(jìn)程從開始至結(jié)

束對(duì)共享變量C值的操作的這段時(shí)間，也就是執(zhí)行進(jìn)程，'I晦界區(qū)”這

段程序的時(shí)間.此外，在進(jìn)程進(jìn)入臨界區(qū)之前，應(yīng)等待直到C為非。（即

（word完整版）操作系統(tǒng)第五版費(fèi)祥林一課后習(xí)題答案解析參考

有資源可用）為止。

（4）舉例。

假定系統(tǒng)中有靜態(tài)分配資源磁帶機(jī)共3臺(tái)，被N個(gè)進(jìn)程共享，由共享變

量C來代表可用磁帶機(jī)臺(tái)數(shù)，其初值為3o現(xiàn)有并發(fā)進(jìn)程P1和P2均申

請(qǐng)使用磁帶機(jī)，執(zhí)行臨界區(qū)程序。

進(jìn)程PI執(zhí)行臨界區(qū)程序

（C）TR1;因（0=3,故（R1）=3o

Ioop2：（RI）TR3因（R1）=3,故（R3）當(dāng)前也=3.

decreaseR3：申請(qǐng)使用磁帶機(jī)，做減1操作，故（R3）=2.

TC&S執(zhí)行”測(cè)試、比較和交換，，TC&S指令。

如果Rk（C）則（R3）TC,即（C）=2，并置條件碼為"00“，跳出臨界

區(qū)程序，去使用磁帶機(jī)。

如果（RI）手（C）,例如，（C）=2,說明進(jìn)程P2搶先申請(qǐng)了磁帶機(jī),

所以，C與保護(hù)在R1中的值不一樣了（C的值必

小于RI的值），應(yīng)以C的當(dāng)前值為準(zhǔn)，執(zhí)行（C）RI（R1此時(shí)變?yōu)?）,

并置條件碼為“01"，轉(zhuǎn)向foopZo于是伍1）=2,跟著（R3卜2o

接著卿）減1后應(yīng)=1了。再執(zhí)行TC&S時(shí)，由于伍1卜（C）=2,

會(huì)使C變?yōu)?。

r（conditio二01）Ioop2;

巧單道批處理系統(tǒng)中，下列三個(gè)作業(yè)采用先來先服務(wù)調(diào)度算法和最高響應(yīng)

比優(yōu)先算法進(jìn)行調(diào)度，哪一種算法性能較好？請(qǐng)完成下表：

提交時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)帶權(quán)周

作業(yè)

間轉(zhuǎn)時(shí)間

（word完整版）操作系統(tǒng)第五版費(fèi)祥林一課后習(xí)題答案解析參考

110:002：00

210:101：00

310:250:25

平均作業(yè)周轉(zhuǎn)時(shí)間二

平均作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間W=

FIFO

開始完成周轉(zhuǎn)帶權(quán)周

作業(yè)提交時(shí)間運(yùn)行時(shí)間

時(shí)間時(shí)間時(shí)間轉(zhuǎn)時(shí)間

110：002：0010:0012:002120/120

210：101：0012:0013:002:50170/60

310：250：2513:0013:253180/25

平均作業(yè)周轉(zhuǎn)時(shí)間=2.61

平均作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間W=3.68

HRRF

開始完成周轉(zhuǎn)帶權(quán)周

作業(yè)提交時(shí)間運(yùn)行時(shí)間

時(shí)間時(shí)間時(shí)間轉(zhuǎn)時(shí)間

110：002：0010:0012:002120/120

210：101：0012:2513:253:15195/60

310：250：2512:0012:252120/25

平均作業(yè)周轉(zhuǎn)時(shí)間=2.41

平均作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間W=3.02

可見HRRF比FIFO要好

（word完整版）操作系統(tǒng)第五版費(fèi)祥林一課后習(xí)題答案解析參考

16若有如表所示四個(gè)作業(yè)進(jìn)入系統(tǒng)，分別計(jì)算在FCFS、S開和HRR衛(wèi)

算法下的平均周轉(zhuǎn)時(shí)間與帶權(quán)平均周轉(zhuǎn)時(shí)間.（時(shí)間以十進(jìn)制表示）

作業(yè)提交時(shí)間（時(shí)）估計(jì)運(yùn)行時(shí)間（小時(shí)）

18.002.00

28.500.50

39.000.10

49.500.20

答:

FCFSSJFHRRF

作業(yè)開始完成周轉(zhuǎn)開始完成周轉(zhuǎn)開始完成周轉(zhuǎn)

時(shí)間時(shí)間時(shí)間時(shí)間時(shí)間時(shí)間時(shí)間時(shí)間時(shí)間

18.0010.002.008.0010.002.0C8.0010.002.00

210.0010.50Z0010.3010.802.3010.1010.602.10

310.5010.601.6010.0010.101.1010.0010.101.10

410.6010.801.3010.1010.300.8010.6010.801.30

平均周T-L725T-L55T-1.625

轉(zhuǎn)時(shí)間-

帝權(quán)平均W-6.875W-5.15W-5.675

周轉(zhuǎn)時(shí)間，

17Kleinrock提出一種動(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賦以不同值可得到不同算法.（I）若&>13><5是什么算法？

（2）若aVbVc是什么算法

答：（I）是先進(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)程

(word完整版)操作系統(tǒng)第五版費(fèi)祥林—課后習(xí)題答案解析參考

的優(yōu)先權(quán)T降得快，故后進(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í)間由下表給出：

作業(yè)提交時(shí)間估計(jì)運(yùn)行時(shí)間(分鐘)

i8：do

28：2035

38：25