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

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

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

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

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

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

能容納4個(gè)用戶進(jìn)程，由于每個(gè)用戶進(jìn)程等待I/O的時(shí)間為80%,故：

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

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

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

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

87%4-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è)有，在哪段時(shí)間內(nèi)等待？為什么會(huì)等待？(2)程序A、B有

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

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

IA計(jì)算B計(jì)算B計(jì)算

處理器

輸入機(jī)B輸入|

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

程序A1計(jì)笠打印|計(jì)苴打印|

程序B計(jì)第輸入「計(jì)部|

時(shí)間(ms)|1111

050100150180200250300

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

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

局部)。

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

ABC

Cn=30msC2i=60msC3i=20ms

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

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

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

運(yùn)行節(jié)省了多少時(shí)間？假設(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/O112122132

CPUC11C21Cl：1C21C31C23C33_

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

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

時(shí)間0379101213141618單位10ms

I/O112122132

CPUCllC21C13C3I(：23C33

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

4在單CPU和兩臺(tái)1/0(11,12)設(shè)備的多道程序設(shè)計(jì)環(huán)境下，同時(shí)投入三個(gè)作業(yè)運(yùn)行。它們的執(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)先級(jí)從高到低為Jobl、Job2和Job3,優(yōu)先級(jí)高的作業(yè)可以搶

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

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

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

CPULJob3IJob2JoblIJob2IJob3|IJobl|IJob3|

11|_Job2JJobl|Job3||Job3

12|_Jobl1Job2IJobl

Jobl|_12CPU1IIICPUI-~l12

Job2II1CPU匚1CPU112_J

—

Job3|_CPUl-iCPUr1IIICPU|Il

時(shí)間|_11]_1ii1111

(ms)

0102030405060708090100110

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

1lOmso

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

(110-30)/110=72.7%o

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

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

5在單CPU和兩臺(tái)1/0(11,⑵設(shè)備的多道程序設(shè)計(jì)環(huán)境下，同時(shí)投入三個(gè)作業(yè)運(yùn)行。它們的執(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)先級(jí)從高到低為Jobl、Job2和Job3,優(yōu)先級(jí)高的作業(yè)可以搶

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

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

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

I/O

CPU

時(shí)間

(ms)

02040506080100120140

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

7假設(shè)內(nèi)存中有3道程序A、B、C,優(yōu)先級(jí)從高到低為A、B和C,它們單獨(dú)運(yùn)行時(shí)的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

如果三道程序同時(shí)并發(fā)執(zhí)行，調(diào)度開銷忽略不計(jì)，但優(yōu)先級(jí)高的程序可中斷優(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í)間圖：

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

時(shí)間

(ms)

0306090120150180210240270300330

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

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

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

8有兩個(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化了4。秒。故CPU利用率為40/80=50%o

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

時(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%o

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

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

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

變存儲(chǔ)器映象圖；（7）啟動(dòng)I/O指令。

答：⑶，（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)系有互斥和同步兩種。其中（I）、（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假設(shè)后備作業(yè)隊(duì)列中等待運(yùn)行的同時(shí)有三個(gè)作業(yè)JI、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í)間為：

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

假設(shè)不按短作業(yè)優(yōu)先算法調(diào)度：不失一般性，設(shè)調(diào)度次序?yàn)椋篔2.JL.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假設(shè)有一組作業(yè)J1,…，Jn,其執(zhí)行時(shí)間依次為S1,…，Sno如果這些作業(yè)同時(shí)到達(dá)系統(tǒng)，

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

間最短。

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

的運(yùn)行時(shí)間滿足：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；為一個(gè)確定的數(shù)，而當(dāng)Si'WS2'<…WS.DWS；時(shí)

才有：OXS/+1XS2'+2XS3'+…+(n-l)S；的值最大,也就是說，此時(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)分別用先來先效勞調(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

211

323

414

552

答:

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

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

11()001()1()1

211010111111

3211II13136.5

411313141414

55141419193.8

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

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

(2)采用RR算法調(diào)度作業(yè)，假設(shè)令時(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í)行時(shí)間提交時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間

110019191.9

210222

320773.5

410444

55014142.8

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

作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間W=(1.9+2+3.5+4+2.8)/5=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=(1+2+4+9+19)75=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)作情況:

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

211011

525161.2

13106161.6

33216189

441181919

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

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

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

開銷時(shí)間為So假設(shè)采用時(shí)問片長度為Q的時(shí)向片輪轉(zhuǎn)法，對(duì)以下各種情況算出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個(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取值不定，按照以下情況討論：

1）xW3次序?yàn)椋簒,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)椋?,5,6,x,9

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

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

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

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

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

