計算機操作系統(tǒng)（第二版）課件：Linux 進(jìn)程調(diào)度算法解析

3.5.3Linux/openEuler進(jìn)程調(diào)度算法解析

進(jìn)程調(diào)度1.Linux調(diào)度器的發(fā)展Linux2.4內(nèi)核的優(yōu)先級調(diào)度器普通進(jìn)程：動態(tài)優(yōu)先級（權(quán)值weight），與進(jìn)程的時間片長度有關(guān)實時進(jìn)程：靜態(tài)優(yōu)先級實時進(jìn)程調(diào)度策略有兩種：SCHED_FIFO和SCHED_RR2.4內(nèi)核調(diào)度器的主要不足之處：

調(diào)度時間開銷是O(n)

每次重新計算進(jìn)程優(yōu)先級開銷較大對交互式進(jìn)程的優(yōu)化并不完善內(nèi)核是非搶占的，因此對實時進(jìn)程的支持不夠看視頻及教材自學(xué)為主1.Linux調(diào)度器的發(fā)展Linux2.6內(nèi)核的O(1)調(diào)度器調(diào)度時間開銷為O(1)，與系統(tǒng)中就緒進(jìn)程數(shù)量無關(guān)就緒隊列設(shè)置3.5.3Linux/openEuler進(jìn)程調(diào)度算法解析1.Linux調(diào)度器的發(fā)展Linux2.6內(nèi)核的O(1)調(diào)度器調(diào)度時間開銷為O(1)，與系統(tǒng)中就緒進(jìn)程數(shù)量無關(guān)

位示圖設(shè)置●●3.5.3Linux/openEuler進(jìn)程調(diào)度算法解析1.Linux調(diào)度器的發(fā)展Linux2.6內(nèi)核的O(1)調(diào)度器支持內(nèi)核搶占，能更好地支持實時進(jìn)程分散計算各進(jìn)程優(yōu)先級及時間片，減小了計算的時間開銷根據(jù)一些經(jīng)驗公式調(diào)整進(jìn)程優(yōu)先級，適當(dāng)照顧交互式進(jìn)程prio=max(100,min(static_prio-bonus+5,139))3.5.3Linux/openEuler進(jìn)程調(diào)度算法解析1.Linux調(diào)度器的發(fā)展

完全公平調(diào)度器：CFS設(shè)計思想：

期望每個進(jìn)程都能同時在CPU上并行執(zhí)行，且各進(jìn)程的執(zhí)行速度相同虛擬運行時間：vruntime將進(jìn)程nice值轉(zhuǎn)換為權(quán)重weight3.5.3Linux/openEuler進(jìn)程調(diào)度算法解析

完全公平調(diào)度器：CFS虛擬運行時間：vruntime

CPU運行期period：就緒隊列中所有任務(wù)運行完一遍的時間

進(jìn)程運行時間計算：例：系統(tǒng)有兩個兩個就緒進(jìn)程A和BWA=15（nice值19），WB=110（nice值10）：則：

TA=2.4ms，TB=17.6ms3.5.3Linux/openEuler進(jìn)程調(diào)度算法解析

