今天我們來(lái)談一談進(jìn)程調(diào)度算法：

1. 先來(lái)先服務(wù)調(diào)度算法（FCFS）

先來(lái)先服務(wù)(FCFS)調(diào)度算法是一種最簡(jiǎn)單的調(diào)度算法，該算法既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。當(dāng)在作業(yè)調(diào)度中采用該算法時(shí)，每次調(diào)度都是從后備作業(yè)隊(duì)列中選擇一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。在進(jìn)程調(diào)度中采用FCFS算法時(shí)，則每次調(diào)度是從就緒隊(duì)列中選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，為之分配處理機(jī)，使之投入運(yùn)行。該進(jìn)程一直運(yùn)行到完成或發(fā)生某事件而阻塞后才放棄處理機(jī)。

算法優(yōu)點(diǎn)：易于理解且實(shí)現(xiàn)簡(jiǎn)單，只需要一個(gè)隊(duì)列(FIFO)，且相當(dāng)公平 算法缺點(diǎn)：比較有利于長(zhǎng)進(jìn)程，而不利于短進(jìn)程，有利于CPU 繁忙的進(jìn)程，而不利于I/O 繁忙的進(jìn)程

2. 短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法（SJF）

短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法，它作用于作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先是從后備隊(duì)列當(dāng)中選擇一個(gè)或者若干個(gè)運(yùn)行時(shí)間最短的作業(yè)，調(diào)入內(nèi)存當(dāng)中運(yùn)行。 短進(jìn)程優(yōu)先是從就緒進(jìn)程隊(duì)列當(dāng)中選出一個(gè)時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，立即執(zhí)行并且一直執(zhí)行到完成，當(dāng)發(fā)生其他問(wèn)題的時(shí)候，這個(gè)時(shí)候就重新調(diào)度。

算法優(yōu)點(diǎn)：相比FCFS 算法，該算法可改善平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，縮短進(jìn)程的等待時(shí)間，提高系統(tǒng)的吞吐量。 算法缺點(diǎn)：對(duì)長(zhǎng)進(jìn)程非常不利，可能長(zhǎng)時(shí)間得不到執(zhí)行，且未能依據(jù)進(jìn)程的緊迫程度來(lái)劃分執(zhí)行的優(yōu)先級(jí)，以及難以準(zhǔn)確估計(jì)進(jìn)程的執(zhí)行時(shí)間，從而影響調(diào)度性能。

3.優(yōu)先權(quán)調(diào)度算法

優(yōu)先級(jí)調(diào)度算法又被稱為優(yōu)先權(quán)調(diào)度算法，這個(gè)算法既可以用于作業(yè)調(diào)度，也可以用于進(jìn)程調(diào)度，這個(gè)算法中的優(yōu)先級(jí)用于描述作業(yè)運(yùn)行的緊迫程度。

在作業(yè)調(diào)度中，優(yōu)先級(jí)調(diào)度算法每次從后備作業(yè)隊(duì)列中選擇優(yōu)先級(jí)最髙的一個(gè)或幾個(gè)作業(yè)，將它們調(diào)入內(nèi)存，分配必要的資源，創(chuàng)建進(jìn)程并放入就緒隊(duì)列。在進(jìn)程調(diào)度中，優(yōu)先級(jí)調(diào)度算法每次從就緒隊(duì)列中選擇優(yōu)先級(jí)最高的進(jìn)程，將處理機(jī)分配給它，使之投入運(yùn)行。

根據(jù)新的更高優(yōu)先級(jí)進(jìn)程能否搶占正在執(zhí)行的進(jìn)程，可將該調(diào)度算法分為： * 非剝奪式優(yōu)先級(jí)調(diào)度算法。當(dāng)某一個(gè)進(jìn)程正在處理機(jī)上運(yùn)行時(shí)，即使有某個(gè)更為重要或緊迫的進(jìn)程進(jìn)入就緒隊(duì)列，仍然讓正在運(yùn)行的進(jìn)程繼續(xù)運(yùn)行，直到由于其自身的原因而主動(dòng)讓出處理機(jī)時(shí)（任務(wù)完成或等待事件），才把處理機(jī)分配給更為重要或緊迫的進(jìn)程。 * 剝奪式優(yōu)先級(jí)調(diào)度算法。當(dāng)一個(gè)進(jìn)程正在處理機(jī)上運(yùn)行時(shí)，若有某個(gè)更為重要或緊迫的進(jìn)程進(jìn)入就緒隊(duì)列，則立即暫停正在運(yùn)行的進(jìn)程，將處理機(jī)分配給更重要或緊迫的進(jìn)程。

