1.2例題精選

例1.1如何理解虛擬機的概念？

解:一臺僅靠由硬件組成的計算機一般被稱為裸機，不易使用。操作系統為用戶使用計算機提

供了許多服務，從而把一臺難于使用的裸機改造成了功能更強大、使用更方便的計算機系統，這

種計算機系統稱為虛擬機。所謂虛擬，是指把一個物理上的實體變為假設干個邏輯上的對應物。

前者是實際存在的，而后者是虛的，只是用戶的一種感覺。在單CPU的計算機系統中能同時運行

多道程序，好似每個程序都獨享一個CPU,這就是虛擬。在構造操作系統時，把操作系統分成假

設干層，每層完成特定的功能，從而形成一個虛擬機。下層的虛擬機為上層的虛擬機提供服務，

這樣逐次擴大以完成操作系統的功能。

討論“虛擬”的概念表現在操作系統的方方面面。例如，虛擬存儲器，使一臺只有4MB存的

計算機可以運行總容量遠遠超過4MB的程序；虛擬外設，能夠使多個用戶同時訪問該外設等。

例1.2什么是多道程序設計，它的主要優點是什么？

解：所謂多道程序設計是指把一個以上的程序存放在存中，并且同時處于運行狀態，這些程

序共享CPU和其他計算機資源。其主要優點是：

〔1〕CPU的利用率高：在單道程序環境下，程序獨占計算機資源，當程序等待I/O操作時

CPU空閑，造成CPU資源的浪費。在多道程序環境下，多個程序共享計算機資源，當某個程序

等待I/。操作時，CPU可以執行其他程序，這大大地提高了CPU的利用率。

〔2〕設備利用率高：在多道程序環境下，存和外設也由多個程序共享，無疑也會提高存和外

設的利用率。

〔3〕系統吞吐量大：在多道程序環境卜\資源的利用率大幅度提高，減少了程序的等待時間，提

高了系統的吞吐量。

討論多道程序在計算機中并發地運行是現代計算機系統的重要特征。早期的單道批處理系統與人

工操作相比自動化程度大大提高，但系統中仍有較多的空閑資源，系統的性能較差。多遭批處理

系統雖有很多優點，但這種系統交互能力差，作業的平均周轉時間長。多道程序處理系統要解決

的主要問題是，如何使多個程序合理、有序地共事處理機、存、外設等資源。

例1.3A,B兩個程序，程序A按順序使用CPU10S,使用設備甲5S,使用CPU5S,

使用設備乙10S,最后使用CPU10So程序B按順序使用設備甲10S,使用CPU10S,

使用設備乙5S,使用CPU5S,使用設備乙10S。〔忽略調度程序執行時間〕試問：〔1〕在順序

環境下執行程序A和程序B,CPU的利用率是多少？〔2〕在多道程序環境下，CPU的利用率

是多少？解口〕程序A和程序B順序執行時，程序A執行完畢，程序B才開始執行。兩個程序

共耗時80S,其中占用CPU時間為40S,順序執行時CPU的利用率為50%。〔2〕在多道程

序環境下，兩個程序并發執行，其執行情況如下列圖。可以看出，兩個程序共耗時45S,其中占

用CPU時間為40S,故此時CPU的利用率為40/45=88.89%。

討論⑴聲單道程序環境下，程序順序執行，CPU被一道程序獨占，即使CPU空閑，其他程

序也不能使人，所以?CPU而利用素低;?[2]在多道程3環境卜，版設干個程序宏觀上同時

執行，微觀上交替執行。當其中一個程序由于某種原因〔例如進展1/0操作〕而不能占用CPU

時，其他程序就可以占用CPU,提高了CPU的利用率。〔3〕在該例中，當程序A使用完

設備甲時，由于CPU正被程序B占用，所以程序A必須等待一段時間〔如虛線所示〕。同

理，當程序B第二次使用完CPU準備使用設備動時，由于此時設備乙正被程序A占用，所以

程序B也必須等待一段時間〔如虛線所示〕，這時CPU將空閑〔如虛線所示〕。

