第三章處理機(jī)的調(diào)度和死鎖(編輯修改稿)
2024-11-03 14:50 本頁面
【文章內(nèi)容簡介】 a 非搶占輪轉(zhuǎn)調(diào)度 當(dāng)前進(jìn)程 實時進(jìn)程 實時進(jìn)程要求調(diào)度 當(dāng)前進(jìn)程運(yùn)行完成 b 非搶占優(yōu)先權(quán)調(diào)度 調(diào)度時間 c 基于時鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度 當(dāng)前進(jìn)程 實時進(jìn)程 實時進(jìn)程要求調(diào)度 搶占時刻（其它中斷） b 立即搶占優(yōu)先權(quán)調(diào)度 當(dāng)前進(jìn)程 實時進(jìn)程 實時進(jìn)程要求調(diào)度 時鐘中斷到達(dá)時 調(diào)度時間 調(diào)度時間 處理機(jī)調(diào)度與死鎖 ? EDF（ earliest deadline first)算法 ? 根據(jù)任務(wù)的截止時間來確定任務(wù)的優(yōu)先級 ? 截止時間越早，優(yōu)先級越高 ? 可以是搶占式或非搶占式 處理機(jī)調(diào)度與死鎖 最早截止時間優(yōu)先 EDF例 1 3 4 2 1 3 4 2 1 2 3 4 t 開始截止時間 任務(wù)到達(dá) 任務(wù)執(zhí)行 圖 3－ 7 EDF算法用于非搶占調(diào)度方式 處理機(jī)調(diào)度與死鎖 2. 最低松弛度優(yōu)先 LLF算法 ?松弛度： ? 若 A進(jìn)程需在 200ms時完成，其本身運(yùn)行需要 100ms，當(dāng)前時刻是 10ms，則 A的松弛度為： 200－ 100－ 10＝ 90 ? 主要用于可搶占的調(diào)度方式中 ? 例： A1 A2 A3 A4 A5 A6 A7 A8 B1 B2 B3 0 20 40 60 80 100 120 140 160 t 圖 3－ 8 A/B任務(wù)每次必須完成的時間 處理機(jī)調(diào)度與死鎖 最低松弛度優(yōu)先 LLF算法 (2) A1(10) A2(10) A3(10) A4(10) t 0 10 20 30 40 50 60 70 80 t1=0 B1(20) B1(5) B2(15) B2(10) t1 t2 t3 t4 t5 t6 t7 t8 處理機(jī)調(diào)度與死鎖 ? MPS和松弛耦合 MPS ? 緊密耦合 ? 共享 RAM和 I/O ? 高速總線和交叉開關(guān)連接 ? 松弛耦合 ? 獨立 RAM和 I/O ? 通道和通信線路連接 ? ? 處理器是否結(jié)構(gòu)相同 處理機(jī)調(diào)度與死鎖 ? ? 靜態(tài)分配 ? 動態(tài)分配 ? 可防止系統(tǒng)中多個處理器忙閑不均 ? SMP中進(jìn)程分配方式 ? 進(jìn)程調(diào)度在主處理器上執(zhí)行 ? 有潛在的不可靠性 處理機(jī)調(diào)度與死鎖 （線程）調(diào)度方式 ? ? 各個處理機(jī)自行在就緒隊列中取任務(wù)。 ? 特點；簡單，分布式調(diào)度，調(diào)度算法可采用前述方法，多個 CPU利用率都不錯（不會閑） ? 但： ? 瓶頸問題，（單隊列） ? 低效性；（需拷貝現(xiàn)場） ? 線程切換頻繁（當(dāng)線程合作時 ,各線程并行的條件不容易滿足） 處理機(jī)調(diào)度與死鎖 ?優(yōu)點： （ 1）對相互合作的進(jìn)（線）程組調(diào)度，可以減小切換，減小系統(tǒng)開銷。 （ 2）每次分配一組 CPU，減少了調(diào)度頻率。 ?分配時間 （ 1）面向程序 （ 2）面向線程：使處理機(jī)利用率更高。 處理機(jī)調(diào)度與死鎖 應(yīng)用程序A 應(yīng)用程序 B Cpu1 線程 1 線程 1 Cpu2 線程 2 空閑 Cpu3 線程 3 空閑 Cpu4 線程 4 空閑 時間 1/2 1/2 浪費 % 應(yīng)用程序A 應(yīng)用程序 B Cpu1 線程 1 線程 1 Cpu2 線程 2 空閑 Cpu3 線程 3 空閑 Cpu4 線程 4 空閑 時間 4/5 1/5 浪費 15% 處理機(jī)調(diào)度與死鎖 ?引入：多處理機(jī)系統(tǒng)，每個處理已不再屬寶貴資源。 ?特點：每個進(jìn)（線）程專用處理機(jī)，使其切換小，提高效率。 ?主要用于大型計算，實時系統(tǒng) 處理機(jī)調(diào)度與死鎖 ?。 ?一、競爭資源引起死鎖。 ? 1．可剝奪（ CPU、內(nèi)存，）和非剝奪性（打印機(jī)，磁帶機(jī)）資源 ? 2．競爭非剝奪性資源 —— 可造成死鎖 p1 p2 R1 R2
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1