操作系統(tǒng)復(fù)習(xí)試題

本文格式為Word版，下載可任意編輯——操作系統(tǒng)復(fù)習(xí)試題1.操作系統(tǒng)是系統(tǒng)軟件中的一種，在進(jìn)行系統(tǒng)安裝時(shí)可以先安裝其它軟件，然

后再裝操作系統(tǒng)。

答:操作系統(tǒng)是系統(tǒng)軟件中的一種，在進(jìn)行系統(tǒng)安裝時(shí)必需先安裝其它軟件，然后再裝操作系統(tǒng)。

2.在虛擬存儲(chǔ)系統(tǒng)中，操作系統(tǒng)為用戶提供了巨大的存儲(chǔ)空間。因此，用戶地

址空間的大小可以不受任何限制。

答：在虛擬存儲(chǔ)系統(tǒng)中，操作系統(tǒng)為用戶提供了巨大的存儲(chǔ)空間。但是，用戶地址空間的大小仍舊不受任何限制。

3.在請(qǐng)求式分頁(yè)系統(tǒng)中，增加內(nèi)存幀一定可以降低缺頁(yè)中斷率。4.

答：在請(qǐng)求式分頁(yè)系統(tǒng)中，增加內(nèi)存幀不一定可以降低缺頁(yè)中斷率。

5.若系統(tǒng)處于擔(dān)憂全狀態(tài)，則一定發(fā)生了死鎖。

答：若系統(tǒng)處于擔(dān)憂全狀態(tài)，則不一定發(fā)生了死鎖。

OPT頁(yè)面替換算法是堆棧型算法？證明如下：由于LRU算法滿足，n=Lt時(shí)，Bt(n)=Bt(n+1)

n表示分派給程序的實(shí)頁(yè)數(shù)，Bt(n)表示t時(shí)刻在n個(gè)實(shí)頁(yè)中的虛頁(yè)集合，Lt為t時(shí)刻不同虛頁(yè)的頁(yè)面數(shù)。由于在主存中保存的是最近使用過(guò)的頁(yè)面。假使先給某一個(gè)程序分派n個(gè)主存頁(yè)面，那么在t時(shí)刻，這n個(gè)主存頁(yè)面都是最近使用過(guò)的頁(yè)面。假使再給這個(gè)程序多分派一個(gè)主存頁(yè)面，那么在t時(shí)刻，這n＋1個(gè)主存頁(yè)面也都是最近使用過(guò)的頁(yè)面。因此，在這n＋1個(gè)主存頁(yè)面中必然包含了前面的n個(gè)主存頁(yè)面。所以，opt算法是堆棧型算法。

1.讀著優(yōu)先、寫(xiě)者優(yōu)先（代碼）。

讀者優(yōu)先

假使有讀者來(lái)時(shí)，

①無(wú)讀者和寫(xiě)者，新讀者可以讀；

②如有寫(xiě)者等待，但有其他讀者正在讀，則新讀者可以讀；③有寫(xiě)者寫(xiě)，新讀者則等待

Varwsem:semaphore;(initialvalue:1)

Writer：

while(1){V(wsem);}P(wsem);intreadCount=0;

semaphorewsem=1;semaphoremutex=1;

reader()：while(1){

P(mutex);

寫(xiě)者優(yōu)先

假使有寫(xiě)者來(lái)時(shí)，

①無(wú)讀者，新寫(xiě)者可以寫(xiě)；

②如有讀者正在讀，則新讀者等待；③有其他寫(xiě)者正在寫(xiě)，新寫(xiě)者則等待。intwriteCount=0;

semaphorewsem,rsem=1;semaphoremutexY=1;writer()：while(1){

P(mutexY);

writeCount=writeCount+1;if(writeCount==1)P(rsem);V(mutexY);P(wsem);V(wsem);P(mutexY);

writeCount=writeCount-1;if(writeCount==0)V(rsem);V(mutex);}

intreadCount=0;

semaphorewsem,rsem=1;semaphoremutexX,mutex=1;reader()：while(1){

readCount=readCount+1;if(readCount==1)P(wsem);V(mutex);P(mutex);

readCount=readCount-1;if(readCount==0)V(wsem);V(mutex);}

P(mutex);P(rsem);P(mutexX);

readCount=readCount+1;if(readCount==1)P(wsem);V(mutexX);V(rsem);V(mutex);P(mutexX);

readCount=readCount-1;if(readCount==0)V(wsem);V(mutexX);}