例1.4試述分時系統與實時系統，并比擬它們的區別。解:分時系統是指在一個系統中多個用戶

分時地使用同一計算機。實時系統是指計算機與時響應外部事件的請求，在規定時限完成對該事

件的處理，并控制所有實時設備和實時任務協調一致地運行。實時系統與分時系統的主要區

別有兩點。(1)分時系統的目標是提供一種通用性很強的系統，有較強的交互能力，而實時系統如

此大都是具有特殊用途的專用系統，交互能力略差；〔2〕分時系統對響應時間雖有要求，但一般

來說，響應時間由人所能承受的等待時間來確定；而實時系統對響應時間要求更高，一般由控制

系統或信息處理系統所能承受的延遲時間來決定。

1.3習題

1.填空題：

(1)當CPU執行操作系統代碼時，稱處理機處于〔A〕執行態［B］目態〔C〕管態〔D〕

就緒態

(2)在如下性質中，不是分時系統的特征。〔A〕多路性〔B〕交互性〔C〕獨占性:D〕成

批性

(3)如下僅一條指令只能在管態下執行。〔A〕讀取時鐘指令〔B〕訪管指令〔C〕屏蔽中斷

指令〔D〕取數指令

2.何謂管態〔系統態〕和目態〔用戶態〕？

3.一般從哪幾方面對操作系統的性能進展評價？

4.試說出幾種你所熟悉的操作系統名稱，并說明其特征。

5.試列舉UNIX操作系統的特點。

6.根據你使用計算機系統的經驗，說明操作系統的作用。

7.試說明批處理系統、分時系統和實時系統的主要特征。

8.如何理解網絡操作系統的主要功能？

9.A,B兩個程序,A按順序使用CPU10s,使用設備甲5s,使用CPU5s,使用設備乙10s,最

后使用CPU10s;程序B按順序使用設備甲10s,使用CPU10s,使用設備乙5s,使用CPU

5s,最后使用設備乙10so請問：

(1)在順序執行程序A和B時，CPU的利用率是多少？

(2)在多道程序環境下執行時，CPU的利用率是多少？

例題：考慮5個進程Pl,P2,P3,P4,P5,見表。規定進程的優先數越小，優先級越高。試描

述在采用下述幾種調度算法時各個進程運行過程，并計算采用每種算法時的進程平均周轉時間。假

進程創建時間運行時間優先數

PI033

P2265

P3441

P4652

P5824

設忽略進程的調度時間。〔1〕先來先服務調度算法；〔2〕時間片輪轉調度算法〔時間片為1ns];

〔3〕非剝奪式優先級調度等法；〔4〕剝奪式優先級調度算法。表2.1例2?5

懈(1)先來先服務調度算法：迸程的運行過程如圖2.3所示O

IO1520

[]I11

P?

P.

Ps

圖2.3先來先服務調度算法進程的運行過程示意圖

(2＞時間片輪轉洞度算法：進程的運行過程如圖2.4所示》

1520

L」111?|」1

Ps

圖2.4時間片輪轉調度算法進程的運行過程示意圖

數據表

算法進程名創建時刻結束時刻周轉射間/ms平均周轉時間/mz

Pi033

Pz297

非剝奪

p4139(3+7+9+12+12)/5=8.60

式優先級3

p.61812

Ps82012

p.033

20

p2218

剝奪式

PH484(3+18+4+7+7)/5=7.80

優先級

巳6137

P;.8157

（3）非剝奪式優先級調度算法：進程的運行過程如圖2.5所示。

圖2.5非剝奪式優先級調度算法進程的運行過程示意圖

（4）剝奪式優先級調度算法：進程的運行過程如圖2.6所示。

圖2.6剝奪式優先級調度算法進程的運行過程示意圖

各種算法的平均周轉時間見表2.2。

*2.2進程的平均周轉時間

算法進程名創建時刻結束時刻周轉時間/ms平均周轉時間/ms

Pl033

297

p2

先來先

p4139(3+7+9+12+12)/5=8.60

服務3

p,61812

Ps82012

Pl044

21816

p2

時間片

41713(4-4-16-F13H-144-7)/5=10.8()

輪轉

62014

Ps8157

練習題

一、單項選擇題

1、一個進程是o〔清華大學1996〕

A由協處理機執行的一個程序B一個獨立的程序+數據集

cPCB結構與程序和數據的組合D一個獨立的程序

2、并發進程之間o

A彼此無關B必須同步C必須互斥D可能需要同步或互斥

3、是進程調度算法。

A時間片輪轉法B先來先服務C響應比高者優先D均衡調度算法

4、當時，進程從執行扎轉變為就緒狀態。〔西北工大1999]

