算法思想

主要從“公平”的角度考慮

算法規(guī)則

按照作業(yè)/進(jìn)程到達(dá)的先后順序進(jìn)行服務(wù)

作業(yè)調(diào)度 or 進(jìn)程調(diào)度？

用于作業(yè)調(diào)度時(shí)，考慮的是哪個(gè)作業(yè)先到達(dá)后備隊(duì)列

用于進(jìn)程調(diào)度時(shí)，考慮的是哪個(gè)進(jìn)程先到達(dá)就緒隊(duì)列

搶占 or 非搶占式？

非搶占式

優(yōu)點(diǎn)和缺點(diǎn)

優(yōu)點(diǎn)：公平、算法實(shí)現(xiàn)簡單
缺點(diǎn)：對長作業(yè)有利，對短作業(yè)不利

是否會(huì)導(dǎo)致饑餓

不會(huì)

算法思想

追求最少的平均等待時(shí)間，最少的平均周轉(zhuǎn)時(shí)間、最少的平均平均帶權(quán)周轉(zhuǎn)時(shí)間

算法規(guī)則

每次調(diào)度時(shí)，選擇當(dāng)前已到達(dá)、且運(yùn)行時(shí)間最短的作業(yè)/進(jìn)程。

作業(yè)調(diào)度 or 進(jìn)程調(diào)度？

可用于作業(yè)調(diào)度 / 進(jìn)程調(diào)度。用于進(jìn)程調(diào)度時(shí)：**短進(jìn)程優(yōu)先（SPF, Shortest Process First）**算法

搶占 or 非搶占式？

SJF / SPF 是非搶占式。搶占式版本：**最短剩余時(shí)間優(yōu)先（SRTN, Shortest Remaining Time Next）**算法

優(yōu)點(diǎn)和缺點(diǎn)

優(yōu)點(diǎn)：“最短的”平均等待時(shí)間、平均周轉(zhuǎn)時(shí)間
缺點(diǎn)：不公平。對短作業(yè)有利，長作業(yè)不利。可能產(chǎn)生饑餓現(xiàn)象；作業(yè)/進(jìn)程的運(yùn)行時(shí)間由用戶提供的，不一定真實(shí)，不一定真正做到短作業(yè)優(yōu)先

是否會(huì)導(dǎo)致饑餓

會(huì)。如果不斷有短作業(yè)到來，導(dǎo)致長作業(yè)饑餓 / 餓死

如果題目中未特別說明，所提到的“短作業(yè)/進(jìn)程優(yōu)先算法”默認(rèn)是非搶占式的

很多書上都會(huì)說“SJF 調(diào)度算法的平均等待時(shí)間、平均周轉(zhuǎn)時(shí)間最少”，這個(gè)表述不嚴(yán)謹(jǐn)。之前例子表明，最短剩余時(shí)間優(yōu)先算法得到的平均等待時(shí)間、平均周轉(zhuǎn)時(shí)間還要更少。

應(yīng)該加上一個(gè)條件“在所有進(jìn)程同時(shí)可運(yùn)行時(shí)，采用SJF調(diào)度算法的平均等待時(shí)間、平均周轉(zhuǎn)時(shí)間最少”；或者“在所有進(jìn)程都幾乎同時(shí)到達(dá)時(shí)，采用SJF調(diào)度算法的平均等待時(shí)間、平均周轉(zhuǎn)時(shí)間最少”；

如不加上述前提條件，應(yīng)該說“搶占式的短作業(yè)/進(jìn)程優(yōu)先調(diào)度算法（最短剩余時(shí)間優(yōu)先, SRNT算法）的平均等待時(shí)間、平均周轉(zhuǎn)時(shí)間最少”

雖然嚴(yán)格來說，SJF的平均等待時(shí)間、平均周轉(zhuǎn)時(shí)間并不一定最少，但相比于其他算法（如FCFS），SJF依然可以獲得較少的平均等待時(shí)間、平均周轉(zhuǎn)時(shí)間

