操作系統(tǒng)習(xí)題課講解

1、1 Problems1: 題面題面 l下面通過程序模擬父親和母親給兒子削蘋果吃的過程： 父親進程和母親進程的功能是削蘋果，然后把削好的 蘋果放在盤子中；兒子進程的功能是在盤子里面有蘋 果的，取蘋果吃。 l假設(shè)如下： 1）蘋果的數(shù)目沒有限制，即父親和母親可以一直 削蘋果； 2）兒子的胃口沒有限制，即兒子可以一直吃蘋果； 3）盤子只能容納一個蘋果； l請編程實現(xiàn)父進程和子進程，同時實現(xiàn)同步互斥。 Problem 1: 知識點知識點 l知識點：互斥和同步 lPage 158 ，結(jié)合book 5.5.3生產(chǎn)者消費者問 題 l需要注意的地方：保證每次只有一個人占用盤 子 3 Problems 1: 思路

2、思路 l思路：采用信號量和互斥體實現(xiàn) u信號量plate表示盤子，初始值1 u信號量apple表示蘋果，初始值0 Problems 1 : 答案答案 父親進程： 削蘋果 semwait(plate) 放蘋果 semsignal(apple) 母親進程： 削蘋果 semwait(plate) 放蘋果 semsignal(apple) 兒子進程 semwait(apple) 取蘋果 semsignal(plate) 吃蘋果 semphere plate =1 semphere apple=0 5 Problems2: 題面題面1/2 l有三個進程：Read、Move和Print，共享兩個緩存B1

3、和B2 進程Read：讀取一條記錄，并放在緩存B1中 進程Move：從緩存B1中讀取記錄，處理后放入緩 存B2中 進程Print：從B2中讀取數(shù)據(jù)并打印 請通過信號量的等待和激發(fā)操作填空 6 Problems2: 題面題面2/2 Problem 2: 知識點知識點 l知識點：互斥和同步、信號量 lPage 154 ，結(jié)合book5.3信號量 l需要注意的地方：系統(tǒng)運行時，必須保證 READ優(yōu)先使用B1緩存，MOVE優(yōu)先使用B2 緩存（原因：初始狀態(tài)B1和B2緩沖中的數(shù)據(jù) 是無效數(shù)據(jù)） 8 Problems 2: 思路思路 l三個進程的關(guān)系如下： 對于READ進程：在對B1 緩沖區(qū)寫數(shù)據(jù)時，首先

4、要判斷MOVE 進 程是否將上一次讀的數(shù)據(jù)取走，如果沒有取走，READ等待；否則， 寫入數(shù)據(jù)（數(shù)據(jù)放到B1，然后通知MOVE進程，B1緩存可用； 對于MOVE進程：首先判斷B1 緩沖區(qū)中的數(shù)據(jù)是否可用，如果沒 有等待；否則，從B1 緩存中讀取數(shù)據(jù)，然后對數(shù)據(jù)進行加工，加 工完畢后，判斷PRINT進程是否已將上次MOVE進程放到B2緩沖區(qū) 中的數(shù)據(jù)取走，如果沒有取走，等待；否則，將加工后的數(shù)據(jù)存放 到B2緩沖區(qū)，然后通知PRINT進程可以使用B2緩沖區(qū)； 對于PRINT進程：判斷B2緩沖區(qū)的數(shù)據(jù)是否可用，如果不可用，則 等待；如果可用，則打印，然后通知MOVE進程，B2的數(shù)據(jù)已取走， MOVE進

5、程可對B2緩沖區(qū) 進行更新操作。 9 Problems 2 : 答案答案1/3 通過上面分析，可以知道 ，在這個程序中我們需要使用 四個信號量，其中： lS0用于表明READ是否可以使用B1； （B1中是否有 空位置 ） lS1用于表明MOVE是否可以使用B1； （B1中是否有 數(shù)據(jù) ） lS2用于表明MOVE是否可以使用B2； （B2中是否有 有空位置 ） lS3用于表明PRINT是否可以使用B2； （B2中是否有 數(shù)據(jù)） 10 Problems 2 : 答案答案2/3 l初始化：因為由于優(yōu)先級的問題，所以有 Semsignal s0=1; （B1中有位置 ）1表示有位置， 0表示沒有位置

