操作系統(tǒng)作業(yè)復(fù)習(xí)資料

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

2、變，又由于存在程序執(zhí)行的隨機(jī)性，所以程序的運(yùn)行失去封 閉性。由于失去了封閉性，也將導(dǎo)致其失去可再現(xiàn)性。即雖然它們執(zhí)行時(shí)的環(huán)境和初始條件相同，但得到的結(jié)果卻 可能各不相同。 習(xí)題二 1、試用加鎖的方法解決飛機(jī)售票系統(tǒng)的問(wèn)題。 例：民航售票系統(tǒng)，n個(gè)售票處 Begin key：=l； Cobeqin PC; Pi; 區(qū); Cotnd End. var keys integer; Const nunn=n; procedure Ph (=1.2, n; Begin vr R:mteger repeat 嚴(yán)膜訂票要職找到共享數(shù)據(jù) 放某月臬日某次航班的規(guī)有曇數(shù)勺 lock (keyfs) R=xkl；嚴(yán)

3、現(xiàn)著票數(shù)呼 if=l) R Ukl R; 輸出一張機(jī)票； 拙共享變量的修改 me 顯示“票已書完、J unlock Forever end; else V(mutex)； 顯示衣票己售完” 用P、v操作解決 cubegin procedure Pi coend P(mutex)； R=x|k；7*現(xiàn)宵票數(shù)勺 xk=R; V(niuleK)； 輸出一張機(jī)票； 解決共亨變量的修改沖突 2、用機(jī)器指令(testAndset)解決飛機(jī)售票系統(tǒng)中任一進(jìn)程的算法。 2解: Begin (ocK:=false? Cobegin Pa； Pi： Coend End var lock: boolean; Con

4、st num =n; procedure P Begin var xi:int repeat 戰(zhàn)旅客要求找到mum; while testAndSetloc町nothing; xi:=count： if 3CE1 then Begin XI：=Xk1； count:=XI; lock; =fal$e; 稀出一張黑； End else begin lock: =false: 輸出“票已啻龍”； end forever end; 習(xí)題三 1、進(jìn)程在做 P、V操作時(shí)對(duì)自己和其他進(jìn)程有何影響？ 進(jìn)程在信號(hào)量上執(zhí)行 P操作后，若信號(hào)量的值為正，當(dāng)前進(jìn)程繼續(xù)執(zhí)行；若信號(hào)量的值為負(fù)，當(dāng)前進(jìn)程變?yōu)榈却隣?態(tài)、

5、放棄處理機(jī)，其它進(jìn)程則有機(jī)會(huì)獲得CPU。 進(jìn)程在信號(hào)量上執(zhí)行 V操作后，不會(huì)對(duì)自己有任何影響，但當(dāng)信號(hào)量的值不大于 上所對(duì)應(yīng)的等待隊(duì)列中的進(jìn)程。 2、設(shè)課程的前驅(qū)、后繼關(guān)系如下，若每修一門課程看作進(jìn)程 繼關(guān)系。 0時(shí)，需要喚醒在該信號(hào)量 Px (x 1.6)試用 P、 V操作算法描述這種前驅(qū)與后 計(jì)算0導(dǎo)論 奇級(jí)訊呂程用設(shè)計(jì) 計(jì)算機(jī)組成原理 數(shù)扌居結(jié)腳 P2 () begin P (S1); 修高級(jí)語(yǔ)言程序設(shè)計(jì) V (S3) End; P5 () begin P (S4); 修86匯編語(yǔ)言； V ( S6); End; P3 () begin P (S2); 修計(jì)算機(jī)組成原理; V (S4);

6、 End; P6 () begin P (S5); P (S6); 修操作系統(tǒng)； En d; 答: Semaphore: S1: =S2： =S3: =S4： =S5: =S6: =0 ; Begin Cobegin P1、P2、P3、P4、P5、P6 coend; end. P1 () Begi n 修計(jì)算機(jī)導(dǎo)論； V (S1); V (S2); End; P4 () Begi n P (S3); 修數(shù)據(jù)結(jié)構(gòu)； V (S5); End; 習(xí)題四 W1進(jìn)程從B取數(shù)輸出；若 1、有三個(gè)進(jìn)程 R、W1、W2,進(jìn)程R從輸入設(shè)備上讀數(shù)據(jù)送緩沖區(qū)B,若是奇數(shù)由 是偶數(shù)則由 W2 進(jìn)程從 B 取數(shù)輸出。設(shè)