如果選擇題中遇到“SJF 算法的平均等待時(shí)間、平均周轉(zhuǎn)時(shí)間最少”的選項(xiàng)，那最好判斷其他選項(xiàng)是不是有很明顯的錯(cuò)誤，如果沒有更合適的選項(xiàng)，那也應(yīng)該選擇該選項(xiàng)

算法思想

要綜合考慮作業(yè)/進(jìn)程的等待時(shí)間和要求服務(wù)的時(shí)間

算法規(guī)則

在每次調(diào)度時(shí)先計(jì)算各個(gè)作業(yè)/進(jìn)程的響應(yīng)比，選擇響應(yīng)比最高的作業(yè)/進(jìn)程，上處理機(jī)。

響應(yīng)比 = (等待時(shí)間+要求服務(wù)時(shí)間) / 要求服務(wù)時(shí)間

作業(yè)調(diào)度 or 進(jìn)程調(diào)度？

均可

搶占 or 非搶占式？

非搶占式。因此只有當(dāng)前運(yùn)行的作業(yè)/進(jìn)程主動(dòng)放棄處理機(jī)時(shí)，才需要調(diào)度，才需要計(jì)算響應(yīng)比。

優(yōu)點(diǎn)和缺點(diǎn)

綜合考慮了等待時(shí)間和運(yùn)行時(shí)間（要求服務(wù)時(shí)間）。

等待時(shí)間相同時(shí)，要求服務(wù)時(shí)間短的優(yōu)先（SJF 的優(yōu)點(diǎn)）。

要求服務(wù)時(shí)間相同時(shí)，等待時(shí)間長的優(yōu)先（FCFS 的優(yōu)點(diǎn)）

等待時(shí)間越來越久，響應(yīng)比會(huì)越來越大，從而避免了長作業(yè)饑餓的問題。

是否會(huì)導(dǎo)致饑餓

不會(huì)

算法思想

公平地、輪流地為各個(gè)進(jìn)程服務(wù)，讓每個(gè)進(jìn)程在一定時(shí)間間隔內(nèi)都可以得到響應(yīng)

算法規(guī)則

按照各進(jìn)程到達(dá)就緒隊(duì)列的順序，輪流讓各個(gè)進(jìn)程執(zhí)行一個(gè)時(shí)間片（如100ms）。若進(jìn)程未在一個(gè)時(shí)間片內(nèi)執(zhí)行完，則剝奪處理機(jī)，將進(jìn)程重新放到就緒隊(duì)列隊(duì)尾重新排隊(duì)。

隨著分時(shí)操作系統(tǒng)的出現(xiàn)而出現(xiàn)，更注重“響應(yīng)時(shí)間”。

作業(yè)調(diào)度 or 進(jìn)程調(diào)度？

進(jìn)程調(diào)度（只有作業(yè)放入內(nèi)存建立了相應(yīng)的進(jìn)程后，才能被分配處理機(jī)時(shí)間片）

搶占 or 非搶占式？

搶占式。

由時(shí)鐘裝置發(fā)出時(shí)鐘中斷來通知CPU時(shí)間片已到。進(jìn)程未能在時(shí)間片內(nèi)運(yùn)行完，會(huì)被剝奪處理機(jī)使用權(quán)。

優(yōu)點(diǎn)和缺點(diǎn)

優(yōu)點(diǎn)：公平；響應(yīng)快，適用于分時(shí)操作系統(tǒng)；
缺點(diǎn)：由于高頻率的進(jìn)程切換，因此有一定開銷；不區(qū)分任務(wù)的緊急程度。

是否會(huì)導(dǎo)致饑餓

不會(huì)

算法思想

隨著計(jì)算機(jī)的發(fā)展，特別是實(shí)時(shí)操作系統(tǒng)的出現(xiàn)，越來越多的應(yīng)用場景需要根據(jù)任務(wù)的緊急程度來決定處理順序

