基於Linux 4.5的進程模型與排程器分析

2020-06-16 16:52:22

1.作業系統是怎麼組織進程的？

　　1.1什麼是執行緒，什麼是進程:

　　　　剛接觸時可能經常會將這兩個東西搞混。簡單一點的說，進程是一個大工程，執行緒則是這個大工程中每個小地方需要做的東西(在linux下看作"輕量級進程"):

　　　　例如當你開啟QQ微信，這時系統啟動了一個進程。然後你開始看別人發的訊息，這時啟動了一個執行緒用來傳輸文字，如果發了一段語音，這也會啟動一個執行緒來傳輸語音......(當然一個程式並不代表一定只有一個進程)

　　1.2進程核心棧與thread_info(用於儲存進、執行緒及其資訊等):

struct task_struct {
......

/* 指向進程核心棧 */
void *stack;

......
};

1 union thread_union {
2 struct thread_info thread_info;
3 unsigned long stack[THREAD_SIZE/sizeof(long)]; /*核心態的進程堆疊*/
4 };

/*執行緒描述符(linux4.5 x86架構)*/
/*typedef unsigned int __u32*/
struct thread_info {
struct task_struct *task; /* 儲存進(線)程的資訊 */
__u32 　　flags; /* 進程標記 */
__u32 　　status; /* 執行緒狀態 */
__u32 　　cpu; /* current CPU */
mm_segment_t addr_limit;
unsigned int sig_on_uaccess_error:1;
unsigned int uaccess_err:1; /* uaccess failed */
};

進程在核心態執行時需要自己的堆疊資訊, 因此linux核心為每個進程都提供了一個核心棧kernel stack;
核心還需要儲存每個進程的PCB資訊, linux核心是支援不同體系的的, 但是不同的體系結構可能進程需要儲存的資訊不盡相同, 這就需要我們實現一種通用的方式, 我們將體系結構相關的部分和無關的部門進行分離;
linux將核心棧和thread_info融合在一起, 組成一個聯合體thread_union。(下圖左塊)

　　　由上圖(左大塊為"進程核心棧", 右塊為"進程描述符")所示，進程的核心棧是向下增長的，也就是棧底在高位地址，棧頂在低位地址，thread_info在進程核心棧的最低處。其中可總結出:

esp暫存器為CPU棧指標，用來存放棧頂單元的地址。當資料寫入時，esp的值減少;
thread_info和核心棧雖然共用了thread_union結構, 但是thread_info大小固定, 儲存在聯合體的開始部分, 而核心棧由高地址向低地址擴充套件, 當核心棧的棧頂到達thread_info的儲存空間時, 則會發生棧溢位(核心中有kstack_end函數判斷);
系統的current指標指向了當前執行進程的thread_union(或者thread_info)的地址;

　　　其中在早期的Linux核心中使用struct thread_info *thread_info，而之後的新版本(2.6.22後)中用進程task_struct中的stack指標指向了進程的thread_union(或者thread_info)的地址來代替thread_info指標，因為聯合體中stack和thread_info都在起始地址, 因此可以很方便的轉型:

#define task_thread_info(task) ((struct thread_info *)(task)->stack)

　　1.3進程標示符PID:

struct task_struct {
........

/* 進程ID，每個進程(執行緒)的PID都不同 */
pid_t pid;
/* 執行緒組ID，同一個執行緒組擁有相同的pid，與領頭執行緒(該組中第一個輕量級進程)pid一致，儲存在tgid中，執行緒組領頭執行緒的pid和tgid相同 */
pid_t tgid;
/* 用於連線到PID、TGID、PGRP、SESSION雜湊表 */
struct pid_link pids[PIDTYPE_MAX];
/*PID : 進程的ID(Process Identifier),對應pids[PIDTYPE_PID]
*TGID : 執行緒組ID(Thread Group Identifier),對應pids[PIDTYPE_TGID]
*PGRP : 行程群組(Process Group),對應pids[PIDTYPE_PGID]
*SESSION : 對談(Session),對應pids[PIDTYPE_SID]
*/

........
};

