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

1、1. 設(shè)有一臺計算機，有兩條I/O通道，分別接一臺卡片輸入機和一臺打印機?？ㄆ瑱C把一疊卡片逐一輸入到緩沖區(qū)B1中，加工處理后在搬到緩沖區(qū)B2中，并在打印機上印出，問：系統(tǒng)要設(shè)幾個進程來完成這個任務(wù)？各自的工作是什么？這些進程間有什么樣的相互制約關(guān)系？用P、V操作寫出這些進程的同步算法。 解： 系統(tǒng)可設(shè)三個進程來完成這個任務(wù)：R進程負責(zé)從卡片輸入機上讀入卡片信息，輸入到緩沖區(qū)B1中；C進程負責(zé)從緩沖區(qū)B1中取出信息，進行加工處理，之后將結(jié)果送到緩沖區(qū)B2中；P進程負責(zé)從緩沖區(qū)B2中取出信息，并在打印機上印出。R進程受C進程影響，B1放滿信息后R進程要等待等C進程將其中信息全部取走，才能繼續(xù)讀入信

2、息；C進程受R進程和P進程的約束：B1中信息放滿后C進程才可從中取出它們，且B2被取空后C進程才可將加工結(jié)果送入其中；P進程受C進程的約束：B2中信息放滿后P進程才可從中取出它們,進行打印。信號量含義及初值：B1full 緩沖區(qū)B1滿，初值為0；（B1full1表示B1滿）B1empty緩沖區(qū)B1空，初值為1；（B1empty1表示B1空）B2full 緩沖區(qū)B2滿，初值為0；（B2full1表示B21滿）B2empty緩沖區(qū)B2空，初值為1；（B2empty1表示B2空） R進程 C進程 P進程P(B2full)從B2中取出信息進行打印V(B2empty)P(B1full)P(B2empty

3、)取B1送入B2V(B1empty)V(B2full)P(B1empty)輸入信息寫入B1V(B1full)2、現(xiàn)有一個作業(yè)，在段式存儲管理的系統(tǒng)中已為其主存分配，建立的段表內(nèi)容如下：段號主存起始地址（段基址）段長度012040176030248020337020計算邏輯地址（2，15），（0，60），（3，18）的絕對地址是多少？注：括號中第一個元素為段號，第二個元素為段內(nèi)地址。解：段式存儲管理的地址轉(zhuǎn)換過程為：（1）根據(jù)邏輯地址中的段號查段表的相應(yīng)欄目；（2）根據(jù)段內(nèi)地址<段長度，檢查地址是否越界；（3）若不越界，則絕對地址=該段的主存起始地址+段內(nèi)地址。邏輯地址（2，15）查段表得

4、段長度為20，段內(nèi)地址15<20，地址不越界，段號2查表得段首地址為480，于是絕對地址為480+15=495。邏輯地址（0，60）查段表得段長度為40，段內(nèi)地址60>40，地址越界，系統(tǒng)發(fā)出“地址越界”中斷。邏輯地址（3，18）查段表得段長度為20，段內(nèi)地址18<20，地址不越界，段號3查表得段首地址為370，于是絕對地址=370+18=388。 3若干個等待訪問磁盤者依次要訪問的柱面為20，44，40，4，80，12，76，假設(shè)每移動一個柱面需要3毫秒時間，移動臂當(dāng)前位于40號柱面，請按下列算法分別計算為完成上述各次訪問總共花費的尋找時間。  （1）先來先服務(wù)算

5、法；   （2）最短尋找時間優(yōu)先算法。解（1）3毫秒×292=876毫秒 （2）3毫秒×120=360毫秒 （注：各算法使移動臂的移動次序和移動的柱面數(shù)如下： （1）40 20 44 40 4 80 12 76 （20） （24）（4） （36） （76）（68） （64） 共移動292柱面 （2）40 44 20 12 4 76 80 （4） （24）（8） （8） （72）（4） 共移動120柱面4某系統(tǒng)中有10臺打印機，有三個進程P1，P2，P3分別需要8臺，7臺和4臺。若P1，P2，P3已申請到4臺，2臺和2臺。試問：按銀行家算法能安全分配嗎？請說明分配過

