批處理系統(tǒng)中采用的調(diào)度算法

重要指標(biāo)（吞吐量，周轉(zhuǎn)時(shí)間，CPU利用率，公平平衡）

非搶占式的先來(lái)先服務(wù)算法（FCFS）：按照進(jìn)程就緒的先后順序使用CPU

特點(diǎn)：公平，實(shí)現(xiàn)簡(jiǎn)單，但是長(zhǎng)進(jìn)程后面的短進(jìn)程需要等待很長(zhǎng)時(shí)間，不利于用戶體驗(yàn)。

非搶占式的最短作業(yè)優(yōu)先（SJF）：具有最短完成時(shí)間的進(jìn)程優(yōu)先執(zhí)行

最短剩余時(shí)間優(yōu)先（SRTN）：SJF搶占式版本，即當(dāng)一個(gè)新就緒的進(jìn)程比當(dāng)前運(yùn)行進(jìn)程具有更短完成時(shí)間時(shí)，系統(tǒng)搶占當(dāng)前進(jìn)程，選擇新就緒的進(jìn)程執(zhí)行。

短作業(yè)優(yōu)先調(diào)度算法特點(diǎn)：改善短作業(yè)的周轉(zhuǎn)時(shí)間，但如果源源不斷有短任務(wù)到來(lái)，可能使長(zhǎng)的任務(wù)長(zhǎng)時(shí)間得不到運(yùn)行，產(chǎn)生饑餓現(xiàn)象。

最高相應(yīng)比優(yōu)先算法（HRRN）：是一個(gè)綜合算法，調(diào)度時(shí)，首先計(jì)算每個(gè)進(jìn)程的響應(yīng)比R，之后總是選擇R最高的進(jìn)程執(zhí)行。

響應(yīng)比R=（等待時(shí)間+處理時(shí)間）/處理時(shí)間

交互系統(tǒng)中采用的調(diào)度算法

重要指標(biāo)（響應(yīng)時(shí)間，公平平衡）

時(shí)間片輪轉(zhuǎn)調(diào)度算法：每個(gè)進(jìn)程被分配一個(gè)時(shí)間片，允許該進(jìn)程在該時(shí)間段運(yùn)行，如果在時(shí)間片結(jié)束時(shí)該進(jìn)程還在運(yùn)行，則剝奪CPU并分配給另一個(gè)進(jìn)程，如果該進(jìn)程在時(shí)間片結(jié)束前阻塞或結(jié)束，則CPU立即進(jìn)行切換。

當(dāng)時(shí)間片選擇太長(zhǎng)，其降級(jí)為先來(lái)先服務(wù)算法，引起對(duì)短的交互請(qǐng)求響應(yīng)時(shí)間長(zhǎng)

當(dāng)時(shí)間片選擇太短，會(huì)導(dǎo)致頻繁的進(jìn)程切換，浪費(fèi)CPU時(shí)間。

通常選擇為20ms~50ms.

對(duì)進(jìn)程表中不同進(jìn)程的大小差異較大的有利，而對(duì)進(jìn)程都是相同大小的不利。

虛擬輪轉(zhuǎn)法：主要基于時(shí)間片輪轉(zhuǎn)法進(jìn)行改進(jìn)，解決在CPU調(diào)度中對(duì)于I/O密集型進(jìn)程的不友好。其設(shè)置了一個(gè)輔助隊(duì)列，對(duì)于I/O型進(jìn)程執(zhí)行完一個(gè)時(shí)間片之后，則進(jìn)入輔助隊(duì)列，CPU調(diào)度時(shí)總是先檢查輔助隊(duì)列是否為空，如果不為空總是優(yōu)先調(diào)度輔助隊(duì)列里的進(jìn)程，直到為空，才調(diào)度就緒隊(duì)列的進(jìn)程。

最高優(yōu)先級(jí)調(diào)度算法：選擇優(yōu)先級(jí)最高的進(jìn)程優(yōu)先執(zhí)行。

優(yōu)先級(jí)可以靜態(tài)不變，也可以動(dòng)態(tài)調(diào)整

優(yōu)先數(shù)決定優(yōu)先級(jí)

就緒隊(duì)列可以按照優(yōu)先級(jí)組織

實(shí)現(xiàn)簡(jiǎn)單，但不公平，可能導(dǎo)致優(yōu)先級(jí)低的進(jìn)程產(chǎn)生饑餓現(xiàn)象。

可能產(chǎn)生優(yōu)先級(jí)反轉(zhuǎn)問(wèn)題（基于優(yōu)先級(jí)的搶占式算法），即一個(gè)低優(yōu)先級(jí)進(jìn)程持有一個(gè)高優(yōu)先級(jí)進(jìn)程所需要的資源，使得高優(yōu)先級(jí)進(jìn)程等待低優(yōu)先級(jí)進(jìn)程運(yùn)行。

多級(jí)反饋隊(duì)列調(diào)度算法：

設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。第一個(gè)隊(duì)列的優(yōu)先級(jí)最高，依次遞減優(yōu)先級(jí)。

對(duì)于各個(gè)隊(duì)列進(jìn)程執(zhí)行時(shí)間片的大小也不同，優(yōu)先級(jí)越高的隊(duì)列，分配到的時(shí)間片越少。

當(dāng)?shù)谝患?jí)隊(duì)列為空時(shí)，再第二級(jí)隊(duì)列進(jìn)行調(diào)度，依次類推，各級(jí)隊(duì)列按照時(shí)間片輪轉(zhuǎn)方式進(jìn)行調(diào)度。

當(dāng)一個(gè)新進(jìn)程創(chuàng)建后，首先把它放入第一隊(duì)列的末尾。按照FCFS原則排隊(duì)等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如它在該時(shí)間片完成，便可準(zhǔn)備撤離系統(tǒng)，如果它在一個(gè)時(shí)間片結(jié)束時(shí)尚未完成，則調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊(duì)列的末尾，再同樣地按照FCFS原則等待調(diào)度執(zhí)行。依次類推。