在操作系統(tǒng)中，幾乎所有進(jìn)程的I/O請(qǐng)求或計(jì)算都是交替突發(fā)的。例如一個(gè)進(jìn)程從磁盤讀取了一段數(shù)據(jù)，然后計(jì)算一段時(shí)間，將計(jì)算得到的數(shù)據(jù)重新寫入磁盤，如此周而復(fù)始的循環(huán)。假如一些進(jìn)程將絕大多數(shù)時(shí)間花費(fèi)到計(jì)算上，我們稱此類進(jìn)程為計(jì)算密集型進(jìn)程；而另一部分進(jìn)程花費(fèi)大多數(shù)時(shí)間在IO等待上，我們稱此類進(jìn)程為I/O密集型進(jìn)程。隨著CPU變得越來(lái)越快，更多的進(jìn)程傾向于I/O密集型。

1、調(diào)度時(shí)機(jī)

有關(guān)調(diào)度處理的一個(gè)重要問題就是何時(shí)進(jìn)行進(jìn)程調(diào)度，一般來(lái)說(shuō)發(fā)生以下四種情形時(shí)系統(tǒng)將對(duì)進(jìn)程進(jìn)行調(diào)度：

一、在創(chuàng)建一個(gè)新進(jìn)程后，需要決定是先運(yùn)行父進(jìn)程還是子進(jìn)程。因?yàn)檫@兩種進(jìn)程都處于就緒狀態(tài)，所以這是一個(gè)正常的調(diào)度決策。一般來(lái)說(shuō)先運(yùn)行父進(jìn)程還是子進(jìn)程和操作系統(tǒng)有關(guān)，不同的操作系統(tǒng)運(yùn)行順序也不同。

二、在一個(gè)進(jìn)程退出時(shí)需要作出調(diào)度決策。一個(gè)進(jìn)程不在運(yùn)行則會(huì)讓出CPU，所以必須從就緒的進(jìn)程中選擇一個(gè)進(jìn)程運(yùn)行，如果沒有就緒進(jìn)程，通常會(huì)運(yùn)行一個(gè)系統(tǒng)提供的空閑進(jìn)程。

三、當(dāng)一個(gè)進(jìn)程阻塞在I/O和信號(hào)量或其他原因阻塞時(shí)，必須選擇另一個(gè)進(jìn)程運(yùn)行。

四、在一個(gè)I/O中斷發(fā)生時(shí)，必須做出調(diào)度決策。如果中斷發(fā)生在IO設(shè)備，當(dāng)該IO設(shè)備完成工作后，會(huì)將等待該IO設(shè)備的進(jìn)程設(shè)置為就緒狀態(tài)，但是否運(yùn)行這些就緒進(jìn)程就要根據(jù)實(shí)際調(diào)度算法判定，有時(shí)會(huì)運(yùn)行被中斷的進(jìn)程，有時(shí)會(huì)運(yùn)行某個(gè)就緒進(jìn)程。

2、調(diào)度算法分類：

如果硬件提供50HZ或其他頻率的周期性中斷，人們可以再每個(gè)周期或每k個(gè)周期中斷時(shí)做出調(diào)度策略。根據(jù)如何處理時(shí)鐘中斷分為兩類：非搶占式中斷和搶占式中斷。非搶占式中斷時(shí)讓一個(gè)進(jìn)程一直運(yùn)行直至堵塞或者自動(dòng)釋放CPU，該進(jìn)程不會(huì)被強(qiáng)制掛起。其結(jié)果是在中斷產(chǎn)生時(shí)，如果沒有更高優(yōu)先級(jí)的進(jìn)程等待到時(shí)，該進(jìn)程會(huì)一直運(yùn)行下去。

相反，搶占式中斷會(huì)挑選一個(gè)進(jìn)程，并讓該進(jìn)程運(yùn)行某一個(gè)固定的最大值，如果在該時(shí)間段內(nèi)進(jìn)程仍然在運(yùn)行，則該進(jìn)程被掛起，調(diào)度程序選擇另一個(gè)進(jìn)程進(jìn)行執(zhí)行。

3、具體分類：

