[linux]程序（五）——程序排程（實時程序排程）

點選打開連結

1，實時程序和普通程序排程的差别

實時程序需要嚴格按照優先級的順序執行，比如在八核平台上，必須是優先級最高的八個程序得到排程，如果此時八個優先級最高的程序都在某一個cpu的rt隊列上，那麼此時的排程就會涉及到了程序在不同cpu的遷移。

2，實時排程算法概述

該實時排程器主要為了解決以下四種情況：

（1）. 在喚醒任務時，待喚醒的任務放置到哪個運作隊列最合适（這裡稱為pre-balance）；

（2）. 新喚醒任務的優先級比某個運作隊列的目前任務更低時，怎麼處理這個更低優先級任務；

（3）. 新喚醒任務的優先級比同一運作隊列的某個任務更高時，并且搶占了該低優先級任務，該低優先級任務怎麼處理？

（4）. 當某個任務降低自身優先級，導緻原來更低優先級任務相比之下具有更高優先級，這種情況怎麼處理。

對于情況2和情況3，實時排程器采用push操作。push操作從根域中所有運作隊列中挑選一個運作隊列（一個cpu對應一個運作隊列），該運作隊列的優先級比待push任務的優先級更低。運作隊列的優先級是指該運作隊列上所有任務的最高優先級。

對于情況4，實時排程器采用pull操作。當某個運作隊列上準備排程時，候選任務比目前任務的優先級更低時，實時排程器檢查其他運作隊列，确定是否可以pull更高優先級任務到本運作隊列。還有，當某個運作隊列上發生排程時，該運作隊列上沒有任務比目前任務優先級高，實時排程器執行pull操作，從其他運作隊列中pull更高優先級任務到本運作隊列。

每CPU變量運作隊列rq，包含一個rt_rq資料結構。rt_rq結構體主要内容如下：

struct rt_rq {
    struct rt_prio_array  active;
    ...
    unsigned long         rt_nr_running;         // 可運作實時任務個數
    unsigned long         rt_nr_migratory;       // 該運作隊列上可以遷移到其他運作隊列的實時任務個數
    unsigned long         rt_nr_uninterruptible;
    int                   highest_prio;
    int                   overloaded;
};
           

實時任務優先級範圍為0到99。這些實時任務組織成優先級索引數組active，該優先級數組的資料結構類型為rt_prio_arry。rt_prio_arry資料結構由兩部分組成，一部分是位圖，

另一部分是數組。

struct rt_prio_arry {
    unsigned long bitmap[BITS_TO_LONGS(MAX_RT_PRIO+1)];
    struct list_head queue[MAX_RT_PRIO]；
}
           

3,根域的概念

cpusets提供了一種機制，cpusets可以将部分CPU劃入一個子集合，這個CPU子集供某個任務或者某個任務組使用。各個cpusets之間可以重疊，如果某個cpuset與其他cpuset沒有重複CPU，那麼将該cpuset稱為獨立的。每個獨立的cpuset定義為一個孤立的域（根域）。與根域有關的資訊儲存在資料結構root_domain中。

struct root_domain {
    atomic_t   refcount;  /* reference count for the domain */
    cpumask_t  span;      /* span of member cpus of the domain*/
    cpumask_t  online;    /* number of online cpus in the domain*/
    cpumask_t  rto_mask;  /* mask of overloaded cpus in the domain*/
    atomic_t   rto_count; /* number of overloaded cpus */
   ....
};
           

4，cpu的優先級管理

每個CPU可以處于如下任何一種狀态：INVALID，IDLE，NORMAL，RT1，．．．，RT99，處于INVALID狀态的CPU不适合任務路由。系統使用2維位圖來維護這些狀态資訊。第1個位圖用于處于同一優先級的不同CPU，CPU優先級是指rt_rq結構中的highest_prio變量；第2個位圖用于不同的優先級。

#define CPUPRI_NR_PRIORITIES (MAX_RT_PRIO + 2)
struct cpupri {
    struct cpupri_vec  pri_to_cpu[CPUPRI_NR_PRIORITIES];     //pri_to_cpu位圖可以快速找到優先級最低的cpu集合
    int                cpu_to_pri[NR_CPUS]; // 各個cpu對應優先級
};
           

5,push和pull算法

push算法

push_rt_task - 把目前run_queue中多餘的實時程序推給其他run_queue。需要滿足以下條件：

1、每次push一個程序，這個程序的優先級在目前run_queue中是第二高的（優先級最高的程序必定正在運作，不需要移動）；

2、目标run_queue上正在運作的不是實時程序（是普通程序），或者是top-N中優先級最低的實時程序，且優先級低于被push的程序；

3、被push的程序允許在目标CPU上運作（沒有親和性限制）；

4、滿足條件的目标run_queue可能存在多個（可能多個CPU上都沒有實時程序在運作），應該選擇與目前CPU最具親緣性的一組CPU中的第一個CPU所對應的run_queue作為push的目标（順着sched_domain--排程域--逐漸往上，找到第一個包含目标CPU的sched_domain。見後面關于sched_domain的描述）；

該函數會在以下時間點被調用：

1、非正在運作的普通程序變成實時程序時（比如通過sched_setscheduler系統調用）；

2、發生排程之後（這時候可能有一個實時程序被更高優先級的實時程序搶占了）；

3、實時程序被喚醒之後，如果不能馬上在目前CPU上運作（它不是目前CPU上優先級最高的程序）；

pull算法

pull_rt_task - 把其他CPU的run_queue中的實時程序pull過來，放到目前CPU的run_queue中。被pull過來的實時程序要滿足以下條件：

1、程序是其所在的run_queue中優先級第二高的（優先級最高的程序必定正在運作，不需要移動）；

2、程序的優先級比目前run_queue中最高優先級的程序還要高；

3、程序允許在目前CPU上運作（沒有親和性限制）；

該函數會在以下時間點被調用：

1、發生排程之前，如果prev程序（将要被替換下去的程序）是實時程序，且優先級高于目前run_queue中優先級最高的實時程序（這說明prev程序已經離開TASK_RUNNING狀态了，否則它不會讓位于比它優先級低的程序）；

2、正在運作的實時程序優先級被調低時（比如通過sched_setparam系統調用）；

3、正在運作的實時程序變成普通程序時（比如通過sched_setscheduler系統調用）；