習(xí)題課講解課件

1Problems1:–題面下面通過程序模擬父親和母親給兒子削蘋果吃的過程：父親進(jìn)程和母親進(jìn)程的功能是削蘋果，然后把削好的蘋果放在盤子中；兒子進(jìn)程的功能是在盤子里面有蘋果的，取蘋果吃。

假設(shè)如下：1）蘋果的數(shù)目沒有限制，即父親和母親可以一直削蘋果；2）兒子的胃口沒有限制，即兒子可以一直吃蘋果；3）盤子只能容納一個(gè)蘋果；

請(qǐng)編程實(shí)現(xiàn)父進(jìn)程和子進(jìn)程，同時(shí)實(shí)現(xiàn)同步互斥。Problem1:–知識(shí)點(diǎn)知識(shí)點(diǎn)：互斥和同步Page158，結(jié)合book5.5.3生產(chǎn)者消費(fèi)者問題需要注意的地方：保證每次只有一個(gè)人占用盤子3Problems1:–思路思路：采用信號(hào)量和互斥體實(shí)現(xiàn)信號(hào)量plate表示盤子，初始值1信號(hào)量apple表示蘋果，初始值0互斥信號(hào)量mutex，防止盤子被多個(gè)人訪問，初始值15Problems2:–題面1/2有三個(gè)進(jìn)程：Read、Move和Print，共享兩個(gè)緩存B1和B2進(jìn)程Read：讀取一條記錄，并放在緩存B1中進(jìn)程Move：從緩存B1中讀取記錄，處理后放入緩存B2中進(jìn)程Print：從B2中讀取數(shù)據(jù)并打印請(qǐng)通過信號(hào)量的等待和激發(fā)操作填空6Problems2:–題面2/2Problem2:–知識(shí)點(diǎn)知識(shí)點(diǎn)：互斥和同步、信號(hào)量Page154，結(jié)合book5.3信號(hào)量需要注意的地方：系統(tǒng)運(yùn)行時(shí)，必須保證READ優(yōu)先使用B1緩存，MOVE優(yōu)先使用B2緩存（原因：初始狀態(tài)B1和B2緩沖中的數(shù)據(jù)是無效數(shù)據(jù)）8Problems2:–思路三個(gè)進(jìn)程的關(guān)系如下：對(duì)于READ進(jìn)程：在對(duì)B1緩沖區(qū)讀取數(shù)據(jù)時(shí)，首先要判斷MOVE進(jìn)程是否將上一次讀的數(shù)據(jù)取走，如果沒有取走，READ等待；否則，讀取一段（數(shù)據(jù)放到B1，然后通知MOVE進(jìn)程，B1緩存可用；對(duì)于MOVE進(jìn)程：首先判斷B1緩沖區(qū)中的數(shù)據(jù)是否可用，如果沒有等待；否則，從B1緩存中讀取數(shù)據(jù)，然后對(duì)數(shù)據(jù)進(jìn)行加工，加工完畢后，判斷PRINT進(jìn)程是否已將上次MOVE進(jìn)程放到B2緩沖區(qū)中的數(shù)據(jù)取走，如果沒有取走，等待；否則，將加工后的數(shù)據(jù)存放到B2緩沖區(qū)，然后通知PRINT進(jìn)程可以使用B2緩沖區(qū)；對(duì)于PRINT進(jìn)程：判斷B2緩沖區(qū)的數(shù)據(jù)是否可用，如果不可用，則等待；如果可用，則打印，然后通知MOVE進(jìn)程，B2的數(shù)據(jù)已取走，MOVE進(jìn)程可對(duì)B2緩沖區(qū)進(jìn)行更新操作。10Problems2:–答案2/3初始化：因?yàn)橛捎趦?yōu)先級(jí)的問題，所以有Semsignals1=1;（B1中有位置）1表示有位置，0表示沒有位置Semsignals2=0;（B1中沒有數(shù)據(jù)）1表示有數(shù)據(jù)，0表示沒有數(shù)據(jù)Semsignals3=1;（B2中有位置）1表示有位置，0表示沒有位置Semsignals4=0;（B2中沒有產(chǎn)品）1表示有數(shù)據(jù)，0表示沒有數(shù)據(jù)Problems3:6.4–題面1/2考慮一個(gè)下面的一個(gè)系統(tǒng)，當(dāng)前不存在未滿足的請(qǐng)求：可用R1R2R3R42100進(jìn)程當(dāng)前分配最大需求仍然需要r1r2r3r4r1r2r3r4r1r2r3r4P100120012P220002750P300346656P423544356P503320652Problems3:–

