[Scheduler] More Detail In Scheduler

專門用語：

• 使用打字機（Courier New）字體表示原始碼。
• task/process即為Linux中的thread。
• 文中的Linux與Linux kernel指的皆為作業系統核心。
  
• 使用斜體字型標示Linux中的資料結構，macro，變數或函式名稱。
• PID即為TID。
  

Kernel版本：

• v2.6.24.3
  

我們在上一篇¹提到2.6.24.3以後版本的scheduler永遠將cfs_rq rb-tree²中最左邊的node挑出來成為current task，而kernel是依據每個task的vruntime大小決定該task在cfs_rq rb-tree中的位置。最後發現不論是task的vruntime或是單次執行時間長度都與task的load欄位³有密切的關係，因此決定再花一篇的篇幅解釋load究竟是何方神聖。

之前所提到的load其實是個內含integer type的weight與inv_weight的structure，一般狀況下weight與inv_weight分別來自於prio_to_weight與prio_to_wmult兩個integer array，也可以稱這兩個array為對照表（look-up table），若是遇到task為real-time task或是idle task，kernel便直接將weight與inv_weight設定為某固定值，實際上替task取得load參數的函式為set_load_weight。

static void set_load_weight(struct task_struct *p)
{
        if (task_has_rt_policy(p)) {
                p->se.load.weight = prio_to_weight[0] * 2;
                p->se.load.inv_weight = prio_to_wmult[0] >> 1;
                return;
        }

        /*
         * SCHED_IDLE tasks get minimal weight:
         */
        if (p->policy == SCHED_IDLE) {
                p->se.load.weight = WEIGHT_IDLEPRIO;
                p->se.load.inv_weight = WMULT_IDLEPRIO;
                return;
        }

        p->se.load.weight = prio_to_weight[p->static_prio - MAX_RT_PRIO];
        p->se.load.inv_weight = prio_to_wmult[p->static_prio - MAX_RT_PRIO];
}

當task為一般task時，它的load便取決於它的static priority，顧名思義static priority通常在建立task的時候就設定好，位於100與140之間⁴，一般預設為120⁵。在已知MAX_RT_PRIO被設定為100的情況下，得知task的static priority之後便可以利用對照表取得weight與inv_weight，weight與inv_weight相乘後約為2^32⁶，prio_to_weight array中的數字則是新版scheduler中少見的magic number。

static const int prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};

static const u32 prio_to_wmult[40] = {
 /* -20 */     48388,     59856,     76040,     92818,    118348,
 /* -15 */    147320,    184698,    229616,    287308,    360437,
 /* -10 */    449829,    563644,    704093,    875809,   1099582,
 /*  -5 */   1376151,   1717300,   2157191,   2708050,   3363326,
 /*   0 */   4194304,   5237765,   6557202,   8165337,  10153587,
 /*   5 */  12820798,  15790321,  19976592,  24970740,  31350126,
 /*  10 */  39045157,  49367440,  61356676,  76695844,  95443717,
 /*  15 */ 119304647, 148102320, 186737708, 238609294, 286331153,
};

看完load的由來之後我們知道kernel schedules tasks與決定每個task單次執行時間長度的主要依據為task的static priority與目前在runqueue的task數（cfs_rq->nr_running）。當runqueue中task數小於或等於5⁷時，task的priority與單次執行時間長度僅受task的static priority影響，當runqueue中的task數大於5時，則runqueue中的task數也成為影響因素之一。

static u64 __sched_period(unsigned long nr_running)
{
        u64 period = sysctl_sched_latency;

        unsigned long nr_latency = sched_nr_latency;

        if (unlikely(nr_running > nr_latency)) {
                period *= nr_running;
                do_div(period, nr_latency);
        }

        return period;
}

1 http://memyselfandtaco.blogspot.com/2008/07/scheduler-behind-scene.html
2 red-black tree（紅黑樹）。
3 load其實是在task_struct中sched_entity裡的欄位。
4 數字越小優先權越高，0~99為real-time task的priority範圍。
5 nice的範圍為-20到20的典故便由此而來。
6 整數運算自動刪除小數位。
7 又是一個magic number。