6、Semsignal s1=0; （B1中沒有數(shù)據(jù) ）1表示有數(shù)據(jù) ，0表示沒有數(shù)據(jù) Semsignal s2=1; （B2中有位置 ）1表示有位置， 0表示沒有位置 Semsignal s3=0; （B2中沒有 產(chǎn)品 ）1表示有數(shù)據(jù) ，0表示沒有數(shù)據(jù) 11 Problems 2 : 答案答案3/3 Problems3: 6.4 題面題面1/2 l考慮一個下面的一個系統(tǒng)，當前不存在未滿足的請求 ： Problems3: 題面題面2/2 l計算每個進程仍然可能需要的資源，并填入標為“仍然需要”中 l系統(tǒng)當前是處于安全狀態(tài)還是不安全狀態(tài)？為什么？ l系統(tǒng)當前是否死鎖，為什么？ l那個進程（如果存在）

7、是死鎖的或可能變成死鎖的？ l如果P3的請求（0，1，0，0）到達，是否可以立即安全地同 意該請求？在什么狀態(tài)（死鎖，安全，不安全）下可以立即同 意系統(tǒng)剩下的全部請求？如果立即同意全部請求，哪個進程（ 如果有）是死鎖的或可能變成死鎖的。 Problems3: 知識點知識點 l資源分配 l安全狀態(tài)定義 l死鎖避免 l死鎖檢測算法 Problem 3: 答案答案a a.計算每個進程仍然可能需要的資源，并填入標為“仍然需要”中 *still needs=maximum demand-current allocation Problem 3: 答案答案b l系統(tǒng)當前是處于安全狀態(tài)還是不安全狀態(tài)？為什么

8、？ l知識點：safe state，Page192 l答案：運行銀行家算法，進程結(jié)束順序為： P1-P4-P5-P2-P3.處于安全狀態(tài) P1結(jié)束時：A=(2 1 0 0) + (0 0 1 2) = (2 1 1 2) P4結(jié)束時：A=(2 1 1 2) + (2 3 5 4) = (4 4 6 6) P5結(jié)束時：A=(4 4 6 6) + (0 3 3 2) = (4 7 9 8) P2結(jié)束時：A=(4 7 9 8 ) + (2 0 0 0) = (6 7 9 8) P3結(jié)束時：A=(6 7 9 8 ) + (0 0 3 4 )= (6 7 12 12) 安全狀態(tài)：指至少有一個進 程執(zhí)行序

9、列不會導(dǎo)致死鎖 Problem 3: 答案答案c W = (2 1 0 0) + (0 1 2 0) = (2 2 2 0) 3. Mark P2; W = (2 2 2 0) + (2 0 0 1) = (4 2 2 1) 4. Mark P1; no deadlock detected Problems5: 8.4 題面題面 l一個進程分配給4個頁幀（下面的所有數(shù)字均為十進制數(shù)，每一項都是從0開始計數(shù) 的）。上一次把一頁裝入到一個頁幀的時間、上一次訪問頁幀中的頁的時間、每個 頁幀中的虛擬頁號以及每個頁幀的訪問位（R）和修改位（M）如下表所示（時間均 為從進程開始到該事件之間的時鐘時間，而不

