四、處理機(jī)調(diào)度

1、處理機(jī)調(diào)度層次

?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

①高級(jí)調(diào)度(High Level Scheduling)：又稱長(zhǎng)程調(diào)度、作業(yè)調(diào)度，決定能否加入到執(zhí)行的進(jìn)程池中

②低級(jí)調(diào)度(Low Level Scheduling)：又稱短程調(diào)度、進(jìn)程調(diào)度，決定哪個(gè)可用進(jìn)程占用處理器

③中級(jí)調(diào)度(Intermediate Scheduling)：又稱為平衡負(fù)載調(diào)度，決定主存中的可用進(jìn)程集合

2、調(diào)度準(zhǔn)則

(1) 資源利用率。

(2) 公平性，諸進(jìn)程獲得合理的CPU 時(shí)間，不發(fā)生進(jìn)程饑餓現(xiàn)象

(3) 平衡性，系統(tǒng)中的CPU和各種外部設(shè)備都能經(jīng)常處于忙碌狀態(tài)

(4) 響應(yīng)時(shí)間短 (5)周轉(zhuǎn)時(shí)間小 (6)吞吐量多

3、短程調(diào)度算法

■? 先來(lái)先服務(wù)(first-come first-served，F(xiàn)CFS)調(diào)度算法

非搶奪式，平均等待時(shí)間比較長(zhǎng)，不適合分時(shí)和實(shí)時(shí)系統(tǒng)。

■? 短作業(yè)優(yōu)先(short job first，SJF)調(diào)度算法

缺點(diǎn)：

(1)須預(yù)知作業(yè)運(yùn)行時(shí)間(2)對(duì)長(zhǎng)作業(yè)非常不利(3)無(wú)法實(shí)現(xiàn)人機(jī)交互

(4)完全未考慮作業(yè)緊迫程度,不能保證緊迫性作業(yè)能得到及時(shí)處理。

■ 輪轉(zhuǎn)調(diào)度算法(RR)

高響應(yīng)比優(yōu)先調(diào)度算法(Highest Response Ratio Next，HRRN)

4、優(yōu)先級(jí)調(diào)度算法，優(yōu)先級(jí)的類型

（1）靜態(tài)優(yōu)先級(jí)：靜態(tài)優(yōu)先級(jí)是在創(chuàng)建進(jìn)程時(shí)確定的，在進(jìn)程的整個(gè)運(yùn)行期間保持不變。優(yōu)先級(jí)是利用某一范圍內(nèi)的一個(gè)整數(shù)來(lái)表示的，例如0～255中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)。確定進(jìn)程優(yōu)先級(jí)大小的依據(jù)有如下三個(gè)：進(jìn)程類型、進(jìn)程對(duì)資源的需求、用戶要求

（2）動(dòng)態(tài)優(yōu)先級(jí)：動(dòng)態(tài)優(yōu)先級(jí)是指在創(chuàng)建進(jìn)程之初，先賦予其一個(gè)優(yōu)先級(jí)，然后其值隨進(jìn)程的推進(jìn)或等待時(shí)間的增加而改變，以便獲得更好的調(diào)度性能。動(dòng)態(tài)優(yōu)先級(jí)根據(jù)進(jìn)程占用CPU的長(zhǎng)短、進(jìn)程等待CPU的長(zhǎng)短來(lái)確定。

■? 優(yōu)先級(jí)調(diào)度算法缺點(diǎn)與解決辦法

缺點(diǎn)：無(wú)窮阻塞或饑餓現(xiàn)象，某個(gè)低優(yōu)先級(jí)進(jìn)程無(wú)窮等待CPU。

解決方法：老化技術(shù)，逐漸增加等待很長(zhǎng)時(shí)間的進(jìn)程的優(yōu)先級(jí)。

5、多級(jí)反饋隊(duì)列輪換調(diào)度算法

■? 調(diào)度機(jī)制

多級(jí)反饋隊(duì)列調(diào)度算法的調(diào)度機(jī)制可描述如下：

(1) 設(shè)置多個(gè)就緒隊(duì)列。

(2) 每個(gè)隊(duì)列都采用FCFS算法。

(3) 按隊(duì)列優(yōu)先級(jí)調(diào)度。

■? 算法性能

如果規(guī)定第一個(gè)隊(duì)列的時(shí)間片略大于多數(shù)人機(jī)交互所需之處理時(shí)間時(shí)，便能較好地滿足各種類型用戶的需要。

6、實(shí)時(shí)調(diào)度

■ 實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件：提供必要的信息、系統(tǒng)處理能力強(qiáng)、采用搶占式調(diào)度機(jī)制、具有快速切換機(jī)制

■? 實(shí)時(shí)調(diào)度算法的分類：① 根據(jù)實(shí)時(shí)任務(wù)性質(zhì)，可將實(shí)時(shí)調(diào)度的算法分為硬實(shí)時(shí)調(diào)度算法和軟實(shí)時(shí)調(diào)度算法；② 按調(diào)度方式，則可分為非搶占調(diào)度算法和搶占調(diào)度算法。

■? 非搶占式調(diào)度算法有非搶占式輪轉(zhuǎn)調(diào)度算法和優(yōu)先調(diào)度算法

■? 搶占式調(diào)度算法

可根據(jù)搶占發(fā)生時(shí)間的不同而進(jìn)一步分成以下兩種調(diào)度算法：

(1) 基于時(shí)鐘中斷的搶占式優(yōu)先級(jí)調(diào)度算法。

(2) 立即搶占(Immediate Preemption)的優(yōu)先級(jí)調(diào)度算法。

6.1最早截止時(shí)間優(yōu)先EDF(Earliest Deadline First)算法

(1)非搶占式調(diào)度方式用于非周期實(shí)時(shí)任務(wù)

(2) 搶占式調(diào)度方式用于周期實(shí)時(shí)任務(wù)

6.2最低松弛度優(yōu)先LLF(Least Laxity First)算法

該算法在確定任務(wù)的優(yōu)先級(jí)時(shí)，根據(jù)的是任務(wù)的緊急(或松弛)程度。任務(wù)緊急程度愈高，賦予該任務(wù)的優(yōu)先級(jí)就愈高，以使之優(yōu)先執(zhí)行。

圖 1? A和B任務(wù)每次必須完成的時(shí)間

圖 2? 利用ELLF算法進(jìn)行調(diào)度的情況