【正文】 單位時(shí)間內(nèi)完成的任務(wù)數(shù)。 – 處理器使用率 處理器忙的時(shí)間百分比。 – 公平 進(jìn)程應(yīng)該被平等對(duì)待，沒(méi)有一個(gè)進(jìn)程會(huì)被餓死 – 強(qiáng)制優(yōu)先級(jí) 當(dāng)進(jìn)程被指定了優(yōu)先級(jí)，調(diào)度策略會(huì)先選擇高優(yōu)先級(jí)的進(jìn)程 – 平衡資源 保持系統(tǒng)中所有資源忙。典型的調(diào)度類型有： ? 長(zhǎng)程調(diào)度 (作業(yè)調(diào)度 ,高級(jí)調(diào)度）決定加入到待執(zhí)行的進(jìn)程池中 ? 中程調(diào)度 （交換調(diào)度 ,中級(jí)調(diào)度）將進(jìn)程調(diào)入內(nèi)存 ,或者將進(jìn)程交換到硬盤 ? 短程調(diào)度 （進(jìn)程調(diào)度，低級(jí)調(diào)度）決定哪一個(gè)就緒進(jìn)程將被處理器執(zhí)行 ? 線程調(diào)度 ：決定哪一個(gè)線程被處理器執(zhí)行 就緒 /掛起 新建 就緒 運(yùn)行 退出 阻塞 短程調(diào)度 阻塞 /掛起 中程調(diào)度 長(zhǎng)程調(diào)度 長(zhǎng)程調(diào)度 中程調(diào)度 ?下一次允許哪一個(gè)進(jìn)程進(jìn)入的 決策 可以基于簡(jiǎn)單的先來(lái)先服務(wù)原則，或者也可以基于管理系統(tǒng)性能的工具 ?使用的原則包括優(yōu)先級(jí)、期待執(zhí)行時(shí)間和 I/O需求 ?同樣，可以根據(jù)請(qǐng)求哪個(gè) I/O資源和試圖平衡 I/O使用的目的進(jìn)行決策 長(zhǎng)程調(diào)度 ?中程調(diào)度的目標(biāo)有 2個(gè)： ?解決內(nèi)存資源緊張的矛盾 ?減小并發(fā)度以降低系統(tǒng)開銷 ? 中程調(diào)度算法將結(jié)合存儲(chǔ)管理來(lái)設(shè)計(jì)。 進(jìn)程調(diào)度方式 ? 剝奪方式： 當(dāng)一個(gè)正在運(yùn)行的進(jìn)程沒(méi)有運(yùn)行完時(shí)，系統(tǒng)采取某種手段強(qiáng)行剝奪已分配給該進(jìn)程的處理器資源。 進(jìn)程調(diào)度方式 進(jìn)程調(diào)度方式 ?有三個(gè)進(jìn)程 p1， p2， p3到達(dá)時(shí)間為： 0， 3， 4，優(yōu)先級(jí)依次增高，運(yùn)行所需的時(shí)間分別為 20， 4， 2，假設(shè)現(xiàn)按優(yōu)先級(jí)策略調(diào)度執(zhí)行，并且不采用時(shí)間片原則，請(qǐng)分別求出非剝奪方式和剝奪方式下各個(gè)進(jìn)程的周轉(zhuǎn)時(shí)間。但短進(jìn)程的等待時(shí)間長(zhǎng)，平均周轉(zhuǎn)時(shí)間長(zhǎng) 調(diào)度算法 p61 ?最短進(jìn)程 SPN（短進(jìn)程優(yōu)先調(diào)度算法） ? 減少 FCFS固有的對(duì)長(zhǎng)進(jìn)程的偏愛的另一種方法是最短進(jìn)程 (SPN) 策略， 這是一種非剝奪的策略 ，其原則是下一次選擇所需處理時(shí)間最短的進(jìn)程，因此，短進(jìn)程將會(huì)越過(guò)長(zhǎng)進(jìn)程，得到優(yōu)先運(yùn)行 ? SPN策略的難點(diǎn)在于需要知道或至少需要估計(jì)每個(gè)進(jìn)程所需要的處理時(shí)間 ? 長(zhǎng)進(jìn)程可能被 “ 餓死 ” 調(diào)度算法 ?最短剩余時(shí)間優(yōu)先調(diào)度算法 (SRTN) ? 對(duì) SPN增加剝奪機(jī)制。 ? 和 SPN一樣，調(diào)度程序必須有關(guān)于處理時(shí)間的估計(jì)，并且存在長(zhǎng)進(jìn)程被餓死的危險(xiǎn) 調(diào)度算法 ?最高響應(yīng)比優(yōu)先調(diào)度算法（ HRRN） ? 響應(yīng)比： R=(w+s)/s=1+w/s w表示等待時(shí)間； s表示執(zhí)行所需時(shí)間 ? 最高響應(yīng)比也是對(duì)最短進(jìn)程法的一種改進(jìn)，當(dāng)當(dāng)前進(jìn)程完成或被阻塞時(shí)， 選擇響應(yīng)比最大的進(jìn)程先執(zhí)行 ，是一種 非剝奪 的策略。 ? 但隨著長(zhǎng)作業(yè)等待的時(shí)間 (w)增長(zhǎng)， R值不斷增大，到達(dá)一定的等待時(shí)間，長(zhǎng)進(jìn)程最終將憑借年齡的增長(zhǎng)戰(zhàn)勝短進(jìn)程，從而獲得處理器。 ?優(yōu)先數(shù)確定方式： ? 靜態(tài)優(yōu)先級(jí)：每個(gè)進(jìn)程創(chuàng)建時(shí)被賦予一個(gè)優(yōu)先數(shù)，該優(yōu)先數(shù)在進(jìn)程整個(gè)生命周期都是固定不變的。 ? 可搶占的優(yōu)先級(jí)調(diào)度法 ：任何時(shí)刻都按照高優(yōu)先級(jí)進(jìn)程在處理器上運(yùn)行的原則進(jìn)行進(jìn)程調(diào)度。 調(diào)度算法 簡(jiǎn)單輪轉(zhuǎn)法 RR 處理器 就緒隊(duì)列 阻塞隊(duì)列 分派 釋放 超時(shí) 等待事件 事件發(fā)生 ?輪轉(zhuǎn)調(diào)度 ? 簡(jiǎn)單輪轉(zhuǎn)法是以就緒隊(duì)列中的所有進(jì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í)逐步降低。 ? 進(jìn)程調(diào)度時(shí)總是先執(zhí)行高優(yōu)先級(jí)隊(duì)列中的進(jìn)程。 ? 同一優(yōu)先級(jí)隊(duì)列（除最低）的進(jìn)程，按 FIFO機(jī)制調(diào)度。 調(diào)度算法 ?反饋 FB ? 在反饋調(diào)度算法中，長(zhǎng)進(jìn)程也存在餓死的現(xiàn)象 ? 當(dāng)比運(yùn)行進(jìn)程更高優(yōu)先級(jí)隊(duì)列到來(lái)一個(gè)新進(jìn)程時(shí)，則應(yīng)該處理高優(yōu)先級(jí)隊(duì)列的進(jìn)程。（ 沒(méi)有特殊說(shuō)明時(shí)，認(rèn)為是搶占方式 ） ? 非搶占方式：當(dāng)前進(jìn)程用完規(guī)定的時(shí)間片后，再調(diào)度高優(yōu)先級(jí)的進(jìn)程。在程序執(zhí)行過(guò)程中，每個(gè)程序被分配給一組處理器，處理器的數(shù)目與程序線程的數(shù)目相等。每一段包括 16種優(yōu)先級(jí)。因此，在每個(gè)優(yōu)先級(jí)上都有一個(gè) FIFO隊(duì)列，一個(gè)進(jìn)程可能在可變優(yōu)先級(jí)類中從一個(gè)隊(duì)列遷移到另一個(gè)隊(duì)列。剩下的低優(yōu)先級(jí)線程共享剩下的一個(gè)處理器 多處理器調(diào)度 實(shí)時(shí)調(diào)度 (realtime scheduling) ? 實(shí)時(shí)任務(wù)： – 具有明確時(shí)間約束的計(jì)算任務(wù)。 實(shí)時(shí)任務(wù)分類 ? 硬