今天分享一篇處理器調(diào)度相關(guān)的理論介紹文章。

1，基本概念

在多道程序系統(tǒng)中，進(jìn)程的數(shù)量往往多于處理機(jī)的個(gè)數(shù)，進(jìn)程爭(zhēng)用處理機(jī)的情況就在所難免。處理機(jī)調(diào)度是對(duì)處理機(jī)進(jìn)行分配，就是從就緒隊(duì)列中，按照一定的算法（公平、低效）選擇一個(gè)進(jìn)程并將處理機(jī)分配給它運(yùn)行，以實(shí)現(xiàn)進(jìn)程并發(fā)地執(zhí)行。

處理機(jī)調(diào)度是多道程序操作系統(tǒng)的基礎(chǔ)，它是操作系統(tǒng)設(shè)計(jì)的核心問題。

2，調(diào)度的層次

一個(gè)作業(yè)從提交開始直到完成，往往要經(jīng)歷以下三級(jí)調(diào)度，如圖2-4所示。

1) 作業(yè)調(diào)度。又稱高級(jí)調(diào)度，.其主要任務(wù)是按一定的原則從外存上處于后備狀態(tài)的作業(yè)中挑選一個(gè)（或多個(gè)）作業(yè)，給它（們）分配內(nèi)存、輸入/輸出設(shè)備等必要的資源，并建立相應(yīng)的進(jìn)程，以使它（們）獲得競(jìng)爭(zhēng)處理機(jī)的權(quán)利。簡言之，就是內(nèi)存與輔存之間的調(diào)度。對(duì)于每個(gè)作業(yè)只調(diào)入一次、調(diào)出一次。

多道批處理系統(tǒng)中大多配有作業(yè)調(diào)度，而其他系統(tǒng)中通常不需要配置作業(yè)調(diào)度。作業(yè)調(diào)度的執(zhí)行頻率較低，通常為幾分鐘一次。

2) 中級(jí)調(diào)度。又稱內(nèi)存調(diào)度。引入中級(jí)調(diào)度是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。為此，應(yīng)使那些暫時(shí)不能運(yùn)行的進(jìn)程，調(diào)至外存等待，把此時(shí)的進(jìn)程狀態(tài)稱為掛起狀態(tài)。當(dāng)它們已具備運(yùn)行條件且內(nèi)存又稍有空閑時(shí)，由中級(jí)調(diào)度來決定，把內(nèi)存上的那些已具備運(yùn)行條件的就緒進(jìn)程，再重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上等待。

3) 進(jìn)程調(diào)度。又稱為低級(jí)調(diào)度，其主要任務(wù)是按照某種方法和策略從就緒隊(duì)列中選取一個(gè)進(jìn)程，將處理機(jī)分配給它。進(jìn)程調(diào)度是操作系統(tǒng)中最基本的一種調(diào)度，在一般操作系統(tǒng)中都必須配置進(jìn)程調(diào)度。進(jìn)程調(diào)度的頻率很高，一般幾十毫秒一次。

3，三級(jí)調(diào)度的聯(lián)系

作業(yè)調(diào)度從外存的后備隊(duì)列中選擇一批作業(yè)進(jìn)入內(nèi)存，為它們建立進(jìn)程，這些進(jìn)程被送入就緒隊(duì)列，進(jìn)程調(diào)度從就緒隊(duì)列中選出一個(gè)進(jìn)程，并把其狀態(tài)改為運(yùn)行狀態(tài)，把CPU分配給它。中級(jí)調(diào)度是為了提高內(nèi)存的利用率，系統(tǒng)將那些暫時(shí)不能運(yùn)行的進(jìn)程掛起來。當(dāng)內(nèi)存空間寬松時(shí)，通過中級(jí)調(diào)度選擇具備運(yùn)行條件的進(jìn)程，將其喚醒。

1) 作業(yè)調(diào)度為進(jìn)程活動(dòng)做準(zhǔn)備，進(jìn)程調(diào)度使進(jìn)程正?；顒?dòng)起來，中級(jí)調(diào)度將暫時(shí)不能運(yùn)行的進(jìn)程掛起，中級(jí)調(diào)度處于作業(yè)調(diào)度和進(jìn)程調(diào)度之間。

2) 作業(yè)調(diào)度次數(shù)少，中級(jí)調(diào)度次數(shù)略多，進(jìn)程調(diào)度頻率最高。

