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

分類(lèi)： linux基礎(chǔ) 2013-02-06 20:42 1110人閱讀 評(píng)論(0) 收藏 舉報(bào)

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

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

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

 

SMP

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

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

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

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