7、緩沖區(qū) B 只有一個(gè)單元，試用信號(hào)量機(jī)制設(shè)計(jì)實(shí)現(xiàn)算法。 1、 se,sf1,sf2:semaphore; se:=1;sf1:=sf2:=0; R（）、 W1（）、 W2 （）并發(fā)執(zhí)行 Process R repeat 讀數(shù) ; P（se）; 送數(shù)到 B; if B mod 2!=0 then V（sf1）; else V（sf2）; until false 2、設(shè)有一臺(tái)計(jì)算機(jī)，掛有 process W1 repeat P(sf1); 從 B 中取數(shù) ; V(se); until false process W2 repeat P(sf2); 從 B 中取數(shù) ; V(se); until fa

8、lse 臺(tái)輸入機(jī)和一臺(tái)打印機(jī)?，F(xiàn)在從輸入機(jī)上把數(shù)據(jù)輸入到緩沖區(qū) B 中，處理程序處理后 再把結(jié)果送到緩沖區(qū) B中，（設(shè)B只能放1個(gè)數(shù)據(jù)）然后在打印機(jī)上輸出。問(wèn)： （ 1 ）系統(tǒng)可設(shè)哪些進(jìn)程來(lái)完成這一任務(wù) ?（ 2）這些進(jìn)程之間有什么樣的制約關(guān)系 ? （ 3）用 PV 操作寫出這些進(jìn)程的同步算法 . 輸入進(jìn)程、處理進(jìn)程、輸出進(jìn)程 處理進(jìn)程不能在輸入進(jìn)程之前執(zhí)行、輸出進(jìn)程不能在處理進(jìn)程之前執(zhí)行；輸入進(jìn)程在未得到處理進(jìn)程、輸 出進(jìn)程的消息前不能運(yùn)行。 輸入（） 、處理（） 、輸出（）進(jìn)程并發(fā)執(zhí)行 答:（ 1） （2） 3） Semaphore：s1 、 s2、 process 輸入（） L1： 讀數(shù)

9、 P（S1） 送數(shù)到 B V（S2） Goto L1 習(xí)題五 1 、設(shè)系統(tǒng)中有 M 個(gè)資源， （ 1 ）如何分配會(huì)導(dǎo)致死鎖？ （ 2）要不死鎖應(yīng)該如何分配？ ? 如果對(duì)每個(gè)進(jìn)程平均分配 推進(jìn)；因此、系統(tǒng)發(fā)生死鎖。 s3； S1: =1； S2: =S3: =0； process 處理() L2: P(S2) 從 B 取數(shù)處理后再送 B V(S3) Goto L2 個(gè)進(jìn)程，每個(gè)進(jìn)程都要求 process 輸出() L3: P(S3) 從 B 取數(shù)輸出 V( S1) Goto L3 K個(gè)資源；若 M=5、N=5、K=2，問(wèn): 1 個(gè)資源，則系統(tǒng)中的可用資源為0，而每個(gè)進(jìn)程都還需要 1 個(gè)資源，才能

10、向前 1 個(gè)資源分配給這 4 個(gè)進(jìn)程中的 1 個(gè)即可。 PV操作同步算法如下所示，信號(hào)量S1,S2,S3的初值都為1,問(wèn)這些算法在什 ? 只要保證有 1 個(gè)進(jìn)程能獲得 2 個(gè)資源，則它在有限的時(shí)間內(nèi)就可以運(yùn)行完成并釋放資源，這樣系統(tǒng)就不會(huì) 死鎖。例如、先給 4 個(gè)進(jìn)程各分配 1 個(gè)資源，讓它們先運(yùn)行，通過(guò)安全性算法測(cè)試可以知道第 5 個(gè)進(jìn)程的 資源申請(qǐng)將被拒絕；再把最后 2、假設(shè)甲、乙、丙三個(gè)并發(fā)進(jìn)程間的 么情況下發(fā)生死鎖 ?如何防止死鎖？ 甲 乙 丙 L1: P(S1) L2: P(S2) L3: P(S3) P(S2) P(S3) P(S1) V(S2) V(S3) V(S1) V(S1)

