操作系統(tǒng)應(yīng)用題解答

1、操作系統(tǒng)應(yīng)用題（解答）部門：xxx時問：xxx整理范文，僅供參考，可下載自行編輯1.設(shè)有一臺計算機(jī)，有兩條I/O通道，分別接一臺卡片輸入機(jī)和一臺打印機(jī)卡片機(jī)把一疊卡片逐一輸入到緩沖區(qū)B1中，加工處理后在搬到緩沖區(qū)B2中,弁在打印機(jī)上印出，問：系統(tǒng)要設(shè)幾個進(jìn)程來完成這個任務(wù)？各自的工作是什么？這些進(jìn)程間有什么樣的相互制約關(guān)系？用P、V操作寫出這些進(jìn)程的同步算法。解：系統(tǒng)可設(shè)三個進(jìn)程來完成這個任務(wù)：R進(jìn)程負(fù)責(zé)從卡片輸入機(jī)上讀入卡片信息，輸入到緩沖區(qū)B1中；C進(jìn)程負(fù)責(zé)從緩沖區(qū)B1中取出信息，進(jìn)行加工處理，之后將結(jié)果送到緩沖區(qū)B2中；P進(jìn)程負(fù)責(zé)從緩沖區(qū)B2中取出信息，并在打印機(jī)上印出。R進(jìn)程受C進(jìn)程影

2、響，B1放滿信息后R進(jìn)程要等彳f等C進(jìn)程將其中信息全部取走，才能繼續(xù)讀入信息；C進(jìn)程受R進(jìn)程和P進(jìn)程的約束：B1中信息放滿后C進(jìn)程才可從中取出它們，且B2被取空后C進(jìn)程才可將加工結(jié)果送入其中；P進(jìn)程受C進(jìn)程的約束：B2中信息放滿后P進(jìn)程才可從中取出它們，進(jìn)行打印。信號量含義及初值：B1full緩沖區(qū)B1滿，初值為0;<B1full=1表示B1滿）B1empty緩沖區(qū)B1空，初值為1;<B1empt尸1表示B1空）B2full緩沖區(qū)B2滿，初值為0;<B2full=1表示B21滿）B2empty-緩沖區(qū)B2空，初值為1;<B2empt尸1表示B2空）R進(jìn)程C進(jìn)程P進(jìn)程b5

3、E2RGbCAP下:計算邏輯地址<2,15）,<0,60）,<3,18）的絕對地址是多少？注：括號中第一個元素為段號，第二個元素為段內(nèi)地址。解：段式存儲管理的地址轉(zhuǎn)換過程為：<1）根據(jù)邏輯地址中的段號查段表的相應(yīng)欄目；<2）根據(jù)段內(nèi)地址<段長度，檢查地址是否越界；<3）若不越界，則絕對地址=該段的主存起始地址+段內(nèi)地址。邏輯地址<2,15)查段表得段長度為20,段內(nèi)地址15<20,地址不越界，段號2查表得段首地址為480,于是絕又t地址為480+15=496邏輯地址<0,60)查段表得段長度為40,段內(nèi)地址60>40,地址越界，

4、系統(tǒng)發(fā)出“地址越界”中斷。邏輯地址<3,18)查段表得段長度為20,段內(nèi)地址18<20,地址不越界，段號3查表得段首地址為370,于是絕對地址=370+18=38&DXDiTa9E3d3.若干個等待訪問磁盤者依次要訪問的柱面為20,44,40,4,80,12,76,假設(shè)每移動一個柱面需要3毫秒時間，移動臂當(dāng)前位于40號柱面，請按下列算法分別計算為完成上述各次訪問總共花費(fèi)的尋找時間。RTCrpUDGiT<1)先來先服務(wù)算法；< 2)最短尋找時間優(yōu)先算法。解<1)3毫秒X292=876毫秒<2)3毫秒X120=360毫秒< 注：各算法使移動臂的移動