3) 進(jìn)程調(diào)度是最基本的，不可或缺的。

4，調(diào)度的時(shí)機(jī)、切換與過程

進(jìn)程調(diào)度和切換程序是操作系統(tǒng)內(nèi)核程序。當(dāng)請(qǐng)求調(diào)度的事件發(fā)生后，才可能會(huì)運(yùn)行進(jìn)程調(diào)度程序，當(dāng)調(diào)度了新的就緒進(jìn)程后，才會(huì)去進(jìn)行進(jìn)程間的切換。理論上這三件事情應(yīng)該順序執(zhí)行，但在實(shí)際設(shè)計(jì)中，在操作系統(tǒng)內(nèi)核程序運(yùn)行時(shí)，如果某時(shí)發(fā)生了引起進(jìn)程調(diào)度的因素，并不一定能夠馬上進(jìn)行調(diào)度與切換。

現(xiàn)代操作系統(tǒng)中，不能進(jìn)行進(jìn)程的調(diào)度與切換的情況有以下幾種情況。

1) 在處理中斷的過程中：中斷處理過程復(fù)雜，在實(shí)現(xiàn)上很難做到進(jìn)程切換，而且中斷處理是系統(tǒng)工作的一部分，邏輯上不屬于某一進(jìn)程，不應(yīng)被剝奪處理機(jī)資源。

2) 進(jìn)程在操作系統(tǒng)內(nèi)核程序臨界區(qū)中：進(jìn)入臨界區(qū)后，需要獨(dú)占式地訪問共享數(shù)據(jù)，理論上必須加鎖，以防止其他并行程序進(jìn)入，在解鎖前不應(yīng)切換到其他進(jìn)程運(yùn)行，以加快該共享數(shù)據(jù)的釋放。

3) 其他需要完全屏蔽中斷的原子操作過程中：如加鎖、解鎖、中斷現(xiàn)場(chǎng)保護(hù)、恢復(fù)等原子操作。在原子過程中，連中斷都要屏蔽，更不應(yīng)該進(jìn)行進(jìn)程調(diào)度與切換。

如果在上述過程中發(fā)生了引起調(diào)度的條件，并不能馬上進(jìn)行調(diào)度和切換，應(yīng)置系統(tǒng)的請(qǐng)求調(diào)度標(biāo)志，直到上述過程結(jié)束后才進(jìn)行相應(yīng)的調(diào)度與切換。

應(yīng)該進(jìn)行進(jìn)程調(diào)度與切換的情況有：

1) 當(dāng)發(fā)生引起調(diào)度的條件，且當(dāng)前進(jìn)程無法繼續(xù)運(yùn)行下去時(shí)，可以馬上進(jìn)行調(diào)度與切換。如果操作系統(tǒng)只在這種情況下進(jìn)行進(jìn)程調(diào)度，就是非剝奪調(diào)度。

2) 當(dāng)中斷處理結(jié)束或自動(dòng)處理結(jié)束后，返回被中斷進(jìn)程的用戶態(tài)程序執(zhí)行現(xiàn)場(chǎng)前，若置上請(qǐng)求調(diào)度標(biāo)志，即可馬上進(jìn)行進(jìn)程調(diào)度與切換。如果操作系統(tǒng)支持這種情況下的運(yùn)行調(diào)度程序，就實(shí)現(xiàn)了剝奪方式的調(diào)度。

進(jìn)程切換往往在調(diào)度完成后立刻發(fā)生，它要求保存原進(jìn)程當(dāng)前切換點(diǎn)的現(xiàn)場(chǎng)信息，恢復(fù)被調(diào)度進(jìn)程的現(xiàn)場(chǎng)信息?，F(xiàn)場(chǎng)切換時(shí)，操作系統(tǒng)內(nèi)核將原進(jìn)程的現(xiàn)場(chǎng)信息推入到當(dāng)前進(jìn)程的內(nèi)核堆棧來保存它們，并更新堆棧指針。內(nèi)核完成從新進(jìn)程的內(nèi)核棧中裝入新進(jìn)程的現(xiàn)場(chǎng)信息、更新當(dāng)前運(yùn)行進(jìn)程空間指針、重設(shè)PC寄存器等相關(guān)工作之后，開始運(yùn)行新的進(jìn)程。

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【749907784】整理了一些個(gè)人覺得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦！?。。ê曨l教程、電子書、實(shí)戰(zhàn)項(xiàng)目及代碼)? ??

