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

操作系統(tǒng)網(wǎng)絡(luò)技術(shù)教研室 胡寶芳期末考試題型單項(xiàng)選擇題（15分，15個(gè)）填空題（15分，15個(gè)空）判斷題（10分，10個(gè)）簡(jiǎn)答題（20分，4個(gè)）計(jì)算和綜合分析題（40分，5個(gè)）進(jìn)程的P、V操作wait、signal原語(yǔ)經(jīng)典進(jìn)程同步問(wèn)題信號(hào)量的設(shè)置：互斥、同步某車站售票廳，任何時(shí)刻最多可容納20名購(gòu)票者進(jìn)入，當(dāng)售票廳中少于20名購(gòu)票者時(shí)，則廳外的購(gòu)票者可立即進(jìn)入，否則需在外面等待。若把一個(gè)購(gòu)票者看作一個(gè)進(jìn)程，請(qǐng)回答下列問(wèn)題：（20分）

(1)用PV操作管理這些并發(fā)進(jìn)程時(shí)，應(yīng)怎樣定義信號(hào)量，寫(xiě)出信號(hào)量的初值以及信號(hào)量各種取值的含義。

(2)根據(jù)所定義的信號(hào)量，寫(xiě)出相應(yīng)的進(jìn)程，保證進(jìn)程能夠正確地并發(fā)執(zhí)行。

(3)若欲購(gòu)票者最多為n人，寫(xiě)出信號(hào)量可能的變化范圍(最大值和最小值)。（1）定義信號(hào)量S，初值為20S>0表示可繼續(xù)進(jìn)入售票廳的人數(shù)

S=0表示售票廳中已有20名購(gòu)票者

S<0表示等待進(jìn)入售票廳的人數(shù)（2）wait(mtex)；Wait（S）；進(jìn)入售票廳；signal（mtex），購(gòu)票，wait(mtex)；退出大廳，signal（S）；signal（mtex）(3)若欲購(gòu)票者最多為n人；20-n<S<20。桌上有一空盤(pán)，允許存放一只水果。爸爸可向盤(pán)中放蘋(píng)果，也可向盤(pán)中放桔子，兒子專等吃盤(pán)中的桔子，女兒專等吃盤(pán)中的蘋(píng)果。規(guī)定當(dāng)盤(pán)空時(shí)一次只能放一只水果供吃者取用，請(qǐng)用P、V原語(yǔ)實(shí)現(xiàn)爸爸、兒子、女兒三個(gè)并發(fā)進(jìn)程的同步。解：在本題中，應(yīng)設(shè)置三個(gè)信號(hào)量S、So、Sa，信號(hào)量S表示盤(pán)子是否為空，其初值為l；信號(hào)量So表示盤(pán)中是否有桔子，其初值為0；信號(hào)量Sa表示盤(pán)中是否有蘋(píng)果，其初值為0。同步描述如下：intS＝1;intSa＝0;intSo＝0;

