操作系統(tǒng)課后答案(一)

CH1應(yīng)用題參考答案

I有一臺計算機，具有1MB內(nèi)存，操作系統(tǒng)占用200KB：每個用戶進程各占200KB。如果用戶

進程等待I/O的時間為80%,假設(shè)增加1MB內(nèi)存，那么CPU的利用率提高多少？

答：設(shè)每個進程等待I/O的百分比為P,那么n個進程同時等待I/O的概率是P",當n個進程同時

等待I/O期間CPU是空閑的，故CPU的利用率為1-曰。由題意可知，除去操作系統(tǒng)，內(nèi)存還

能容納4個用戶進程，由于每個用戶進程等待I/O的時間為80%,故：

CPU利用率=1-(80%)4=0.59

假設(shè)再增加1MB內(nèi)存，系統(tǒng)中可同時運行9個用戶進程，此時：

CPU利用率=1-(80%)9=0.87

故增加1MB內(nèi)存使CPU的利用率提高了47%：

87%4-59%=147%

147%-100%=47%

2一個計算機系統(tǒng)，有一臺輸入機和一臺打印機，現(xiàn)有兩道程序投入運行，且程序A先開始做，

程序B后開始運行。程序A的運行軌跡為：計算50ms＞打印100ms、再計算50ms＞打印100ms,

結(jié)束。程序B的運行軌跡為：計算50ms、輸入80ms、再計算100ms,結(jié)束。試說明(1)兩道程

序運行時，CPU有無空閑等待？假設(shè)有，在哪段時間內(nèi)等待？為什么會等待？(2)程序A、B有

無等待CPU的情況？假設(shè)有，指出發(fā)生等待的時刻。

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

IA計算B計算B計算

處理器

輸入機B輸入|

打印機A打印|A打印|

程序A1計笠打印|計苴打印|

程序B計第輸入「計部|

時間(ms)|1111

050100150180200250300

(I)兩道程序運行期間，CPU存在空閑等待，時間為100至150ms之間(見圖中有色局部)。

(2)程序A無等待現(xiàn)象，但程序B有等待。程序B有等待時間段為18()ms至200ms間(見圖中有色

局部)。

3設(shè)有三道程序，按A、B、C優(yōu)先次序運行，其內(nèi)部計算和I/O操作時間由圖給出。

ABC

Cn=30msC2i=60msC3i=20ms

Ii2=40ms[22=30msh2=40ms

C)3=10msC23=10msC3j=2Oms

試畫出按多道運行的時間關(guān)系圖(忽略調(diào)度執(zhí)行時間)，完成三道程序共花多少時間？比單道

運行節(jié)省了多少時間？假設(shè)處理器調(diào)度程序每次進行程序轉(zhuǎn)換化時1ms,試畫出各程序狀態(tài)轉(zhuǎn)

換的時間關(guān)系圖。

答：

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

時間0378101213141719單位10ms

I/O112122132

CPUC11C21Cl：1C21C31C23C33_

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

忽略調(diào)度執(zhí)行時間，多道運行方式(非搶占式)：

時間0379101213141618單位10ms

I/O112122132

CPUCllC21C13C3I(：23C33

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

4在單CPU和兩臺1/0(11,12)設(shè)備的多道程序設(shè)計環(huán)境下，同時投入三個作業(yè)運行。它們的執(zhí)行軌

跡如下：

Jobl：I2(30ms)>CPU(lOms)、Il(30ms)CPU(lOms)、I2(20ms)

Job2：Il(20ms)>CPU(20ms)、I2(40ms)

Job3：CPU(30ms)>Il(20ms)、CPU(lOms)、Il(10ms)

如果CPU、Il和12都能并行工作,優(yōu)先級從高到低為Jobl、Job2和Job3,優(yōu)先級高的作業(yè)可以搶

占優(yōu)先級低的作業(yè)的CPU,但不搶占II和12。試求：(1)每個作業(yè)從投入到完成分別所需的時間。

⑵從投入到完成CPU的利用率。(3)1/0設(shè)備利用率。

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

CPULJob3IJob2JoblIJob2IJob3|IJobl|IJob3|

11|_Job2JJobl|Job3||Job3

12|_Jobl1Job2IJobl

Jobl|_12CPU1IIICPUI-~l12

Job2II1CPU匚1CPU112_J

—

Job3|_CPUl-iCPUr1IIICPU|Il

時間|_11]_1ii1111