批處理：批處理一般運(yùn)用在商業(yè)領(lǐng)域，用來(lái)處理薪水冊(cè)、存貨清單等。在批處理系統(tǒng)中，不會(huì)有用戶不耐煩地在終端旁邊等待一個(gè)短請(qǐng)求，因此其常用非搶占式算法。 交互式：在交互式系統(tǒng)中，為了避免一個(gè)進(jìn)程霸占CPU拒絕為其他用戶服務(wù)，所以用的都是搶占式算法。 實(shí)時(shí)：在實(shí)時(shí)操作系統(tǒng)中，搶占有時(shí)不是必須的，因?yàn)橄到y(tǒng)知道他們有可能會(huì)長(zhǎng)時(shí)間得不到運(yùn)行，所以會(huì)很快地完成各自的工作然后堵塞。實(shí)時(shí)系統(tǒng)和交互系統(tǒng)的差別是：實(shí)時(shí)系統(tǒng)只運(yùn)行哪些用來(lái)推進(jìn)現(xiàn)有應(yīng)用程序的，而交互式系統(tǒng)則是通用的。

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

4、調(diào)度算法在不同環(huán)境中的一些目標(biāo)：

所有系統(tǒng)：

公平：給每個(gè)進(jìn)程公平的CPU份額

策略強(qiáng)制執(zhí)行：看到所宣布的策略執(zhí)行

平衡：保持系統(tǒng)的所有部分都忙碌 批處理系統(tǒng)：

吞吐量：每小時(shí)最大作業(yè)數(shù) 周轉(zhuǎn)時(shí)間：從提交到終止間的最小時(shí)間 CPU利用率：保持CPU始終忙碌

交互式系統(tǒng)：

相應(yīng)時(shí)間：快速相應(yīng)用戶請(qǐng)求 均衡性：滿足用戶的期望

實(shí)時(shí)系統(tǒng)：

滿足截止時(shí)間：避免丟失數(shù)據(jù) 可預(yù)測(cè)性：在多媒體系統(tǒng)中避免品質(zhì)降低

5、具體調(diào)度算法：

1、批處理中調(diào)度算法：

（1） 先來(lái)先服務(wù)：最簡(jiǎn)單的非搶占式算法，基本上維持一個(gè)就緒進(jìn)程的單一隊(duì)列，有新作業(yè)到來(lái)時(shí)會(huì)插入到隊(duì)列尾部。每次系統(tǒng)調(diào)用時(shí)從隊(duì)列頭部取作業(yè)進(jìn)行運(yùn)行，指導(dǎo)該作業(yè)完成。 優(yōu)點(diǎn)：易于理解并且便于在程序中運(yùn)用。缺點(diǎn)：當(dāng)存在一個(gè)需要占用較長(zhǎng)CPU的進(jìn)程存在時(shí)，會(huì)造成后邊進(jìn)程持續(xù)等待而無(wú)法執(zhí)行，及時(shí)等待進(jìn)程中存在只需要很少CPU時(shí)間即可完成的進(jìn)程。

（2）、最短作業(yè)優(yōu)先：最短作業(yè)優(yōu)先屬于運(yùn)行作業(yè)預(yù)知的非搶占式算法

如上圖所示作業(yè),這里四個(gè)作業(yè)假如分別為A、B、C和D，其運(yùn)行時(shí)間分別為8,4,4,4.若按照先來(lái)先服務(wù)算法，則平均周轉(zhuǎn)時(shí)間為（8 + 12 + 16 + 20）/ 4 = 14,。如果按照最短作業(yè)算法，如下所示：

則平均周轉(zhuǎn)時(shí)間為（4 + 8 + 12+ 20）/ 4 = 11.則很明顯最短作業(yè)算法得到的平均周轉(zhuǎn)時(shí)間最短。但必須指出，只有在所有的作業(yè)都可同時(shí)運(yùn)行的情況下，最短作業(yè)算法才最有效。

（3）、最短剩余作業(yè)優(yōu)先：使用該算法，調(diào)度程序總是選擇運(yùn)行剩余時(shí)間最短的那個(gè)作業(yè)。當(dāng)新的進(jìn)程到來(lái)時(shí)，如果新的程序比當(dāng)前正在運(yùn)行的程序完成所需更短的時(shí)間，則當(dāng)前進(jìn)程掛起，運(yùn)行新的進(jìn)程。 2、交互系統(tǒng)中的調(diào)度

（1）、輪轉(zhuǎn)調(diào)度：輪轉(zhuǎn)調(diào)度是一種最古老，最簡(jiǎn)單且最公平使用最廣的算法。它為每一個(gè)進(jìn)程分配一個(gè)時(shí)間段

