Linux進程核心調度器之主調度器schedule--Linux進程的管理與調度(十九）

主調度器

在內核中的許多地方, 如果要將CPU分配給與當前活動進程不同的另一個進程, 都會直接調用主調度器函數schedule, 從系統調用返回後, 內核也會檢查當前進程是否設置了重調度標誌TLF_NEDD_RESCHED

例如, 前述的周期性調度器的scheduler_tick就會設置該標誌, 如果是這樣則內核會調用schedule, 該函數假定當前活動進程一定會被另一個進程取代.

1.1 調度函數的__sched首碼
在詳細論述schedule之前, 需要說明一下__sched首碼, 該首碼可能用於調用schedule的函數, 包括schedule本身.

__sched首碼的聲明, 在include/linux/sched.h, L416, 如下所示

/* Attach to any functions which should be ignored in wchan output. */
#define __sched         __attribute__((__section__(".sched.text")))

attribute((_section(“…”)))是一個gcc的編譯屬性, 其目的在於將相關的函數的代碼編譯之後, 放到目標文件的以惡搞特定的段內, 即.sched.text中. 該信息使得內核在顯示棧轉儲活類似信息時, 忽略所有與調度相關的調用. 由於調度哈書調用不是普通代碼流程的一部分, 因此在這種情況下是沒有意義的.

用它修飾函數的方式如下

void __sched some_function(args, ...)
{
    ......
    schedule();
    ......
}

1.2 schedule函數

schedule就是主調度器的函數, 在內核中的許多地方, 如果要將CPU分配給與當前活動進程不同的另一個進程, 都會直接調用主調度器函數schedule.

該函數完成如下工作

1. 確定當前就緒隊列, 併在保存一個指向當前(仍然)活動進程的task_struct指針
2. 檢查死鎖, 關閉內核搶占後調用__schedule完成內核調度
3. 恢復內核搶占, 然後檢查當前進程是否設置了重調度標誌TLF_NEDD_RESCHED, 如果該進程被其他進程設置了TIF_NEED_RESCHED標誌, 則函數重新執行進行調度

該函數定義在kernel/sched/core.c, L3243, 如下所示

asmlinkage __visible void __sched schedule(void)
{

    /*  獲取當前的進程  */
    struct task_struct *tsk = current;

    /*  避免死鎖 */
    sched_submit_work(tsk);
    do {
        preempt_disable();                                  /*  關閉內核搶占  */
        __schedule(false);                                  /*  完成調度  */
        sched_preempt_enable_no_resched();                  /*  開啟內核搶占  */
    } while (need_resched());   /*  如果該進程被其他進程設置了TIF_NEED_RESCHED標誌，則函數重新執行進行調度    */
}
EXPORT_SYMBOL(schedule);

1.2.2 sched_submit_work避免死鎖

該函數定義在kernel/sched/core.c, L3231, 如下所示

static inline void sched_submit_work(struct task_struct *tsk)
{
    /*  檢測tsk->state是否為0 （runnable）, 若為運行態時則返回，
     *   tsk_is_pi_blocked(tsk),檢測tsk的死鎖檢測器是否為空，若非空的話就return
    if (!tsk->state || tsk_is_pi_blocked(tsk))
        return;
    /*
     * If we are going to sleep and we have plugged IO queued,
     * make sure to submit it to avoid deadlocks.
     */
    if (blk_needs_flush_plug(tsk))  /*  然後檢測是否需要刷新plug隊列，用來避免死鎖  */
        blk_schedule_flush_plug(tsk);
}

1.2.3 preempt_disable和sched_preempt_enable_no_resched開關內核搶占

內核搶占

Linux除了內核態外還有用戶態。用戶程式的上下文屬於用戶態，系統調用和中斷處理常式上下文屬於內核態. 如果一個進程在用戶態時被其他進程搶占了COU則成發生了用戶態搶占, 而如果此時進程進入了內核態, 則內核此時代替進程執行, 如果此時發了搶占, 我們就說發生了內核搶占.

內核搶占是Linux 2.6以後引入的一個重要的概念

我們說：如果進程正執行內核函數時，即它在內核態運行時，允許發生內核切換(被替換的進程是正執行內核函數的進程)，這個內核就是搶占的。

搶占內核的主要特點是：一個在內核態運行的進程，當且僅當在執行內核函數期間被另外一個進程取代。

這與用戶態的搶占有本質區別.

內核為了支撐內核搶占, 提供了很多機制和結構, 必要時候開關內核搶占也是必須的, 這些函數定義在include/linux/preempt.h, L145

#define preempt_disable() \
do { \
    preempt_count_inc(); \
    barrier(); \
} while (0)

#define sched_preempt_enable_no_resched() \
do { \
    barrier(); \
    preempt_count_dec(); \
} while (0)

1.3 __schedule開始進程調度

__schedule完成了真正的調度工作, 其定義在kernel/sched/core.c, L3103, 如下所示

1.3.1 __schedule函數主框架

static void __sched notrace __schedule(bool preempt)
{
    struct task_struct *prev, *next;
    unsigned long *switch_count;
    struct rq *rq;
    int cpu;

    /*  ==1==  
        找到當前cpu上的就緒隊列rq
        並將正在運行的進程curr保存到prev中  */
    cpu = smp_processor_id();
    rq = cpu_rq(cpu);
    prev = rq->curr;

    /*
     * do_exit() calls schedule() with preemption disabled as an exception;
     * however we must fix that up, otherwise the next task will see an
     * inconsistent (higher) preempt count.
     *
     * It also avoids the below schedule_debug() test from complaining
     * about this.
     */
    if (unlikely(prev->state == TASK_DEAD))
        preempt_enable_no_resched_notrace();

    /*  如果禁止內核搶占，而又調用了cond_resched就會出錯
     *  這裡就是用來捕獲該錯誤的  */
    schedule_debug(prev);

    if (sched_feat(HRTICK))
        hrtick_clear(rq);

    /*  關閉本地中斷  */
    local_irq_disable();

    /*  更新全局狀態，
     *  標識當前CPU發生上下文的切換  */
    rcu_note_context_switch();

    /*
     * Make sure that signal_pending_state()->signal_pending() below
     * can't be reordered with __set_current_state(TASK_INTERRUPTIBLE)
     * done by the caller to avoid the race with signal_wake_up().
     */
    smp_mb__before_spinlock();
    /*  鎖住該隊列  */
    raw_spin_lock(&rq->lock);
    lockdep_pin_lock(&rq->lock);

    rq->clock_skip_update <<= 1; /* promote REQ to ACT */

    /*  切換次數記錄, 預設認為非主動調度計數(搶占)  */
    switch_count = &prev->nivcsw;

    /*
     *  scheduler檢查prev的狀態state和內核搶占表示
     *  如果prev是不可運行的, 並且在內核態沒有被搶占
     *  
     *  此時當前進程不是處於運行態, 並且不是被搶占
     *  此時不能只檢查搶占計數
     *  因為可能某個進程(如網卡輪詢)直接調用了schedule
     *  如果不判斷prev->stat就可能誤認為task進程為RUNNING狀態
     *  到達這裡，有兩種可能，一種是主動schedule, 另外一種是被搶占
     *  被搶占有兩種情況, 一種是時間片到點, 一種是時間片沒到點
     *  時間片到點後, 主要是置當前進程的need_resched標誌
     *  接下來在時鐘中斷結束後, 會preempt_schedule_irq搶占調度
     *  
     *  那麼我們正常應該做的是應該將進程prev從就緒隊列rq中刪除, 
     *  但是如果當前進程prev有非阻塞等待信號, 
     *  並且它的狀態是TASK_INTERRUPTIBLE
     *  我們就不應該從就緒隊列總刪除它 
     *  而是配置其狀態為TASK_RUNNING, 並且把他留在rq中

    /*  如果內核態沒有被搶占, 並且內核搶占有效
        即是否同時滿足以下條件：
        1  該進程處於停止狀態
        2  該進程沒有在內核態被搶占 */
    if (!preempt && prev->state)
    {

        /*  如果當前進程有非阻塞等待信號，並且它的狀態是TASK_INTERRUPTIBLE  */
        if (unlikely(signal_pending_state(prev->state, prev)))
        {
            /*  將當前進程的狀態設為：TASK_RUNNING  */
            prev->state = TASK_RUNNING;
        }
        else   /*  否則需要將prev進程從就緒隊列中刪除*/
        {
            /*  將當前進程從runqueue(運行隊列)中刪除  */
            deactivate_task(rq, prev, DEQUEUE_SLEEP);

            /*  標識當前進程不在runqueue中  */
            prev->on_rq = 0;

            /*
             * If a worker went to sleep, notify and ask workqueue
             * whether it wants to wake up a task to maintain
             * concurrency.
             */
            if (prev->flags & PF_WQ_WORKER) {
                struct task_struct *to_wakeup;

                to_wakeup = wq_worker_sleeping(prev);
                if (to_wakeup)
                    try_to_wake_up_local(to_wakeup);
            }
        }
        /*  如果不是被搶占的，就累加主動切換次數  */
        switch_count = &prev->nvcsw;
    }

    /*  如果prev進程仍然在就緒隊列上沒有被刪除  */
    if (task_on_rq_queued(prev))
        update_rq_clock(rq);  /*  跟新就緒隊列的時鐘  */

    /*  挑選一個優先順序最高的任務將其排進隊列  */
    next = pick_next_task(rq, prev);
    /*  清除pre的TIF_NEED_RESCHED標誌  */
    clear_tsk_need_resched(prev);
    /*  清楚內核搶占標識  */
    clear_preempt_need_resched();

    rq->clock_skip_update = 0;

    /*  如果prev和next非同一個進程  */
    if (likely(prev != next))
    {
        rq->nr_switches++;  /*  隊列切換次數更新  */
        rq->curr = next;    /*  將next標記為隊列的curr進程  */
        ++*switch_count;    /* 進程切換次數更新  */

        trace_sched_switch(preempt, prev, next);
        /*  進程之間上下文切換    */
        rq = context_switch(rq, prev, next); /* unlocks the rq */
    }
    else    /*  如果prev和next為同一進程，則不進行進程切換  */
    {
        lockdep_unpin_lock(&rq->lock);
        raw_spin_unlock_irq(&rq->lock);
    }

    balance_callback(rq);
}
STACK_FRAME_NON_STANDARD(__schedule); /* switch_to() */

1.3.2 pick_next_task選擇搶占的進程

內核從cpu的就緒隊列中選擇一個最合適的進程來搶占CPU

next = pick_next_task(rq);

全局的pick_next_task函數會從按照優先順序遍歷所有調度器類的pick_next_task函數, 去查找最優的那個進程, 當然因為大多數情況下, 系統中全是CFS調度的非實時進程, 因而linux內核也有一些優化的策略

其執行流程如下

• 如果當前cpu上所有的進程都是cfs調度的普通非實時進程, 則直接用cfs調度, 如果無程式可調度則調度idle進程

其定義在kernel/sched/core.c, line 3068, 如下所示

/*
 * Pick up the highest-prio task:
 */
static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev)
{
    const struct sched_class *class = &fair_sched_class;
    struct task_struct *p;

    /*
     * Optimization: we know that if all tasks are in
     * the fair class we can call that function directly:
     *
     * 如果待被調度的進程prev是隸屬於CFS的普通非實時進程
     * 而當前cpu的全局就緒隊列rq中的進程數與cfs_rq的進程數相等
     * 則說明當前cpu上的所有進程都是由cfs調度的普通非實時進程
     *
     * 那麼我們選擇最優進程的時候
     * 就只需要調用cfs調度器類fair_sched_class的選擇函數pick_next_task
     * 就可以找到最優的那個進程p
     */
    /*  如果當前所有的進程都被cfs調度, 沒有實時進程  */
    if (likely(prev->sched_class == class &&
           rq->nr_running == rq->cfs.h_nr_running))
    {
        /*  調用cfs的選擇函數pick_next_task找到最優的那個進程p*/
        p = fair_sched_class.pick_next_task(rq, prev);
        /*  #define RETRY_TASK ((void *)-1UL)有被其他調度氣找到合適的進程  */
        if (unlikely(p == RETRY_TASK))
            goto again; /*  則遍歷所有的調度器類找到最優的進程 */

        /* assumes fair_sched_class->next == idle_sched_class */
        if (unlikely(!p))   /*  如果沒有進程可被調度  */
            p = idle_sched_class.pick_next_task(rq, prev); /*  則調度idle進程  */

        return p;
    }

/*  進程中所有的調度器類, 是通過next域鏈接域鏈接在一起的
 *  調度的順序為stop -> dl -> rt -> fair -> idle 
 *  again出的迴圈代碼會遍歷他們找到一個最優的進程  */
again:
    for_each_class(class)
    {
        p = class->pick_next_task(rq, prev);
        if (p)
        {
            if (unlikely(p == RETRY_TASK))
                goto again;
            return p;
        }
    }

    BUG(); /* the idle class will always have a runnable task */
}

