調度程序負責決定哪個進程投入運行，何時運行以及運行多長時間。只有通過調度程序合理調度，系統資源才能最大限度發揮作用，多進程才會有並發執行的效果。
最大限度地利用處理器時間的原則是，只要有可以執行的進程，那麼就總會有進程正在執行。
1.多任務
多任務系統分兩類：非搶占式多任務(cooperative multitasking)和搶占式多任務(preemptive multitasking)。由調度器來決定什麼時候停止一個進程運行，這個強制掛起動作叫做搶占(preemption)。
進程在被搶占之前可以運行的時間是預先設定好的，叫做時間片。有效管理時間片能使調度程序從系統全局角度作出調度決定，這樣還可以避免個別進程獨占系統資源。
現代操作系統多采用動態時間片計算方法和可配置的計算策略。但是Linux獨一無二的“公平”調度程序本身並沒有采用時間片來達到公平調度。
相反，cooperative multitasking中除非進程自己主動停止運行，否則會一直執行，主動掛起自己的操作叫讓步。缺點是，調度器無法管理每個進程具體執行多少時間，更糟的是，一個絕不讓步的懸掛進程能使系統崩潰。
2.Linux進程調度
Linux2.4之前的調度程序都相當簡陋，讓人也很容易理解，但是它在眾多可運行進程或多處理器環境下都難以勝任。
正因為如此，Linux2.5內核中引入了新的調度程序--O(1)，即大O表示法，簡單說，它指不管輸入有多大，調度程序都可以在恆定的時間內完成工作。這主要感謝靜態時間片算法和正對每一處理器的運行隊列。O(1)調度器在擁有數以十計的多處理器的環境下尚能表現近乎完美的性能和可擴展性，但是實踐證明對於調度那些響應時間敏感的程序卻先天不足(比如交互程序)，O(1)對於大服務器的工作負載很理想，但是在很多交互程序要運行的桌面系統上則表現不佳。
在2.6內核開發初期，開發人員為了提高對交互程序調度性能，引入了新調度算法。其中最著名的是“反轉樓梯最後期限調度算法”RSDL，該算法吸取了隊列理論，將公平調度概念引入Linux調度程序，並且最終在2.6.23版本中替代了O(1)算法，它此刻被稱為“完全公平調度算法”，CFS.
3.策略 :決定調度程序在何時讓什麼進程運行，策略往往就決定系統的整體印象，並且還要負責優化使用處理器時間。所以無論從那個方面看，它都是直觀重要的。
(1)I/O消耗型和處理器消耗型的進程
I/O消耗型：指進程的大部分時間用來提交I/O請求或是等待I/O請求，這樣的進程經常處於可運行狀態，但通常只運行很短時間，在等待I/O時會阻塞。
處理器消耗型：進程大部分時間都在執行代碼，除非被搶占，否則一直執行，沒太多I/O需求。調度器不應該經常讓他們執行，應盡量降低它們的調度頻率，而延長其運行時間。
調度策略就是要在這兩個矛盾中尋找平衡：進程響應迅速(響應時間短)和最大系統利用率(高吞吐量)，為了滿足這個需求，調度程序通常采用非常復雜的算法來決定最值得運行的進程投入運行。
(2)進程優先級
是一種根據進程的價值和其對處理器時間的需求來對進程進行分級的方法。通常做法是優先級高的先運行，低的後運行，相同優先級輪轉執行，在某些系統中，優先級高的使用時間片也較長。
調度程序總是選擇時間片未用盡而且優先級最高的進程運行。用戶和系統都可以通過設置進程優先級來影響系統的調度。
Linux采用了兩個不同的優先級范圍。第一個是nice值(范圍從-20～19)，默認值是0，越大的nice值表示優先級越低，低nice值的進程可以獲得更多的處理器時間。Linux中nice值代表時間片的比例.(ps –el可以查看系統進程，NI一列就是nice值)
第二種是實時優先級，其值可配，從0~99，越高的值表示優先級越高。
ps -eo state,uid,pid,ppid,rtprio,time,comm
(3)時間片
指進程在被搶占前所能持續運行的時間。時間片過長會導致系統對交互響應表現欠佳，時間片太短會明顯增加進程切換帶來的處理器耗時。IO消耗型不需要長的時間片，而處理器消耗型的進程希望越長越好(提高高速緩存命中率)。
Linux的CFS調度器沒有直接分配時間片到進程，而是分配處理器的使用比。這樣進程所獲得的處理器時間其實是和系統負載密切相關的，這個比例進一步還會受進程nice值影響。具有更小nice值的進程會被賦予高權重，從而有用更多的處理器使用比。
多數系統中，是否將一個進程立刻投入運行，完全由進程優先級和是否擁有時間片決定的。而在Linux的CFS調度器，其搶占時機取決於新的可運行程序消耗了多少處理器使用比，如果消耗的使用比比當前進程小，則新進程立刻投入運行，否則推遲運行。
比如系統僅有文字處理和視頻編碼兩個進程，nice值相同，分給的處理器使用比都是50%。文本編輯器大部分時間用於等待用戶輸入，因此肯定不會用到處理器的50%，而視頻編碼是有可能用到50%的。我們關心的是，當IO發生，文本編輯器被喚醒時，CFS發現文本編輯器運行的時間比視頻編碼器短的多，因為文本編輯器沒有消耗掉承諾給它的50%處理器使用比，因此CFS立即讓文本編輯器投入運行。
4.Linux調度算法
(1)調度器類
Linux調度器是以模塊的方式提供的，這樣可以讓不同類型的進程可以有針對性地選擇調度算法。這種模塊化結構稱為調度器類。，它允許可動態的添加的調度算法並存，調度屬於自己范疇的進程。
每個調度器都有一個優先級，系統會按照優先級順序遍歷調度類，選出最高優先級的調度器類，然後選擇下面要執行的進程。
CFS是一個針對普通進程的調度類，SCHED_NORMAL，還有實時調度類。
(2)傳統UNIX進程調度
一般采用絕對的優先級和時間片，這會導致以下問題：
①nice值對應到絕對時間片，導致進程切換無法最優化
②相對的nice值，把進程的nice值減1，所帶來的效果取決於nice初始值
③時間片會隨定時器節拍改變
④對喚醒進程提升優先級，會留下玩弄調度器的後門(可以改變影響優先級)。
(3)CFS原理
CFS基於一個簡單的理念：進程調度的效果應如同系統具備一個理想中的多任務處理器。在有n個進程的系統中，每個進程獲得1/n處理器時間。
CFS在所有可運行總數基礎上計算出一個進程應該運行多久。允許每個進程運行一段時間，循環輪轉，選擇運行最少的進程作為下一個運行進程。每個進程都按其權重在全部可運行進程中所占比例的“時間片”來運行。CFS為完美多任務中的無限小調度周期設立一個目標—“目標延遲”。每個進程時間片的最小粒度是1ms.
任何處理器進程所獲得的處理器時間是由它自己和其他可運行進程的nice相對值決定的。CFS不是完美的公平，但是在幾百個進程環境中可以體現出近乎完美的多任務。
5.Linux調度的實現
代碼位於kernel/sched/fair.c
(1)時間記賬
①所有調度器都必須對進程運行時間做記賬，CFS不再有時間片概念，但是為確保每個進程只在公平分配給它的處理器時間運行，也會用以下實體機構來做時間記賬，在<linux/sched.h>
struct sched_entity { 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;
u64 vruntime;
u64 prev_sum_exec_runtime;
…
};
這個結構體作為se成員，嵌入在進程描述符struct task_struct內
②虛擬運行時間
Vruntime所有可運行進程總數的被加權後的計算時間，單位是ns.其與定時器節拍無關。CFS用vruntime來記錄一個程序到底運行了多長時間以及它還應該再運行多久。
記賬功能在fair.c文件實現
static void update_curr(struct cfs_rq *cfs_rq) {
struct sched_entity *curr = cfs_rq->curr;
u64 now = rq_of(cfs_rq)->clock_task;
unsigned long delta_exec;
if (unlikely(!curr))
return;
/*
* Get the amount of time the current task was running
* since the last time we changed load (this cannot
* overflow on 32 bits):
*/
delta_exec = (unsigned long)(now - curr->exec_start);
if (!delta_exec)
return;
__update_curr(cfs_rq, curr, delta_exec);
curr->exec_start = now;
if (entity_is_task(curr)) {
struct task_struct *curtask = task_of(curr);
trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
cpuacct_charge(curtask, delta_exec);
account_group_exec_runtime(curtask, delta_exec);
}
account_cfs_rq_runtime(cfs_rq, delta_exec);
}
update_curr()由系統定時器周期性調用，它計算了當前進程的執行時間(加權計算的)與vruntime相加。Vruntime可以准確地測量給定進程的運行時間，而且可知道誰應該是下一個被運行的進程。
(2)進程選擇
CFS始終選擇具有最小vruntime的進程來執行。
CFS用紅黑樹來組織可運行進程隊列，vruntime值作為紅黑樹的鍵值，通過鍵值檢索對應節點的速度與整個樹的節點規模成指數比關系。
①挑選下一個任務
簡單說，CFS運行rbtree樹中最左邊葉子節點所代表的進程，實現函數是
static struct sched_entity *__pick_next_entity(struct sched_entity *se) {
struct rb_node *next = rb_next(&se->run_node);
if (!next)
return NULL;
return rb_entry(next, struct sched_entity, run_node);
}
函數本身並不會遍歷樹找到最左邊葉子節點，盡管有效查找葉子節點是紅黑樹的優勢O(logn),更容易的做法是把最左側葉子節點緩存起來。該函數返回值就是下一個運行的進程，若返回NULL，表示沒有可運行進程，CFS調用器選擇idle任務運行。
②向紅黑樹中添加進程
enqueue_entity()函數實現添加進程到rbtree，以及緩存最左邊葉子節點，在進程變為可運行狀態(被喚醒)或者通過fork()調用第一次創建進程時發生。
static void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
/*
* Update the normalized vruntime before updating min_vruntime
* through callig update_curr().
*/
if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
se->vruntime += cfs_rq->min_vruntime;
/*
* Update run-time statistics of the 'current'.
*/
update_curr(cfs_rq);
enqueue_entity_load_avg(cfs_rq, se, flags & ENQUEUE_WAKEUP);
account_entity_enqueue(cfs_rq, se);
update_cfs_shares(cfs_rq);
if (flags & ENQUEUE_WAKEUP) {
place_entity(cfs_rq, se, 0);
enqueue_sleeper(cfs_rq, se);
}
update_stats_enqueue(cfs_rq, se);
check_spread(cfs_rq, se);
if (se != cfs_rq->curr)
__enqueue_entity(cfs_rq, se);
se->on_rq = 1;
if (cfs_rq->nr_running == 1) {
list_add_leaf_cfs_rq(cfs_rq);
check_enqueue_throttle(cfs_rq);
}
}
該函數更新運行時間和其他一些統計數據，然後調用__enqueue_entity()進行繁重的插入操作，把數據項真正插入到rbtree中。
③從樹中刪除進程
刪除發生在進程堵塞(變為不可運行狀態)或終止時。
static void dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
/*
* Update run-time statistics of the 'current'.
*/
update_curr(cfs_rq);
dequeue_entity_load_avg(cfs_rq, se, flags & DEQUEUE_SLEEP);
update_stats_dequeue(cfs_rq, se);
if (flags & DEQUEUE_SLEEP) {
#ifdef CONFIG_SCHEDSTATS
if (entity_is_task(se)) {
struct task_struct *tsk = task_of(se);
if (tsk->state & TASK_INTERRUPTIBLE)
se->statistics.sleep_start = rq_of(cfs_rq)->clock;
if (tsk->state & TASK_UNINTERRUPTIBLE)
se->statistics.block_start = rq_of(cfs_rq)->clock;
}
#endif
}
clear_buddies(cfs_rq, se);
if (se != cfs_rq->curr)
__dequeue_entity(cfs_rq, se);
se->on_rq = 0;
account_entity_dequeue(cfs_rq, se);
/*
* Normalize the entity after updating the min_vruntime because the
* update can refer to the ->curr item and we need to reflect this
* movement in our normalized position.
*/
if (!(flags & DEQUEUE_SLEEP))
se->vruntime -= cfs_rq->min_vruntime;
/* return excess runtime on last dequeue */
return_cfs_rq_runtime(cfs_rq);
update_min_vruntime(cfs_rq);
update_cfs_shares(cfs_rq);
}
rb_erase()，然後更新rb_leftmost緩存，如果刪除的是最做左節點，要重新找到新的最左節點。
(3)調度器入口
調度器入口點是schedule()函數，調用pick_next_task()，以優先級為序，從最高優先級類開始，每個調度器類都實現了pick_next_task()，從第一個返回的非NULL值的類中選擇下一個可運行進程。
(4)睡眠和喚醒
當休眠時，進程把自己標記成休眠狀態，從可執行紅黑樹中移出，當如等待隊列，然後調用schedule()選擇了一個進程執行。
喚醒過程剛好相反：進程被設置為可執行狀態，然後從等待隊列中移到可執行紅黑樹中。
休眠分TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE ，兩種狀態的進程位於同一個等待隊列上，等待某些事件，不能夠運行。
①等待隊列
休眠通過等待隊列處理，等待隊列是由等待某些事件發生的進程組成的簡單鏈表.
DEFINE_WAIT(wait); Add_wait_queue(wait);
While(!condition){
Prepare_to_wait(&q,&wait,TASK_INTERRUPTIBLE);
If(signal_pending(current))
Schedule();
}
Finish_wait(&q,&wait);
②喚醒
通過wake_up()進行，喚醒指定等待隊列的所有進程，把喚醒進程狀態設置為TASK_RUNNING,調用enqueue_task()將此進程放入紅黑樹中，如果被喚醒進程優先級比當前正執行的優先級高，還要設置need_resched標志。
6.搶占和上下文切換
(1)上下文切換，也就是從一個執行進程切換到另一個可執行進程，在schedule()調用context_swtich()函數完成。
context_swtich()一是調用switch_mm()，把虛擬內存從上一個進程映射切換到新進程中。
二是調用swtich_to()把上一個進程的處理器狀態新進程的處理器狀態，包括保存、恢復棧信息和寄存器信息，還有其他任何與體系結構相關的信息。
內核提供了一個need_resched標志來表明是否需要重新調度，每個進程都包含一個need_resched。
(2)搶占
用戶搶占：內核即將返回用戶空間的時候，檢查need_resched標志被設置，就會調用schedule()。包括：①從系統調用返回用戶空間時，②從中斷處理程序返回用戶空間時③用戶調用sleep()等主動讓出。
內核搶占：只要沒有持有鎖，內核就可以進行搶占(thread_info裡的preempt_count=0說明不持有鎖)
發生時間點：①中斷處理程序正在執行，且返回內核空間之前②內核代碼再一次具有可搶占性的時候③內核進程顯示的調用schedule()④內核進程阻塞。
7.實時調度策略
Linux提供了兩種實時調度策略：SCHED_FIFO和SCHED_RR，普通的，非實時的調度策略是SCHED_NORMAL。實時策略不被CFS管理，由一個特殊的實時調度器管理。
SCHED_FIFO:實現了一個簡單的，先入先出的算法，它不使用時間片，處於可運行狀態的SCHED_FIFO會比任何SCHED_NORMAL的進程先得到調度，並且它會一直執行，直到執行完，但是有高優先級的SCHED_FIFO或SCHED_RR會立刻搶占。
SCHED_RR與SCHED_FIFO大體相同，是帶有時間片的SCHED_FIFO—實時輪流調度算法。
Linux的實時調度算法提供了一種軟實時工作方式：內核調度進程，盡力使進程在它的限定時間到來前運行，但內核不保證總能滿足這些進程需求。而硬實時系統保證在一定條件下可以保證任何調度的需求。
實時優先級從0～MAX_RT_PRIO-1.默認是0～99.SCHED_NORMAL級進程的nice值共享這個取值空間，MAX_RT_PRIO～MAX_RT_PRIO+40.默認情況下nice從-20～19對應100～139的實時優先級范圍。
8.與調度相關的系統調用
Linux提供了一個系統調用族，用於管理與調度程序相關的參數。
(1) 與調度策略有關的
sched_setscheduler()和sched_getscheduler()分別用於設置和獲取進程的調度策略和實時優先級。
對於一個普通進程來說,nice()函數可以將給定進程的靜態優先級增加一個給定的量。只有超級用戶才能使用負值。
(2)與處理器綁定
sched_setaffinity()設置綁定處理器，
(3)放棄處理器
sched_yield()顯示的將處理器時間讓給其他進程，把自己移到過期隊列，這樣確保一段時間內它不會再被執行，由於實時進程不會過期，所以屬於例外。