11、 V(S2) V(S3) goto L1 goto L2 goto L3 答： 甲P(S1)后暫停、乙P(S2)后暫停、丙P(S3)后暫停 采用按序分配，丙改為 P(S1)、 P( S 3)。 也可以改甲或乙進(jìn)程的 P、 V 操作次序，以限制進(jìn)程的并發(fā)執(zhí)行。 習(xí)題六 1. 設(shè)有 5 個(gè)哲學(xué)家，共享一張放有五把椅子的桌子，每人分得一把椅子。但是，桌子上總共只有5 支筷子，在每人 兩邊分開各放一支。哲學(xué)家們?cè)诙亲羽囸I時(shí)才試圖分兩次從兩邊拾起筷子就餐。 條件： (1) 只有拿到兩支筷子時(shí)，哲學(xué)家才能吃飯。 (2) 如果筷子已在他人手上，則該哲學(xué)家必須等待到他人吃完之后才能拿到筷子。 (3) 任一哲學(xué)

12、家在自己未拿到兩支筷子吃飯之前，決不放下自己手中的筷子。 試: (1) 描述一個(gè)保證不會(huì)出現(xiàn)兩個(gè)鄰座同時(shí)要求吃飯的通信算法。 (2) 描述一個(gè)既沒(méi)有兩鄰座同時(shí)吃飯，又沒(méi)有人餓死(永遠(yuǎn)拿不到筷子)的算法。 (3) 在什么情況下， 5 個(gè)哲學(xué)家全部吃不上飯？ 答：使用非對(duì)稱解決 -即奇數(shù)號(hào)的哲學(xué)家先拿起他左邊的筷子，接著拿起他右邊的筷子，而偶數(shù)號(hào)的哲學(xué)家先拿 起他右邊的筷子，接著再拿他左邊的筷子。 ( 1 ) 設(shè) 信 號(hào) 量 c0c4, 初 始 值 均 為 1, 分 別 表 示 i 號(hào) 筷 子 被 拿 (i=0,1,2,3,4), send(i): 第 i個(gè) 哲 學(xué)家要 吃飯 begin thin

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

14、; ci+1 mod 5) else P(ci+1 mod 5) P(ci) Eat V(ci+1 mod 5) V(ci) End (3) 非對(duì)稱解決，并發(fā)主程序略 Program diningphilosophers; Var chopstick:array0.4 of semaphore(:=1),i:integer; Procedure philosopher(i:integer); Begi n Repeat Thi nk; If(i mod 2 ! =0) then Begin P(chopsticki) ； P(chopstick(i+1) mod 5);吃面; V(chopst

15、ick(i+1) mod 5) ; V(chopsticki); End Else Begin P(chopstick(i+1) mod 5) ; P(chopsticki);吃面; V(chopstick(i+1) mod 5) ; V(chopsticki); End Forever End 習(xí)題七 1、某程序在虛擬(邏輯)地址 100處有一條取數(shù)指令LOAD 1,500而500單元存放數(shù)據(jù)51888。若程序分配到的內(nèi) 存地址為5000，試畫出下列方式下的該指令及數(shù)據(jù)的物理地址和變換過(guò)程。 (1) 靜態(tài)重定位 (2) 動(dòng)態(tài)重定位 C1）靜態(tài)墮圧位 a LOAD 1. 500 500 空也蘭

16、 2、若一個(gè)虛擬地址空間占 8頁(yè)，每個(gè)頁(yè)大小為1024，需要映射到32個(gè)內(nèi)存塊上，試問(wèn): （1）虛擬地址要用多少位表示？ （2）物理地址要用多少位表示？ 答 （1）邏輯地址需要的位數(shù)： 31013 8*1024=2 *2 =2 所以需要13位。 （2）物理地址需要的位數(shù)： 32*1024=2 5*2 10=215 所以需要15位。 習(xí)題八 1、在頁(yè)式存儲(chǔ)管理系統(tǒng)中某個(gè)時(shí)刻某個(gè)進(jìn)程的頁(yè)表如下，設(shè)地址結(jié)構(gòu)為32位，頁(yè)號(hào)占據(jù)22位，試把邏輯地址0A5CH 轉(zhuǎn)換成物理地址（以十六進(jìn)制表示）。 霽 1 13 2 3 7 1、聲一t 地址結(jié)構(gòu)為3迪 頁(yè)號(hào)占捋22世因此頁(yè)內(nèi)位穢占掲10也 師以頁(yè)（Hi）底是

