前面我們重點分析了如何通過 fork, vfork, pthread_create 去創(chuàng)建一個進程或者線程，以及后面說了它們共同調用 do_fork 的實現(xiàn)?，F(xiàn)在已經(jīng)知道一個進程是如何創(chuàng)建的，但是進程何時被執(zhí)行，需要調度器來選擇。所以這一節(jié)我們介紹下進程調度和進程切換的詳情。

進程的分類

在 CPU 的角度看進程行為的話，可以分為兩類：

• CPU 消耗型：此類進程就是一直占用 CPU 計算，CPU 利用率很高
• IO 消耗型：此類進程會涉及到 IO，需要和用戶交互，比如鍵盤輸入，占用 CPU 不是很高，只需要 CPU 的一部分計算，大多數(shù)時間是在等待 IO

CPU 消耗型進程需要高的吞吐率，IO 消耗型進程需要強的響應性，這兩點都是調度器需要考慮的。
為了更快響應 IO 消耗型進程，內核提供了一個搶占(preempt)機制，使優(yōu)先級更高的進程，去搶占優(yōu)先級低的進程運行。內核用以下宏來選擇內核是否打開搶占機制：

• CONFIG_PREEMPT_NONE: 不打開搶占，主要是面向服務器。此配置下，CPU 在計算時，當輸入鍵盤之后，因為沒有搶占，可能需要一段時間等待鍵盤輸入的進程才會被 CPU 調度。
• CONFIG_PREEMPT : 打開搶占，一般多用于手機設備。此配置下，雖然會影響吞吐率，但可以及時響應用戶的輸入操作。

調度相關的數(shù)據(jù)結構

先來看幾個相關的數(shù)據(jù)結構：

task_struct

我們先把 task_struct 中和調度相關的結構拎出來：
struct task_struct {
......
const struct sched_class *sched_class;
struct sched_entity se;
struct sched_rt_entity rt;
......
struct sched_dl_entity dl;
......
unsigned int policy;
......
}

• struct sched_class：對調度器進行抽象，一共分為5類。

1. Stop調度器：優(yōu)先級最高的調度類，可以搶占其他所有進程，不能被其他進程搶占；
2. Deadline調度器：使用紅黑樹，把進程按照絕對截止期限進行排序，選擇最小進程進行調度運行；
3. RT調度器：為每個優(yōu)先級維護一個隊列；
4. CFS調度器：采用完全公平調度算法，引入虛擬運行時間概念；
5. IDLE-Task調度器：每個CPU都會有一個idle線程，當沒有其他進程可以調度時，調度運行idle線程；

• unsigned int policy：進程的調度策略有6種，用戶可以調用調度器里的不同調度策略。

1. SCHED_DEADLINE：使task選擇Deadline調度器來調度運行
2. SCHED_RR：時間片輪轉，進程用完時間片后加入優(yōu)先級對應運行隊列的尾部，把CPU讓給同優(yōu)先級的其他進程；
3. SCHED_FIFO：先進先出調度沒有時間片，沒有更高優(yōu)先級的情況下，只能等待主動讓出CPU；
4. SCHED_NORMAL：使task選擇CFS調度器來調度運行；
5. SCHED_BATCH：批量處理，使task選擇CFS調度器來調度運行；
6. SCHED_IDLE：使task以最低優(yōu)先級選擇CFS調度器來調度運行；

• struct sched_entity se：采用CFS算法調度的普通非實時進程的調度實體。
• struct sched_rt_entity rt：采用Roound-Robin或者FIFO算法調度的實時調度實體。
• struct sched_dl_entity dl：采用EDF算法調度的實時調度實體。

分配給 CPU 的 task，作為調度實體加入到運行隊列中。

runqueue 運行隊列

runqueue 運行隊列是本 CPU 上所有可運行進程的隊列集合。每個 CPU 都有一個運行隊列，每個運行隊列中有三個調度隊列，task 作為調度實體加入到各自的調度隊列中。
struct rq {
......
struct cfs_rq cfs;
struct rt_rq rt;
struct dl_rq dl;
......
}
三個調度隊列：

• struct cfs_rq cfs：CFS調度隊列
• struct rt_rq rt：RT調度隊列
• struct dl_rq dl：DL調度隊列