10、是從事件發(fā)生到當前的時鐘值）。 當虛擬頁4發(fā)生頁錯誤時，使用下列內(nèi)存管理策略，哪一個頁幀將用于置換？解釋原 因。 a.FIFO（先進先出）算法 b.LRU（最近最少使用）算法 c.Colck算法 d.最佳（使用下面的訪問串）算法：4,0,0,0,2,4,2,1,0,3,2 Problems5: 答案答案a la. FIFO(先進先出）先進先出）p255 PFN 3 since loaded longest ago at time 20 Problems5: 答案答案b b.LRU (最近最少使用）最近最少使用） (替換主存中上次使用距當前最遠的頁替換主存中上次使用距當前最遠的頁) PFN 1

11、since referenced longest ago at time 160 Problems5: 答案答案c c. Clock Clear R in PFN 3 (oldest loaded), clear R in PFN 2 (next oldest loaded), victim PFN is 0 since R=0 Problems5: 答案答案d d. 最佳最佳(替換下次訪問距當前時間最長的頁）替換下次訪問距當前時間最長的頁） Replace the page in PFN 3 since VPN 3 (in PFN 3) is used furthest in the fut

12、ure 4,0,0,0,2,4,2,1,0,3,2 Problems6: 8.6 題面題面 l一個進程在磁盤上包含8個虛擬頁，在主存中固定分配 給4個頁幀。發(fā)生如下順序的頁訪問： 1,0,2,2 ,1,7,6,7, 0,1,2,0 ,3,0,4,5, 1,5,2,4, 5,6,7,6 ,7,2,4,2 ,7,3,3,2, 3 a.如果使用LRU替換策略，給出相繼駐留在這4個頁幀 中的頁。計算主存的命中率。假設(shè)這些幀最初是空的。 b.如果使用FIFO策略，重復(fù)問題（a） c.比較使用這兩種策略的命中率。解釋為什么對這個特 殊的訪問順序，使用FIFO的效率接近于LRU Problems7: 9.1

13、 題面題面 l 考慮以下進程集合 l給出類似于表9.5和圖9.5的分析（P286） Problems7: 9.1 答案答案 l FCFS（先到先服務(wù)，非搶占） Problems7: 9.1 答案答案 RR q = 1（時間片輪轉(zhuǎn)，搶占） Problems7: 9.1 答案答案 lRR q=4（時間片輪轉(zhuǎn)，搶占） Problems7: 9.1 答案答案 lSPN (最短進程優(yōu)先，非搶占) Problems7: 9.1 答案答案 lSRT（最短剩余時間優(yōu)先，搶占） Problems7: 9.1 答案答案 lHRRN(最高響應(yīng)比,R=（w+s）/s,非搶占) Problems7: 9.1 答案答案

14、lFB（反饋，時間片+動態(tài)優(yōu)先級）(q=1，注意時間片 到了，就緒隊列沒有進程則不降級) Problems7: 9.1 答案答案 lFB q=2i(注意時間片到了，就緒隊列沒有進程則不降 級) Problems8: 9.2 題面題面 l 考慮以下進程集合 l給出類似于表9.5和圖9.5的分析 Problems8: 9.2 思路思路 l 參考Problem7 Problems8: 9.2 答案答案 Problems8: 9.2 答案答案2/2 Problems9: 11.3 題面題面 l 使用與表11.2（P347）類似的方式，分析下 列磁道請求：27，129，110，186，147，41 ，1

15、0，64，120。初始磁道為100 （1）磁頭沿磁道號減小的方向運行 （2）磁頭沿磁道號增大的方向運行 Problems9: 11.3 思路思路and答案答案 l知識點：各種磁盤調(diào)度算法 lFIFO SSTF SCAN C-SCAN （1）磁頭沿磁道號減小的方向運行 FIFO 初始磁道為100 27，129，110，186，147，41，10，64，120 SSTF(最短服務(wù)時間) 初始磁道為100 27，129，110，186，147，41，10，64，120 Problems9: 11.3 答案答案 lSCAN(磁頭沿一個方向往返，滿足運動方向上的請求) 初始磁道為100 27，129，1

16、10，186，147，41，10，64，120 Problems9: 11.3 答案答案 lC-SCAN（磁頭向一個方向單向運動） 初始磁道為100 27，129，110，186，147，41，10，64，120 Problems9: 11.3 答案答案 l（2）磁頭沿磁道號增大的方向運動 lFIFO,SSTF與磁頭運動方向無關(guān)，結(jié)果與上題一致 lSCAN 初始磁道為100 27，129，110，186，147，41，10，64，120 Problems9: 11.3 答案答案 lC-SCAN 初始磁道為100 27，129，110，186，147，41，10，64，120 Problems9: 11.3 答案答案 Problems10: 題面題面 lThere is sequence of disk track requests:75 62 99 144 50 162 110 26 198.