變量wsem用來(lái)保證讀者與寫(xiě)者之間的互斥，以及寫(xiě)者與寫(xiě)者之間的互斥；變量writeCount用來(lái)記錄寫(xiě)者的數(shù)目；變量mutexY用來(lái)實(shí)現(xiàn)讀者對(duì)于變量writeCount訪問(wèn)的互斥；變量readCount用來(lái)記錄讀者的數(shù)目；變量mutexX用來(lái)實(shí)現(xiàn)讀者對(duì)于變量readCount訪問(wèn)的互斥;mutex用來(lái)實(shí)現(xiàn)rsem上不要有長(zhǎng)的排隊(duì)等待。

2.資源分派圖的化簡(jiǎn)。

可以通過(guò)對(duì)資源分派圖的約簡(jiǎn)，來(lái)判斷系統(tǒng)是否處于死鎖狀態(tài)．資源分派圖中的約簡(jiǎn)方法如下：

(1)尋覓一個(gè)非孤立且沒(méi)有請(qǐng)求邊的進(jìn)程結(jié)點(diǎn)pi,若無(wú)算法終止；(2)去除所有pi的分派邊使pi成為一個(gè)孤立結(jié)點(diǎn)；

(3)尋覓所有請(qǐng)求邊均可滿足的進(jìn)程pj,將pj的請(qǐng)求邊全部改為分派邊；(4)轉(zhuǎn)步驟(1)．

若算法終止時(shí)，所有結(jié)點(diǎn)均為孤點(diǎn)，則稱(chēng)資源分派圖是可以完全約簡(jiǎn)的，否則稱(chēng)為不可完全約簡(jiǎn)的．文獻(xiàn)已經(jīng)證明，系統(tǒng)處于死鎖狀態(tài)的充分必要條件是資源分派圖不可完全約簡(jiǎn)．這一結(jié)論稱(chēng)為死鎖定理．

定理：S為死鎖狀態(tài)的充分必要條件是S的資源分派圖不可完全約簡(jiǎn)．

對(duì)于問(wèn)題1，假設(shè)進(jìn)程p3申請(qǐng)資源類(lèi)r2中的一個(gè)實(shí)例，由于沒(méi)有空閑的資源實(shí)例，將增加一條申請(qǐng)邊(p3,r2)，形成圖5－2.此時(shí),出現(xiàn)了兩個(gè)環(huán)路:p1?r1?p2?r3?p3?r2?p1和p2?r3?p3?r2?p2.進(jìn)一步分析可以驗(yàn)證，此時(shí)系統(tǒng)已經(jīng)發(fā)生死鎖，且進(jìn)程p1、p2和p3都參與了死鎖.

對(duì)于問(wèn)題2，此圖中亦有一個(gè)環(huán)路:p1?r2?p4?r1?p1

然而并不存在死鎖.注意觀測(cè)p2可能會(huì)釋放資源類(lèi)r1中的一個(gè)資源實(shí)例,該資源實(shí)例可分派給進(jìn)程p3,從而使環(huán)路斷開(kāi).

綜合上述分析可以看出,假使資源分派圖中不存在環(huán)路,則系統(tǒng)中不存在死鎖;反之,假使資源分派圖中存在環(huán)路,則系統(tǒng)中可能存在死鎖,也可能不存在死鎖.

3.扔球問(wèn)題。

（1）有一個(gè)充分大的池子，兩個(gè)人分別向池中扔球，甲扔紅球，乙扔藍(lán)球，一次扔一個(gè)，開(kāi)始時(shí)池中有紅、藍(lán)球各一個(gè)，要求池中球滿足條件：1＜＝紅球數(shù)／藍(lán)球數(shù)＜＝2，用PV操作描述兩個(gè)進(jìn)程