知識(shí)點(diǎn)資源分配安全狀態(tài)定義死鎖避免死鎖檢測算法Problem3:答案aa.計(jì)算每個(gè)進(jìn)程仍然可能需要的資源，并填入標(biāo)為“仍然需要”中*stillneeds=maximumdemand-currentallocation進(jìn)程當(dāng)前分配最大需求仍然需要r1r2r3r4r1r2r3r4r1r2r3r4P1001200120000P2200027500750P3003466566622P4235443562002P5033206520320可用R1R2R3R42100Problem3:答案b系統(tǒng)當(dāng)前是處于安全狀態(tài)還是不安全狀態(tài)？為什么？知識(shí)點(diǎn)：safestate，Page192答案：運(yùn)行銀行家算法，進(jìn)程結(jié)束順序?yàn)椋? P1->P4->P5->P2->P3.處于安全狀態(tài) P1結(jié)束時(shí)：A=(2100)+(0012)=(2112)P4結(jié)束時(shí)：A=(2112)+(2354)=(4466)P5結(jié)束時(shí)：A=(4466)+(0332)=(4798)P2結(jié)束時(shí)：A=(4798)+(2000)=(6798)P3結(jié)束時(shí)：A=(6798)+(0034)=(671212)Problem3:答案c&dIsthissystemcurrentlydeadlocked?Whyorwhynot?Whichprocesses,ifany,areormaybecomedeadlocked?

知識(shí)點(diǎn)：死鎖檢測算法Problem3:答案ee.如果P3的請(qǐng)求（0，1，0，0）到達(dá)，是否可以立即安全地同意該請(qǐng)求？在什么狀態(tài)（死鎖，安全，不安全）下可以立即同意系統(tǒng)剩下的全部請(qǐng)求？如果立即同意全部請(qǐng)求，哪個(gè)進(jìn)程（如果有）是死鎖的或可能變成死鎖的。知識(shí)點(diǎn)：銀行家算法，思路，先假設(shè)同意P3的請(qǐng)求，接著計(jì)算使用剩下的資源是否能夠找到一個(gè)進(jìn)程序列不會(huì)造成死鎖！Problems4:6.5–題面

請(qǐng)把6.4節(jié)的死鎖檢測算法應(yīng)用于下面的數(shù)據(jù)，并給出結(jié)果Problems4:–思路and答案知識(shí)點(diǎn)：死鎖檢測算法(6.4)1.W=(2100) 2. MarkP3; W=(2100)+(0120)=(2220)3. MarkP2; W=(2220)+(2001)=(4221)4. MarkP1;nodeadlockdetectedProblems5:–

答案aa.FIFO

PFN3sinceloadedlongestagoattime20

虛擬頁號(hào)頁幀加載時(shí)間訪問時(shí)間R位M位2060161011113016010022616210332016311Problems5:–

答案b b.LRU

PFN1sincereferencedlongestagoattime160

虛擬頁號(hào)頁幀加載時(shí)間訪問時(shí)間R位M位2060161011113016010022616210332016311Problems5:–

答案d d.最佳

ReplacethepageinPFN3sinceVPN3(inPFN3)isusedfurthestinthefuture4,0,0,0,2,4,2,1,0,3,2Problems6:8.6–