　　　　PID就像我們學生的學號，每個人的身份證號一樣，是獨一無二的。而我們會有一個群體，比如同一個班級，同一個學校等，即有同一個群組，因此建立了TGID，用來將同一個組的PID串聯起來。其中getpid()返回當前進程的tgid值而不是pid的值。

　　　　而在系統執行的時候，可能會建立非常非常多的進程，因此為了提高核心的查詢效率，專門建立了四個hash表pids[PIDTYPE_TGID]、pids[PIDTYPE_TGID]、pids[PIDTYPE_PGID]、pids[PIDTYPE_SID]用來索引。

　　　　在核心中，這四個雜湊表一共佔16個頁框，也就是每個雜湊表佔4個頁框，他們每個可以擁有2048個表項，核心會把把這四個雜湊表的地址儲存到pid_hash陣列中。現在問題來了，拿pids[PIDTYPE_TGID]為例，怎麼在2048個表項中儲存32767個PID值，其實核心會對每個已經分配的PID值進行一個處理，得到的結果的數值就是對應的表項，處理結果相同的PID被串成一個連結串列，如下：

　　　　當我們使用"kill 29384"命令時，核心會根據29384處理得出199，然後以199為下標，獲取PID雜湊表中對應的連結串列頭，並在此連結串列中找出PID=29384的進程。在進程描述符(thread_info)的*task中使用struct pid_link pids[PIDTYPE_MAX]鏈入這四個雜湊表。對於另外三個雜湊表，道理一樣。

　　1.4進程狀態的轉換:

　　　　進程的狀態用state表示，簡單表示有以下3種:

volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */

　　　　其中詳細有以下狀態:

/*
* Task state bitmask. NOTE! These bits are also
* encoded in fs/proc/array.c: get_task_state().
*
* We have two separate sets of flags: task->state
* is about runnability, while task->exit_state are
* about the task exiting. Confusing, but this way
* modifying one set can't modify the other one by
* mistake.
*/
#define TASK_RUNNING 0
#define TASK_INTERRUPTIBLE 1
#define TASK_UNINTERRUPTIBLE 2
#define __TASK_STOPPED 4
#define __TASK_TRACED 8

/* in tsk->exit_state */
#define EXIT_DEAD 16
#define EXIT_ZOMBIE 32
#define EXIT_TRACE (EXIT_ZOMBIE | EXIT_DEAD)

/* in tsk->state again */
#define TASK_DEAD 64
#define TASK_WAKEKILL 128 /** wake on signals that are deadly **/
#define TASK_WAKING 256
#define TASK_PARKED 512
#define TASK_NOLOAD 1024
#define TASK_STATE_MAX 2048

/* Convenience macros for the sake of set_task_state */
#define TASK_KILLABLE (TASK_WAKEKILL | TASK_UNINTERRUPTIBLE)
#define TASK_STOPPED (TASK_WAKEKILL | __TASK_STOPPED)
#define TASK_TRACED (TASK_WAKEKILL | __TASK_TRACED)

1.4.1五種互斥狀態:　　　　　　

state域能夠取5個互為排斥的值（簡單來說就是這五個值任意兩個不能一起使用，只能單獨使用）:

狀態	描述
TASK_RUNNING	表示進程要麼正在執行，要麼正要準備執行（已經就緒），正在等待cpu時間片的排程
TASK_INTERRUPTIBLE	進程因為等待一些條件而被掛起（阻塞）而所處的狀態。這些條件主要包括：硬中斷、資源、一些信號……，一旦等待的條件成立，進程就會從該狀態（阻塞）迅速轉化成為就緒狀態TASK_RUNNING
TASK_UNINTERRUPTIBLE	意義與TASK_INTERRUPTIBLE類似，除了不能通過接受一個信號來喚醒以外，對於處於TASK_UNINTERRUPIBLE狀態的進程，哪怕我們傳遞一個信號或者有一個外部中斷都不能喚醒他們。只有它所等待的資源可用的時候，他才會被喚醒。這個標誌很少用，但是並不代表沒有任何用處，其實他的作用非常大，特別是對於驅動刺探相關的硬體過程很重要，這個刺探過程不能被一些其他的東西給中斷，否則就會讓進城進入不可預測的狀態
TASK_STOPPED	進程被停止執行，當進程接收到SIGSTOP、SIGTTIN、SIGTSTP或者SIGTTOU信號之後就會進入該狀態
TASK_TRACED	表示進程被debugger等進程監視，進程執行被偵錯程式所停止，當一個進程被另外的進程所監視，每一個信號都會讓進城進入該狀態

