Linux核心調度器之周期性調度器scheduler_tick--Linux進程的管理與調度(十八）

我們前面提到linux有兩種方法激活調度器：核心調度器和
周期調度器

• 一種是直接的, 比如進程打算睡眠或出於其他原因放棄CPU
• 另一種是通過周期性的機制, 以固定的頻率運行, 不時的檢測是否有必要

因而內核提供了兩個調度器主調度器，周期性調度器，分別實現如上工作, 兩者合在一起就組成了核心調度器(core scheduler), 也叫通用調度器(generic scheduler).

他們都根據進程的優先順序分配CPU時間, 因此這個過程就叫做優先調度, 我們將在本節主要講解核心調度器的設計和優先調度的實現方式.

而我們的周期性調度器以固定的頻率激活負責當前進程調度類的周期性調度方法, 以保證系統的併發性

1 前景回顧

首先還是讓我們簡單回顧一下子之前的的內容

1.1 進程調度

記憶體中保存了對每個進程的唯一描述, 並通過若幹結構與其他進程連接起來.

調度器面對的情形就是這樣, 其任務是在程式之間共用CPU時間, 創造並行執行的錯覺, 該任務分為兩個不同的部分, 其中一個涉及調度策略, 另外一個涉及上下文切換.

內核必須提供一種方法, 在各個進程之間儘可能公平地共用CPU時間, 而同時又要考慮不同的任務優先順序.

調度器的一般原理是, 按所需分配的計算能力, 向系統中每個進程提供最大的公正性, 或者從另外一個角度上說, 他試圖確保沒有進程被虧待.

1.2 進程的分類

linux把進程區分為實時進程和非實時進程, 其中非實時進程進一步劃分為互動式進程和批處理進程

根據進程的不同分類Linux採用不同的調度策略.

對於實時進程，採用FIFO, Round Robin或者Earliest Deadline First (EDF)最早截止期限優先調度演算法|的調度策略.

對於普通進程則採用CFS完全公平調度器進行調度

1.3 linux調度器的演變

1.4 Linux的調度器組成

2個調度器

可以用兩種方法來激活調度

• 一種是直接的, 比如進程打算睡眠或出於其他原因放棄CPU
• 另一種是通過周期性的機制, 以固定的頻率運行, 不時的檢測是否有必要

因此當前linux的調度程式由兩個調度器組成：主調度器，周期性調度器(兩者又統稱為通用調度器(generic scheduler)或核心調度器(core scheduler))

並且每個調度器包括兩個內容：調度框架(其實質就是兩個函數框架)及調度器類

6種調度策略

linux內核目前實現了6中調度策略(即調度演算法), 用於對不同類型的進程進行調度, 或者支持某些特殊的功能

• SCHED_NORMAL和SCHED_BATCH調度普通的非實時進程
• SCHED_FIFO和SCHED_RR和SCHED_DEADLINE則採用不同的調度策略調度實時進程
• SCHED_IDLE則在系統空閑時調用idle進程.

5個調度器類

而依據其調度策略的不同實現了5個調度器類, 一個調度器類可以用一種種或者多種調度策略調度某一類進程, 也可以用於特殊情況或者調度特殊功能的進程.

其所屬進程的優先順序順序為

stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class

3個調度實體

調度器不限於調度進程, 還可以調度更大的實體, 比如實現組調度.

這種一般性要求調度器不直接操作進程, 而是處理可調度實體, 因此需要一個通用的數據結構描述這個調度實體,即seched_entity結構, 其實際上就代表了一個調度對象，可以為一個進程，也可以為一個進程組.

linux中針對當前可調度的實時和非實時進程, 定義了類型為seched_entity的3個調度實體

• sched_dl_entity 採用EDF演算法調度的實時調度實體
  sched_rt_entity
  
• 採用Roound-Robin或者FIFO演算法調度的實時調度實體 rt_sched_class
• sched_entity 採用CFS演算法調度的普通非實時進程的調度實體

2 周期性調度器

周期性調度器在scheduler_tick中實現. 如果系統正在活動中, 內核會按照頻率HZ自動調用該函數. 如果沒有近曾在等待調度, 那麼在電腦電力供應不足的情況下, 內核將關閉該調度器以減少能耗. 這對於我們的嵌入式設備或者手機終端設備的電源管理是很重要的.

2.1 周期性調度器主流程

scheduler_tick函數定義在kernel/sched/core.c, L2910中, 它有兩個主要任務

1. 更新相關統計量

管理內核中的與整個系統和各個進程的調度相關的統計量. 其間執行的主要操作是對各種計數器+1

1. 激活負責當前進程調度類的周期性調度方法

檢查進程執行的時間是否超過了它對應的ideal_runtime，如果超過了，則告訴系統，需要啟動主調度器(schedule)進行進程切換。(註意thread_info:preempt_count、thread_info:flags (TIF_NEED_RESCHED))

/*
 * This function gets called by the timer code, with HZ frequency.
 * We call it with interrupts disabled.
 */

void scheduler_tick(void)
{
    /*  1.  獲取當前cpu上的全局就緒隊列rq和當前運行的進程curr  */

    /*  1.1 在於SMP的情況下，獲得當前CPU的ID。如果不是SMP，那麼就返回0  */
    int cpu = smp_processor_id();

    /*  1.2 獲取cpu的全局就緒隊列rq, 每個CPU都有一個就緒隊列rq  */
    struct rq *rq = cpu_rq(cpu);

    /*  1.3 獲取就緒隊列上正在運行的進程curr  */
    struct task_struct *curr = rq->curr;

    sched_clock_tick();

    /*  2 更新rq上的統計信息, 並執行進程對應調度類的周期性的調度  */

    /*  加鎖 */
    raw_spin_lock(&rq->lock);

    /*  2.1 更新rq的當前時間戳.即使rq->clock變為當前時間戳  */
    update_rq_clock(rq);

    /*  2.2 執行當前運行進程所在調度類的task_tick函數進行周期性調度  */
    curr->sched_class->task_tick(rq, curr, 0);

    /*  2.3 更新rq的負載信息,  即就緒隊列的cpu_load[]數據
     *  本質是講數組中先前存儲的負荷值向後移動一個位置，
     *  將當前負荷記入數組的第一個位置 */
    update_cpu_load_active(rq);



    /*  2.4 更新cpu的active count活動計數
     *  主要是更新全局cpu就緒隊列的calc_load_update*/
    calc_global_load_tick(rq);

    /* 解鎖 */
    raw_spin_unlock(&rq->lock);

    /* 與perf計數事件相關 */
    perf_event_task_tick();

#ifdef CONFIG_SMP

     /* 當前CPU是否空閑 */
    rq->idle_balance = idle_cpu(cpu);

    /* 如果到是時候進行周期性負載平衡則觸發SCHED_SOFTIRQ */
    trigger_load_balance(rq);

#endif

    rq_last_tick_reset(rq);
}

2.2 更新統計量

2.3 激活進程所屬調度類的周期性調度器

由於調度器的模塊化結構, 主體工程其實很簡單, 在更新統計信息的同時, 內核將真正的調度工作委托給了特定的調度類方法

內核先找到了就緒隊列上當前運行的進程curr, 然後調用curr所屬調度類sched_class的周期性調度方法task_tick

即

curr->sched_class->task_tick(rq, curr, 0);

task_tick的實現方法取決於底層的調度器類, 例如完全公平調度器會在該方法中檢測是否進程已經運行了太長的時間, 以避免過長的延遲, 註意此處的做法與之前就的基於時間片的調度方法有本質區別, 舊的方法我們稱之為到期的時間片, 而完全公平調度器CFS中則不存在所謂的時間片概念.

目前我們的內核中的3個調度器類struct sched_entity, struct sched_rt_entity, 和struct sched_dl_entity dl, 我們針對當前內核中實現的調度器類分別列出其周期性調度函數task_tick

如果當前進程是完全公平隊列中的進程, 則首先根據當前就緒隊列中的進程數算出一個延遲時間間隔，大概每個進程分配2ms時間，然後按照該進程在隊列中的總權重中占得比例，算出它該執行的時間X，如果該進程執行物理時間超過了X，則激發延遲調度；如果沒有超過X，但是紅黑樹就緒隊列中下一個進程優先順序更高，即curr->vruntime-leftmost->vruntime > X,也將延遲調度

延遲調度的真正調度過程在：schedule中實現，會按照調度類順序和優先順序挑選出一個最高優先順序的進程執行

• 如果當前進程是實時調度類中的進程：則如果該進程是SCHED_RR，則遞減時間片[為HZ/10]，到期，插入到隊列尾部，並激發延遲調度，如果是SCHED_FIFO，則什麼也不做，直到該進程執行完成

如果當前進程希望被重新調度, 那麼調度類方法會在task_struct中設置TIF_NEED_RESCHED標誌, 以表示該請求, 而內核將會在接下來的適當實際完成此請求.

3 周期性調度器的激活

3.1 定時器周期性的激活調度器

定時器是Linux提供的一種定時服務的機制. 它在某個特定的時間喚醒某個進程，來做一些工作.

在低解析度定時器的每次時鐘中斷完成全局統計量更新後, 每個cpu在軟中斷中執行一下操作

• 更新該cpu上當前進程內核態、用戶態使用時間xtime_update
• 調用該cpu上的定時器函數
• 啟動周期性定時器（scheduler_tick）完成該cpu上任務的周期性調度工作；

在支持動態定時器的系統中，可以關閉該調度器，從而進入深度睡眠過程；scheduler_tick查看當前進程是否運行太長時間，如果是，將進程的TIF_NEED_RESCHED置位，然後再中斷返回時，調用schedule，進行進程切換操作

//  http://lxr.free-electrons.com/source/arch/arm/kernel/time.c?v=4.6#L74
/*
* Kernel system timer support.
*/
void timer_tick(void)
{
    profile_tick(CPU_PROFILING);
    xtime_update(1);
#ifndef CONFIG_SMP
    update_process_times(user_mode(get_irq_regs()));
#endif
}

//  http://lxr.free-electrons.com/source/kernel/time/timer.c?v=4.6#L1409
/*
 * Called from the timer interrupt handler to charge one tick to the current
 * process.  user_tick is 1 if the tick is user time, 0 for system.
 */
void update_process_times(int user_tick)
{
    struct task_struct *p = current;

    /* Note: this timer irq context must be accounted for as well. */
    account_process_tick(p, user_tick);
    run_local_timers();
    rcu_check_callbacks(user_tick);
#ifdef CONFIG_IRQ_WORK
    if (in_irq())
        irq_work_tick();
#endif
    scheduler_tick();
    run_posix_cpu_timers(p);
}

早期實現

Linux初始化時, init_IRQ()函數設定8253的定時周期為10ms(一個tick值). 同樣，在初始化時, time_init()用setup_irq()設置時間中斷向量irq0, 中斷服務程式為timer_interrupt.

在2.4版內核及較早的版本當中, 定時器的中斷處理採用底半機制, 底半處理函數的註冊在start_kernel()函數中調用sechd_init(), 在這個函數中又調用init_bh(TIMER_BH, timer_bh)註冊了定時器的底半處理函數. 然後系統才調用time_init( )來註冊定時器的中斷向量和中斷處理函數.

在中斷處理函數timer_interrupt()中，主要是調用do_timer()函數完成工作。do_timer()函數的主要功能就是調用mark_bh()產生軟中斷，隨後處理器會在合適的時候調用定時器底半處理函數timer_bh()。在timer_bh()中, 實現了更新定時器的功能. 2.4.23版的do_timer()函數代碼如下（經過簡略）：

void do_timer(struct pt_regs *regs)
{
       (*(unsigned long *)&jiffies)++;
       update_process_times(user_mode(regs));
       mark_bh(TIMER_BH);
}

而在內核2.6版本以後，定時器中斷處理採用了軟中斷機制而不是底半機制。時鐘中斷處理函數仍然為timer_interrup()-> do_timer_interrupt()-> do_timer_interrupt_hook()-> do_timer()。不過do_timer()函數的實現有所不同

void do_timer(struct pt_regs *regs)
{
       jiffies_64++;
       update_process_times(user_mode(regs));
       update_times();
}

更詳細的實現linux-2.6

Linux中斷處理之時鐘中斷（一）

（原創）linux內核進程調度以及定時器實現機制

進程管理與調度5 – 進程調度、進程切換原理詳解