father(){while(1){P(S);

將水果放入盤(pán)中;if（放入的是桔子）V(So);elseV(Sa);}}son(){while(1){

P(So);

從盤(pán)中取出桔子;V(S);

吃桔子;

｝

}daughter(){while(1){

P(Sa);

從盤(pán)中取出蘋(píng)果;V(S);

吃蘋(píng)果;

｝｝若盤(pán)子里有n個(gè)蘋(píng)果和n個(gè)桔子，女兒從盤(pán)子里拿蘋(píng)果吃，兒子從盤(pán)子里拿桔子，每次只能拿一個(gè)，寫(xiě)出女兒和兒子的進(jìn)程把學(xué)生和監(jiān)考老師都看作進(jìn)程,學(xué)生有N人,教師1人.考場(chǎng)門(mén)口每次只能進(jìn)出一個(gè)人,進(jìn)考場(chǎng)原則是先來(lái)先進(jìn).當(dāng)N個(gè)學(xué)生都進(jìn)入考場(chǎng)后,教師才能發(fā)卷子.學(xué)生交卷后可以離開(kāi)考場(chǎng).教師要等收上來(lái)全部卷子并封裝卷子后才能離開(kāi)考場(chǎng).(1)問(wèn)共需設(shè)置幾個(gè)進(jìn)程?(2)試用P、V操作解決上述問(wèn)題中的同步和互斥關(guān)系.Var

mutex,s,paper:semaphore:=1,0,0

int

scount：=0學(xué)生Si：{wait(mutex);進(jìn)來(lái)Scount=Scount+1;

signal(mutex);ifscount>=nthensignal(S)

wait(paper);//等待發(fā)試卷

做題，交卷wait(mutex);Scount=Scount-1;

signal(mutex);ifscount<=0thensignal(S)}教師{wait(S);發(fā)試卷；Fori:=1tondosignal(paper)……收試卷；wait(S);封試卷，離開(kāi)考場(chǎng)；}處理機(jī)調(diào)度假設(shè)在單道批處理環(huán)境下有四個(gè)作業(yè)，已知它們進(jìn)入系統(tǒng)的時(shí)間、估計(jì)運(yùn)行時(shí)間應(yīng)用先來(lái)先服務(wù)、最短作業(yè)優(yōu)先和最高響應(yīng)比優(yōu)先作業(yè)調(diào)度算法，分別計(jì)算出作業(yè)的平均周轉(zhuǎn)時(shí)間和帶權(quán)的平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間帶權(quán)的平均周轉(zhuǎn)時(shí)間應(yīng)用先來(lái)先服務(wù)112.54.975最短作業(yè)優(yōu)先953.25最高響應(yīng)比優(yōu)先102.53.775銀行家算法設(shè)有五個(gè)進(jìn)程P0，P1，P2，P3，p4共享一組資源A，B，C，假定在某個(gè)時(shí)刻他們的資源分配狀態(tài)如下所示：（15分）已分配的資源最大需求量 剩余資源

A B C A B C ABCP0 01 0 7 5 3332P1 20 0 3 2 2 P2 30 2 9 0 2 P3 21 1 2 2 2 P4 00 2 4 3 3問(wèn)題:此狀態(tài)是否為安全狀態(tài)？如果是,則找出安全序列。在此基礎(chǔ)上P1申請(qǐng)（1，0，2）能否分配？為什么？P4申請(qǐng)（3，3，0）能否分配？為什么？P0申請(qǐng)（0，2，0）能否分配？為什么？已分配的資源最大需求量 剩余資源

A B C A B C ABCP0 01 0 7 5 3 332P1 20 0 3 2 2 P2 30 2 9 0 2 P3 21 1 2 2 2 P4 00 2 4 3 3答案：此狀態(tài)是安全狀態(tài)，安全序列是P1，P2，P3，P4，P0。在此基礎(chǔ)上P1申請(qǐng)（1，0，2）能分配，需寫(xiě)出分配序列P4申請(qǐng)（3，3，0）不能分配。P0申請(qǐng)（0，2，0）不能分配。內(nèi)存地址變換在分頁(yè)存儲(chǔ)管理系統(tǒng)中，有一作業(yè)大小為4頁(yè)，頁(yè)長(zhǎng)為1K，頁(yè)表如下：求出邏輯地址0A5C所對(duì)應(yīng)的物理地址。（要求寫(xiě)出計(jì)算過(guò)程）頁(yè)號(hào)塊號(hào)051102437125CH請(qǐng)求分頁(yè)有個(gè)一虛擬存儲(chǔ)系統(tǒng),每個(gè)進(jìn)程在內(nèi)存占有3頁(yè)數(shù)據(jù)區(qū),

剛開(kāi)始時(shí)數(shù)據(jù)區(qū)為空。有以下訪頁(yè)序列:2、3、4、5、3、4、1、2、3、5、1、4、2、4

試給出下列情形下的缺頁(yè)次數(shù):

(1)系統(tǒng)采用先進(jìn)先出(FIFO)淘汰算法.

(2)系統(tǒng)采用最近最少使用(LRU)淘汰算法.(3)系統(tǒng)采用最佳淘汰算法.2、3、4、5、3、4、1、2、3、5、1、4、2、4

FCFS23453412351424LRU23453412351424最佳23453412351424磁盤(pán)調(diào)度假設(shè)磁盤(pán)有200個(gè)磁道，磁盤(pán)請(qǐng)求隊(duì)列中是一些隨機(jī)請(qǐng)求，它們按照到達(dá)的次序分別處于98、183、37、122、14、124、65、67號(hào)磁道上，當(dāng)前磁頭在53號(hào)磁道上，并向磁道號(hào)減小的方向上移動(dòng)。請(qǐng)給出按FCFS，SSTF，SCAN及CSCAN算法進(jìn)行磁盤(pán)調(diào)度時(shí)滿足請(qǐng)求的次序，并計(jì)算出它們的平均尋道長(zhǎng)度。FCFS當(dāng)前磁道53下一個(gè)磁道移動(dòng)距離98451831853714612285144081241106559672平均尋道：80SSTF當(dāng)前磁道53下一個(gè)磁道移動(dòng)距離65126723730141398841