　1.4.2二種終止狀態:　　　　　　

　　　　　　這兩個附加的進程狀態既可以被新增到state域中，又可以被新增到exit_state域中。只有當進程終止的時候，才會達到這兩種狀態:

狀態	描述
EXIT_ZOMBIE	進程的執行被終止，但是其父進程還沒有使用wait()等系統呼叫來獲知它的終止資訊，此時進程成為殭屍進程
EXIT_DEAD	進程的最終狀態

　　　　1.4.3睡眠狀態:　　　　　　

　　　　　　正常只需將state域的值設為以下兩種狀態就可進入睡眠狀態:

狀態	描述
TASK_INTERRUPTIBLE	進程處於睡眠狀態，正在等待某些事件發生。進程可以被信號中斷。接收到信號或被顯式的喚醒呼叫喚醒之後，進程將轉變為 TASK_RUNNING 狀態。
TASK_UNINTERRUPTIBLE	此進程狀態類似於 TASK_INTERRUPTIBLE，只是它不會處理信號。中斷處於這種狀態的進程是不合適的，因為它可能正在完成某些重要的任務。當它所等待的事件發生時，進程將被顯式的喚醒呼叫喚醒。

　　　　　　而在Linux2.6.25以後，新增了一條睡眠狀態 : “TASK_KILLABLE”:

狀態	描述
TASK_KILLABLE	當進程處於這種可以終止的新睡眠狀態中，它的執行原理類似於 `TASK_UNINTERRUPTIBLE`，只不過可以響應致命信號。

　　　　　　由程式碼的line 31可以看出，TASK_UNINTERRUPTIBLE + TASK_WAKEKILL = TASK_KILLABLE。

　　1.4.4進程轉換圖:

　　　　

　　因此，通過對以上資料的操作，作業系統便可以對進程進行組織和管理。

2.進程是怎麼被排程的？

　　2.1什麼是排程器?　　　　

　　　　一台個人電腦，最直觀的資源便是你的硬碟、磁碟、記憶體等等，但其實CPU也是一個資源，每個程式在跑的時候都需要佔用CPU一定時間。因此，如何讓每個程式合理、公平地跑一定的時間，是一個很重要的問題，需要設計一個專門的地方去分配，這就是排程器。排程器的一個重要目標是有效地分配 CPU 時間片，同時提供很好的使用者體驗。排程器還需要面對一些互相衝突的目標，例如既要為關鍵實時任務最小化響應時間, 又要最大限度地提高 CPU 的總體利用率。

　　2.2進程的分類.

　　　　當涉及有關排程的問題時, 傳統上把進程分類為”I/O受限(I/O-dound)”或”CPU受限(CPU-bound)”.

型別	別稱	描述	範例
I/O受限型	I/O密集型	頻繁的使用I/O裝置, 並花費很多時間等待I/O操作的完成	資料庫伺服器, 文字編輯器
CPU受限型	計算密集型	花費大量CPU時間進行數值計算	圖形繪製程式

　　　　另外一種分類法把進程區分為三類:

型別	描述	範例
互動式進程(interactive process)	此類進程經常與使用者進行互動, 因此需要花費很多時間等待鍵盤和滑鼠操作. 當接受了使用者的輸入後, 進程必須很快被喚醒, 否則使用者會感覺系統反應遲鈍	shell, 文字編輯程式和圖形應用程式
批次處理進程(batch process)	此類進程不必與使用者互動, 因此經常在後台執行. 因為這樣的進程不必很快相應, 因此常受到排程程式的怠慢	程式語言的編譯程式, 資料庫搜尋引擎以及科學計算
實時進程(real-time process)	這些進程由很強的排程需要, 這樣的進程絕不會被低優先順序的進程阻塞. 並且他們的響應時間要盡可能的短	視訊音訊應用程式, 機器人控制程式以及從物理感測器上收集資料的程式

