進(jìn)程的分類

在 CPU 的角度看進(jìn)程行為的話，可以分為兩類：

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

CPU 消耗型進(jìn)程需要高的吞吐率，IO 消耗型進(jìn)程需要強的響應(yīng)性，這兩點都是調(diào)度器需要考慮的。

為了更快響應(yīng) IO 消耗型進(jìn)程，內(nèi)核提供了一個搶占(preempt)機制，使優(yōu)先級更高的進(jìn)程，去搶占優(yōu)先級低的進(jìn)程運行。內(nèi)核用以下宏來選擇內(nèi)核是否打開搶占機制：

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

調(diào)度相關(guān)的數(shù)據(jù)結(jié)構(gòu)

先來看幾個相關(guān)的數(shù)據(jù)結(jié)構(gòu)：

task_struct

我們先把 task_struct 中和調(diào)度相關(guān)的結(jié)構(gòu)拎出來：

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：對調(diào)度器進(jìn)行抽象，一共分為5類。

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

unsigned int policy：進(jìn)程的調(diào)度策略有6種，用戶可以調(diào)用調(diào)度器里的不同調(diào)度策略。

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

struct sched_entity se：采用CFS算法調(diào)度的普通非實時進(jìn)程的調(diào)度實體。
struct sched_rt_entity rt：采用Roound-Robin或者FIFO算法調(diào)度的實時調(diào)度實體。
struct sched_dl_entity dl：采用EDF算法調(diào)度的實時調(diào)度實體。

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

runqueue 運行隊列

runqueue 運行隊列是本 CPU 上所有可運行進(jìn)程的隊列集合。每個 CPU 都有一個運行隊列，每個運行隊列中有三個調(diào)度隊列，task 作為調(diào)度實體加入到各自的調(diào)度隊列中。

struct rq {
 ......
 struct cfs_rq cfs;
 struct rt_rq rt;
 struct dl_rq dl;
 ......
}

三個調(diào)度隊列：

struct cfs_rq cfs：CFS調(diào)度隊列
struct rt_rq rt：RT調(diào)度隊列
struct dl_rq dl：DL調(diào)度隊列

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

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

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

struct sched_entity {
  ...
  struct rb_node    run_node;      
  ...
  u64          vruntime;              
  ...
};

這些數(shù)據(jù)結(jié)構(gòu)的關(guān)系如下圖所示：

調(diào)度時刻

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

1. 設(shè)置調(diào)度標(biāo)記

為 CPU 上正在運行的進(jìn)程 thread_info 結(jié)構(gòu)體里的 flags 成員設(shè)置 TIF_NEED_RESCHED。

那么，什么時候設(shè)置TIF_NEED_RESCHED呢？

scheduler_tick 時鐘中斷

wake_up_process 喚醒進(jìn)程的時候

do_fork 創(chuàng)建新進(jìn)程的時候

set_user_nice 修改進(jìn)程nice值的時候

smp_send_reschedule 負(fù)載均衡的時候

【文章福利】需要C/C++ linux服務(wù)器架構(gòu)師學(xué)習(xí)資料加群812855908（資料包括C/C++，Linux，golang技術(shù)，內(nèi)核，Nginx，ZeroMQ，MySQL，redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協(xié)程，DPDK，ffmpeg等）

2. 執(zhí)行調(diào)度

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

用戶態(tài)搶占

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

內(nèi)核態(tài)搶占

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

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

調(diào)度算法

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

O(n)

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

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

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

O(1)

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

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

CFS 調(diào)度器

CFS是 Completely Fair Scheduler 簡稱，即完全公平調(diào)度器。CFS 調(diào)度器和以往的調(diào)度器不同之處在于沒有固定時間片的概念，而是公平分配 CPU 使用的時間。比如：2個優(yōu)先級相同的任務(wù)在一個 CPU 上運行，那么每個任務(wù)都將會分配一半的 CPU 運行時間，這就是要實現(xiàn)的公平。

但現(xiàn)實中，必然是有的任務(wù)優(yōu)先級高，有的任務(wù)優(yōu)先級低。CFS 調(diào)度器引入權(quán)重 weight 的概念，用 weight 代表任務(wù)的優(yōu)先級，各個任務(wù)按照 weight 的比例分配 CPU 的時間。比如：2個任務(wù)A和B，A的權(quán)重是1024，B的權(quán)重是2048，則A占 1024/(1024+2048) = 33.3% 的 CPU 時間，B占 2048/(1024+2048)=66.7% 的 CPU 時間。

