內存中保存了對每個進程的唯一描述, 並通過若干結構與其他進程連接起來.
調度器面對的情形就是這樣, 其任務是在程序之間共享CPU時間, 創造並行執行的錯覺, 該任務分為兩個不同的部分, 其中一個涉及調度策略, 另外一個涉及上下文切換.
內核必須提供一種方法, 在各個進程之間盡可能公平地共享CPU時間, 而同時又要考慮不同的任務優先級.
調度器的一個重要目標是有效地分配 CPU 時間片，同時提供很好的用戶體驗。調度器還需要面對一些互相沖突的目標，例如既要為關鍵實時任務最小化響應時間, 又要最大限度地提高 CPU 的總體利用率.
調度器的一般原理是, 按所需分配的計算能力, 向系統中每個進程提供最大的公正性, 或者從另外一個角度上說, 他試圖確保沒有進程被虧待.
linux把進程區分為實時進程和非實時進程, 其中非實時進程進一步劃分為交互式進程和批處理進程
在linux中, 調度算法可以明確的確認所有實時進程的身份, 但是沒辦法區分交互式程序和批處理程序, linux2.6的調度程序實現了基於進程過去行為的啟發式算法, 以確定進程應該被當做交互式進程還是批處理進程. 當然與批處理進程相比, 調度程序有偏愛交互式進程的傾向
根據進程的不同分類Linux采用不同的調度策略.
對於實時進程，采用FIFO或者Round Robin的調度策略.
對於普通進程，則需要區分交互式和批處理式的不同。傳統Linux調度器提高交互式應用的優先級，使得它們能更快地被調度。而CFS和RSDL等新的調度器的核心思想是”完全公平”。這個設計理念不僅大大簡化了調度器的代碼復雜度，還對各種調度需求的提供了更完美的支持.
注意Linux通過將進程和線程調度視為一個，同時包含二者。進程可以看做是單個線程，但是進程可以包含共享一定資源（代碼和/或數據）的多個線程。因此進程調度也包含了線程調度的功能.
目前非實時進程的調度策略比較簡單, 因為實時進程值只要求盡可能快的被響應, 基於優先級, 每個進程根據它重要程度的不同被賦予不同的優先級，調度器在每次調度時, 總選擇優先級最高的進程開始執行. 低優先級不可能搶占高優先級, 因此FIFO或者Round Robin的調度策略即可滿足實時進程調度的需求.
但是普通進程的調度策略就比較麻煩了, 因為普通進程不能簡單的只看優先級, 必須公平的占有CPU, 否則很容易出現進程饑餓, 這種情況下用戶會感覺操作系統很卡, 響應總是很慢，因此在linux調度器的發展歷程中經過了多次重大變動, linux總是希望尋找一個最接近於完美的調度策略來公平快速的調度進程.
一開始的調度器是復雜度為
然而，linux是集全球很多程序員的聰明才智而發展起來的超級內核，沒有最好，只有更好，在
2個調度器
可以用兩種方法來激活調度
一種是直接的, 比如進程打算睡眠或出於其他原因放棄CPU
另一種是通過周期性的機制, 以固定的頻率運行, 不時的檢測是否有必要
因此當前linux的調度程序由兩個調度器組成：主調度器，周期性調度器(兩者又統稱為通用調度器(generic scheduler)或核心調度器(core scheduler))
並且每個調度器包括兩個內容：調度框架(其實質就是兩個函數框架)及調度器類
調度器類是實現了不同調度策略的實例，如 CFS、RT class等。
它們的關系如下圖
![調度器的組成](https://www.unixlinux.online/unixlinux/UploadFiles_9426/201703/2017030111464102.jpg "\")
當前的內核支持兩種調度器類（sched_setscheduler系統調用可修改進程的策略）：CFS（公平）、RT（實時）；5種調度策略：SCHED_NORAML（最常見的策略）、SCHED_BATCH（除了不能搶占外與常規任務一樣，允許任務運行更長時間，更好地使用高速緩存，適合於成批處理的工作）、SCHED_IDLE（它甚至比nice 19還有弱，為了避免優先級反轉使用）和SCHED_RR（循環調度，擁有時間片，結束後放在隊列末）、SCHED_FIFO（沒有時間片，可以運行任意長的時間）；其中前面三種策略使用的是cfs調度器類，後面兩種使用rt調度器類。<喎?http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPjxzdHJvbmc+Mrj2tfe2yMb3wOA8L3N0cm9uZz48L3A+DQo8cD61scewtcTE2rrL1qez1jLW1rX3tsjG98Dgo6hzY2hlZF9zZXRzY2hlZHVsZXLPtc2ztffTw7/J0N64xL34s8y1xLLfwtSjqaO6PHN0cm9uZz5DRlOjqLmrxr2197bIxvejqTwvc3Ryb25nPqGiPHN0cm9uZz5SVKOoyrXKsbX3tsjG96OpPC9zdHJvbmc+PC9wPg0KPHA+PHN0cm9uZz411ta197bIst/C1Dwvc3Ryb25nPjwvcD4NCjx0YWJsZT4NCjx0aGVhZD4NCgk8dHI+DQoJPHRoPg0KCQnX1rbOPC90aD4NCgk8dGggYWxpZ249"center"> 描述
最早截止時間優先（Earliest Dealine First， EDF）是實時系統中常用的一種調度算法，系統中有多個任務時，由調度算法決定哪個任務當前占用處理器，那麼EDF算法就是按照任務的截止時間（deadline）來確定任務的執行順序，最早截止的任務先執行。
最早截止時間優先EDF（Earliest DeadlineFirst）算法是非常著名的實時調度算法之一。在每一個新的就緒狀態，調度器都是從那些已就緒但還沒有完全處理完畢的任務中選擇最早截止時間的任務，並將執行該任務所需的資源分配給它。在有新任務到來時，調度器必須立即計算EDF，排出新的定序，即正在運行的任務被剝奪，並且按照新任務的截止時間決定是否調度該新任務。如果新任務的最後期限早於被中斷的當前任務，就立即處理新任務。按照EDF算法，被中斷任務的處理將在稍後繼續進行。
該算法的思想是從兩個任務中選擇截至時間最早的任務,把它暫作為當前處理任務,再判斷該任務是否在當前周期內,若不在當前周期內,就讓另一任務暫作當前處理任務,若該任務也不在當前周期內,就讓CPU空跑到最靠近的下一個截至時間的開始,若有任務在該周期內,就判斷該任務的剩余時間是否小於當前截至時間與當前時間的差,若小於,則讓該任務運行到結束.否則,就讓該任務運行到該周期的截止時間,就立即搶回處理器,再判斷緊接著的最早截至時間,並把處理器給它,做法同上,如此反復執行.
其中前面三種策略使用的是cfs調度器類，後面兩種使用rt調度器類。
另外，對於調度框架及調度器類，它們都有自己管理的運行隊列，調度框架只識別rq（其實它也不能算是運行隊列），而對於cfs調度器類它的運行隊列則是cfs_rq（內部使用紅黑樹組織調度實體），實時rt的運行隊列則為rt_rq（內部使用優先級bitmap+雙向鏈表組織調度實體）
本質上, 通用調度器(核心調度器)是一個分配器,與其他兩個組件交互.
調度器用於判斷接下來運行哪個進程.
內核支持不同的調度策略(完全公平調度, 實時調度, 在無事可做的時候調度空閒進程,即0號進程也叫swapper進程,idle進程), 調度類使得能夠以模塊化的方法實現這些側露額, 即一個類的代碼不需要與其他類的代碼交互
當調度器被調用時, 他會查詢調度器類, 得知接下來運行哪個進程
在選中將要運行的進程之後, 必須執行底層的任務切換.
這需要與CPU的緊密交互. 每個進程剛好屬於某一調度類, 各個調度類負責管理所屬的進程. 通用調度器自身不涉及進程管理, 其工作都委托給調度器類.
調度器使用一系列數據結構來排序和管理系統中的進程. 調度器的工作方式的這些結構的涉及密切相關, 幾個組件在許多方面
struct task_struct
{
........
/* 表示是否在運行隊列 */
int on_rq;
/* 進程優先級
* prio: 動態優先級，范圍為100~139，與靜態優先級和補償(bonus)有關
* static_prio: 靜態優先級，static_prio = 100 + nice + 20 (nice值為-20~19,所以static_prio值為100~139)
* normal_prio: 沒有受優先級繼承影響的常規優先級，具體見normal_prio函數，跟屬於什麼類型的進程有關
*/
int prio, static_prio, normal_prio;
/* 實時進程優先級 */
unsigned int rt_priority;
/* 調度類，調度處理函數類 */
const struct sched_class *sched_class;
/* 調度實體(紅黑樹的一個結點) */
struct sched_entity se;
/* 調度實體(實時調度使用) */
struct sched_rt_entity rt;
struct sched_dl_entity dl;
#ifdef CONFIG_CGROUP_SCHED
/* 指向其所在進程組 */
struct task_group *sched_task_group;
#endif
........
}
int prio, static_prio, normal_prio;
unsigned int rt_priority;
動態優先級 靜態優先級 實時優先級
其中task_struct采用了三個成員表示進程的優先級:prio和normal_prio表示動態優先級, static_prio表示進程的靜態優先級.
為什麼表示動態優先級需要兩個值prio和normal_prio
調度器會考慮的優先級則保存在prio. 由於在某些情況下內核需要暫時提高進程的優先級, 因此需要用prio表示. 由於這些改變不是持久的, 因此靜態優先級static_prio和普通優先級normal_prio不受影響.
此外還用了一個字段rt_priority保存了實時進程的優先級
實時進程的優先級用實時優先級rt_priority來表示
linux2.6內核將任務優先級進行了一個劃分, 實時優先級范圍是0到MAX_RT_PRIO-1（即99），而普通進程的靜態優先級范圍是從MAX_RT_PRIO到MAX_PRIO-1（即100到139）。
/* http://lxr.free-electrons.com/source/include/linux/sched/prio.h?v=4.6#L21 */
#define MAX_USER_RT_PRIO 100
#define MAX_RT_PRIO MAX_USER_RT_PRIO
/* http://lxr.free-electrons.com/source/include/linux/sched/prio.h?v=4.6#L24 */
#define MAX_PRIO (MAX_RT_PRIO + 40)
#define DEFAULT_PRIO (MAX_RT_PRIO + 20)
unsigned int policy;
policy保存了進程的調度策略，目前主要有以下五種：
參見
http://lxr.free-electrons.com/source/include/uapi/linux/sched.h?v=4.6
/*
* Scheduling policies
*/
#define SCHED_NORMAL 0
#define SCHED_FIFO 1
#define SCHED_RR 2
#define SCHED_BATCH 3
/* SCHED_ISO: reserved but not implemented yet */
#define SCHED_IDLE 5
#define SCHED_DEADLINE 6
CHED_BATCH用於非交互的處理器消耗型進程
CHED_IDLE是在系統負載很低時使用CFS
SCHED_BATCH用於非交互, CPU使用密集型的批處理進程. 調度決策對此類進程給予”冷處理”: 他們絕不會搶占CF調度器處理的另一個進程, 因此不會干擾交互式進程. 如果打算使用nice值降低進程的靜態優先級, 同時又不希望該進程影響系統的交互性, 此時最適合使用該調度類.
而SCHED_LDLE進程的重要性則會進一步降低, 因此其權重總是最小的
注意
盡管名稱是SCHED_IDLE但是SCHED_IDLE不負責調度空閒進程. 空閒進程由內核提供單獨的機制來處理
SCHED_RR和SCHED_FIFO用於實現軟實時進程. SCHED_RR實現了輪流調度算法, 一種循環時間片的方法, 而SCHED_FIFO實現了先進先出的機制, 這些並不是由完全貢品調度器類CFS處理的, 而是由實時調度類處理.
/* http://lxr.free-electrons.com/source/include/linux/sched.h?v=4.6#L1431 */
unsigned int policy;
/* http://lxr.free-electrons.com/source/include/linux/sched.h?v=4.6#L1413 */
const struct sched_class *sched_class;
struct sched_entity se;
struct sched_rt_entity rt;
struct sched_dl_entity dl;
cpumask_t cpus_allowed;
調度器不限於調度進程, 還可以調度更大的實體, 比如實現組調度: 可用的CPUI時間首先在一半的進程組(比如, 所有進程按照所有者分組)之間分配, 接下來分配的時間再在組內進行二次分配
cpus_allows是一個位域, 在多處理器系統上使用, 用來限制進程可以在哪些CPU上運行
sched_class結構體表示調度類, 類提供了通用調度器和各個調度器之間的關聯, 調度器類和特定數據結構中匯集地幾個函數指針表示, 全局調度器請求的各個操作都可以用一個指針表示, 這使得無需了解調度器類的內部工作原理即可創建通用調度器, 定義在kernel/sched/sched.h
struct sched_class {
/* 系統中多個調度類, 按照其調度的優先級排成一個鏈表
下一優先級的調度類
* 調度類優先級順序: stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class
*/
const struct sched_class *next;
/* 將進程加入到運行隊列中，即將調度實體（進程）放入紅黑樹中，並對 nr_running 變量加1 */
void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
/* 從運行隊列中刪除進程，並對 nr_running 變量中減1 */
void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
/* 放棄CPU，在 compat_yield sysctl 關閉的情況下，該函數實際上執行先出隊後入隊；在這種情況下，它將調度實體放在紅黑樹的最右端 */
void (*yield_task) (struct rq *rq);
bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);
/* 檢查當前進程是否可被新進程搶占 */
void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
/*
* It is the responsibility of the pick_next_task() method that will
* return the next task to call put_prev_task() on the @prev task or
* something equivalent.
*
* May return RETRY_TASK when it finds a higher prio class has runnable
* tasks.
*/
/* 選擇下一個應該要運行的進程運行 */
struct task_struct * (*pick_next_task) (struct rq *rq,
struct task_struct *prev);
/* 將進程放回運行隊列 */
void (*put_prev_task) (struct rq *rq, struct task_struct *p);
#ifdef CONFIG_SMP
/* 為進程選擇一個合適的CPU */
int (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);
/* 遷移任務到另一個CPU */
void (*migrate_task_rq)(struct task_struct *p);
/* 用於進程喚醒 */
void (*task_waking) (struct task_struct *task);
void (*task_woken) (struct rq *this_rq, struct task_struct *task);
/* 修改進程的CPU親和力(affinity) */
void (*set_cpus_allowed)(struct task_struct *p,
const struct cpumask *newmask);
/* 啟動運行隊列 */
void (*rq_online)(struct rq *rq);
/* 禁止運行隊列 */
void (*rq_offline)(struct rq *rq);
#endif
/* 當進程改變它的調度類或進程組時被調用 */
void (*set_curr_task) (struct rq *rq);
/* 該函數通常調用自 time tick 函數；它可能引起進程切換。這將驅動運行時（running）搶占 */
void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
/* 在進程創建時調用，不同調度策略的進程初始化不一樣 */
void (*task_fork) (struct task_struct *p);
/* 在進程退出時會使用 */
void (*task_dead) (struct task_struct *p);
/*
* The switched_from() call is allowed to drop rq->lock, therefore we
* cannot assume the switched_from/switched_to pair is serliazed by
* rq->lock. They are however serialized by p->pi_lock.
*/
/* 用於進程切換 */
void (*switched_from) (struct rq *this_rq, struct task_struct *task);
void (*switched_to) (struct rq *this_rq, struct task_struct *task);
/* 改變優先級 */
void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
int oldprio);
unsigned int (*get_rr_interval) (struct rq *rq,
struct task_struct *task);
void (*update_curr) (struct rq *rq);
#ifdef CONFIG_FAIR_GROUP_SCHED
void (*task_move_group) (struct task_struct *p);
#endif
};
對於各個調度器類, 都必須提供struct sched_class的一個實例, 目前內核中有實現以下五種:
// http://lxr.free-electrons.com/source/kernel/sched/sched.h?v=4.6#L1254
extern const struct sched_class stop_sched_class;
extern const struct sched_class dl_sched_class;
extern const struct sched_class rt_sched_class;
extern const struct sched_class fair_sched_class;
extern const struct sched_class idle_sched_class;
目前系統中,Scheduling Class的優先級順序為
stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class
開發者可以根據己的設計需求,來把所屬的Task配置到不同的Scheduling Class中.
用戶層應用程序無法直接與調度類交互, 他們只知道上下文定義的常量SCHED_XXX(用task_struct->policy表示), 這些常量提供了調度類之間的映射。
SCHED_NORMAL, SCHED_BATCH, SCHED_IDLE被映射到fair_sched_class
SCHED_RR和SCHED_FIFO則與rt_schedule_class相關聯
就緒隊列是核心調度器用於管理活動進程的主要數據結構。
各個·CPU都有自身的就緒隊列，各個活動進程只出現在一個就緒隊列中, 在多個CPU上同時運行一個進程是不可能的.
早期的內核中就緒隊列是全局的, 即即有全局唯一的rq, 但是 在Linux-2.6內核時代，為了更好的支持多核，Linux調度器普遍采用了per-cpu的run queue，從而克服了多CPU系統中，全局唯一的run queue由於資源的競爭而成為了系統瓶頸的問題，因為在同一時刻，一個CPU訪問run queue時，其他的CPU即使空閒也必須等待，大大降低了整體的CPU利用率和系統性能。當使用per-CPU的run queue之後，每個CPU不再使用大內核鎖，從而大大提高了並行處理的調度能力。
就緒隊列是全局調度器許多操作的起點, 但是進程並不是由就緒隊列直接管理的, 調度管理是各個調度器的職責, 因此在各個就緒隊列中嵌入了特定調度類的子就緒隊列(cfs的頂級調度就隊列 struct cfs_rq, 實時調度類的就緒隊列struct rt_rq和deadline調度類的就緒隊列struct dl_rq
每個CPU都有自己的 struct rq 結構，其用於描述在此CPU上所運行的所有進程，其包括一個實時進程隊列和一個根CFS運行隊列，在調度時，調度器首先會先去實時進程隊列找是否有實時進程需要運行，如果沒有才會去CFS運行隊列找是否有進行需要運行，這就是為什麼常說的實時進程優先級比普通進程高，不僅僅體現在prio優先級上，還體現在調度器的設計上，至於dl運行隊列，我暫時還不知道有什麼用處，其優先級比實時進程還高，但是創建進程時如果創建的是dl進程創建會錯誤(具體見sys_fork)。
就緒隊列用struct rq來表示, 其定義在kernel/sched/sched.h, line 566
/*每個處理器都會配置一個rq*/
struct rq {
/* runqueue lock: */
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.
*/
/*用以記錄目前處理器rq中執行task的數量*/
unsigned long nr_running;
#ifdef CONFIG_NUMA_BALANCING
unsigned int nr_numa_running;
unsigned int nr_preferred_running;
#endif
#define CPU_LOAD_IDX_MAX 5
/*用以表示處理器的負載，在每個處理器的rq中都會有對應到該處理器的cpu_load參數配置，
在每次處理器觸發scheduler tick時，都會調用函數update_cpu_load_active,進行cpu_load的更新
在系統初始化的時候會調用函數sched_init把rq的cpu_load array初始化為0.
了解他的更新方式最好的方式是通過函數update_cpu_load,公式如下
cpu_load[0]會直接等待rq中load.weight的值。
cpu_load[1]=(cpu_load[1]*(2-1)+cpu_load[0])/2
cpu_load[2]=(cpu_load[2]*(4-1)+cpu_load[0])/4
cpu_load[3]=(cpu_load[3]*(8-1)+cpu_load[0])/8
cpu_load[4]=(cpu_load[4]*(16-1)+cpu_load[0]/16
調用函數this_cpu_load時，所返回的cpu load值是cpu_load[0]
而在進行cpu blance或migration時，就會呼叫函數
source_load target_load取得對該處理器cpu_load index值，
來進行計算*/
unsigned long cpu_load[CPU_LOAD_IDX_MAX];
unsigned long last_load_update_tick;
#ifdef CONFIG_NO_HZ_COMMON
u64 nohz_stamp;
unsigned long nohz_flags;
#endif
#ifdef CONFIG_NO_HZ_FULL
unsigned long last_sched_tick;
#endif
/* capture load from *all* tasks on this cpu: */
/*load->weight值，會是目前所執行的schedule entity的load->weight的總和
也就是說rq的load->weight越高，也表示所負責的排程單元load->weight總和越高
表示處理器所負荷的執行單元也越重*/
struct load_weight load;
/*在每次scheduler tick中呼叫update_cpu_load時，這個值就增加一，
可以用來反饋目前cpu load更新的次數*/
unsigned long nr_load_updates;
/*用來累加處理器進行context switch的次數，會在調用schedule時進行累加，
並可以通過函數nr_context_switches統計目前所有處理器總共的context switch次數
或是可以透過查看檔案/proc/stat中的ctxt位得知目前整個系統觸發context switch的次數*/
u64 nr_switches;
/*為cfs fair scheduling class 的rq就緒隊列 */
struct cfs_rq cfs;
/*為real-time scheduling class 的rq就緒隊列 */
struct rt_rq rt;
/* 為deadline scheduling class 的rq就緒隊列 */
/* 用以支援可以group cfs tasks的機制*/
#ifdef CONFIG_FAIR_GROUP_SCHED
/* list of leaf cfs_rq on this cpu: */
/*
在有設置fair group scheduling 的環境下，
會基於原本cfs rq中包含有若干task的group所成的排程集合，
也就是說當有一個group a就會有自己的cfs rq用來排程自己所屬的tasks,
而屬於這group a的tasks所使用到的處理器時間就會以這group a總共所分的的時間為上限。
基於cgroup的fair group scheduling 架構，可以創造出有階層性的task組織，
根據不同task的功能群組化在配置給該群主對應的處理器資源，
讓屬於該群主下的task可以透過rq機制使用該群主下的資源。
這個變數主要是管理CFS RQ list，
操作上可以透過函數list_add_leaf_cfs_rq把一個group cfs rq加入到list中，
或透過函數list_del_leaf_cfs_rq把一個group cfs rq移除，
並可以透過for_each_leaf_cfs_rq把一個rq上得所有leaf cfs_rq走一遍
*/
struct list_head leaf_cfs_rq_list;
#endif
/*
* 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:
*/
/*一般來說，linux kernel 的task狀態可以為
TASK_RUNNING, TASK_INTERRUPTIBLE(sleep), TASK_UNINTERRUPTIBLE(Deactivate Task),
此時Task會從rq中移除)或TASK_STOPPED.
透過這個變量會統計目前rq中有多少task屬於TASK_UNINTERRUPTIBLE的狀態。
當調用函數active_task時，會把nr_uninterruptible值減一，
並透過該函數enqueue_task把對應的task依據所在的scheduling class放在對應的rq中
並把目前rq中nr_running值加一 */
unsigned long nr_uninterruptible;
/*
curr:指向目前處理器正在執行的task;
idle:指向屬於idle-task scheduling class 的idle task;
stop:指向目前最高等級屬於stop-task scheduling class
的task; */
struct task_struct *curr, *idle;
/*
基於處理器的jiffies值，用以記錄下次進行處理器balancing 的時間點*/
unsigned long next_balance;
/*
用以存儲context-switch發生時，
前一個task的memory management結構並可用在函數finish_task_switch
透過函數mmdrop釋放前一個task的結構體資源 */
struct mm_struct *prev_mm;
unsigned int clock_skip_update;
/* 用以記錄目前rq的clock值，
基本上該值會等於通過sched_clock_cpu(cpu_of(rq))的返回值，
並會在每次調用scheduler_tick時通過函數update_rq_clock更新目前rq clock值。
函數sched_clock_cpu會通過sched_clock_local或ched_clock_remote取得
對應的sched_clock_data,而處理的sched_clock_data值，
會通過函數sched_clock_tick在每次調用scheduler_tick時進行更新；
*/
u64 clock;
u64 clock_task;
/*用以記錄目前rq中有多少task處於等待i/o的sleep狀態
在實際的使用上，例如當driver接受來自task的調用，
但處於等待i/o回復的階段時，為了充分利用處理器的執行資源，
這時就可以在driver中調用函數io_schedule，
此時就會把目前rq中的nr_iowait加一，並設定目前task的io_wait為1
然後觸發scheduling 讓其他task有機會可以得到處理器執行時間*/
atomic_t nr_iowait;
#ifdef CONFIG_SMP
/*root domain是基於多核心架構下的機制，
會由rq結構記住目前采用的root domain，
其中包括了目前的cpu mask(包括span,online rt overload), reference count 跟cpupri
當root domain有被rq參考到時，refcount 就加一，反之就減一。
而cpumask span表示rq可掛上的cpu mask,noline為rq目前已經排程的
cpu mask cpu上執行real-time task.可以參考函數pull_rt_task，當一個rq中屬於
real-time的task已經執行完畢，就會透過函數pull_rt_task從該
rq中屬於rto_mask cpu mask 可以執行的處理器上，找出是否有一個處理器
有大於一個以上的real-time task，若有就會轉到目前這個執行完成
real-time task 的處理器上
而cpupri不同於Task本身有區分140個(0-139)
Task Priority (0-99為RT Priority 而 100-139為Nice值 -20-19).
CPU Priority本身有102個Priority (包括,-1為Invalid,
0為Idle,1為Normal,2-101對應到到Real-Time Priority 0-99).
參考函數convert_prio, Task Priority如果是 140就會對應到
CPU Idle,如果是>=100就會對應到CPU Normal,
若是Task Priority介於0-99之間,就會對應到CPU Real-Time Priority 101-2之間.)
在實際的操作上,例如可以通過函數cpupri_find 傳入入一個要插入的Real-Time Task,
此時就會依據cpupri中pri_to_cpu選擇一個目前執行Real-Time Task
且該Task的優先級比目前要插入的Task更低的處理器,
並通過CPU Mask(lowest_mask)返回目前可以選擇的處理器Mask.
可以參考kernel/sched_cpupri.c.
在初始化的過程中,通過函數sched_init調用函數init_defrootdomain,
對Root Domain和CPU Priority機制進行初始化.
*/
struct root_domain *rd;
/*Schedule Domain是基於多核心架構下的機制.
每個處理器都會有一個基礎的Scheduling Domain,
Scheduling Domain可以通過parent找到上一層的Domain,
或是通過child找到下一層的 Domain (NULL表示結尾.).
也可以通過span字段,表示這個Domain所能覆蓋的處理器的范圍.
通常Base Domain會涵蓋系統中所有處理器的個數,
而Child Domain所能涵蓋的處理器個火速不超過它的Parent Domain.
而當進行Scheduling Domain 中的Task Balance,就會以該Domain所涵蓋的處理器為最大范圍.
同時,每個Schedule Domain都會包括一個或一個以上的
CPU Groups (結構為struct sched_group),並通過next字段把
CPU Groups鏈接在一起(成為一個單向的Circular linked list),
每個CPU Group都會有變量cpumask來定義CPU Group
可以參考Linux Kernel文件 Documentation/scheduler/sched-domains.txt.
*/
struct sched_domain *sd;
struct callback_head *balance_callback;
unsigned char idle_balance;
/* For active balancing */
int active_balance;
int push_cpu;
struct cpu_stop_work active_balance_work;
/* cpu of this runqueue: */
int cpu;
int online;
/*當RunQueue中此值為1,表示這個RunQueue正在進行
Fair Scheduling的Load Balance,此時會調用stop_one_cpu_nowait
暫停該RunQueue所出處理器調度,
並通過函數active_load_balance_cpu_stop,
把Tasks從最忙碌的處理器移到Idle的處理器器上執行. */
int active_balance;
/*用以存儲目前進入Idle且負責進行Load Balance的處理器ID.
調用的流程為,在調用函數schedule時,
若該處理器RunQueue的nr_running為0 (也就是目前沒有
正在執行的Task),就會調用idle_balance,並觸發Load Balance */
int push_cpu;
/* cpu of this runqueue: */
/*用以存儲前運作這個RunQueue的處理器ID*/
int cpu;
/*為1表示目前此RunQueue有在對應的處理器上並執行 */
int online;
/*如果RunQueue中目前有Task正在執行,
這個值會等等於該RunQueue的Load Weight除以目前RunQueue中Task數目的均值.
(rq->avg_load_per_task = rq->load.weight / nr_running;).*/
unsigned long avg_load_per_task;
/*這個值會由Real-Time Scheduling Class調用函數update_curr_rt,
用以統計目前Real-Time Task執行時間的均值,
在這個函數中會以目前RunQueue的clock_task減去目前Task執行的起始時間,
取得執行時間的Delta值. (delta_exec = rq->clock_task – curr->se.exec_start; ).
在通過函數sched_rt_avg_update把這個Delta值跟原本RunQueue中的rt_avg值取平均值.
以運行的周期來看,這個值可反應目前系統中Real-Time Task平均被分配到的執行時間值 .*/
u64 rt_avg;
/* 這個值主要在函數sched_avg_update更新 */
u64 age_stamp;
/*這值會在處理Scheduling時,若判斷目前處理器runQueue沒有正在運行的Task,
就會通過函數idle_balance更新這個值為目前RunQueue的clock值.
可用以表示這個處理器何時進入到Idle的狀態 */
u64 idle_stamp;
/*會在有Task運行且idle_stamp不為0 (表示前一個轉台是在Idle)時
以目前RunQueue的clock減去idle_stmp所計算出的Delta值為依據,
更新這個值， 可反應目前處理器進入Idle狀態的時間長短 */
u64 avg_idle;
/* This is used to determine avg_idle's max value */
u64 max_idle_balance_cost;
#endif
#ifdef CONFIG_IRQ_TIME_ACCOUNTING
u64 prev_irq_time;
endif
#ifdef CONFIG_PARAVIRT
u64 prev_steal_time;
#endif
#ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
u64 prev_steal_time_rq;
#endif
/* calc_load related fields */
/*用以記錄下一次計算CPU Load的時間,
初始值為目前的jiffies加上五秒與1次的Scheduling Tick的間隔
(=jiffies + LOAD_FREQ,且LOAD_FREQ=(5*HZ+1))*
/
unsigned long calc_load_update;
/*等於RunQueue中nr_running與nr_uninterruptible的總和.
(可參考函式calc_load_fold_active).*/
long calc_load_active;
#ifdef CONFIG_SCHED_HRTICK
#ifdef CONFIG_SMP
int hrtick_csd_pending;
/*在函數it_rq_hrtick初始化RunQueue High-Resolution
Tick時， 此值設為0.
在函數hrtick_start中,會判斷目前觸發的RunQueue跟目前處理器所使用的RunQueue是否一致,
若是,就直接呼叫函數hrtimer_restart,反之就會依據RunQueue中hrtick_csd_pending的值,
如果hrtick_csd_pending為0,就會通過函數__smp_call_function_single讓RunQueue所在的另一個
處理器執行rq->hrtick_csd.func和函數 __hrtick_start.
並等待該處理器執行完畢後,才重新把hrtick_csd_pending設定為1.
也就是說, RunQueue的hrtick_csd_pending是用來作為SMP架構下,
由處理器A觸發處理器B執行*/
struct call_single_data hrtick_csd;
#endif
/*為gh-Resolution Tick的結構,會通過htimer_init初始化.*/
struct hrtimer hrtick_timer;
#endif
#ifdef CONFIG_SCHEDSTATS
/* latency stats */
/*為Scheduling Info.的統計結構,可以參考
include/linux/sched.h中的宣告. 例如在每次觸發
Schedule時,呼叫函式schedule_debug對上一個Task
的lock_depth進行確認(Fork一個新的Process 時,
會把此值預設為-1就是No-Lock,當呼叫
Kernel Lock時, 就會把Current Task的lock_depth加一.),
若lock_depth>=0,就會累加Scheduling Info.的bkl_count值,
用以代表Task Blocking的次數.*/
struct sched_info rq_sched_info;
/*可用以表示RunQueue中的Task所得到CPU執行
時間的累加值.
在發生Task Switch時,會透過sched_info_switch呼叫
sched_info_arrive並以目前RunQueue Clock值更新
Task 的sched_info.last_arrival時間,而在Task所分配時間
結束後,會在函式sched_info_depart中以現在的
RunQueue Clock值減去Task的sched_info.last_arrival
時間值,得到的 Delta作為變數rq_cpu_time的累
加值.*/
unsigned long long rq_cpu_time;
/* could above be rq->cfs_rq.exec_clock + rq->rt_rq.rt_runtime ? */
/* sys_sched_yield() stats */
/*用以統計呼叫System Call sys_sched_yield的次數.*/
unsigned int yld_count;
/* schedule() stats */
/*可用以統計觸發Scheduling的次數. 在每次觸發
Scheduling時,會透過函式schedule呼叫schedule_debug,
呼叫schedstat_inc對這變數進行累加.*/
unsigned int sched_count;
/*可用以統計進入到Idle Task的次數. 會在函式
pick_next_task_idle中,呼叫schedstat_inc對這變數進行
累加.*/
unsigned int sched_goidle;
/* try_to_wake_up() stats */
/*用以統計Wake Up Task的次數.*/
unsigned int ttwu_count;
/*用以統計Wake Up 同一個處理器Task的次數.*/
unsigned int ttwu_local;
/* BKL stats */
unsigned int bkl_count;
#endif
#ifdef CONFIG_SMP
struct llist_head wake_list;
#endif
#ifdef CONFIG_CPU_IDLE
/* Must be inspected within a rcu lock section */
struct cpuidle_state *idle_state;
#endif
};
系統中所有的就緒隊列都在runqueues數組中, 該數組的每個元素分別對應於系統中的一個CPU, 如果是單處理器系統只有一個就緒隊列, 則數組就只有一個元素
內核中也提供了一些宏, 用來獲取cpu上的就緒隊列的信息
// http://lxr.free-electrons.com/source/kernel/sched/sched.h?v=4.6#L716
DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
#define cpu_rq(cpu) (&per_cpu(runqueues, (cpu)))
#define this_rq() this_cpu_ptr(&runqueues)
#define task_rq(p) cpu_rq(task_cpu(p))
#define cpu_curr(cpu) (cpu_rq(cpu)->curr)
#define raw_rq() raw_cpu_ptr(&runqueues)
在系統中至少有一個CFS運行隊列，其就是根CFS運行隊列，而其他的進程組和進程都包含在此運行隊列中，不同的是進程組又有它自己的CFS運行隊列，其運行隊列中包含的是此進程組中的所有進程。當調度器從根CFS運行隊列中選擇了一個進程組進行調度時，進程組會從自己的CFS運行隊列中選擇一個調度實體進行調度(這個調度實體可能為進程，也可能又是一個子進程組)，就這樣一直深入，直到最後選出一個進程進行運行為止
對於 struct cfs_rq 結構沒有什麼好說明的，只要確定其代表著一個CFS運行隊列，並且包含有一個紅黑樹進行選擇調度進程即可。
其定義在kernel/sched/sched.h#L359
/* CFS-related fields in a runqueue */
/* CFS調度的運行隊列，每個CPU的rq會包含一個cfs_rq，而每個組調度的sched_entity也會有自己的一個cfs_rq隊列 */
struct cfs_rq {
/* CFS運行隊列中所有進程的總負載 */
struct load_weight load;
/*
* nr_running: cfs_rq中調度實體數量
* h_nr_running: 只對進程組有效，其下所有進程組中cfs_rq的nr_running之和
*/
unsigned int nr_running, h_nr_running;
u64 exec_clock;
/*
* 當前CFS隊列上最小運行時間，單調遞增
* 兩種情況下更新該值:
* 1、更新當前運行任務的累計運行時間時
* 2、當任務從隊列刪除去，如任務睡眠或退出，這時候會查看剩下的任務的vruntime是否大於min_vruntime，如果是則更新該值。
*/
u64 min_vruntime;
#ifndef CONFIG_64BIT
u64 min_vruntime_copy;
#endif
/* 該紅黑樹的root */
struct rb_root tasks_timeline;
/* 下一個調度結點(紅黑樹最左邊結點，最左邊結點就是下個調度實體) */
struct rb_node *rb_leftmost;
/*
* 'curr' points to currently running entity on this cfs_rq.
* It is set to NULL otherwise (i.e when none are currently running).
* curr: 當前正在運行的sched_entity（對於組雖然它不會在cpu上運行，但是當它的下層有一個task在cpu上運行，那麼它所在的cfs_rq就把它當做是該cfs_rq上當前正在運行的sched_entity）
* next: 表示有些進程急需運行，即使不遵從CFS調度也必須運行它，調度時會檢查是否next需要調度，有就調度next
*
* skip: 略過進程(不會選擇skip指定的進程調度)
*/
struct sched_entity *curr, *next, *last, *skip;
#ifdef CONFIG_SCHED_DEBUG
unsigned int nr_spread_over;
#endif
#ifdef CONFIG_SMP
/*
* CFS load tracking
*/
struct sched_avg avg;
u64 runnable_load_sum;
unsigned long runnable_load_avg;
#ifdef CONFIG_FAIR_GROUP_SCHED
unsigned long tg_load_avg_contrib;
#endif
atomic_long_t removed_load_avg, removed_util_avg;
#ifndef CONFIG_64BIT
u64 load_last_update_time_copy;
#endif
#ifdef CONFIG_FAIR_GROUP_SCHED
/*
* h_load = weight * f(tg)
*
* Where f(tg) is the recursive weight fraction assigned to
* this group.
*/
unsigned long h_load;
u64 last_h_load_update;
struct sched_entity *h_load_next;
#endif /* CONFIG_FAIR_GROUP_SCHED */
#endif /* CONFIG_SMP */
#ifdef CONFIG_FAIR_GROUP_SCHED
/* 所屬於的CPU rq */
struct rq *rq; /* cpu runqueue to which this cfs_rq is attached */
/*
* leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
* a hierarchy). Non-leaf lrqs hold other higher schedulable entities
* (like users, containers etc.)
*
* leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This
* list is used during load balance.
*/
int on_list;
struct list_head leaf_cfs_rq_list;
/* 擁有該CFS運行隊列的進程組 */
struct task_group *tg; /* group that "owns" this runqueue */
#ifdef CONFIG_CFS_BANDWIDTH
int runtime_enabled;
u64 runtime_expires;
s64 runtime_remaining;
u64 throttled_clock, throttled_clock_task;
u64 throttled_clock_task_time;
int throttled, throttle_count;
struct list_head throttled_list;
#endif /* CONFIG_CFS_BANDWIDTH */
#endif /* CONFIG_FAIR_GROUP_SCHED */
};
其定義在kernel/sched/sched.h#L449
/* Real-Time classes' related field in a runqueue: */
struct rt_rq {
struct rt_prio_array active;
unsigned int rt_nr_running;
unsigned int rr_nr_running;
#if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
struct {
int curr; /* highest queued rt task prio */
#ifdef CONFIG_SMP
int next; /* next highest */
#endif
} highest_prio;
#endif
#ifdef CONFIG_SMP
unsigned long rt_nr_migratory;
unsigned long rt_nr_total;
int overloaded;
struct plist_head pushable_tasks;
#ifdef HAVE_RT_PUSH_IPI
int push_flags;
int push_cpu;
struct irq_work push_work;
raw_spinlock_t push_lock;
#endif
#endif /* CONFIG_SMP */
int rt_queued;
int rt_throttled;
u64 rt_time;
u64 rt_runtime;
/* Nests inside the rq lock: */
raw_spinlock_t rt_runtime_lock;
#ifdef CONFIG_RT_GROUP_SCHED
unsigned long rt_nr_boosted;
struct rq *rq;
struct task_group *tg;
#endif
};
其定義在kernel/sched/sched.h#L490
/* Deadline class' related fields in a runqueue */
struct dl_rq {
/* runqueue is an rbtree, ordered by deadline */
struct rb_root rb_root;
struct rb_node *rb_leftmost;
unsigned long dl_nr_running;
#ifdef CONFIG_SMP
/*
* Deadline values of the currently executing and the
* earliest ready task on this rq. Caching these facilitates
* the decision wether or not a ready but not running task
* should migrate somewhere else.
*/
struct {
u64 curr;
u64 next;
} earliest_dl;
unsigned long dl_nr_migratory;
int overloaded;
/*
* Tasks on this rq that can be pushed away. They are kept in
* an rb-tree, ordered by tasks' deadlines, with caching
* of the leftmost (earliest deadline) element.
*/
struct rb_root pushable_dl_tasks_root;
struct rb_node *pushable_dl_tasks_leftmost;
#else
struct dl_bw dl_bw;
#endif
};
我們前面提到, 調度器不限於調度進程, 還可以調度更大的實體, 比如實現組調度: 可用的CPUI時間首先在一半的進程組(比如, 所有進程按照所有者分組)之間分配, 接下來分配的時間再在組內進行二次分配.
這種一般性要求調度器不直接操作進程, 而是處理可調度實體, 因此需要一個通用的數據結構描述這個調度實體,即seched_entity結構, 其實際上就代表了一個調度對象，可以為一個進程，也可以為一個進程組。對於根的紅黑樹而言，一個進程組就相當於一個調度實體，一個進程也相當於一個調度實體。
我們可以先看看sched_entity結構，其定義在include/linux/sched.h, 如下：
/* 一個調度實體(紅黑樹的一個結點)，其包含一組或一個指定的進程，包含一個自己的運行隊列，一個父親指針，一個指向需要調度的運行隊列指針 */
struct sched_entity {
/* 權重，在數組prio_to_weight[]包含優先級轉權重的數值 */
struct load_weight load; /* for load-balancing */
/* 實體在紅黑樹對應的結點信息 */
struct rb_node run_node;
/* 實體所在的進程組 */
struct list_head group_node;
/* 實體是否處於紅黑樹運行隊列中 */
unsigned int on_rq;
/* 開始運行時間 */
u64 exec_start;
/* 總運行時間 */
u64 sum_exec_runtime;
/* 虛擬運行時間，在時間中斷或者任務狀態發生改變時會更新
* 其會不停增長，增長速度與load權重成反比，load越高，增長速度越慢，就越可能處於紅黑樹最左邊被調度
* 每次時鐘中斷都會修改其值
* 具體見calc_delta_fair()函數
*/
u64 vruntime;
/* 進程在切換進CPU時的sum_exec_runtime值 */
u64 prev_sum_exec_runtime;
/* 此調度實體中進程移到其他CPU組的數量 */
u64 nr_migrations;
#ifdef CONFIG_SCHEDSTATS
/* 用於統計一些數據 */
struct sched_statistics statistics;
#endif
#ifdef CONFIG_FAIR_GROUP_SCHED
/* 代表此進程組的深度，每個進程組都比其parent調度組深度大1 */
int depth;
/* 父親調度實體指針，如果是進程則指向其運行隊列的調度實體，如果是進程組則指向其上一個進程組的調度實體
* 在 set_task_rq 函數中設置
*/
struct sched_entity *parent;
/* 實體所處紅黑樹運行隊列 */
struct cfs_rq *cfs_rq;
/* 實體的紅黑樹運行隊列，如果為NULL表明其是一個進程，若非NULL表明其是調度組 */
struct cfs_rq *my_q;
#endif
#ifdef CONFIG_SMP
/*
* Per entity load average tracking.
*
* Put into separate cache line so it does not
* collide with read-mostly values above.
*/
struct sched_avg avg ____cacheline_aligned_in_smp;
#endif
};
在struct sched_entity結構中，值得我們注意的成員是
* 在進程運行時, 我們需要記錄消耗的CPU時間, 以用於完全公平調度器. sum_exec_runtime就用於該目的.
跟蹤運行時間是由update_curr不斷累積完成的. 內核中許多地方都會調用該函數, 例如, 新進程加入就緒隊列時, 或者周期性調度器中. 每次調用時, 會計算當前時間和exec_start之間的差值, exec_start則更新到當前時間. 差值則被加到sum_exec_runtime.
在進程執行期間虛擬時鐘上流逝的時間數量由vruntime統計
在進程被撤銷時, 其當前sum_exec_runtime值保存到prev_sum_exec_runtime, 此後, 進程搶占的時候需要用到該數據, 但是注意, 在prev_sum_exec_runtime中保存了sum_exec_runtime的值, 而sum_exec_runtime並不會被重置, 而是持續單調增長
每個進程的task_struct中都嵌入了sched_entity對象, 所以進程是可調度的實體, 但是請注意, 其逆命一般是不正確的, 即可調度的實體不一定是進程.
對於怎麼理解一個進程組有它自己的CFS運行隊列，其實很好理解，比如在根CFS運行隊列的紅黑樹上有一個進程A一個進程組B，各占50%的CPU，對於根的紅黑樹而言，他們就是兩個調度實體。調度器調度的不是進程A就是進程組B，而如果調度到進程組B，進程組B自己選擇一個程序交給CPU運行就可以了，而進程組B怎麼選擇一個程序給CPU，就是通過自己的CFS運行隊列的紅黑樹選擇，如果進程組B還有個子進程組C，原理都一樣，就是一個層次結構。
其定義在include/linux/sched.h, 如下：
struct sched_rt_entity {
struct list_head run_list;
unsigned long timeout;
unsigned long watchdog_stamp;
unsigned int time_slice;
unsigned short on_rq;
unsigned short on_list;
struct sched_rt_entity *back;
#ifdef CONFIG_RT_GROUP_SCHED
struct sched_rt_entity *parent;
/* rq on which this entity is (to be) queued: */
struct rt_rq *rt_rq;
/* rq "owned" by this entity/group: */
struct rt_rq *my_q;
#endif
};
其定義在include/linux/sched.h, 如下：
struct sched_dl_entity {
struct rb_node rb_node;
/*
* Original scheduling parameters. Copied here from sched_attr
* during sched_setattr(), they will remain the same until
* the next sched_setattr().
*/
u64 dl_runtime; /* maximum runtime for each instance */
u64 dl_deadline; /* relative deadline of each instance */
u64 dl_period; /* separation of two instances (period) */
u64 dl_bw; /* dl_runtime / dl_deadline */
/*
* Actual scheduling parameters. Initialized with the values above,
* they are continously updated during task execution. Note that
* the remaining runtime could be < 0 in case we are in overrun.
*/
s64 runtime; /* remaining runtime for this instance */
u64 deadline; /* absolute deadline for this instance */
unsigned int flags; /* specifying the scheduler behaviour */
/*
* Some bool flags:
*
* @dl_throttled tells if we exhausted the runtime. If so, the
* task has to wait for a replenishment to be performed at the
* next firing of dl_timer.
*
* @dl_boosted tells if we are boosted due to DI. If so we are
* outside bandwidth enforcement mechanism (but only until we
* exit the critical section);
*
* @dl_yielded tells if task gave up the cpu before consuming
* all its available runtime during the last job.
*/
int dl_throttled, dl_boosted, dl_yielded;
/*
* Bandwidth enforcement timer. Each -deadline task has its
* own bandwidth to be enforced, thus we need one timer per task.
*/
struct hrtimer dl_timer;
};
我們知道，linux是一個多用戶系統，如果有兩個進程分別屬於兩個用戶，而進程的優先級不同，會導致兩個用戶所占用的CPU時間不同，這樣顯然是不公平的(如果優先級差距很大，低優先級進程所屬用戶使用CPU的時間就很小)，所以內核引入組調度。如果基於用戶分組，即使進程優先級不同，這兩個用戶使用的CPU時間都為50%。
如果task_group中的運行時間還沒有使用完，而當前進程運行時間使用完後，會調度task_group中的下一個被調度進程；相反，如果task_group的運行時間使用結束，則調用上一層的下一個被調度進程。需要注意的是，一個組調度中可能會有一部分是實時進程，一部分是普通進程，這也導致這種組要能夠滿足即能在實時調度中進行調度，又可以在CFS調度中進行調度。
linux可以以以下兩種方式進行進程的分組：
用戶ID：按照進程的USER ID進行分組，在對應的/sys/kernel/uid/目錄下會生成一個cpu.share的文件，可以通過配置該文件來配置用戶所占CPU時間比例。
cgourp(control group)：生成組用於限制其所有進程，比如我生成一個組(生成後此組為空，裡面沒有進程)，設置其CPU使用率為10%，並把一個進程丟進這個組中，那麼這個進程最多只能使用CPU的10%，如果我們將多個進程丟進這個組，這個組的所有進程平分這個10%。
注意的是，這裡的進程組概念和fork調用所產生的父子進程組概念不一樣，文章所使用的進程組概念全為組調度中進程組的概念。為了管理組調度，內核引進了struct task_group結構
其定義在kernel/sched/sched.h?v=4.6#L240, 如下：
/* task group related information */
struct task_group {
struct cgroup_subsys_state css;
#ifdef CONFIG_FAIR_GROUP_SCHED
/* schedulable entities of this group on each cpu */
struct sched_entity **se;
/* runqueue "owned" by this group on each cpu */
struct cfs_rq **cfs_rq;
unsigned long shares;
#ifdef CONFIG_SMP
/*
* load_avg can be heavily contended at clock tick time, so put
* it in its own cacheline separated from the fields above which
* will also be accessed at each tick.
*/
atomic_long_t load_avg ____cacheline_aligned;
#endif
#endif
#ifdef CONFIG_RT_GROUP_SCHED
struct sched_rt_entity **rt_se;
struct rt_rq **rt_rq;
struct rt_bandwidth rt_bandwidth;
#endif
struct rcu_head rcu;
struct list_head list;
struct task_group *parent;
struct list_head siblings;
struct list_head children;
#ifdef CONFIG_SCHED_AUTOGROUP
struct autogroup *autogroup;
#endif
struct cfs_bandwidth cfs_bandwidth;
};
在struct task_group結構中，最重要的成員為 struct sched_entity * se 和 struct cfs_rq * cfs_rq。
在多核多CPU的情況下，同一進程組的進程有可能在不同CPU上同時運行，所以每個進程組都必須對每個CPU分配它的調度實體(struct sched_entity 和 struct sched_rt_entity)和運行隊列(struct cfs_rq 和 struct rt_rq)。
進程調度器的框架如下圖所示
![調度器的設計](https://www.unixlinux.online/unixlinux/UploadFiles_9426/201703/2017030111464103.jpg "\")
從圖中可以看出來，每個CPU對應包含一個運行隊列結構(struct rq)，而每個運行隊列又包含有其自己的實時進程運行隊列(struct rt_rq)、普通進程運行隊列(struct cfs_rq)、和deadline實時調度的運行隊列(struct dl_rq)，也就是說每個CPU都有他們自己的實時進程運行隊列及普通進程運行隊列
為了方便，我們在圖中只描述普通進程的組織結構(最復雜的也是普通進程的組織結構)，而紅色se則為當前CPU上正在執行的程序，藍色為下個將要執行的程序，其實圖中並不規范，實際上當進程運行時，會從紅黑樹中剝離出來，然後設定下一個調度進程，當進程運行時間結束時，再重新放入紅黑樹中。而為什麼CPU0上有兩個藍色將被調度進程，將在組調度中解釋。而為什麼紅黑樹中又有一個子紅黑樹，我們將在調度實體中解釋。
參照 linux調度器源碼分析 - 概述(一)
通過的調度策略對象–調度類
linux下每個進程都由自身所屬的調度類進行管理， sched_class結構體表示調度類, 調度類提供了通用調度器和各個調度器之間的關聯, 調度器類和特定數據結構中匯集地幾個函數指針表示, 全局調度器請求的各個操作都可以用一個指針表示, 這使得無需了解調度器類的內部工作原理即可創建通用調度器, 定義在kernel/sched/sched.h
開發者可以根據己的設計需求,來把所屬的Task配置到不同的Scheduling Class中.
用戶層應用程序無法直接與調度類交互, 他們只知道上下文定義的常量SCHED_XXX(用task_struct->policy表示), 這些常量提供了調度類之間的映射。
目前系統中,Scheduling Class的優先級順序為
stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class
被調度的實體–進程或者進程組
linux下被調度的不只是進程, 還可以是進程組. 因此需要一種更加通用的形式組織被調度數據結構, 即調度實體, 同樣不同的進程用不同的調度實體表示
用就緒隊列保存和組織調度進程
所有的就緒進程(TASK_RUNNING)都被組織在就緒隊列, 也叫運行隊列中, 每個CPU對應包含一個運行隊列結構(struct rq)，而每個運行隊列又嵌入了有其自己的實時進程運行隊列(struct rt_rq)、普通進程運行隊列(struct cfs_rq)、和EDF實時調度的運行隊列(struct dl_rq)，也就是說每個CPU都有他們自己的實時進程運行隊列及普通進程運行隊列