　　2.3排程器的演變.

　　　　一開始的排程器是複雜度為 $O (n)$ 然而，linux是集全球很多程式設計師的聰明才智而發展起來的超級核心，沒有最好，只有更好，在 $O (1)$

排程器	Linux版本
O(n)的始排程演算法	linux-0.11~2.4
O(1)排程器	linux-2.5
CFS排程器	linux-2.6~至今

　　2.4排程器的設計.

　　　　Linux的2種排程器:

排程器	描述
主排程器	直接根據進程的狀態進行排程，比如當其打算睡眠或出於其他原因放棄佔用CPU時
周期排程器	通過周期性的機制, 以固定的頻率執行, 不時地去檢測是否有必要進行排程

　　　　其中這兩者統稱為通用排程器(generic scheduler)或核心排程器(core scheduler)。

　　　　每個排程器包括兩個內容：排程框架(其實質就是兩個函數框架)及排程器類。

　　　　Linux的6種排程策略:

排程策略	描述	所在排程器類
SCHED_NORMAL	（也叫SCHED_OTHER）用於普通進程，通過CFS排程器實現。SCHED_BATCH用於非互動的處理器消耗型進程。SCHED_IDLE是在系統負載很低時使用	CFS
SCHED_BATCH	SCHED_NORMAL普通進程策略的分化版本。採用分時策略，根據動態優先順序(可用nice()API設定），分配CPU運算資源。注意：這類進程比上述兩類實時進程優先順序低，換言之，在有實時進程存在時，實時進程優先排程。但針對吞吐量優化, 除了不能搶占外與常規任務一樣，允許任務執行更長時間，更好地使用快取記憶體，適合於成批次處理的工作	CFS
SCHED_IDLE	優先順序最低，在系統空閒時才跑這類進程(如利用閒散計算機資源跑地外文明搜尋，蛋白質結構分析等任務，是此排程策略的適用者）	CFS-IDLE
SCHED_FIFO	先入先出排程演算法（實時排程策略），相同優先順序的任務先到先服務，高優先順序的任務可以搶占低優先順序的任務	RT
SCHED_RR	輪流排程演算法（實時排程策略），後者提供 Roound-Robin 語意，採用時間片，相同優先順序的任務當用完時間片會被放到佇列尾部，以保證公平性，同樣，高優先順序的任務可以搶占低優先順序的任務。不同要求的實時任務可以根據需要用sched_setscheduler() API設定策略	RT
SCHED_DEADLINE	新支援的實時進程排程策略，針對突發型計算，且對延遲和完成時間高度敏感的任務適用。基於Earliest Deadline First (EDF) 排程演算法	DL

　　　　Linux的5種排程類:

排程器類	描述	對應排程策略
stop_sched_class	優先順序最高的執行緒，會中斷所有其他執行緒，且不會被其他任務打斷作用 1.發生在cpu_stop_cpu_callback 進行cpu之間任務migration 2.HOTPLUG_CPU的情況下關閉任務	無, 不需要排程普通進程
dl_sched_class	採用EDF最早截至時間優先演算法排程實時進程	SCHED_DEADLINE
rt_sched_class	採用提供 Roound-Robin演算法或者FIFO演算法排程實時進程具體排程策略由進程的task_struct->policy指定	SCHED_FIFO, SCHED_RR
fair_sched_clas	採用CFS演算法排程普通的非實時進程	SCHED_NORMAL, SCHED_BATCH
idle_sched_class	採用CFS演算法排程idle進程, 每個cup的第一個pid=0執行緒：swapper，是一個靜態執行緒。排程類屬於：idel_sched_class，所以在ps裡面是看不到的。一般執行在開機過程和cpu異常的時候做dump	SCHED_IDLE

其所屬進程的優先順序順序為:

stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class

Linux的3種排程實體:

排程器不限於排程進程, 還可以排程更大的實體, 比如實現組排程: 可用的CPUI時間首先在一半的行程群組(比如, 所有進程按照所有者分組)之間分配, 接下來分配的時間再在組內進行二次分配，這種一般性要求排程器不直接操作進程, 而是處理可排程實體, 因此需要一個通用的資料結構描述這個排程實體,即seched_entity結構, 其實際上就代表了一個排程物件，可以為一個進程，也可以為一個行程群組。linux中針對當前可排程的實時和非實時進程, 定義了型別為seched_entity的3個排程實體:

排程實體	名稱	描述	對應排程器類
sched_dl_entity	DEADLINE排程實體	採用EDF演算法排程的實時排程實體	dl_sched_class
sched_rt_entity	RT排程實體	採用Roound-Robin或者FIFO演算法排程的實時排程實體	rt_sched_class
sched_entity	CFS排程實體	採用CFS演算法排程的普通非實時進程的排程實體	fair_sched_class

　　2.5CFS排程器.

　　　　CFS完全公平排程器的排程器類叫fair_sched_class，下面是linux 4.5中的資料結構:

/*
* All the scheduling class methods:
*/
const struct sched_class fair_sched_class = {
.next = &idle_sched_class,
.enqueue_task = enqueue_task_fair,
.dequeue_task = dequeue_task_fair,
.yield_task = yield_task_fair,
.yield_to_task = yield_to_task_fair,

.check_preempt_curr = check_preempt_wakeup,

.pick_next_task = pick_next_task_fair,
.put_prev_task = put_prev_task_fair,

#ifdef CONFIG_SMP
.select_task_rq = select_task_rq_fair,
.migrate_task_rq = migrate_task_rq_fair,

.rq_online = rq_online_fair,
.rq_offline = rq_offline_fair,

.task_waking = task_waking_fair,
.task_dead = task_dead_fair,
.set_cpus_allowed = set_cpus_allowed_common,
#endif

.set_curr_task = set_curr_task_fair,
.task_tick = task_tick_fair,
.task_fork = task_fork_fair,

.prio_changed = prio_changed_fair,
.switched_from = switched_from_fair,
.switched_to = switched_to_fair,

.get_rr_interval = get_rr_interval_fair,

.update_curr = update_curr_fair,

#ifdef CONFIG_FAIR_GROUP_SCHED
.task_move_group = task_move_group_fair,
#endif
};

其中一些成員變數的含義為:

成員	描述
next	下個優先順序的排程類, 讓所有的排程類通過next連結在一個連結串列中
enqueue_task	向就緒佇列中新增一個進程, 某個任務進入可執行狀態時，該函數將得到呼叫。它將排程實體（進程）放入紅黑樹中，並對 nr_running 變數加 1
dequeue_task	將一個進程從就就緒佇列中刪除, 當某個任務退出可執行狀態時呼叫該函數，它將從紅黑樹中去掉對應的排程實體，並從 nr_running 變數中減 1
yield_task	在進程想要資源放棄對處理器的控制權的時, 可使用在sched_yield系統呼叫, 會呼叫核心API yield_task完成此工作. compat_yield sysctl 關閉的情況下，該函數實際上執行先出隊後入隊；在這種情況下，它將排程實體放在紅黑樹的最右端
check_preempt_curr	該函數將檢查當前執行的任務是否被搶占。在實際搶占正在執行的任務之前，CFS 排程程式模組將執行公平性測試。這將驅動喚醒式（wakeup）搶占
pick_next_task	該函數選擇接下來要執行的最合適的進程
put_prev_task	用另一個進程代替當前執行的進程
set_curr_task	當任務修改其排程類或修改其任務組時，將呼叫這個函數
task_tick	在每次啟用周期排程器時, 由周期性排程器呼叫, 該函數通常呼叫自 time tick 函數；它可能引起進程切換。這將驅動執行時（running）搶占
task_fork	核心排程程式為排程模組提供了管理新任務啟動的機會, 用於建立fork系統呼叫和排程器之間的關聯, 每次新進程建立後, 則用new_task通知排程器, CFS 排程模組使用它進行組排程，而用於實時任務的排程模組則不會使用這個函數

　　　　CFS的就緒佇列:

struct cfs_rq {
struct load_weight load;/*CFS佇列中所有進程的總負載*/
unsigned int nr_running, h_nr_running;

u64 exec_clock;/**/
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).
*/
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
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;
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 */
};

一些成員變數的含義:

成員	描述
nr_running	佇列上可執行進程的數目
h_nr_running	只對行程群組有效，其下所有行程群組中cfs_rq的nr_running總和
load	就緒佇列上可執行進程的累計負荷權重(總負載)
min_vruntime	跟蹤記錄佇列上所有進程的最小虛擬執行時間. 這個值是實現與就緒佇列相關的虛擬時鐘的基礎。當更新當前執行任務的累計執行時間時或者當任務從佇列刪除去，如任務睡眠或退出，這時候會檢視剩下的任務的vruntime是否大於min_vruntime，如果是則更新該值。
tasks_timeline	用於在按時間排序的紅黑樹中管理所有進程(紅黑樹的root)
rb_leftmost	總是設定為指向紅黑樹最左邊的節點, 即需要被排程的進程. 該值其實可以可以通過病例紅黑樹獲得, 但是將這個值儲存下來可以減少搜尋紅黑樹花費的平均時間
curr	當前正在執行的sched_entity（對於組雖然它不會在cpu上執行，但是當它的下層有一個task在cpu上執行，那麼它所在的cfs_rq就把它當做是該cfs_rq上當前正在執行的sched_entity
next	表示有些進程急需執行，即使不遵從CFS排程也必須執行它，排程時會檢查是否next需要排程，有就排程next
skip	略過進程(不會選擇skip指定的進程排程)

　　　　CFS排程的原理:

　　　　在理想狀態下時每個進程都能獲得相同的時間片，並且同時執行在CPU上，但實際上一個CPU同一時刻執行的進程只能有一個。也就是說，當一個進程佔用CPU時，其他進程就必須等待。而往往有一些需要優先去佔用CPU的進程，所以實際上我們是根據每個進程的權重來分配每個進程的執行時間，越重要的進程，我們設定的權重就越高。

　　　　而前面說過，排程還有一個重要的意義在於要對所有進程儘可能地公平分配時間，可是從分配時間來看，權重越高的似乎分配到的執行時間就會越多，並沒有讓人感覺到公平，於是CFS引入了一個變數 : 虛擬執行時間(virtual runtime) ，它會懲罰當前正在執行的進程，以使那些正在等待的進程下次被排程。用vruntime的大小來衡量哪個進程是最優先需要被排程的。

　　　　虛擬執行時間計算公式為：一次排程間隔的vruntime = 實際執行時間 * NICE_0_LOAD / 進程權重;

　　　　其中程式碼NICE_0_LOAD對應的是nice為0的進程的權重值為1024，而所有進程都以nice為0的進程的權重1024作為基準，計算自己的vruntime增加速度。(見後面公式)

/*nice和權重值的轉換表*/
static const int 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,
};

