1．先來先服務(wù)調(diào)度算法
先來先服務(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ī)淌山。
來看一個(gè)例子，假設(shè)有三個(gè)進(jìn)程和它們各自執(zhí)行時(shí)間（以毫秒為單位）如下表：
那么如果三個(gè)進(jìn)程按照P1, P2, P3的順序啟動(dòng)的話顾瞻，按照先到先服務(wù)的調(diào)度算法泼疑，執(zhí)行過程如下：
平均等待時(shí)間就是(0 + 24 + 27) / 3 = 17毫秒。FCFS算法是非搶占式的荷荤，一旦內(nèi)核將CPU分配給一個(gè)進(jìn)程就不會(huì)被釋放
了退渗，除非進(jìn)程結(jié)束或者請(qǐng)求I/O阻塞。這也是我們之前學(xué)習(xí)的多任務(wù)系統(tǒng)的特點(diǎn)蕴纳。
2会油、基于優(yōu)先級(jí)調(diào)度 (Priority Scheduling)
在優(yōu)先級(jí)調(diào)度算法中，每個(gè)進(jìn)程都關(guān)聯(lián)一個(gè)優(yōu)先級(jí)古毛，內(nèi)核將CPU分配給最高優(yōu)先級(jí)的進(jìn)程翻翩。具有相同優(yōu)先級(jí)的進(jìn)程，按照
先來先服務(wù)的原則進(jìn)行調(diào)度稻薇。假設(shè)進(jìn)程的執(zhí)行時(shí)間和優(yōu)先級(jí)如下嫂冻，并且這些進(jìn)程同時(shí)存在于內(nèi)存中時(shí)，內(nèi)核基于優(yōu)先級(jí)的
調(diào)度過程如下：
采取基于優(yōu)先級(jí)調(diào)度算法要考慮進(jìn)程餓死的問題塞椎，因?yàn)楦邇?yōu)先級(jí)的進(jìn)程總是會(huì)被優(yōu)先調(diào)度桨仿，具有低優(yōu)先級(jí)的進(jìn)程可能永遠(yuǎn)
都不會(huì)被內(nèi)核調(diào)度執(zhí)行。Aging是對(duì)于這個(gè)問題的一個(gè)解決方案案狠，所謂Aging就是指逐漸提高系統(tǒng)中長(zhǎng)時(shí)間等待的進(jìn)程的
優(yōu)先級(jí)服傍。比如如果優(yōu)先級(jí)的范圍從127到0（127表示最低優(yōu)先級(jí)），那么我們可以每15分鐘將等待進(jìn)程的優(yōu)先級(jí)加1骂铁。最終
經(jīng)過一段時(shí)間吹零，即便是擁有最低優(yōu)先級(jí)127的進(jìn)程也會(huì)變成系統(tǒng)中最高優(yōu)先級(jí)的進(jìn)程，從而被執(zhí)行从铲。
優(yōu)先級(jí)調(diào)度可以搶占式或者非搶占式的瘪校。當(dāng)一個(gè)進(jìn)程在Ready隊(duì)列中時(shí)，內(nèi)核將它的優(yōu)先級(jí)與正在CPU上執(zhí)行的進(jìn)程的優(yōu)先級(jí)
進(jìn)行比較阱扬。當(dāng)發(fā)現(xiàn)這個(gè)新進(jìn)程的優(yōu)先級(jí)比正在執(zhí)行的進(jìn)程高時(shí)：對(duì)于搶占式內(nèi)核馍刮，新進(jìn)程會(huì)搶占CPU窃蹋，之前正在執(zhí)行的進(jìn)程
轉(zhuǎn)入Ready隊(duì)列匈辱；對(duì)于非搶占式內(nèi)核树酪，新進(jìn)程只會(huì)被放置在Ready隊(duì)列的頭部，不會(huì)搶占正在執(zhí)行的進(jìn)程滥朱。
3懂版、短進(jìn)程優(yōu)先(SCBF--Shortest CPU Burst First)
最短CPU運(yùn)行期優(yōu)先[調(diào)度算法](http://baike.baidu.com/view/2963962.htm)(SCBF--Shortest CPU Burst First)
該算法從就緒隊(duì)列中選出下一個(gè)“CPU執(zhí)行期最短”的進(jìn)程，為之分配處理機(jī)。
最短作業(yè)優(yōu)先調(diào)度是優(yōu)先級(jí)調(diào)度的特例耍贾。在優(yōu)先級(jí)調(diào)度中我們根據(jù)進(jìn)程的優(yōu)先級(jí)來進(jìn)行調(diào)度简肴，在最短作業(yè)優(yōu)先調(diào)度中我們
根據(jù)作業(yè)的執(zhí)行時(shí)間長(zhǎng)短來調(diào)度。通過下面的例子來看看SJF是怎樣調(diào)度的。
進(jìn)程1首先執(zhí)行了1毫秒，當(dāng)執(zhí)行時(shí)間更短的進(jìn)程2進(jìn)入Ready隊(duì)列時(shí)發(fā)生搶占。進(jìn)程3在進(jìn)程2執(zhí)行1毫秒后到來，但是進(jìn)程3的
執(zhí)行時(shí)間比進(jìn)程2長(zhǎng)。同理進(jìn)程4的到來也沒法搶占進(jìn)程2，所以進(jìn)程2可以一直執(zhí)行到結(jié)束。之后是執(zhí)行時(shí)間第二短的進(jìn)程4
執(zhí)行，最后是進(jìn)程1（要看剩余執(zhí)行時(shí)間腺占，還剩7毫秒）和進(jìn)程3嚎研。
SJF調(diào)度是最優(yōu)的調(diào)度教翩，但難點(diǎn)在于如何預(yù)測(cè)進(jìn)程的執(zhí)行時(shí)間(Burst Time)杆勇。對(duì)于批處理系統(tǒng)中的長(zhǎng)期調(diào)度來說饱亿，可以將用戶
提交進(jìn)程時(shí)輸入的執(zhí)行時(shí)間上限作為依據(jù)。但對(duì)于短期調(diào)度來說配猫，沒有辦法能夠提前得知下一個(gè)要被分配CPU的進(jìn)程的執(zhí)行
時(shí)間長(zhǎng)短。我們只能通過歷史數(shù)據(jù)來進(jìn)行預(yù)測(cè)胃惜，公式如下：
α可以取0.5，公式前半部分表示最近一次Burst Time蛹疯，而后半部分表示過去歷史平均的Burst Time饮寞。
該算法雖可獲得較好的調(diào)度性能孝扛，但難以準(zhǔn)確地知道下一個(gè)CPU執(zhí)行期，而只能根據(jù)每一個(gè)進(jìn)程的執(zhí)行歷史來預(yù)測(cè)幽崩。
4苦始、輪轉(zhuǎn)法 (Round-Robin Scheduling) (RR)
前幾種算法主要用于批處理系統(tǒng)中，不能作為分時(shí)系統(tǒng)中的主調(diào)度算法慌申，在分時(shí)系統(tǒng)中陌选，都采用時(shí)間片輪轉(zhuǎn)法。
簡(jiǎn)單輪轉(zhuǎn)法：系統(tǒng)將所有就緒進(jìn)程按FIFO規(guī)則排隊(duì)蹄溉，按一定的時(shí)間間隔把處理機(jī)分配給隊(duì)列中的進(jìn)程咨油。這樣，就緒
隊(duì)列中所有進(jìn)程均可獲得一個(gè)時(shí)間片的處理機(jī)而運(yùn)行柒爵。多級(jí)隊(duì)列方法：將系統(tǒng)中所有進(jìn)程分成若干類役电，每類為一級(jí)。
RR調(diào)度算法轉(zhuǎn)為分時(shí)系統(tǒng)設(shè)計(jì)棉胀，它與FCFS很像法瑟，但是加入了搶占。具體調(diào)度過程是：內(nèi)核從Ready隊(duì)列中選取第一個(gè)進(jìn)程唁奢，
將CPU資源分配給它霎挟，并且設(shè)置一個(gè)定時(shí)器在一個(gè)時(shí)間片后中斷該進(jìn)程，調(diào)度Ready隊(duì)列中的下一進(jìn)程麻掸。很明顯酥夭，RR調(diào)度
算法是搶占式的，并且在該算法的調(diào)度下论笔，沒有一個(gè)進(jìn)程能夠連續(xù)占用CPU超過一個(gè)時(shí)間片，從而達(dá)到了分時(shí)的目的千所。
來看下面的例子狂魔，假設(shè)一個(gè)時(shí)間片的長(zhǎng)度為4毫秒：
5、高響應(yīng)比優(yōu)先調(diào)度算法
(1) 如果作業(yè)的等待時(shí)間相同,則要求服務(wù)的時(shí)間愈短,其優(yōu)先權(quán)愈高,因而該算法有利于短作業(yè).
(2) 當(dāng)要求服務(wù)的時(shí)間相同時(shí),作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間,等待時(shí)間愈長(zhǎng),其優(yōu)先權(quán)愈高,因而它實(shí)現(xiàn)的是先來先服務(wù).
(3) 對(duì)于長(zhǎng)作業(yè),作業(yè)的優(yōu)先級(jí)可以隨等待時(shí)間的增加而提高,當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí),其優(yōu)先級(jí)便可升到很高, 從而也可獲得處理機(jī).
該算法照顧了短作業(yè),且不會(huì)使長(zhǎng)作業(yè)長(zhǎng)期得不到服務(wù)
6淫痰、搶占式調(diào)度算法
- 非搶占式調(diào)度算法
為每一個(gè)被控對(duì)象建立一個(gè)實(shí)時(shí)任務(wù)并將它們排列成一輪轉(zhuǎn)隊(duì)列,調(diào)度程序每次選擇隊(duì)列中的第一個(gè)任務(wù)投入運(yùn)行.該任務(wù)完成后便把它掛在輪轉(zhuǎn)隊(duì)列的隊(duì)尾等待下次調(diào)度運(yùn)行. - 非搶占式優(yōu)先調(diào)度算法.
實(shí)時(shí)任務(wù)到達(dá)時(shí),把他們安排在就緒隊(duì)列的對(duì)首,等待當(dāng)前任務(wù)自我終止或運(yùn)行完成后才能被調(diào)度執(zhí)行. - 搶占式調(diào)度算法
1）基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法.
實(shí)時(shí)任務(wù)到達(dá)后,如果該任務(wù)的優(yōu)先級(jí)別高于當(dāng)前任務(wù)的優(yōu)先級(jí)并不立即搶占當(dāng)前任務(wù)的處理機(jī),而是等到時(shí)鐘中斷到來時(shí),調(diào)度程序才剝奪當(dāng)前任務(wù)的執(zhí)行,將處理機(jī)分配給新到的高優(yōu)先權(quán)任務(wù).
2）立即搶占的優(yōu)先權(quán)調(diào)度算法.
在這種調(diào)度策略中,要求操作系統(tǒng)具有快速響應(yīng)外部時(shí)間中斷的能力.一旦出現(xiàn)外部中斷,只要當(dāng)前任務(wù)未處于臨界區(qū)便立即剝奪當(dāng)前任務(wù)的執(zhí)行,把處理機(jī)分配給請(qǐng)求中斷的緊迫任務(wù)最楷，實(shí)時(shí)進(jìn)程調(diào)度，實(shí)時(shí)進(jìn)程搶占當(dāng)前待错。