(ms)

0102030405060708090100110

(1)Jobl從投入到運行完成需ll()ms,Job2從投入到運行完成需90ms,Job3從投入到運行完成需

1lOmso

⑵CPU空閑時間段為：60ms至70ms,80ms至90ms,100ms至110ms。所以CPU利用率為

(110-30)/110=72.7%o

(3)設(shè)備II空閑時間段為:20ms至40ms,90ms至100ms,故II的利用率為(110-30)/110=72.7%。

設(shè)備12空閑時間段為:30ms至50ms,故12的利用率為(11520)/110=81.8%。

5在單CPU和兩臺1/0(11,⑵設(shè)備的多道程序設(shè)計環(huán)境下，同時投入三個作業(yè)運行。它們的執(zhí)行軌

跡如下：

Jobl：I2(30ms)>CPU(lOms)、Il(30ms)>CPU(lOms)

Job2：Il(20ms)>CPU(20ms)、I2(40ms)

Job3：CPU(30ms)、Il(20ms)

如果CPU、Il和12都能開行工作，優(yōu)先級從高到低為Jobl、Job2和Job3,優(yōu)先級高的作業(yè)可以搶

占優(yōu)先級低的作業(yè)的CPU。試求：(1)每個作業(yè)從投入到完成分別所需的時間。⑵每個作業(yè)投入到

完成CPU的利用率。(3)1/0設(shè)備利用率。

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

I/O

CPU

時間

(ms)

02040506080100120140

多道總運行時間為140ms°CPU利用率為（140-30）/140=78.6%

7假設(shè)內(nèi)存中有3道程序A、B、C,優(yōu)先級從高到低為A、B和C,它們單獨運行時的CPU和

I/O占用曲1■間為：

程序A：60203010402020(ms)

I/O2CPUI/OICPUI/OICPUI/OI

程序B：304070303()(ms)

I/O1CPU1/02CPUI/O2

程序C：40603070(1ms)

CPUI/OlCPUI/O2

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

級與I/O設(shè)備無關(guān)。試畫出多道運行的時間關(guān)系圖，并問最早與最遲結(jié)束的程序是哪個？每道程序

執(zhí)行到結(jié)束分別用了多少時間？計算三個程序全部運算結(jié)束時的CPU利用率？

答：畫出三個作業(yè)并發(fā)執(zhí)行的時間圖：

CPU|C|B|A|B|CIf|IB|CIAICI

[01IB|1AlC1Al|A|

[02?A||B||B||C

A|102Cpu|101|P||101|cpu|101|

u

B|1()1|cpu|巳11°2?cpu|102|

C

101「CPU」102

時間

(ms)

0306090120150180210240270300330

（1）最早結(jié)束的程序為B,最后結(jié)束的程序為C。

（2）程序A為250mso程序B為220ms。程序C為310ms。

⑶CPU利用率為（310-120）/310=61.3%

8有兩個程序，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秒。兩個

程序共用了80秒，CPU化了4。秒。故CPU利用率為40/80=50%o

9在某計算機系統(tǒng)中，時鐘中斷處理程序每次執(zhí)行的時間為2ms（包括進程切換開銷）。假設(shè)

時鐘中斷頻率為60HZ,試問CPU用于時鐘中斷處理的時間比率為多少？

答：因時鐘中斷頻率為60HZ,所以，時鐘周期為：l/60s=50/3ms。在每個時鐘周期中，CPU花2ms

執(zhí)行中斷任務(wù)。所以,CPU用于時鐘中斷處理的時間比率為：2（50/3）=6/50=12%o

CH2應(yīng)用題參考答案

1以下指令中哪些只能在核心態(tài)運行？

（1）讀時鐘日期；（2）訪管指令；（3）設(shè)時鐘日期；（4）加載PSW；（5）置特殊存放器；（6）改

變存儲器映象圖；（7）啟動I/O指令。

答：⑶，（4）,（5）,（6）,（7）。

2假設(shè)有一種低級調(diào)度算法是讓“最近使用處理器較少的進程”運行，試解釋這種算法對“I/O

繁重”型作業(yè)有利，但并不是永遠不受理“處理器繁重”型作業(yè)。

答:因為I/O繁忙型作業(yè)忙于I/O,所以它CPU用得少，按調(diào)度策略能優(yōu)先執(zhí)行。同樣原因一個進

程等待CPU足夠久時，由于它是“最近使用處理器較少的進程”，就能被優(yōu)先調(diào)度，故不會饑餓。

3并發(fā)進程之間有什么樣的相互制約關(guān)系？以下口常生活中的活動是屬哪種制約關(guān)系：（1）踢足

球，（2）吃自助餐，（3）圖書館借書，（4）電視機生產(chǎn)流水線工序。

答：并發(fā)進程之間的根本相互制約關(guān)系有互斥和同步兩種。其中（I）、（3）為互斥問題。（2）、（4）為同

步問題。

4在按動態(tài)優(yōu)先數(shù)調(diào)度進程的系統(tǒng)中，每個進程的優(yōu)先數(shù)需定時重新計算。在處理器不斷地在

進程之間交替的情況下，重新計算進程優(yōu)先數(shù)的時間從何而來？

答：許多操作系統(tǒng)重新計算進程的優(yōu)先數(shù)在時鐘中斷處理例程中進行，由于中斷是隨機的，碰到哪

個進程，就插入哪個進程中運行處理程序，并把處理時間記在這個進程的賬上。

5假設(shè)后備作業(yè)隊列中等待運行的同時有三個作業(yè)JI、J2、J3,它們各自的運行時間為a、b、c,

且滿足a<b<c,試證明采用短作業(yè)優(yōu)先算法調(diào)度能獲得最小平均作業(yè)周轉(zhuǎn)時間。

答：采用短作業(yè)優(yōu)先算法調(diào)度時，三個作業(yè)的總周轉(zhuǎn)時間為：

T1=a+（a+b）+（a+b+c）=3a+2b+c①

假設(shè)不按短作業(yè)優(yōu)先算法調(diào)度：不失一般性，設(shè)調(diào)度次序為：J2.JL.J3。那么三個作業(yè)的總周轉(zhuǎn)

時間為：

T2=b+(b+a)+(b+a+c)=3b+2a+c②

令②-①式得到：

T2-Tl=b-a>0

可見，采用短作業(yè)優(yōu)先算法調(diào)度才能獲得最小平均作業(yè)周轉(zhuǎn)時間。

6假設(shè)有一組作業(yè)J1,…，Jn,其執(zhí)行時間依次為S1,…，Sno如果這些作業(yè)同時到達系統(tǒng)，

并在一臺單CPU處理器上按單道方式執(zhí)行。試找出一種作業(yè)調(diào)度算法，使得平均作業(yè)周轉(zhuǎn)時

間最短。

答：首先，對n個作業(yè)按執(zhí)行時間從小到大重新進行排序，那么對n個作業(yè)：J1，，…，Jn\它們

的運行時間滿足：S1WS2，W…WS(n-l)，WSn\那么有：

T=[Si+(Si+S2)+(Si+S2+S3)+…+(S]+S2+S3+,,,+Sn)J/n

=[nXSi'+(n-l)XS2'+(n-3)XS3']+-+S?]]/n

，

=(S；+S2+Sj+…+Sn'MOXSr+lXS2+2XS；+-+(n-l)S?']/n

由于任何調(diào)度方式下，S「-S2'+S；+…+S；為一個確定的數(shù)，而當Si'WS2'<…WS.DWS；時

才有：OXS/+1XS2'+2XS3'+…+(n-l)S；的值最大,也就是說，此時T值最小。所以,按短作

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

7假定執(zhí)行表中所列作業(yè)，作業(yè)號即為到達順序，依次在時刻0按次序1、2、3、4、5進入單

處理器系統(tǒng)。

1)分別用先來先效勞調(diào)度算法、時間片輪轉(zhuǎn)算法、短作業(yè)優(yōu)先算法及非強占優(yōu)先權(quán)調(diào)度算法

算出各作業(yè)的執(zhí)行先后次序(注意優(yōu)先權(quán)高的數(shù)值小)；

2)計算每種情況下作業(yè)的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。

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

1103

211

323

414

552

答:

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

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

11()001()1()1

211010111111

3211II13136.5

411313141414

55141419193.8

作業(yè)平均周轉(zhuǎn)時間T=(10+l1+13+14+19)/5=13.4

作業(yè)平均帶權(quán)周轉(zhuǎn)時間W=(l+ll+6.5+14+3.8)/5=726

(2)采用RR算法調(diào)度作業(yè)，假設(shè)令時間片長=1，各作業(yè)執(zhí)行情況為：1、2、3、4、5、1、3、5、

1、5、1、5、1、5、1、1、1、1、1。

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

110019191.9

210222

320773.5

410444

55014142.8

作業(yè)平均周轉(zhuǎn)時間T=(l9+2+7+4+14)/5=9.2

作業(yè)平均帶權(quán)周轉(zhuǎn)時間W=(1.9+2+3.5+4+2.8)/5=2.84

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

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

2100111

4111222

3222442

5544991.8

1109919191.9

作業(yè)平均周轉(zhuǎn)時間T=(1+2+4+9+19)75=7

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

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

執(zhí)行次序優(yōu)先數(shù)執(zhí)行時間等待時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間

211011

525161.2

13106161.6

33216189

441181919

作業(yè)平均周轉(zhuǎn)時間T=(1+6+16+18+19)/5=12

作業(yè)平均帶權(quán)周轉(zhuǎn)時間W=(1+1.2+1.6+9+19)/5=636

8對某系統(tǒng)進行監(jiān)測后說明平均每個進程在I/O阻塞之前的運行時間為To一次進程切換的系統(tǒng)

開銷時間為So假設(shè)采用時問片長度為Q的時向片輪轉(zhuǎn)法，對以下各種情況算出CPU利用率。

1)Q=82)Q>T3[S<Q<T4=Q=S5=Q接近于0

答：

1)Q=8CPU利用率=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個待運行的作業(yè)，各自預(yù)計運行時間分別是：9、6、3、5和x,采用哪種運行次序使得

