第一章

作者：佚名來源：網(wǎng)絡

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

200KBo如果用戶進程等待I/O得時間為80%,若增加1MB內(nèi)存，則CPU得

利用率提高多少？

答：設每個進程等待I/O得百分比為P,則n個進程同時等待刀0得概率就是

Pn,當n個進程同時等待I/O期間CPU就是空閑得，故CPU得利用率為1-Pn。

由題意可知，除去操作系統(tǒng)，內(nèi)存還能容納4個用戶進程，由于每個用戶進程

等待I/O得時間為80%,故：

CPU利用率=1-(80%)4=0、59

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

(1-80%)9=0、87

故增加IMB內(nèi)存使CPU得利用率提高了47%:

87%/59%=147%

147%-100%=47%

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

序A先開始做，程序B后開始運行。程序A得運行軌跡為：計算50ms、打印

100ms、再計算50nls、打印100ms,結(jié)束。程序B得運行軌跡為：計算50ms、

輸入80ms、再計算100ms,結(jié)束。試說明(1)兩道程序運行時，CPU有無空

閑等待？若有，在哪段時間內(nèi)等待？為什么會等待？(2)程序A、B有無等

待CPU得情況？若有，指出發(fā)生等待得時刻。

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

1A計篁|R計七R計七|

處理器?i!

???

i口蛤入?：

輸入機

打印機iA打前[jA打印]

程序A1計跳]打印1計*1打印]

程序B1計蝮1輸入陽1計篁1

時間(ms)111III11

050100150180200250300

(1)兩道程序運行期間，CPU存在空閑等待，時間為100至150ms之間(見圖

中有色部分)

(2)程序A無等待現(xiàn)象，但程序B有等待。程序B有等待時間段為180rns至

200ms間(見圖中有色部分)

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

給出。

ABC

Cn=30msC2|=60msCji^ZOms

iII11I

Ii2=40ms3M301nsb產(chǎn)40ms

?

ii1I1

C13=10msGJ=10msCjj^ZOms

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

時間？比單道運行節(jié)省了多少時間？若處理器調(diào)度程序每次進行程序轉(zhuǎn)換化時

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

答：

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

9

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

2）調(diào)度執(zhí)行時間1ms,多道運行方式（搶占式）：

I/O

CPU

OS

4在單CPU與兩臺1/0(Il,12)設備得多道程序設計環(huán)境下，同時投入三個

作業(yè)運行。它們得執(zhí)行軌跡如下：

Jobl:12(30ms)>CPU(10ms)、Il(30ms)>CPU(10ms)>12(20ms)

Job2:Il(20ms)、CPU(20ms)、12(40ms)

J0b3:CPU(30ms)、Il(20ms)、CPU(10ms)、H(10ms)

如果CPU、n與12都能并行工作，優(yōu)先級從高到低為Jobl、Job2與Job3,

優(yōu)先級高得作業(yè)可以搶占優(yōu)先級低得作業(yè)得CPU,但不搶占H與12。試求：

(1)每個作業(yè)從投入到完成分別所需得時間。(2)從投入到完成CPU得利

用率。(3)12設備利用率。

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

CPUJob31Job2JJoblIJob2|Job3|1Jobl11Job3|

11UJob2J|JoblIJob311Job3|

12|_Jobl________11Job21JoblI

Jobl121CPUin1CPUF12[

Job2II1CPUiICPUI121

Job3ICPUL1CPU—1IIiCPUini

時間111111111]11

(ms)

0102030405060708090100110

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

從投入到運行完成需110ms、

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

利用率為(110-30)/10=72、7%□

設備H空閑時間段為：20ms至40ms,90ms至100ms,故II得利用率為

(110-30)/110=72、7%。

設備12空閑時間段為：30ms至50ms,故12得利用率為(110-20)/110=81,

8%。

5在單CPU與兩臺1/0(II,12)設備得多道程序設計環(huán)境下，同時投入三個

作業(yè)運行。它們得執(zhí)行軌跡如下：