A進程被調度程序選中B時間片到C等待某一事件D等待的事件發生

5、系統中有n[n>2]個進程，并且當前沒有執行進程調度程序，如此—不可能發生。

A有一個運行進程，沒有就緒進程，剩下的n-1個進程處于等待狀態

B有一個運行進程和n-1個就緒進程，但沒有進程處于等待狀態

C有一個運行進程和1個就緒進程，剩下的n-2個進程處于等待狀態

D沒有運行進程但有2個就緒進程，剩下的n-2個進程處于等待狀態

6、支持多道程序設計的操作系統在運行過程中，不斷地選擇新進程運行來實現CPU的共享，

但其中不是引起操作系統選擇新進程的直接原因。〔復旦大學1999〕

A運行進程的時間片用完B運行進程出錯

C運行進程要等待某一事件的發生D有新進程進入就緒狀態

二、判斷題

1、在剝奪式進程管理方式下，現運行進程的優先級不低于系統中所有進程的優先級。

2、進程是一個獨立的運行單位，也是系統進展資源分配和調度的根本單位。

3、程序的并發執行是指同一時刻有兩個以上的程序，它們的指令在同一處理器上執行。

4、進程山進程控制塊和數據集以與對該數據集進展操作的程序段組成。

5、并發是并行的不同表述，其原理一樣。

三、問答題

1、操作系統中為什么要引入進程的概念？為了實現進程的并發運行，操作系統在進程管理

方面應做那些工作？〔大學1997〕

2、試比擬進程與程序的區別。〔工業大學2000]

3、進程與線程的主要區別是什么？〔西北工大1999]

例：假設某系統中有4種資源(RI,R2,R3,R4),在某時刻系統中共有5個進程。進程P1,

P2,P3,P4,P5的最大資源需求數向量和此時已分配到的資源數向量分別為

進程當前己分配到資源最大資源需求

P1(0,0,1,2)(0,0,1,2)

p2(2,0,0,0)(2,7,5,0)

P3(0,0,3,4)(6,6,5,6)

P4(2,3,5,4)(4,3,5,6)

P5(0,3,3,2)(0,6,5,2)

系統中當前可用資源向量為(2,1,0,0)。問：

(1)當前系統是否是安全的？

(2)如果進程3已發出資源請求向量(0,1,0,0),系統能否將資源分配給它？

解：(1)進程的最大資源需求數減去當前進程P1:(0,0,0,0)

已獲得的資源數就是進程仍需的資源數。此時各個P2；[0,7,5,0)

進程的仍需資源數向量為P3:(6,6,2,2)

P4：(2,0,0,2)P1完成后：(2,1,1,2)

P5:(0,3,2,0)P4完成后：(4,4,6,6)

P5完成后：(4,7,9,8)

P2完成后：(6,7,9,8)

而系統的可用資源向量為(2,1,0,0),這P3完成后：(6,7,12,12)

時存在如下進程執行序列，可以使進程順利執行完

畢，所以該狀態是安全的。

進程可用資源數

(2)在P3發出資源請求(0,1,0,0)后,

假設系統把資源分配給P3,如此各進程己分配資

源數為

P1:(0,0,1,2)

P2：(2,0,0,0)

P3：(0,1,3,4)

P4：(2,3,5,4)

P5:(0,3,3,2)

這時系統可用資源數為(2,0,0,0),各個