6、程。解：系統(tǒng)能為進程P3分配二臺打印機。因為盡管此時10臺打印機已分配給進程P1 4臺，P22臺和P34臺，全部分配完，但P3已分配到所需要的全部4臺打印機，它不會對打印機再提出申請，所以它能順利運行下去，能釋放占用的4臺打印機，使進程P1，P2均可能獲得乘余的要求4臺和5臺，按銀行家算法是安全的。5用PV操作解決讀者寫者問題的正確程序如下： begin S, Sr: Semaphore; rc: integer;       S:=1; Sr:=1; rc:=0; cobegin PROCESS Reader i ( i=1,2)  

7、;       begin P(Sr)         rc:=rc+1;         if rc=1 then P(S);         V(Sr);         read file;      &

8、#160;  P(Sr);         rc:=rc-1       if rc=0 thenV(S);       V(Sr);       end ;     PROCESS Writer j (j=1,2)     begin P(S);      

9、     Write file;           V(S)end;   coend ; end; 請回答：（1）信號量 Sr的作用；（2）程序中什么語句用于讀寫互斥，寫寫互斥；（3）若規(guī)定僅允許5個進程同時讀怎樣修改程序？解（1）Sr用于讀者計數(shù)rc的互斥信號量； （2）if rc=1 then P（S）中的P（S）用于讀寫互斥，寫者進程中的P（S）用于寫寫互斥，讀寫互斥。（3）程序中增加一個信號量S5，初值為5，P（S5）語句加在讀者進程P（Sr）之

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

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

12、使用。（2）mutex：用于互斥的信號量，初值為1。 各進程的代碼如下 ： 進程A 進程B 進程C . . . . P(mutex) P(mutex) P(mutex) 申請打印機 申請打印機 申請打印機 使用打印機 使用打印機 使用打印機 V(mutex) V(mutex) V(mutex) 8. 假定在某移動臂磁盤上，剛剛處理了訪問75號柱面的請求，目前正在80號柱面讀信息，并且有下述請求序列等待訪問磁盤：請求序列： 1 2 3 4 5 6 7 8欲訪問柱面號： 160 40190 188 905832102試用：(1)電梯調(diào)度算法 (2)最短尋找時間優(yōu)先算法分別列出實際處理上述請求的次序

13、。解(1)電梯調(diào)度算法:由”剛剛處理了訪問75號柱面的請求，目前正在80號柱面讀信息”可知:初始磁頭前進的方向是:”從小到大”所以:處理次序為：5 8 1 4 3 6 2 790102160188190584032(2)最短尋找時間優(yōu)先算法:處理次序為：5 8 6 2 7 1 4 390102 584032160 1881909. 有三個進程P1，P2和P3并發(fā)工作。進程P1需用資源S3和S1；進程P2需用資源S1和S2；進程P3需用資源S2和S3?；卮穑?1)若對資源分配不加限制，會發(fā)生什么情況?為什么?(2)為保證進程正確工作，應(yīng)采用怎樣的資源分配策略?為什么?解：(1)可能會發(fā)生死鎖例如

14、：進程P1，P2和P3分別獲得資源S3，S1和S2后再繼續(xù)申請資源時都要等待，這是循環(huán)等待。(或進程在等待新源時均不釋放已占資源)(2)可有幾種答案：A.采用靜態(tài)分配由于執(zhí)行前已獲得所需的全部資源，故不會出現(xiàn)占有資源又等待別的資源的現(xiàn)象(或不會出現(xiàn)循環(huán)等待資源現(xiàn)象)。或B.采用按序分配不會出現(xiàn)循環(huán)等待資源現(xiàn)象。或C.采用銀行家算法因為在分配時，保證了系統(tǒng)處于安全狀態(tài)。10. 某車站售票廳，任何時刻最多可容納20名購票者進入，當(dāng)售票廳中少于20名購票者時，則廳外的購票者可立即進入，否則需在外面等待。若把一個購票者看作一個進程，請回答下列問題：(1)用PV操作管理這些并發(fā)進程時，應(yīng)怎樣定義信號量，

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