• cfs_rq：跟蹤就緒隊列信息以及管理就緒態(tài)調度實體，并維護一棵按照虛擬時間排序的紅黑樹。tasks_timeline->rb_root是紅黑樹的根，tasks_timeline->rb_leftmost指向紅黑樹中最左邊的調度實體，即虛擬時間最小的調度實體。

struct cfs_rq {
...
struct rb_root_cached tasks_timeline
...
};

• sched_entity：可被內核調度的實體。每個就緒態(tài)的調度實體sched_entity包含插入紅黑樹中使用的節(jié)點rb_node，同時vruntime成員記錄已經(jīng)運行的虛擬時間。

struct sched_entity {
...
struct rb_node run_node;
...
u64          vruntime;
...
};
這些數(shù)據(jù)結構的關系如下圖所示：

調度時刻

調度的本質就是選擇下一個進程，然后切換。在執(zhí)行調度之前需要設置調度標記 TIF_NEED_RESCHED，然后在調度的時候會判斷當前進程有沒有被設置 TIF_NEED_RESCHED，如果設置則調用函數(shù) schedule 來進行調度。

1. 設置調度標記

為 CPU 上正在運行的進程 thread_info 結構體里的 flags 成員設置 TIF_NEED_RESCHED。
那么，什么時候設置TIF_NEED_RESCHED呢 ？

1. scheduler_tick 時鐘中斷

1. wake_up_process 喚醒進程的時候

1. do_fork 創(chuàng)建新進程的時候

1. set_user_nice 修改進程nice值的時候

1. smp_send_reschedule 負載均衡的時候

2. 執(zhí)行調度

Kernel 判斷當前進程標記是否為 TIF_NEED_RESCHED，是的話調用 schedule 函數(shù)，執(zhí)行調度，切換上下文，這也是上面搶占(preempt)機制的本質。那么在哪些情況下會執(zhí)行 schedule 呢？

1. 用戶態(tài)搶占

ret_to_user 是異常觸發(fā)，系統(tǒng)調用，中斷處理完成后都會調用的函數(shù)。

1. 內核態(tài)搶占

可以看出無論是用戶態(tài)搶占，還是內核態(tài)搶占，最終都會調用 schedule 函數(shù)來執(zhí)行真正的調度：

還記得調度的本質嗎？調度的本質就是選擇下一個進程，然后切換。如上圖所示，用函數(shù) pick_next_task 選擇下一個進程，其本質就是調度算法的實現(xiàn)；用函數(shù) context_switch 完成進程的切換，即進程上下文的切換。下面我們分別看下這兩個核心功能。

調度算法

字段	版本
O(n) 調度器	linux0.11 - 2.4
O(1) 調度器	linux2.6
CFS調度器	linux2.6至今

O(n)

O(n) 調度器是在內核2.4以及更早期版本采用的算法，O(n) 代表的是尋找一個合適的任務的時間復雜度。調度器定義了一個 runqueue 的運行隊列，將進程的狀態(tài)變?yōu)?Running 的都會添加到此運行隊列中，但是不管是實時進程，還是普通進程都會添加到這個運行隊列中。當需要從運行隊列中選擇一個合適的任務時，就需要從隊列的頭遍歷到尾部，這個時間復雜度是O(n)，運行隊列中的任務數(shù)目越大，調度器的效率就越低。

所以 O(n) 調度器有如下缺陷：

• 時間復雜度是 O(n)，運行隊列中的任務數(shù)目越大，調度器的效率就越低。
• 實時進程不能及時調度，因為實時進程和普通進程在一個列表中，每次查實時進程時，都需要全部掃描整個列表，所以實時進程不是很“實時”。
• SMP 系統(tǒng)不好，因為只有一個 runqueue，選擇下一個任務時，需要對這個 runqueue 隊列進行加鎖操作，當任務較多的時候，則在臨界區(qū)的時間就比較長，導致其余的 CPU 自旋浪費。
• CPU空轉的現(xiàn)象存在，因為系統(tǒng)中只有一個runqueue，當運行隊列中的任務少于 CPU 的個數(shù)時，其余的 CPU 則是 idle 狀態(tài)。

