計(jì)算機(jī)操作系統(tǒng)(大學(xué)課程)第三章(參考版)
2024-10-21 20:15本頁(yè)面
【正文】 定理：死鎖狀態(tài)的充分條件，資源分配圖不可完全簡(jiǎn)化 ? ： Work= available L:={Li| alloci=0 reqi=0} (孤立進(jìn)程點(diǎ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}) ?解除 ?檢測(cè)到死鎖后 ， 回退到上一狀態(tài) （ 要進(jìn)行資源剝奪 ，且需保存以前狀態(tài)的分配信息 ） ， 重新分配 ， 若不行 ， 繼續(xù)回退 …… ， 。 (2)P4到達(dá)系統(tǒng) ,最多需要 60個(gè)存儲(chǔ)單元 ,最初需要 35個(gè)單元 。 系統(tǒng)的安全狀態(tài)（ 2） ? （ 共有 12個(gè)該類資源） 進(jìn)程 最大需求 已分配 可用 P1 10 5 3 P2 4 2 P3 9 2 安全序列： p2?p1?p3 系統(tǒng)的安全狀態(tài)（ 3） ? 3 安全 —— 不安全的轉(zhuǎn)換 ? 上例中，若 P3再申請(qǐng)一臺(tái)，則不安全 進(jìn)程 最大需求 已分配 可用 P1 10 5 2 P2 4 2 P3 9 3 ?安全狀態(tài) 避免死鎖 ?不安全狀態(tài) 可能進(jìn)入死鎖 ?不安全狀態(tài)是否必然導(dǎo)致系統(tǒng)進(jìn)入死鎖？ ?1．?dāng)?shù)據(jù)結(jié)構(gòu) ? available[j]=k: 系統(tǒng)現(xiàn)有 Rj類資源 k個(gè)； ? max[i,j]=k: 進(jìn)程 i需要 Rj的最大數(shù) k個(gè)； ? alloc[i,j]=k: 進(jìn)程 i已得到 Rj類資源 k個(gè)； ? need[i,j]=k: 進(jìn)程 i需要 Rj類資源 k個(gè) ? 有： need[i,j]= max[i,j]－ alloc[i,j] ? Requesti：進(jìn)程 i請(qǐng)求資源數(shù) ? worki：進(jìn)程 i執(zhí)行完后系統(tǒng)應(yīng)有資源數(shù)（也即可用數(shù)） ? finish[i]：布爾量，表進(jìn)程 i能否順序完成。 ?系統(tǒng)中描述資源所需的數(shù)據(jù)結(jié)構(gòu) 某類資源： Maxi：某進(jìn)程所需的最大資源數(shù) Allocationi：某進(jìn)程已分配的資源數(shù) Needi：某進(jìn)程還需要的資源數(shù) Available i：系統(tǒng)中可用的資源數(shù) Maxi= Allocationi + Needi Available i 比較 ?1. 安全狀態(tài) ? 按某種順序并發(fā)進(jìn)程都能達(dá)到獲得最大資源而順序完成的序列為安全序列。 死鎖預(yù)防和避免 ? 死鎖預(yù)防 四、摒棄 “ 環(huán)路 ” 條件 有序資源分配法：為資源編號(hào)，申請(qǐng)時(shí)需按編號(hào)進(jìn)行。 死鎖預(yù)防和避免 ? 死鎖預(yù)防 ? 一、互斥條件是資源固有屬性，不能避免。 ?3．檢測(cè)：檢測(cè)到死鎖再清除。 2 1 3 D P2Req(R2) P2Req(R1) P1Req(R1) P1Req(R2) P2Rel(R2) P2Rel(R1) P1Rel(R1) P1Rel(R2) 4 產(chǎn)生死鎖的必要條件 ?1．互斥條件（資源的臨界性） ?2．請(qǐng)求和保持條件 ?3．不剝奪條件 ?4．環(huán)路等待 ?1．預(yù)防；破壞 4個(gè)條件之一：有效，使資源利用率低。 ? 1．可剝奪（ CPU、內(nèi)存，）和非剝奪性（打印機(jī)，磁帶機(jī)）資源 ? 2．競(jìng)爭(zhēng)非剝奪性資源 —— 可造成死鎖 p1 p2 R1 R2 ?3．競(jìng)爭(zhēng)臨時(shí)性資源 ? 臨時(shí)性資源是指由一個(gè)進(jìn)程產(chǎn)生，被另一個(gè)進(jìn)程使用一段時(shí)間后便無(wú)用的資源。 ?主要用于大型計(jì)算，實(shí)時(shí)系統(tǒng) ?例 考慮 5個(gè)進(jìn)程 P1,P2,P3,P4,P5,見(jiàn)表 先度越小 ,優(yōu)先級(jí)越高 .試描述在采用下述幾種調(diào)度算法時(shí)各個(gè)進(jìn)程的運(yùn)行過(guò)程 .并計(jì)算采用每種算法時(shí)的進(jìn)程平均周轉(zhuǎn)時(shí)間 .假設(shè)忽略進(jìn)程的調(diào)度時(shí)間 . 先來(lái)先服務(wù)調(diào)度算法 時(shí)間片輪轉(zhuǎn)調(diào)度算法 (時(shí)間片為 1ms) 非剝奪式 SJF調(diào)度算法 剝奪式優(yōu)先級(jí)調(diào)度算法 表 1 進(jìn)程 創(chuàng)建時(shí)間 運(yùn)行時(shí)間 (ms) 優(yōu)先級(jí) P1 0 3 3 P2 2 6 5 P3 4 4 1 P4 6 5 2 P5 8 2 4 解 : (1) FCFS調(diào)度算法 ,進(jìn)程的運(yùn)行過(guò)程如圖所示 : (2) 時(shí)間片輪轉(zhuǎn)調(diào)度算法 ,進(jìn)程的運(yùn)行情況如圖所示 : 0~1:p1 1~2:p2p1 2~3:p1p2 3~4:p3p2p1 4~5:p3p2 5~6:p4p2p3 6~7:p3p4p2 7~8:p5p2p3p4
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1