Linux CFS調度器之task_tick_fair處理周期性調度器--Linux進程的管理與調度(二十九）

1. CFS如何處理周期性調度器周期性調度器的工作由scheduler_tick函數完成(定義在 "kernel/sched/core.c, line 2910" ), 在scheduler_tick中周期性調度器通過調用curr進程所屬調度器類sched_class的task_tick函數完成周 ...

1. CFS如何處理周期性調度器

周期性調度器的工作由scheduler_tick函數完成(定義在kernel/sched/core.c, line 2910), 在scheduler_tick中周期性調度器通過調用curr進程所屬調度器類sched_class的task_tick函數完成周期性調度的工作

周期調度的工作形式上sched_class調度器類的task_tick函數完成, CFS則對應task_tick_fair函數, 但實際上工作交給entity_tick完成.

2 CFS的周期性調度

2.1 task_tick_fair與周期性調度

CFS完全公平調度器類通過task_tick_fair函數完成周期性調度的工作, 該函數定義在kernel/sched/fair.c?v=4.6#L8119

/*
 * scheduler tick hitting a task of our scheduling class:
 */
static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
{
    struct cfs_rq *cfs_rq;
    /*  獲取到當前進程curr所在的調度實體  */
    struct sched_entity *se = &curr->se;

    /* for_each_sched_entity
     * 在不支持組調度條件下, 只迴圈一次
     * 在組調度的條件下, 調度實體存在層次關係,
     * 更新子調度實體的同時必須更新父調度實體  */
    for_each_sched_entity(se)
    {
        /*  獲取噹噹前運行的進程所在的CFS就緒隊列  */
        cfs_rq = cfs_rq_of(se);
        /*  完成周期性調度  */
        entity_tick(cfs_rq, se, queued);
    }

    if (static_branch_unlikely(&sched_numa_balancing))
        task_tick_numa(rq, curr);
}

我們可以看到, CFS周期性調度的功能實際上是委托給entity_tick函數來完成的

2.2 entity_tick函數

在task_tick_fair中, 內核將CFS周期性調度的實際工作交給了entity_tick來完成, 該函數定義在kernel/sched/fair.c, line 3470中, 如下所示

static void
entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
{
    /*
     * Update run-time statistics of the 'current'.
     */
    update_curr(cfs_rq);

    /*
     * Ensure that runnable average is periodically updated.
     */
    update_load_avg(curr, 1);
    update_cfs_shares(cfs_rq);

#ifdef CONFIG_SCHED_HRTICK
    /*
     * queued ticks are scheduled to match the slice, so don't bother
     * validating it and just reschedule.
     */
    if (queued) {
        resched_curr(rq_of(cfs_rq));
        return;
    }
    /*
     * don't let the period tick interfere with the hrtick preemption
     */
    if (!sched_feat(DOUBLE_TICK) &&
            hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))
        return;
#endif

    if (cfs_rq->nr_running > 1)
        check_preempt_tick(cfs_rq, curr);
}

首先, 一如既往的使用update_curr來更新統計量

接下來是hrtimer的更新, 這些由內核通過參數CONFIG_SCHED_HRTICK開啟

然後如果cfs就緒隊列中進程數目nr_running少於兩個(< 2)則實際上無事可做. 因為如果某個進程應該被搶占, 那麼至少需要有另一個進程能夠搶占它(即cfs_rq->nr_running > 1)

如果進程的數目不少於兩個, 則由check_preempt_tick作出決策

if (cfs_rq->nr_running > 1)
        check_preempt_tick(cfs_rq, curr);

2.3 check_preempt_tick函數

在entity_tick中, 如果cfs的就緒隊列中進程數目不少於2, 說明至少需要有另外一個進程能夠搶占當前進程, 此時內核交給check_preempt_tick作出決策. check_preempt_tick函數定義在kernel/sched/fair.c, line 3308

/*
 * Preempt the current task with a newly woken task if needed:
 */
static void
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    unsigned long ideal_runtime, delta_exec;
    struct sched_entity *se;
    s64 delta;

    /*  計算curr的理論上應該運行的時間  */
    ideal_runtime = sched_slice(cfs_rq, curr);

    /*  計算curr的實際運行時間
     *  sum_exec_runtime: 進程執行的總時間
     *  prev_sum_exec_runtime:進程在切換進CPU時的sum_exec_runtime值  */
    delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;

    /*  如果實際運行時間比理論上應該運行的時間長
     *  說明curr進程已經運行了足夠長的時間
     *  應該調度新的進程搶占CPU了  */
    if (delta_exec > ideal_runtime)
    {
        resched_curr(rq_of(cfs_rq));
        /*
         * The current task ran long enough, ensure it doesn't get
         * re-elected due to buddy favours.
         */
        clear_buddies(cfs_rq, curr);
        return;
    }

    /*
     * Ensure that a task that missed wakeup preemption by a
     * narrow margin doesn't have to wait for a full slice.
     * This also mitigates buddy induced latencies under load.
     */
    if (delta_exec < sysctl_sched_min_granularity)
        return;

    se = __pick_first_entity(cfs_rq);
    delta = curr->vruntime - se->vruntime;

    if (delta < 0)
        return;

    if (delta > ideal_runtime)
        resched_curr(rq_of(cfs_rq));
}