其中for_each_class遍歷所有的調度器類, 依次執行pick_next_task操作選擇最優的進程

它會從優先順序最高的sched_class_highest(目前是stop_sched_class)查起, 依次按照調度器類的優先順序從高到低的順序調用調度器類對應的pick_next_task_fair函數直到查找到一個能夠被調度的進程

for_each_class定義在kernel/sched/sched.h, 如下所示

#define sched_class_highest (&stop_sched_class)
#define for_each_class(class) \
   for (class = sched_class_highest; class; class = class->next)

extern const struct sched_class stop_sched_class;
extern const struct sched_class dl_sched_class;
extern const struct sched_class rt_sched_class;
extern const struct sched_class fair_sched_class;
extern const struct sched_class idle_sched_class;

除了全局的pick_next_task函數, 每個調度器類都提供了pick_next_task函數用以查找對應調度器下的最優進程, 其定義如下所示

實際上，對於RT進程，put和pick並不操作運行隊列

對於FIFO和RR的區別，在scheduler_tick中通過curr->sched_class->task_tick進入到task_tick_rt的處理, 如果是非RR的進程則直接返回，否則遞減時間片，如果時間片耗完，則需要將當前進程放到運行隊列的末尾, 這個時候才操作運行隊列（FIFO和RR進程，是否位於同一個plist隊列？），時間片到點，會重新移動當前進程requeue_task_rt，進程會被加到隊列尾，接下來set_tsk_need_resched觸發調度，進程被搶占進入schedule