平均響應(yīng)時間最短？

答：按照最短作業(yè)優(yōu)先的算法可以使平均響應(yīng)時間最短。X取值不定，按照以下情況討論：

1）xW3次序為：x,3,5,6,9

2）3<xW5次序為：3,x,5,6,9

3）5<xW6次序為：3,5,x,6,9

4）6<xW9次序為：3,5,6,x,9

5）9<x次序為：3,5,6,9,x

10有5個批處理作業(yè)A到E均已到達計算中心，其運行時間分別2、4、6、8和10分鐘；各自

的優(yōu)先級分別被規(guī)定為1、2、3、4和5,這里5為最高級。對于1）時間片輪轉(zhuǎn)算法、2）優(yōu)

先數(shù)法、3）短作業(yè)優(yōu)先算法、4）先來先效勞調(diào)度算法（按到達次序C、D、B、E、A）,在忽

略進程切換時間的前提下，計算出平均作業(yè)周轉(zhuǎn)時間c（對1）每個作業(yè)獲得相同的2分鐘長

的時間片；對2）到4）采用單道運行，直到結(jié)束。）

答：

（DFCFS調(diào)度算法

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

C6061

D86141.75

B414184.5

E1018282.8

A2283015

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

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

⑵優(yōu)先級調(diào)度算法

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

