Process Scheduling - 2

• run queue

Linux 核心將所有可執行的行程(其狀態為 TASK_RUNNING)記錄於 run queue 之中，除了 swapper 行程。
若是多處理器的系統，則每一個 CPU 會有自己的 run queue 變數。

定義於 kernel/sched.c

struct prio_array {
　　unsigned int nr_active;
　　unsigned long bitmap[BITMAP_SIZE];
　　struct list_head queue[MAX_PRIO];
};

struct runqueue {
　　spinlock_t lock;
　　
　　/*
　　 * nr_running and cpu_load should be in the same cacheline because
　　 * remote CPUs use both these fields when doing load calculation.
　　 */
　　unsigned long nr_running;
#ifdef CONFIG_SMP
　　unsigned long cpu_load;
#endif
　　unsigned long long nr_switches;

　　/*
　　 * This is part of a global counter where only the total sum
　　 * over all CPUs matters. A task can increase this counter on
　　 * one CPU and if it got migrated afterwards it may decrease
　　 * it on another CPU. Always updated under the runqueue lock:
　　 */
　　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];
　　int best_expired_prio;
　　atomic_t nr_iowait;

#ifdef CONFIG_SMP
　　struct sched_domain *sd;
　　
　　/* For active balancing */
　　int active_balance;
　　int push_cpu;
　　
　　task_t *migration_thread;
　　struct list_head migration_queue;
#endif


#ifdef CONFIG_SCHEDSTATS
　　/* latency stats */
　　struct sched_info rq_sched_info;
　　
　　/* sys_sched_yield() stats */
　　unsigned long yld_exp_empty;
　　unsigned long yld_act_empty;
　　unsigned long yld_both_empty;
　　unsigned long yld_cnt;
　　
　　/* schedule() stats */
　　unsigned long sched_noswitch;
　　unsigned long sched_switch;
　　unsigned long sched_cnt;
　　unsigned long sched_goidle;
　　
　　/* pull_task() stats */
　　unsigned long pt_gained[MAX_IDLE_TYPES];
　　unsigned long pt_lost[MAX_IDLE_TYPES];
　　
　　/* active_load_balance() stats */
　　unsigned long alb_cnt;
　　unsigned long alb_lost;
　　unsigned long alb_gained;
　　unsigned long alb_failed;
　　
　　/* try_to_wake_up() stats */
　　unsigned long ttwu_cnt;
　　unsigned long ttwu_attempts;
　　unsigned long ttwu_moved;
　　
　　/* wake_up_new_task() stats */
　　unsigned long wunt_cnt;
　　unsigned long wunt_moved;
　　
　　/* sched_migrate_task() stats */
　　unsigned long smt_cnt;
　　
　　/* sched_balance_exec() stats */
　　unsigned long sbe_cnt;
#endif
};

runqueue 結構中名稱為 arrays 的欄位，是具有 2 個 prio_array_t 型別(即 struct prio_array)的陣列，
arrays[0] 與 arrays[1] 都包含 140 個雙向鏈結串列的串列首，用來記錄優先等級 0 到 139 的可執行的行程。
另外有 2 個指標會分別指向 arrays[0] 與 arrays[1]，代表 active 與 expired 的行程集合，如下圖所示。

在系統的運作過程中，active 行程用完其執行時間就變成 expired 行程。而當 active 的佇列為空時，
expired 的佇列就會與 active 的佇列互換，便是將這 2 個指標指向不同的 arrays 的位置來達成。