5，進(jìn)程調(diào)度方式

所謂進(jìn)程調(diào)度方式是指當(dāng)某一個(gè)進(jìn)程正在處理機(jī)上執(zhí)行時(shí)，若有某個(gè)更為重要或緊迫的進(jìn)程需要處理，即有優(yōu)先權(quán)更髙的進(jìn)程進(jìn)入就緒隊(duì)列，此時(shí)應(yīng)如何分配處理機(jī)。

通常有以下兩種進(jìn)程調(diào)度方式：

1) 非剝奪調(diào)度方式，又稱非搶占方式。是指當(dāng)一個(gè)進(jìn)程正在處理機(jī)上執(zhí)行時(shí)，即使有某個(gè)更為重要或緊迫的進(jìn)程進(jìn)入就緒隊(duì)列，仍然讓正在執(zhí)行的進(jìn)程繼續(xù)執(zhí)行，直到該進(jìn)程完成或發(fā)生某種事件而進(jìn)入阻塞狀態(tài)時(shí)，才把處理機(jī)分配給更為重要或緊迫的進(jìn)程。

在非剝奪調(diào)度方式下，一旦把CPU分配給一個(gè)進(jìn)程，那么該進(jìn)程就會(huì)保持CPU直到終止或轉(zhuǎn)換到等待狀態(tài)。這種方式的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單、系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)，但它不能用于分時(shí)系統(tǒng)和大多數(shù)的實(shí)時(shí)系統(tǒng)。

2) 剝奪調(diào)度方式，又稱搶占方式。是指當(dāng)一個(gè)進(jìn)程正在處理機(jī)上執(zhí)行時(shí)，若有某個(gè)更為重要或緊迫的進(jìn)程需要使用處理機(jī)，則立即暫停正在執(zhí)行的進(jìn)程，將處理機(jī)分配給這個(gè)更為重要或緊迫的進(jìn)程。.

采用剝奪式的調(diào)度，對(duì)提高系統(tǒng)吞吐率和響應(yīng)效率都有明顯的好處。但“剝奪”不是一種任意性行為，必須遵循一定的原則，主要有：優(yōu)先權(quán)、短進(jìn)程優(yōu)先和時(shí)間的原則等。

調(diào)度的基本準(zhǔn)則

不同的調(diào)度算法具有不同的特性，在選擇調(diào)度算法時(shí)，必須考慮算法所具有的特性。為了比較處理機(jī)調(diào)度算法的性能，人們提出很多評(píng)價(jià)準(zhǔn)則，下面介紹主要的幾種：

1) CPU利用率。CPU是計(jì)算機(jī)系統(tǒng)中最重要和昂貴的資源之一，所以應(yīng)盡可能使CPU 保持“忙”狀態(tài)，使這一資源利用率最高。

2) 系統(tǒng)吞吐量。表示單位時(shí)間內(nèi)CPU完成作業(yè)的數(shù)量。長作業(yè)需要消耗較長的處理機(jī)時(shí)間，因此會(huì)降低系統(tǒng)的吞吐量。而對(duì)于短作業(yè)，它們所需要消耗的處理機(jī)時(shí)間較短，因此能提高系統(tǒng)的吞吐量。調(diào)度算法和方式的不同，也會(huì)對(duì)系統(tǒng)的吞吐量產(chǎn)生較大的影響。

3) 周轉(zhuǎn)時(shí)間。是指從作業(yè)提交到作業(yè)完成所經(jīng)歷的時(shí)間，包括作業(yè)等待、在就緒隊(duì)列中排隊(duì)、在處迤機(jī)上運(yùn)行以及進(jìn)行輸入/輸出操作所花費(fèi)時(shí)間的總和。

作業(yè)的周轉(zhuǎn)時(shí)間可用公式表示如下：

周轉(zhuǎn)時(shí)間 = 作業(yè)完成時(shí)間 - 作業(yè)提交時(shí)間

平均周轉(zhuǎn)時(shí)間是指多個(gè)作業(yè)周轉(zhuǎn)時(shí)間的平均值：

平均周轉(zhuǎn)時(shí)間 = (作業(yè)1的周轉(zhuǎn)時(shí)間 + … + 作業(yè) n 的周轉(zhuǎn)時(shí)間) / n