在引入權(quán)重之后，分配給進(jìn)程的時間計算公式如下：

實際運行時間 = 調(diào)度周期 * 進(jìn)程權(quán)重 / 所有進(jìn)程權(quán)重之和

CFS 調(diào)度器用nice值表示優(yōu)先級，取值范圍是[-20, 19]，nice和權(quán)重是一一對應(yīng)的關(guān)系。數(shù)值越小代表優(yōu)先級越大，同時也意味著權(quán)重值越大，nice值和權(quán)重之間的轉(zhuǎn)換關(guān)系：

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。

調(diào)度周期

如果一個 CPU 上有 N 個優(yōu)先級相同的進(jìn)程，那么每個進(jìn)程會得到 1/N 的執(zhí)行機會，每個進(jìn)程執(zhí)行一段時間后，就被調(diào)出，換下一個進(jìn)程執(zhí)行。如果這個 N 的數(shù)量太大，導(dǎo)致每個進(jìn)程執(zhí)行的時間很短，就要調(diào)度出去，那么系統(tǒng)的資源就消耗在進(jìn)程上下文切換上去了。

所以對于此問題在 CFS 中則引入了調(diào)度周期，使進(jìn)程至少保證執(zhí)行0.75ms。調(diào)度周期的計算通過如下代碼：

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;

當(dāng)進(jìn)程數(shù)目小于8時，則調(diào)度周期等于6ms。當(dāng)進(jìn)程數(shù)目大于8時，則調(diào)度周期等于進(jìn)程的數(shù)目乘以0.75ms。

虛擬運行時間

根據(jù)上面進(jìn)程實際運行時間的公式，可以看出，權(quán)重不同的2個進(jìn)程的實際執(zhí)行時間是不相等的，但是 CFS 想保證每個進(jìn)程運行時間相等，因此 CFS 引入了虛擬時間的概念。虛擬時間(vriture_runtime)和實際時間(wall_time)轉(zhuǎn)換公式如下：

vriture_runtime = (wall_time * NICE0_TO_weight) / weight

其中，NICE0_TO_weight 代表的是 nice 值等于0對應(yīng)的權(quán)重，即1024，weight 是該任務(wù)對應(yīng)的權(quán)重。

權(quán)重越大的進(jìn)程獲得的虛擬運行時間越小，那么它將被調(diào)度器所調(diào)度的機會就越大，所以，CFS 每次調(diào)度原則是：總是選擇 vriture_runtime 最小的任務(wù)來調(diào)度。

為了能夠快速找到虛擬運行時間最小的進(jìn)程，Linux 內(nèi)核使用紅黑樹來保存可運行的進(jìn)程。CFS跟蹤調(diào)度實體sched_entity的虛擬運行時間vruntime，將sched_entity通過enqueue_entity()和dequeue_entity()來進(jìn)行紅黑樹的出隊入隊，vruntime少的調(diào)度實體sched_entity排列到紅黑樹的左邊。

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

相關(guān)步驟如下：

每個sched_latency周期內(nèi)，根據(jù)各個任務(wù)的權(quán)重值，可以計算出運行時間runtime；
運行時間runtime可以轉(zhuǎn)換成虛擬運行時間vruntime；
根據(jù)虛擬運行時間的大小，插入到CFS紅黑樹中，虛擬運行時間少的調(diào)度實體放置到左邊；

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

選擇下一個進(jìn)程

pick_next_task_fair 會判斷上一個 task 的調(diào)度器是否是 CFS，這里我們默認(rèn)都是 CFS 調(diào)度：

update_curr

update_curr 函數(shù)用來更新當(dāng)前進(jìn)程的運行時間信息:

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);
}

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

pick_next_entity