E100101

D810182.25

C618244

B424287

A2283015

作業(yè)平均周轉(zhuǎn)時間T=(l0+18+24+28+30)/5=22

作業(yè)平均帶權(quán)周轉(zhuǎn)時間W=(1+2.25+4+7+15)/5=5.85

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

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

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

A2021

B48123

C614203.33

D818263.25

E1020303

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

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

A2021

B4261.5

C66122

D812202.5

E1020303

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

作業(yè)平均帶權(quán)周轉(zhuǎn)時間W=(1+1.5+2+2.5+3)75=2

II有5個批處理作業(yè)A到E均已到達計算中心，其運行時間分別10、6、2、4和8分鐘：各自

的優(yōu)先級分別被規(guī)定為3、5、2、1和4,這里5為最高級。假設(shè)不考慮系統(tǒng)切換開銷，計算

出平均作業(yè)周轉(zhuǎn)時間。⑴FCFS（按A、B、C、D、E）；（2）優(yōu)先級調(diào)度算法，（3）時間片輪轉(zhuǎn)

法（每個作業(yè)獲得相同的2分鐘長的時間片）。

答：

（DFCFS調(diào)度算法

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

A10010I

B610162.66

C216189

D418225.5

E822303.75

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

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

⑵優(yōu)先級調(diào)度算法

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