算法規(guī)則

每個(gè)作業(yè)/進(jìn)程有各自的 優(yōu)先級，調(diào)度時(shí)選擇 優(yōu)先級最高的作業(yè)/進(jìn)程

通常來說，優(yōu)先級排序：

系統(tǒng)進(jìn)程 > 用戶進(jìn)程
前臺進(jìn)程 > 后臺進(jìn)程
I/O密集型進(jìn)程 > CPU密集型進(jìn)程（計(jì)算型進(jìn)程）

作業(yè)調(diào)度 or 進(jìn)程調(diào)度？

均可。既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。甚至，還會(huì)用于在之后會(huì)學(xué)習(xí)的I/O調(diào)度中

搶占 or 非搶占式？

搶占式、非搶占式 都有。

非搶占式在 進(jìn)程主動(dòng)放棄處理機(jī) 時(shí)進(jìn)行調(diào)度即可；搶占式還需在 就緒隊(duì)列變化 時(shí)，檢查是否會(huì)發(fā)生搶占。

優(yōu)點(diǎn)和缺點(diǎn)

優(yōu)點(diǎn)：用優(yōu)先級區(qū)分緊急程度、重要程度，可靈活調(diào)整，適用于實(shí)時(shí)操作系統(tǒng)
缺點(diǎn)：若不斷地有高優(yōu)先級進(jìn)程到來，則可能導(dǎo)致饑餓

是否會(huì)導(dǎo)致饑餓

會(huì)

算法思想

對其他調(diào)度算法的 折中 權(quán)衡

算法規(guī)則

設(shè)置多級就緒隊(duì)列，各級隊(duì)列優(yōu)先級從高到低，時(shí)間片從小到大

新進(jìn)程到達(dá)時(shí)先進(jìn)入第1級隊(duì)列，按FCFS原則排隊(duì)等待被分配時(shí)間片，若用完時(shí)間片進(jìn)程還未結(jié)束，則進(jìn)程進(jìn)入下一級隊(duì)列隊(duì)尾。如果此時(shí)已經(jīng)是在最下級的隊(duì)列，則重新放回該隊(duì)列隊(duì)尾

只有第 k 級隊(duì)列為空時(shí)，才會(huì)為 k+1 級隊(duì)頭的進(jìn)程分配時(shí)間片

作業(yè)調(diào)度 or 進(jìn)程調(diào)度？

進(jìn)程調(diào)度

搶占 or 非搶占式？

搶占。在k 級隊(duì)列的進(jìn)程運(yùn)行過程中，若更上級的隊(duì)列（1 ~ k-1級）中進(jìn)入了一個(gè)新進(jìn)程，則由于新進(jìn)程處于優(yōu)先級更高的隊(duì)列中，因此新進(jìn)程會(huì)搶占處理機(jī)，原來運(yùn)行的進(jìn)程放回 k 級隊(duì)列隊(duì)尾。

優(yōu)點(diǎn)和缺點(diǎn)

對各類型進(jìn)程相對公平（FCFS的優(yōu)點(diǎn)）；每個(gè)新到達(dá)的進(jìn)程都可以很快就得到響應(yīng)（RR的優(yōu)點(diǎn)）；短進(jìn)程只用較少的時(shí)間就可完成（SPF的優(yōu)點(diǎn)）；不必實(shí)現(xiàn)估計(jì)進(jìn)程的運(yùn)行時(shí)間（避免用戶作假）；可靈活地調(diào)整對各類進(jìn)程的偏好程度，比如CPU密集型進(jìn)程、I/O密集型進(jìn)程（拓展：可以將因I/O而阻塞的進(jìn)程重新放回原隊(duì)列，這樣I/O型進(jìn)程就可以保持較高優(yōu)先級）

是否會(huì)導(dǎo)致饑餓

會(huì)，考慮不斷有短時(shí)間的進(jìn)程到來的情況。