ouc操作系統(tǒng)第三章處理機(jī)調(diào)度與死鎖-wenkub
2023-05-21 19:17:14 本頁(yè)面
【正文】 家算法舉例 ? 五個(gè)進(jìn)程｛ P0, P1, P2, P3, P4｝和三類資源｛ A, B, C｝，各種資源的數(shù)量分別為 7，在 T0時(shí)刻的資源分配情況如圖所示 56 57 1. T0時(shí)刻的安全性： 2. P1請(qǐng)求資源 ? P1發(fā)出請(qǐng)求向量 Request1(1， 0， 2)，系統(tǒng)按銀行家算法進(jìn)行檢查 ① Request1(1, 0, 2)≤Need1(1, 2, 2) ② Request1(1, 0, 2)≤Available1 (3, 3, 2) ③ 系統(tǒng)先假定可為 P1分配資源，并修改 Available, Allocation1和 Need1向量，由此形成的資源變化情況如圖 中的圓括號(hào)所示 ④ 再利用安全性算法檢查此時(shí)系統(tǒng)是否安全 58 59 P1申請(qǐng)資源時(shí)的安全性檢查 存在安全序列： (P1， P3， P4， P0， P2) 3. P4請(qǐng)求資源 ? P4發(fā)出請(qǐng)求向量 Request4(3， 3， 0)，系統(tǒng)按銀行家算法進(jìn)行檢查 ① Request4(3, 3, 0)≤Need4(4, 3, 1)。 若找到， 執(zhí)行步驟 3。 ② Finish[1..n] ? 系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。 Need［ i,j］ := Need［ i,j］ Requesti［ j］ 。 ? 若是，就可以分配； ? 否則，該申請(qǐng)暫不予滿足 48 49 1. 銀行家算法中的數(shù)據(jù)結(jié)構(gòu) ① 可利用資源向量 Available[1… m] ? 表示 m種資源中每種可供使用的數(shù)量 ， 初始值是系統(tǒng)中每類資源的全部數(shù)量 Available［ j］ =K 表示目前資源 j 有 K 個(gè)可供使用 ② 最大需求矩陣 Max[1..n,1..m] ? 表示 n個(gè)進(jìn)程中的每個(gè)進(jìn)程對(duì) m種資源的最大需求量 Max［ i,j］ =K 表示進(jìn)程 i 對(duì)資源 j 的最大需求量為 K ③ 已分配矩陣 Allocation[1..n,1..m] ○ 每種資源已分配給每個(gè)進(jìn)程的數(shù)量 Allocation［ i,j］ =K, 進(jìn)程 i當(dāng)前已獲得資源 j 的數(shù)目為 K ④ 需求矩陣 Need[1..n,1..m] ○ 每個(gè)進(jìn)程還需要資源的數(shù)量 Need［ i,j］ =K, 表示進(jìn)程 i還需要 K個(gè)資源 j ，才能執(zhí)行完 50 ? 數(shù)據(jù)結(jié)構(gòu)的小結(jié) ① Available［ j］：目前資源 j可供使用的數(shù)量 ② Max［ i,j］：進(jìn)程 i需要資源 j 的最大數(shù)量 ③ Allocation［ i,j］：進(jìn)程 i當(dāng)前已獲得資源 j的數(shù)量 ④ Need［ i,j］：進(jìn)程 i還需要多少資源 j，才能執(zhí)行完 51 ?所以， Need［ i,j］ = Max［ i,j］ Allocation［ i,j］ 52 2. 銀行家算法 ? 設(shè)向量 Requesti[1...m] ? 如果 Requesti［ j］ =K， 表示進(jìn)程 Pi需要 K個(gè)資源 j ? Pi申請(qǐng)資源時(shí) ， OS如下進(jìn)行檢查： ① 如果 Requesti［ j］ ≤ Need［ i,j］ ， 執(zhí)行下一步；否則認(rèn)為出錯(cuò) ， 因?yàn)樗枰馁Y源數(shù)已超過(guò)它所宣布的最大值 。 ? 產(chǎn)生死鎖的原因 ① 競(jìng)爭(zhēng)資源 ○ 由于系統(tǒng)中的資源不夠進(jìn)程用的，可能引起對(duì)資源的競(jìng)爭(zhēng)而死鎖 ② 進(jìn)程間推進(jìn)順序非法 ○ 進(jìn)程在請(qǐng)求和釋放資源時(shí)，順序不當(dāng) 34 ① 競(jìng)爭(zhēng)資源引起死鎖 ? 兩個(gè)概念 ○ 可剝奪資源 ? 進(jìn)程獲得該種資源后，還可被剝奪 (CPU、內(nèi)存 ) ○ 非可剝奪資源 ? 一旦獲得，用完后才能被收回 (打印機(jī) ) 35 ? 競(jìng)爭(zhēng)非剝奪性資源 36 I/O設(shè)備共享時(shí)的死鎖情況 ? 競(jìng)爭(zhēng)非剝奪性資源 ○ 臨時(shí)性資源 ?一個(gè)進(jìn)程產(chǎn)生，被另一個(gè)用了一段時(shí)間后便無(wú)用的資源 (如：消息 ) 37 進(jìn)程之間通信時(shí)的死鎖 38 圖 314 進(jìn)程推進(jìn)順序?qū)λ梨i的影響 Rel(R1) Rel(R2) Req(R1) Req(R2) Req(R1) Req(R2) Rel(R1) Rel(R2) P2 P1 ② ① ④ ③ ② 進(jìn)程推進(jìn)順序不當(dāng)引起死鎖 D 不安全區(qū) 產(chǎn)生死鎖的必要條件 ① 互斥條件 ○ 進(jìn)程在使用某資源時(shí)，不允許其他進(jìn)程使用 ② 請(qǐng)求和保持條件 ○ 進(jìn)程已保持至少一個(gè)資源，請(qǐng)求另一個(gè)資源時(shí)無(wú)法獲得，便阻塞，但又不放棄已占用的資源 ③ 不剝奪條件 ○ 資源使用完前，不允許剝奪，直至其用完 ④ 環(huán)路等待條件 ○ 發(fā)生死鎖，一定會(huì)有“ 進(jìn)程 資源”環(huán)形鏈 ? 注：只有四個(gè)條件同時(shí)滿足時(shí)，才會(huì)死鎖 39 處理死鎖的基本方法 ① 預(yù)防死鎖 ? 設(shè)置限制條件，破壞四個(gè)條件中的一個(gè)或幾個(gè) ? 簡(jiǎn)單易行，但限制條件往往較嚴(yán)格，影響效率 ② 避免死鎖 ? 動(dòng)態(tài)分配資源時(shí)，防止系統(tǒng)進(jìn)入不安全狀態(tài) ? 限制條件不必很苛刻，但實(shí)現(xiàn)較難 ③ 檢測(cè)死鎖 ? 不用任何限制條件，也不檢查系統(tǒng)是否進(jìn)入安全區(qū)。用于發(fā)生外部中斷的緊急任務(wù) 27 28 實(shí)時(shí)進(jìn)程調(diào)度 29 常用的幾種實(shí)時(shí)調(diào)度算法 1. 最早截止時(shí)間優(yōu)先 (EDF,Earliest Deadline First)算法 ? 根據(jù)開始截止時(shí)間確定優(yōu)先級(jí) ? 越早，優(yōu)先級(jí)越高 ? 就緒隊(duì)列按優(yōu)先級(jí)排序 ? 可用于搶占、非搶占調(diào)度 30 EDF算法用于非搶占調(diào)度方式 開始截止時(shí)間： 3早于 2， 4早于 2 31 2. 最低松弛度優(yōu)先 (LLF, Least Laxity First)算法 ? 主要用于 搶占調(diào)度方式 ? 根據(jù)任務(wù)緊急 (或松弛 )的程度，松弛度越低 (緊急度越高 )，優(yōu)先級(jí)越高 松弛度 = 完成截止時(shí)間 – 剩余運(yùn)行時(shí)間 當(dāng)前時(shí)間 32 A和 B任務(wù)每次必須完
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1