問題1 : 為什麼要多此一舉判斷所有的進程是否全是cfs調度的普通非實時進程?

加快經常性事件, 是程式開發中一個優化的準則, 那麼linux系統中最普遍的進程是什麼呢? 肯定是非實時進程啊, 其調度器必然是cfs, 因此

rev->sched_class == class && rq->nr_running == rq->cfs.h_nr_running

這種情形發生的概率是很大的, 也就是說多數情形下, 我們的linux中進程全是cfs調度的

而likely這個巨集業表明瞭這點, 這也是gcc內建的一個編譯選項, 它其實就是告訴編譯器表達式很大的情況下為真, 編譯器可以對此做出優化

//  http://lxr.free-electrons.com/source/tools/virtio/linux/kernel.h?v=4.6#L91
 #ifndef likely
 # define likely(x)     (__builtin_expect(!!(x), 1))
 #endif

 #ifndef unlikely
 # define unlikely(x)   (__builtin_expect(!!(x), 0))
 #endif

1.4 context_switch進程上下文切換

進程上下文的切換其實是一個很複雜的過程, 我們在這裡不能詳述, 但是我會儘可能說明白

具體的內容請參照

1.4.1 進程上下文切換

上下文切換(有時也稱做進程切換或任務切換)是指CPU從一個進程或線程切換到另一個進程或線程