信號(hào)量初值：r=1；b=0

扔紅扔藍(lán)

P(r)P(b)

扔一個(gè)紅扔一個(gè)藍(lán)

V(b)V(r)

V(r)

（2）一個(gè)充分大的池子，甲乙丙三人扔球，甲扔紅，乙扔藍(lán)，丙扔綠。開(kāi)始時(shí)池子中又紅綠藍(lán)球各一個(gè)。要求：池中球滿足要求：1<=紅/藍(lán)<=2，且藍(lán)<=綠<=紅+藍(lán)

信號(hào)量初值：r，b1，g=1；b2=0

扔紅扔藍(lán)扔綠P(r)P(b1)P(g)

扔一個(gè)紅P(b2)扔一個(gè)綠V(b1)扔一個(gè)藍(lán)V(b2)V(g)V(r)V(r)V(g)

4.最正確頁(yè)面尺寸算法例：在一個(gè)分頁(yè)系統(tǒng)中，設(shè)計(jì)算機(jī)的內(nèi)存大小為M，作業(yè)平均尺寸為

J，一個(gè)頁(yè)表項(xiàng)占x個(gè)存儲(chǔ)單位，問(wèn)最正確頁(yè)面尺寸P是多少？

每個(gè)進(jìn)程需要的頁(yè)數(shù)：J/P占用x·J/P個(gè)存儲(chǔ)單位

每個(gè)進(jìn)程的內(nèi)部碎片平均為：P/2

由頁(yè)表和內(nèi)部碎片帶來(lái)的總開(kāi)銷(xiāo)：x·J/P+P/2=M對(duì)P求導(dǎo)，令其等于0，得到方程：-x·(J/P^2)+1/2=0

由此得到最正確頁(yè)面尺寸公式P=2xJ^(1/2)

5.安全性檢測(cè)算法（已知流程圖，寫(xiě)代碼）。

數(shù)據(jù)結(jié)構(gòu)：

Available:array[1..m]ofinteger;//系統(tǒng)可用資源Claim:array[1..n,1..m]ofinteger;//進(jìn)程最大需求Allocation:array[1..n,1..m]ofinteger;//當(dāng)前分派Need:array[1..n,1..m]ofinteger;//尚需資源Request:array[1..n,1..m]ofinteger;//當(dāng)前請(qǐng)求

intWork[m];工作變量,記錄可用資源.

intFinish[n];工作變量,記錄進(jìn)程是否可進(jìn)行完.1.Work=Available；Finish=false；2.尋覓滿足如下條件的i:

(1)Finish[i]==false；(2)Need[i]≤Work[i]；假如不存在,則轉(zhuǎn)步驟4；

3.Work=Work+Allocation[i]；Finish[i]=true；轉(zhuǎn)步驟2

4.假如對(duì)于所有i,Finish[i]=true,則系統(tǒng)處于安全狀態(tài),否則處于擔(dān)心全狀態(tài).

Work:=Available;

T有滿足條件的j:Finish[j]=falseNeed[j]?Work

FT?j,finish[j]=true

FFinish[j]=true;

Work:=Work+Allocation[j]

安全

6.進(jìn)程的狀態(tài)及其轉(zhuǎn)移。

擔(dān)心全

運(yùn)行：進(jìn)程當(dāng)前處于運(yùn)行狀態(tài)。?就緒；進(jìn)程已準(zhǔn)備好運(yùn)行。

?阻塞；進(jìn)程等待某些事件發(fā)生（如I/O操作）后才能運(yùn)行。

?創(chuàng)立：進(jìn)程剛產(chǎn)生，但還未被操作系統(tǒng)提交到可運(yùn)行進(jìn)程池中。?消失：進(jìn)程被操作系統(tǒng)從可運(yùn)行進(jìn)程池中釋放。帶有掛起狀態(tài)的進(jìn)程狀態(tài)圖：