處理機(jī)調(diào)度與死鎖n(參考版)
2025-05-02 12:28本頁面
【正文】 習(xí)題 ? P115： ? 18， 20， 21， 22 。 假設(shè)有 m個資源，每個進(jìn)程最多可申請 k個資源，則系統(tǒng)要想避免死鎖的發(fā)生，允許的最多進(jìn)程數(shù) n為 1+（ mk） /（ k1）。 xW，不會死鎖； (5) x=8/3。 x=W，不會死鎖； (3) x=2。利用資源分配圖舉一個死鎖例子便可。 N=3， W=2； (5) M=6。 N=2， W=2； (3) M=3。當(dāng) M， N， W分別取下列值時，試判斷下列哪些情況會發(fā)生死鎖？為什么？ (1) M=2。 161。161。Pk161。PkU2V2 1V2 2V2 kW2 3 1W2 3 4W2 3 k161。P2P4161。 死鎖的解除 ? 檢測到死鎖后 ， 回退到上一狀態(tài) （ 要進(jìn)行資源剝奪 ， 且需保存以前狀態(tài)的分配信息 ） ， 重新分配 ， 若不行 ， 繼續(xù)回退 …… ， 死鎖的解除（ 2） U1V1 2V1 3V1 kW1 3 2W1 3 4W1 3 kP2P3161。 定理 ：死鎖狀態(tài)的充分條件，資源分配圖不可完全簡化 Work:= available L:={Li| alloci=0∩reqi=0} /*孤立進(jìn)程點 */ For all Li L do Begin For all reqi =work do Begin Work:=work+alloci L=Li∪ L End End Deadlock:= ~(L={p1 … pn}) ： ?(1)剝奪資源。 (4) 如果所有進(jìn)程的 Finish［ i］ =true都滿足， 則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 Finish［ i］ ∶ = true。 ② Need［ i,j］ ≤ Work［ j］； 若找到， 執(zhí)行步驟 (3)， 否則，執(zhí)行步驟 (4)。 74 系統(tǒng)的安全狀態(tài)（ 2） 進(jìn)程 最大需求 已分配 可用 P1 10 5 3 P2 4 2 P3 9 2 安全序列： p2?p1?p3 系統(tǒng)的安全狀態(tài)（ 3） 3安全 — 不安全的轉(zhuǎn)換 ? 上例中，若 P3再申請一臺，則不安全 進(jìn)程 最大需求 已分配 可用 P1 10 5 2 P2 4 2 P3 9 3 1．?dāng)?shù)據(jù)結(jié)構(gòu) available[j]=k: 系統(tǒng)現(xiàn)有 Rj類資源 k個； max[i,j]=k: 進(jìn)程 i需要 Rj的最大數(shù) k個； alloc[i,j]=k: 進(jìn)程 i已得到 Rj類資源 k個； need[i,j]=k: 進(jìn)程 i需要 Rj類資源 k個 有： need[i,j]= max[i,j]－ alloc[i,j] requesti 進(jìn)程 i請求資源數(shù) worki：進(jìn)程 i執(zhí)行完后系統(tǒng)應(yīng)有資源數(shù)（也即可用數(shù)） finish[i]：布爾量，表進(jìn)程 i能否順序完成。 缺點： （ 1）新增資源不便，（原序號已排定） （ 2）資源與進(jìn)程使用順序不同造成浪費(fèi) （ 3）用戶不自由 系統(tǒng)的安全狀態(tài) 在 “ 避免死鎖 ” 方法中的判斷條件 1. 安全狀態(tài) ? 系統(tǒng)按某種順序并發(fā)進(jìn)程都能達(dá)到獲得最大資源而順序完成的序列為安全序列。 摒棄請求和保持條件 全分配，全釋放（ AND同步 p52） 優(yōu)點：簡單且安全 缺點：（ 1）資源嚴(yán)重浪費(fèi) （ 2）延遲進(jìn)程運(yùn)行 摒棄 “ 不剝奪 ” 條件 增加系統(tǒng)開銷，且進(jìn)程前段工作可能失效。 4．解除死鎖：與 “ 檢測 ” 配套。 2．避免死鎖：防止進(jìn)入不安全態(tài)。 P1 P3 S3 S1 P2 S2 圖 314進(jìn)程之間通信時的死鎖 進(jìn)程推進(jìn)順序不當(dāng)引起死鎖。 競爭資源引起死鎖。 圖 311 給出了 A和 B截止的時間點。 對于 A，合適截止時間依次為 60、 80、 100 ? 。 ? 若 A進(jìn)程需在 200ms時完成，其本身運(yùn)行需要 100ms，當(dāng)前時刻是 10ms，則 A的松弛度為： 200－ 100－ 10＝ 90 ? 主要用于可搶占的調(diào)度方式中 ? 在實現(xiàn)該算法時，要求系統(tǒng)中有一個 按松弛度排序的實時任務(wù)就緒隊列，松弛度最低的（數(shù)值小的）任務(wù)排在隊列的前面。 任務(wù) 1 任務(wù)執(zhí)行 → 任務(wù)到達(dá) → 任務(wù) 1 t 圖 39 EDF算法用于非搶占式點的調(diào)度方式 任務(wù) 3 任務(wù) 4 任務(wù) 2 任務(wù) 2 任務(wù) 3 任務(wù) 4 開始截止時間 ： 任務(wù) 1的 任務(wù) 3的 任務(wù) 4的 任務(wù) 2的 結(jié)束 下一步 下一步 最早截止時間優(yōu)先（ EDF） B 101 02 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 1 0 0B 2A 1 A 2 A 3 A 4 A 5A 1最 后 期 限A 2最 后 期 限A 3最 后 期 限A 4最 后 期 限A 5最 后 期 限B 1最 后 期 限B 1最 后 期 限時 間 tA 1 B 2B 1 A 2 B 1 A 3 A 4 B 2 A 5B2A 1A 2A 3A 4 A 5 , B 2B 1錯過B 2B 1 A 2 A 3 A 5A 1錯過A 2A 3A 4錯過A 5 , B 2B 1A 1B2B 1 A 2 B 1 A 3 A 4 B 2 A 5A 1A 2A 3A 4 A 5 , B 2B 1到 達(dá) 時 間 、 執(zhí) 行 時 間和 最 后 期 限固 定 優(yōu) 先 級 調(diào) 度（ A 具 有 較 高 優(yōu) 先 級 ）固 定 優(yōu) 先 級 調(diào) 度（ B 具 有 較 高 優(yōu) 先 級 ）使 用 完 成 最 后 期 限最 早 和 最 后 期 限 調(diào) 度圖 3－ 10 最早截止時間優(yōu)先算法用于搶占調(diào)度方式之例 2. 最低松弛度優(yōu)先 LLF算法 ? 松弛度： ? 根據(jù)任務(wù)緊急（或松弛）的程度，來確定任務(wù)的優(yōu)先級。圖 39給出了該算法用于非搶占式調(diào)度方式示例。 ? 具有快速響應(yīng)外部中斷能力。 處理機(jī)調(diào)度 表 SRT 的調(diào)度性能 WT進(jìn)程 到達(dá)時間Tin 服務(wù)時間Tr 開始時間Ts 結(jié)束時間Tc = 0 3 4 15 8 3 15 8 20 10 TA=3 TB=13 TC=4 TD=14 TE=2 = 8 3 6 4 5 2 2 0 4 6 A B
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1