因為CFS中的就緒佇列是一棵以vruntime為鍵值的紅黑樹，虛擬時間越小的進程越靠近整個紅黑樹的最左端。因此，排程器每次選擇位於紅黑樹最左端的那個進程，該進程的vruntime最小。(對應之前的min_vruntime)

　　　　其中vruntime以下公式計算它的增長數值:

條件	公式
當前進程的nice != NICE_0_LOAD	vruntime += delta_exec * NICE_0_LOAD / 進程權重
當前進程的nice == NICE_0_LOAD	vruntime += delta_exec

　其中delta_exce為"核心計算當前和上一次更新負荷權重時兩次的時間的差值", 計算公式為：delta_exec = 當前時間 - 上次更新時間

　　　　因此權重越大的進程的vruntime的增長率會越小，更容易排在紅黑樹偏左端，進而更容易被排程，而權重小的則相反。

　　　　計算完vruntime之後，就要進行設定紅黑樹。

　　2.6紅黑樹

　　　　2.6.1什麼是紅黑樹?

　　　　紅黑樹是一種在插入或刪除結點時都需要維持平衡的二叉查詢樹，並且每個結點都具有顏色屬性：

一個結點要麼是紅色的，要麼是黑色的。
根結點是黑色的。
如果一個結點是紅色的，那麼它的子結點必須是黑色的，也就是說在沿著從根結點出發的任何路徑上都不會出現兩個連續的紅色結點。
從一個結點到一個NULL指標的每條路徑上必須包含相同數目的黑色結點。

