在多進(jìn)程、多線程并發(fā)的環(huán)境里，從概念上看，有多個(gè)進(jìn)程或者多個(gè)線程在同時(shí)執(zhí)行，具體到單個(gè)CPU級(jí)別，實(shí)際上任何時(shí)刻只能有一個(gè)進(jìn)程或者線程處于執(zhí)行狀態(tài)；因此OS需要決定哪個(gè)進(jìn)程執(zhí)行，哪些進(jìn)程等待，也就是進(jìn)程的調(diào)度。
一、調(diào)度的目標(biāo)
1、首先要區(qū)分程序使用CPU的三種模式：IO密集型、計(jì)算密集型和平衡型。對(duì)于IO密集型程序來(lái)說(shuō)，響應(yīng)時(shí)間非常重要；對(duì)于CPU密集型來(lái)說(shuō)，CPU的周轉(zhuǎn)時(shí)間就比較重要；對(duì)于平衡型程序來(lái)說(shuō)，響應(yīng)和周轉(zhuǎn)之間的平衡是最重要的。
2、CPU的調(diào)度就是要達(dá)到極小化平均響應(yīng)時(shí)間、極大化系統(tǒng)吞吐率、保持系統(tǒng)各個(gè)功能部件均處于繁忙狀態(tài)和提供某種公平的機(jī)制。
3、對(duì)于實(shí)時(shí)系統(tǒng)來(lái)說(shuō)，調(diào)度的目標(biāo)就是要達(dá)到截止時(shí)間前完成所應(yīng)該完成的任務(wù)和提供性能的可預(yù)測(cè)性。
二、調(diào)度算法
1、FCFS（First come first serve)，或者稱為FIFO算法，先來(lái)先處理。這個(gè)算法的優(yōu)點(diǎn)是簡(jiǎn)單，實(shí)現(xiàn)容易，并且似乎公平；缺點(diǎn)在于短的任務(wù)有可能變的非常慢，因?yàn)槠淝懊娴娜蝿?wù)占用很長(zhǎng)時(shí)間，造成了平均響應(yīng)時(shí)間非常慢。
2、時(shí)間片輪詢算法，這是對(duì)FIFO算法的改進(jìn)，目的是改善短程序（運(yùn)行時(shí)間短）的響應(yīng)時(shí)間，其方法就是周期性地進(jìn)行進(jìn)程切換。這個(gè)算法的關(guān)鍵點(diǎn)在于時(shí)間片的選擇，時(shí)間片過(guò)大，那么輪轉(zhuǎn)就越接近FIFO，如果太小，進(jìn)程切換的開銷大于執(zhí)行程序的開銷，從而降低了系統(tǒng)效率。因此選擇合適的時(shí)間片就非常重要。選擇時(shí)間片的兩個(gè)需要考慮的因素：一次進(jìn)程切換所使用的系統(tǒng)消耗以及我們能接受的整個(gè)系統(tǒng)消耗、系統(tǒng)運(yùn)行的進(jìn)程數(shù)。
時(shí)間片輪詢看上起非常公平，并且響應(yīng)時(shí)間非常好，然而時(shí)間片輪轉(zhuǎn)并不能保證系統(tǒng)的響應(yīng)時(shí)間總是比FIFO短，這很大程度上取決于時(shí)間片大小的選擇，以及這個(gè)大小與進(jìn)程運(yùn)行時(shí)間的相互關(guān)系。
3、STCF算法（Short time to complete first)，顧名思義就是短任務(wù)優(yōu)先算法。這種算法的核心就是所有的程序都有一個(gè)優(yōu)先級(jí)，短任務(wù)的優(yōu)先級(jí)比長(zhǎng)任務(wù)的高，而OS總是安排優(yōu)先級(jí)高的進(jìn)程運(yùn)行。
STCF又分為兩類：非搶占式和搶占式。非搶占式STCF就是讓已經(jīng)在CPU上運(yùn)行的程序執(zhí)行到結(jié)束或者阻塞，然后在所有的就緒進(jìn)程中選擇執(zhí)行時(shí)間最短的來(lái)執(zhí)行；而搶占式STCF就不是這樣，在每進(jìn)來(lái)一個(gè)新的進(jìn)程時(shí)，就對(duì)所有進(jìn)程（包括正在CPU上執(zhí)行的進(jìn)程）進(jìn)行檢查，誰(shuí)的執(zhí)行時(shí)間短，就運(yùn)行誰(shuí)。
STCF總是能提供最優(yōu)的響應(yīng)時(shí)間，然而它也有缺點(diǎn)，第一可能造成長(zhǎng)任務(wù)的程序無(wú)法得到CPU時(shí)間而饑餓，因?yàn)镺S總是優(yōu)先執(zhí)行短任務(wù)；其次，關(guān)鍵問(wèn)題在于我們?cè)趺粗莱绦虻倪\(yùn)行時(shí)間，怎么預(yù)測(cè)某個(gè)進(jìn)程需要的執(zhí)行時(shí)間？通常有兩個(gè)辦法：使用啟發(fā)式方法估算（例如根據(jù)程序大小估算），或者將程序執(zhí)行一遍后記錄其所用的CPU時(shí)間，在以后的執(zhí)行過(guò)程中就可以根據(jù)這個(gè)測(cè)量數(shù)據(jù)來(lái)進(jìn)行STCF調(diào)度。
4、優(yōu)先級(jí)調(diào)度，STCF遇到的問(wèn)題是長(zhǎng)任務(wù)的程序可能饑餓，那么優(yōu)先級(jí)調(diào)度算法可以通過(guò)給長(zhǎng)任務(wù)的進(jìn)程更高的優(yōu)先級(jí)來(lái)解決這個(gè)問(wèn)題；優(yōu)先級(jí)調(diào)度遇到的問(wèn)題可能是短任務(wù)的進(jìn)程饑餓，這個(gè)可以通過(guò)動(dòng)態(tài)調(diào)整優(yōu)先級(jí)來(lái)解決。實(shí)際上動(dòng)態(tài)調(diào)整優(yōu)先級(jí)（稱為權(quán)值）+時(shí)間片輪詢的策略正是linux的進(jìn)程調(diào)度策略之一的 SCHED_OTHER分時(shí)調(diào)度策略,它的調(diào)度過(guò)程如下：
（1）創(chuàng)建任務(wù)指定采用分時(shí)調(diào)度策略，并指定優(yōu)先級(jí)nice值(-20~19)。
（2）將根據(jù)每個(gè)任務(wù)的nice值確定在cpu上的執(zhí)行時(shí)間(counter)。
（3）如果沒(méi)有等待資源，則將該任務(wù)加入到就緒隊(duì)列中。
（4）調(diào)度程序遍歷就緒隊(duì)列中的任務(wù)，通過(guò)對(duì)每個(gè)任務(wù)動(dòng)態(tài)優(yōu)先級(jí)的計(jì)算(counter+20-nice)結(jié)果，選擇計(jì)算結(jié)果最大的一個(gè)去運(yùn)行，當(dāng)這個(gè)時(shí)間片用完后(counter減至0)或者主動(dòng)放棄cpu時(shí)，該任務(wù)將被放在就緒隊(duì)列末尾(時(shí)間片用完)或等待隊(duì)列(因等待資源而放棄cpu)中。
（5）此時(shí)調(diào)度程序重復(fù)上面計(jì)算過(guò)程，轉(zhuǎn)到第4步。
（6）當(dāng)調(diào)度程序發(fā)現(xiàn)所有就緒任務(wù)計(jì)算所得的權(quán)值都為不大于0時(shí)，重復(fù)第2步。
linux還有兩個(gè)實(shí)時(shí)進(jìn)程的調(diào)度策略：FIFO和RR,實(shí)時(shí)進(jìn)程會(huì)立即搶占非實(shí)時(shí)進(jìn)程。
5、顯然，沒(méi)有什么調(diào)度算法是毫無(wú)缺點(diǎn)的，因此現(xiàn)代OS通常都會(huì)采用混合調(diào)度算法。例如將不同的進(jìn)程分為幾個(gè)大類，每個(gè)大類有不同的優(yōu)先級(jí)，不同大類的進(jìn)程的調(diào)度取決于大類的優(yōu)先級(jí)，同一個(gè)大類的進(jìn)程采用時(shí)間片輪詢來(lái)保證公平性。
6、其他調(diào)度算法，保證調(diào)度算法保證每個(gè)進(jìn)程享用的CPU時(shí)間完全一樣；彩票調(diào)度算法是一種概率調(diào)度算法，通過(guò)給進(jìn)程“發(fā)彩票”的多少，來(lái)賦予不同進(jìn)程不同的調(diào)用時(shí)間，彩票調(diào)度算法的優(yōu)點(diǎn)是非常靈活，如果你給短任務(wù)發(fā)更多“彩票”，那么就類似STCF調(diào)度，如果給每個(gè)進(jìn)程一樣多的“彩票”，那么就類似保證調(diào)度；用戶公平調(diào)度算法，是按照每個(gè)用戶，而不是按照每個(gè)進(jìn)程來(lái)進(jìn)行公平分配CPU時(shí)間，這是為了防止貪婪用戶啟用了過(guò)多進(jìn)程導(dǎo)致系統(tǒng)效率降低甚至停頓。
7、實(shí)時(shí)系統(tǒng)的調(diào)度算法，實(shí)時(shí)系統(tǒng)需要考慮每個(gè)具體任務(wù)的響應(yīng)時(shí)間必須符合要求，在截止時(shí)間前完成。
（1）EDF調(diào)度算法，就是最早截止任務(wù)優(yōu)先（Earliest deadline first)算法，也就是讓最早截止的任務(wù)先做。當(dāng)新的任務(wù)過(guò)來(lái)時(shí)，如果它的截止時(shí)間更靠前，那么就讓新任務(wù)搶占正在執(zhí)行的任務(wù)。EDF算法其實(shí)是貪心算法的一種體現(xiàn)。如果一組任務(wù)可以被調(diào)度（也就是所有任務(wù)的截止時(shí)間在理論上都可以得到滿足），那么EDF可以滿足。如果一批任務(wù)不能全部滿足（全部在各自的截止時(shí)間前完成），那EDF滿足的任務(wù)數(shù)最多，這就是它最優(yōu)的體現(xiàn)。EDF其實(shí)就是搶占式的STCF，只不過(guò)將程序的執(zhí)行時(shí)間換成了截止時(shí)間。EDF的缺點(diǎn)在于需要對(duì)每個(gè)任務(wù)的截止時(shí)間做計(jì)算并動(dòng)態(tài)調(diào)整優(yōu)先級(jí)，并且搶占任務(wù)也需要消耗系統(tǒng)資源。因此它的實(shí)際效果比理論效果差一點(diǎn)。
（2）RMS調(diào)度算法，EDF是動(dòng)態(tài)調(diào)度算法，而RMS（rate monotonic scheduling)算法是一種靜態(tài)最優(yōu)算法；該算法在進(jìn)行調(diào)度前先計(jì)算出所有任務(wù)的優(yōu)先級(jí)，然后按照計(jì)算出來(lái)的優(yōu)先級(jí)進(jìn)行調(diào)度，任務(wù)執(zhí)行中間既不接收新任務(wù)，也不進(jìn)行優(yōu)先級(jí)調(diào)整或者CPU搶占。因此它的優(yōu)點(diǎn)是系統(tǒng)消耗小，缺點(diǎn)就是不靈活了。對(duì)于RMS算法，關(guān)鍵點(diǎn)在于判斷一個(gè)任務(wù)組是否能被調(diào)度，這里有一個(gè)定律，如果一個(gè)系統(tǒng)的所有任務(wù)的CPU利用率都低于ln2，那么這些任務(wù)的截止時(shí)間均可以得到滿足，ln2約等于0.693147，也就是此時(shí)系統(tǒng)還剩下有30%的CPU時(shí)間。這個(gè)證明是Liu和Kayland在1973年給出的。
三、優(yōu)先級(jí)反轉(zhuǎn)
1、什么是優(yōu)先級(jí)反轉(zhuǎn)？
優(yōu)先級(jí)反轉(zhuǎn)是指一個(gè)低優(yōu)先級(jí)的任務(wù)持有一個(gè)被高優(yōu)先級(jí)任務(wù)所需要的共享資源。高優(yōu)先任務(wù)由于因資源缺乏而處于受阻狀態(tài)，一直等到低優(yōu)先級(jí)任務(wù)釋放資源為止。而低優(yōu)先級(jí)獲得的CPU時(shí)間少，如果此時(shí)有優(yōu)先級(jí)處于兩者之間的任務(wù)，并且不需要那個(gè)共享資源，則該中優(yōu)先級(jí)的任務(wù)反而超過(guò)這兩個(gè)任務(wù)而獲得CPU時(shí)間。如果高優(yōu)先級(jí)等待資源時(shí)不是阻塞等待，而是忙循環(huán)，則可能永遠(yuǎn)無(wú)法獲得資源，因?yàn)榇藭r(shí)低優(yōu)先級(jí)進(jìn)程無(wú)法與高優(yōu)先級(jí)進(jìn)程爭(zhēng)奪CPU時(shí)間，從而無(wú)法執(zhí)行，進(jìn)而無(wú)法釋放資源，造成的后果就是高優(yōu)先級(jí)任務(wù)無(wú)法獲得資源而繼續(xù)推進(jìn)。
2、解決方案：
（1）設(shè)置優(yōu)先級(jí)上限，給臨界區(qū)一個(gè)高優(yōu)先級(jí)，進(jìn)入臨界區(qū)的進(jìn)程都將獲得這個(gè)高優(yōu)先級(jí)，如果其他試圖進(jìn)入臨界區(qū)的進(jìn)程的優(yōu)先級(jí)都低于這個(gè)高優(yōu)先級(jí)，那么優(yōu)先級(jí)反轉(zhuǎn)就不會(huì)發(fā)生。
（2）優(yōu)先級(jí)繼承，當(dāng)一個(gè)高優(yōu)先級(jí)進(jìn)程等待一個(gè)低優(yōu)先級(jí)進(jìn)程持有的資源時(shí)，低優(yōu)先級(jí)進(jìn)程將暫時(shí)獲得高優(yōu)先級(jí)進(jìn)程的優(yōu)先級(jí)別，在釋放共享資源后，低優(yōu)先級(jí)進(jìn)程回到原來(lái)的優(yōu)先級(jí)別。嵌入式系統(tǒng)VxWorks就是采用這種策略。
這里還有一個(gè)八卦，1997年的美國(guó)的火星探測(cè)器（使用的就是vxworks)就遇到一個(gè)優(yōu)先級(jí)反轉(zhuǎn)問(wèn)題引起的故障。簡(jiǎn)單說(shuō)下，火星探測(cè)器有一個(gè)信息總線，有一個(gè)高優(yōu)先級(jí)的總線任務(wù)負(fù)責(zé)總線數(shù)據(jù)的存取，訪問(wèn)總線都需要通過(guò)一個(gè)互斥鎖（共享資源出現(xiàn)了）；還有一個(gè)低優(yōu)先級(jí)的，運(yùn)行不是很頻繁的氣象搜集任務(wù)，它需要對(duì)總線寫數(shù)據(jù)，也就同樣需要訪問(wèn)互斥鎖；最后還有一個(gè)中優(yōu)先級(jí)的通信任務(wù)，它的運(yùn)行時(shí)間比較長(zhǎng)。平常這個(gè)系統(tǒng)運(yùn)行毫無(wú)問(wèn)題，但是有一天，在氣象任務(wù)獲得互斥鎖往總線寫數(shù)據(jù)的時(shí)候，一個(gè)中斷發(fā)生導(dǎo)致通信任務(wù)被調(diào)度就緒，通信任務(wù)搶占了低優(yōu)先級(jí)的氣象任務(wù)，而無(wú)巧不成書的是，此時(shí)高優(yōu)先級(jí)的總線任務(wù)正在等待氣象任務(wù)寫完數(shù)據(jù)歸還互斥鎖，但是由于通信任務(wù)搶占了CPU并且運(yùn)行時(shí)間比較長(zhǎng)，導(dǎo)致氣象任務(wù)得不到CPU時(shí)間也無(wú)法釋放互斥鎖，本來(lái)是高優(yōu)先級(jí)的總線任務(wù)也無(wú)法執(zhí)行，總線任務(wù)無(wú)法及時(shí)執(zhí)行的后果被探路者認(rèn)為是一個(gè)嚴(yán)重錯(cuò)誤，最后就是整個(gè)系統(tǒng)被重啟。Vxworks允許優(yōu)先級(jí)繼承，然而遺憾的工程師們將這個(gè)選項(xiàng)關(guān)閉了。
（3）第三種方法就是使用中斷禁止，通過(guò)禁止中斷來(lái)保護(hù)臨界區(qū)，采用此種策略的系統(tǒng)只有兩種優(yōu)先級(jí)：可搶占優(yōu)先級(jí)和中斷禁止優(yōu)先級(jí)。前者為一般進(jìn)程運(yùn)行時(shí)的優(yōu)先級(jí)，后者為運(yùn)行于臨界區(qū)的優(yōu)先級(jí)?；鹦翘铰氛哒怯捎谠谂R界區(qū)中運(yùn)行的氣象任務(wù)被中斷發(fā)生的通信任務(wù)所搶占才導(dǎo)致故障，如果有臨界區(qū)的禁止中斷保護(hù)，此一問(wèn)題也不會(huì)發(fā)生。