完全公平調(diào)度器：CFS虛擬運行時間：vruntime進(jìn)程虛擬運行時間：structload_weight{unsignedlongweight;//進(jìn)程權(quán)重Winv_weight;//232/W的值};3.5.3Linux/openEuler進(jìn)程調(diào)度算法解析

完全公平調(diào)度器CFS——調(diào)度舉例CPU實際時間(ms)TA(ms)VTA(ms)TB(ms)VTB(ms)說明（每次period中，A可運行2.4ms，B可運行17.6ms）101068300A用完可運行時間，重新調(diào)度，VTB＜VTA，調(diào)度B運行20106831093B未用完可運行時間，B繼續(xù)運行301068320186B用完可運行時間，重新調(diào)度，VTB＜VTA，B繼續(xù)運行401068330279B用完可運行時間，重新調(diào)度，VTB＜VTA，B繼續(xù)運行501068340372B用完可運行時間，重新調(diào)度，VTB＜VTA，B繼續(xù)運行601068350465B用完可運行時間，重新調(diào)度，VTB＜VTA，B繼續(xù)運行701068360558B用完可運行時間，重新調(diào)度，VTB＜VTA，B繼續(xù)運行801068370651B用完可運行時間，重新調(diào)度，VTA＜VTB，調(diào)度A運行9020136670744A用完可運行時間，重新調(diào)度，VTB＜VTA，調(diào)度B運行以此類推……，總是企圖讓所有進(jìn)程的VT趨向于相等，實現(xiàn)公平調(diào)度

完全公平調(diào)度器：CFSCFS調(diào)度器的相關(guān)數(shù)據(jù)結(jié)構(gòu)

進(jìn)程描述符task_struck結(jié)構(gòu)：struct

task_struct

{

volatile

long

state;

/*

進(jìn)程狀態(tài)*/

int

prio,

static_prio,

normal_prio;

/*

進(jìn)程優(yōu)先級*/

unsigned

int

rt_priority;

/*

實時進(jìn)程的實時優(yōu)先級*/

const

struct

sched_class

*sched_class;

/*

進(jìn)程的調(diào)度器類*/

struct

sched_entity

se;

/*

普通進(jìn)程調(diào)度實體*/

struct

sched_rt_entity

rt;

/*

實時進(jìn)程調(diào)度實體*/

......

};

3.5.3Linux/openEuler進(jìn)程調(diào)度算法解析

調(diào)度實體sched_entity：structsched_entity{structload_weight load;/*進(jìn)程權(quán)重結(jié)構(gòu)：weight和inv_weight*/structrb_node run_node;/*在紅黑樹中的節(jié)點*/unsignedint on_rq;/*若進(jìn)程在就緒隊列中，則置為1*/u64 exec_start;/*進(jìn)程本次調(diào)入CPU執(zhí)行的開始實際時間*/u64 sum_exec_runtime;/*進(jìn)程總共執(zhí)行的實際時間*/u64 vruntime;/*進(jìn)程總共執(zhí)行的虛擬時間*/u64 prev_sum_exec_runtime;/*進(jìn)程前一次投入運行的總的執(zhí)行時間*/

......

};

完全公平調(diào)度器：CFSCFS調(diào)度器的相關(guān)數(shù)據(jù)結(jié)構(gòu)3.5.3Linux/openEuler進(jìn)程調(diào)度算法解析CFS就緒隊列cfs_rq：部分字段structcfs_rq{structload_weightload;/*就緒隊列進(jìn)程的總權(quán)重*/unsignedlongnr_running;/*就緒隊列中的進(jìn)程數(shù)量*/u64exec_clock;/*CPU實際執(zhí)行總時間*/u64min_vruntime;/*為新進(jìn)程或剛被喚醒的進(jìn)程設(shè)置vruntime*/structrb_roottasks_timeline;/*紅黑樹的根節(jié)點*/structrb_node*rb_leftmost;/*紅黑樹中最左邊的節(jié)點，即下一個被調(diào)度進(jìn)程*/structrb_node*rb_load_balance_curr;/*負(fù)載平衡的下一個被調(diào)度進(jìn)程節(jié)點*/structsched_entity*curr;/*當(dāng)前正在CPU上運行的進(jìn)程的調(diào)度實體*/unsignedlongnr_spread_over;}；

完全公平調(diào)度器：CFSCFS調(diào)度器的相關(guān)數(shù)據(jù)結(jié)構(gòu)3.5.3Linux/openEuler進(jìn)程調(diào)度算法解析CFS調(diào)度器的相關(guān)數(shù)據(jù)結(jié)構(gòu)CPU就緒隊列rq：部分字段structrq{spinlock_t

lock;/*就緒隊列的自旋鎖*/unsignedlongnr_running;/*就緒隊列中的進(jìn)程總數(shù)*/unsignedcharidle_at_tick;/*當(dāng)前CPU是否處于空閑狀態(tài)*/structload_weightload;/*就緒隊列總權(quán)重*/u64nr_switches;/*該CPU進(jìn)程切換次數(shù)*/structcfs_rqcfs;/*該CPU的CFS調(diào)度器的就緒隊列*/structrt_rqrt;/*該CPU的實時進(jìn)程就緒隊列*/unsignedlongnr_uninterruptible;/*該CPU上可中斷睡眠的進(jìn)程數(shù)*/structtask_struct*curr,*idle;structmm_struct*prev_mm;/*該CPU上最后運行進(jìn)程的mm_struct*/intcpu;/*本就緒隊列對應(yīng)的CPU*/

…

}

完全公平調(diào)度器：CFSCFS調(diào)度器的模塊化調(diào)度五種調(diào)度器類：

stop_sched_class→dl_sched_class→rt_sched_class→fair_sched_class→idle_sched_class

調(diào)度器類與調(diào)度策略的對應(yīng)關(guān)系：stop_sched_class：只使用在某些特殊情況，如在CPU之間遷移任務(wù)實現(xiàn)負(fù)載平衡時dl_sched_class：SCHED_DEADLINE，實時進(jìn)程調(diào)度策略rt_sched_class：SCHED_RR與SCHED_FIFO調(diào)度策略fair_sched_class：SCHED_NORMAL與SCHED_BACH調(diào)度策略idle_sched_class：SCHED_IDLE調(diào)度策略

完全公平調(diào)度器：CFSCFS調(diào)度器的模塊化調(diào)度

調(diào)度器類結(jié)構(gòu)：structsched_class{conststructsched_class*next;structtask_struct*(*pick_next_task)(structrq*rq);void(*put_prev_task)(structrq*rq,structtask_struct*p);void(*task_tick)(structrq*rq,structtask_struct*p);

…};

完全公平調(diào)度器：CFS2.CFS調(diào)度器的實現(xiàn)CFS調(diào)度器類結(jié)構(gòu)定義staticconststructsched_classfair_sched_class={.next=&idle_sched_class,/*指向下一個調(diào)度器對象*/.enqueue_task=enqueue_task_fair,.dequeue_task=dequeue_task_fair,.pick_next_task=pick_next_task_fair,.put_prev_task=put_prev_task_fair,.task_tick=task_tick_fair,

…};3.5.3Linux/openEuler進(jìn)程調(diào)度算法解析2.CFS調(diào)度器的實現(xiàn)CFS調(diào)度器類結(jié)構(gòu)定義staticvoidenqueue_task_fair(structrq*rq,structtask_struct*p,intwakeup)功能：將指定進(jìn)程加入到其所在的cfs_rq就緒隊列中staticvoiddequeue_task_fair(structrq*rq,structtask_struct*p,intsleep)功能：將指定進(jìn)程從所在cfs_rq中刪除staticvoidyield_task_fair(structrq*rq)功能：調(diào)用進(jìn)程讓出CPU使用權(quán)staticvoidcheck_preempt_wakeup(structrq*rq,structtask_struct*p)功能：檢查剛創(chuàng)建的新進(jìn)程或剛被喚醒的進(jìn)程P是否應(yīng)該搶占當(dāng)前運行進(jìn)程3.5.3Linux/openEuler進(jìn)程調(diào)度算法解析2.CFS調(diào)度器的實現(xiàn)CFS調(diào)度器類結(jié)構(gòu)定義staticstructtask_struct*pick_next_task_fair(structrq*rq)功能：從cfs_rq中找到下一個調(diào)度運行的進(jìn)程staticvoidput_prev_task_fair(structrq*rq,structtask_struct*prev)功能：把當(dāng)前運行進(jìn)程放入其所在的cfs_rq中staticvoidtask_tick_fair(structrq*rq,structtask_struct*curr)功能：檢查當(dāng)前運行進(jìn)程本次調(diào)度中實際運行時間是否大于它本次應(yīng)該運行的時間，如果是，則設(shè)置調(diào)度標(biāo)志TIF_NEED_RESCHEDstaticvoidtask_new_fair(structrq*rq,structtask_struct*p)功能：計算新進(jìn)程的vruntime，并加入cfs_rq中3.5.3Linux/openEuler進(jìn)程調(diào)度算法解析3.Linux/openEuler實時調(diào)度

實時調(diào)度策略：SCHED_FIFO策略：

采用簡單的FIFO調(diào)度算法SCHED_RR策略：

采用時間片輪轉(zhuǎn)算法

時間片=100*Hz/1000dl_sched_classrt_sched_class3.5.3Linux/openEuler進(jìn)程調(diào)度算法解析

就緒隊列rt_rqstructrt_rq{structrt_prio_arrayactive;/*實時進(jìn)程的優(yōu)先級就緒隊列*/intrt_load_balance_idx;structlist_head*rt_load_balance_head,t_load_balance_curr;};

就緒隊列設(shè)置structrt_prio_array{DECLARE_BITMAP(bitmap,MAX_RT_PRIO+1);/*優(yōu)先級位圖*/structlist_headqueue[MAX_RT_PRIO];/*優(yōu)先級隊列*/};3.5.3Linux/openEuler進(jìn)程調(diào)度算法解