16、但使用時應(yīng)一致(即上述的s全應(yīng)改成t)。11 有兩個進程P1和P2，它們執(zhí)行的過程如下：P1: 10秒CPU操作、20秒I/O操作（設(shè)備1）、5秒CPU操作、10秒I/O操作（設(shè)備2）、5秒CPU操作、結(jié)束P1: 15秒I/O操作（設(shè)備1）、10秒CPU操作、15秒I/O操作（設(shè)備2）、10秒CPU操作、結(jié)束（1） 如果進程P1和P2順序執(zhí)行，請畫出進程P1和P2執(zhí)行情況圖；（2） 如果進程P1和P2并發(fā)執(zhí)行，請畫出進程P1和P2執(zhí)行情況圖；（3） 分別計算在（1）和（2）情況下，CPU的利用率、設(shè)備1和設(shè)備2的利用率。解：(1) P1和P2順序執(zhí)行P1:CPUI/O(DEV2)CPUI/O(

17、DEV1)CPU0 10 30 35 45 50P2:CPUI/O(DEV2)CPUI/O(DEV1)50 65 75 90 100(2) P1和P2并發(fā)執(zhí)行 CPU(P1)CPU(P1)1)CPU(P2)CPU(P2)CPU(P1)I/O(DEV1)(P1)I/O(DEV1)(P2)I/O(DEV2)I/O(DEV2)(P2)0 10 15 25 35 40 50 55(3) 在情況（1）下，CPU的利用率=40/100=40%設(shè)備1的利用率=35/100=35%設(shè)備2的利用率=25/100=25%在情況（2）下，CPU的利用率=40/55=73%設(shè)備1的利用率=35/55=64%設(shè)備2的利

18、用率=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=0x660C0x1502：0x65020x1d71：缺頁0x2c27：0x14270x4000：越界13有一個文件系統(tǒng)，根目錄常駐內(nèi)存，目錄文件采用鏈接

19、式，每個磁盤塊存放10個下級文件的描述，最多存放40個下級文件(最多涉及到4個盤塊)，若下級文件為目錄文件，則上級目錄指向該目錄文件的第一塊，否則指向普通文件的文件控制塊。普通文件采用二級索引形式，文件控制塊中給出12個磁盤塊地址，前10個磁盤塊地址指出前10頁的物理地址，第11個磁盤塊地址指向一級索引表，一級索引表給出256個磁盤塊地址，即指出該文件第10頁至第256頁的地址，第12個磁盤塊地址指向二級索引表，二級索引表中指出256個一級索引表的地址。(1) 該文件系統(tǒng)中的普通文件最大可有多少頁?(2) 若要讀文件/A/D/K/Q中的某一頁, 最少要啟動磁盤幾次? 最多要啟動磁盤幾次?答：（

20、1）一個文件的所有塊可以通過下面三種途徑找到：直接通過FCB找到前10塊，通過一級索引找到256塊，通過二級索引找到256*256塊，所以一個文件最大可以有10+256+2562塊最壞情況是：每次讀取目錄描述信息的時候都在最后一個塊找到下級的目錄或文件，所以要找到Q文件的FCB至少要讀取A的第一塊，D、G、二個目錄項的所有四個塊，再讀取Q的FCB，總共要1+4*2+110次啟動硬盤。找到FCB后再讀取該文件頁所在的塊，如果這一塊在前10塊之列，那么在啟動一次硬盤就可以找到這一塊，如果這一塊在最后一塊，則可能需要通過二級索引找到這一塊，這總共需要讀取二級索引和最后一塊共2+1次讀取硬盤。14.一