進程仍需資源向量為

P1:(0,0,0,0)

P2：(0,7,5,0)

P3：(6,5,2,2)

P4：(2,0,0,2)

P5：(0,3,2,0)

滿足資源需求的進程執行序列為

進程可用資源數

P1完成后：(2,0,1,2)

P4完成后：(4,3,6,6)

P5完成后：(4,6,9,8)

此時可用資源已不能滿足P2或P3的需求，即此時系統狀態是不安全的，系統將拒絕資源請求。

討盼銀行家算法的關鍵是尋找一個進程的運行序列，如果系統按該序列調度進程運行，系統的可

用資源就可以滿足它們的需求，這時資源分配是安全的；否如此，假設該進程序列不存在，如此資源分

配是不安全的，系統暫不進展資源分配。

一、生產者和消費者問題

1、有n個緩沖區，一個生產者和一個消費者情況：

123456789n

outin

consumerprcducer

main()

{intS=l;〃可否進入緩沖區

intfull=O;//產品數目

intempty=n//可用緩沖區數

intbuffer[n];

intin=0;〃指向下一個可放產品的緩沖區

intout=0;〃指向下一個可取產品的緩沖區

producerQ;

consumer();

}

producer()

{

While(生產未完畢)

{produceaproduct

P(empty);

P(S);

Buffer[in]=product;

in=(in+l)modn;

V(S);

V(full);

consumerf)

(

While(消費未完畢)

{P(full);

P(S)；

TakeaproductfromBuffer[out]

Out=(out+l)modn;

V(S);

V(empty);

}

Consumetheproduct

2、m個生產者和k個消費者共享n個緩沖區的情況:

有界緩沖區兀-Ci

c

P2--z

12?…一?n

Pi一Cf

123456789n

outin

consumerproducer

main()

intB[n];//緩沖區

intp=r=O;//p表示生產者指針，r表示消費者指針

intS=l;//可否進入緩沖區

intfull=O;〃產品數目

intempty=n;//可用緩沖區數

producer-i(i=1

consumer-j(j=l,2,...,k);

}

Producer-i(i=1

{

while(producingdoesnotend)

{

produceaproduct

P(empty);

P(S);

B[p]=product;

p=(p+l)modn;//每放入一個產品，位置指針后移一位

V(S);

V(full);

Consumer-j(j=1

(

while(continuetoconsume)

{

P(full);

P(S)；

TakeaproductfromB[rj

r=(r+l)modn;//從第一個開始，消費一個后，指向下一個

V(S);

V(empty);

Consume

二、讀者與寫者問題

1、讀者與寫者有一樣的優先級的情況:

main()

intS=l;〃讀者與寫者，寫者與寫者間的互斥，即可否修改文件

intSr=l;〃可否修改讀者個數

intrc=O;//讀者個數

reader();

writer();

)

reader()

{

While(讀過程未完畢)

(

P(Sr);

if(rc==O)

{P(S);

rc=rc+l;

V(Sr);

readfileF

else

(

rc=rc+1;

V(Sr);

readfileF

}

P(Sr);

rc=rc-1;

if(rc==O)V(S);

V(Sr);

writerf)

{

While(寫過程未完畢)

{

P(S);

WritefileF

V(S);

2、寫者優先問題:

main()

(

intS=l;〃讀者與寫者，寫者與寫者間的互斥，即可否修改文件

intSn=n;//最多有n個進程可以同時進展讀操作

reader();

writer()

reader(i)

{

P(S);

P(Sn);

V(S);

ReadfileF

V(Sn);

writer(j)

{

P(S)

WritefileF

V(S);

}

例題

1、有一個閱覽室，讀者進入時必須先在一登記表上進展登記。該表為每一座位列出一個表目，包

括座號、。讀者離開時要撤消登記信息。閱覽室有100個座位，試問：

(1)為描述讀者的動作，應編寫幾個程序？，應該設置幾個進程？進程和程序之間的關系如

何？

(2)試用P、V操作描述這些進程之間的同步算法。

2、假設系統有某類資源m*n+l個，允許作業執行過程中動態申請該類資源，但在該系統上運行的

每一個作業對該類資源的占有量在任一時刻都不會超過m+1個。當作業申請資源時，只要資源

尚未分配完，如此總能滿足它的要求。但用限制系統中可同時執行的作業個數來防止死鎖。你認

為作業調度允許同時執行的最大作業數應為多少？證明之。

3、假設系統有同類資源m個，被n個進程共享，試問：當m>n和m〈n,每個進程最多可申請多

少個這類資源而使系統一定不會發生死鎖？

4、設Pa,Pb,Pc為一組合作進程，其進程流程圖如下所示。試用信號燈的P、V操作實現這三個

進程的同步。

Q

PbvPc

vJ

5、醫生給病人看病，需要化驗，于是醫生開出化驗單，病人到化驗室化驗，化驗結果送回醫生處供

醫生診斷。醫生看病為一個進程，化驗室化驗為一個進程，二者需要交換信息，試用信號燈的P、V

操作實現這兩個進程的同步關系。

6、設有兩個優先級一樣的進程Pl、P2如下：令信號量SI,S2的初值為0,試問Pl、P2并發運

行完畢后X=?y=?z=?

進程Pl進程P2

y=i;x=i；

y=y+2;x=x+1;

V(S1);P(S1);

Z=y+1;x=x+y;

P(S2);V(S2);

Y=z+y;z=x+z;

7、在一個盒子里，混裝了數量相等的圍棋白子和黑子。現在要用自動分揀系統把白子和黑子分開。

該系統設有兩個進程Pl、P2,其中P1將揀白子，P2將揀黑子。規定每個進程每次只揀一子。當

一進程正在揀子時，不允許另一進程去揀，當一進程揀了一子時，必須讓另一進程去揀。試寫出兩

個并發進程能正確執行的程序。

8、桌上有一只盤子，每次只能放入一個水果。爸爸專向盤中放蘋果，媽媽專向盤中放橘子，一個女

兒專等吃盤中的蘋果，一個兒子專等吃盤中的橘子。試用P、V操作寫出他們能同步的程序。

例4.1某虛擬存儲器的用戶空間共有32個頁面，每頁1KB,主存16KB。試問：〔1〕邏

輯地址的有效位是多少？

〔2〕物理地址需要多少位？

〔3〕假定某時刻系統為用戶的第0,1,2,3頁分別分配的物理塊號為5,10,4,7,試將

虛地址0A5c和093c變換為物理地址。

解〔1〕程序空間的大小為32KB,因此邏輯地址的有效位數是15位。

〔2〕存儲空間的大小是16KB,因此物理地址至少需要14位。

〔3〕當頁面為1KB時，虛地址OA5c表示頁號為00010,頁地址是1001011100。

該頁在存的第4塊，即塊號為0100,因此OA5co93c的物理地址是113CH。

討論分頁存儲管理的地址變換非常簡單，只要記住一點，山頁號查頁表得物理塊號，然后與頁地

址拼接成物理地址。

例4.2某段式存儲管理中采用如表4.1所示的段表。

表4.1段表

段號段的長度/B內存起始地址

O660219

1143330

21OO90

35801237

?1961952

〔1〕給定段號和段地址，說明段式管理中的地址變換過程。

〔2〕計算[0,430],[1.10],[2,500],[3,400],[4,20],[5,100]的存地址，其中

方括號的第一元索是段號，第二元素是段地址。

〔3〕說明存取主存中的一條指令或數據至少要訪問幾次主存。

解〔1〕為了實現從邏輯地址到物理地址的變換，在系統中需要設置段表存放器，存放段表起站地址

和段表長度TL。在進展地址變換時，系統將邏輯地址中的段號S與段表長度TL進展比擬。假設S

>TL,如此表示段號太大，是訪問越界〔段號越界〕，產生越界中斷。假設未越界，如此根據段表的

起始地址和段號，計算出該段對應段表項的位置，從中讀出該段在存中的起始位置和段長SL,再檢

查段地址d是否超過該段的段長SL。假設超過，即d>SL,如此同樣發出越界中斷信號〔段地址

越界〕；假設未越界，如此將該段的起始地址與段地址d相加，即得要訪問的存物理地址。

〔2〕[0,430]的物理地址是219+430=649。

[1,10]的物理地址是3330+103340。

因500>100,所以[2,500]越界〔段地址越界〕。

[3,400]的物理地址是1237+400=1637。

[4,20]的物理地址是1952+20=1972。

因5>4,所以[5,100]越界〔段號越界〕。

〔3〕存取主存中的一條指令或數據至少要訪問2次主存。一次是訪問段表，另一次是訪問需要的

指令或數據。

討論在分段存儲管理的地址變換過程中，要點是由段號杳段表得段起始地址，然后與段地址相加

得物理地址。但要注意，段地址是二維地址，段號和段地址都有.可能越界。

例4.3分頁和分段有何區別？為什么說分段系統較之分頁系統更易于實現信息共享和保護？如何

實現？

解分頁和分段都采用離散分配方式，但兩者有顯著的差異。

[1]頁是信息的物理單位，分頁是系統的需要，是為了提高存的利用率；段是信息的邏輯單位，目

的在于更好地滿足用戶的需要。

〔2〕頁的大小固定，且由系統確定，一個系統只能有一種大小的頁面；段的長度不固定，決定于用

戶的程序。

〔3〕分頁的作業地址空間是一維的，單一的線性地址空間；分段的作業地址空間是二線的，一個地

址包括段號和段地址。

在分頁和分段存儲管理系統中，多個作業并發運行，共享同一存塊里的程序或數據是可行的。為了

實現共享，必須在各共享者的段表或頁表中分別有指向共享存塊的表目。對分段式系統，被共享的

程序或數據可作為單獨的一段。在物理上它是一段，在不同的進程中，可以對應不同的邏輯段，相

對來說比擬易于實現C對分頁管理，如此要困難得多。首先，必須保證被共享的程序或數據占有整

數塊，以便與非共享局部分開。其次，由于共享程序或數據被多個進程訪問，所以每個進程對共享

程序或數據的訪問都應該是有限制條件的。因此，從共享和保護的實現上來看，須共享的程序段或

數據段是一個邏輯單位，而分段存儲管理中被共享的程序或數據作為一個整體〔一段〕，實現共享和

保護就要方便得多。

分段系統的共事是通過兩個〔或多個〕進程的段表之相應表目都指向同一個物理段，并設置共享計

數來實現的。每段設置訪問方式，就可以實現段的保護。

討論分頁與分段的邏輯地址一個是一維，一個是二維，一定要加以區別。從共享與保護來講.分頁

管理也可以實現，但非常復雜，一般系統不易實現。

例4.4在一個請求分頁系統中，假設一個作業的頁面走向為4,3,2,1,4,3,5,4,3,2,

1,5。當分配給該作業的物理塊數M分別是3和4時，分別采用LRU和FIFO頁面替換算法，

432143543215432143543215

F444111555L4441115222

TI

F33344422R333444411

O2223331U22233335

缺頁次數=1。次，缺頁率=<10/12〉X100%=83%。

(2>當A^=4時.采用LRU替換算法

4321435432

444444444445

33333333333

2222555511

111]11222

1

缺頁次數=8次，缺貞率=(8/12)X100%=67%O

當AZ=4時，采用FIFO替換算法：

4321435432

——&-------

444444555511

333333.44445

2222223333

111111222

計算訪問過程中所發生的缺頁次數和缺頁率；比擬所得結果。

缺頁次數=1。次，缺頁率=〔10/12〕*100%=83%。

通過以上缺頁次數和缺頁率的分析計算，可以看出，對于LRU算法，增加物理塊數，可以減少缺頁

次數，降低缺頁率。而對FIFO算法，增加物理塊數，不一定能減少缺頁次數。

討論計算缺頁次數和缺頁率時，要注意初始時刻所有物理塊為空。調入頁面時，不需要頁面替換，

但是需要引起缺頁中斷。

例4.5什么是虛擬存儲器？在分頁存儲管理系統中如何實現虛擬存儲？

解所謂虛擬存儲器是指僅把作業的一局部裝入存便可運行作業的存儲管理系統。它具有請求調入功

能和置換功能，能從邏輯上對存容量進展擴大。

請求分頁存儲管理系統是在分頁管理的根底上實現的。頁表中除了有頁號、物理塊號兩項外，還需

要狀態位、訪問字段、修改位、外存地址等信息。由于是局部調入存，每當所要訪問的頁面不在存

時，便要產生缺頁中斷，請求操作系統將所缺頁調入存。缺頁中斷的處理過程是保存CPU現場；從

外存中找釗所缺的頁面；假設存已滿，如此選擇一頁換出，從外存讀入所缺的頁面，寫入存，修改

頁表。

在進展地址變換時，假設發現被訪問的頁不在存，必須先通過缺頁中斷將所缺的頁面調入存，并修

改頁表。其余的過程與分頁管理類似。全過程如圖4.3所示。

開始

圖4.3請求分頁管理的地址變換過程

討論請求分頁存儲管理系統實現的重點，在于對地址變換過程和缺頁中斷處理過程的

理解。

例4.6類似于請求分頁存儲管理中的請求式調頁那樣，在請求分段存儲管理中也可以

采用請求式調段策略。試提出一個合理的段替換算法，并說明在段替換過程中會出現哪些在負面替

換過程中不出現的問題。

解可以使用FIFO替換算法。它在存中查找第一個滿足要求的段。為防止部存儲碎片，可把該段的

末被占用的局部并入空閑空間表中。假設找不到滿足要求的段，如此可以選擇兩個或多個連續的段

來滿足要求。

在段替換過程中，必須要考慮到段的大小變化，但在頁面替換中頁面的大小是固定的。

討論關于請求分段存儲管理的段替換算法，考慮到段大小的不固定，可能需要替換假設干個連續的

段才能滿足要求，所以替換算法應力求簡單，FIFO算法成為首選。

4.3習題

4.1填空題：

〔1〕存儲管理方案中,可采用覆蓋技術。

〔A〕單一連續區存儲管理〔B〕可變分區存儲管理

〔C〕段式存儲管理〔D〕段頁式存儲管理

〔2〕對如圖4.4所示的存分配情況〔其中，陰影局部表示已占用塊，空白局部表示空閑塊〕，假

設要申請一塊40KB的存，對于最優適應分配策略給出分配區域的首地址是。

〔A〕110KB[B]190KB〔C〕330KB[D]410KB

〔3〕在圖4.4所示中，假設要申請一塊40KB的存，使首地址最大的分配策略是。

〔A〕首次適應分配策略〔B〕最優適應分配策略

[C]最壞適應分配策略〔D〕單一連續區分配策略

〔4〕如下算法中會產生Belady異常現象的是。

〔A〕先進先出〔FIFO〕頁面替換算法

[B]最近最久未使用[LRU]替換算法

[C]最不經常使用CLFU]頁面替換算法

〔D〕最優〔Optimal〕頁面替換算法

4.2為什么要引入動態重定位？如何實現？

4.3在動態分區管理中，有哪些分區分配算法？各有何優缺點？

4.4在采用首次適應算法的分區管理中，回收存時可能出現哪幾種情況？應怎樣處理這些情況？

4.5什么叫覆蓋？使用覆蓋技術有什么要求？

4.6在系統中引入交換技術后帶來哪些好處？為實現交換，系統應具備哪些方面的功能？

4.7對于一個利用快表且頁表存于存的分頁系統，假定CPU一次訪存時間為L5us。訪問快表的

時間可以忽略不計。試問：

[1]如果85%的地址映射可以直接通過快表完成〔即快表命中率為85%〕那么進程完成一次存讀

寫的平均有效訪問時間是多少？

〔2〕假設快表的命中率只有50%,那么進程完成一次存讀寫的平均有效訪問時間又是多少？

〔3〕快表命中率對平均有效訪問時間有何影響？

4.8什么叫動態裝入？動態裝入的優點是什么？

4.9為什么引入虛擬存儲概念？虛擬存儲器的容量由什么決定？受什么影響？

4.10請指出下面哪些程序設計技術和數據結構適合于請求分頁存儲管理環境，哪些不適合請求式分

頁存儲管理環境。

〔1〕棧〔2〕雜湊符號表〔3〕順序查找〔4〕折半查找〔5〕純代碼〔6〕向量操作。

4.11假定有一個請求分頁存儲管理系統，測得各相關成分的利用率為：CPU利用率為20%;磁

盤交換區為96.7%;其他I/O設備為50%。

試問下面哪些措施將〔可能〕改良CPU的利用率？

[1]增加一個更快速的CPU。〔2〕增大磁盤交換區的容量。

〔3〕增加多道程序的度數。〔4〕減少多道程序的度數。

〔5〕增加其他更快速的I/O設備。

4.12設有二維數組

intA[1..100][1..100];

其中數組元素A[1,1]存放在頁面大小為200的分頁存儲管理系統中的地址200處，數組

按行存儲。使用該數組的一個較小的程序存放在第0頁中〔地址0?〕，這樣將只會從第。頁取指令。

假定現有三個頁面，第一個頁面存放程序，其余兩個頁面用于存放數據，初始為空。試問：假設

使用LRU替換算法，下面的數組初始化循環將會產生多少次缺頁中斷？假設每頁的頁面大小為100,

數組初始化循環將會產生多少次缺頁中斷？并說明頁面大小對缺頁中斷次數的影響.

(1)for(j=l;j<=l00;j++)for(k=1;k<=100;k++)A[j][k]=0;

(2)for(j=l;j<=100;j++)for(k=l;k<=100;k++)A[k][j]=0;

4.13考慮下面的頁訪問串：

1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6

假定有1,2,3,4,5,6,7個頁塊。試問：假設應用下面的頁面替換算法，各會出現多少

次缺頁中斷？注意，所給定的頁塊初始均為空，因此，首次訪問一頁時就會發生缺頁中斷，

〔1〕LRU替換算法。〔2〕FIFO替換算法。〔3〕Optima替換算法。

4.14什么是局部性原理？什么是抖動？有什么方法可以減少系統的抖動現象？

4.15什么叫工作集？工作集模型的優點是什么？

例1：假定盤塊的大小為1KB,硬盤的大小為500MB,采用顯式分配方式時，其FAT需占用多少

存儲空間？如果文件A占用硬盤的第11,12,16,14四個盤塊，試畫出文件A中各個盤塊間的

情況與FAT的情況。

例2:存放在某個磁盤上的文件系統，采用混合索引分配方式，其FCB中共有13個地址項，第0~9

個地址項為直接地址，第1。個地址項為一次間接地址，第11個地址項為二次間接地址，第12個

地址項為三次間接地址。如果每個盤塊的大小為512字節，假設盤塊號需要用3個字節來描述，而

每個盤塊最多存放170個盤塊地址：

[1]該文件系統允許文件的最大長度是多少？

〔2〕將文件的字節偏移量5000,15000,150000轉換為物理塊號和塊偏移量。

〔3〕假設某個文件的FCB已在存，但其他信息均在外存，為了訪問該文件中某個位置的容，最少

需要幾次訪問磁盤，最多需要幾次訪問磁盤？

答：

(1)該文件系統允許文件的最大長度是多少？

10+170+170x170+170x170x170=4,942,080盤塊

4,942,080*512Byte=2,471,040KB

(2)將文件的字節偏移量5000、15000、150000轉換為物理塊號和塊偏移晟。

5000=9x512+392

15000=29x512+152

15(X)(X)=292x512+496

(3)假設某個文件的設備目錄表項(FCB)己在存中，其它信息在外存，為了訪問該文件的某個字節，最少需要兒

次訪