調(diào)度程序沒有太復(fù)雜的原理。大限度地利用處理器時(shí)間的原則是，只要有可執(zhí)行進(jìn)程，那么就總會(huì)有進(jìn)程執(zhí)行。但是只要系統(tǒng)中可運(yùn)行的進(jìn)程數(shù)目比處理器個(gè)數(shù)多，就注定某一給定時(shí)刻會(huì)有一些進(jìn)程不能執(zhí)行。
4.1 多任務(wù)
linux提供了搶占式的多任務(wù)處理模式，由調(diào)度程序來決定什么時(shí)候停止一個(gè)進(jìn)程的運(yùn)行，以便其他進(jìn)程能夠得到執(zhí)行的機(jī)會(huì)。這個(gè)強(qiáng)制的掛起動(dòng)作就叫做搶占。進(jìn)程在被搶占之前能夠運(yùn)行的時(shí)間都是預(yù)先設(shè)置好的，叫進(jìn)程的時(shí)間片。
在非搶占模式下，除非進(jìn)程自己主動(dòng)停止運(yùn)行，否則他會(huì)一直執(zhí)行。
4.2 linux的進(jìn)程調(diào)度
4.3 策略
4.3.1 I/O消耗型和處理器消耗型的進(jìn)程。
進(jìn)程可以被分為I/O消耗型和處理器消耗型。前者指進(jìn)程的大部分時(shí)間用來提交I/O請(qǐng)求或是等待I/O請(qǐng)求。因此這樣的進(jìn)程經(jīng)常處于可運(yùn)行狀態(tài)，但通常都是運(yùn)行短短一會(huì)兒，因?yàn)樗诘却嗟腎/O請(qǐng)求時(shí)總會(huì)阻塞。相反處理器耗費(fèi)型進(jìn)程把時(shí)間大多用在執(zhí)行代碼上。除非被搶占，否則他們通常都是一致不停的運(yùn)行。對(duì)于這類進(jìn)程，調(diào)度策略往往是盡量降低他們的調(diào)度頻率，而延長其運(yùn)行時(shí)間。
4.3.2 優(yōu)先級(jí)進(jìn)程
調(diào)度算法中最基本的一類就是基于優(yōu)先級(jí)的調(diào)度。通常的做法是優(yōu)先級(jí)高的進(jìn)程先運(yùn)行，低的后運(yùn)行，優(yōu)先級(jí)高的進(jìn)程使用的時(shí)間片也較長。調(diào)度程序總是選擇時(shí)間片未用盡而且優(yōu)先級(jí)高的進(jìn)程運(yùn)行。用戶和系統(tǒng)都可以通過設(shè)置進(jìn)程的優(yōu)先級(jí)來影響系統(tǒng)的調(diào)度。
linux采用兩種不同的優(yōu)先級(jí)范圍1、nice值，越低優(yōu)先級(jí)越高；第二種是實(shí)時(shí)優(yōu)先級(jí)，其值可配置，默認(rèn)情況下變化從0——99.越大優(yōu)先級(jí)也越高。任何實(shí)時(shí)進(jìn)程優(yōu)先級(jí)都高于普通進(jìn)程。實(shí)時(shí)優(yōu)先級(jí)和nice值處于互不相交的兩個(gè)范疇。
4.3.3 時(shí)間片
時(shí)間片是一個(gè)數(shù)值，它表明進(jìn)程在被搶占前能持續(xù)運(yùn)行的時(shí)間。調(diào)度策略必須規(guī)定一個(gè)默認(rèn)的時(shí)間片：時(shí)間片過長——交互相應(yīng)不佳；過短——明顯增大進(jìn)程切換帶來的處理器耗時(shí)，進(jìn)程運(yùn)行的時(shí)間片過短。I/O消耗型不需要很長的時(shí)間片，處理器消耗型希望時(shí)間片越長越好。
Linux中使用新的CFS調(diào)度器，其搶占時(shí)機(jī)取決于新的可運(yùn)行程序消耗了多少處理器使用比。如果消耗的使用比比當(dāng)前進(jìn)程小，則新進(jìn)程立刻投入運(yùn)行，搶占當(dāng)前進(jìn)程。否則將推遲其運(yùn)行。
4.3.4 調(diào)度策略的活動(dòng)
以文本編輯器和視頻解碼器來舉例。對(duì)文本編輯器而言，第一我們希望系統(tǒng)給它更多的處理器時(shí)間，這并非因?yàn)樗枰嗟奶幚砥鲿r(shí)間，而是因?yàn)槲覀兿Ｍ茉谖覀冃枰臅r(shí)候總是能立刻等到處理器資源，響應(yīng)我們的要求搶占視頻解碼器。這樣才能保證文本編輯器具有很好的交互性能，響應(yīng)用戶輸入。
一旦文本編輯器被喚醒，CFS注意到給它的處理器使用比是50%，但是其實(shí)它用了很少。特別是，CFS發(fā)現(xiàn)文本編輯器比視頻解碼器用的少很多。這種情況下為了讓所有進(jìn)程公平分享處理器，它會(huì)立刻搶占視頻解碼程序讓文本編輯器立刻投入運(yùn)行。文本編輯器運(yùn)行后，立即處理了用戶的點(diǎn)擊輸入后，又一次進(jìn)入睡眠等待用戶的下一次輸入。因?yàn)槲谋揪庉嬈鞑]有消費(fèi)掉承諾的50%的處理器使用比，因此情況依舊，CFS總是會(huì)毫不猶豫的讓文本編輯器在需要時(shí)投入運(yùn)行，而讓視頻處理程序只能在剩下的時(shí)刻運(yùn)行。
4.4 Linux調(diào)度算法
4.4.1 調(diào)度器類
linux調(diào)度器是以模塊的方式提供的，這樣做的目的是允許不同類型的進(jìn)程可以有針對(duì)性的選擇調(diào)度算法。
4.4.2 Unix系統(tǒng)中的進(jìn)程調(diào)度
在Unix系統(tǒng)上，優(yōu)先級(jí)以nice值形式輸出給用戶空間，這會(huì)引起一些問題：
1、若要將nice值映射到時(shí)間片，就必然要將nice單位值對(duì)應(yīng)到處理器的絕對(duì)時(shí)間。但這樣做將導(dǎo)致進(jìn)程切換無法最優(yōu)化進(jìn)行。優(yōu)先級(jí)高時(shí)間片多低則少，無法解決I/O消耗型與處理器消耗型進(jìn)程之間的矛盾。
2、相對(duì)nice值，把進(jìn)程的nice值-1所帶來的效果取決于其nice的初始值。
3、如果執(zhí)行nice值到時(shí)間片的映射，需要分配一個(gè)絕對(duì)的時(shí)間片，這個(gè)要求意味著時(shí)間片必須是定時(shí)節(jié)拍器的整數(shù)倍
4、調(diào)度器為了進(jìn)程能更快的投入運(yùn)行，而去對(duì)新要喚醒的進(jìn)程提升優(yōu)先級(jí)，打破了公平原則，獲得更多的處理器時(shí)間，損害其他進(jìn)程的利益。
4.4.3 公平調(diào)度
進(jìn)程調(diào)度的效果應(yīng)該如同系統(tǒng)具備一個(gè)理想中的完美多任務(wù)處理器。這種系統(tǒng)中，每個(gè)進(jìn)程將能獲得1/n的處理器時(shí)間——n是指可運(yùn)行進(jìn)程的數(shù)量。
CFS的做法是允許每個(gè)進(jìn)程運(yùn)行一段時(shí)間、循環(huán)輪轉(zhuǎn)、選擇運(yùn)行最少的進(jìn)程作為下一個(gè)運(yùn)行進(jìn)程，而不再采用分配每個(gè)進(jìn)程時(shí)間片的做法。
nice值在CFS中被作為進(jìn)程獲取處理器比重的權(quán)重。CFS為完美多任務(wù)中的無限小調(diào)度周期的近似值設(shè)立了一個(gè)目標(biāo)。這個(gè)目標(biāo)稱作：目標(biāo)延遲，越小的調(diào)度周期將帶來越好的交互性，同時(shí)也更接近完美的多任務(wù)。但是你必須承受更高的切換代價(jià)和更差的系統(tǒng)吞吐能力。
CFS引入了每個(gè)進(jìn)程獲得時(shí)間片的底線，這個(gè)底線成為最小粒度。
4.5 Linux調(diào)度的實(shí)現(xiàn)
1、時(shí)間記賬
2、進(jìn)程選擇
3、調(diào)度器入庫
4、睡眠和喚醒
4.5.1 時(shí)間記賬
1、調(diào)度器實(shí)體結(jié)構(gòu) sched_entity 調(diào)度器實(shí)體結(jié)構(gòu)作為名為se的成員變量，嵌入在進(jìn)程描述符struct task_struct內(nèi)。
2、虛擬實(shí)時(shí)
vruntime變量存放進(jìn)程的虛擬運(yùn)行時(shí)間，該運(yùn)行時(shí)間的計(jì)算是經(jīng)過了所有可運(yùn)行進(jìn)程總數(shù)的標(biāo)準(zhǔn)化（或者說是被加權(quán)的）。虛擬時(shí)間是以ns為單位的，所以vruntime與定時(shí)器節(jié)拍不再相關(guān)。
update_curr()是有系統(tǒng)定時(shí)器周期性調(diào)用的，無論在進(jìn)程處于可運(yùn)行狀態(tài)還是被堵塞處于不可運(yùn)行狀態(tài)。vruntime可以準(zhǔn)確的測(cè)量給定進(jìn)程的運(yùn)行時(shí)間。
4.5.2 進(jìn)程選擇
當(dāng)CFS需要選擇下一個(gè)運(yùn)行程序時(shí)，它會(huì)挑一個(gè)具有最小vruntime的進(jìn)程。CFS使用紅黑樹來組織可運(yùn)行進(jìn)程隊(duì)列，并利用其迅速找到最小vruntime值的進(jìn)程。
4.5.3 調(diào)度器入口
進(jìn)程調(diào)度的主要入口點(diǎn)是函數(shù)schedule（）。schedule（）通常都需要和一個(gè)具體的調(diào)度類相關(guān)聯(lián)，它會(huì)找到一個(gè)高優(yōu)先級(jí)的調(diào)度類，然后問后者誰是下一個(gè)該運(yùn)行的進(jìn)程。schedule（）函數(shù)會(huì)調(diào)用pick_next_task()。
4.5.4 睡眠和喚醒
休眠的進(jìn)程處于一個(gè)特殊的不可執(zhí)行的狀態(tài)。如果沒有這種特殊狀態(tài)的話，調(diào)度程序就可能選出一個(gè)本不愿意被執(zhí)行的進(jìn)程，更糟糕的是，休眠就必須以輪詢的方式實(shí)現(xiàn)了。
1、等待隊(duì)列
休眠通過等待隊(duì)列進(jìn)行處理。等待隊(duì)列是由等待某些事件發(fā)生的進(jìn)程組成的簡(jiǎn)單鏈表。內(nèi)核用wake_queue_head_t來代表等待隊(duì)列
2、喚醒
4.6 搶占和上下文切換
上下文切換，也就是從一個(gè)可執(zhí)行進(jìn)程切換到另一個(gè)可執(zhí)行進(jìn)程。由定義在kernel/sched.c中的context_switch()函數(shù)負(fù)責(zé)處理。每當(dāng)一個(gè)新的進(jìn)程被選出來準(zhǔn)備投入運(yùn)行的時(shí)候，schedule（）就會(huì)調(diào)用該函數(shù)。它完成兩項(xiàng)基本工作：
1、調(diào)用asm/mmu_context.h中的switch_mm(),該函數(shù)負(fù)責(zé)把虛擬內(nèi)存從上一個(gè)進(jìn)程映射到新進(jìn)程中。
2、調(diào)用switch_to()，該函數(shù)負(fù)責(zé)從上一個(gè)進(jìn)程的處理器狀態(tài)切換到新進(jìn)程的處理器狀態(tài)。這包括保存、恢復(fù)棧信息和寄存器信息，還有其他任何與體系結(jié)構(gòu)相關(guān)的狀態(tài)信息，都必須以每個(gè)進(jìn)程為對(duì)象進(jìn)行管理和保存。
內(nèi)核必須知道在什么時(shí)候調(diào)用schedule（）函數(shù)。內(nèi)核提供了一個(gè)need_resched標(biāo)志來表明是偶需要重調(diào)度。當(dāng)某個(gè)進(jìn)程被搶占時(shí)，scheduler_tick()就會(huì)設(shè)置這個(gè)標(biāo)志；當(dāng)一個(gè)優(yōu)先級(jí)高的進(jìn)程進(jìn)入可執(zhí)行狀態(tài)時(shí)，try_to_wake_up()也會(huì)設(shè)置這個(gè)標(biāo)志，內(nèi)核檢查該標(biāo)志，調(diào)用schedule（）切換到新進(jìn)程。
用于訪問和操作need_resched的函數(shù)
set_tsk_need_resched();
clear_tsk_need_resched()；
need_resched（）檢查need_resched標(biāo)志，被設(shè)置返回真。
在返回用戶空間以及從中斷返回的時(shí)候，內(nèi)核也會(huì)檢查need_resched標(biāo)志。如果已經(jīng)被設(shè)置，則內(nèi)核會(huì)在繼續(xù)執(zhí)行之前調(diào)用調(diào)度程序。
每個(gè)進(jìn)程都含有一個(gè)need_resched標(biāo)志，這是因?yàn)樵L問進(jìn)程描述符內(nèi)的數(shù)值要比訪問一個(gè)全局變量快（因?yàn)閏urrent宏速度很快并且描述符通常都在高速緩存中）。
4.6.1 用戶搶占
內(nèi)核即將返回用戶空間的時(shí)候，如果need_resched標(biāo)志被設(shè)置，會(huì)導(dǎo)致schedule（）被調(diào)用，此時(shí)就會(huì)發(fā)生用戶搶占。
用戶搶占在以下情況下發(fā)生：
1、從系統(tǒng)調(diào)用返回
2、從中斷處理程序返回用戶空間
4.6.2 內(nèi)核搶占
每個(gè)進(jìn)程的thread_info引入了preempt_count計(jì)數(shù)器。該計(jì)數(shù)器初始值為0，當(dāng)使用鎖的時(shí)候其值+1，釋放鎖時(shí)-1.當(dāng)數(shù)值為0的時(shí)候內(nèi)核可搶占。從中斷返回內(nèi)核空間的時(shí)候，內(nèi)核會(huì)檢查need_resched和preempt，如果符合條件則調(diào)度程序會(huì)被調(diào)用。
如果內(nèi)核中的進(jìn)程被阻塞了或者內(nèi)核顯式的調(diào)用的schedule（），內(nèi)核搶占也會(huì)發(fā)生。
內(nèi)核搶占發(fā)生在：
1、中斷處理程序正在執(zhí)行
2、內(nèi)核代碼再一次具有可搶占性的時(shí)候。
3、顯示調(diào)用schedule
4、內(nèi)核任務(wù)阻塞
4.7 實(shí)時(shí)調(diào)度策略
linux提供了兩種實(shí)時(shí)調(diào)度策略：SCHED_FIFO和SCHED_RR
SCHED_FIFO：簡(jiǎn)單的先進(jìn)先出，不使用時(shí)間片，會(huì)比任何SCHED_NORMAL級(jí)別的進(jìn)程優(yōu)先得到調(diào)度。SHCED_FIFO會(huì)一直處于執(zhí)行狀態(tài)，直到自己阻塞或釋放處理器，只有高優(yōu)先級(jí)的FIFO或者RR可以搶占其任務(wù)。
SCHED_RR：與FIFO大體相同，RR進(jìn)程在耗盡實(shí)現(xiàn)分配的時(shí)間后就不能再執(zhí)行了。
Linux的實(shí)時(shí)調(diào)度算法提供了一種軟實(shí)時(shí)的工作方式。軟實(shí)時(shí)的含義是，內(nèi)核調(diào)度進(jìn)程，盡力使得進(jìn)程在它限定的時(shí)間到來前運(yùn)行，但內(nèi)核不保證完全滿足這種要求，硬實(shí)時(shí)保證在一定條件下，可以滿足任何調(diào)度的要求。
實(shí)時(shí)優(yōu)先級(jí)范圍從0到99，SCHED_NORMAL級(jí)進(jìn)程的nice值共享了這個(gè)取值空間，默認(rèn)情況下，nice值從-20到19對(duì)應(yīng)從100——139的的實(shí)時(shí)優(yōu)先級(jí)范圍。
4.8 與調(diào)度相關(guān)的系統(tǒng)調(diào)用
nice（）設(shè)置nice值
sched_setscheduler()；設(shè)置進(jìn)程的調(diào)度策略
sched_getscheduler();
sched_setparam(); 設(shè)置進(jìn)程的實(shí)時(shí)優(yōu)先級(jí)
sched_getparm()；
sched_get_priority_max()； 獲取實(shí)時(shí)優(yōu)先級(jí)的大值
sched_get_priority_min()；
sched_rr_get_interval(); 獲取進(jìn)程的時(shí)間片值
sched_setaffinity()； 設(shè)置進(jìn)程的處理器親和力
sched_getaffinity（）；
sched_yield()； 暫時(shí)讓出處理器，通過將進(jìn)程從活動(dòng)隊(duì)列中移到過期隊(duì)列中實(shí)現(xiàn)的。由此產(chǎn)生的效果不僅搶占了該進(jìn)程并將其放入過期隊(duì)列，這樣保證一段時(shí)間內(nèi)它都不會(huì)執(zhí)行了。
重慶分公司
重慶分公司