B601

E861.75

A10142.4

C22413

D4267.5

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

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

⑶時間片輪轉(zhuǎn)法

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

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

A1020303

B616223.66

C2463

D412164

E820283.5

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

作業(yè)平均帶權(quán)周轉(zhuǎn)時間W=(3+3.66+3+4+3.5)/5=3.43

12(1)假定一個處理器正在執(zhí)行兩道作業(yè)，一道以計算為主，另一道以輸入輸出為主，你將怎樣

賦予它們占有處理器的優(yōu)先級?為什么？

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

計算與輸入輸出均勻。應(yīng)該如何賦予它們占有處理器的優(yōu)先級使得系統(tǒng)效率較高？

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

限制一個計算進程長時間霸占處理器。因而，(1)1/0為主作業(yè)優(yōu)先級高。(2)輸入輸出為主作業(yè)優(yōu)

先級最高，輸入輸出均勻的作業(yè)其次，而計算為主作業(yè)的優(yōu)先級最低。

13請你設(shè)計一種先進的計算機體系結(jié)構(gòu)，它使用硬件而不是中斷來完成進程切換，那么CPU需

要哪些信息？請描述用硬件完成進程切換的工作過程。

答：該計算機有一個專用硬件存放器，它始終存放指向當前運行進程的PCB的指針。當系統(tǒng)中發(fā)

生了一個事件，如I/O結(jié)束事件，CPU便可把運行進程的上下文保存到專用硬件存放器指針指向的

PCB中保護起來，然后，CPU轉(zhuǎn)向中斷向量表，找到設(shè)備中斷處理程序入口，讓專川硬件存放器

指針指向(設(shè)備)中斷效勞例程，于是，便可啟動中斷效勞例程工作。

14單道批處理系統(tǒng)中，以下二個作業(yè)采用先米先效勞調(diào)度算法和最高響應(yīng)比優(yōu)先算法進行調(diào)度,

哪一種算法性能較好？請完成下表：

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

作業(yè)提交時間運行時間

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

110：002：00

210：101：00

310：250：25

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

平均作業(yè)帶權(quán)周轉(zhuǎn)時間亞二

答:

FIFO

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

作業(yè)提交時間運行時間

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

110：002：0010:0012:002120/120

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

310：250：2513:0013:253180/25

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

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

HRRF

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

作業(yè)提交時間運行時間

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

110：002：0010:0012:002120/120

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

310：250：2512:0012:252120/25

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

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

可見HRRF比FIFO要好。

15假設(shè)有如表所示四個作業(yè)進入系統(tǒng)，分別計算在FCFS、SJF和HRRF算法下的平均周轉(zhuǎn)時間

與帶權(quán)平均周轉(zhuǎn)時間。（時間以十進制表示）

作業(yè)提交時間（時）估計運行時間（小時）開始執(zhí)行時間（時）

18.002.008.()0

28.500.5010.30

39.000.1010.00

49.500.2010.10

答:

FCFSSJFHRRF

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

時間時間時間時間時間時間時間時間時間

18.0010.002.008.0010.002.008.0010.002.00

210.0010.502.0010.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=1.725T=1.55T=1.625

轉(zhuǎn)時間=

帶權(quán)平均W=6.875W=5.15W=5.675

周轉(zhuǎn)時間=

16Kleinrock提出一種動態(tài)優(yōu)先權(quán)算法：進程在就緒隊列等待時，其優(yōu)先權(quán)以速率a變化；當進

