操作系統(tǒng)作業(yè)答案

1、習題一1、舉例說明為什么對并發(fā)執(zhí)行的程序不加控制會產(chǎn)生與執(zhí)行時間有關(guān)的錯誤？解：程序在并發(fā)執(zhí)行時由于資源是共享的，而且常常資源數(shù)少于程序?qū)@些資源的需求數(shù)，致使這些并發(fā)執(zhí)行的程序之間因為競爭資源導(dǎo)致存在間接制約關(guān)系，這種間接制約使得并發(fā)執(zhí)行的程序具有隨機性（異步性），即“執(zhí)行暫停執(zhí)行”，它們何時啟動、何時停止是未知的。例如：飛機售票系統(tǒng)、堆棧的存數(shù)與取數(shù)過程等（示例說明略）。2、程序并發(fā)執(zhí)行為什么會失去順序執(zhí)行時的封閉性和可再現(xiàn)性？解：所謂“封閉性”是指程序執(zhí)行得到的最終結(jié)果由給定的初始條件決定，不受外界因素的影響。在程序并發(fā)執(zhí)行時由于資源共享，導(dǎo)致這些資源的狀態(tài)將由多個程序來改變，又由于存在

2、程序執(zhí)行的隨機性，所以程序的運行失去封閉性。由于失去了封閉性，也將導(dǎo)致其失去可再現(xiàn)性。即雖然它們執(zhí)行時的環(huán)境和初始條件相同，但得到的結(jié)果卻可能各不相同。習題二1、試用加鎖的方法解決飛機售票系統(tǒng)的問題。例：民航售票系統(tǒng)，n個售票處2、用機器指令（testAndset）解決飛機售票系統(tǒng)中任一進程的算法。習題三1、進程在做P、V操作時對自己和其他進程有何影響？進程在信號量上執(zhí)行P操作后，若信號量的值為正，當前進程繼續(xù)執(zhí)行；若信號量的值為負，當前進程變?yōu)榈却隣顟B(tài)、放棄處理機，其它進程則有機會獲得CPU。 進程在信號量上執(zhí)行V操作后，不會對自己有任何影響，但當信號量的值不大于0時，需要喚醒在該信號量上所

3、對應(yīng)的等待隊列中的進程。2、設(shè)課程的前驅(qū)、后繼關(guān)系如下，若每修一門課程看作進程Px（x1.6）試用P、V操作算法描述這種前驅(qū)與后繼關(guān)系。答：Semaphore：S1：=S2：=S3：=S4：=S5：=S6：=0；Begin Cobegin P1、P2、P3、P4、P5、P6 coend; end.P1（） P2（） P3（）Begin begin begin 修計算機導(dǎo)論； P（S1）； P（S2）； V（S1）； 修高級語言程序設(shè)計 修計算機組成原理； V（S2）； V（S3） V（S4）；End; End; End;P4（） P5（） P6（）Begin begin begin P（S3）

4、； P（S4）； P（S5）； 修數(shù)據(jù)結(jié)構(gòu)； 修86匯編語言； P（S6）； V（S5）； V（S6）； 修操作系統(tǒng)；End; End; End;習題四1、有三個進程 R、W1、W2，進程 R 從輸入設(shè)備上讀數(shù)據(jù)送緩沖區(qū) B，若是奇數(shù)由 W1 進程從 B 取數(shù)輸出；若是偶數(shù)則由 W2 進程從 B 取數(shù)輸出。設(shè)緩沖區(qū) B 只有一個單元，試用信號量機制設(shè)計實現(xiàn)算法。1、se,sf1,sf2:semaphore;se:=1;sf1:=sf2:=0; R（）、W1（）、W2（）并發(fā)執(zhí)行Process R process W1 process W2repeat repeat repeat 讀數(shù); P(s

5、f1); P(sf2); P(se); 從B中取數(shù); 從B中取數(shù); 送數(shù)到B; V(se); V(se); if B mod 2!=0 then until false until false V(sf1); else V(sf2);until false2、設(shè)有一臺計算機，掛有一臺輸入機和一臺打印機?，F(xiàn)在從輸入機上把數(shù)據(jù)輸入到緩沖區(qū) B 中，處理程序處理后再把結(jié)果送到緩沖區(qū)B中，（設(shè)B只能放1個數(shù)據(jù)）然后在打印機上輸出。問: （1）系統(tǒng)可設(shè)哪些進程來完成這一任務(wù)? （2）這些進程之間有什么樣的制約關(guān)系? （3）用 PV 操作寫出這些進程的同步算法. 答：（1） 輸入進程、處理進程、輸出進程

6、（2） 處理進程不能在輸入進程之前執(zhí)行、輸出進程不能在處理進程之前執(zhí)行；輸入進程在未得到處理進程、輸出進程的消息前不能運行。 （3） 輸入（）、處理（）、輸出（）進程并發(fā)執(zhí)行Semaphore:s1、s2、s3；S1：=1；S2：=S3：=0； process 輸入（） process 處理（） process 輸出（） L1: 讀數(shù) L2: P(S2) L3: P(S3) P(S1) 從B取數(shù)處理后再送B 從B取數(shù)輸出 送數(shù)到B V(S3) V（S1） V(S2) Goto L2 Goto L3 Goto L1 習題五1、設(shè)系統(tǒng)中有 M 個資源，N 個進程，每個進程都要求 K 個資源；若 M