Jobl:12(30ms)、CPU(lOrns)、Il(30ms).CPU(10ms)

Job2:Il(20ms)、CPU(20ms)、12(40ms)

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

如果CPU、Il與12都能并行工作,優(yōu)先級從高到低為Jobl、Job2與Job3,

優(yōu)先級高得作業(yè)可以搶占優(yōu)先級低得作業(yè)得CPUo

試求：(1)每個作業(yè)從投入到完成分別所需得時間.

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

(3)I/O設備利用率。

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

CPU:Job3IJob2|Jobl|Job2|Job3|IJobl|

11Job2|1Jobl1Job31

12iJobl11Job2______________|

Jobl[121CPU1I】1CPU1

Job21IIICPU1,CPU1121

Job31CPU1，-CPUIl1

時間1111111111

(ms)

0102030405060708090

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

從投入到運行完成需90nlso

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

(90-20)/90=77、78%。

(3)設備H空閑時間段為：20ms至40ms,故H得利用率為(90-20)/90

=77、78%。設備12空閑時間段為：30ms至50ms，故12得利用率為(90-20)

/90=77、78%。

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

得計算軌跡為：

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

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

c：計算(10)、I/O(30)、計算(20)

如果三道程序都使用相同設備進行I/O(即程序用串行方式使用設備，調(diào)度開銷

忽略不計)。試分別畫出單道與多道運行得時間關(guān)系圖。兩種情況下，CPU得平

均利用率各為多少？

答：分別畫出單道與多道運行得時間圖

(1)單道運行時間關(guān)系圖

I/OA|BIc|

111

1t(

111

111

?Bicjic?

CPUIA「?Bj

i1"1

1iI?

iit

191

時間11iii1:11

(ms)

02040506080100120140160180190

單道總運行時間為190msoCPU利用率為（190-80）/190=57、9%

單道運行時間關(guān)系圖

I/OA|BC

1J

1

?

1

CPU1AB|A|BC

1L￡Jr-?

i

?

?

i

i

時間[1!111I

(ms)

02040506080!00120140

多道總運行時間為140ms。CPU利用率為（140-30）/140=78、6%

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

運行時得CPU與I/O占用時間為：

程序A：60203010402020(ms)

I/O2CPUI/OlCPUI/OlCPUI/Ol

程序B：3040703030(ms)

I/O】CPUI/O2CPUI/O2

程序C：40603070(ms)

CPUI/OlCPU1/02

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

級低得程序，優(yōu)先級與I/O設備無關(guān)。試畫出多道運行得時間關(guān)系圖，并問最

早與最遲結(jié)束得程序就是哪個？每道程序執(zhí)行到結(jié)束分別用了多少時間？計算

三個程序全部運算結(jié)束時得CPU利用率？

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

CPU[ClB1A[B]CI口IB[C]A|CI

101IB||A|C1A]IAI

102I…Ai.il1BIIB,|ICI

A|102ppu|101|P101|cpu|101|

B|101|cpu「5之寸叫102|cpu|102|

C嚴ufn陷101向102?

時間I1I..L..I..I.I.JL.I..I.I

(ms)

0306090120150180210240270300330

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

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

（3）CPU利用率為（310-120）/310=61、3%

有兩個程序，A程序按順序使用：（CPU）10秒、（設備甲）5秒、（CPU）5秒、

（設備乙）10秒、（CPU）10秒。B程序按順序使用：（設備甲）10秒、（CPU）

10秒、（設備乙）5秒、（CPU）5秒、（設備乙）10秒。在順序環(huán)境下先執(zhí)行

A,再執(zhí)行B,求出總得CPU利用率為多少？

答：程序A執(zhí)行了40秒，其中CPU用了25秒。程序B執(zhí)行了40秒，其中

CPU用了15秒。兩個程序共用了80秒，CPU化40秒。故CPU利用率為40/80

=50%。

9、在某計算機系統(tǒng)中，時鐘中斷處理程序每次執(zhí)行得時間為2ms（包括進程切

換開銷）。若時鐘中斷頻率為60Hz,試問CPU用于時鐘中斷處理得時間比率為

多少？

答：因時鐘中斷頻率為60Hz,所以，時鐘周期為："60s=50/3ms。在每個時鐘周期中，

CPU花2ms執(zhí)行中斷任務。所以，CPU用于時鐘中斷處理得時間比率為：2（50/3）=電0=

12%。

第二章

作者：佚名來源：網(wǎng)絡

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

(1)讀時鐘日期；(2)訪管指令；(3)設時鐘日期；(4)加載PSW;(5)置特殊

寄存器：(6)改變存儲器映象圖；(7)啟動I/O指令。

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

2假設有一種低級調(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)系有互斥與同步兩種。其中(1)、(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若后備作業(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)時間為：

Tl==a+(a+b)+(a+b+c)=3a+2b+c①

若不按短作業(yè)優(yōu)先算法調(diào)度，不失一般性，設調(diào)度次序為：J2.Jl.J3o則

三個作業(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、若有一組作業(yè)J1,…，Jn,其執(zhí)行時間依次為S1,…，Sn。如果這些

作業(yè)同時到試找出一種作業(yè)調(diào)度算法到達系統(tǒng)，并在一臺單CPU處理器上按單

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

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

'，…，Jn,創(chuàng)門得運行時間滿足：S1<S2W……WS(n-1)WSn'。那

么有：

T=[S|+(S(+Sj)+(S!+&+S：)+…+(S|+Sz+Sj+???+So)]/n

=[nXSi+(n-1)XSj'+(n-3)XS；]+…+SB]]/n

*+S；+Sj+-+SB)-[0XS/+1XS2'+2XS；+-+(n-1)Sj/n

由于任何調(diào)度方式下，sr+S2'+S3'+…+Sn'為一個確定得數(shù)，而當SI'

WS2'W…<S(n-1)，WSn，時才有：O*S1+1*S2+2*S3+…(n-1)Sn

得值最大，也就就是說，此時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)時間

1100010101

211010111111

32111113136.5

411313141414

55141419193.8

作業(yè)平均冏轉(zhuǎn)時間1=(10+11+13+14+19)/5=13.4

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

(2)采用雙算法調(diào)度作業(yè)，若令時間片長=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

21022

320773.5

410444

55014142.8

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

作業(yè)平均帶權(quán)周轉(zhuǎn)時間WT1.9+2+3.5+4+25)/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-Cl+2+4+9+l9)/5=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è)，運作情況：

8對某系統(tǒng)進行監(jiān)測后表明平均每個進程在"0阻塞之前得運行時間為T。一

次進程'切換得系統(tǒng)開銷時間為So若采用時間片長度為Q得時間片輪轉(zhuǎn)法，

對下列各種情況算出CPU利用率。

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

答：I)0=8CPU利用率=17(T+S)

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

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

4)Q-SCPU利用率=50%

5)Q-0CPU利用率一0