　　　　如下圖所示:

　　　　可以很明顯的看出，該樹的最左端的值是最小的。取走最左端的端點後，需要重新平衡紅黑樹。

　　　　2.6.2重新設定min_vruntime的紅黑樹

　　　　程式碼如下:

static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
　　 /*初始化vruntime的值
　　　*相當於如下的程式碼
　　　*if (cfs_rq->curr != NULL)
　　　*　　vruntime = cfs_rq->curr->vruntime;
　　　*else
　　　*　　vruntime = cfs_rq->min_vruntime;
　　　*/
u64 vruntime = cfs_rq->min_vruntime;
　　if (cfs_rq->curr)
vruntime = cfs_rq->curr->vruntime;

　　　　/* 檢測紅黑樹是都有最左的節點, 即是否有進程在樹上等待排程
　　　　* cfs_rq->rb_leftmost(struct rb_node *)儲存了進程紅黑樹的最左節點
　　　　* 這個節點儲存了即將要被排程的結點 */

　　if (cfs_rq->rb_leftmost) {
　　　　/* 獲取最左結點的排程實體資訊se, se中儲存了其vruntime　　　　　　
　　　　 * rb_leftmost的vruntime即樹中所有節點的vruntiem中最小的那個 */
struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
struct sched_entity,
run_node);
　　　/* 如果就緒佇列上沒有curr進程　　　　　
　　　 * 則vruntime設定為樹種最左結點的vruntime 　　　　　
　　　 * 否則設定vruntiem值為cfs_rq->curr->vruntime和se->vruntime的最小值 */
if (!cfs_rq->curr)　　/* 此時vruntime的原值為cfs_rq->min_vruntime*/
vruntime = se->vruntime;
else　　　　　　　　　　/* 此時vruntime的原值為cfs_rq->curr->vruntime*/
vruntime = min_vruntime(vruntime, se->vruntime);
}

