【正文】 1A2A3A4A5A6A7A820 40 60 80 1 0 0 1 2 0 1 4 0 1 6 0B1B2B3t0A每隔 20MS執(zhí)行一次，執(zhí)行時(shí)間為 10MS B每隔 50MS執(zhí)行一次，執(zhí)行時(shí)間為 25MS 第三章 處理機(jī)調(diào)度與死鎖 松弛度 =必須完成時(shí)間 其本身的運(yùn)行時(shí)間 當(dāng)前時(shí)間 第三章 處理機(jī)調(diào)度與死鎖 利用 ELLF算法進(jìn)行調(diào)度的情況 t 1 A 1 (10) 10 20 30 40 50 60 80 t 0 t 1 =0 B 1 (15) t 2 t 3 70 A 2 (10) A 3 (5) A 4 (10) t 4 t 5 t 6 t 7 t 8 B 1 (5) B 2 (20) B 2 (10) 第三章 處理機(jī)調(diào)度與死鎖 產(chǎn)生死鎖的原因和必要條件 死鎖問題的提出 死鎖是指計(jì)算機(jī)系統(tǒng)和進(jìn)程所處的一種狀態(tài)。 任務(wù)的緊急程度愈高 ， 為該任務(wù)所賦予的優(yōu)先級(jí)就愈高 ， 以使之優(yōu)先執(zhí)行 。 第三章 處理機(jī)調(diào)度與死鎖 等待另一個(gè)搶占點(diǎn)調(diào)度時(shí)間搶占點(diǎn)當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程的請求實(shí)時(shí)進(jìn)程基于時(shí)鐘搶占的優(yōu)先權(quán)搶占調(diào)度 第三章 處理機(jī)調(diào)度與死鎖 當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程的請求實(shí)時(shí)進(jìn)程搶占當(dāng)前進(jìn)程并立即執(zhí)行調(diào)度時(shí)間實(shí)時(shí)進(jìn)程立即搶占優(yōu)先權(quán)調(diào)度 第三章 處理機(jī)調(diào)度與死鎖 常用的幾種實(shí)時(shí)調(diào)度算法 1. 最早截止時(shí)間優(yōu)先即 EDF(Earliest Deadline First)算法 根據(jù)任務(wù)的開始截止時(shí)間或完成截止時(shí)間來確定任務(wù)的優(yōu)先級(jí)，截止時(shí)間越早，其優(yōu)先級(jí)越高 最早截止時(shí)間優(yōu)先調(diào)度算法有搶占式和非搶占式 第三章 處理機(jī)調(diào)度與死鎖 1 3 4 2開始截止時(shí)間任務(wù)執(zhí)行任務(wù)到達(dá)1 2 3 41 3 4 2t1）非搶占式調(diào)度用于非周期性實(shí)時(shí)任務(wù) 第三章 處理機(jī)調(diào)度與死鎖 2） 搶占式調(diào)度方式用于周期實(shí)時(shí)任務(wù) 假如在一個(gè)實(shí)時(shí)系統(tǒng)中 ， 有兩個(gè)周期性實(shí)時(shí)任務(wù) A和 B， 任務(wù) A要求每 20 ms執(zhí)行一次 ， 執(zhí)行時(shí)間 為 10 ms；任務(wù) B只要求每 50 ms執(zhí)行一次 ， 執(zhí)行 時(shí)間為 25 ms。 第三章 處理機(jī)調(diào)度與死鎖 實(shí)時(shí)進(jìn)程的請求實(shí)時(shí)進(jìn)程加到運(yùn)行隊(duì)列中等待下一執(zhí)行片段調(diào)度時(shí)間時(shí)鐘進(jìn)程 1 進(jìn)程 2 進(jìn)程 n 實(shí)時(shí)進(jìn)程?非搶占時(shí)間片輪轉(zhuǎn)調(diào)度 第三章 處理機(jī)調(diào)度與死鎖 當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程的請求 實(shí)時(shí)進(jìn)程加到運(yùn)行隊(duì)列頭部調(diào)度時(shí)間實(shí)時(shí)進(jìn)程當(dāng)前進(jìn)程阻塞或完成非搶占式 優(yōu)先權(quán)調(diào)度 第三章 處理機(jī)調(diào)度與死鎖 2. 搶占式調(diào)度算法 (1) 基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法。 第三章 處理機(jī)調(diào)度與死鎖 實(shí)時(shí)調(diào)度算法的分類 1. 非搶占式調(diào)度算法 (1) 非搶占式輪轉(zhuǎn)調(diào)度算法。 第三章 處理機(jī)調(diào)度與死鎖 2. 系統(tǒng)處理能力強(qiáng) 3. 采用搶占式調(diào)度機(jī)制 4. 具有快速切換機(jī)制 (1) 對外部中斷的快速響應(yīng)能力。 (4) 資源要求。 (2) 開始截止時(shí)間和完成截止時(shí)間。 (3) 長批處理作業(yè)用戶 。 第三章 處理機(jī)調(diào)度與死鎖 Q=1（每級(jí)反饋隊(duì)列每一級(jí)時(shí)間片為 1） 1 1 2 1 3 2 4 3 5 4 5 2 3 4 2 3 4 2 4 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 T=1/5（ 4+18+12+13+3） = W=1/5（ ++++） = 第三章 處理機(jī)調(diào)度與死鎖 Q=2**N（每級(jí)反饋隊(duì)列每一級(jí)時(shí)間片以 2冪次方遞增） 1 1 2 1 3 2 2 4 5 3 3 4 4 5 2 2 2 3 4 4 T=1/5（ 4+15+14+14+6） = W=1/5（ ++++） = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 第三章 處理機(jī)調(diào)度與死鎖 特點(diǎn)：吞吐量不定，消耗可能高、有利于 偏重 I/O進(jìn)程，可能會(huì)饑餓 第三章 處理機(jī)調(diào)度與死鎖 多級(jí)反饋隊(duì)列調(diào)度算法的性能 (1) 終端型作業(yè)用戶 。 B類不受限制。 ? 最短剩余時(shí)間優(yōu)先調(diào)度是搶占算法。 新加入的特性是附加一個(gè) FCFS策略隊(duì)列來收集從 I/O等待中釋放的進(jìn)程。 第三章 處理機(jī)調(diào)度與死鎖 Q=4（時(shí)間片為 4） 作業(yè) 1 作業(yè) 2 作業(yè) 3 作業(yè) 4 作業(yè) 2 作業(yè) 5 作業(yè) 4 0 3 7 11 15 17 19 20 T=1/5（ 3+15+7+14+11） = W=1/5（ ++++） = 第三章 處理機(jī)調(diào)度與死鎖 Q=1（時(shí)間片為 1） 1 2 1 2 3 2 4 3 2 5 4 3 2 5 4 3 2 4 4 0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 T=1/5（ 4+16+13+14+7） = W=1/5（ ++++） = 第三章 處理機(jī)調(diào)度與死鎖 RR算法主要用于分時(shí)系統(tǒng)或事務(wù)處理系統(tǒng)，可保 證對各終端用戶的及時(shí)響應(yīng)。 時(shí)間片輪轉(zhuǎn)調(diào)度算法是搶占算法。 (3) 對于長作業(yè) ， 作業(yè)的優(yōu)先級(jí)可以隨等待時(shí)間的增加而提高 ， 當(dāng)其等待時(shí)間足夠長時(shí) ， 其優(yōu)先級(jí)便可升到很高 ， 從而也可獲得處理機(jī) 。 據(jù)此 ， 又可表示為： 要求服務(wù)時(shí)間響應(yīng)時(shí)間要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間優(yōu)先權(quán) ???第三章 處理機(jī)調(diào)度與死鎖 (1) 如果作業(yè)的等待時(shí)間相同 ， 則要求服務(wù)的時(shí)間愈短 ， 其優(yōu)先權(quán)愈高 ， 因而該算法有利于短作業(yè) 。 當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時(shí) ， 如果再規(guī)定當(dāng)前進(jìn)程的優(yōu)先權(quán)以速率 b下降 ， 則可防止一個(gè)長作業(yè)長期地壟斷處理機(jī) 。 若所有的進(jìn)程都具有相同的優(yōu)先權(quán)初值 ， 則顯然是最先進(jìn)入就緒隊(duì)列的進(jìn)程 ， 將因其動(dòng)態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲得處理機(jī) ， 此即 FCFS算法 。 第三章 處理機(jī)調(diào)度與死鎖 4) 動(dòng)態(tài)優(yōu)先權(quán)是指 ， 在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán) ， 是可以隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變的 ， 以便獲得更好的調(diào)度性能 。 (2) 進(jìn)程對資源的需求。 只是具體用法各異：有的系統(tǒng)用“ 0”表示最高優(yōu)先權(quán) ， 當(dāng)數(shù)值愈大時(shí) ， 其優(yōu)先權(quán)愈低；而有的系統(tǒng)恰恰相反 。 第三章 處理機(jī)調(diào)度與死鎖 3) 靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的 ， 且在進(jìn)程的整個(gè)運(yùn)行期間保持不變 。 如果 Pi≤Pj， 原進(jìn)程 Pj便繼續(xù)執(zhí)行；但如果是 Pi＞ Pj, 則立即停止 Pj的執(zhí)行 ， 做進(jìn)程切換 ， 使 i進(jìn)程投入執(zhí)行 。 但在其執(zhí)行期間 ， 只要又出現(xiàn)了另一個(gè)其優(yōu)先權(quán)更高的進(jìn)程 ， 進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程 (原優(yōu)先權(quán)最高的進(jìn)程 )的執(zhí)行 ， 重新將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程 。 這種調(diào)度算法主要用于批處理系統(tǒng)中；也可用于某些對實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中 。 第三章 處理機(jī)調(diào)度與死鎖 特點(diǎn)：吞吐量高、 能提供較好的響應(yīng)時(shí)間，對 長進(jìn)程不利、可能產(chǎn)生饑餓 第三章 處理機(jī)調(diào)度與死鎖 高優(yōu)先權(quán)優(yōu)先調(diào)度算法 選擇優(yōu)先級(jí)高的進(jìn)程和作業(yè)作為調(diào)度對象。 (2) 該算法完全未考慮作業(yè)的緊迫程度 ， 因而不能保證緊迫性作業(yè) (進(jìn)程 )會(huì)被及時(shí)