5、次序和移動的柱面數(shù)如下：< 1)402044404-801276< 20)<24)<4)<36)<76)<68)<64)共移動292柱面< 2)404420124-7680< 4)<24)<8)<8)<72)<4)共移動120柱面4 .某系統(tǒng)中有10臺打印機(jī)，有三個進(jìn)程P1,P2,P3分別需要8臺，7臺和4臺。若P1,P2,P3已申請到4臺，2臺和2臺。試問：按銀行家算法能安全分配嗎？請說明分配過程。5PCzVD7HxA解：系統(tǒng)能為進(jìn)程P3分配二臺打印機(jī)。因為盡管此時10臺打印機(jī)已分配給進(jìn)程P14臺，P2

6、2臺和P34臺，全部分配完，但P3已分配到所需要的全部4臺打印機(jī)，它不會對打印機(jī)再提出申請，所以它能順利運(yùn)行下去，能釋放占用的4臺打印機(jī)，使進(jìn)程P1,P2均可能獲得乘余的要求4臺和5臺，按銀行家算法是安全的。jLBHrnAILg5 .用PV操作解決讀者寫者問題的正確程序如下：beginS,Sr:Semaphore。rc:integer。S:=1。Sr:=1。rc:=0。cobeginPROCESSReaderi(i=1,2>beginP(Sr>rc:=rc+1。ifrc=1thenP(S>。V(Sr>。readfile。P(Sr>。rc:=rc-1ifrc=0th

7、enV(S>。V(Sr>。end。PROCESSWriterj(j=1,2>beginP(S>。Writefile。V(S>end。coend。end。請回答：<1）信號量Sr的作用；<2）程序中什么語句用于讀寫互斥，寫寫互斥；<3）若規(guī)定僅允許5個進(jìn)程同時讀怎樣修改程序？XHAQX74J0X解<1）Sr用于讀者計數(shù)rc的互斥信號量；<2）ifrc=1thenP<S）中的P<S）用于讀寫互斥，寫者進(jìn)程中的P<S）用于寫寫互斥，讀寫互斥。LDAYtRyKfE<3）程序中增加一個信號量S5,初彳直為5,P<S

8、5）語句加在讀者進(jìn)程P<Sr）之前，V<S5語句加在t者進(jìn)程第2個V<Sr）之后。Zzz6ZB2Ltk6 .判斷下面的同步問題的算法是否正確？若有錯，請指出錯誤原因并予以改正。設(shè)A、B兩進(jìn)程共用一個緩沖區(qū)Q,A向Q寫入信息，B則從Q讀出信息，算法框圖如圖所示。進(jìn)程AV(S>進(jìn)程B（S>從Q讀出信息注：信號量S的初值為0解：這個算法不對。因為AB兩進(jìn)程共用一個緩沖區(qū)Q如果A先運(yùn)行，且信息數(shù)量足夠多，那么緩沖區(qū)Q中的信息就會發(fā)生后面的沖掉前面的，造成信息丟失，B就不能從Q中讀出完整的信息。dvzfvkwMI1進(jìn)行改正：A、B兩進(jìn)程要同步使用緩沖區(qū)Q。為此，設(shè)立兩個信號

9、量：empty表示緩沖區(qū)Q為空，初值為1;full表示緩沖區(qū)Q為滿，初值為0。算法框圖如圖所示。A.進(jìn)程B進(jìn)程rIfP（empty>IP（full>向Q寫入信息從Q中t,出信息V（full>IV（empty>7 .有三個用戶進(jìn)程AB和C,在運(yùn)行過程中都要使用系統(tǒng)中的一臺打印機(jī)輸出計算結(jié)果。試說明AB、C進(jìn)程之間存在什么樣的制約關(guān)系？為保證這三個進(jìn)程能正確地打印出各自的結(jié)果，請用信號量和P、V操作寫出各自的有關(guān)申請、使用打印機(jī)的代碼。要求給出信號量的含義和初值。rqyn14ZNXI解：(1>A、B、C三個進(jìn)程之間存在互斥的制約關(guān)系。因為打印機(jī)屬于臨界資源，必須一個進(jìn)

10、程使用完之后另一個進(jìn)程才能使用。EmxvxOtOco<2)mutex：用于互斥的信號量，初值為1。各進(jìn)程的代碼如下：進(jìn)程A進(jìn)程B進(jìn)程CP(mutex>P(mutex>P(mutex>申請打印機(jī)申請打印機(jī)申請打印機(jī)使用打印機(jī)使用打印機(jī)使用打印機(jī)V(mutex>V(mutex>V(mutex>8.假定在某移動臂磁盤上，剛剛處理了訪問75號柱面的請求，目前正在80號柱面讀信息，并且有下述請求序列等待訪問磁盤：SixE2yXPq5請求序列：12345678欲訪問柱面號：16040190188905832102試用：(1>電梯調(diào)度算法(2>最短尋找時

11、間優(yōu)先算法分別列出實際處理上述請求的次序。解(1>電梯調(diào)度算法：由”剛剛處理了訪問75號柱面的請求，目前正在80號柱面讀信息”可知：初始磁頭前進(jìn)的方向是：”從小到大"6ewMyirQFL5814362790102160188190584032(2最短尋找時間優(yōu)先算法：處理次序為：58627143901025840321601881909.有三個進(jìn)程P1,P2和P3并發(fā)工作。進(jìn)程P1需用資源S3和S1;進(jìn)程P2需用資源S1和S2;進(jìn)程P3需用資源S2和S&回答：kavU42VRUs(1若對資源分配不加限制，會發(fā)生什么情況？為什么？(2為保證進(jìn)程正確工作，應(yīng)采用怎樣的資源分

12、配策略？為什么？訕：(1可能會發(fā)生死鎖例如：進(jìn)程P1,P2和P3分別獲得資源S3,S1和S2后再繼續(xù)申請資源時都要等待，這是循環(huán)等待。(或進(jìn)程在等待新源時均不釋放已占資源(2可有幾種答案：A.采用靜態(tài)分配由于執(zhí)行前已獲得所需的全部資源，故不會出現(xiàn)占有資源又等待別的資源的現(xiàn)象(或不會出現(xiàn)循環(huán)等待資源現(xiàn)象。y6V3ALoS89或B.采用按序分配不會出現(xiàn)循環(huán)等待資源現(xiàn)象?；駽.采用銀行家算法因為在分配時，保證了系統(tǒng)處于安全狀態(tài)。10 .某車站售票廳，任何時刻最多可容納20名購票者進(jìn)入，當(dāng)售票廳中少于20名購票者時，則廳外的購票者可立即進(jìn)入，否則需在外面等待。若把一個購票者看作一個進(jìn)程，請回答下列問題

13、：M2ub6vSTnP(1用PV操作管理這些并發(fā)進(jìn)程時，應(yīng)怎樣定義信號量，寫出信號量的初值以及信號量各種取值的含義。(2根據(jù)所定義的信號量，把應(yīng)執(zhí)行的PV操作填入下述方框中，以保證進(jìn)程能夠正確地并發(fā)執(zhí)行。COBEGINPROCESSPI(12,begin;進(jìn)入售票廳；購票；退出；end;COEND(3若欲購票者最多為n個人，寫出信號量可能的變化范圍(最大值和最小值。解(1定義一信號量S,初始值為20。意義：S0S的值表示可繼續(xù)進(jìn)入售票廳的人數(shù)S=0表示售票廳中已有20名顧客(購票者S0|S|的值為等待進(jìn)入售票廳的人數(shù)(2上框為P(S下框為V(S(3S的最大值為20S的最小值為20n注：信號量的

14、符號可不同(如寫成t，但使用時應(yīng)一致(即上述的s全應(yīng)改成t。11 .有兩個進(jìn)程P1和P2,它們執(zhí)行的過程如下：P1:10秒CPLB作、20秒I/O操作設(shè)備1)、5秒CPLB作、10秒I/O操作設(shè)備2)、5秒CPl作、結(jié)束0YujCfmUCwP1:15秒I/O操作設(shè)備1)、10秒CPU1作、15秒I/O操作設(shè)備2)、10秒CPUt作、結(jié)束eUts8ZQVRd(1) 如果進(jìn)程P1和P2順序執(zhí)行，請畫出進(jìn)程P1和P2執(zhí)行情況圖；(2) 如果進(jìn)程P1和P2并發(fā)執(zhí)行，請畫出進(jìn)程P1和P2執(zhí)行情況圖；(3) 分別計算在1)和2)情況下，CPU的利用率、設(shè)備1和設(shè)備2的利用率。解：(1P1和P2順序執(zhí)行P1

15、:'L-CPUI/O(DEV1CPI/O(DECP01030354550sQsAEJkW5TP2:I/O(DEV1>L-GPUI/O(DEV2>CPU50657590100GMsIasNXkA(2P1和P2并發(fā)執(zhí)行CPU(PCPU(PCPU(ICPU(P2CPU(PI/O(DEV1>_I/O(DEV>(P1I/O(DEV2>I/O(DEV010152535405055TIrRGchYzg(3>在情況<1)下，CPU勺利用率=40/100=40%備1的利用率=35/100=35%設(shè)備2的利用率=25/100=25%在情況<2)下，CPU勺利

16、用率=40/55=73股備1的利用率=35/55=64%設(shè)備2的利用率=25/55=45%12 .一個程序P的用戶空間為16K,存儲管理采用請求式分頁系統(tǒng)，每個頁面大小為2K,存在以下的頁表：頁框號后效位121310100211510081其中，有效位=1表示頁面在內(nèi)存；0表示頁面不在內(nèi)存。請將虛地址0X060C,0x1502,0x1d71,0x2c27,0x4000轉(zhuǎn)換為物理地址。答：用戶地址空間共用14bit表示.范圍為:0x00000x3FFF.超過這個范圍即為"越界”0X060C:1548+12*2048=0x660C0x15020x65020x1d71:缺頁0x2c27:0

17、x14270x4000:越界13 .有一個文件系統(tǒng)，根目錄常駐內(nèi)存，目錄文件采用鏈接式，每個磁盤塊存放10個下級文件的描述，最多存放40個下級文件(最多涉及到4個盤塊>,若下級文件為目錄文件，則上級目錄指向該目錄文件的第一塊，否則指向普通文件的文件控制塊。普通文件采用二級索引形式，文件控制塊中給出12個磁盤塊地址，前10個磁盤塊地址指出前10頁的物理地址，第11個磁盤塊地址指向一級索引表，一級索引表給出256個磁盤塊地址，即指出該文件第10頁至第256頁的地址，第12個磁盤塊地址指向二級索引表，二級索引表中指出256個一級索引表的地址。（1該文件系統(tǒng)中的普通文件最大可有多少頁?7EqZc

18、WLZNX（2若要讀文件/A/D/K/Q中的某一頁，最少要啟動磁盤幾次？最多要啟動磁盤幾次？答：1）一個文件的所有塊可以通過下面三種途徑找到：直接通過FCB找到前10塊，通過一級索引找到256塊，通過二級索引找到256*256塊，所以一個文件最大可以有10+256+2562塊lzq7IGf02E因為目錄文件果用攫搔形式.一個域盤塊存放I。個下級文件的描逑.一個目錄下星塞林欣的個卜線文件.故一個|呆£件城各3門個列理塊,根“系文件已在內(nèi)存，故歸必啟動梗廉讀入它.最小蝠居根目球文怦“目日文件1次1忒D目讀文件1次1次K目錄文件1忒1次Q文件控制跳1次1次Q文忖靈一應(yīng)1次3次共5黑13/最

19、壞情況是：每次讀取目錄描述信息的時候都在最后一個塊找到下級的目錄或文件，所以要找到Q文件的FCB至少要讀取A的第一塊，DG二個目錄項的所有四個塊，再讀取Q的FCB總共要1+4*2+1=10次啟動硬盤。找到FCB后再讀取該文件頁所在的塊，如果這一塊在前10塊之列，那么在啟動一次硬盤就可以找到這一塊，如果這一塊在最后一塊，則可能需要通過二級索引找到這一塊，這總共需要讀取二級索引和最后一塊共2+1次讀取硬盤。zvpgeqJ1hk14. 一個系統(tǒng)中存在某類資源m個，被n個進(jìn)程共享。資源的分配和釋放必須一個一個進(jìn)行，請證明在以下兩個條件下不會發(fā)生死鎖：NrpoJac3v1每個進(jìn)程需要資源的最大數(shù)在1m之

20、間；所有進(jìn)程需要的資源總數(shù)小于m+n證明：假設(shè)進(jìn)程Pi(0<i<n+1>需要的資源數(shù)為Ri,則R1+R2+.+Rn<m+n(1>1 <=Ri<=m(2>假設(shè)進(jìn)程已經(jīng)分配到的置源為Ai(0<i<n+1>,則Ai<=Ri假設(shè)當(dāng)前發(fā)生了死鎖，則A1+A2+.+An=mAi<Ri(0<i<n+1>也就是Ai+1<=Ri則A1+A2+-.+An+n<=R1+R2+,+Rn即m+n<=R1+R2+.+Rn和<1)矛盾，死鎖不成立。15. 一個請求式分頁存儲系統(tǒng)，頁表存放在內(nèi)存：訪問一次內(nèi)

21、存需要100ns如果僅調(diào)入一個頁面，需要花費(fèi)8ms吶存有空頁面，或需要進(jìn)行頁面置換，單被置換的頁面沒有修改過)；如果調(diào)入一個頁面同時需要進(jìn)行被置換頁面的寫出，則需要20ms假設(shè)頁面被修改的比例是60%請問，缺頁率必須控制在多少以下，才能使得EAT<200ns?解：假設(shè)缺頁率為f_rate,則，EAT=(1-f_rate>*100+f_rate*(40%*8000+60%*20000>如EAT<200,則，（1-f_rate>*100+f_rate*（40%*8000+60%*20000><200100-100*f_rate+15200*f_rate&l

22、t;200151*f_rate<1f_rate<1/151即缺頁率小于0.66%。16. 一個文件有100個磁盤塊，假設(shè)文件控制塊在內(nèi)存<如果文件采用索引分配（indexedallocation>,索引表也在內(nèi)存）。在下列情況下，請計算在contiguous,linked,indexed（single-level>三種分配方式下，分別需要多少次磁盤I/O操作？<每讀出或?qū)懭胍粋€磁盤塊都需要一次磁盤I/O操作）（10%>1nowfTG4KI假設(shè)在contiguous分配方式下，文件頭部無空閑的磁盤塊，但文件尾部有空閑的磁盤塊。假設(shè)要增加的塊信息存放在內(nèi)存

23、中。fjnFLDa5Zo在文件開始處添加一個磁盤塊；在文件結(jié)尾處添加一個磁盤塊；在文件中間刪除第50塊磁盤塊；<假設(shè)磁盤塊編號從099）在文件第50塊前添加一個磁盤塊；<假設(shè)磁盤塊編號從099）解：在文件開始處添加一個磁盤塊：連續(xù)：201/鏈接：1/索引：1在文件結(jié)尾處添加一個磁盤塊：連續(xù)：1/鏈接：101/索引：1在文件中間刪除一個磁盤塊：連續(xù)：48*2+1+1=98/鏈接：52/索引：0在文件中間添加一個磁盤塊：連續(xù)：101/鏈接：52/索引：117. 一個操作系統(tǒng)有20個進(jìn)程，競爭使用30個同類資源，申請方式是逐個進(jìn)行，一旦某個進(jìn)程獲得了它的全部資源，就馬上歸還所有的資源，每

24、個進(jìn)程最多使用30,最少使用一個資源。20個進(jìn)程需要的資源總數(shù)小于50。如果僅考慮這類資源，系統(tǒng)會產(chǎn)生死鎖嗎？請說明理由。tfnNhnE6e5答:設(shè)max(i>表示第i個進(jìn)程的最大資源需求量，need(i>表示第i個進(jìn)程還需要的資源量，alloc(i>表示第i個進(jìn)程已分配的資源量。由題中所給條件可知：max(1>+max(20>=(need(1>+need(20>>+(alloc(1>+alloc(20>><50HbmVN777sL如果在這個系統(tǒng)中發(fā)生了死鎖，那么一方面30個資源R應(yīng)該全部分配出去，即<反證法)alloc(1>+alloc(20>=30V7l4jRB8Hs另一方面所有進(jìn)程將陷入無限等待狀態(tài)。由上述兩式可得：need(1>+need(20><205鍵)上式表示死鎖