而根據(jù)進(jìn)程創(chuàng)建后其優(yōu)先級(jí)是否可以改變，可以將進(jìn)程優(yōu)先級(jí)分為以下兩種： * 靜態(tài)優(yōu)先級(jí)。優(yōu)先級(jí)是在創(chuàng)建進(jìn)程時(shí)確定的，且在進(jìn)程的整個(gè)運(yùn)行期間保持不變。確定靜態(tài)優(yōu)先級(jí)的主要依據(jù)有進(jìn)程類型、進(jìn)程對(duì)資源的要求、用戶要求。 * 動(dòng)態(tài)優(yōu)先級(jí)。在進(jìn)程運(yùn)行過(guò)程中，根據(jù)進(jìn)程情況的變化動(dòng)態(tài)調(diào)整優(yōu)先級(jí)。動(dòng)態(tài)調(diào)整優(yōu)先級(jí)的主要依據(jù)為進(jìn)程占有CPU時(shí)間的長(zhǎng)短、就緒進(jìn)程等待CPU時(shí)間的長(zhǎng)短。

4.高響應(yīng)比優(yōu)先調(diào)度算法（HRRN）

高響應(yīng)比優(yōu)先調(diào)度算法主要用于作業(yè)調(diào)度，是堆FCFS和SJF的一種平衡。

FCFS是只考慮每個(gè)作業(yè)的等待時(shí)間不考慮執(zhí)行時(shí)間長(zhǎng)短，而SJF是只考慮執(zhí)行時(shí)間未考慮等待時(shí)間的長(zhǎng)短。

所以高響應(yīng)比同時(shí)考慮每個(gè)作業(yè)的等待時(shí)間和估計(jì)運(yùn)行時(shí)間，在每次進(jìn)行作業(yè)調(diào)度時(shí)，先計(jì)算后備作業(yè)隊(duì)列當(dāng)中的每個(gè)作業(yè)響應(yīng)比，然后找出響應(yīng)比最高的作業(yè)投入運(yùn)行。

響應(yīng)比R定義如下： R =(W+T)/T = 1+W/T

其中T為該作業(yè)估計(jì)需要的執(zhí)行時(shí)間，W為作業(yè)在后備狀態(tài)隊(duì)列中的等待時(shí)間。每當(dāng)要進(jìn)行作業(yè)調(diào)度時(shí)，系統(tǒng)計(jì)算每個(gè)作業(yè)的響應(yīng)比，選擇其中R最大者投入執(zhí)行。 算法優(yōu)點(diǎn)：由于長(zhǎng)作業(yè)也有機(jī)會(huì)投入運(yùn)行，在同一時(shí)間內(nèi)處理的作業(yè)數(shù)顯然要少于SJF法，從而采用HRRN方式時(shí)其吞吐量將小于采用SJF 法時(shí)的吞吐量。 算法缺點(diǎn)：由于每次調(diào)度前要計(jì)算響應(yīng)比，系統(tǒng)開銷也要相應(yīng)增加。

5.時(shí)間片輪轉(zhuǎn)算法

主要用于分時(shí)系統(tǒng)。這種算法中，系統(tǒng)將所有的就緒進(jìn)程按照到達(dá)時(shí)間先后次序排成一個(gè)隊(duì)列，按照先來(lái)先服務(wù)的原則運(yùn)行，但是僅僅只能運(yùn)行一個(gè)時(shí)間片，使用完一個(gè)時(shí)間片的時(shí)間以后，即使進(jìn)程并未完成其運(yùn)行，也必須釋放出處理機(jī)給下一個(gè)就緒的進(jìn)程，而被剝奪的進(jìn)程返回就緒隊(duì)列末尾重新排隊(duì)，等候再次運(yùn)行。并且通過(guò)上下文切換執(zhí)行當(dāng)前的隊(duì)首進(jìn)程，京城可以未使用完一個(gè)時(shí)間片，就讓出處理機(jī)。