成為時(shí)間片。如果在該時(shí)間片結(jié)束時(shí)該進(jìn)程還在運(yùn)行，則將剝奪CPU并分配給另一個(gè)進(jìn)程。如果該進(jìn)程在時(shí)間片內(nèi)堵塞或者結(jié)束，則CPU立即切換。時(shí)間片調(diào)度容易實(shí)現(xiàn)，調(diào)度程序只需要維護(hù)一張可運(yùn)行程序的進(jìn)程列表即可。

時(shí)間片輪轉(zhuǎn)調(diào)度中存在的問題就是時(shí)間片長(zhǎng)度的選擇，因?yàn)閺囊粋€(gè)進(jìn)程切換到另一個(gè)進(jìn)程需要花費(fèi)時(shí)間處理管

理事務(wù)——保存和裝入寄存器值及內(nèi)存映像、更新各種表格和列表、清除和重新調(diào)入內(nèi)存高速緩存。假如進(jìn)程切換，或者叫做上下文切換時(shí)間過短，則CPU在花費(fèi)太多時(shí)間用去上下文切換，CPU利用率佳慧降低。如果時(shí)間片選擇過長(zhǎng)，假如存在50個(gè)進(jìn)程，時(shí)間片選擇100ms。如果第50個(gè)進(jìn)程只需要1ms就可以完成，但在時(shí)間片輪轉(zhuǎn)算法中其只有等待5s鐘后才有機(jī)會(huì)運(yùn)行。顯然對(duì)這個(gè)進(jìn)程是不公平的。

（2）、優(yōu)先級(jí)調(diào)度：輪轉(zhuǎn)調(diào)度隱含的假設(shè)是所有進(jìn)程同等重要，也就是所有進(jìn)程的優(yōu)先級(jí)相同。然后對(duì)于操作

系統(tǒng)和用戶會(huì)認(rèn)為某些進(jìn)程要比其他進(jìn)程更為重要。因此調(diào)度算法調(diào)度時(shí)需要考慮一些外部因素。優(yōu)先級(jí)調(diào)度的基本思想是為每一個(gè)進(jìn)程賦予一個(gè)優(yōu)先級(jí)，允許最高優(yōu)先級(jí)的可運(yùn)行程先運(yùn)行。

同時(shí)為了防止高優(yōu)先級(jí)的程序一直占用CPU，調(diào)度程序可在每個(gè)時(shí)鐘中斷時(shí)降低當(dāng)前進(jìn)程的優(yōu)先級(jí)，如果當(dāng)前進(jìn)

程的優(yōu)先級(jí)低于次高優(yōu)先級(jí)進(jìn)程，則進(jìn)行進(jìn)程切換。一個(gè)可行的方法是，每個(gè)進(jìn)程可以賦予一個(gè)允許運(yùn)行的最大時(shí)間片，當(dāng)這個(gè)時(shí)間片用完時(shí)，下一個(gè)次高優(yōu)先級(jí)的進(jìn)程獲得機(jī)會(huì)運(yùn)行。

（3）、多級(jí)隊(duì)列：多級(jí)隊(duì)列的思想是將進(jìn)程分為幾個(gè)優(yōu)先級(jí)類，當(dāng)一個(gè)進(jìn)程用完所分配的時(shí)間片后將會(huì)被移到

下一類。我們考慮一個(gè)需要100個(gè)時(shí)間片來(lái)進(jìn)行連續(xù)計(jì)算的計(jì)算的進(jìn)程。假如它最初被分配1個(gè)時(shí)間片，則時(shí)間片用完之后將其移到下一類，同時(shí)它將獲得2個(gè)時(shí)間片，依次類推，接下來(lái)其將獲得8、16、32和64個(gè)時(shí)間片。這樣其通過7次進(jìn)程切換就可以完成，如果是純粹的時(shí)間片輪轉(zhuǎn)算法則需要100此進(jìn)程切換。并且隨著優(yōu)先級(jí)的不斷下降，其可以將CPU讓給運(yùn)行時(shí)間較短的進(jìn)程。

例如：伯克利制造的注明的XDS 940系統(tǒng)有4個(gè)優(yōu)先級(jí)類，分別是終端、IO、短時(shí)間片和長(zhǎng)時(shí)間片。當(dāng)一個(gè)一直

等待終端的進(jìn)程被喚醒時(shí)，它被轉(zhuǎn)到最高優(yōu)先級(jí)類（終端）。當(dāng)?shù)却疟P數(shù)據(jù)進(jìn)程就緒時(shí)被轉(zhuǎn)到第二類。當(dāng)進(jìn)程時(shí)間片用完仍就緒一般被放到第三類。但如果一個(gè)進(jìn)程已經(jīng)多次用完時(shí)間片而從未因終端或其他IO原因阻塞，那么它會(huì)被轉(zhuǎn)入最低優(yōu)先級(jí)類。