稍微詳細描述一下，上下文切換可以認為是內核（操作系統的核心）在 CPU 上對於進程（包括線程）進行以下的活動：

1. 掛起一個進程，將這個進程在 CPU 中的狀態（上下文）存儲於記憶體中的某處，
2. 在記憶體中檢索下一個進程的上下文並將其在 CPU 的寄存器中恢復
3. 跳轉到程式計數器所指向的位置（即跳轉到進程被中斷時的代碼行），以恢復該進程

因此上下文是指某一時間點CPU寄存器和程式計數器的內容, 廣義上還包括記憶體中進程的虛擬地址映射信息.

上下文切換隻能發生在內核態中, 上下文切換通常是計算密集型的。也就是說，它需要相當可觀的處理器時間，在每秒幾十上百次的切換中，每次切換都需要納秒量級的時間。所以，上下文切換對系統來說意味著消耗大量的 CPU 時間，事實上，可能是操作系統中時間消耗最大的操作。

Linux相比與其他操作系統（包括其他類 Unix 系統）有很多的優點，其中有一項就是，其上下文切換和模式切換的時間消耗非常少.

1.4.2 context_switch流程

context_switch函數完成了進程上下文的切換, 其定義在kernel/sched/core.c#L2711

context_switch( )函數建立next進程的地址空間。進程描述符的active_mm欄位指向進程所使用的記憶體描述符，而mm欄位指向進程所擁有的記憶體描述符。對於一般的進程，這兩個欄位有相同的地址，但是，內核線程沒有它自己的地址空間而且它的 mm欄位總是被設置為 NULL