17、1K日 P=LAdiV PAGE_SIZE=OA5CH div 400H2、 D=LAmod PAGE_SIZE=0A5CH rnod400H =25CH 杏頁(yè)袁可卻.頁(yè)號(hào)為2時(shí)對(duì)應(yīng)師境號(hào)的4.且塊最為40DH （1KB . 所以，PA=4X400H+25CH=125CH 禪二； OA5CHOO06 0000, 0WXL 0000, 0000佃仙* 0101, 11Q0B 由于塊號(hào)為*則根堀地址結(jié)構(gòu)具憂理地址為： 00*0. 0000. 00000000 0001, 0010, 0101, 11OOB=1：5CH 2、在靜態(tài)頁(yè)式下，內(nèi)存總量為65536字節(jié)，每個(gè)存儲(chǔ)塊為4KB, 程序代碼段長(zhǎng)

18、32768字節(jié)，數(shù)據(jù)段長(zhǎng)16386字節(jié), 堆棧段長(zhǎng)15870字節(jié)，規(guī)定不允許一個(gè)塊內(nèi)包含兩個(gè)段的內(nèi)容，請(qǐng)問(wèn)能為該程序分配空間嗎？如果塊長(zhǎng)為512字節(jié) 呢？ 答： 2. 內(nèi)存總塊數(shù)=65536/4KB胡6塊 代碼段需要量=32768/4KB8塊 數(shù)據(jù)段需要量=16386/4KB=4.00048B28125=5塊 堆桟殷需要皇=138了W4KB=3 874M 171875=4i 8+5+4=1716:所以，沒(méi)有足夠的內(nèi)存塊分配。 如果塊長(zhǎng)為512字節(jié)： 內(nèi)存位塊數(shù)-65536/512-128塊 代碼段需4-32768/512=64塊 數(shù)據(jù)段需要量二 16386/512二32 00390625二33

19、塊 堆棧段需=15870/512=30 99609375=31 塊 64+33+31=128所以可以分配= 習(xí)題九 1在某頁(yè)式虛擬存儲(chǔ)系統(tǒng)中，頁(yè)面大小為100個(gè)單元，某作業(yè)占有內(nèi)存塊數(shù) m=2,若它的訪問(wèn)虛存邏輯地址序列為： 55、 135、 96、 227、 42、 156、 330、 169、 11、 252、 253 假設(shè)各個(gè)內(nèi)存塊初始為空，試問(wèn)： （1） 按OPT置換算法畫圖表示頁(yè)面置換過(guò)程并求缺頁(yè)中斷率f=？ （2） 按FIFO置換算法畫圖表示頁(yè)面置換過(guò)程并求缺頁(yè)中斷率f= ？ （3） 按LRU置換算法畫圖表示頁(yè)面置換過(guò)程并求缺頁(yè)中斷率f= ？ 頁(yè)面走向Z=CL丄0, Ch 1, 3

20、,02, 2 (1) OPT算法頁(yè)面置換過(guò)程： 1020131022 0 1 1 2 2 1 3 3 0 1 2 0 u a 0 u 1 1 1 i 1 F J 4 j J J J 4 比中仁 7/1163.6% (2) FIFO葬頁(yè)面置換過(guò)程； 01020131022 n2 0 1 t 1 n i 1 A 0 1 1 t Q 1 0 1 I 3 Q Q F 4 i 4 4 4 J 其中 f=8/1172.7% (3) LRU算法頁(yè)面置換過(guò)程： 01020131022 0 1 Q 2 0 1 3 I 0 I I 0 1 0 1 o 1 3 1 0 0 F J V 4 J J V V 其中仁 7/11