第三章處理機(jī)的調(diào)度和死鎖-文庫吧資料
2024-10-06 14:50本頁面
【正文】 0， 2， 0）后的情況（不安全） 處理機(jī)調(diào)度與死鎖 ? ? p1 p2 處理機(jī)調(diào)度與死鎖 ? 簡化資源分配圖 若能完全簡化則消去所有的邊。 ? 能找到安全序列的狀態(tài)為安全狀態(tài)。 處理機(jī)調(diào)度與死鎖 死鎖預(yù)防和避免 ? 死鎖預(yù)防 四、摒棄 “ 環(huán)路 ” 條件 有序資源分配法：為資源編號(hào)，申請(qǐng)時(shí)需按編號(hào)進(jìn)行。 處理機(jī)調(diào)度與死鎖 死鎖預(yù)防和避免 ? 死鎖預(yù)防 ? 一、互斥條件是資源固有屬性，不能避免。 ?3．檢測：檢測到死鎖再清除。 2 1 3 D P2Req(R2) P2Req(R1) P1Req(R1) P1Req(R2) P2Rel(R2) P2Rel(R1) P1Rel(R1) P1Rel(R2) 4 處理機(jī)調(diào)度與死鎖 產(chǎn)生死鎖的必要條件 ?1．互斥條件（資源的臨界性） ?2．請(qǐng)求和保持條件 ?3．不剝奪條件 ?4．環(huán)路等待 處理機(jī)調(diào)度與死鎖 ?1．預(yù)防；破壞 4個(gè)條件之一：有效，使資源利用率低。 ? 1．可剝奪（ CPU、內(nèi)存，）和非剝奪性（打印機(jī)，磁帶機(jī)）資源 ? 2．競爭非剝奪性資源 —— 可造成死鎖 p1 p2 R1 R2 處理機(jī)調(diào)度與死鎖 ?3．競爭臨時(shí)性資源 ? 臨時(shí)性資源是指由一個(gè)進(jìn)程產(chǎn)生，被另一個(gè)進(jìn)程使用一段時(shí)間后便無用的資源。 ?主要用于大型計(jì)算，實(shí)時(shí)系統(tǒng) 處理機(jī)調(diào)度與死鎖 ?。 處理機(jī)調(diào)度與死鎖 應(yīng)用程序A 應(yīng)用程序 B Cpu1 線程 1 線程 1 Cpu2 線程 2 空閑 Cpu3 線程 3 空閑 Cpu4 線程 4 空閑 時(shí)間 1/2 1/2 浪費(fèi) % 應(yīng)用程序A 應(yīng)用程序 B Cpu1 線程 1 線程 1 Cpu2 線程 2 空閑 Cpu3 線程 3 空閑 Cpu4 線程 4 空閑 時(shí)間 4/5 1/5 浪費(fèi) 15% 處理機(jī)調(diào)度與死鎖 ?引入：多處理機(jī)系統(tǒng)，每個(gè)處理已不再屬寶貴資源。 （ 2）每次分配一組 CPU，減少了調(diào)度頻率。 ? 快速任務(wù)分派 處理機(jī)調(diào)度與死鎖 ?1非搶占式調(diào)度算法 ? 時(shí)間片輪轉(zhuǎn) 秒級(jí) ? 非搶占優(yōu)先權(quán)（協(xié)同） 秒 ~毫秒級(jí) ?2搶占式調(diào)度算法 ? 時(shí)鐘中斷搶占優(yōu)先權(quán) 毫秒級(jí) ? 基于搶占點(diǎn)搶占 ? 立即搶占 immediate preemption 毫秒 ~微秒級(jí) ? 只要不在臨界區(qū)即搶占（中斷引發(fā)） 進(jìn)程 1 進(jìn)程 2 進(jìn)程 n 實(shí)時(shí)進(jìn)程 調(diào)度時(shí)間 實(shí)時(shí)進(jìn)程要求調(diào)度 調(diào)度實(shí)時(shí)進(jìn)程運(yùn)行 a 非搶占輪轉(zhuǎn)調(diào)度 當(dāng)前進(jìn)程 實(shí)時(shí)進(jìn)程 實(shí)時(shí)進(jìn)程要求調(diào)度 當(dāng)前進(jìn)程運(yùn)行完成 b 非搶占優(yōu)先權(quán)調(diào)度 調(diào)度時(shí)間 c 基于時(shí)鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度 當(dāng)前進(jìn)程 實(shí)時(shí)進(jìn)程 實(shí)時(shí)進(jìn)程要求調(diào)度 搶占時(shí)刻（其它中斷） b 立即搶占優(yōu)先權(quán)調(diào)度 當(dāng)前進(jìn)程 實(shí)時(shí)進(jìn)程 實(shí)時(shí)進(jìn)程要求調(diào)度 時(shí)鐘中斷到達(dá)時(shí) 調(diào)度時(shí)間 調(diào)度時(shí)間 處理機(jī)調(diào)度與死鎖 ? EDF（ earliest deadline first)算法 ? 根據(jù)任務(wù)的截止時(shí)間來確定任務(wù)的優(yōu)先級(jí) ? 截止時(shí)間越早，優(yōu)先級(jí)越高 ? 可以是搶占式或非搶占式 處理機(jī)調(diào)度與死鎖 最早截止時(shí)間優(yōu)先 EDF例 1 3 4 2 1 3 4 2 1 2 3 4 t 開始截止時(shí)間 任務(wù)到達(dá) 任務(wù)執(zhí)行 圖 3－ 7 EDF算法用于非搶占調(diào)度方式 處理機(jī)調(diào)度與死鎖 2. 最低松弛度優(yōu)先 LLF算法 ?松弛度： ? 若 A進(jìn)程需在 200ms時(shí)完成，其本身運(yùn)行需要 100ms，當(dāng)前時(shí)刻是 10ms，則 A的松弛度為： 200－ 100－ 10＝ 90 ? 主
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1