/* ensure we never gain time by being placed backwards.
　　 * 為了保證min_vruntime單調不減
　　 * 只有在vruntime超出的cfs_rq->min_vruntime的時候才更新 */
cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
#ifndef CONFIG_64BIT
smp_wmb();
cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;
#endif
}

　　　　重新平衡完min_vruntime的紅黑樹之後，就可以繼續通過CFS去排程進程了，並以此迴圈。

3.體會

　　這些只是Linux下的一小部分罷了，原始碼的程式碼量大到嚇人，基於無數大牛們的努力寫出了現在的Linux，而Linux永遠在不斷的更新，這些程式碼演算法等等永遠不會是最好的，我還需要不斷的學習新的知識，繼續探索這個充斥著01的世界。

本文永久更新連結地址：https://www.linuxidc.com/Linux/2018-05/152166.htm

基於Linux 4.5的進程模型與排程器分析

1.4.3睡眠狀態:

1.4.4進程轉換圖:

2.進程是怎麼被排程的？

2.1什麼是排程器?

2.2進程的分類.

2.3排程器的演變.

2.4排程器的設計.

Linux的2種排程器:

Linux的6種排程策略:

Linux的5種排程類:

2.5CFS排程器.

CFS排程的原理:

2.6紅黑樹

2.6.1什麼是紅黑樹?

2.6.2重新設定min_vruntime的紅黑樹

3.體會

熱門文章

　　　　1.4.3睡眠狀態:　　　　　　

　　1.4.4進程轉換圖:

　　　　

　　2.1什麼是排程器?　　　　

　　2.2進程的分類.

　　2.3排程器的演變.

　　2.4排程器的設計.

　　　　Linux的2種排程器:

　　　　Linux的6種排程策略:

　　　　Linux的5種排程類:

　　2.5CFS排程器.

　　　　CFS排程的原理:

　　2.6紅黑樹

　　　　2.6.1什麼是紅黑樹?

　　　　2.6.2重新設定min_vruntime的紅黑樹