linux kernel基礎系列之（一）排程原理

1. 資料結構：

• 優先級隊列

struct prio_array {

    unsigned int nr_active;    表示等待執行的程序總數

    unsigned long bitmap[BITMAP_SIZE];    一個unsigned long在核心中隻有32位哈，大家要跟64位OS上的C程式中的long區分開，那個是64位的。那麼這個bitmap是幹什麼的呢？它是用位的方式，表示某個優先級上有沒有待處理的隊列，是實作快速找到最高待處理優先程序的關鍵。如果我定義了四種優先級，我隻需要四位就能表示某個優先級上有沒有程序要運作，例如優先級是2和3上有程序，那麼就應該是0110.......非常省空間，效率也快，不是嗎？

    struct list_head queue[MAX_PRIO];     與上面的bitmap是對應的，它存儲所有等待運作的程序。

};

• 運作隊列

struct runqueue {

    spinlock_t lock;   這是個自旋鎖，nginx裡解決驚群現象時也是用這個。與普通鎖的差別就是，使用普通鎖時，你去試圖拿一把鎖，結果發現已經被别人拿走了，你就在那睡覺，等别人鎖用完了叫你起來。是以如果有一個人拿住鎖了，一百個人都在門前睡覺等。當之前的人用完鎖回來後，會叫醒所有100個等鎖的人，然後這些人開始互相搶，搶到的人拿鎖進去，其他的人繼續等。自旋鎖不同，當他去拿鎖發現鎖被别人拿走了，他在那不睡覺的等，稍打個盹就看看自己主動看看鎖有沒有還回來。大家比較出優劣了嗎？

    unsigned long nr_running;

#ifdef CONFIG_SMP

    unsigned long cpu_load;

#endif

    unsigned long long nr_switches;

    unsigned long nr_uninterruptible;

    unsigned long expired_timestamp;

    unsigned long long timestamp_last_tick;

    task_t *curr, *idle;

    struct mm_struct *prev_mm;

    prio_array_t *active, *expired, arrays[2];上面說了半天的優先級隊列在這裡，但是在runqueue裡，為什麼不隻一個呢？這個在下面講。

    int best_expired_prio;

    atomic_t nr_iowait;

    ... ...

};

Reference:

1. linux核心排程算法（1）--快速找到最高優先級程序
2. Linux 2.6 排程系統分析
3. https://elixir.bootlin.com/linux/v2.6.11/source/include/linux/sched.h
4. https://elixir.bootlin.com/linux/v2.6.11/source/kernel/sched.c