21、個系統(tǒng)中存在某類資源m個，被n個進程共享。資源的分配和釋放必須一個一個進行，請證明在以下兩個條件下不會發(fā)生死鎖：l 每個進程需要資源的最大數(shù)在1m之間；l 所有進程需要的資源總數(shù)小于m+n；證明：假設(shè)進程Pi(0<i<n+1)需要的資源數(shù)為Ri，則 R1+R2+.+Rn<m+n (1) 1 <= Ri <= m (2) 假設(shè)進程已經(jīng)分配到的資源為Ai(0<i<n+1)，則Ai<=Ri假設(shè)當(dāng)前發(fā)生了死鎖，則 A1+A2+.+An=m Ai<Ri (0<i<n+1)也就是 Ai+1<=Ri 則 A1+A2+.+An+n<

22、=R1+R2+.+Rn 即 m+n<=R1+R2+.+Rn和（1）矛盾，死鎖不成立。15一個請求式分頁存儲系統(tǒng)，頁表存放在內(nèi)存：l 訪問一次內(nèi)存需要100nsl 如果僅調(diào)入一個頁面，需要花費8ms（內(nèi)存有空頁面，或需要進行頁面置換，單被置換的頁面沒有修改過）；l 如果調(diào)入一個頁面同時需要進行被置換頁面的寫出，則需要20ms;l 假設(shè)頁面被修改的比例是60%;請問，缺頁率必須控制在多少以下，才能使得EAT<200ns?解： 假設(shè)缺頁率為f_rate,則，EAT=(1-f_rate)*100+f_rate*(40%*8000+60%*20000)如EAT<200,則，(1- f_

23、rate)*100+f_rate*(40%*8000+60%*20000)<200100-100*f_rate+15200*f_rate<200151*f_rate<1f_rate<1/151即缺頁率小于0.66%。16一個文件有100個磁盤塊，假設(shè)文件控制塊在內(nèi)存（如果文件采用索引分配(indexed allocation)，索引表也在內(nèi)存）。在下列情況下，請計算在contiguous, linked, indexed(single-level)三種分配方式下，分別需要多少次磁盤I/O操作？（每讀出或?qū)懭胍粋€磁盤塊都需要一次磁盤I/O操作）(10%)假設(shè)在contig

24、uous分配方式下，文件頭部無空閑的磁盤塊，但文件尾部有空閑的磁盤塊。假設(shè)要增加的塊信息存放在內(nèi)存中。l 在文件開始處添加一個磁盤塊；l 在文件結(jié)尾處添加一個磁盤塊；l 在文件中間刪除第50塊磁盤塊；（假設(shè)磁盤塊編號從099）l 在文件第50塊前添加一個磁盤塊；（假設(shè)磁盤塊編號從099）解：l 在文件開始處添加一個磁盤塊：連續(xù)：201/鏈接：1/索引：1l 在文件結(jié)尾處添加一個磁盤塊：連續(xù)：1/鏈接：101/索引：1l 在文件中間刪除一個磁盤塊：連續(xù)：48*211=98/鏈接：52/索引：0l 在文件中間添加一個磁盤塊：連續(xù)：101/鏈接：52/索引：117.一個操作系統(tǒng)有20個進程，競爭使用30個同類資源，申請方式是逐個進行，一旦某個進程獲得了它的全部資源，就馬上歸還所有的資源，每個進程最多使用30，最少使用一個資源。20個進程需要的資源總數(shù)小于50。如果僅考慮這類資源，系統(tǒng)會產(chǎn)生死鎖嗎？請說明理由。 答：設(shè)max(i)表示第i個進程的最大資源需求量，need(i)表示第i個進程還需要的資源量，alloc(i)表示第i個進程已分配的資源量。由題中所給條件可知：max(1)+max(20)=(need(1)+need(20)+(alloc(1)+alloc(20)<50如果在這個系統(tǒng)中發(fā)生了死鎖，那么一方面3