【正文】 的線程被剝奪，具有更高優(yōu)先級的進(jìn)程占用處理器 進(jìn)程和線程優(yōu)先級 ?兩類優(yōu)先級的處理方式有一定的不同 – 在實(shí)時優(yōu)先級類中，所有線程具有固定的優(yōu)先級，并且它們的優(yōu)先級永遠(yuǎn)不會改變，某一給定優(yōu)先級的所有活動線程在一個循環(huán)隊列中 – 在可變優(yōu)先級類中，一個線程的優(yōu)先級在開始時是最初指定的值，但在它的生命周期中可能會發(fā)生變化，上升或者下降。最低優(yōu)先級隊列，按時間片輪轉(zhuǎn)調(diào)度算法執(zhí)行 調(diào)度算法 允許進(jìn)入 CPU RQ0 RQ1 RQ2 RQn 釋放 CPU 釋放 CPU 釋放 CPU 釋放 反饋調(diào)度 不同優(yōu)先級的就緒隊列可以給予相同的時間片，也可以不同。當(dāng)一高優(yōu)先級進(jìn)程運(yùn)行時，若有一更高優(yōu)先級進(jìn)程到達(dá)就緒隊列，則當(dāng)前運(yùn)行進(jìn)程立刻將處理器讓給更高優(yōu)先級的進(jìn)程（即使未處理完，也無遇到阻塞情況） 調(diào)度算法 最高優(yōu)先數(shù)算 法 ? 可搶占 CPU – Process Arrival time Priority Burst time ? P1 0 0 8 ? P2 2 1 5 ? P3 4 3 7 ? P4 0 2 3 ? P5 5 7 2 ? Gantt Chart 0 3 4 5 7 13 17 25 P1 P4 P2 P2 P3 P3 P5 最 高優(yōu)先數(shù)算 法 0 3 4 5 7 13 17 25 P1 P4 P2 P2 P3 P3 P5 ?輪轉(zhuǎn)調(diào)度 (簡單輪轉(zhuǎn)法 RR) ? 系統(tǒng)把所有就緒進(jìn)程按先后次序排隊，處理機(jī)總是優(yōu)先分配給就緒隊列中的第一個就緒進(jìn)程，并分配它一個固定的時間片 (如 50毫秒 ) ? 當(dāng)該運(yùn)行進(jìn)程用完規(guī)定的時間片時，被迫釋放處理機(jī)給下一個處于就緒隊列中的第一個進(jìn)程 ,自己回到就緒隊列的尾部，并等待下次調(diào)度 ? 當(dāng)某個正在運(yùn)行的進(jìn)程的時間片尚未用完，但進(jìn)程需要 I/O時，該進(jìn)程被送到相應(yīng)阻塞隊列，等 I/O完成重新返回到就緒隊列尾部，等待調(diào)度。當(dāng)一個時鐘中斷周期到后，調(diào)度程序總是 選擇預(yù)期剩余時間最短 的進(jìn)程 ? 當(dāng)一個新進(jìn)程加入就緒隊列時，它可能比當(dāng)前運(yùn)行的進(jìn)程具有更短的剩余時間，因此，調(diào)度程序?qū)儕Z當(dāng)前程序，將處理器分配給新進(jìn)程。這個準(zhǔn)則也可用于中程調(diào)度和長程調(diào)度 調(diào)度算法設(shè)計指標(biāo) 處理器調(diào)度的類型（級別） ?多道程序的關(guān)鍵是調(diào)度。對處理器而言，可分配的資源是在處理器上的執(zhí)行時間，分配途徑是調(diào)度 ? 處理器調(diào)度 ：指采用合理的策略和方法在多個可運(yùn)行實(shí)體間分配 CPU資源。 – 最后期限 當(dāng)可以指定進(jìn)程完成的最后期限時，調(diào)度原則將服從于其他目標(biāo)，使得距最后期限最近 – 平均周轉(zhuǎn)時間： p61 – 平均帶權(quán)周轉(zhuǎn)時間 ： p61 ? 面向 系統(tǒng)準(zhǔn)則所關(guān)心的性能指標(biāo) – 吞吐量 單位時間內(nèi)完成的任務(wù)數(shù)。 進(jìn)程調(diào)度方式 ? 剝奪方式： 當(dāng)一個正在運(yùn)行的進(jìn)程沒有運(yùn)行完時，系統(tǒng)采取某種手段強(qiáng)行剝奪已分配給該進(jìn)程的處理器資源。 ? 但隨著長作業(yè)等待的時間 (w)增長， R值不斷增大，到達(dá)一定的等待時間，長進(jìn)程最終將憑借年齡的增長戰(zhàn)勝短進(jìn)程，從而獲得處理器。同樣這對短作業(yè)和要求 I/O 操作多的作業(yè)顯然是不利的 ? 因而，在簡單輪轉(zhuǎn)法的基礎(chǔ)上又提出了分級輪轉(zhuǎn)法 調(diào)度算法 ?分級輪轉(zhuǎn)法 – 將一個就緒隊列根據(jù)進(jìn)程的優(yōu)先級不同，劃分二個或二個以上的就緒隊列，并賦給每個隊列不同的優(yōu)先級，甚至可以分配不同的時間片 – 一般情況下，調(diào)度算法把相同的時間片分配給優(yōu)先級高的就緒隊列中的隊首進(jìn)程 – 只有當(dāng)優(yōu)先級高的就緒隊列中的所有進(jìn)程全部運(yùn)行完畢或等待 I/O操作而沒有進(jìn)程運(yùn)行時，才把處理機(jī)分配給低優(yōu)先級就緒隊列中的進(jìn)程 調(diào)度算法 高優(yōu)先級就緒隊列 低優(yōu)先級就緒隊列 處理器 分級輪轉(zhuǎn)調(diào)度 分派 超時 等待事件 阻塞隊列 釋放 超時 事件發(fā)生 高優(yōu)先級隊列空 調(diào)度算法 ?分級輪轉(zhuǎn)法 – 為了公平性，低優(yōu)先級就緒隊列的進(jìn)程如果獲得調(diào)度，將得到比高優(yōu)先級就緒隊列進(jìn)程更多的時間片，加以彌補(bǔ) – 這樣能大大降低長作業(yè)的交換頻率，減少系統(tǒng)在交換作業(yè)時的時間消耗，又給了短作業(yè)較高的優(yōu)先級 ?反饋 FB（多級反饋隊列調(diào)度算法） ? 分級輪轉(zhuǎn)調(diào)度和動態(tài)優(yōu)先級算法的結(jié)合， 采用剝奪策略 ? 劃分多個就緒隊列，優(yōu)先級逐步降低。（ 沒有特殊說明時，認(rèn)為是搶占方式 ） ? 非搶占方式：當(dāng)前進(jìn)程用完規(guī)定的時間片后，再調(diào)度高優(yōu)先級的進(jìn)程。剩下的低優(yōu)先級線程共享剩下的一個處理器 多處理器調(diào)度 實(shí)時調(diào)度 (realtime scheduling) ? 實(shí)時任務(wù)： – 具有明確時間約束的計算任務(wù)。 ? (2) RR—— 同等對待所有的作業(yè) (給它們分配相等的 CPU時間 ) ，因此，由于短作業(yè)將首先完成，所以短作業(yè)可以較快地離開系統(tǒng)。 en