題面一個(gè)進(jìn)程在磁盤上包含8個(gè)虛擬頁，在主存中固定分配給4個(gè)頁幀。發(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個(gè)頁幀中的頁。計(jì)算主存的命中率。假設(shè)這些幀最初是空的。b.如果使用FIFO策略，重復(fù)問題（a） c.比較使用這兩種策略的命中率。解釋為什么對(duì)這個(gè)特殊的訪問順序，使用FIFO的效率接近于LRU

Problems8:9.1–答案FCFS（先到先服務(wù)，非搶占）012345678910111213141516171819AAABBBBBCCDDDDDEEEEE進(jìn)程ABCDE平均值到達(dá)時(shí)間013912服務(wù)時(shí)間(Ts)35255完成時(shí)間38101520周轉(zhuǎn)時(shí)間(Tr)3-0=38-1=710-3=715-9=620-12=86.2Tr/Ts11.43.51.21.61.74Problems8:9.1–答案012345678910111213141516171819ABABCABCBDBDEDEDEDEE進(jìn)程ABCDE平均值到達(dá)時(shí)間013912服務(wù)時(shí)間(Ts)35255完成時(shí)間61181820周轉(zhuǎn)時(shí)間(Tr)6-0=611-1=108-3=518-9=920-12=87.6Tr/Ts222.51.81.61.98RRq=1（時(shí)間片輪轉(zhuǎn)，搶占）Problems:9.1–答案RRq=4（時(shí)間片輪轉(zhuǎn)，搶占）012345678910111213141516171819AAABBBBCCBDDDDEEEEDE進(jìn)程ABCDE平均值到達(dá)時(shí)間013912服務(wù)時(shí)間(Ts)35255完成時(shí)間31091920周轉(zhuǎn)時(shí)間(Tr)3-0=310-1=99-3=619-9=1020-12=87.2Tr/Ts11.8321.61.88Problems8:9.1–答案SPN(最短進(jìn)程優(yōu)先，非搶占)012345678910111213141516171819AAACCBBBBBDDDDDEEEEE進(jìn)程ABCDE平均值到達(dá)時(shí)間013912服務(wù)時(shí)間(Ts)35255完成時(shí)間31051520周轉(zhuǎn)時(shí)間(Tr)3-0=310-1=95-3=215-9=620-12=85.6Tr/Ts11.811.21.61.32Problems8:9.1–答案SRT（最短剩余時(shí)間優(yōu)先，搶占）012345678910111213141516171819AAACCBBBBBDDDDDEEEEE進(jìn)程ABCDE平均值到達(dá)時(shí)間013912服務(wù)時(shí)間(Ts)35255完成時(shí)間31051520周轉(zhuǎn)時(shí)間(Tr)3-0=310-1=95-3=215-9=620-12=85.6Tr/Ts11.811.21.61.32Problems8:9.1–答案HRRN(最高響應(yīng)比,R=（w+s）/s,非搶占)012345678910111213141516171819AAABBBBBCCDDDDDEEEEE進(jìn)程ABCDE平均值到達(dá)時(shí)間013912服務(wù)時(shí)間(Ts)35255完成時(shí)間38101520周轉(zhuǎn)時(shí)間(Tr)3-0=38-1=710-3=715-9=620-12=86.2Tr/Ts11.43.51.21.61.74Problems8:9.1–答案FB（反饋，時(shí)間片+動(dòng)態(tài)優(yōu)先級(jí)）(q=1，注意時(shí)間片到了，就緒隊(duì)列沒有進(jìn)程則不降級(jí))012345678910111213141516171819ABACBCABBDDDEEEBDEDE進(jìn)程ABCDE平均值到達(dá)時(shí)間013912服務(wù)時(shí)間(Ts)35255完成時(shí)間71661920周轉(zhuǎn)時(shí)間(Tr)7-0=716-1=156-3=319-9=1020-12=88.6Tr/Ts2.3331.521.62.286Problems8:9.1–答案FBq=2i(注意時(shí)間片到了，就緒隊(duì)列沒有進(jìn)程則不降級(jí))012345678910111213141516171819ABAACBBCBBDDEDDEEDEE進(jìn)程ABCDE平均值到達(dá)時(shí)間013912服務(wù)時(shí)間(Ts)35255完成時(shí)間41081820周轉(zhuǎn)時(shí)間(Tr)4-0=410-1=98-3=518-9=920-12=87.0Tr/Ts1.331.82.51.81.61.81Problems8:9.2–題面考慮以下進(jìn)程集合給出類似于表9.5和圖9.5的分析進(jìn)程ABCD到達(dá)0123處理1919Problems8:9.2–思路參考Problem7Problems8:9.2–答案Problems8:9.2–答案2/2Problems9:11.3–題面

使用與表11.2類似的方式，分析下列磁道請(qǐng)求：27，129，110，186，147，41，10，64，120。初始磁道為100（1）磁頭沿磁道號(hào)減小的方向運(yùn)行（2）磁頭沿磁道號(hào)增大的方向運(yùn)行Problems9:11.3–思路and答案知識(shí)點(diǎn)：各種磁盤調(diào)度算法FIFOSSTFSCANC-SCAN（1）磁頭沿磁道號(hào)減小的方向運(yùn)行FIFO初始磁道為100 27，129，110，186，147，41，10，64，120Next27129110186147411064120AVG越過7310219763910631545661.8SSTF(最短服務(wù)時(shí)間)

初始磁道為100 27，129，110，186，147，41，10，64，120Next11012012914718664412710AVG越過10109183912223141729.1Problems9:11.3–答案SCAN(磁頭沿一個(gè)方向往返，滿足運(yùn)動(dòng)方向上的請(qǐng)求)

初始磁道為100 27，129，110，186，147，41，10，64，120Next64412710110120129147186AVG越過36231417100109183929.6Problems9:11.3–答案C-SCAN（磁頭向一個(gè)方向單向運(yùn)動(dòng)）

初始磁道為100 27，129，110，186，147，41，10，64，120Next64412710186147129120110AVG越過36231417176391891038Problems9:11.3–答案（2）磁頭沿磁道號(hào)增大的方向運(yùn)動(dòng)FIFO,SSTF與磁頭運(yùn)動(dòng)方向無關(guān)，結(jié)果與上題一致SCAN

初始磁道為100 27，129，110，186，147，41，10，64，120Next11012012914718664412710AVG越過10109183912223141729.6Problems9:11.3–答案C-SCAN

初始磁道為100 27，129，110，186，147，41，10，64，120Next11012012914718610274164AVG越過10109183917617142338Problems9:11.3–答案Problems10:–題面Thereissequenceofdisktrackrequests:7562991445016211026198.Assumethatthediskhe