（4）、保證調(diào)度：一個(gè)完全不同的調(diào)度算法是向用戶做出明確的性能保證，然后去實(shí)現(xiàn)它。一個(gè)簡(jiǎn)單的保證

是：若系統(tǒng)工作時(shí)有n個(gè)用戶登錄，則每個(gè)用戶獲得1/n的CPU處理能力。同理，對(duì)于一個(gè)含有n個(gè)進(jìn)程的系統(tǒng)，若所有進(jìn)程都是等價(jià)的，則每個(gè)進(jìn)程獲得1/n的CPU時(shí)間。為了實(shí)現(xiàn)所做的保證，系統(tǒng)必須跟蹤各個(gè)進(jìn)程自創(chuàng)建以來(lái)獲得的所有CPU時(shí)間，然后計(jì)算其應(yīng)獲得的時(shí)間。由于兩者都是已知的，所以很容易根據(jù)兩者的大小為進(jìn)程分配時(shí)間。

（5）、彩票調(diào)度：其基本思想是向進(jìn)程提供各種系統(tǒng)資源的彩票。一旦需要作出一項(xiàng)調(diào)整決策時(shí)就隨機(jī)抽取一

張彩票，擁有該彩票的進(jìn)程獲得資源。在用用到CPU調(diào)度時(shí)，系統(tǒng)可以掌握每秒鐘50此的一種彩票，作為獎(jiǎng)勵(lì)每個(gè)獲獎(jiǎng)?wù)呖梢缘玫?0ms的CPU時(shí)間。

假如系統(tǒng)出售100張彩票，而一個(gè)進(jìn)程持有其中的20張，那么在一次抽獎(jiǎng)中該進(jìn)程獲獎(jiǎng)的概率為20%。在較長(zhǎng)的

時(shí)間中，該進(jìn)程會(huì)得到20%的CPU。相對(duì)于優(yōu)先級(jí)調(diào)度，此調(diào)度算法更容易理解：擁有f份額的進(jìn)程大約得到系統(tǒng)資源的f份額。

彩票調(diào)度一個(gè)有趣的性質(zhì)是，如果一個(gè)新進(jìn)程出現(xiàn)并獲得一些彩票，那么在下一次調(diào)度時(shí)該進(jìn)程會(huì)和其擁有相

同數(shù)量彩票的進(jìn)程具有相同的優(yōu)先級(jí)，也就是說(shuō)彩票調(diào)度算法反應(yīng)迅速。

如果我們希望協(xié)作進(jìn)程可以交換他們的彩票。例如一個(gè)客戶進(jìn)程向服務(wù)器進(jìn)程發(fā)送消息并阻塞，其可以將自己

手里的彩票交給服務(wù)器，這樣就增加了服務(wù)器獲得CPU的概率，服務(wù)器運(yùn)行完成后將彩票再退還給客戶進(jìn)程。

（6）、公平分享調(diào)度：以上講的各個(gè)進(jìn)程調(diào)度算法關(guān)注的都是進(jìn)程本身，并沒有關(guān)注進(jìn)程的所有者是誰(shuí)。假如

一個(gè)系統(tǒng)有兩個(gè)用戶，其中一個(gè)有9個(gè)進(jìn)程，另一個(gè)只有一個(gè)進(jìn)程。如果按照上述調(diào)度算法，用戶1將獲得90%的CPU實(shí)踐，用戶2只獲得10%的時(shí)間。為了避免這種情形，操作系統(tǒng)必須考慮這一因素，定義一個(gè)公平策略。例如每個(gè)用戶分得50%的CPU時(shí)間保證，無(wú)論用戶有多少個(gè)進(jìn)程存在，每個(gè)用戶都會(huì)得到應(yīng)有的CPU份額。

例如：考慮兩個(gè)用戶的系統(tǒng)，每個(gè)用戶獲得50%的CPU時(shí)間，用戶1有四個(gè)進(jìn)程：A，B，C和D。用戶2只有一個(gè)進(jìn)

程E，則按照輪轉(zhuǎn)調(diào)度算法進(jìn)程執(zhí)行順序是AEBECEDEAEBECE….如果假設(shè)用戶1獲得的時(shí)間為2的兩倍，則執(zhí)行順序是ABECDEABE…。當(dāng)然，也有可能存在其他情況，這取決于系統(tǒng)對(duì)公平的定義。