context_switch( )函數保證：如果next是一個內核線程, 它使用prev所使用的地址空間

它主要執行如下操作

• 調用switch_mm(), 把虛擬記憶體從一個進程映射切換到新進程中
• 調用switch_to(),從上一個進程的處理器狀態切換到新進程的處理器狀態。這包括保存、恢復棧信息和寄存器信息

由於不同架構下地址映射的機制有所區別, 而寄存器等信息弊病也是依賴於架構的, 因此switch_mm和switch_to兩個函數均是體繫結構相關的

1.4.3 switch_mm切換進程虛擬地址空間

switch_mm主要完成了進程prev到next虛擬地址空間的映射, 由於內核虛擬地址空間是不許切換的, 因此切換的主要是用戶態的虛擬地址空間

這個是一個體繫結構相關的函數, 其實現在對應體繫結構下的arch/對應體繫結構/include/asm/mmu_context.h文件中, 我們下麵列出了幾個常見體繫結構的實現

其主要工作就是切換了進程的CR3

控制寄存器（CR0～CR3）用於控制和確定處理器的操作模式以及當前執行任務的特性

CR0中含有控制處理器操作模式和狀態的系統控制標誌；

CR1保留不用；

CR2含有導致頁錯誤的線性地址；

CR3中含有頁目錄表物理記憶體基地址，因此該寄存器也被稱為頁目錄基地址寄存器PDBR（Page-Directory Base address Register）。

1.4.4 switch_to切換進程堆棧和寄存器

執行環境的切換是在switch_to()中完成的, switch_to完成最終的進程切換，它保存原進程的所有寄存器信息，恢復新進程的所有寄存器信息，並執行新的進程

調度過程可能選擇了一個新的進程, 而清理工作則是針對此前的活動進程, 請註意, 這不是發起上下文切換的那個進程, 而是系統中隨機的某個其他進程, 內核必須想辦法使得進程能夠與context_switch常式通信, 這就可以通過switch_to巨集實現. 因此switch_to函數通過3個參數提供2個變數,

在新進程被選中時, 底層的進程切換冽程必須將此前執行的進程提供給context_switch, 由於控制流會回到陔函數的中間, 這無法用普通的函數返回值來做到, 因此提供了3個參數的巨集

/*
 * Saving eflags is important. It switches not only IOPL between tasks,
 * it also protects other tasks from NT leaking through sysenter etc.
*/
#define switch_to(prev, next, last)

內核在switch_to中執行如下操作

1. 進程切換, 即esp的切換, 由於從esp可以找到進程的描述符
2. 硬體上下文切換, 設置ip寄存器的值, 並jmp到__switch_to函數

1.5 need_resched, TIF_NEED_RESCHED標識與用戶搶占

1.5.1 need_resched標識TIF_NEED_RESCHED

內核在即將返回用戶空間時檢查進程是否需要重新調度，如果設置了，就會發生調度, 這被稱為用戶搶占, 因此內核在thread_info的flag中設置了一個標識來標誌進程是否需要重新調度, 即重新調度need_resched標識TIF_NEED_RESCHED

並提供了一些設置可檢測的函數

// http://lxr.free-electrons.com/source/include/linux/sched.h?v=4.6#L3093
static __always_inline bool need_resched(void)
{
    return unlikely(tif_need_resched());
}

