CPU調(diào)度（CPU scheduling）
調(diào)度是什么？
在計(jì)算機(jī)中，調(diào)度是分配完成一個(gè)工作所需資源的方法。工作可指諸如線程threads、進(jìn)程processes或者數(shù)據(jù)流data flows這樣的虛擬計(jì)算元素，這些虛擬計(jì)算元素將會(huì)被調(diào)度按照一定順序(in turn)分配到諸如處理器processors，又稱CPU、網(wǎng)絡(luò)鏈路network links或者擴(kuò)展卡expansion cards這樣的硬件資源上。
調(diào)度器scheduler就是執(zhí)行調(diào)度工作的程序。調(diào)度器使得整個(gè)計(jì)算機(jī)系統(tǒng)的資源處于忙碌狀態(tài)（又叫負(fù)載均衡load balancing），允許多用戶有效地共享系統(tǒng)資源，或者達(dá)到指定的服務(wù)質(zhì)量。調(diào)度器使得在單處理器（a single central processing unit,CPU）上通過多任務(wù)處理，從而讓其執(zhí)行多個(gè)進(jìn)程成為可能。
一個(gè)調(diào)度器根據(jù)目的不同而有多種不同的設(shè)計(jì)，如：吞吐量最大化、響應(yīng)時(shí)間(response time)和等待時(shí)間(wait time)最小化、最低延遲等等。而實(shí)踐中，這些目的往往是互相沖突的，因此調(diào)度器會(huì)曹勇一個(gè)權(quán)衡利弊的折中方案進(jìn)行設(shè)計(jì)，其側(cè)重點(diǎn)取決于用戶需求。
操作系統(tǒng)中調(diào)度器的種類
調(diào)度器是操作系統(tǒng)的一個(gè)模塊，能夠選擇將被CPU處理的下一個(gè)作業(yè)或者說下一個(gè)進(jìn)程。操作系統(tǒng)提供三種調(diào)度器：長期調(diào)度器（long-term scheduler）、中期調(diào)度器（medium-term scheduler）、短期調(diào)度器（short-term scheduler），其名稱中的“長、中、短”顯示執(zhí)行其功能的相對頻率。
進(jìn)程調(diào)度器 Process scheduler
是操作系統(tǒng)的一部分，決定了某個(gè)進(jìn)程何時(shí)被CPU執(zhí)行。通常它能暫停一個(gè)正在運(yùn)行的進(jìn)程，并將這個(gè)進(jìn)程轉(zhuǎn)到運(yùn)行隊(duì)列running queue中，轉(zhuǎn)而開始執(zhí)行另一個(gè)進(jìn)程，這樣的調(diào)度器稱為“搶占式調(diào)度器”，否則就是“協(xié)同調(diào)度器”。
-
長期調(diào)度器long-term scheduler：
又叫“準(zhǔn)入調(diào)度器（admission schedular）”、“作業(yè)調(diào)度器”或者“高級(jí)調(diào)度器”，決定了任務(wù)或進(jìn)程是否被允許載入就緒隊(duì)列(ready queue)中（即主存內(nèi)）。換句話說，這種調(diào)度將已進(jìn)入系統(tǒng)并處于后背狀態(tài)的作業(yè)按某種算法選擇一個(gè)或一批，為其建立進(jìn)程，并進(jìn)入主機(jī)，當(dāng)該作業(yè)執(zhí)行完畢時(shí)，還負(fù)責(zé)回收系統(tǒng)資源【注：正在執(zhí)行的程序即進(jìn)程】。因此，這類調(diào)度器掌控著能在系統(tǒng)上運(yùn)行的程序、決定并發(fā)的程度（是否要同時(shí)執(zhí)行多個(gè)或少數(shù)進(jìn)程，以及如何分配I/O密集型和CPU密集型進(jìn)程）。
通常，大多數(shù)程序可以歸為I/O密集型和CPU密集型。I/O密集型程序?qū)⒋蠖鄶?shù)時(shí)間花在了I/O操作而不是運(yùn)算上，而CPU密集型程序正好相反，它將大多數(shù)時(shí)間花在了運(yùn)算上，而很少產(chǎn)生I/O操作。如何組合這兩種類型的程序?qū)τ陂L期調(diào)度器來說非常重要：如果全是I/O密集型程序，那么就緒隊(duì)列幾乎一直都是空的使得調(diào)度器無所事事；另一方面，若全是CPU密集型程序，會(huì)導(dǎo)致I/O等待隊(duì)列處于空隊(duì)狀態(tài)，使得一些設(shè)備沒人用，這樣一來系統(tǒng)資源分配就不均衡。 -
中期調(diào)度器Medium-term scheduler：
又稱為“交換調(diào)度器”或者“中級(jí)調(diào)度器”，主要負(fù)責(zé)暫時(shí)將主存中的進(jìn)程轉(zhuǎn)移到二級(jí)存儲(chǔ)設(shè)備（比如說硬盤），我們通常把這種行為稱為“交換swapping”。
詳細(xì)說，它將進(jìn)程從主存或CPU競爭中移出來，從而降低多道程序設(shè)計(jì)的麻煩程度，這些被移出來的進(jìn)程后面能被再次載入主存，并從中斷的地方繼續(xù)執(zhí)行，看得出來，這樣的操作可以隨時(shí)調(diào)整進(jìn)程在主存中的存在數(shù)量和時(shí)機(jī)。
從狀態(tài)上說，中級(jí)調(diào)度就是按照給定的原則和策略，將處于外存交換區(qū)中就緒狀態(tài)或等待狀態(tài)的進(jìn)程調(diào)入主存，或把處于主存就緒狀態(tài)或主存等待狀態(tài)的進(jìn)程交換到外存交換區(qū)。
從狀態(tài)上看三級(jí)調(diào)度
那究竟什么時(shí)候中期調(diào)度器工作呢？
比如主存中某個(gè)進(jìn)程不咋活躍或者其優(yōu)先級(jí)低（后面在二級(jí)存儲(chǔ)設(shè)備中存在某個(gè)程序亟待運(yùn)行），又或者是那些總是產(chǎn)生錯(cuò)誤，發(fā)出Error的家伙，還或者是某個(gè)進(jìn)程占用了大量的主存空間，這時(shí)中期調(diào)度器就會(huì)把他們放入交換區(qū)，以便騰出一些主存空間給其他需求更為迫切的進(jìn)程使用。而當(dāng)系統(tǒng)主存空間充足的時(shí)候，亦或者某個(gè)進(jìn)程不在阻塞隊(duì)列（即這個(gè)進(jìn)程所需要的資源都已經(jīng)準(zhǔn)備好）中時(shí)，中期調(diào)度器又會(huì)將剛剛放入交換區(qū)中的進(jìn)程重新載入主存（進(jìn)入運(yùn)行隊(duì)列）中。
現(xiàn)在的許多系統(tǒng)支持將虛擬地址空間映射到二級(jí)存儲(chǔ)設(shè)備中而不是交換區(qū)，中期調(diào)度器便可以通過將二進(jìn)制文件視為“交換出去的進(jìn)程swapped out processes”來扮演長期調(diào)度器的角色。這樣，當(dāng)需要二進(jìn)制文件的一部分時(shí)，可以按需交換（又稱“懶散加載lazy loaded”）。 -
短期調(diào)度器Short-term scheduler：
常常又被稱為“CPU 調(diào)度器”、“進(jìn)程調(diào)度器”、“微觀調(diào)度器”或者“低級(jí)調(diào)度器”（我們通常說得調(diào)度就是指這個(gè)），決定了在一個(gè)時(shí)鐘中斷、I/O中斷、系統(tǒng)調(diào)用其他種類信號(hào)之后，哪一個(gè)正處于就緒隊(duì)列中且在主存中的進(jìn)程能被CPU執(zhí)行（將CPU控制權(quán)交給這個(gè)進(jìn)程）。因此，短期調(diào)度器做出決定的頻率比前兩種調(diào)度器更加頻繁——每隔一段非常短的時(shí)間片都得做出一次決定。這種調(diào)度器可以是搶占式的，即能夠強(qiáng)行把一個(gè)正在CPU中執(zhí)行的進(jìn)程拽出（中斷），然后把CPU分配給其他進(jìn)程；也可以是非搶占式的。
搶占式調(diào)度器需要一個(gè)處于內(nèi)核態(tài)kernel mode、能被中斷處理程序捕獲的可編程間隔定時(shí)器才能實(shí)現(xiàn)。
-
分派程序Dispatcher：
與CPU調(diào)度功能相關(guān)的另一個(gè)部分是分派程序。分派程序是一個(gè)模塊，用來把CPU的控制權(quán)交給由短期調(diào)度器選出來的進(jìn)程。它通常具有下面的功能：
1）上下文切換context switches，當(dāng)短期調(diào)度器選出一個(gè)新進(jìn)程時(shí)，分派程序就立馬保存現(xiàn)場（即當(dāng)前正在被CPU執(zhí)行的進(jìn)程/線程的狀態(tài)），接著馬不停蹄地對被選中的新進(jìn)程進(jìn)行初始化或者加載這個(gè)新進(jìn)程原先被保存的狀態(tài)。
2）從內(nèi)核模式切換到用戶模式。
3）跳轉(zhuǎn)到用戶程序的合適位置，以便重新啟動(dòng)程序。
分派程序應(yīng)該盡可能快，因?yàn)樵诿看芜M(jìn)程切換時(shí)都會(huì)使用它。其實(shí)在進(jìn)程切換期間，CPU實(shí)際上空閑了一段時(shí)間，為了提高CPU利用率，應(yīng)該避免不必要的上下文切換。這段時(shí)間又被叫做“分派延遲dispatch latency”。