帶權(quán)周轉(zhuǎn)時(shí)間是指作業(yè)周轉(zhuǎn)時(shí)間與作業(yè)實(shí)際運(yùn)行時(shí)間的比值：

平均帶權(quán)周轉(zhuǎn)時(shí)間是指多個(gè)作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間的平均值：

平均帶權(quán)周轉(zhuǎn)時(shí)間 = (作業(yè)1的帶權(quán)周轉(zhuǎn)時(shí)間 + … + 作業(yè) n 的帶權(quán)周轉(zhuǎn)時(shí)間) / n

4) 等待時(shí)間。=開始時(shí)間—提交時(shí)間。

是指進(jìn)程處于等待處理機(jī)狀態(tài)時(shí)間之和，等待時(shí)間越長，用戶滿意度越低。處理機(jī)調(diào)度算法實(shí)際上并不影響作業(yè)執(zhí)行或輸入/輸出操作的時(shí)間，只影響作業(yè)在就緒隊(duì)列中等待所花的時(shí)間。因此，衡量一個(gè)調(diào)度算法的優(yōu)劣常常只需簡單地考察等待時(shí)間。

5) 響應(yīng)時(shí)間。是指從用戶提交請(qǐng)求到系統(tǒng)首次產(chǎn)生響應(yīng)所用的時(shí)間。在交互式系統(tǒng)中，周轉(zhuǎn)時(shí)間不可能是最好的評(píng)價(jià)準(zhǔn)則，一般采用響應(yīng)時(shí)間作為衡量調(diào)度算法的重要準(zhǔn)則之一。從用戶角度看，調(diào)度策略應(yīng)盡量降低響應(yīng)時(shí)間，使響應(yīng)時(shí)間處在用戶能接受的范圍之內(nèi)。

要想得到一個(gè)滿足所有用戶和系統(tǒng)要求的算法幾乎是不可能的。設(shè)計(jì)調(diào)度程序，一方面要滿足特定系統(tǒng)用戶的要求（如某些實(shí)時(shí)和交互進(jìn)程快速響應(yīng)要求)，另一方面要考慮系統(tǒng)整體效率（如減少整個(gè)系統(tǒng)進(jìn)程平均周轉(zhuǎn)時(shí)間），同時(shí)還要考慮調(diào)度算法的開銷。

操作系統(tǒng)典型調(diào)度算法

在操作系統(tǒng)中存在多種調(diào)度算法，其中有的調(diào)度算法適用于作業(yè)調(diào)度，有的調(diào)度算法適用于進(jìn)程調(diào)度，有的調(diào)度算法兩者都適用。下面介紹幾種常用的調(diào)度算法。

先來先服務(wù)(FCFS)調(diào)度算法

FCFS調(diào)度算法是一種最簡單的調(diào)度算法，該調(diào)度算法既可以用于作業(yè)調(diào)度也可以用于進(jìn)程調(diào)度。

在作業(yè)調(diào)度中，算法每次從后備作業(yè)隊(duì)列中選擇最先進(jìn)入該隊(duì)列的一個(gè)或幾個(gè)作業(yè)，將它們調(diào)入內(nèi)存，分配必要的資源，創(chuàng)建進(jìn)程并放入就緒隊(duì)列。

在進(jìn)程調(diào)度中，F(xiàn)CFS調(diào)度算法每次從就緒隊(duì)列中選擇最先進(jìn)入該隊(duì)列的進(jìn)程，將處理機(jī)分配給它，使之投入運(yùn)行，直到完成或因某種原因而阻塞時(shí)才釋放處理機(jī)。

下面通過一個(gè)實(shí)例來說明FCFS調(diào)度算法的性能。假設(shè)系統(tǒng)中有4個(gè)作業(yè)，它們的提交時(shí)間分別是8、8.4、8.8、9，運(yùn)行時(shí)間依次是2、1、0.5、0.2，系統(tǒng)釆用FCFS調(diào)度算法，這組作業(yè)的平均等待時(shí)間、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間見表2-3。

平均等待時(shí)間 t = (0+1.6+2.2+2.5)/4=1.575

平均周轉(zhuǎn)時(shí)間 T = (2+2.6+2.7+2.7)/4=2.5

平均帶權(quán)周轉(zhuǎn)時(shí)間 W = (1+2.6+5.牡13.5)/4=5.625