在整個(gè)過(guò)程中，時(shí)間片的大小尤為重要，時(shí)間片過(guò)大，那么所有的進(jìn)程都能在一個(gè)時(shí)間片內(nèi)執(zhí)行完畢，則時(shí)間片輪轉(zhuǎn)算法就會(huì)退化成為FCFS,如果太小，那么進(jìn)程之間頻繁切換，那么處理機(jī)的開銷很大，真正用于運(yùn)行用戶進(jìn)程的時(shí)間將減小。因此時(shí)間片需要選擇恰當(dāng)。

時(shí)間片大小的確定： 1. 系統(tǒng)對(duì)響應(yīng)時(shí)間的要求 2. 就緒隊(duì)列中進(jìn)程的數(shù)目 3. 系統(tǒng)的處理能力

算法優(yōu)點(diǎn)：時(shí)間片輪轉(zhuǎn)調(diào)度算法的特點(diǎn)是簡(jiǎn)單易行、平均響應(yīng)時(shí)間短。 算法缺點(diǎn)：不利于處理緊急作業(yè)。在時(shí)間片輪轉(zhuǎn)算法中，時(shí)間片的大小對(duì)系統(tǒng)性能的影響很大，因此時(shí)間片的大小應(yīng)選擇恰當(dāng)。

6.多級(jí)反饋隊(duì)列

多級(jí)反饋隊(duì)列調(diào)度算法是一種CPU處理機(jī)調(diào)度算法，UNIX操作系統(tǒng)采取的便是這種調(diào)度算法。多級(jí)反饋隊(duì)列調(diào)度算法可以兼顧多方面的系統(tǒng)目標(biāo)。

多級(jí)反饋隊(duì)列調(diào)度算法的實(shí)現(xiàn)思想如下： * 1.應(yīng)設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)，第1級(jí)隊(duì)列的優(yōu)先級(jí)最高，第2級(jí)隊(duì)列次之，其余隊(duì)列的優(yōu)先級(jí)逐次降低。 * 2.賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也各不相同，在優(yōu)先級(jí)越高的隊(duì)列中，每個(gè)進(jìn)程的運(yùn)行時(shí)間片就越小。例如，第2級(jí)隊(duì)列的時(shí)間片要比第1級(jí)隊(duì)列的時(shí)間片長(zhǎng)一倍， ……第i+1級(jí)隊(duì)列的時(shí)間片要比第i級(jí)隊(duì)列的時(shí)間片長(zhǎng)一倍。 * 3.當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第1級(jí)隊(duì)列的末尾，按FCFS原則排隊(duì)等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如它能在該時(shí)間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)；如果它在一個(gè)時(shí)間片結(jié)束時(shí)尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第2級(jí)隊(duì)列的末尾，再同樣地按FCFS 原則等待調(diào)度執(zhí)行；如果它在第2級(jí)隊(duì)列中運(yùn)行一個(gè)時(shí)間片后仍未完成，再以同樣的方法放入第3級(jí)隊(duì)列……如此下去，當(dāng)一個(gè)長(zhǎng)進(jìn)程從第1級(jí)隊(duì)列依次降到第 n 級(jí)隊(duì)列后，在第 n 級(jí)隊(duì)列中便釆用時(shí)間片輪轉(zhuǎn)的方式運(yùn)行。 * 4.僅當(dāng)?shù)?級(jí)隊(duì)列為空時(shí)，調(diào)度程序才調(diào)度第2級(jí)隊(duì)列中的進(jìn)程運(yùn)行；僅當(dāng)?shù)? ~ (i-1)級(jí)隊(duì)列均為空時(shí)，才會(huì)調(diào)度第i級(jí)隊(duì)列中的進(jìn)程運(yùn)行。如果處理機(jī)正在執(zhí)行第i級(jí)隊(duì)列中的某進(jìn)程時(shí)，又有新進(jìn)程進(jìn)入優(yōu)先級(jí)較高的隊(duì)列（第 1 ~ (i-1)中的任何一個(gè)隊(duì)列），則此時(shí)新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第i級(jí)隊(duì)列的末尾，把處理機(jī)分配給新到的更高優(yōu)先級(jí)的進(jìn)程。

多級(jí)反饋隊(duì)列的優(yōu)勢(shì)有： * 終端型作業(yè)用戶：短作業(yè)優(yōu)先。 * 短批處理作業(yè)用戶：周轉(zhuǎn)時(shí)間較短。 * 長(zhǎng)批處理作業(yè)用戶：經(jīng)過(guò)前面幾個(gè)隊(duì)列得到部分執(zhí)行，不會(huì)長(zhǎng)期得不到處理。