程在處理器上運行，時其優(yōu)先權(quán)以速率B變化。給參數(shù)。、B賦以不同值可得到不同算法。

（1）假設(shè)a>8>0是什么算法？（2）假設(shè)a<8<0是什么算法

答：

（1）是先進先出算法。因為在就緒隊列中的進程比在CPU上運行的進程的優(yōu)先數(shù)提

高得快，故進程切換時，先進入就緒隊列的進程優(yōu)先權(quán)就越高。

（2）是后進先出算法。因為在就緒隊列中的進程比在CPU上運行的進程的優(yōu)先權(quán)下

降得快，故后進入就緒隊列的進程此先進入的進程的優(yōu)先權(quán)高。

1717有一個四道作W的操作系統(tǒng),假設(shè)在一段時間內(nèi)先后到達6個作業(yè).它們的提交和估計運

行時間由下表給出：

作業(yè)提交時間估計運行時間（分鐘）

18：0060

28：2035

38：2520

48：3025

58：355

68：4010

系統(tǒng)采用SJF調(diào)度算法，作業(yè)被調(diào)度進入系統(tǒng)后中途不會退出，但作業(yè)運行時可被更短作

業(yè)搶占。（1）分別給出6個作業(yè)的執(zhí)行時間序列、即開始執(zhí)行時間、作業(yè)完成時間、作業(yè)周轉(zhuǎn)時

間。（2）計算平均作業(yè)周轉(zhuǎn)時間。

答:

執(zhí)行次月:提交時間執(zhí)行時間開始時間完成時間周轉(zhuǎn)時間

J18:00608:009:0060

J58:3559:009:0530

J68:40109:059:1535

J38:25209:159:3570

J48:30259:3510:0090

J28:203510:0010:35135

作業(yè)平均周轉(zhuǎn)時間T=(60+30十35+70十90十135)/6=70

注意，JI被調(diào)度運行后，直到它執(zhí)行結(jié)束，才會引出作業(yè)調(diào)度程序工作。所以，J2至J6

雖在J1執(zhí)行期間進入，但未被調(diào)度，均在等待。當J1撤離后，作業(yè)調(diào)度程序工作，按SJF算

法，顯然有執(zhí)行次序：J5、J6、J3、J4、和J2。

18有一個具有兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進程調(diào)度采用以

優(yōu)先數(shù)為根底的搶占式調(diào)度算法，在下表所示的作業(yè)序列，作業(yè)優(yōu)先數(shù)即為進程優(yōu)先數(shù)，優(yōu)

先數(shù)越小優(yōu)先級越高。

作業(yè)名到達時間估計運行時間優(yōu)先數(shù)

A10：0040分5

B10：2030分3

C10：3050分4

D10：5020分6

(1)列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間.

(2)計算平均周轉(zhuǎn)時間。

答：

每個作業(yè)運行將經(jīng)過兩個階段：作業(yè)調(diào)度(SJF算法)和進程調(diào)度(優(yōu)先數(shù)搶占式)。另外，批處理

最多容納2道作業(yè)，更多的作業(yè)將在后備隊列等待。

時間(分鐘)10:0010:2010:3010:5011:1012:4)012:2。

ABAcD

CPU

進程就緒隊列人DD

作業(yè)后備隊列c

(1)10:00,作業(yè)A到達并投入運行。

(2)10:2(),作業(yè)B到達且優(yōu)先權(quán)高于作業(yè)A,故作業(yè)B投入運行而作業(yè)A在就緒隊列等待。

(3)10:30,作業(yè)C到達，因內(nèi)存中已有兩道作業(yè)，故作業(yè)C進入作業(yè)后備隊列等待。

(4)10:50,作業(yè)B運行結(jié)束，作業(yè)D到達，按SJF短作業(yè)優(yōu)先算法，作業(yè)D被裝入內(nèi)存進入就

緒隊列。而由于作業(yè)A的優(yōu)先級高于作業(yè)D,故作業(yè)A投入運行。

(5)11:10,作業(yè)A運行結(jié)束,作業(yè)C被調(diào)入內(nèi)存,且作業(yè)C的優(yōu)先級高于作業(yè)D,故作業(yè)C投

入運行。

