這篇說說內(nèi)核的進(jìn)程調(diào)度機(jī)制，進(jìn)程調(diào)度是內(nèi)核的一個(gè)重要工作，由調(diào)度器完成。
進(jìn)程狀態(tài)
內(nèi)核調(diào)度器調(diào)度的實(shí)體(KSE, kernal schedule entry)是進(jìn)程和線程。內(nèi)核必須知道所有進(jìn)程和線程的狀態(tài)，比如把時(shí)間片給一個(gè)阻塞的進(jìn)程是沒有意義的。從內(nèi)核的角度來看，進(jìn)程的狀態(tài)有3種：
1. 運(yùn)行，表示正在運(yùn)行的進(jìn)程
2. 等待，沒有運(yùn)行，但是等待時(shí)間片運(yùn)行的進(jìn)程
3. 睡眠，也就是阻塞，包括可中斷的阻塞和不可中斷的阻塞。睡眠的進(jìn)程在等待一個(gè)事件的發(fā)生，調(diào)度器無法在下一次任務(wù)切換時(shí)選擇睡眠的進(jìn)程
進(jìn)程在幾種狀態(tài)中不斷的切換
1表示運(yùn)行的進(jìn)程要等待某個(gè)事件，進(jìn)入到了睡眠狀態(tài)
2表示運(yùn)行的進(jìn)程交出CPU資源，進(jìn)入到了等待狀態(tài)
3表示睡眠的進(jìn)程等待的事件發(fā)生了，它進(jìn)入到等待狀態(tài)，不能直接進(jìn)入到運(yùn)行狀態(tài)
4表示等待的進(jìn)程獲得CPU資源，變成運(yùn)行狀態(tài)
5表示運(yùn)行的進(jìn)程結(jié)束，進(jìn)入到終止?fàn)顟B(tài)
內(nèi)核將所有的進(jìn)程保存在一個(gè)進(jìn)程表中，不論是運(yùn)行，等待，睡眠。睡眠的進(jìn)程會(huì)被特別標(biāo)記出來，調(diào)度器知道它們無法立即運(yùn)行，就不會(huì)在下一個(gè)任務(wù)切換時(shí)選擇它們。睡眠的進(jìn)程被分在多個(gè)隊(duì)列中，它們會(huì)在適當(dāng)?shù)臅r(shí)候被喚醒。對(duì)于睡眠的進(jìn)程，又分為兩種:
1. TASK_INTERUPTIBLE，可中斷的睡眠，當(dāng)內(nèi)核發(fā)送信號(hào)給該進(jìn)程表示它等待的事情已經(jīng)發(fā)生時(shí)，響應(yīng)信號(hào)處理程序把進(jìn)程狀態(tài)改成TASK_RUNNING,表示進(jìn)入可運(yùn)行狀態(tài)，只要調(diào)度器選中它就可以運(yùn)行
2. TASK_UNINTERUPTIBLE，不可中斷的睡眠，不能由外部信號(hào)喚醒，即不響應(yīng)外部信號(hào)，只能由內(nèi)核親自喚醒。
所謂的僵尸進(jìn)程是指進(jìn)程資源已經(jīng)被釋放，但是還保存在進(jìn)程表中的進(jìn)程。通常造成僵尸進(jìn)程的原因是子進(jìn)程已經(jīng)被終結(jié)，但是父進(jìn)程沒有調(diào)用wait4系統(tǒng)調(diào)用來確認(rèn)父進(jìn)程知道子進(jìn)程已死亡。這樣子進(jìn)程由于沒有被父進(jìn)程確認(rèn)死亡，但是已經(jīng)釋放了資源，變成了僵尸進(jìn)程。
從執(zhí)行權(quán)限的維度來考察進(jìn)程狀態(tài)，進(jìn)程狀態(tài)分為用戶態(tài)和核心態(tài)。用戶態(tài)只能訪問進(jìn)程自身的數(shù)據(jù)，是受限的。核心態(tài)具有無限權(quán)限，可以訪問任意數(shù)據(jù)。
用戶態(tài)到核心態(tài)的切換有兩種方式，一種是用戶態(tài)執(zhí)行系統(tǒng)調(diào)用，會(huì)切換到核心態(tài)。第二種是中斷，當(dāng)中斷發(fā)生時(shí)，也會(huì)切換到核心態(tài)。
對(duì)于搶占式調(diào)度模型來說，
1. 中斷具有最高權(quán)限，可以搶占處于用戶態(tài)或者核心態(tài)的進(jìn)程的時(shí)間片
2. 當(dāng)進(jìn)程處于核心態(tài)并執(zhí)行系統(tǒng)調(diào)用時(shí)，不能被其他進(jìn)程搶占，當(dāng)然中斷除外
3. 在用戶態(tài)執(zhí)行的進(jìn)程可以隨時(shí)被搶占
調(diào)度器
調(diào)度器主要解決兩個(gè)問題
1. 調(diào)度策略，即決定為每個(gè)進(jìn)程分配多少運(yùn)行時(shí)間，何時(shí)切換到下一個(gè)進(jìn)程，下一個(gè)進(jìn)程是什么
2. 上下文切換，即從進(jìn)程A切換到進(jìn)程B時(shí)，要保證進(jìn)程B的執(zhí)行環(huán)境和上次被撤銷執(zhí)行時(shí)完全一致，比如寄存器的內(nèi)容，虛擬地址空間的各個(gè)數(shù)據(jù)結(jié)構(gòu)。
Linux的調(diào)度器和傳統(tǒng)基于時(shí)間片的調(diào)度器有所區(qū)別，它考慮的是進(jìn)程的等待時(shí)間，即所有可運(yùn)行的進(jìn)程在一個(gè)就緒隊(duì)列里面等待的時(shí)間。對(duì)CPU時(shí)間要求最嚴(yán)格的進(jìn)程被挑選執(zhí)行。就緒隊(duì)列中的進(jìn)程被組織成一棵紅黑樹來加速操作。等待最長的進(jìn)程在最左邊。
調(diào)度器子系統(tǒng)的主要組件如下，
1. 主調(diào)度器和周期性調(diào)度器稱為通用調(diào)度器，來確定是否要調(diào)度。前者處理進(jìn)程打算睡眠或者因?yàn)槟撤N原因放棄CPU的情況，后者以周期性頻率運(yùn)行，檢測(cè)是否需要上下文切換
2. 調(diào)度器類來挑選下一個(gè)執(zhí)行的進(jìn)程。調(diào)度器類分裝了不同的調(diào)度算法，比如完全公平調(diào)度，實(shí)時(shí)調(diào)度，以模塊的方式運(yùn)行
3. 選中下一個(gè)要執(zhí)行的進(jìn)程后，就要進(jìn)行上下文切換，需要和CPU緊密結(jié)合
4. 每個(gè)進(jìn)程都屬于一個(gè)特定的調(diào)度器類，由調(diào)度器類來管理所屬的進(jìn)程，通用調(diào)度器不涉及進(jìn)程的狀態(tài)
進(jìn)程的task_struct結(jié)構(gòu)中和調(diào)度相關(guān)的屬性如下
1. prio, static_prio, normal_prio表示進(jìn)程的優(yōu)先級(jí)信息。static_prio表示靜態(tài)優(yōu)先級(jí)，也就是進(jìn)程啟動(dòng)時(shí)分配的nice優(yōu)先級(jí)值。normal_prio是基于static_prio和調(diào)度策略計(jì)算出來的優(yōu)先級(jí)，進(jìn)程分支時(shí)，子進(jìn)程基礎(chǔ)normal_prio。prio是調(diào)度器考慮的優(yōu)先級(jí)，有時(shí)候內(nèi)核要臨時(shí)提升某個(gè)進(jìn)程的優(yōu)先級(jí)，就是修改prio值，不影響static_prio和normal_prio
2. sched_class表示該進(jìn)程所屬的調(diào)度器類
3. sched_entity表示進(jìn)程所屬的調(diào)度實(shí)體，調(diào)度器不僅可以調(diào)度進(jìn)程，還可以調(diào)度進(jìn)程組，線程等調(diào)度實(shí)體
4. policy表示進(jìn)程的調(diào)度策略，比如SCHED_NORMAL調(diào)度普通進(jìn)程，用完全公平調(diào)度器類來處理。SCHED_BATCH,SCHED_IDEL,SCHED_RR,SCHED_FIFO等
5. time_slice指定該進(jìn)程可以使用的剩余時(shí)間片
調(diào)度器類必須提供sched_class的實(shí)例，指定了調(diào)度器類可以進(jìn)行的操作
1. enqueue_task表示把一個(gè)進(jìn)程加入到就緒隊(duì)列，當(dāng)一個(gè)進(jìn)程狀態(tài)從睡眠變成可運(yùn)行時(shí)，就是發(fā)生了這個(gè)操作進(jìn)入到了就緒隊(duì)列
2. dequeue_task表示把一個(gè)進(jìn)程移出就緒隊(duì)列，比如一個(gè)進(jìn)程從可運(yùn)行狀態(tài)切換到不可運(yùn)行狀態(tài)
3. yield_task表示進(jìn)程自愿放棄CPU控制權(quán)的操作
4. check_preempt_curr表示一個(gè)新喚醒的進(jìn)程來搶占當(dāng)前進(jìn)程，比如wake_up_new_task喚醒新進(jìn)程時(shí)發(fā)生這個(gè)操作
5. pick_next_task用于選擇下一個(gè)執(zhí)行的進(jìn)程，向進(jìn)程提供CPU資源。但在不同進(jìn)程切換時(shí)，還需要執(zhí)行一個(gè)底層的上下文切換
6. task_tick表示激活周期性調(diào)度器
7. task_new表示將fork出來的新進(jìn)程加入到調(diào)度器類
用戶層程序是無法直接和調(diào)度器類交互的，都是通過調(diào)度策略常量，比如SCHED_NORMAL，SCHED_BATCH，SCHED_IDEL映射到完全公平調(diào)度器類fair_sched_class, SCHED_RR,SCHED_FIFO映射到實(shí)時(shí)調(diào)度器rt_sched_class。
每個(gè)CPU都對(duì)應(yīng)一個(gè)就緒隊(duì)列，一個(gè)活動(dòng)進(jìn)程只能出現(xiàn)在一個(gè)就緒隊(duì)列中。對(duì)于只使用進(jìn)程的程序來說，一個(gè)進(jìn)程只能同時(shí)在一個(gè)CPU執(zhí)行。而基于線程的程序來說，源于一個(gè)進(jìn)程的不同線程可以同時(shí)運(yùn)行在多個(gè)CPU。就緒隊(duì)列的結(jié)構(gòu)如下
1. nr_running和load表示當(dāng)前就緒隊(duì)列的負(fù)載情況。就緒隊(duì)列的虛擬時(shí)鐘的速度就是基于這個(gè)信息
2. cfs_rq是完全公平調(diào)度器類的子就緒隊(duì)列，rt_rq是實(shí)時(shí)調(diào)度器類的就緒隊(duì)列
3. curr指向當(dāng)前正在運(yùn)行的進(jìn)程
4. clock用于實(shí)現(xiàn)就緒隊(duì)列自身的時(shí)鐘，每次調(diào)用周期性調(diào)度器都會(huì)更新clock值
調(diào)度實(shí)體的結(jié)構(gòu)如下，它表示一般性的可以調(diào)度的實(shí)體，包括進(jìn)程，進(jìn)程組，線程等等
1. load表示負(fù)載，表示該實(shí)體占用隊(duì)列總負(fù)荷的比例。計(jì)算負(fù)荷是調(diào)度器類的一個(gè)重任，它影響到虛擬時(shí)鐘的速度
2. run_node表示紅黑樹的節(jié)點(diǎn)，讓這個(gè)實(shí)體可以出現(xiàn)在紅黑樹上
3. on_rq來表示該實(shí)體是否處于就緒隊(duì)列
4. exec_start表示進(jìn)程每次開始執(zhí)行的時(shí)間，sum_exec_runtime表示該進(jìn)程總共執(zhí)行了的時(shí)間。每次進(jìn)程運(yùn)行開始時(shí)，都會(huì)記錄exec_start值，然后每次調(diào)用update_curr系統(tǒng)調(diào)用都會(huì)用當(dāng)前時(shí)間減去exec_start，把差值加到sum_exec_runtime中。
5. 當(dāng)進(jìn)程被撤銷CPU時(shí)，會(huì)把sum_exec_runtime保存到pre_sum_exec_runtime中去。當(dāng)進(jìn)程搶占時(shí)，sun_exec_time又單調(diào)增長。
6. vruntime記錄進(jìn)程運(yùn)行期間虛擬時(shí)鐘流式的時(shí)間數(shù)量
通用調(diào)度器有兩類，一個(gè)是周期性調(diào)度器，一個(gè)是主調(diào)度器。周期性調(diào)度器在schedule_tick函數(shù)中實(shí)現(xiàn)。內(nèi)核按照頻率自動(dòng)調(diào)用這個(gè)函數(shù)，會(huì)激活當(dāng)前進(jìn)程的調(diào)度器類的周期性
調(diào)度方法。
如果當(dāng)前進(jìn)程需要被重新調(diào)度，那么調(diào)度器類會(huì)在task_struct中設(shè)置TIF_NEED_RESCHED標(biāo)志，內(nèi)核會(huì)在適當(dāng)?shù)臅r(shí)機(jī)完成該調(diào)度請(qǐng)求。
主調(diào)度器負(fù)責(zé)把CPU從一個(gè)進(jìn)程交給另一個(gè)進(jìn)程。主調(diào)度器在schedule函數(shù)中實(shí)現(xiàn)。當(dāng)系統(tǒng)調(diào)用返回時(shí)，內(nèi)核會(huì)檢查當(dāng)前進(jìn)程是否設(shè)置了重調(diào)度標(biāo)志TIF_NEED_RESCHED。如果設(shè)置了該標(biāo)志，那么內(nèi)核會(huì)調(diào)用schedule函數(shù)來切換。
1.schedule函數(shù)首先確定當(dāng)前就緒隊(duì)列，并在prev指針保存當(dāng)前還在運(yùn)行的進(jìn)程task_struct。修改就緒隊(duì)列的clock值，取消TIF_NEED_RESCHED標(biāo)志。
2. 如果當(dāng)前進(jìn)程處于可中斷睡眠狀態(tài)，并且接收到喚醒信號(hào)，那么把當(dāng)前進(jìn)程狀態(tài)改成可運(yùn)行，否則使進(jìn)程停止活動(dòng)，進(jìn)入睡眠隊(duì)列。
3. 調(diào)用調(diào)度器類的put_prev_task通知調(diào)度器類當(dāng)前進(jìn)程要被另一個(gè)進(jìn)程所替換。調(diào)用pick_next_task選取下一個(gè)進(jìn)程。不一定會(huì)選取新的進(jìn)程，比如其他進(jìn)程都處于睡眠狀態(tài)，就一個(gè)可以運(yùn)行的進(jìn)程。一旦選擇了一個(gè)進(jìn)程，那么就要準(zhǔn)備執(zhí)行硬件級(jí)的上下文切換
4. context_switch負(fù)責(zé)執(zhí)行硬件級(jí)的上下文切換
5. 檢查重調(diào)度標(biāo)志，如果當(dāng)前進(jìn)程設(shè)置了TIF_NEED_SCHED標(biāo)志，就goto到need_resched執(zhí)行。
來看看上下文切換做了什么工作
1. 先調(diào)用和體系結(jié)構(gòu)相關(guān)的prepare_task_switch函數(shù)為切換做事先準(zhǔn)備
2. mm和oldmm表示下一個(gè)進(jìn)程的用戶空間虛擬地址上下文實(shí)例和上一個(gè)進(jìn)程的用戶空間虛擬地址上下文實(shí)例
3. switch_mm函數(shù)更換由task_struct的mm描述的用戶空間虛擬地址上下文，比如加載的頁表，刷出TLB。主要是存放在高速緩存和TLB中的供CPU使用的數(shù)據(jù)。而更多的數(shù)據(jù)保存在內(nèi)存中，是不需要切換的的，在需要時(shí)從內(nèi)存加載
4. swtich_to函數(shù)切換寄存器和內(nèi)核棧中的數(shù)據(jù)，將新進(jìn)程用戶空間程序之前使用到的寄存器內(nèi)容恢復(fù)到寄存器。關(guān)于寄存器的內(nèi)容，有一個(gè)要點(diǎn)是當(dāng)用戶態(tài)進(jìn)入到核心態(tài)時(shí)，會(huì)把用戶空間程序的寄存器內(nèi)容保存到內(nèi)核棧。所以上下文切換時(shí)，寄存器內(nèi)容不需要特別處理。進(jìn)程總是從核心態(tài)開始執(zhí)行，返回到用戶空間時(shí)，寄存器的內(nèi)容會(huì)從內(nèi)核?；謴?fù)。
完全公平調(diào)度器類的基本原理是計(jì)算進(jìn)程的虛擬時(shí)鐘值，虛擬時(shí)鐘值是度量一個(gè)等待的進(jìn)程可以獲得的CPU時(shí)間。這個(gè)值是由實(shí)際時(shí)鐘和進(jìn)程的負(fù)荷權(quán)重計(jì)算出來的。所有與虛擬時(shí)鐘相關(guān)的計(jì)算都是有update_curr函數(shù)相關(guān)的。update_curr被周期性調(diào)度器觸發(fā)
就緒隊(duì)列的紅黑樹最左邊節(jié)點(diǎn)是要被選出的節(jié)點(diǎn)，紅黑樹是按照vruntime的值來排序的。紅黑樹還維護(hù)了一個(gè)min_vruntime值，表示整棵數(shù)最小的虛擬時(shí)鐘值。當(dāng)最左邊節(jié)點(diǎn)的vruntime值大于min_vruntime時(shí)，會(huì)更新min_vruntime值為最左邊節(jié)點(diǎn)的vruntime值。
1. vruntime值總是不斷增長的，也就是說節(jié)點(diǎn)在紅黑樹中不斷右移。當(dāng)進(jìn)程進(jìn)入運(yùn)行時(shí)，它的vruntime會(huì)增長。越重要的進(jìn)程的vruntime值增長越慢，也就是說右移的速度越慢
2. min_vruntime值總是單調(diào)增長的。當(dāng)一個(gè)進(jìn)程進(jìn)入睡眠時(shí)它的vruntime是保持不變的，當(dāng)它醒來時(shí)，它在紅黑樹中的位置相對(duì)左移，被更優(yōu)先調(diào)度。
進(jìn)程調(diào)度是基于就緒隊(duì)列的，就緒隊(duì)列中等待的進(jìn)程都是可運(yùn)行狀態(tài)。而睡眠的進(jìn)程則處于等待隊(duì)列，在等待隊(duì)列中的進(jìn)程不會(huì)被調(diào)度器選擇。而睡眠的進(jìn)程醒來之后，會(huì)進(jìn)入就緒隊(duì)列。睡眠的進(jìn)程有兩種，可中斷和不可中斷。喚醒一個(gè)在等待隊(duì)列中睡眠的進(jìn)程有幾種方式。
1. 等待的信號(hào)到達(dá)，處理可中斷的睡眠進(jìn)程
2. 等待的事件發(fā)生，比如讀取網(wǎng)卡數(shù)據(jù)的進(jìn)程在網(wǎng)卡沒有數(shù)據(jù)的時(shí)候進(jìn)入不可中斷睡眠，當(dāng)網(wǎng)卡數(shù)據(jù)達(dá)到時(shí)，會(huì)調(diào)用wake_up函數(shù)，來喚醒在等待網(wǎng)卡數(shù)據(jù)的進(jìn)程
聯(lián)系客服