O(1)

內核2.6采用了O(1) 調度器，讓每個 CPU 維護一個自己的 runqueue，從而減少了鎖的競爭。每一個runqueue 運行隊列維護兩個鏈表，一個是 active 鏈表，表示運行的進程都掛載 active 鏈表中；一個是 expired 鏈表，表示所有時間片用完的進程都掛載 expired 鏈表中。當 acitve 中無進程可運行時，說明系統(tǒng)中所有進程的時間片都已經(jīng)耗光，這時候則只需要調整 active 和 expired 的指針即可。每個優(yōu)先級數(shù)組包含140個優(yōu)先級隊列，也就是每個優(yōu)先級對應一個隊列，其中前100個對應實時進程，后40個對應普通進程。如下圖所示：

總的來說 O(1) 調度器的出現(xiàn)是為了解決 O(n) 調度器不能解決的問題，但 O(1) 調度器有個問題，一個高優(yōu)先級多線程的應用會比低優(yōu)先級單線程的應用獲得更多的資源，這就會導致一個調度周期內，低優(yōu)先級的應用可能一直無法響應，直到高優(yōu)先級應用結束。CFS調度器就是站在一視同仁的角度解決了這個問題，保證在一個調度周期內每個任務都有執(zhí)行的機會，執(zhí)行時間的長短，取決于任務的權重。下面詳細看下CFS調度器是如何動態(tài)調整任務的運行時間，達到公平調度的。

CFS 調度器

CFS是 Completely Fair Scheduler 簡稱，即完全公平調度器。CFS 調度器和以往的調度器不同之處在于沒有固定時間片的概念，而是公平分配 CPU 使用的時間。比如：2個優(yōu)先級相同的任務在一個 CPU 上運行，那么每個任務都將會分配一半的 CPU 運行時間，這就是要實現(xiàn)的公平。
但現(xiàn)實中，必然是有的任務優(yōu)先級高，有的任務優(yōu)先級低。CFS 調度器引入權重 weight 的概念，用 weight 代表任務的優(yōu)先級，各個任務按照 weight 的比例分配 CPU 的時間。比如：2個任務A和B，A的權重是1024，B的權重是2048，則A占 1024/(1024 2048) = 33.3% 的 CPU 時間，B占 2048/(1024 2048)=66.7% 的 CPU 時間。
在引入權重之后，分配給進程的時間計算公式如下：
實際運行時間 = 調度周期 * 進程權重 / 所有進程權重之和
CFS 調度器用nice值表示優(yōu)先級，取值范圍是[-20, 19]，nice和權重是一一對應的關系。數(shù)值越小代表優(yōu)先級越大，同時也意味著權重值越大，nice值和權重之間的轉換關系：
const int sched_prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/*  -5 */ 3121, 2501, 1991, 1586, 1277,
/*   0 */ 1024, 820, 655, 526, 423,
/*   5 */ 335, 272, 215, 172, 137,
/*  10 */ 110, 87, 70, 56, 45,
/*  15 */ 36, 29, 23, 18, 15,
};
數(shù)組值計算公式是：weight = 1024 / 1.25nice。

調度周期

如果一個 CPU 上有 N 個優(yōu)先級相同的進程，那么每個進程會得到 1/N 的執(zhí)行機會，每個進程執(zhí)行一段時間后，就被調出，換下一個進程執(zhí)行。如果這個 N 的數(shù)量太大，導致每個進程執(zhí)行的時間很短，就要調度出去，那么系統(tǒng)的資源就消耗在進程上下文切換上去了。
所以對于此問題在 CFS 中則引入了調度周期，使進程至少保證執(zhí)行0.75ms。調度周期的計算通過如下代碼：
static u64 __sched_period(unsigned long nr_running)
{
if (unlikely(nr_running > sched_nr_latency))
return nr_running * sysctl_sched_min_granularity;
else
return sysctl_sched_latency;
}

static unsigned int sched_nr_latency = 8;
unsigned int sysctl_sched_latency   = 6000000ULL;
unsigned int sysctl_sched_min_granularity   = 750000ULL;
當進程數(shù)目小于8時，則調度周期等于6ms。當進程數(shù)目大于8時，則調度周期等于進程的數(shù)目乘以0.75ms。

