浙江大學遠程教育學院

《操作系統(tǒng)原理》課程作業(yè)

姓名：學號：

年級：學習中心：

一、單項選擇題

7進程P0和P1口勺共享變量定義及其初值為

booleanflag[2]；

intturn=()；

flag[O]=FALSE；llag[1]=FALSE；

若進程PO和Pl訪問臨界資源H勺類C代碼實現(xiàn)如下：

voidPOO//PO進程

{while(TURE){

flag[O]=TRUE;tum=1;

while(flag[1]&&turn==1);

臨界區(qū)；

flag[0]=FALSE;

voidPI()〃P1進程

(while(TURE){

flag[1]=TRUE;lum-0;

while(flag[01&&turn==0);

臨界區(qū)；

flag[1]=FALSE;

)

)

則并發(fā)執(zhí)行進程P0和PI時產(chǎn)生口勺狀況是：

A.不能保證進程互斥進入臨界區(qū)、會出現(xiàn)“饑餓”現(xiàn)象

B.不能保證進程互斥進入臨界區(qū)、不會出現(xiàn)“饑餓”現(xiàn)象

C.能保證進程互斥進入臨界區(qū)、會出現(xiàn)“饑餓”現(xiàn)象

D.能保證進程互斥進入臨界區(qū)、不會出現(xiàn)“饑餓”現(xiàn)象

【答案】D

2.有兩個進程P1和P2描述如下：

shareddata：

intcounter=6;

Pl:

Computing;

counter=countcr+1;

P2:

Printing;

counter=counter-2;

兩個進程并發(fā)執(zhí)行，運行完畢后，counter的值不也許為。

A.4B.5C.6D.7

【答案】C

3.某計算機采用二級頁表的分頁存儲管理方式，按字節(jié)編址，頁大小為字節(jié)，頁表項大

小為2字節(jié)，邏輯地址構(gòu)造為：

頁目錄號頁號頁內(nèi)偏移量

邏輯地址空間大小為216頁，則表達整個邏輯地址空間的頁目錄表中包括表項的個數(shù)至少是

A.64B.128C.256D.512

【答案】B

4.在動態(tài)分區(qū)系統(tǒng)中，有如下空閑塊：

空閑塊塊大小(KB)塊的基址

18060

275150

355250

490350

此時,某進程P祈求50KB內(nèi)存，系統(tǒng)從第1個空閑塊開始查找，成果把第4個空閑塊分

派給了P進程，請問是用哪一種分辨別配算法實現(xiàn)這一方案？

A.初次適應B.最佳適應C.最差適應D.下次適應

【答案】C

5.在一頁式存儲管理系統(tǒng)中，頁表內(nèi)容如下所示。

頁號幀號

02

11

28

若頁大小為1K,邏輯地h：的頁號為2,頁內(nèi)地址為451,轉(zhuǎn)換成H勺物理地址為

(3)8643B.8192C.2048D.2499

【答案】A

6.采用段式存儲管理口勺系統(tǒng)中，若地址用32位表達，其中20位表達段號，則容許每段日勺最

大長度是

A.224B.212C.210D.232

【答案】B

7.在一段式存儲管理系統(tǒng)中，某段表的內(nèi)容如下:

段號段首址段長

0100K35K

1560K20K

2260KI5K

3670K32K

若邏輯地址為(2,158),則它對應的I物理地址為o

A.100K+158B.260K+158C.560K+158D.670K+158

【答案】B

8.一種分段存儲管理系統(tǒng)中，地址長度為32位，其中段長占8位，則最大段長是

A.28字節(jié)B.2S字節(jié)C.2的字節(jié)D.2融字節(jié)

【答案】C

9.有一祈求分頁式存儲管理系統(tǒng)，頁面大小為每頁100字節(jié)，有一種50x50的整型數(shù)組按行

為主序持續(xù)寄存，每個整數(shù)占兩個字節(jié)，將數(shù)組初始化為。的程序描述如下：

intAl50][50J;

for(inti=0;i<50;i++)

for(intj=0;j<50;j++)

Afijl=O;

若在程執(zhí)行時內(nèi)存只有一種存儲塊用來寄存數(shù)組信息，試問該程序執(zhí)行時產(chǎn)生次

缺頁中斷。

A.IB.50C.100D.2500

【答案】B

10.一臺計算機有4個頁框，裝入時間、上次引用時間、和每個頁口勺訪問位R和修改位M,

如下所示:

頁裝入時間上次引用時間RM

012627900

1230260i0

212027211

316028011

采用FIFO算法將淘汰_____一頁；

A.0B.1C.2D.3

【答案】C

11.一臺計算機有4個頁框，裝入時間、上次引用時間、和每個頁的訪問位R和修改位M,

如下所示：

頁裝入時,可上次引用時間RM

012627900

123026010

212027211

316028011

采用NRU算法將淘汰_____一頁；

A.0B.1C.2D.3

【答案】A

12.一臺計算機有4個頁框，裝入時間、上次引用時間、和每個頁的訪問位R和修改位M,

如下所示:

頁裝入時間上次引用時間RM

012627900

123026010

212027211

316028011

采用LRU算法將淘汰______一頁;

A.0B.1C.2D.3

【答案】B

13??臺計算機有4個頁框，裝入時間、上次引用時間、和每個頁的訪問位R和修改位M,

如下所示：

頁裝入時間上次引用時間RM

012627900

123026010

212027211

316028011

采用第二次機會算法將淘汰頁；

A.OB.1C.2D.3

【答案】A

二、綜合題

1.4在所列的兩種設置中，哪些功能需要操作系統(tǒng)提供支持？(a)手持設備(b)實時系統(tǒng)，

a.批處理程序

b.虛擬存儲器

c.分時

1.4對于實時系統(tǒng)來說，操作系統(tǒng)需要以一種公平日勺方式支持虛擬存儲器和

分時系統(tǒng)。對于手持系統(tǒng)，操作系統(tǒng)需要提供虛擬存儲器，不過不需要提供分時

系統(tǒng)C批處理程序在兩種環(huán)境中都是非必需的Ic

1.17列出下列操作系統(tǒng)W、J基本特點：

a.批處理b.交互式c.分時d.實時e.網(wǎng)絡f.并行式g.分布式h.集群式i.手持式

ba批處理：具有相似需求的作業(yè)被成批日勺集合起來，并把它們作為一種整體通

過一種操作員或自動作業(yè)程序裝置運行通過計算機。通過緩沖區(qū)，線下操作，后

臺和多道程序，運用嘗試保持CPU和I/O一直繁忙，從而使得性能被提高，批

處理系統(tǒng)對于運行那些需要較少互動的大型作業(yè)十分合用。它們可以被更遲地提

交或獲得。

c.b.交互式：這種系統(tǒng)由許多短期交易構(gòu)成，并且下一種交易的成果是無法預知

日勺。從顧客提交到等待成果日勺響應時間應當是比較短日勺，一般為1秒左右。

de分時：這種系統(tǒng)使用CPU調(diào)度和多道程序來經(jīng)濟的提供一種系統(tǒng)的人機通信

功能。CPU從一種顧客迅速切換到另一種顧客。以每個程序從終端機中讀取它

日勺下一種控制卡，并且把輸出的信息對的迅速的輸出到顯示屏上來替代用

soopledcardimages定義日勺作業(yè)。

e.d.實時：常常用于專門的用途。這個系統(tǒng)從感應器上讀取數(shù)據(jù)，并且必須在嚴

格的時間內(nèi)做出響應以保證對的H勺性能。

f.e.網(wǎng)絡：提供應操作系統(tǒng)一種特性，使得其進入網(wǎng)絡，例如;文獻共享。

g.f,并行式：每一種處理器都運行同一種操作系統(tǒng)日勺拷貝。這些拷貝通過系統(tǒng)總

線進行通信。

hg分布式：這種系統(tǒng)在幾種物理處理器中分布式計算，處理器不共享內(nèi)存或時

鐘。每個處理器均有它各自的當?shù)卮鎯ζ?。它們通過多種通信線路在進行通信，

例如：一條高速日勺總線或一種當?shù)貧WI網(wǎng)絡。

i.h.集群式：集群系統(tǒng)是由多種計算機耦合成單一系統(tǒng)并分布?于整個集群來完畢

計算任務。

j.i.手持式：一種可以完畢像記事本，email和網(wǎng)頁瀏覽等簡樸任務日勺小型計算機

系統(tǒng)。手持系統(tǒng)與老式日勺臺式機的區(qū)別是更小日勺內(nèi)存和屏幕以及更慢的處理能

力。

2.3討論向操作系統(tǒng)傳遞參數(shù)H勺三個重要的措施。

1.通過寄存器來傳遞參數(shù)

2.寄存器傳遞參數(shù)塊的首地址

3.參數(shù)通過程序寄存或壓進堆棧中，并通過操作系統(tǒng)彈出堆棧。

2.12采用微內(nèi)核措施來設計系統(tǒng)歐）重要長處是什么？在微內(nèi)核中怎樣使客戶程序和系統(tǒng)服

務互相作用？微內(nèi)核措施日勺缺陷是什么？

a）增長一種新的服務不需要修改內(nèi)核

b）在顧客模式中比在內(nèi)核模式中更安全、更易操作

c）一種簡樸日勺內(nèi)核設計和功能一般導致一種更可靠的操作系統(tǒng)

顧客程序和系統(tǒng)服務通過使用進程件的通信機制在微內(nèi)核中互相作用，例如

發(fā)送消息。這些消息由操作系統(tǒng)運送。微內(nèi)核最重要的缺陷是與進程間通信

的過度聯(lián)絡和為了保證顧客程序和系統(tǒng)服務互相作用而頻繁使用操作系統(tǒng)

的消息傳遞功能。

3.2問:描述一下內(nèi)核在兩個進程間進行上下文功換啊動作.

總的來說，操作系統(tǒng)必須保留正在運行的進程的狀態(tài)，恢復進程的狀態(tài)。保留

進程口勺狀態(tài)重要包括CPU寄存器的值以及內(nèi)存分派，上下文切換還必須執(zhí)行

某些確切體系構(gòu)造的操作，包括刷新數(shù)據(jù)和指令緩存。

（書中答案）進程關聯(lián)是由進程的PCB來表達的，它包括CPU寄存器時值和內(nèi)存

管理信息等。當發(fā)生上下文切換時，內(nèi)核會將舊進程日勺關聯(lián)狀態(tài)保留在其PCB

中，然后裝入經(jīng)調(diào)度要執(zhí)行的新進程的已保留的關聯(lián)狀態(tài)。

3.4如下所示的I程序，闡明LINEA也許會輸出什么？

#include<stdio.h>

/include<unistd.h>

#include<sys/types.h>

intvalue=8;

intmain()

pid_tpid;

/*forkachildprocess*/

pid=fork();

if(pid==0){/*childprocess*/

value+=15;

}

else{/*parentprocess*/

/*parentwillwai:forthechildtocomplete*/

wait(NULL);

printf(uParent:value=%d\n",value);/*LINEA*/

exit(0);

)

)

Parent:value=8o

4.4在多線程程序中，如下哪些程序狀態(tài)構(gòu)成是被線程共享的?

a.寄存值

b.堆內(nèi)存

C.全局變量

d.棧內(nèi)存

一種線程程序Fl勺線程共享堆內(nèi)存和全局變量，但每個線程均有屬于自己的一組寄存值和棧內(nèi)

存。

47由圖411給出的程序使用了Pthread的應用程序編程接口(API),在程序的第c行和第

p行分別會輸出什么？

#include<pthread.h>

#include<stdio.h>

intvalue=O;

void*runner(void*param);/*thethread*/

intmain(intargc,char*argv[J)

{

intpid;

pthread_l(id;

pthread_attr_tattr;

pid=fork();

if(pid==0){/*childprocess*/

pthrcad_attr_init(&attr);

pthread_create(&tid,&attr,runner,NULL);

p(hreadjoin(tid.NULL);

printf(MCHILD:value=%d"，value);/*LINEC*/

)

elseif(pid>0){/*parentprocess*/

wait(NULL);

printffTARENT:value=%d'\value);/*LINEP*/

)

)

void*runner(void*param){

value=10;

pthread_exit(O);

1

答：c行會輸出10,p行會輸出0.

5.4考慮下列進程集，進程占用的CPU區(qū)間長度以亳秒來計算：

進程區(qū)間時間優(yōu)先級

Pi103

P21

假設在時刻0以進程P，P2,P3,P4,P5的次序抵達。

a.畫出4個Gantt圖分別演示用FCFS、SJF、非掄占優(yōu)先級（數(shù)字小代表優(yōu)先級高）

和RR（時間片=1）算法調(diào)度時進程日勺執(zhí)行過程。

b.a.甘特圖

c.FCFS

P1P2P3P4P5

12345678910111213141516171819

d.

e.SJF

P2P4P3P5Pl

12345678910111213141516171819

f.

g.Non-preeniptivePriority

P2P5PlP3P4

12345678910111213141516171819

h.

i.RR(quantum=l)

PlP2P3P4P5PlP3P5PlP5PlP5PlP5PlPlPlPIPl

1234567891()111213141516171819

j-

b.每個進程在每種調(diào)度算法下的周轉(zhuǎn)時間是多少？

TurnaroundTime

ProcessFCFSSJFNPPRR(quantum=1)

PI10191619

P211112

P3134187

P4142194

P5199614

Average13.47.2129.2

c.每個進程在每種調(diào)度算法卜的等待時間是多少？

ProcessFCFSSJFNPPRR(quantum=l)

PI0969

P210001

P3112165

P4131183

P514419

Average3.28.25.4

d.哪一種調(diào)度算法日勺平均等待時間對所有進程而言最小?

SJF

5.5下面哪些算法會引起饑餓

a.先來先服務

b.最短作'也優(yōu)先調(diào)度

c.輪轉(zhuǎn)法調(diào)度

d.優(yōu)先級調(diào)度

最短作業(yè)優(yōu)先調(diào)度和優(yōu)先級調(diào)度算法會引起饑餓

5.7考慮一種運行10個I/O約束（型）任務和一種CPU約束（型）任務的系統(tǒng)。假設.I/O

約束任務每進行1亳秒的CPU計算發(fā)射一次I/O操作,但每個I/O操作的完畢需要10毫秒。

同步，假設上下文切換要0.1亳秒，所有H勺進程都是長進程。對一種RR調(diào)度來說，如下狀

況時CPU的運用率是多少：

a.時間片是1亳秒

b.時間片是1（）亳秒

答：a.時間片是1亳秒：不管是哪個進程被調(diào)度，這個調(diào)度都會為每一次的上下文切換花費

一種0.1亳秒H勺上下文切換。CPU的J運用率是1/1.1*100=92%,

b.時間片是10亳秒：這I/O限制任務會在使用完1亳秒時間片后進行一次上下文切換。這

個時間片規(guī)定在所有的進程間都走一遍，因此，10*1.1+10.1(由于每個I/O限定任務執(zhí)行

為1亳秒，然后承擔上下文切換H勺任務，而CPU限制任務的執(zhí)行10亳秒在承擔一種上下文

切換之前)。因此，CPU的運用率是20、21.1*100=94%。

6.01在生產(chǎn)者和消費者問題中，信號量mutex,empty,full的作用是什么？假如對調(diào)生產(chǎn)者

進程中的兩個wait操作和兩個signal操作，則也許發(fā)生什么狀況？

信號量mutex曰勺作用是保證各生產(chǎn)者進程和消費者進程對緩沖池的I互斥訪問。信號量

empty和full均是資源信號量，它們分別對應于緩沖池中的空閑緩沖區(qū)和緩沖池中的J產(chǎn)品，

生產(chǎn)者需要通過wait(empty)來申請使用空閑緩沖區(qū)，而消及者需要通過wait(full)才能獲得

緩沖中的產(chǎn)品，可見，這兩個信號量起著同步生產(chǎn)者和消費者的作用，它們保證生產(chǎn)者不會

將產(chǎn)品寄存到滿緩沖區(qū)中，而消費者不會從空緩沖區(qū)中取產(chǎn)品。

在土產(chǎn)者一消費者問題中，假如將兩個wait操作，即wait(full)和wait(mutcx)互換位置，

或者wail(emply)和wait(mutex).互換位置，都也許引起死鎖?？紤]系統(tǒng)中緩沖區(qū)全滿時，若

畢生產(chǎn)者進程先執(zhí)行了wail(mutex)操作并獲得成功，當再執(zhí)行wail(empty)操作時，它將因

失敗而進入阻塞狀態(tài)，它期待消費者執(zhí)行signal(empty)來喚醒自己，在此之前，它不也許執(zhí)

行signal(mutex)操作,從而使企圖通過wait(mutex)進入自己的J臨界區(qū)U勺其他生產(chǎn)者和所有的J

消費者進程所有進入阻塞狀態(tài)，系統(tǒng)進入死鎖狀態(tài)。類似地，消費者進程若先執(zhí)行

wait(mutcx),后執(zhí)行wait(fuH)同樣也許導致死鎖。

signal(full)和signal(mutex)互換位置,或者signal(empty)和signal(mutex)互換位置，則不

會引起死鎖，其影響只是使某個臨界資源的釋放略為推遲某些。

6.02一組合作進程，執(zhí)行次序如下圖。請用wait、signal操作實現(xiàn)進程間II勺同步操作。

如圖示并發(fā)進程之間的前趨關系，為了使上述進程同

步，可設置8個信號量a、b、c、d、e、f、g、h,它們II勺

初值均為0,而對應的進程可描述為（其中“…”表達進

程本來的代碼）：

inain()

cobcgin{

人?U,l

Pl(){…；signal(a);signal(b);}

P2(){wait(a);…；signal(c);signal(d);}

P3(){wait(b);…；signal(e);signal(f);)

P4(){wait(c);wait(e);…；signal(g);}

P5(){wait(d);wait(f);…；signal(h);}

P6(){wait(g);wait(h);…；}

}coend

6.03在生產(chǎn)者和消費者問題中，多種生產(chǎn)者進程(ProducerProcess)和多種消費者進程

(ConsumerProcess)共享一種大小為8的緩沖區(qū)，池們的信號量和共享變量設置如下:

ininextc=0,nexlp=0,huf|8];

semaphorefull;empty;mutex;

生產(chǎn)者進程和消費者進程問題的算法描述如下：

ProducerProcess:ConsumerProcess:

intitemp;intitemc;

while(l){while(l){

1itemp=rand();//Generateanumber1wait(full);

2wait(empty);2wait(niutex);

3wait(mutcx);3itcmc=buf[ncxtc);

4buf[nextp]=itemp;4nextc=(nextc+1)%8;

5nextp=(nextp+1)%8;5signal(mutex);

6signal(mutex);6signal(empty);

7signal(full);7cout?itemc?endl;

})

(1)生產(chǎn)者進程和消費者進程的I臨界區(qū)是哪些？

生產(chǎn)者進程的J臨界區(qū)是第4行和第5行；消費者進程的J臨界區(qū)是第3行和第4行。

(2)信號量full、empty和mutex日勺初值是多少？

empty=8，full=0,mutex=I。

(3)假如對調(diào)生產(chǎn)者進程中的兩個P操作即第2行和第3吁，以及對調(diào)消費者進程中的兩個P

操作即第1行和第2行，如下所示。也許發(fā)生什么狀況？

ProducerProcessConsumerProcess

1itemp=rand();//Generateanumber1wait(mutex);

2wait(mutex);2wait(full);

3wait(empty);3itemc=buf[nextcj;

系統(tǒng)也許會產(chǎn)生死鎖。例如，生產(chǎn)者進程得到信號量mutex,不過沒有空緩沖區(qū)即empty

W0時，此時生產(chǎn)者進程阻塞；而消費者進程乂無法得到信號量mulex,此時消費者進程也

阻塞，系統(tǒng)產(chǎn)生了死鎖。

(4)上面的生產(chǎn)者和消費者同步算法有一種缺陷，在有空緩沖區(qū)時，當消費者進程正在臨

界區(qū)時，生產(chǎn)者進程必須等待，反之亦然。您怎樣可以處理這個問題，以提高生產(chǎn)者和消費

者進程之間并發(fā)？寫出新的生產(chǎn)者進程和消費者進程"勺同步算法。

增長一種信號量mutexl,初值為1,其算法如下：

ProducerProcessConsumerProcess

intitemp;intitemc;

while(l){while(l){

1itemp=rand();//Generateanumber1wait(full);

2wait(empty);2wait(mutex);

3wait(mutex1);3itcmc=buf[ncxtc];

4buflncxtpj=itcmp;4ncxtc=(ncxtc+1)%8;

5nextp=(nextp+1)%8;5signal(mutex);

6signal(mutexl);6signal(empty);

7signal(full);7coul?itemc?endl;

}

6.04有2個合作H勺進程Pl、P2。他們從一臺輸入設備讀入數(shù)據(jù),Pl進程讀入數(shù)據(jù)a,P2進

程讀入數(shù)據(jù)b。輸入設備是一臺獨享設備。兩個進程做如下計算：

Pl:x=a+b

P2:y=a*b

計算完畢后成果的x、y由進程Pl輸出。用信號量實現(xiàn)Pl、P2同步算法。

設置三個信號：si表達數(shù)據(jù)a與否讀入，s2表達數(shù)據(jù)b與否讀入，S3表達數(shù)據(jù)丫二@將計算

與否完畢。P1和P2兩個進程的同步算法如下：

semaphoresl=0,s2=0,s3=0;

main()

cobegin{

PI:P2:

({

input(a)；wait(sl)；

signal(s1)：input(b)；

wait(s2)；signal(s2)；

x=a+b；y=a*b；

wait(s3)：signal(s3)：

Print(x,y,z)：

))

Jcocnd

7.1假設有如卜圖所示的交通死鎖狀況：

(1)闡明產(chǎn)生死鎖的4個必要條件在此處成1。

(2)給出一種防止死鎖的簡樸規(guī)則。

7.11設有一系統(tǒng)在某時刻的資源分派狀況如下:

進程號已分派資源最大祈求資源剩余資源

ABCDABCDABCD

PO001200121520

Pl10001750

P213542356

P306320652

P400140656

請問：

(1)系統(tǒng)中各進程尚需資源數(shù)各是多少？

(2)目前系統(tǒng)安全嗎？

(4)假如此時進程P1提出資源祈求(0,4,2,系統(tǒng)能分派給它嗎？

(1)尚需資源數(shù)矩陣如下：

Need=Max-Allocation

Need

ABCD

PO0000

Pl0750

P21002

P30020

P40642

(2)系統(tǒng)是安全的，由于可以找到一種安全序列:<P0,P2,P3,P4,P1>

(3)如P1申請(0,42,0),則：

Request1(0,4,2,0)<=nccd1(0,7,5,0)

Request1(0,4,2,0)<=availablc(l,5,2,0)

新日勺狀態(tài)為

AllocationMaxNeedAvailable

P00012001200001100

P1142017500330

P2135423561002

P3063206520020

P4001406560642

該狀態(tài)是安全的J,存在安全序列如vP0,P2,P3,P4,P1>,因此可以分派資源給P1。

8.3某系統(tǒng)有五個固定分區(qū)，其長度依次為100K,500K,200K.300K,600K。今有四個進程，

對內(nèi)存"勺需求分別是212K,417K,112K,426Ko當分別用First-fit,Best-fit,Worst-fit算

法響應這四個進程的內(nèi)存申請時，請分別給出系統(tǒng)的內(nèi)存分派動態(tài)。哪種算法最有效？

根據(jù)First-fit、Best-fitsWorst-fit算法，計算成果如下:

First-fit:

212K進程裝到500K分區(qū)

417K進程裝到600K分區(qū)

112K進程裝到200K分區(qū)

426K進程臨時等待

Best-fit:

212K進程裝到300K分區(qū)

417K進程裝到500K分區(qū)

112K進程裝到200K分區(qū)

426K進程裝到600K分區(qū)

Worst-fit:

212K進程裝至lj600K分區(qū)

417K進程裝到500K分區(qū)

112K進程裝到300K分區(qū)

426K進程臨時等待

僅就本題為例，Best-fit算法是最佳的。

8.5對下列問題，試比較持續(xù)內(nèi)存分派方案、純段式分派方案、純頁式分派方案中的內(nèi)存組

織措施：

a.外部碎片

b.內(nèi)部碎片

c.共享跨進程代碼的能力

持續(xù)內(nèi)存分派會產(chǎn)生外部碎片，由于地址空間是被持續(xù)分派的，當舊進程結(jié)束，新進程初始

化的時候，洞會擴大。持續(xù)內(nèi)存分派也不容許進程共享代碼，由于一種進程的虛擬內(nèi)

存段是不被容許闖入不持續(xù)口勺段的。純段式分派也會產(chǎn)生外部碎片，由于在物理內(nèi)存

中，一種進程時段是被持續(xù)放置日勺，以及當死進程時段被新進程時段所替代時，碎片

也將會產(chǎn)生。然而，段式分派可以使進程共享代碼；例如，兩個不一樣的進程可以共

享一種代碼段，不過有不一樣日勺數(shù)據(jù)段。純頁式分派不會產(chǎn)生外部碎片，但會產(chǎn)生內(nèi)

部碎片。進程可以在頁granularily中被分派，以及假如一頁沒有被完全運用，它就會

產(chǎn)生內(nèi)部碎片并且會產(chǎn)生一種相稱的空間揮霍。在頁granularity,頁式分派也容許進

程共享代碼。

8.9考慮一種分頁式存儲管理系統(tǒng)，其頁表常駐內(nèi)存。

（1）假如內(nèi)存訪問耗時200ns,那么，訪問內(nèi)存中H勺數(shù)據(jù)需要多長時間？

（2）假如引入聯(lián)想寄存器，并且75%11勺頁面可以從關聯(lián)寄存器中找到，那么，此時的有效

訪問時間為多少？（假設訪問關聯(lián)寄存器的時間可以忽視）

（1）400納秒，其中，200納秒訪問頁表，200納秒訪問內(nèi)存中的數(shù)據(jù)。

（2）有效訪問時間=0.75*（200納秒訪問內(nèi)存數(shù)據(jù)+0納秒訪問關聯(lián)寄存器）+0.25*（200

納秒訪問內(nèi)存數(shù)據(jù)1200納秒訪問頁表）=250納秒

8.12假設有下列段表：

段基地址段長度

0219600

1230()14

290100

31327580

4195296

下列邏輯地址對應日勺物理地址是什么？

(1)0,430

(2)1J0

(3)2,500

(4)3.400

(5)4,112

(1)219+430=649

(2)2300+10=2310

(3)第2段口勺有效長度是100。段內(nèi)偏移量500超過了這個上限，因此這是個非法地址

(4)1327+400=1727

(3)第4段的有效長度是96。段內(nèi)偏移量112超過了這個上限，因此這是個非法地址

9.5假設一種“按需調(diào)頁”虛擬存儲空間，頁表由寄存器保留。在存在空閑頁幀的條件下，處

理一次缺頁H勺時間是8亳秒。假如沒有空閑頁面，但待換出頁面并未更改，處理一次

缺頁的時間也是8毫秒。假如待換出頁面已被更改，則需要20亳秒。訪問一次內(nèi)存H勺

時間是100納秒。假設70%的待換出頁面已被更改，請問缺頁率不超過多少，才能保

證有效訪問時間不不小于或等于200納秒？

設缺頁率為P。題目并沒有明確，當缺頁中斷時，內(nèi)存中與否有空閑頁幀，因此假設內(nèi)存總

是忙時。

訪問內(nèi)存中頁面：(I-P)*100ns

頁面不在內(nèi)存，但不需要保留待換出頁面：P*(l-70%)*(8rns+100ns)

頁面不在內(nèi)存，但需要保留待換出頁面：P*70%*(20ms+100ns)

因此，有效訪問時間=(1-P)*100ns+P*(1-70%)*(8ms+100ns)+P*70%*

(20nis+100ns)=200ns

P=0.000006

9/0對?種祈求調(diào)頁系統(tǒng)測得如下數(shù)據(jù)：

?CPU運用率20%

?用作頁面互換的磁盤的運用率97.7%

?其他I/O設備運用率5%

下列措施中，哪些會改善CPU運用率(假如有口勺話)，請闡明理由:

(1)安裝一種更快日勺CPU

(2)安裝一種更大容量日勺磁盤用作頁面互換

(3)增長并發(fā)進程數(shù)

(4)減少并發(fā)進程數(shù)

(5)安裝更多內(nèi)存

(6)安裝更快的硬盤，或安裝更多H勺硬盤和控制器

(7)增長一種預取頁面算法

(8)增長頁面長度

首先判斷系統(tǒng)正在頻繁地進行換頁操作。因此，減少并發(fā)進程數(shù)會明顯地減少換頁操作,

提高CPUR勺運用率。其他措施也有些效果，例如，安裝更多內(nèi)存。

k.安裝一種更快的JCPU。沒用。

1.安裝一種更大容量H勺磁盤用作頁面互換。沒用，互換空間本來就足夠了。

m.增長并發(fā)進程數(shù)。沒用，狀況將會更糟。

n.減少并發(fā)進程數(shù)。效果明顯。

。.安裝更多內(nèi)存。也許會有效果，由于空閑頁幀增長了，換頁的幾率將相對減少。

p.安裝更快的硬盤，或安裝更多的硬盤和控制器。效果不明顯。

q.增長一種預取頁面算法。效果不確定。

增長頁面長度。假如次序訪問居多，則會減少缺頁次數(shù)。假如隨機訪問居多，由于單個頁面

占用更大的物理空間，頁項總數(shù)減少，因此缺頁次數(shù)會增長；由于頁面長度增長，頁面日勺傳

播時間會增長。綜上，此方案的效果不確定。

9.14一頁式虛擬存儲系統(tǒng)，用于頁面互換的磁盤的平均訪問、傳播時間是2()亳秒。頁表保

留在主存，訪問時間1微秒。也就是說，每引用一次指令或數(shù)據(jù)，需要訪問兩次內(nèi)存。

為改善性能，我們可以增設一種關聯(lián)寄存器。假如頁表項在關聯(lián)寄存器里，則只要訪

問一次內(nèi)存就夠了。假設80%日勺訪問，其頁表項在關聯(lián)寄存器中；剩余的20%里，10%

的訪問(即總數(shù)的2%)會產(chǎn)生缺頁。請計算有效訪問時間。

有效訪問時間=80%*1微秒+(1-80%)((1-10%)*1微秒*2+10%*(1微秒*2+20

亳秒)尸0.8+0.2*(0.9*2+0.1*20232)

=0.8+0.2*2023

=401.2微秒

9.01在某祈求分頁管理系統(tǒng)中，一種作業(yè)共5頁，作業(yè)執(zhí)行時依次訪問如下頁面：1,4,3,

1,2,5,1,4,2,1,4,5,若分派給該作業(yè)的主存塊數(shù)為3,分別采用FIFO、LRU,

試求出缺頁中斷的次數(shù)及缺頁率。(規(guī)定畫出頁面置換狀況表)

(I)采用FIFO頁面置換算法，其缺頁狀況如表所示：

FIFO頁面置換算法口勺缺頁狀況

頁面143125142145

走向

塊1111222444

塊244455522

塊33331115

11

缺頁VVV

缺頁中斷次數(shù)為9,缺頁率為9/12=75%。

(2)采用LRU頁面置換算法，其缺頁狀況如表所示。

LRU頁面置換算法的缺頁狀況

頁面143125142145

走向

塊111111111

塊24422444

塊3335525

缺頁、V47q47y

缺頁中斷次數(shù)為8,缺頁率為8/12=67%。

10.1假設有?種文獻系統(tǒng)，它里面的文獻被刪除后，當連接到該文獻日勺鏈接仍然存在時,

文獻的磁盤空間會再度被運用。假如一種新日勺文獻被創(chuàng)立在同一種存儲區(qū)域或具有同樣H勺絕

對■途徑名，這會產(chǎn)生什么問題？怎樣才能防止這些問題?

假設F1是舊的文獻，F(xiàn)2是新的文獻。當一種顧客通過已存在的鏈接訪問F1,實際卻是訪問

F2。這里使用日勺是對文獻F1的存取保護而不是與文獻F2有關的存儲保護。

采用刪除指向?種已刑除文獻日勺所有璉接的措施防止該問題?？梢酝ㄟ^幾種措施實現(xiàn)；

1.設置一種記錄指向一種文獻的所有鏈接的J鏈表，當這個文獻被刪除時，刪掉這些鏈接。

2.保留這些鏈接，當試圖訪問一種已被刪除的文獻時，刪掉這些鏈接。

3.設置一種文獻的指針鏈表（或計數(shù)器），當指向該文獻的所有指針被刪除時才真正刪除

這個文獻。

10.9有些系統(tǒng)文獻提供文獻共享時候只保留文獻口勺一種拷貝，而此外H勺一種系統(tǒng)則是保留

多種拷貝，對共享文獻的每一種顧客提供一種拷貝，論述這種措施的相對長處。

答：在一種單一時更制，同步更新了一種文獻也許會導致顧客獲得不對B勺的信息，文獻被留

在了不對的及I狀態(tài).伴隨多份拷貝，它會揮霍存儲并且多種副本也許不一致。

IL6假設一種在磁盤上日勺文獻系統(tǒng)，其中邏輯塊和物理塊大小為512字節(jié)。假定每個文獻口勺

信息已經(jīng)在內(nèi)存中，對于三種分派方略中的每一種（持續(xù)、鏈接、索引），請回答下面這些

問題。

（1）闡明在這個系統(tǒng)中是怎樣實現(xiàn)從邏輯地址到物理地址映射的？（對于索引分派，假設

文獻的長度總是不不小于512塊）。

（2）假如目前位于邏輯塊10（即最終一次訪問的邏輯塊是10）,且但愿訪問邏輯塊4,必須

從磁盤上讀多少個物理塊?

答：令Z是開始邏輯地址（塊號）。

a.若使用持續(xù)分派方略時。用512清除邏輯地址，則X和Y分別表達得到口勺整數(shù)和余數(shù)。

（1）將X加上Z得到物理塊號，Y為塊內(nèi)的位移

（2）1

b.若使用鏈接分派方略。用511清除邏輯地址，則X和Y分別表達得到R勺整數(shù)和余數(shù)。

（1）查找鏈表到第X+1塊，Y+1位該塊內(nèi)的位移量。

（2）4

c.若使用索引分派方略。用512清除邏輯地址，則X和Y分別表達得到日勺整數(shù)和余數(shù)。

（1）把索引塊讀入內(nèi)存中，則物理塊地址寄存在索引塊在第X位置中，Y為塊內(nèi)的位

移量。

（2）2

11.01考慮一種具有100塊II勺文獻。假如文獻控制塊（和索引塊，當用索引分派時）已經(jīng)在內(nèi)

存中。當使用持續(xù)、鏈接、單級索引分派方略時，各需要多少次磁盤I/O操作？假設在持續(xù)

分派時，在開始部分沒有擴張的空間，但在結(jié)尾部分有擴張空間，并且假設被增長塊的信息

已在內(nèi)存中：

（1）在開始增長一塊。

（2）在中間增長一塊。

（3）在末端增長一塊。

（4）在開始刪除一塊。

（5）在中間刪除一塊。

（6）在末端刪除一塊。

答:多種方略對應的磁盤I/O操作次數(shù)如表

持續(xù)鏈接索引

a.20111

b.10152I

c.131

d.19810

e.98520

f.01000

11.02有一磁盤組共有10個盤面，每個盤面上有100個磁道，每個磁道有16個扇區(qū)。假設

分派以扇區(qū)為單位。

（1）若使用位示圖管理磁盤空間，問位示圖需要占用多少空間？

（2）若空白文獻目錄的每個表目占用5個字節(jié)，問什么時候空白文獻目錄不小于位示

圖？

（3）空白文獻目錄是管理磁盤空間的?種措施，該措施將文獻存儲設備上日勺每個持續(xù)空

閑區(qū)看作一種空白文獻，系統(tǒng)為所有空白文獻單獨建立一種目錄，每個空白文獻在

這個目錄中占一種表項；表項的內(nèi)容至少包括第一種空白塊日勺地址（物理塊號）、空

白塊的數(shù)目。

(4)（1）由題設所給條件可知，磁盤組扇區(qū)總數(shù)為16*100*10=16000（個）

（5）因此，使用位示圖描述扇區(qū)狀態(tài)需要的位數(shù)為16（X）0（位）/8（位/字節(jié)）=2023

（字節(jié)）

（6）（2）已知空白文獻目錄日勺每個表項占5個字節(jié).而位示圖需占2023字節(jié).即2023

字節(jié)

（7）可寄存的表項數(shù)為2023/5=400（個）.

（8）當空白區(qū)數(shù)目不小于400時，空白文獻目錄不小于位示圖。

12.2假設一種磁盤驅(qū)動器有5000個柱面，從。至IJ4999,驅(qū)動器正在為柱面143的一種祈

求提供服務，且前面的一種服務祈求是在柱面125。按FIFO次序，即將到來的祈求隊列是

86,1470,913,1774,948,1509,1022,1750,130

從目前磁頭位置開始，按照下面的磁盤調(diào)度算法，要滿足隊列中即將到來的祈求規(guī)定磁頭總

的移動距離（按柱面數(shù)計）是多少？

a.FCFS

b.SSTF

c.SCAN

（1.LOOK

e.C-SCAN

【答】

a.FCFS口勺調(diào)度是143,86,1470,913,1774,948,1509,1022，1750，

130?？倢で缶嚯x是70810

b.SSTF臥J調(diào)度是143,130,86,913,948,1022,1470,1509,1750,

1774?？倢で缶嚯x是1745.

c.SCAN的調(diào)度是143,913,948,1022,1470,1509,1750,1774,4999,

130,86?？倢で缶嚯x是9769。

d.LOOK的調(diào)度是143,913,948,1022,1470,1509,1750,1774,130,

86。總尋求距離是3319o

e.C-SCANR勺調(diào)度是143,913,948,1022,1470,1509,1750,1774,

4999,86,130?？倢で缶嚯x是9985。

f.C-LOOK的調(diào)度是143,913,948,1022,1470,1509,1750,1774,

86,13()?？倢で缶嚯x是3363..

12.14MTBF(平均無端隙時間)是硬盤可靠性的一種指標。雖然這個指標被稱作“時間”，

但實際上MTBF一般是以設備的正常工作小時數(shù)度量的。

(1)假如一種系統(tǒng)包括1000個磁盤驅(qū)動器，每個驅(qū)動器的MTBF是750000小時，下面

的描述中哪一種最符合該系統(tǒng)發(fā)生一次磁盤故障的時間：每1023年，每世紀，每

十年，每月.每個星期,每天.每小時,每分鐘,每秒鐘？

(2)記錄表明，一種20到2