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

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

實時調(diào)度器類

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

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

 

SMP

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

調(diào)度域：多個就緒隊列（CPU）組織為一個調(diào)度域，將物理上鄰近或共享高速緩存的CPU群集起來，它是負載均衡的單位，在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é)點。我們的開發(fā)機器是2個物理CPU，每個物理CPU內(nèi)有4個core，每個core又虛擬出2個超線程，所以我們看到的16個CPU，其實是16個超線程，一般的NUMA初始設(shè)置是把同一個物理CPU的放在同一個NUMA節(jié)點內(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