虛擬運行時間

根據(jù)上面進程實際運行時間的公式，可以看出，權重不同的2個進程的實際執(zhí)行時間是不相等的，但是 CFS 想保證每個進程運行時間相等，因此 CFS 引入了虛擬時間的概念。虛擬時間(vriture_runtime)和實際時間(wall_time)轉換公式如下：
vriture_runtime = (wall_time * NICE0_TO_weight) / weight
其中，NICE0_TO_weight 代表的是 nice 值等于0對應的權重，即1024，weight 是該任務對應的權重。
權重越大的進程獲得的虛擬運行時間越小，那么它將被調度器所調度的機會就越大，所以，CFS 每次調度原則是：總是選擇 vriture_runtime 最小的任務來調度。
為了能夠快速找到虛擬運行時間最小的進程，Linux 內核使用紅黑樹來保存可運行的進程。CFS跟蹤調度實體sched_entity的虛擬運行時間vruntime，將sched_entity通過enqueue_entity()和dequeue_entity()來進行紅黑樹的出隊入隊，vruntime少的調度實體sched_entity排列到紅黑樹的左邊。

如上圖所示，紅黑樹的左節(jié)點比父節(jié)點小，而右節(jié)點比父節(jié)點大。所以查找最小節(jié)點時，只需要獲取紅黑樹的最左節(jié)點即可。

相關步驟如下：

1. 每個sched_latency周期內，根據(jù)各個任務的權重值，可以計算出運行時間runtime；
2. 運行時間runtime可以轉換成虛擬運行時間vruntime；
3. 根據(jù)虛擬運行時間的大小，插入到CFS紅黑樹中，虛擬運行時間少的調度實體放置到左邊；

1. 在下一次任務調度的時候，選擇虛擬運行時間少的調度實體來運行。pick_next_task 函數(shù)就是從從就緒隊列中選擇最適合運行的調度實體，即虛擬時間最小的調度實體，下面我們看下 CFS 調度器如何通過 pick_next_task 的回調函數(shù) pick_next_task_fair 來選擇下一個進程的。

選擇下一個進程

pick_next_task_fair 會判斷上一個 task 的調度器是否是 CFS，這里我們默認都是 CFS 調度：

update_curr

update_curr 函數(shù)用來更新當前進程的運行時間信息:
static void update_curr(struct cfs_rq *cfs_rq)
{
struct sched_entity *curr = cfs_rq->curr;
u64 now = rq_clock_task(rq_of(cfs_rq));
u64 delta_exec;
if (unlikely(!curr))
return;
delta_exec = now - curr->exec_start;                  ------(1)
if (unlikely((s64)delta_exec <= 0))
return;
curr->exec_start = now;                               ------(2)
schedstat_set(curr->statistics.exec_max,
max(delta_exec, curr->statistics.exec_max));
curr->sum_exec_runtime  = delta_exec;                 ------(3)
schedstat_add(cfs_rq->exec_clock, delta_exec);
curr->vruntime  = calc_delta_fair(delta_exec, curr);  ------(4)
update_min_vruntime(cfs_rq);                          ------(5)
account_cfs_rq_runtime(cfs_rq, delta_exec);
}

1. delta_exec = now - curr->exec_start;  計算出當前CFS運行隊列的進程，距離上次更新虛擬時間的差值
2. curr->exec_start = now;  更新exec_start的值
3. curr->sum_exec_runtime = delta_exec; 更新當前進程總共執(zhí)行的時間
4. 通過 calc_delta_fair 計算當前進程虛擬時間
5. 通過 update_min_vruntime 函數(shù)來更新CFS運行隊列中最小的 vruntime 的值

pick_next_entity

pick_next_entity 函數(shù)會從就緒隊列中選擇最適合運行的調度實體（虛擬時間最小的調度實體），即從 CFS 紅黑樹最左邊節(jié)點獲取一個調度實體。
static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
struct sched_entity *left = __pick_first_entity(cfs_rq); ------(1)
struct sched_entity *se;

/*
* If curr is set we have to see if its left of the leftmost entity
* still in the tree, provided there was anything in the tree at all.
*/
if (!left || (curr