進程的分類

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

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

CPU 消耗型進程需要高的吞吐率，IO 消耗型進程需要強的響應性，這兩點都是調度器需要考慮的。

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

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

調度相關的數據結構

先來看幾個相關的數據結構：

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類。

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

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

SCHED_DEADLINE：使task選擇Deadline調度器來調度運行
SCHED_RR：時間片輪轉，進程用完時間片后加入優先級對應運行隊列的尾部，把CPU讓給同優先級的其他進程；
SCHED_FIFO：先進先出調度沒有時間片，沒有更高優先級的情況下，只能等待主動讓出CPU；
SCHED_NORMAL：使task選擇CFS調度器來調度運行；
SCHED_BATCH：批量處理，使task選擇CFS調度器來調度運行；
SCHED_IDLE：使task以最低優先級選擇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：跟蹤就緒隊列信息以及管理就緒態調度實體，并維護一棵按照虛擬時間排序的紅黑樹。tasks_timeline->rb_root是紅黑樹的根，tasks_timeline->rb_leftmost指向紅黑樹中最左邊的調度實體，即虛擬時間最小的調度實體。

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

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

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

這些數據結構的關系如下圖所示：

調度時刻

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

1. 設置調度標記

為 CPU 上正在運行的進程 thread_info 結構體里的 flags 成員設置 TIF_NEED_RESCHED。

那么，什么時候設置TIF_NEED_RESCHED呢？

scheduler_tick 時鐘中斷

wake_up_process 喚醒進程的時候

do_fork 創建新進程的時候

set_user_nice 修改進程nice值的時候

smp_send_reschedule 負載均衡的時候

【文章福利】需要C/C++ linux服務器架構師學習資料加群812855908（資料包括C/C++，Linux，golang技術，內核，Nginx，ZeroMQ，MySQL，redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協程，DPDK，ffmpeg等）

2. 執行調度

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

用戶態搶占

ret_to_user 是異常觸發，系統調用，中斷處理完成后都會調用的函數。

內核態搶占

可以看出無論是用戶態搶占，還是內核態搶占，最終都會調用 schedule 函數來執行真正的調度：

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

調度算法

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

O(n)

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

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

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

O(1)

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

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

CFS 調度器

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

但現實中，必然是有的任務優先級高，有的任務優先級低。CFS 調度器引入權重 weight 的概念，用 weight 代表任務的優先級，各個任務按照 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值表示優先級，取值范圍是[-20, 19]，nice和權重是一一對應的關系。數值越小代表優先級越大，同時也意味著權重值越大，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,
};

數組值計算公式是：weight = 1024 / 1.25nice。

調度周期

如果一個 CPU 上有 N 個優先級相同的進程，那么每個進程會得到 1/N 的執行機會，每個進程執行一段時間后，就被調出，換下一個進程執行。如果這個 N 的數量太大，導致每個進程執行的時間很短，就要調度出去，那么系統的資源就消耗在進程上下文切換上去了。

所以對于此問題在 CFS 中則引入了調度周期，使進程至少保證執行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;

當進程數目小于8時，則調度周期等于6ms。當進程數目大于8時，則調度周期等于進程的數目乘以0.75ms。

虛擬運行時間

根據上面進程實際運行時間的公式，可以看出，權重不同的2個進程的實際執行時間是不相等的，但是 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排列到紅黑樹的左邊。

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

相關步驟如下：

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

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

選擇下一個進程

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

update_curr

update_curr 函數用來更新當前進程的運行時間信息:

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; 計算出當前CFS運行隊列的進程，距離上次更新虛擬時間的差值
curr->exec_start = now; 更新exec_start的值
curr->sum_exec_runtime += delta_exec; 更新當前進程總共執行的時間
通過 calc_delta_fair 計算當前進程虛擬時間
通過 update_min_vruntime 函數來更新CFS運行隊列中最小的 vruntime 的值

pick_next_entity

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

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

從樹中挑選出最左邊的節點
選擇最左的那個調度實體 left
摘取紅黑樹上第二左的進程節點

put_prev_entity

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

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; //紅黑樹根節點
 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 所應該在的位置
以 se->vruntime 值為鍵值進行紅黑樹結點的比較
將新進程的節點加入到紅黑樹中
為新插入的結點進行著色

set_next_entity

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

進程上下文切換

理解了下一個進程的選擇后，就需要做當前進程和所選進程的上下文切換。

Linux 內核用函數 context_switch 進行進程的上下文切換，進程上下文切換主要涉及到兩部分：進程地址空間切換和處理器狀態切換：

進程的地址空間切換

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

寄存器狀態切換

其中 x19-x28 是 arm64 架構規定需要調用保存的寄存器，可以看到處理器狀態切換的時候將前一個進程（prev）的 x19-x28，fp,sp,pc 保存到了進程描述符的 cpu_contex 中，然后將即將執行的進程 (next) 描述符的 cpu_contex 的 x19-x28，fp,sp,pc 恢復到相應寄存器中，而且將 next 進程的進程描述符 task_struct 地址存放在 sp_el0 中，用于通過 current 找到當前進程，這樣就完成了處理器的狀態切換。