(6)12:00,作業(yè)C運行結(jié)束，作業(yè)D投入運行。

(7)12:20,作業(yè)D運行結(jié)束。

作業(yè)進入內(nèi)存時間運行結(jié)束時間

A10:0011:10

B10:2010:50

C11:1012:00

D10:5012:20

各作業(yè)周轉(zhuǎn)時間為：作業(yè)A7(),作業(yè)B30,作業(yè)C90,作業(yè)D9()。平均作業(yè)周轉(zhuǎn)時間

為70分鐘。

19某多道程序設(shè)計系統(tǒng)供用戶使用的主存為100K,磁帶機2臺，打印機1臺。采用可變分區(qū)內(nèi)

存管理，采用靜態(tài)方式分配外圍設(shè)備，忽略用戶作業(yè)I/O時間?，F(xiàn)有作業(yè)序列如下：

作業(yè)號進入輸入井時間運行時間主存需求量磁帶需求打印機需求

18:0025分鐘15K11

28:2010分鐘30K01

38:2020分鐘60K10

48:3020分鐘20K10

58:3515分鐘10K11

作業(yè)調(diào)度采用FCFS策略，優(yōu)先分配主存低地址區(qū)且不準移動已在主存的作業(yè)，在主存中的各作

業(yè)平分CPU時間?，F(xiàn)求：(1)作業(yè)被調(diào)度的先后次序?(2)全部作業(yè)運行結(jié)束的時間?(3)作業(yè)平均周

轉(zhuǎn)時間為多少?(4)最大作業(yè)周轉(zhuǎn)時間為多少？

答：(1)作業(yè)調(diào)度選擇的作業(yè)次序為：作業(yè)1、作業(yè)3、作業(yè)4、作業(yè)2和作業(yè)5。

(2)全部作業(yè)運行結(jié)束的時間9:30o

(3)周轉(zhuǎn)時間：作業(yè)1為30分鐘、作業(yè)2為55分鐘、作業(yè)3為40分鐘、作業(yè)4為40分鐘和作

業(yè)5為55分鐘。

(4)平均作業(yè)周轉(zhuǎn)時間=44分鐘。

(5))最大作業(yè)周轉(zhuǎn)時間為55分鐘。

20某多道程序設(shè)計系統(tǒng)采用可變分區(qū)內(nèi)存管理，供用戶使用的主存為200K,磁帶機5臺。采用

靜態(tài)方式分配外圍設(shè)備，且不能移動在主存中的作業(yè)，忽略用戶作業(yè)I/O時間?，F(xiàn)有作業(yè)序

列如下：

作業(yè)號進入輸入井時間運行時間主存需求量磁帶需求

A8:3040分鐘30K3

B8:5025分鐘120K1

C9:0035分鐘100K2

D9:0520分鐘20K3

E9:1010分鐘60K1

現(xiàn)求：(l)FIFO算法選中作業(yè)執(zhí)行的次序及作業(yè)平均周轉(zhuǎn)時間?(2)SJF算法選中作業(yè)執(zhí)行的次序及

作業(yè)平均周轉(zhuǎn)時間？

答：

(1)FIFO算法選中作業(yè)執(zhí)行的次序為：A、B、D、C和E。作業(yè)平均周轉(zhuǎn)時間為63分鐘。

⑵SJF算法選中作業(yè)執(zhí)行的次序為：A、B、D、E和C。作業(yè)平均周轉(zhuǎn)時間為58分鐘。

CH3應(yīng)用題參考答案

1有三個并發(fā)進程：R負責(zé)從輸入設(shè)備讀入信息塊，M負責(zé)對信息塊加工處理；P負責(zé)打印輸出信息塊。

今提供；

1)一個緩沖區(qū)，可放置K個信息塊；

2)二個緩沖區(qū)，每個可放置K個信息塊：

試用信號量和P、V操作寫出三個進程正確工作的流程。

答：

I)varB:array[0,k-l]ofitem;

sread:semaphore:=k;

smanagc:semaphore:=0;

swriie:semaphore:=0;

rptr:integer:=0;

mptr:integer:=0;

wptr:integer:=0;

x:item

cobegin

processreader;processmanager;processwriter;

begin