7、=5、N=5、K=2，問：（1）如何分配會導(dǎo)致死鎖？（2）要不死鎖應(yīng)該如何分配？ 如果對每個進程平均分配1個資源，則系統(tǒng)中的可用資源為 0，而每個進程都還需要1個資源，才能向前推進；因此、系統(tǒng)發(fā)生死鎖。 只要保證有1個進程能獲得2個資源，則它在有限的時間內(nèi)就可以運行完成并釋放資源，這樣系統(tǒng)就不會死鎖。例如、先給4個進程各分配1個資源，讓它們先運行，通過安全性算法測試可以知道第5個進程的資源申請將被拒絕；再把最后1個資源分配給這4個進程中的1個即可。2、假設(shè)甲、乙、丙三個并發(fā)進程間的PV操作同步算法如下所示, 信號量S1,S2,S3 的初值都為1，問這些算法在什么情況下發(fā)生死鎖?如何防止死鎖？

8、甲 乙 丙 . . .L1：P(S1) L2：P(S2) L3：P(S3) P(S2) P(S3) P(S1) . . . V(S2) V(S3) V(S1) V(S1) V(S2) V(S3) . . . goto L1 goto L2 goto L3答：甲P(S1)后暫停、乙P(S2) 后暫停、丙P(S3) 后暫停 采用按序分配，丙改為P（S1）、P（S3）。也可以改甲或乙進程的P、V操作次序，以限制進程的并發(fā)執(zhí)行。習題六1.設(shè)有5個哲學(xué)家，共享一張放有五把椅子的桌子，每人分得一把椅子。但是，桌子上總共只有5支筷子，在每人兩邊分開各放一支。哲學(xué)家們在肚子饑餓時才試圖分兩次從兩邊拾起筷子就餐

9、。條件：(1) 只有拿到兩支筷子時，哲學(xué)家才能吃飯。(2) 如果筷子已在他人手上，則該哲學(xué)家必須等待到他人吃完之后才能拿到筷子。(3) 任一哲學(xué)家在自己未拿到兩支筷子吃飯之前，決不放下自己手中的筷子。試:(1)描述一個保證不會出現(xiàn)兩個鄰座同時要求吃飯的通信算法。(2)描述一個既沒有兩鄰座同時吃飯，又沒有人餓死（永遠拿不到筷子）的算法。(3) 在什么情況下，5 個哲學(xué)家全部吃不上飯？ 答：使用非對稱解決 即奇數(shù)號的哲學(xué)家先拿起他左邊的筷子，接著拿起他右邊的筷子，而偶數(shù)號的哲學(xué)家先拿起他右邊的筷子，接著再拿他左邊的筷子。（1）設(shè)信號量c0c4,初始值均為1,分別表示i號筷子被拿(i=0,1,2,3

10、,4),send(i):第i個哲學(xué)家要吃飯beginthink;P(ci); P(ci+1 mod 5);eat;V(ci+1 mod 5); V(ci);End;該過程能保證兩鄰座不同時吃飯,但會出現(xiàn)5個哲學(xué)家一人拿一只筷子,誰也吃不上飯的死鎖情況（2）解決的思路:讓奇數(shù)號的哲學(xué)家先取右手邊的筷子,讓偶數(shù)號的哲學(xué)家先取左手邊的筷子.這樣,任何一個哲學(xué)家拿到一只筷子之后,就已經(jīng)阻止了他鄰座的一個哲學(xué)家吃飯的企圖,除非某個哲學(xué)家一直吃下去,否則不會有人會餓死.send(i): 第i個哲學(xué)家要吃飯Beginthink;If i mod 2=0 then P(ci); P(ci+1mod 5)eat

11、;V(ci; ci+1 mod 5) else P(ci+1 mod 5)P(ci)EatV(ci+1 mod 5)V(ci) End（3）非對稱解決，并發(fā)主程序略Program diningphilosophers; Var chopstick:array0.4 of semaphore(:=1),i:integer;Procedure philosopher(i:integer);BeginRepeatThink;If(i mod 2！=0) thenBeginP(chopsticki)；P(chopstick(i+1) mod 5)；吃面；V(chopstick(i+1) mod 5)；

12、V(chopsticki)；EndElseBeginP(chopstick(i+1) mod 5)；P(chopsticki)；吃面；V(chopstick(i+1) mod 5)；V(chopsticki)；EndForeverEnd習題七1、某程序在虛擬（邏輯）地址100處有一條取數(shù)指令LOAD 1,500 而500單元存放數(shù)據(jù)51888。若程序分配到的內(nèi)存地址為5000，試畫出下列方式下的該指令及數(shù)據(jù)的物理地址和變換過程。（1）靜態(tài)重定位（2）動態(tài)重定位2、若一個虛擬地址空間占8頁，每個頁大小為1024，需要映射到32個內(nèi)存塊上，試問：（1）虛擬地址要用多少位表示？（2）物理地址要用多少

13、位表示？答（1）邏輯地址需要的位數(shù)：8*1024=23*210=213所以需要13位。（2）物理地址需要的位數(shù)：32*1024=25*210=215所以需要15位。習題八1、在頁式存儲管理系統(tǒng)中某個時刻某個進程的頁表如下，設(shè)地址結(jié)構(gòu)為32位，頁號占據(jù)22位，試把邏輯地址0A5CH轉(zhuǎn)換成物理地址（以十六進制表示）。2、在靜態(tài)頁式下，內(nèi)存總量為65536字節(jié)，每個存儲塊為4KB，一程序代碼段長32768字節(jié),數(shù)據(jù)段長16386字節(jié)，堆棧段長15870字節(jié)，規(guī)定不允許一個塊內(nèi)包含兩個段的內(nèi)容，請問能為該程序分配空間嗎？如果塊長為512字節(jié)呢？ 答：習題九1.在某頁式虛擬存儲系統(tǒng)中，頁面大小為100個單元，某作業(yè)占有內(nèi)存塊數(shù)m=2，若它的訪問虛存邏輯地址序列為：55、135、96、227、42、156、330、169、11、252、253假設(shè)各個內(nèi)存塊初始為空，試問：（1）按O