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