的時(shí)間片；對(duì)2）到4）采用單道運(yùn)行，直到結(jié)束。）

答：

（DFCFS調(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+4.5+2.8+15)/5=5.01

⑵優(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=(l0+18+24+28+30)/5=22

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

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

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

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

A2021

B48123

C614203.33

D818263.25

E1020303

（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=(1+1.5+2+2.5+3)75=2

II有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í)。假設(shè)不考慮系統(tǒng)切換開銷，計(jì)算

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

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

答：

（DFCFS調(diào)度算法

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

A10010I

B610162.66

C216189

D418225.5

E822303.75

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

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

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

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

B601

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=(l+1.75+2.4+13-7.5)/5=5.13

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

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

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

A1020303

B616223.66

C2463

D412164

E820283.5

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

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

12(1)假定一個(gè)處理器正在執(zhí)行兩道作業(yè)，一道以計(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)程長時(shí)間霸占處理器。因而，(1)1/0為主作業(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è)事件，如I/O結(jié)束事件，CPU便可把運(yùn)行進(jìn)程的上下文保存到專用硬件存放器指針指向的

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

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

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

哪一種算法性能較好？請(qǐng)完成下表：

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

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

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

110：002：00

210：101：00

310：250：25

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

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

答:

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:50145/60

310：250：2513:0013:253180/25

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

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

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要好。

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

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

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

18.002.008.()0

28.500.5010.30

39.000.1010.00

49.500.2010.10

答:

FCFSSJFHRRF

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

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

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)時(shí)間=

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

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

16Kleinrock提出一種動(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)以速率B變化。給參數(shù)。、B賦以不同值可得到不同算法。

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

答：

（1）是先進(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)高。

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

行時(shí)間由下表給出：

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

18：0060

28：2035

38：2520

48：3025

58：355

68：4010

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

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

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

答:

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

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)時(shí)間T=(60+30十35+70十90十135)/6=70

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

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

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

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

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

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

作業(yè)名到達(dá)時(shí)間估計(jì)運(yùn)行時(shí)間優(yōu)先數(shù)

A10：0040分5

B10：2030分3

C10：3050分4

D10：5020分6

(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ì)列等待。

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

ABAcD

CPU

進(jìn)程就緒隊(duì)列人DD

作業(yè)后備隊(duì)列c

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

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

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

(4)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)先級(jí)高于作業(yè)D,故作業(yè)A投入運(yùn)行。

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

入運(yùn)行。

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

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

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

A10:0011:10

B10:2010:50

C11:1012:00

D10:5012:20

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

為70分鐘。

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

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

作業(yè)號(hào)進(jìn)入輸入井時(shí)間運(yùn)行時(shí)間主存需求量磁帶需求打印機(jī)需求

18:0025分鐘15K11

28:2010分鐘30K01

38:2020分鐘60K10

48:3020分鐘20K10

58:3515分鐘10K11

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

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

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

答：(1)作業(yè)調(diào)度選擇的作業(yè)次序?yàn)椋鹤鳂I(yè)1、作業(yè)3、作業(yè)4、作業(yè)2和作業(yè)5。

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

(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分鐘。

20某多道程序設(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è)序

列如下：

作業(yè)號(hào)進(jìn)入輸入井時(shí)間運(yùn)行時(shí)間主存需求量磁帶需求

A8:3040分鐘30K3

B8:5025分鐘120K1

C9:0035分鐘100K2

D9:0520分鐘20K3

E9:1010分鐘60K1

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

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

答：

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

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

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

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

今提供；

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

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

試用信號(hào)量和P、V操作寫出三個(gè)進(jìn)程正確工作的流程。

答：

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