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

后再裝操作系統(tǒng)。后再裝操作系統(tǒng)。址空間的大小可以不受任何限制。址空間的大小照舊不受任何限制。4.答：在懇求式分頁(yè)系統(tǒng)中，增加內(nèi)存幀不肯定可以降低缺頁(yè)中斷率。5.假設(shè)系統(tǒng)處于擔(dān)憂全狀態(tài)，則肯定發(fā)生了死鎖。答OPT頁(yè)面替換算法是堆棧型算法？證明如下：LRU算法滿足，n<Lt時(shí)，Bt(n)(包含于符號(hào))Bt(n+1)n>=Lt時(shí)，Bt(n)=Bt(n+1)n表示安排給程序的實(shí)頁(yè)數(shù)，Bt(n)t時(shí)刻在n個(gè)實(shí)頁(yè)中的虛頁(yè)集合，Ltt時(shí)刻不同虛n個(gè)主存頁(yè)面，那么在t時(shí)刻，這n個(gè)主存頁(yè)面都是最近使用過(guò)的頁(yè)面。假設(shè)再給這個(gè)程序多安排一t時(shí)刻，這n＋1個(gè)主存頁(yè)面也都是最近使用過(guò)的頁(yè)面。因此，在這n＋1個(gè)主存頁(yè)面中必定包含了前面的n個(gè)主存頁(yè)面。所以，opt算法是堆棧型算法。讀著優(yōu)先、寫(xiě)者優(yōu)先〔代碼。讀者優(yōu)先假設(shè)有讀者來(lái)時(shí)，①無(wú)讀者和寫(xiě)者，讀者可以讀；②如有寫(xiě)者等待，但有其他讀者正在讀，則讀者可以讀；③有寫(xiě)者寫(xiě)，讀者則等待Varwsem:semaphore;(initialvalue:1)Writer： <writeoperation>while(1){ V(wsem);<otheraction> }P(wsem); intreadCount=0;semaphorewsem=1;semaphoremutex=1;reader：while(1){<otheractions>P(mutex);寫(xiě)者優(yōu)先假設(shè)有寫(xiě)者來(lái)時(shí)，①無(wú)讀者，寫(xiě)者可以寫(xiě)；②如有讀者正在讀，則讀者等待；③有其他寫(xiě)者正在寫(xiě)，寫(xiě)者則等待。intwriteCount=0;semaphorewsem,rsem=1;semaphoremutexY=1;writer：while(1){<otheractions>P(mutexY);writeCount=writeCount+1;if(writeCount==1)P(rsem);V(mutexY);P(wsem);<writeoperations>V(wsem);P(mutexY);writeCount=writeCount-1;if(writeCount==0)V(rsem);V(mutex);

readCount=readCount+1;if(readCount==1)P(wsem);V(mutex);<readoperations>P(mutex);readCount=readCount-1;if(readCount==0)V(wsem);V(mutex);}<otheractions>P(mutex);P(rsem);P(mutexX);readCount=readCount+1;if(readCount==1)P(wsem);V(mutexX);V(rsem);V(mutex);<readoperations>P(mutexX);readCount=readCount-1;if(readCount==0)V(wsem);V(mutexX);}}intreadCount=0;semaphorewsem,rsem=1;semaphoremutexX,mutex=1;reader：while(1){變量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ì)等待。資源安排圖的化簡(jiǎn)。可以通過(guò)對(duì)資源安排圖的約簡(jiǎn)，來(lái)推斷系統(tǒng)是否處于死鎖狀態(tài)．資源安排圖中的約簡(jiǎn)方法如下：查找一個(gè)非孤立且沒(méi)有懇求邊的進(jìn)程結(jié)點(diǎn)pi,假設(shè)無(wú)算法完畢；(2)pipi成為一個(gè)孤立結(jié)點(diǎn)；(3)pj,pj的懇求邊全部改為安排邊；(4)轉(zhuǎn)步驟(1)．假設(shè)算法完畢時(shí)，全部結(jié)點(diǎn)均為孤點(diǎn)，則稱資源安排圖是可以完全約簡(jiǎn)的，否則稱為不行完全約簡(jiǎn)的．文獻(xiàn)已經(jīng)證明，系統(tǒng)處于死鎖狀態(tài)的充分必要條件是資源安排圖不行完全約簡(jiǎn)．這一結(jié)論稱為死鎖定理．定理：SS的資源安排圖不行完全約簡(jiǎn)．1p3r2中的一個(gè)實(shí)例，由于沒(méi)有空閑的資源實(shí)例，將增加一條申請(qǐng)邊(p3,r2)，形成圖5－2.此時(shí),消滅了兩個(gè)環(huán)路:p1r1p2r3p3r2p1p2r3p3r2p2.進(jìn)一步分析可以驗(yàn)證，此時(shí)系統(tǒng)已經(jīng)發(fā)生死鎖，且p1、p2p3都參與了死鎖.2，此圖中亦有一個(gè)環(huán)路:p1r2p4r1p1然而并不存在死鎖.p2r1中的一個(gè)資源實(shí)例,該資源p3,從而使環(huán)路斷開(kāi).綜合上述分析可以看出,假設(shè)資源安排圖中不存在環(huán)路,則系統(tǒng)中不存在死鎖;反之,假設(shè)資源安排圖中存在環(huán)路,則系統(tǒng)中可能存在死鎖,也可能不存在死鎖.扔球問(wèn)題。有一個(gè)充分大的池子，兩個(gè)人分別向池中扔球，甲扔紅球，乙扔藍(lán)球，一次扔一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)一個(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)最正確頁(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ì)P0，得到方程：-x·(J/P^2)+1/2=0由此得到最正確頁(yè)面尺寸公式P=2xJ^(1/2)安全性檢測(cè)算法〔流程圖，寫(xiě)代碼。數(shù)據(jù)構(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)前懇求intWork[m];工作變量,記錄可用資源.intFinish[n];工作變量,記錄進(jìn)程是否可進(jìn)展完.Work=Available；Finish=false；i:Finish[i]==false；(2)Need[i]≤Work[i]；假設(shè)不存在,4；Work=Work+Allocation[i]；Finish[i]=true；2i,Finish[i]=true,則系統(tǒng)處于安全狀態(tài),否則處于擔(dān)憂全狀態(tài).Work:=Available;T 有滿足條件的j:Finish[j]=falseNeed[j]Work

FTFTj,finish[j]=trueFinish[j]=true;Work:=Work+Allocation[j]安全 擔(dān)憂全進(jìn)程的狀態(tài)及其轉(zhuǎn)移 。運(yùn)行：進(jìn)程當(dāng)前處于運(yùn)行狀態(tài)。就緒；進(jìn)程已預(yù)備好運(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)圖：帶有一個(gè)