// http://lxr.free-electrons.com/source/include/linux/thread_info.h?v=4.6#L106
#define tif_need_resched() test_thread_flag(TIF_NEED_RESCHED)

1.5.2 用戶搶占和內核搶占

當內核即將返回用戶空間時, 內核會檢查need_resched是否設置，如果設置，則調用schedule()，此時，發生用戶搶占。

一般來說，用戶搶占發生幾下情況

1. 從系統調用返回用戶空間
2. 從中斷(異常)處理程式返回用戶空間

當kerne(系統調用或者中斷都在kernel中)返回用戶態時，系統可以安全的執行當前的任務，或者切換到另外一個任務.

搶占時伴隨著schedule()的執行, 因此內核提供了一個TIF_NEED_RESCHED標誌來表明是否要用schedule()調度一次

根據搶占發生的時機分為用戶搶占和內核搶占。

用戶搶占發生在內核即將返回到用戶空間的時候。內核搶占發生在返回內核空間的時候。

2 總結

2.1 schedule調度流程

schedule就是主調度器的函數, 在內核中的許多地方, 如果要將CPU分配給與當前活動進程不同的另一個進程, 都會直接調用主調度器函數schedule, 該函數定義在kernel/sched/core.c, L3243, 如下所示

該函數完成如下工作

1. 確定當前就緒隊列, 併在保存一個指向當前(仍然)活動進程的task_struct指針
2. 檢查死鎖, 關閉內核搶占後調用__schedule完成內核調度
3. 恢復內核搶占, 然後檢查當前進程是否設置了重調度標誌TLF_NEDD_RESCHED, 如果該進程被其他進程設置了TIF_NEED_RESCHED標誌, 則函數重新執行進行調度

do {
        preempt_disable();                                  /*  關閉內核搶占  */
        __schedule(false);                                  /*  完成調度  */
        sched_preempt_enable_no_resched();                  /*  開啟內核搶占  */
    } while (need_resched());   /*  如果該進程被其他進程設置了TIF_NEED_RESCHED標誌，則函數重新執行進行調度    */

2.2 __schedule如何完成內核搶占

1. 完成一些必要的檢查, 並設置進程狀態, 處理進程所在的就緒隊列
2. 調度全局的pick_next_task選擇搶占的進程
   1. 如果當前cpu上所有的進程都是cfs調度的普通非實時進程, 則直接用cfs調度, 如果無程式可調度則調度idle進程
   2. 否則從優先順序最高的調度器類sched_class_highest(目前是stop_sched_class)開始依次遍歷所有調度器類的pick_next_task函數, 選擇最優的那個進程執行
3. context_switch完成進程上下文切換
   1. 調用switch_mm(), 把虛擬記憶體從一個進程映射切換到新進程中
   2. 調用switch_to(),從上一個進程的處理器狀態切換到新進程的處理器狀態。這包括保存、恢復棧信息和寄存器信息

2.3 調度的內核搶占和用戶搶占

內核在完成調度的過程中總是先關閉內核搶占, 等待內核完成調度的工作後, 再把內核搶占開啟, 如果在內核完成調度器過程中, 這時候如果發生了內核搶占, 我們的調度會被中斷, 而調度卻還沒有完成, 這樣會丟失我們調度的信息.

而同樣我們可以看到, 在調度完成後, 內核會去判斷need_resched條件, 如果這個時候為真, 內核會重新進程一次調度, 此次調度由於發生在內核態因此仍然是一次內核搶占

need_resched條件其實是判斷need_resched標識TIF_NEED_RESCHED的值, 內核在thread_info的flag中設置了一個標識來標誌進程是否需要重新調度, 即重新調度need_resched標識TIF_NEED_RESCHED, 內核在即將返回用戶空間時會檢查標識TIF_NEED_RESCHED標誌進程是否需要重新調度，如果設置了，就會發生調度, 這被稱為用戶搶占,

而內核搶占是通過自旋鎖preempt_count實現的, 同樣當內核可以進行內核搶占的時候(比如從中斷處理程式返回內核空間或內核中的進程被堵塞的時候)，內核會檢查preempt_count和TIF_NEED_RESCHED標誌，如果進程設置了 TIF_NEED_RESCHED標誌,並且preempt_count為0，發生內核搶占