9有5個待運行得作業(yè)，各自預計運行時間分別就是：9、6、3、5與x，

采用哪種運行次序使得平均響應時間最短？

答：按照最短作業(yè)優(yōu)先得算法可以使平均響應時間最短。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)先級分跳狠掀完為、、飛、飛、氏積5、這里5為最

高級。對于1）時間片輪轉(zhuǎn)算法、2）優(yōu)先數(shù)法、3）短作業(yè)優(yōu)先算法、4）先來

先服務調(diào)度算法（按到達次序C、D、B、E、A）,在忽略進程切換時間得前

提下，計算出平均作業(yè)周轉(zhuǎn)時間。（對1）每個作業(yè)獲得相同得2分鐘長得時間

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

答：（1）FCFS調(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

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

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

E100101

D810182.25

C618244

B424287

A2283015

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

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

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

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

A2021

B48123

C614203.33

D818263.25

E1020303

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

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

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

（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=(l+1.5+2+2.5+3y5=2

11、有5個批處理作業(yè)A到E均已到達計算中心，其運行時間分別10、6、

2、4與8分鐘；各自得優(yōu)先級分別被規(guī)定為3、5、2、1與4,這里5為

最高級。若不考慮系統(tǒng)切換開銷，計算出平均作業(yè)周轉(zhuǎn)時間。（l）FCFs（按A、

B、C、D、E）;（2）優(yōu)先級調(diào)度算法，（3）時間片輪轉(zhuǎn)法（每個作業(yè)獲得相

同得2分鐘長得時間片）。

答：

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

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

A100101

B610162.66

C216189

D4182253

E822303.75

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

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

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

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

B6061

E86141.75

A1014242.4

C2242613

D426307.5

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

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

(3)時間片輪轉(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ōu)先級使得

系統(tǒng)效率較高？

答：處理器調(diào)度算法會考慮以下因素：作業(yè)響應時間要求；讓CPU盡量與外圍

設備并行工作；限制一個計算進程長時間霸占處理器。因而，(1)F0為主作

業(yè)優(yōu)先級高。(2)輸入輸出為主作業(yè)優(yōu)先級最高，輸入輸出均勻得作業(yè)其次，

而計算為主作業(yè)得優(yōu)先級最低。

13請您設計一種先進得計算機體系結(jié)構(gòu)，它使用硬件而不就是中斷來完成進程

切換，則CPU需要哪些信息？請描述用硬件完成進程切換得工作過程。

答：該計算機有一個專用硬件寄存器，它始終存放指向當前運行進程得PCB得

指針。當系統(tǒng)中發(fā)生了一個事件，如F0結(jié)束事件，CPU便可把運行進程得上下

文保存到專用硬件寄存器指針指向得PCB中保護起來，然后，CPU轉(zhuǎn)向中斷向

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

務例程，于就是，便可啟動中斷服務例程工作。

14設計一條機器指令與一種與信號量機制不同得算法，使得并發(fā)進程對共享變

量得使用不會出現(xiàn)與時間有關(guān)得錯誤。

解：

(1)設計機器指令。

設計一條如下得”測試、比較與交換”三地址指令，提供了一種硬件互斥解決方

案：

R1R3B2D2

TC&S

該指令得功能如下：

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

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

(3)如果(R1)=(C)則(R3)-C,并置條件碼為"00”,

如果(RI)W(c)則(C)一口，并置條件碼為"01”、

(2)編寫進程訪問共享變量得程序。

對每個訪問共享變量C得進程，編寫訪問共享變量得程序段為：

陸界區(qū)程序說明

共享變量c得值保護到RI中。

(C)fR1;

R1得值傳送到R3中，進程修改共享變量時，先對R3操

loop2:(RI)fR3;

作(不就是直接操作C)O

Add/decreaseR3;

R3加1/減1,進程歸還/申請由共享變量C代表得

TC&S;

共享資源(假定每次一個)。

R(condition=01)

執(zhí)行”測試、比較與交換”指令。

loop2;

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

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

此解與互斥使用共享變量得思路絕然不同，并發(fā)運行得進程可不互斥地訪問它們

得共享變量。此方案認為造成共享變量C值錯誤得原因在于：一個進程（P1）

在改變C值得過程中，另一個進程伊2）插進來也改變了C得值，而本進程（P1）

卻不知道，造成了c值結(jié)果不正確。如果有辦法使本進程口1）能知道C值就

是否改變，改變得話在繼承改變了得C值得基礎(chǔ)上，再作自己得改變操作，則

就不會導致共享變量C值得錯誤。為此，本解決方案中，當一個進程1）準備改

變C值時，先把C得值保護在R1中，然后，通過R3來改變共享變量C得值。

當要把新得值（即R3內(nèi)得值）送C之前，先要判斷一下在本進程（P1）工作

期間就是否有別得進程口2）插進來也改變了C得值（并發(fā)進程Pl、P2得執(zhí)

行完全會造成這種情況），方法就是：將扭1）中被保護得C得原來值，與C得

當前值比較，若相等，說明C值未被改變過，則將本進程（P1）修改過得新值

送C（即（R3）-C）；若不相等，說明C值在工作期間被改變過，則應該

繼承C得新值（即（C）一R1）并且返回到loop2處重新對C值計數(shù)，以此

保證C值得最終結(jié)果得正確性。這里提及“進程工作期間”指得就是一個進程從

開始至結(jié)束對共享變量C值得操作得這段時間，也就就是執(zhí)行進程，'I晦界

區(qū)”這段程序得時間。止匕外，在進程進入臨界區(qū)之前，應等待直到C為非。（即

有資源可用）為止。

（4）舉例。

假定系統(tǒng)中有靜態(tài)分配資源磁帶機共3臺，被N個進程共享，由共享變量C來

代表可用磁帶機臺數(shù)，其初值為3?，F(xiàn)有并發(fā)進程P1與P2均申請使用磁帶機,

執(zhí)行臨界區(qū)程序。

進程P1執(zhí)行臨界區(qū)程序

（C）-*R1；因（C）=3,故（R1）=3o

loop2:（R1）一R3因（R1）=3,故（R3）當前也=3。

decreaseR3：申請使用磁帶機，做減1操作，故（R3）=2、

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

如果Rl=（C）則（R3）-C,即（C）=2,并置條件碼為“00”,跳出臨界區(qū)

程序，去使用磁帶機。

如果（RI）W（C）,例如，（C）=2,說明進程P2搶先申請了磁帶機，所以,

C與保護在R1中得值不一樣了（C得值必

小于R1得值），應以C得當前值為準，執(zhí)行（C）RI（R1此時變?yōu)?）,

并置條件碼為“01”,轉(zhuǎn)向foopZ。于就是伍1）=2,跟著（R3卜2。接

著卿）減1后應=1了。再執(zhí)行TC&S時，由于伍1卜（C）=2,會使C變

為1。

r（conditio二01）loop2;

巧單道批處理系統(tǒng)中，下列三個作業(yè)采用先來先服務調(diào)度算法與最高響應比優(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)時間W=

答:

FIFO

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

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

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

110：002：0010:0012:002120/120

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

310：250：2513:0013:253180/25

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

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

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

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

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

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

18.002.00

28.500.50

39.000.10

49.500.20

答，

FCFSSJFHRRF

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

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

18.0010.002.008.0010.002.008.0010.002.00

210.0010.502.00103010.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-135T-1.625

轉(zhuǎn)時間?

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

周轉(zhuǎn)時間，

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

速率a變化；當進程在處理器上運行，時其優(yōu)先權(quán)以速率p變化。給參數(shù)a,b賦

以不同值可得到不同算法。(1)若a>b>c就是什么算法？(2)若a<b<c

就是什么算法

答：(1)就是先進先出算法。因為在就緒隊列中得進程比在CPU上運行得進

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

(2)就是后進先出算法。因為在就緒隊列中得進程比在CPU上運行得進程得

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

18有一個四道作業(yè)得操作系統(tǒng)，若在一段時間內(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)時間。

答

作業(yè)提交需運行開始運行被搶占還完成周轉(zhuǎn)

號時間時間時間需運行時間時間時間

J18:00608:00401035155

J28:20358:20309:5595

J38:25208:258:4520

J48:30259:00259:2555

J58:3558:458:5015

J68:40108:509:0020

說明：

(1)J2到達時搶占JI;J3到達時搶占J2。

(2)但只到達時，因不滿足SJF,故J4不能被運行，J3繼續(xù)執(zhí)行5分鐘。

(3)由于就是4道得作業(yè)系統(tǒng)，故后面作業(yè)不能進入主存而在后備隊列等待,

直到有作業(yè)結(jié)束。

(4)根據(jù)進程調(diào)度可搶占原則，J3第一個做完。而這時J5、J6均己進入后

備隊列，而J5可進入主存。

(5)因J5最短，故它第二個完成。這時J6方可進入主存。因J6最短，故

它第三個完成。

(6)然后就是：J4、J2與J1

(7)T=(155+95+20+55+15+20)/6=60

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

進程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)得搶占式調(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: