(代碼基于linux4.4.42)
在探讨程序排程之前，我們想一下如下幾個問題：
程序建立後組織在哪裡？
何時去挑選程序來運作？
cpu挑選誰作為下一個運作的程序？
歸納起來，就是WHERE？WHEN？ and WHO？
WHRER?
一. 資料結構
要回答這個問題，我們先以公平排程為例來看看一些相關的資料結構：
| task_struct代表一個任務(程序/線程)： struct task_struct{ 。。。。 const struct sched_class *sched_class; struct sched_entity se; struct sched_rt_entity rt; 。。。。 } |
在task_struct中的兩個元素結構體sched_entity和sched_rt_entity是排程實體，顧名思義，它們是排程管理的主要實體：
| struct sched_entity { 。。。。。。 struct rb_node run_node; struct list_head group_node; 。。。。。。 #ifdef CONFIG_FAIR_GROUP_SCHED int depth; struct sched_entity*parent; struct cfs_rq*cfs_rq; struct cfs_rq*my_q; #endif 。。。。。。。 }; |
關于cfs排程我們關注的另外一個結構叫cfs運作隊列struct cfs_rq，其主要作用是将排程實體組織起來。而實際它用于組織的資料結構并非是隊列，而是紅黑樹。
| struct cfs_rq { 。。。。。。 unsigned int nr_running, h_nr_running; 。。。。。。 struct rb_root tasks_timeline; struct rb_node *rb_leftmost; struct sched_entity *curr, *next, *last, *skip; 。。。。。。 }; |
講完來cfs，接着我們再來看看實時排程的兩個相關結構，首先是rt排程實體：
| struct sched_rt_entity { struct list_head run_list; 。。。。。。 }; |
再看看組織實時任務的rt運作隊列：
| 實時運作隊列。 struct rt_rq { struct rt_prio_array active; unsigned int rt_nr_running; 。。。。。。 }; |
最後，我們還要講一個結構運作隊列結構：
| struct rq { struct cfs_rq cfs; struct rt_rq rt; struct dl_rq dl; #ifdef CONFIG_FAIR_GROUP_SCHED struct list_head leaf_cfs_rq_list; #endif }; |
二. 組織關系
我們在上面列出了task_struct、排程實體(sched_entity, sched_rt_entity)、排程運作隊列(cfs_rq,rt_rq) 和 rq四種結構體，這四中結構提就是程序排程的主要組織結構。
2.1 cfs排程
上面的結構中，運作隊列結構struct rq我們可以将其了解為所有程序的組織結構的"root"。 核心使用每cpu變量定義了struct rq結構執行個體runqueues：
DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues)
在多核系統中我們可以将runqueues了解為struct rq runqueues[cpus](雖然這種了解不夠準确)，每個cpu對應着一個runqueues的一個元素。在核心中可以通過宏“rq = cpu_rq(N)”來擷取cpuN對應的rq運作隊列指針。
下面來看看這些結構是如何把任務都組織起來的。
圖1 cfs排程的組織情況
這裡隻畫出了cpu0的情況，其他cpu的情況和cpu0類似。
整個結構的“根”在struct rq runqueues[0]，它管理着三個“隊列”：cfs運作隊列、rt運作隊列和dl運作隊列。這三個“隊列”分别代表着不同的排程類，struct cfs_rq cfs是用于組織公平排程相關的結構；struct rt_rq rt用于組織實時任務排程相關結構；而struct dl_rq dl主要用于deadline排程相關結構。不同的排程其組織結構也有所差異，我們這裡以公平排程為例來進行說明。
而cfs運作隊列struct cfs_rq則主要包含了struct rb_root tasks_timeline紅黑根節點結構和struct rb_node *rb_leftmost紅黑節點指針。在cfs排程中所有的任務通過内置的成員組織成紅黑樹，每個cpu組織有一棵紅黑樹。 而struct rb_root tasks_timeline結構中的tasks_timeline.rb_node成員指向了本cpu上紅黑樹的樹"根"，紅黑樹中的每個紅黑節點代表一個排程實體，在不考慮組排程的情況下，一個排程實體實際上就對應一個任務task_struct結構。
cfs_rq的另外一個成員rb_leftmost指向本cpu紅黑樹中最左邊的節點。在CFS排程中，位置越靠近左邊的紅黑樹節點就越有得到排程的機會。而rb_leftmost所指向的紅黑樹節點就在下一次排程時發生時選擇運作，這大大增加了任務排程選擇的速度。
整棵紅黑樹中的紅黑節點也就隻起到了連接配接器的作用，真正排程的主要結構還是排程實體struct sched_entity，這個結構裡面嵌入了struct rb_node run_node紅黑節點。這樣就可以通過紅黑節點将本cpu上的所有排程實體間接的組織成了一棵紅黑樹。核心在沒有使能CONFIG_FAIR_GROUP_SCHED組排程的情況下，一個排程實體sched_entity對應着一個任務task_struct結構，就像我們圖中所看到的那樣。
但是如果核心配置了CONFIG_FAIR_GROUP_SCHED組排程，則情況會複雜一些：sched_entity不一定再是老老實實對應一個任務task_struct，它有可能是一個“組”。這個時候sched_entity的成員struct cfs_rq *my_q又指向一個cfs_rq結構，即一個cfs運作隊列，而随這個struct cfs_rq *my_q->tasks_timeline而來的又會是一顆長滿了排程實體sched_entity的“子紅黑樹”。
雖然在使能了CONFIG_FAIR_GROUP_SCHED的cfs組排程中，一個排程實體sched_entity不再一定對應着一個任務task_struct；但是一個任務task_struct始終對應着一個sched_entity，而這個與task_struct一一對應的排程實體，在組排程中就是紅黑樹的葉子節點。即組排程中紅黑樹的葉子節點才真正代表着一個實實在在的任務。
有了上面的了解作為鋪墊，我們就可以來大概了解一下核心是如何找到下一個将要運作的任務的。
核心中主要通過sched_class.pick_next_task()函數來選擇下一個将運作的任務，這裡的sched_class是排程類。目前的核心中的定義4個排程類：dl_sched_class、rt_sched_class、fair_sched_class和idle_sched_class。
1) 首先通過cpu = smp_processor_id()擷取目前cpu；
2) 在通過rq = cpu_rq(cpu)擷取目前cpu對應的runqueues[cpu];
3) 周遊系統中的所有排程類(前面提到的4個sched_class)，依次調用各個sched_class.pick_next_task()函數(直到找到一個可運作的任務)。
4) 不同的sched_class.pick_next_task()函數會找到struct rq runqueues[cpu]結構中各自的排程運作隊列結構。如cfs排程會找到rq中的struct cfs_rq cfs，而rt排程則會找到這個rq中的struct rt_rq rt成員。
5) 有了排程運作隊列，如上面的cfs_rq，就可以根據各自的排程算法先找到最适合運作的排程實體sched_entiy(實時排程為sched_rt_entity)，然後自然也就找到了對應的任務task_struct。剩下的任務切換工作就交給核心來完成。
2.2 rt排程
rt排程的結構在《RT任務排程概覽》中已經介紹過。為了保持本章的一緻性和完整性，也簡單介紹一下rt排程的組織結構。
和cfs一樣，struct rq runqueues依然是rt程序組織結構的“根”，但是隻不過所有的實時任務組織在struct rt_rq rq.rt中。與cfs采用紅黑樹組織管理架構不同，實時任務的采用的是優先級數組方式來管理，這種優先級數組不是通用的資料結構，而是專為任務排程所設計，它定義在核心kernel/sched/sched.h檔案中：
/*
* This is the priority-queue data structure of the RT scheduling class:
*/
struct rt_prio_array {
DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */
struct list_head queue[MAX_RT_PRIO];
};
其中rt_prio_arry的第一個成員是一個位圖變量bitmap用以标記哪個優先級有就緒的任務；而連結清單數組queue[MAX_RT_PRIO]則為每個優先級的實時任務都準備了一個struct list_head連結清單，用以将各個優先級的任務組織起來。
當bitmap中的某一位為1時，表示queue[MAX_RT_PRIO]對應的某個優先級的連結清單中挂有就緒的任務。
在rt_rq中，優先級數組成員為：struct rt_prio_array active，整個rt排程的組織架構如下所示：
圖2：rt任務的組織架構
如上圖所示，rt排程的組織也是通過rq/rt_rq/sched_rt_entity/task_struct的層級方式組織起來。當系統要從rt排程類中挑選一個任務時，流程如下：
1) 首先通過cpu = smp_processor_id()擷取目前cpu；
2) 在通過rq = cpu_rq(cpu)擷取目前cpu對應的runqueues[cpu];
3) 周遊所有的排程類，找到rt_sched_class，接着找到rt對應的回調函數pick_next_task_rt，這個函數會找到requeues[cpuN]中的struct rt_rq rt成員;
4) 再通過rt_rq.active擷取到rt運作隊列中的優先級數組。優先級數組中有兩個元素，一個是含有MAX_RT_PRIO個struct list_head元素的數組queue[]；另外一個是位圖bitmap。
5) 在沒有指定組排程的情況下，優先級數組中的的兩個元素就将本cpu上的所有的排程實體組織起來。其中queue[MAX_RT_PRIO]中的每個元素挂着某一個優先級的所有就緒的排程實體(也有可能某個優先級沒有任何就緒排程實體)；如果某一優先級中有就緒的排程實體，則bitmap中的對應的某一位就置1。
6) 具有同一個優先級的所有就緒rt排程實體都通過sched_rt_entity.run_list 連結組織成一個連結清單，挂到queue[prio]連結清單頭上。
7) 和cfs排程類似sched_rt_entity是嵌入在任務task_struct中的。如果一個任務是實時任務，那麼它就唯一對應一個rt排程實體sched_rt_entity；在沒有定義實時組排程的情況下sched_rt_entity與task_struct是一一對應的；然而一旦定義了組排程，和cfs排程的情況類似，一個sched_rt_entity可能代表一個組，即實時排程實體可以通過struct rt_rq sched_rt_entity.my_q成員又組織成一個優先級數組。隻有在sched_rt_entity.my_q為NULl時，這個實時排程實體才表示一個真正的任務。
核心中的排程的大概架構就講到這裡。為了了解整個組織原理，沒有詳細講解裡面的細節，以免“喧賓奪主”。有了架構概念，後續會更好的了解到具體的排程細節。