FCFS調(diào)度算法屬于不可剝奪算法。從表面上看，它對(duì)所有作業(yè)都是公平的，但若一個(gè)長作業(yè)先到達(dá)系統(tǒng)，就會(huì)使后面許多短作業(yè)等待很長時(shí)間，因此它不能作為分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)的主要調(diào)度策略。但它常被結(jié)合在其他調(diào)度策略中使用。例如，在使用優(yōu)先級(jí)作為調(diào)度策略的系統(tǒng)中，往往對(duì)多個(gè)具有相同優(yōu)先級(jí)的進(jìn)程按FCFS原則處理。

FCFS調(diào)度算法的特點(diǎn)是算法簡單，但效率低；對(duì)長作業(yè)比較有利，但對(duì)短作業(yè)不利（相對(duì)SJF和高響應(yīng)比）；有利于CPU繁忙型作業(yè)，而不利于I/O繁忙型作業(yè)。

短作業(yè)優(yōu)先(SJF)調(diào)度算法

短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法（Shortest Job First ）是指對(duì)短作業(yè)（進(jìn)程）優(yōu)先調(diào)度的算法。短作業(yè)優(yōu)先(SJF)調(diào)度算法是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。而短進(jìn)程優(yōu)先(SPF)調(diào)度算法，則是從就緒隊(duì)列中選擇一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使之立即執(zhí)行，直到完成或發(fā)生某事件而阻塞時(shí)，才釋放處理機(jī)。

例如，考慮表2-3中給出的一組作業(yè)，若系統(tǒng)采用短作業(yè)優(yōu)先調(diào)度算法，其平均等待時(shí)間、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間見表2-4。

平均等待時(shí)間 t = (0+2.3+1.4+1)/4=1.175

平均周轉(zhuǎn)時(shí)間 T = (2+3.3+1.9+1.2)/4=2.1

平均帶權(quán)周轉(zhuǎn)時(shí)間 W = (1+3.3+3.8+6)/4=3.525

SJF調(diào)度算法也存在不容忽視的缺點(diǎn)：

該算法對(duì)長作業(yè)不利，由表2-3和表2-4可知，SJF調(diào)度算法中長作業(yè)的周轉(zhuǎn)時(shí)間會(huì)增加。更嚴(yán)重的是，如果有一長作業(yè)進(jìn)入系統(tǒng)的后備隊(duì)列，由于調(diào)度程序總是優(yōu)先調(diào)度那些 (即使是后進(jìn)來的）短作業(yè)，將導(dǎo)致長作業(yè)長期不被調(diào)度（“饑餓”現(xiàn)象，注意區(qū)分“死鎖”。后者是系統(tǒng)環(huán)形等待，前者是調(diào)度策略問題）。

該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)會(huì)被及時(shí)處理。

由于作業(yè)的長短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶又可能會(huì)有意或無意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。

注意，SJF調(diào)度算法的平均等待時(shí)間、平均周轉(zhuǎn)時(shí)間最少。

優(yōu)先級(jí)調(diào)度算法

優(yōu)先級(jí)調(diào)度算法又稱優(yōu)先權(quán)調(diào)度算法，該算法既可以用于作業(yè)調(diào)度，也可以用于進(jìn)程調(diào)度，該算法中的優(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)行過程中，根據(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í)間的長短、就緒進(jìn)程等待CPU時(shí)間的長短。

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

高響應(yīng)比優(yōu)先調(diào)度算法主要用于作業(yè)調(diào)度，該算法是對(duì)FCFS調(diào)度算法和SJF調(diào)度算法的一種綜合平衡，同時(shí)考慮每個(gè)作業(yè)的等待時(shí)間和估計(jì)的運(yùn)行時(shí)間。在每次進(jìn)行作業(yè)調(diào)度時(shí)，先計(jì)算后備作業(yè)隊(duì)列中每個(gè)作業(yè)的響應(yīng)比，從中選出響應(yīng)比最高的作業(yè)投入運(yùn)行。

響應(yīng)比的變化規(guī)律可描述為：

根據(jù)公式可知：

當(dāng)作業(yè)的等待時(shí)間相同時(shí)，則要求服務(wù)時(shí)間越短，其響應(yīng)比越高，有利于短作業(yè)。

當(dāng)要求服務(wù)時(shí)間相同時(shí)，作業(yè)的響應(yīng)比由其等待時(shí)間決定，等待時(shí)間越長，其響應(yīng)比越高，因而它實(shí)現(xiàn)的是先來先服務(wù)。