pick_next_entity 函數(shù)會從就緒隊列中選擇最適合運行的調(diào)度實體（虛擬時間最小的調(diào)度實體），即從 CFS 紅黑樹最左邊節(jié)點獲取一個調(diào)度實體。

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 && entity_before(curr, left)))
  left = curr;

 se = left; /* ideally we run the leftmost entity */

 /*
  * Avoid running the skip buddy, if running something else can
  * be done without getting too unfair.
  */
 if (cfs_rq->skip == se) {
  struct sched_entity *second;

  if (se == curr) {
   second = __pick_first_entity(cfs_rq);                   ------(2)
  } else {
   second = __pick_next_entity(se);                        ------(3)
   if (!second || (curr && entity_before(curr, second)))
    second = curr;
  }

  if (second && wakeup_preempt_entity(second, left) < 1)
   se = second;
 }

 /*
  * Prefer last buddy, try to return the CPU to a preempted task.
  */
 if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
  se = cfs_rq->last;

 /*
  * Someone really wants this to run. If it's not unfair, run it.
  */
 if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
  se = cfs_rq->next;

 clear_buddies(cfs_rq, se);

 return se;
}

從樹中挑選出最左邊的節(jié)點
選擇最左的那個調(diào)度實體 left
摘取紅黑樹上第二左的進(jìn)程節(jié)點

put_prev_entity

put_prev_entity 會調(diào)用 __enqueue_entity 將prev進(jìn)程(即current進(jìn)程)加入到 CFS 隊列 rq 上的紅黑樹，然后將 cfs_rq->curr 設(shè)置為空。

static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
 struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node; //紅黑樹根節(jié)點
 struct rb_node *parent = NULL;
 struct sched_entity *entry;
 bool leftmost = true;

 /*
  * Find the right place in the rbtree:
  */
 while (*link) {                                ------(1)
  parent = *link;
  entry = rb_entry(parent, struct sched_entity, run_node);
  /*
   * We dont care about collisions. Nodes with
   * the same key stay together.
   */
  if (entity_before(se, entry)) {              ------(2)
   link = &parent->rb_left;
  } else {
   link = &parent->rb_right;
   leftmost = false;
  }
 }
  
 rb_link_node(&se->run_node, parent, link);     ------(3)
 rb_insert_color_cached(&se->run_node,          ------(4)
          &cfs_rq->tasks_timeline, leftmost);
}

從紅黑樹中找到 se 所應(yīng)該在的位置
以 se->vruntime 值為鍵值進(jìn)行紅黑樹結(jié)點的比較
將新進(jìn)程的節(jié)點加入到紅黑樹中
為新插入的結(jié)點進(jìn)行著色

set_next_entity

set_next_entity 會調(diào)用 __dequeue_entity 將下一個選擇的進(jìn)程從 CFS 隊列的紅黑樹中刪除，然后將 CFS 隊列的 curr 指向進(jìn)程的調(diào)度實體。

進(jìn)程上下文切換

理解了下一個進(jìn)程的選擇后，就需要做當(dāng)前進(jìn)程和所選進(jìn)程的上下文切換。

Linux 內(nèi)核用函數(shù) context_switch 進(jìn)行進(jìn)程的上下文切換，進(jìn)程上下文切換主要涉及到兩部分：進(jìn)程地址空間切換和處理器狀態(tài)切換：

進(jìn)程的地址空間切換

將下一個進(jìn)程的 pgd 虛擬地址轉(zhuǎn)化為物理地址存放在 ttbr0_el1 中(這是用戶空間的頁表基址寄存器)，當(dāng)訪問用戶空間地址的時候 mmu 會通過這個寄存器來做遍歷頁表獲得物理地址。完成了這一步，也就完成了進(jìn)程的地址空間切換，確切的說是進(jìn)程的虛擬地址空間切換。

寄存器狀態(tài)切換

其中 x19-x28 是 arm64 架構(gòu)規(guī)定需要調(diào)用保存的寄存器，可以看到處理器狀態(tài)切換的時候?qū)⑶耙粋€進(jìn)程（prev）的 x19-x28，fp,sp,pc 保存到了進(jìn)程描述符的 cpu_contex 中，然后將即將執(zhí)行的進(jìn)程 (next) 描述符的 cpu_contex 的 x19-x28，fp,sp,pc 恢復(fù)到相應(yīng)寄存器中，而且將 next 進(jìn)程的進(jìn)程描述符 task_struct 地址存放在 sp_el0 中，用于通過 current 找到當(dāng)前進(jìn)程，這樣就完成了處理器的狀態(tài)切換。