linux調(diào)度器（八）——實(shí)時調(diào)度與SMP

分類： linux基礎(chǔ) 2013-02-06 20:42 1110人閱讀 評論(0) 收藏 舉報

實(shí)時調(diào)度器類

實(shí)時調(diào)度類有兩類進(jìn)程：
循環(huán)進(jìn)程SCHED_RR：循環(huán)進(jìn)程有時間片，隨著進(jìn)程的運(yùn)行時間會減少。當(dāng)時間片用完時又將其置為初值，并將進(jìn)程置于隊(duì)列末尾。
先進(jìn)先出SCHED_FIFO：沒有時間片調(diào)度，運(yùn)行后可執(zhí)行任意長時間直到自己放棄CPU。
實(shí)際上兩類進(jìn)程在相同優(yōu)先級隊(duì)列上都是先進(jìn)先出的，只是一個有時間片一個沒有時間片。
    現(xiàn)在實(shí)時進(jìn)程的調(diào)度其實(shí)就是使用之前內(nèi)核的O(1)，每個優(yōu)先級（總共MAX_RT_PRIO）有一個queue，并且通過一個bitmap（位數(shù)也是MAX_RT_PRIO+1）表示所有優(yōu)先級隊(duì)列的狀態(tài)，即bitmap的第0位，表示優(yōu)先級queue[0]是否有等待運(yùn)行的進(jìn)程，0表示沒有，1表示有，所以每次調(diào)度的時候總是查找bitmap第一個非0的位，然后取出它的queue的head，它就是這次調(diào)度獲得的進(jìn)程。下面我們簡單的解釋一下，實(shí)時調(diào)度器類的周期性調(diào)度器，主調(diào)度器。
    它對應(yīng)的實(shí)時周期性調(diào)度器對應(yīng)函數(shù)為task_tick_rt，首先更新當(dāng)前進(jìn)程的執(zhí)行時間，檢查是不是FIFO進(jìn)程，如果是的話直接返回，否則是RR進(jìn)程，那么就把它的時間片減1，并判斷是否為0，如果不為0則直接返回，否則就重新分配時間片，并把它放到它的優(yōu)先級隊(duì)列的隊(duì)尾，然后設(shè)置TIF_NEED_RESCHED標(biāo)志。
    大多數(shù)邏輯如enqueue_task_rt，dequeue_task_rt，put_prev_task_rt跟CFS差不多，只是所操作的隊(duì)列不一樣了（實(shí)時類只需以p->prio為索引訪問queue[p->prio]），另外需要注意的就兩個：pick_next_task_rt（該過程我們上面也解釋了，通過bitmap及queue獲得），check_preempt_curr_rt（判斷是否該preempt對于實(shí)時進(jìn)程唯一有效的就是優(yōu)先級，顯然新的進(jìn)程比當(dāng)前的優(yōu)先級高的話，那么它就可以搶占，否則如果相等的話則因?yàn)镾MP，所以有這個當(dāng)前進(jìn)程可能會被遷移到其它進(jìn)程，具體條件當(dāng)前進(jìn)程可運(yùn)行的cpu!=1，新進(jìn)程可運(yùn)行cpu==1,當(dāng)前進(jìn)程找到其它可用的cpu，只有這幾個條件都滿足了才可以讓當(dāng)前的進(jìn)程讓同等優(yōu)先級的進(jìn)程搶占，但它帶來的開銷也是很大的）

注：其實(shí)實(shí)時進(jìn)程也是有組調(diào)度的，這里我們不再去分析它，并且不管CFS還是RT它們都可以對隊(duì)列進(jìn)行throttled的特性，這里我們也沒有去分析。

 

SMP

         下面我們簡單介紹一下SMP的主要過程：框架周期性調(diào)度器在執(zhí)行完上面所說的過程后會調(diào)用trigger_load_balance觸發(fā)個SCHEDULE_SOFTIRQ軟中斷，該中斷確保會在適當(dāng)?shù)臅r機(jī)執(zhí)行run_rebalance_domains。該函數(shù)最終對當(dāng)前CPU調(diào)用rebalance_domains判斷該CPU下的每個調(diào)度域是否需要balance，如果需要最終將調(diào)用load_balance來實(shí)現(xiàn)負(fù)載均衡；另外內(nèi)核為每個就緒隊(duì)列提供一個遷移線程，用來接收遷移請求，這些請求被保存在migration_queue鏈表中。
load_balance函數(shù)首先查找CPU（進(jìn)入這個過程的CPU已經(jīng)是CPU_IDLE）所屬調(diào)度域內(nèi)最忙的（CPU）運(yùn)行隊(duì)列，然后使用move_tasks將該隊(duì)列（最忙）中適當(dāng)數(shù)目的進(jìn)程遷移到當(dāng)前CPU的運(yùn)行隊(duì)列里，最終move_tasks調(diào)用特定調(diào)度器類的load_balance方法。下面兩種進(jìn)程在load_balance里無法完成：
A. 進(jìn)程由于親緣性不能在當(dāng)前CPU下運(yùn)行
B. 進(jìn)程正在運(yùn)行（成本太大）
當(dāng)load_balance失敗的時候（沒有完成一個進(jìn)程的balance），會設(shè)置最忙運(yùn)行隊(duì)列的active_balance及它將要遷移的目標(biāo)CPU（當(dāng)前CPU），然后喚醒最忙CPU的遷移線程wake_up_process(busiest->migration_thread)，那么此時最忙CPU運(yùn)行的就是這個遷移線程（之前的線程不再運(yùn)行），所以之前的線程現(xiàn)在就有可能會被遷移到目標(biāo)CPU；最忙CPU運(yùn)行遷移線程，當(dāng)它檢查到rq->active_balance則調(diào)用active_load_balance，最終分別調(diào)用特定調(diào)度器類的move_one_task函數(shù)（該函數(shù)完成的過程會比load_balance更激烈的方法，如不考慮優(yōu)先級）。

調(diào)度域：多個就緒隊(duì)列（CPU）組織為一個調(diào)度域，將物理上鄰近或共享高速緩存的CPU群集起來，它是負(fù)載均衡的單位，在balance時應(yīng)優(yōu)先選擇在同一個調(diào)度域內(nèi)的CPU之間的遷移

在CPU（邏輯CPU）間的遷移優(yōu)先（這也關(guān)系到調(diào)度域的組織）：同一個core（L1,L2），同一個物理CPU（L3），同一個NUMA節(jié)點(diǎn)。我們的開發(fā)機(jī)器是2個物理CPU，每個物理CPU內(nèi)有4個core，每個core又虛擬出2個超線程，所以我們看到的16個CPU，其實(shí)是16個超線程，一般的NUMA初始設(shè)置是把同一個物理CPU的放在同一個NUMA節(jié)點(diǎn)內(nèi)。這些信息可以從/proc/cpuinfo查看：processor（表示邏輯cpu，也就是超線程）；physical id（表示物理CPU ID）；core id（表示一個物理CPU內(nèi)的core id，不同CPU間的core id可能一樣）；siblings（表示）一個物理CPU上的超線程數(shù)；cpu cores（表示一個物理CPU的core數(shù)）

參考：http://hi.baidu.com/_kouu/item/479891211a84e3c9a5275ad9