對(duì)于長作業(yè)，作業(yè)的響應(yīng)比可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長時(shí)，其響應(yīng)比便可升到很高，從而也可獲得處理機(jī)。克服了饑餓狀態(tài)，兼顧了長作業(yè)。

時(shí)間片輪轉(zhuǎn)調(diào)度算法

時(shí)間片輪轉(zhuǎn)調(diào)度算法主要適用于分時(shí)系統(tǒng)。在這種算法中，系統(tǒng)將所有就緒進(jìn)程按到達(dá)時(shí)間的先后次序排成一個(gè)隊(duì)列，進(jìn)程調(diào)度程序總是選擇就緒隊(duì)列中第一個(gè)進(jìn)程執(zhí)行，即先來先服務(wù)的原則，但僅能運(yùn)行一個(gè)時(shí)間片，如100ms。在使用完一個(gè)時(shí)間片后，即使進(jìn)程并未完成其運(yùn)行，它也必須釋放出（被剝奪）處理機(jī)給下一個(gè)就緒的進(jìn)程，而被剝奪的進(jìn)程返回到就緒隊(duì)列的末尾重新排隊(duì)，等候再次運(yùn)行。

在時(shí)間片輪轉(zhuǎn)調(diào)度算法中，時(shí)間片的大小對(duì)系統(tǒng)性能的影響很大。如果時(shí)間片足夠大，以至于所有進(jìn)程都能在一個(gè)時(shí)間片內(nèi)執(zhí)行完畢，則時(shí)間片輪轉(zhuǎn)調(diào)度算法就退化為先來先服務(wù)調(diào)度算法。如果時(shí)間片很小，那么處理機(jī)將在進(jìn)程間過于頻繁切換，使處理機(jī)的開銷增大，而真正用于運(yùn)行用戶進(jìn)程的時(shí)間將減少。因此時(shí)間片的大小應(yīng)選擇適當(dāng)。

時(shí)間片的長短通常由以下因素確定：系統(tǒng)的響應(yīng)時(shí)間、就緒隊(duì)列中的進(jìn)程數(shù)目和系統(tǒng)的處理能力。

多級(jí)反饋隊(duì)列調(diào)度算法（集合了前幾種算法的優(yōu)點(diǎn)）

多級(jí)反饋隊(duì)列調(diào)度算法是時(shí)間片輪轉(zhuǎn)調(diào)度算法和優(yōu)先級(jí)調(diào)度算法的綜合和發(fā)展，如圖2-5 所示。通過動(dòng)態(tài)調(diào)整進(jìn)程優(yōu)先級(jí)和時(shí)間片大小，多級(jí)反饋隊(duì)列調(diào)度算法可以兼顧多方面的系統(tǒng)目標(biāo)。例如，為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時(shí)間而照顧短進(jìn)程；為獲得較好的I/O設(shè)備利用率和縮短響應(yīng)時(shí)間而照顧I/O型進(jìn)程；同時(shí)，也不必事先估計(jì)進(jìn)程的執(zhí)行時(shí)間。

多級(jí)反饋隊(duì)列調(diào)度算法的實(shí)現(xiàn)思想如下：

應(yīng)設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)，第1級(jí)隊(duì)列的優(yōu)先級(jí)最高，第2級(jí)隊(duì)列次之，其余隊(duì)列的優(yōu)先級(jí)逐次降低。

賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也各不相同，在優(yōu)先級(jí)越高的隊(duì)列中，每個(gè)進(jìn)程的運(yùn)行時(shí)間片就越小。例如，第2級(jí)隊(duì)列的時(shí)間片要比第1級(jí)隊(duì)列的時(shí)間片長一倍， ……第i+1級(jí)隊(duì)列的時(shí)間片要比第i級(jí)隊(duì)列的時(shí)間片長一倍。

當(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è)長進(jìn)程從第1級(jí)隊(duì)列依次降到第 n 級(jí)隊(duì)列后，在第 n 級(jí)隊(duì)列中便釆用時(shí)間片輪轉(zhuǎn)的方式運(yùn)行。

僅當(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í)間較短。

• 長批處理作業(yè)用戶：經(jīng)過前面幾個(gè)隊(duì)列得到部分執(zhí)行，不會(huì)長期得不到處理。

原文作者：【一起學(xué)嵌入式】