【正文】 2 A4 B2 A5B1 A2 A3 B2 A5A1B1B1 A2 B1 A3 B2 A4 B2 A5 B2A1 A2B2A3 A4 A5B1最后期限B2最后期限A1最后期限A2最后期限A3最后期限A4最后期限A5最后期限到達時間、執(zhí)行時間和最后期限A1固定優(yōu)先級調(diào)度固定優(yōu)先級調(diào)度A2 B1 A3 A4 A5 ， B2A5 ， B2A4A1( 錯過 )A2 B1 A3( 錯過 )A1 A2 B1( 錯過 )A3 A4 A5 ， B20 10 20 30 40 50 60 70 80 90 100 時間 t /ms使用完成最后期限最早和最后期限調(diào)度(A 有較高優(yōu)先級 )(B 有較高優(yōu)先級 )最早截至?xí)r間優(yōu)先調(diào)度 最后期限 A到達就執(zhí)行 B到達就執(zhí)行 第三章 處理機調(diào)度與死鎖 第四行是采用最早截止時間優(yōu)先算法的時間圖。任務(wù)的緊急程度愈高，為該任務(wù)所賦予的優(yōu)先級就愈高，以使之優(yōu)先執(zhí)行。 第三章 處理機調(diào)度與死鎖 該算法主要用于可搶占調(diào)度方式中。 第三章 處理機調(diào)度與死鎖 圖 311 A和 B任務(wù)每次必須完成的時間 A1A2A3A4A5A6A7A820 40 60 80 100 120 140 160B1B2B3t0第三章 處理機調(diào)度與死鎖 在剛開始時 (t1?=?0)， A1必須在 20 ms時完成，而它本身運行又需 10 ms，可算出 A1的松弛度為 10 ms； B1必須在 50 ms時完成，而它本身運行就需 25 ms，可算出 B1的松弛度為 25 ms，故調(diào)度程序應(yīng)先調(diào)度 A1執(zhí)行。 在 t5?=?45 ms時 ， B1執(zhí)行完成 ， 而此時A3的松弛度已減為 5 ms(即 60??10??45)， 而 B2的松弛度為 30 ms(即 100??25??45)， 于是又應(yīng)調(diào)度 A3執(zhí)行 。 第三章 處理機調(diào)度與死鎖 圖 312 利用 LLF算法進行調(diào)度的情況 t1A1( 10)10 20 30 40 50 60 80t0t1＝ 0B1( 20)t2t370A2( 10) A3( 10) A4( 10)t4t5t6t7t8B1( 5) B2( 15) B2( 10)第三章 處理機調(diào)度與死鎖 小結(jié) ?處理機調(diào)度的基本算法 ?先來先服務(wù) （ FCFS） ?短進程優(yōu)先 （ SPF） ?高優(yōu)先權(quán)調(diào)度 （ FPF ） ?時間片輪轉(zhuǎn)（ RR） ?多級反饋隊列調(diào)度 ?作業(yè)調(diào)度算法 ?先來先服務(wù) （ FCFS） ?短作業(yè)優(yōu)先 （ SJF） ?高優(yōu)先權(quán)調(diào)度（ FPF） ?高響應(yīng)比優(yōu)先（ HRN） 實時調(diào)度 ?最低松弛度優(yōu)先即 LLF(Least Laxity First)算法 第三章 處理機調(diào)度與死鎖 綜合實驗 ?處理機調(diào)度模擬 (先來先服務(wù) （ FCFS）、 短進程優(yōu)先 （ SPF）、高優(yōu)先權(quán)調(diào)度 （ FPF ）、時間片輪轉(zhuǎn)（ RR） ?主存空間和磁盤空間的分配和回收 ?模擬文件系統(tǒng) ?模擬實現(xiàn)資源分配。 即：一組進程中 ， 每個進程都無限等待被該組進程中另一進程所占有的資源 ， 因而永遠無法得到的資源 ， 這種現(xiàn)象稱為進程死鎖 ， 這一組進程就稱為 死鎖進程 。）這時候，很顯然兩兄弟都出發(fā)不了。男朋友也是這樣想的，女朋友給我打了我才給他打！女朋友越來越生氣，她一直沒等到電話，因為男朋友一直沒打給她，為什么不打！因為男朋友沒有接到女朋友的電話！為什么女朋友不打？他一直沒有接到男朋友的電話啊，兩人死鎖了。 圖 314示出了在進程之間通信時形成死鎖的情況 。 第三章 處理機調(diào)度與死鎖 圖 314 進程之間通信時的死鎖 S2P1S3P3S1P2形成環(huán)路引起死鎖 第三章 處理機調(diào)度與死鎖 ? 死鎖的起因 ?進程推進順序不當引起死鎖 1) 進程推進順序合法 在進程 P1和 P2并發(fā)執(zhí)行時 ， 如果按下述兩種順序推進： A1: P1 request (r1) A2: P2 request (r2) B1: P1 request (r2) B2: P2 request (r1) C1: P1 release (r1) C2: P2 release (r2) D1: P1 release (r2) D2: P2 release (r1) 則兩個進程可順利完成，若 A A2或者 A A1則可能發(fā)生死鎖 馬兒光吃草 ,不快跑 第三章 處理機調(diào)度與死鎖 危險區(qū) N A1 B1 C1 D1 P1進展 P2進展 D2 C2 B2 A2 A1: P1 request (r1) A2: P2 request (r2) B1: P1 request (r2) B2: P2 request (r1) C1: P1 release (r1) C2: P2 release (r2) D1: P1 release (r2) D2: P2 release (r1) 產(chǎn)生死鎖的 根本原因 是系統(tǒng)能夠提供的資源個數(shù)比要求的該資源的進程數(shù)少 。（部分分配， 占有申請 ） 第三章 處理機調(diào)度與死鎖 (3) 不剝奪條件 ：指進程已獲得的資源 ， 在未使用完之前 ， 不能被剝奪 ， 只能在使用完時由 自己釋放 。 第三章 處理機調(diào)度與死鎖 處理死鎖的基本方法 不考慮此問題： （鴕鳥政策） 讓死鎖發(fā)生： 允許死鎖發(fā)生，但能檢測出死鎖并實現(xiàn)修復(fù)。預(yù)防死鎖是一種較易實現(xiàn)的方法，已被 廣泛使用 。這種方法只需事先 施加較弱的限制條件 ，便可獲得較高的資源利用率及系統(tǒng)吞吐量，但在實現(xiàn)上有一定的難度。但可通過系統(tǒng)所設(shè)置的檢測機構(gòu)，及時地檢測出死鎖的發(fā)生，并精確地確定與死鎖有關(guān)的進程和資源； 然后，采取適當措施，從系統(tǒng)中將已發(fā)生的死鎖清除掉。常用的實施方法是撤消或掛起一些進程，以便回收一些資源，再將這些資源分配給已處于阻塞狀態(tài)的進程，使之轉(zhuǎn)為就緒狀態(tài)，以繼續(xù)運行?？梢?避免發(fā)生死鎖。當一個已經(jīng)保持了某些資源的進程，再提出新的資源請求而不能立即得到滿足時，必須釋放它已經(jīng)保持了的所有資源，待以后需要時再重新申請。 資源順序分配法 例如，令輸入機的序號為 1，打印機的序號為 2，磁帶機為3，磁盤為 4。 但也存在下述嚴重問題： ?系統(tǒng)中各類資源所分配 (確定 )的序號必須相對穩(wěn)定 ， 這就限制了新類型設(shè)備的增加 。 第三章 處理機調(diào)度與死鎖 系統(tǒng)安全狀態(tài) （ 避免死鎖） 1． 安全狀態(tài) 在 避免死鎖 的方法中，允許進程 動態(tài) 地申請資源，但系統(tǒng)在進行資源分配之前，應(yīng)先計算此次資源分配的安全性。 安全序列 ：進程安全執(zhí)行完的順序 避免死鎖的實質(zhì)在于：系統(tǒng)在進行資源分配時，如何使系統(tǒng)不進入不安全狀態(tài)。假設(shè)在 T0時刻，進程 P P2和P3已分別獲得 5臺、 2臺和 2臺磁帶機，尚有 3臺空閑未分配，如下表所示： 進 程 最大需求 已 分 配 可 用 P 1 10 5 3 P 2 4 2 P 3 9 2 此時已分配 9臺，安全序列： P2， P1， P3 第三章 處理機調(diào)度與死鎖 3． 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換 如果不按照安全序列分配資源，則系統(tǒng)可能會由安全狀態(tài)進入不安全狀態(tài)。 存在安全狀態(tài)，不代表不可能發(fā)生死鎖， 表示的是有解決死鎖的方法存在。 第三章 處理機調(diào)度與死鎖 ?銀行家算法中的數(shù)據(jù)結(jié)構(gòu) (1) 可利用資源向量 Available。 這是一個 n m的矩陣 ， 它定義了系統(tǒng)中 n個進程中的每一個進程對 m類資源的最大需求 。如果 Allocation[i,j]=K， 則表示進程 i當前已分得 R j類資源的數(shù)目為 K。 上述三個矩陣間存在下述關(guān)系： Need[i, j]=Max[i, j]Allocation[i, j] 第三章 處理機調(diào)度與死鎖 銀行家算法避免死鎖 算法： 開始 申請量 =尚需 量 y n n y 申請量 〈 =系統(tǒng)剩余 安全性控制 分配 進入下一步驟 預(yù)分配作廢 阻塞 安全 首先為申請預(yù)分配資源 錯誤 預(yù)測 n y 第三章 處理機調(diào)度與死鎖 例 . 多項資源的安全序列 （ a）初始狀態(tài) Max Matrix 第三章 處理機調(diào)度與死鎖 Max Matrix （ a） P2運行完成 第三章 處理機調(diào)度與死鎖 Max Matrix Max Matrix 第三章 處理機調(diào)度與死鎖 例 . 進入不安全狀態(tài) （ a）初始狀態(tài) Max Matrix 第三章 處理機調(diào)度與死鎖 例 . 進入不安全狀態(tài) Max Matrix （ b） P1申請 1個 R 1個 R3 第三章 處理機調(diào)度與死鎖 2．銀行家算法 設(shè) Request i是進程 Pi的請求向量，如果 Request i[j]=K，表示進程 P i需要 K個 R j類型的資源。若安全，才正式將資源分配給進程 Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進程 Pi等待。 第三章 處理機調(diào)度與死鎖 (2) 從進程集合中找到一個能滿足下述條件的進程： ① Finish[i]=false； ② Need[i,j]≤Work[j] ；若找到 ， 執(zhí)行步驟 (3)， 否則 ，執(zhí)行步驟 (4)。 圖 317 T0時刻的安全序列 W ork N eed A l l ocat i on W ork +A l l ocat i on 資源 情況 進 程 A B C A B C A B C A B C Fini sh P 1 3 3 2 1 2 2 2 0 0 5 3 2 t rue P 3 5 3 2 0 1 1 2 1 1 7 4 3 t rue P 4 7 4 3 4 3 1 0 0 2 7 4 5 t rue P 2 7 4 5 6 0 0 3 0 2 10 4 7 t rue P 0 10 4 7 7 4 3 0 1 0 10 5 7 tr ue {P1， P3， P4， P2， P0}是安全序列嗎？ 第三章 處理機調(diào)度與死鎖 (2) ?P1請求資源： P1發(fā)出請求向量 Request1(1， 0， 2)， 系統(tǒng)按銀行家算法進行檢查： ① Request1(1， 0， 2)≤Need1(1， 2， 2) ② Request1(1， 0， 2)≤Available1(3， 3， 2) ③ 系統(tǒng)先假定可為 P1分配資源，并修改 Available，Allocation1和 Need1向量，由此形成的資源變化情況如圖 316中的圓括號所示。 (4) ?P0請求資源： P0發(fā)出請求向量 Requst0(0， 2， 0)， 系統(tǒng)按銀行家算法進行檢查： ① Request0(0， 2， 0)≤Need0(7， 4， 3)； ② Request0(0， 2， 0)≤Available(2， 3， 0)； ③ 系統(tǒng)暫時先假定可為 P0分配資源，并修改有關(guān)數(shù)據(jù)，如圖 3