極簡cfs公平調度演算法

3.1 名詞解釋

struct sched_entity
{
    unsigned int    on_rq;                           // se是否在rq上，不在的話即使task是Ready狀態也不會投入運行的
    u64             vruntime;                        // cpu運行時長，cfs調度演算法總是選擇該值最小的se投入運行
};
 
struct task
{
    struct sched_entity se;                        // 調度實例
};
 
struct rq
{
    struct cfs_rq cfs;                          // 所有要調度的se都掛在cfs rq中
    struct task_struct* curr;                   // 當前cpu上運行的task
};
 
struct cfs_rq
{
    struct rb_root tasks_timeline;              // 以vruntime為key，se為value的紅黑樹根節點，schedule時，cfs調度演算法每次從這裡挑選vruntime最小的se投入運行
    struct rb_node* rb_leftmost;                // tasks_timeline紅黑樹最左的葉子節點，即vruntime最小的se，直接取這個節點以加快速度
    sched_entity* curr;                         // cfs_rq中當前正在運行的se
    struct rq* rq;                              /* cpu runqueue to which this  cfs_rq is attached */
    unsigned int nr_running;                    // cfs_rq隊列上有多少個se
};

entity_tick()
{
    update_curr();
    // 如果當前cfs_rq上的se大於1，則檢查是否要重新調度
    if (cfs_rq->nr_running > 1)
        check_preempt_tick(cfs_rq, curr);
}

2> update_curr()主要是++當前task se的vruntime（當然這裡還對組調度進行了處理，這裡不講組調度，先略過）

void update_curr(struct cfs_rq* cfs_rq)
{
    struct sched_entity* curr = cfs_rq->curr;
    curr->vruntime += delta_exec;                   // 增加se的運行時間
}

 3> check_preempt_tick()判定當前運行的時間大於sched_slice時，即超過了時間片，或者其vruntime比當前cpu rq隊列中最小的vruntime task大一個時間片，就會標記resched，然後等中斷返回後會調用schedule()進行task切換

void check_preempt_tick()
{
    // 如果運行時間大於sched_slice，則resched
    if (delta_exec > ideal_runtime)
        resched_task(rq_of(cfs_rq)->curr);
        
    // 如果比最小vruntime大一個sched_slice，則resched
    se = __pick_first_entity(cfs_rq);                // 選擇cfs.rb_leftmost的se，即vruntime最小的se
    delta = curr->vruntime - se->vruntime;
    if (delta > ideal_runtime)
        resched_task(rq_of(cfs_rq)->curr);
}

 4> resched_curr()非常簡單，就是設置一個resched標記位TIF_NEED_RESCHED

void resched_curr(struct rq* rq)
{
    struct task_struct* curr = rq->curr;
    set_tsk_thread_flag(curr, TIF_NEED_RESCHED);
}

void schedule()
{
    prev = rq->curr;
    put_prev_task_fair(rq, prev);        // 對當前task進行處理，如果該task屬於一個group，還要對組調度進行處理，這裡不展開
    // 選擇下一個task並切換運行
    next = pick_next_task(rq);           // 選擇一個vruntime最小的task進行調度
    context_switch(rq, prev, next);
}

2> pick_next_task() → pick_next_task_fair() → pick_next_entity() → __pick_first_entity()，__pick_first_entity()選擇vruntime最小的cfs_rq->rb_leftmost節點se進行調度

struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
{
    struct rb_node *left = cfs_rq->rb_leftmost;
    return rb_entry(left, struct sched_entity, run_node);
}