check_preempt_tick函數的目的在於, 判斷是否需要搶占當前進程. 確保沒有哪個進程能夠比延遲周期中確定的份額運行得更長. 該份額對應的實際時間長度在sched_slice中計算.

而上一節我們提到, 進程在CPU上已經運行的實際時間間隔由sum_exec_runtime - prev_sum_runtime給出.

還記得上一節，在set_next_entity函數的最後, 將選擇出的調度實體se的sum_exec_runtime保存在了prev_sum_exec_runtime中, 因為該調度實體指向的進程, 馬上將搶占處理器成為當前活動進程, 在CPU上花費的實際時間將記入sum_exec_runtime, 因此內核會在prev_sum_exec_runtime保存此前的設置. 要註意進程中的sum_exec_runtime沒有重置. 因此差值sum_exec_runtime - prev_sum_runtime確實標識了在CPU上執行花費的實際時間.

在處理周期性調度時, 這個差值就顯得格外重要

因此搶占決策很容易做出決定, 如果檢查發現當前進程運行需要被搶占, 那麼通過resched_task發出重調度請求. 這會在task_struct中設置TIF_NEED_RESCHED標誌, 核心調度器會在下一個適當的時機發起重調度.

其實需要搶占的條件有下麵兩種可能性

curr進程的實際運行時間delta_exec比期望的時間間隔ideal_runtime長

此時說明curr進程已經運行了足夠長的時間

curr進程與紅黑樹中最左進程left虛擬運行時間的差值大於curr的期望運行時間ideal_runtime

此時說明紅黑樹中最左結點left與curr節點更渴望處理器, 已經接近於饑餓狀態, 這個我們可以這樣理解, 相對於curr進程來說, left進程如果參與調度, 其期望運行時間應該域curr進程的期望時間ideal_runtime相差不大, 而此時如果curr->vruntime - se->vruntime > curr.ideal_runtime, 我們可以初略的理解為curr進程已經優先於left進程多運行了一個周期, 而left又是紅黑樹總最饑渴的那個進程, 因此curr進程已經遠遠領先於隊列中的其他進程, 此時應該補償其他進程。

如果檢查需要發生搶占, 則內核通過resched_curr(rq_of(cfs_rq))設置重調度標識, 從而觸發延遲調度

2.4 resched_curr設置重調度標識TIF_NEED_RESCHED

周期性調度器並不顯式進行調度, 而是採用了延遲調度的策略, 如果發現需要搶占, 周期性調度器就設置進程的重調度標識TIF_NEED_RESCHED, 然後由主調度器完成調度工作.

TIF_NEED_RESCHED標識, 表明進程需要被調度, TIF首碼表明這是一個存儲在進程thread_info中flag欄位的一個標識信息

在內核的一些關鍵位置, 會檢查當前進程是否設置了重調度標誌TLF_NEDD_RESCHED, 如果該進程被其他進程設置了TIF_NEED_RESCHED標誌, 則函數重新執行進行調度

前面我們在check_preempt_tick中如果發現curr進程已經運行了足夠長的時間, 其他進程已經開始饑餓, 那麼我們就需要通過resched_curr來設置重調度標識TIF_NEED_RESCHED

resched_curr函數定義在kernel/sched/core.c, line 446中, 並沒有什麼複雜的工作, 其實就是通過set_tsk_need_resched(curr);函數設置重調度標識

3 總結

周期調度的工作形式上sched_class調度器類的task_tick函數完成, CFS則對應task_tick_fair函數, 但實際上工作交給entity_tick完成.

而entity_tick中則通過check_preempt_tick函數檢查是否需要搶占當前進程curr, 如果發現curr進程已經運行了足夠長的時間, 其他進程已經開始饑餓, 那麼我們就需要通過resched_curr函數來設置重調度標識TIF_NEED_RESCHED

其中check_preempt_tick檢查可搶占的條件如下

curr進程的實際運行時間delta_exec比期望的時間間隔ideal_runtime長, 此時說明curr進程已經運行了足夠長的時間
curr進程與紅黑樹中最左進程left虛擬運行時間的差值大於curr的期望運行時間ideal_runtime, 此時我們可以理解為curr進程已經優先於left進程多運行了一個周期, 而left又是紅黑樹總最饑渴的那個進程, 因此curr進程已經遠遠領先於隊列中的其他進程, 此時應該補償其他進程