在Linux 操作系統(tǒng)的神秘世界里，進程就像是一個個充滿活力的小生命，它們不斷地誕生、成長、工作，最終走向終止。你可以把 Linux 內(nèi)核想象成一個龐大而有序的城市，進程則是城市里形形色色的居民和組織，它們有著各自的任務(wù)和使命，在這個城市里穿梭忙碌。

進程的創(chuàng)建，如同新生命的誕生，為系統(tǒng)帶來了新的活力和任務(wù)；進程的調(diào)度，就像是城市交通的指揮者，合理地分配時間和資源，確保每個進程都能有序地運行；而進程的終止，則是生命的落幕，釋放出資源，讓系統(tǒng)得以持續(xù)高效地運轉(zhuǎn)。今天，就讓我們一起深入 Linux 內(nèi)核進程的世界，揭開它們創(chuàng)建、調(diào)度和終止的神秘面紗，探尋其中的奧秘和樂趣 。

一、Linux進程的概念

進程（Process）是指計算機中已運行的程序，是系統(tǒng)進行資源分配和調(diào)度的基本單位，是操作系統(tǒng)結(jié)構(gòu)的基礎(chǔ)。在早期面向進程設(shè)計的計算機結(jié)構(gòu)中，進程是程序的基本執(zhí)行實體；在當代面向線程設(shè)計的計算機結(jié)構(gòu)中，進程是線程的容器。進程是程序真正運行的實例，若干進程可能與同一個程序相關(guān)，且每個進程皆可以同步或異步的方式獨立運行。

• 狹義定義：進程是正在運行的程序的實例。
• 廣義定義：進程是一個具有一定獨立功能的程序關(guān)于某個數(shù)據(jù)集合的一次運行活動。它是操作系統(tǒng)動態(tài)執(zhí)行的基本單元，在傳統(tǒng)的操作系統(tǒng)中，進程既是基本的分配單元，也是基本的執(zhí)行單元。

進程的概念主要有兩點：第一，進程是一個實體。每一個進程都有它自己的地址空間，一般情況下，包括文本區(qū)域（text region）、數(shù)據(jù)區(qū)域（data region）和堆棧（stack region）。文本區(qū)域存儲處理器執(zhí)行的代碼；數(shù)據(jù)區(qū)域存儲變量和進程執(zhí)行期間使用的動態(tài)分配的內(nèi)存；堆棧區(qū)域存儲著活動過程調(diào)用的指令和本地變量。第二，進程是一個“執(zhí)行中的程序”。程序是一個沒有生命的實體，只有處理器賦予程序生命時（操作系統(tǒng)執(zhí)行之），它才能成為一個活動的實體，我們稱其為進程。

1.1描述進程PCB

進程：資源的封裝單位，linux用一個PCB來描述進程，即task_struct， 其包含mm,fs,files,signal…

(1)root目錄，是一個進程概念，不是系統(tǒng)概念

apropos chroot
man chroot 2

將分區(qū)/dev/sda5掛載到/mnt/a，調(diào)用chroot，改變root目錄，當前進程下的文件b.txt即位于當前進程的根目錄。

(2)fd也是進程級概念

(base) leon@leon-Laptop:/proc/29171$ ls fd -l

總用量 0

lrwx------ 1 leon leon 64 5月 16 10:26 0 -> /dev/pts/19
lrwx------ 1 leon leon 64 5月 16 10:26 1 -> /dev/pts/19
lrwx------ 1 leon leon 64 5月 16 10:26 2 -> /dev/pts/19

(3)pid，系統(tǒng)全局概念

Linux總的PID是有限的，用完P(guān)ID

: ( ) { : ∣ : & } ; : :()\{:|:\&\};::(){:∣:&};:

每個用戶的PID也是有限的

• ulimit -u 最大進程數(shù)
• ulimit –a

(base) leon@leon-Laptop:/proc/29171$ cat /proc/sys/kernel/pid_max

1.2 task_ struct內(nèi)容分類

在進程執(zhí)行時，任意給定一個時間，進程都可以唯一的被表征為以下元素：

• 標示符: 描述本進程的唯一標示符，?用來區(qū)別其他進程。
• 狀態(tài): 任務(wù)狀態(tài)，退出代碼，退出信號等。
• 優(yōu)先級: 相對于其他進程的優(yōu)先級。
• 程序計數(shù)器: 程序中即將被執(zhí)行的下一條指令的地址。
• 內(nèi)存指針: 包括程序代碼和進程相關(guān)數(shù)據(jù)的指針，還有和其他進程共享的內(nèi)存塊的指針
• 上下文數(shù)據(jù): 進程執(zhí)行時處理器的寄存器中的數(shù)據(jù)
• I／O狀態(tài)信息: 包括顯?示的I/O請求,分配給進程的I／O設(shè)備和被進程使用的文件列表。
• 記賬信息: 可能包括處理器時間總和，使用的時鐘數(shù)總和，時間限制，記賬號等。

1.3Linux進程的組織方式

linux里的多個進程，其實就是管理多個task_struct，那他們是怎么組織聯(lián)系的呢？

組織task_struct的數(shù)據(jù)結(jié)構(gòu)：

• a.鏈表，遍歷進程
• b.樹：方便查找父子相關(guān)進程
• c.哈希表：用于快速查找

用三種數(shù)據(jù)結(jié)構(gòu)來管理task_struct，以空間換時間。父進程監(jiān)控子進程，linux總是白發(fā)人送黑發(fā)人。父進程通過wait，讀取task_struct的退出碼，得知進程死亡原因。并且清理子進程尸體。

Android/或者服務(wù)器，都會用由父進程監(jiān)控子進程狀態(tài)，適時重啟等；

1.4進程的狀態(tài)和轉(zhuǎn)換

(1)五種狀態(tài)

進程在其生命周期內(nèi)，由于系統(tǒng)中各進程之間的相互制約關(guān)系及系統(tǒng)的運行環(huán)境的變化，使得進程的狀態(tài)也在不斷地發(fā)生變化（一個進程會經(jīng)歷若干種不同狀態(tài)）。通常進程有以下五種狀態(tài)，前三種是進程的基本狀態(tài)。

1. 運行狀態(tài)：進程正在處理機上運行。在單處理機環(huán)境下，每一時刻最多只有一個進程處于運行狀態(tài)。
2. 就緒狀態(tài)：進程已處于準備運行的狀態(tài)，即進程獲得了除處理機之外的一切所需資源，一旦得到處理機即可運行。
3. 阻塞狀態(tài)，又稱等待狀態(tài)：進程正在等待某一事件而暫停運行，如等待某資源為可用（不包括處理機）或等待輸入/輸出完成。即使處理機空閑，該進程也不能運行。
4. 創(chuàng)建狀態(tài)：進程正在被創(chuàng)建，尚未轉(zhuǎn)到就緒狀態(tài)。創(chuàng)建進程通常需要多個步驟：首先申請一個空白的PCB，并向PCB中填寫一些控制和管理進程的信息；然后由系統(tǒng)為該進程分 配運行時所必需的資源；最后把該進程轉(zhuǎn)入到就緒狀態(tài)。
5. 結(jié)束狀態(tài)：進程正從系統(tǒng)中消失，這可能是進程正常結(jié)束或其他原因中斷退出運行。當進程需要結(jié)束運行時，系統(tǒng)首先必須置該進程為結(jié)束狀態(tài)，然后再進一步處理資源釋放和 回收等工作。

注意區(qū)別就緒狀態(tài)和等待狀態(tài)：就緒狀態(tài)是指進程僅缺少處理機，只要獲得處理機資源就立即執(zhí)行；而等待狀態(tài)是指進程需要其他資源（除了處理機）或等待某一事件。之所以把處理機和其他資源劃分開，是因為在分時系統(tǒng)的時間片輪轉(zhuǎn)機制中，每個進程分到的時間片是若干毫秒。

也就是說，進程得到處理機的時間很短且非常頻繁，進程在運行過程中實際上是頻繁地轉(zhuǎn)換到就緒狀態(tài)的；而其他資源（如外設(shè)）的使用和分配或者某一事件的發(fā)生（如I/O操作的完成）對應(yīng)的時間相對來說很長，進程轉(zhuǎn)換到等待狀態(tài)的次數(shù)也相對較少。這樣來看，就緒狀態(tài)和等待狀態(tài)是進程生命周期中兩個完全不同的狀態(tài)，很顯然需要加以區(qū)分。

(2)狀態(tài)轉(zhuǎn)換

1. 就緒狀態(tài) -> 運行狀態(tài)：處于就緒狀態(tài)的進程被調(diào)度后，獲得處理機資源（分派處理機時間片），于是進程由就緒狀態(tài)轉(zhuǎn)換為運行狀態(tài)。
2. 運行狀態(tài) -> 就緒狀態(tài)：處于運行狀態(tài)的進程在時間片用完后，不得不讓出處理機，從而進程由運行狀態(tài)轉(zhuǎn)換為就緒狀態(tài)。此外，在可剝奪的操作系統(tǒng)中，當有更高優(yōu)先級的進程就 、 緒時，調(diào)度程度將正執(zhí)行的進程轉(zhuǎn)換為就緒狀態(tài)，讓更高優(yōu)先級的進程執(zhí)行。
3. 運行狀態(tài) -> 阻塞狀態(tài)：當進程請求某一資源（如外設(shè)）的使用和分配或等待某一事件的發(fā)生（如I/O操作的完成）時，它就從運行狀態(tài)轉(zhuǎn)換為阻塞狀態(tài)。進程以系統(tǒng)調(diào)用的形式請求操作系統(tǒng)提供服務(wù)，這是一種特殊的、由運行用戶態(tài)程序調(diào)用操作系統(tǒng)內(nèi)核過程的形式。
4. 阻塞狀態(tài) -> 就緒狀態(tài)：當進程等待的事件到來時 ，如I/O操作結(jié)束或中斷結(jié)束時，中斷處理程序必須把相應(yīng)進程的狀態(tài)由阻塞狀態(tài)轉(zhuǎn)換為就緒狀態(tài)。

二、Linux進程誕生

2.1進程創(chuàng)建方式

在 Linux 系統(tǒng)中，主要有三種方式可以創(chuàng)建新的進程，分別是fork、vfork和clone系統(tǒng)調(diào)用 。這三種方式就像是三把不同的鑰匙，雖然都能打開進程創(chuàng)建的大門，但各自有著獨特的開啟方式和適用場景。

1. fork函數(shù)是最常用的創(chuàng)建進程的方式，它就像是一個復(fù)印機，創(chuàng)建出的子進程幾乎是父進程的完整副本，擁有自己獨立的地址空間、堆棧和數(shù)據(jù)副本。這種方式適用于需要獨立運行的子進程，比如一個 Web 服務(wù)器程序，當有新的客戶端連接時，就可以通過fork創(chuàng)建一個新的子進程來處理該客戶端的請求 。
2. vfork函數(shù)則像是一個特殊的克隆工具，創(chuàng)建的子進程與父進程共享地址空間，并且保證子進程先運行，直到子進程調(diào)用exec或exit函數(shù)后，父進程才會繼續(xù)執(zhí)行。這種方式適用于子進程需要立即執(zhí)行另一個程序的場景，比如在啟動一個新的應(yīng)用程序時，就可以使用vfork來創(chuàng)建子進程，然后在子進程中調(diào)用exec函數(shù)來加載新的應(yīng)用程序。
3. clone函數(shù)則更加靈活，它可以根據(jù)用戶的需求，選擇性地繼承父進程的部分資源，比如可以共享文件描述符、信號處理函數(shù)等。這種方式就像是一個定制化的工廠，可以根據(jù)不同的需求生產(chǎn)出不同類型的進程，適用于創(chuàng)建線程或者需要精細控制資源共享的場景 。

fork創(chuàng)建一個新進程，也需要創(chuàng)建task_struct所有資源；實際上創(chuàng)建一個新進程之初，子進程完全拷貝父進程資源，如下圖示：

比如fs結(jié)構(gòu)體：

struct fs_struct {
* root
* pwd
};

子進程會拷貝一份fs_struct，

*p2_fs = *p1_fs;

pwd路徑和root路徑與父進程相同，子進程修改當前路徑，就會修改其p2_fs->pwd值；父進程修改當前路徑，修改p1_fs->pwd;

2.2fork 函數(shù)原理

fork函數(shù)的原型非常簡潔：pid_t fork(void); 。這個函數(shù)就像是一個神奇的開關(guān)，當它被調(diào)用時，會在操作系統(tǒng)中引發(fā)一系列奇妙的變化。它會創(chuàng)建一個新的進程，這個新進程就是子進程，而調(diào)用fork的進程則是父進程。

從實現(xiàn)原理上看，fork函數(shù)會復(fù)制父進程的幾乎所有資源，包括虛擬地址空間、堆棧、打開的文件描述符等。在虛擬地址空間方面，父子進程各自擁有自己獨立的虛擬地址空間，但它們共享代碼段（因為代碼段通常是只讀的，不需要為每個進程單獨復(fù)制一份）。這就好比父子倆住在各自的房子里（虛擬地址空間），但他們共享同一個圖書館（代碼段） 。

在早期的 Unix 系統(tǒng)中，fork創(chuàng)建子進程時會直接復(fù)制父進程的整個地址空間，這會導(dǎo)致大量的內(nèi)存拷貝操作，效率非常低下。后來引入了寫時拷貝（Copy-On-Write，COW）技術(shù)，大大提高了fork的效率。寫時拷貝技術(shù)的原理是，在fork創(chuàng)建子進程時，并不立即復(fù)制父進程的地址空間，而是讓父子進程共享相同的物理內(nèi)存頁面。只有當其中一個進程試圖修改共享的內(nèi)存頁面時，系統(tǒng)才會為修改的頁面創(chuàng)建一個副本，分別分配給父子進程。這就好比父子倆一開始共享同一本書（物理內(nèi)存頁面），當其中一個人想要在書上做筆記（修改內(nèi)存頁面）時，才會復(fù)制一本新的書給他 。

其他資源大體與fs類似，最復(fù)雜的是mm拷貝，需借助MMU來完成拷貝；

即寫時拷貝技術(shù)：

#include <sched.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>

int data = 10;

int child_process()
{
	printf(“Child process %d, data %d\n”,getpid(),data);
	data = 20;
	printf(“Child process %d, data %d\n”,getpid(),data);
	_exit(0);
}

int main(int argc, char* argv[])
{
	int pid;
	pid = fork();
	if(pid==0) {
		child_process();
	}
	else{
		sleep(1);
		printf(“Parent process %d, data %d\n”,getpid(), data);
		exit(0);
	}
	return 0;
}

寫時拷貝技術(shù)帶來了很多好處。首先，它節(jié)省了內(nèi)存開銷，因為在大多數(shù)情況下，父子進程在fork之后并不會立即修改共享的內(nèi)存，所以不需要一開始就復(fù)制大量的內(nèi)存。其次，它提高了進程創(chuàng)建的效率，減少了fork操作的時間開銷 。

第一階段：只有一個進程P1，數(shù)據(jù)段可讀可寫：

第二階段，調(diào)用fork之后創(chuàng)建子進程P2，P2完全拷貝一份P1的mm_struct，其指針指向相同地址，即P1/P2虛擬地址，物理地址完全相同，但該內(nèi)存的頁表地址變?yōu)橹蛔x；

第三階段：當P2改寫data時，子進程改寫只讀內(nèi)存，會引起內(nèi)存缺頁中斷，在ISR中申請一片新內(nèi)存，通常是4K，把P1進程的data拷貝到這4K新內(nèi)存。再修改頁表，改變虛實地址轉(zhuǎn)換關(guān)系，使物理地址指向新申請的4K，這樣子進程P2就得到新的4K內(nèi)存，并修改權(quán)限為可讀寫，然后從中斷返回到P2進程寫data才會成功。整個過程虛擬地址不變，對應(yīng)用程序員來說，感覺不到地址變化。

誰先寫，誰申請新物理內(nèi)存；Data=20；這句代碼經(jīng)過了賦值無寫權(quán)限，引起缺頁中斷，申請內(nèi)存，修改頁表，拷貝數(shù)據(jù)…回到data=20再次賦值，所以整個執(zhí)行時間會很長。

這就是linux中的寫時拷貝技術(shù)(copy on write), 誰先寫誰申請新內(nèi)存，沒有優(yōu)先順序；cow依賴硬件MMU實現(xiàn)，沒有MMU的系統(tǒng)就沒法實現(xiàn)cow，也就不支持fork函數(shù),只有vfork;

2.3vfork 函數(shù)原理

vfork函數(shù)的原型同樣簡單：pid_t vfork(void); 。它與fork函數(shù)有著明顯的區(qū)別。vfork創(chuàng)建的子進程與父進程共享地址空間，這意味著子進程完全運行在父進程的地址空間上，如果子進程修改了某個變量，那么父進程中的這個變量也會被改變。而且，vfork保證子進程先運行，在子進程調(diào)用exec或exit函數(shù)之前，父進程會被阻塞，處于暫停狀態(tài) 。

這種特性使得vfork適用于一些特定的場景，比如子進程需要立即執(zhí)行另一個程序的情況。因為子進程共享父進程的地址空間，所以在創(chuàng)建子進程時不需要復(fù)制大量的內(nèi)存，從而節(jié)省了時間和資源。例如，當我們需要啟動一個新的程序時，可以使用vfork創(chuàng)建子進程，然后在子進程中調(diào)用exec函數(shù)來加載新的程序，這樣可以快速地啟動新程序，而不會浪費過多的資源 。

不過，使用vfork也需要特別小心。由于子進程和父進程共享地址空間，如果子進程在調(diào)用exec或exit之前對共享的變量進行了修改，可能會影響到父進程的正常運行。所以，在使用vfork時，一定要確保子進程盡快調(diào)用exec或exit函數(shù)，以避免出現(xiàn)意想不到的問題 。

2.4clone 函數(shù)原理

clone函數(shù)的原型相對復(fù)雜一些：int clone(int (*fn)(void *), void *child_stack, int flags, void *arg); 。它接受多個參數(shù)，這些參數(shù)賦予了clone函數(shù)強大的靈活性。

fn參數(shù)是一個函數(shù)指針，指向新進程開始執(zhí)行的函數(shù)，就像是為新進程設(shè)定了一個起點。child_stack參數(shù)指定了新進程的用戶態(tài)棧指針，為新進程提供了一個獨立的堆?？臻g 。

flags參數(shù)是一個標志位，它決定了新進程如何繼承父進程的資源。通過設(shè)置不同的標志位，可以實現(xiàn)不同的資源共享和進程創(chuàng)建方式。比如，CLONE_VM標志表示新進程與父進程共享內(nèi)存描述符和所有的頁表，這樣它們就可以共享內(nèi)存空間；CLONE_FS標志表示共享文件系統(tǒng)，包括根目錄、當前目錄和文件權(quán)限掩碼等；CLONE_FILES標志表示共享打開的文件描述符，使得父子進程可以訪問相同的文件 。

arg參數(shù)是傳遞給fn函數(shù)的參數(shù)，就像是給新進程傳遞了一份 “行李”，讓它在開始執(zhí)行時可以使用 。

clone函數(shù)創(chuàng)建進程的獨特之處在于它可以根據(jù)用戶的需求，精細地控制新進程對父進程資源的繼承方式，既可以創(chuàng)建完全獨立的進程，也可以創(chuàng)建共享部分資源的輕量級進程（線程）。這種靈活性使得clone函數(shù)在很多場景下都能發(fā)揮重要作用，比如在實現(xiàn)多線程庫時，就可以利用clone函數(shù)來創(chuàng)建共享內(nèi)存和文件描述符的輕量級進程，模擬線程的行為 。

Linux中創(chuàng)建進程(fork，vfork)和線程(pthread_create)，在內(nèi)核都是調(diào)用do_fork()–>clone()，參數(shù)clone_flags標記表明哪些資源是需要克隆的，創(chuàng)建線程時，所有資源都克??；

從調(diào)度的角度理解線程，從資源角度來理解進程，內(nèi)核里只要是task_struct，就可以被調(diào)度；linux中的線程又叫輕量級進程lwp;

ret = pthread_create(&tid1, NULL, thread_fun, NULL);
if (ret == -1) {
perror(“cannot create new thread”);
return -1;
}
strace ./a.out

2.5幕后英雄：do_fork 和 copy_process

在進程創(chuàng)建的過程中，do_fork函數(shù)是真正的核心。它就像是一場精彩演出背后的導(dǎo)演，負責協(xié)調(diào)和安排進程創(chuàng)建的各個環(huán)節(jié) 。do_fork函數(shù)定義在 Linux 內(nèi)核的kernel/fork.c文件中，它接受多個參數(shù)，包括clone_flags（克隆標志）、stack_start（棧起始地址）、regs（寄存器值）和stack_size（棧大?。┑?。這些參數(shù)就像是導(dǎo)演手中的劇本和道具清單，決定了新進程的各種特性和資源分配 。

do_fork函數(shù)主要完成以下幾個關(guān)鍵任務(wù)：首先，它會根據(jù)clone_flags標志來檢查創(chuàng)建進程的合法性，確保滿足各種條件和限制。然后，它會調(diào)用copy_process函數(shù)來創(chuàng)建新進程的描述符和其他內(nèi)核數(shù)據(jù)結(jié)構(gòu) 。在創(chuàng)建過程中，它會為新進程分配一個唯一的進程 ID（PID），這個 PID 就像是新進程的身份證，用于在系統(tǒng)中唯一標識這個進程 。

copy_process函數(shù)則是do_fork函數(shù)的得力助手，它負責具體創(chuàng)建新進程的描述符和其他內(nèi)核數(shù)據(jù)結(jié)構(gòu)。它就像是一個勤勞的工匠，精心打造新進程所需的各種 “零件” 。copy_process函數(shù)首先會調(diào)用dup_task_struct函數(shù)復(fù)制當前進程的task_struct結(jié)構(gòu)體，這個結(jié)構(gòu)體是進程描述符，包含了進程的各種信息，如進程狀態(tài)、優(yōu)先級、打開的文件描述符等 。

接著copy_process函數(shù)會檢查新進程的資源限制，確保不會超過系統(tǒng)的限制。然后，它會初始化新進程的各種屬性，如設(shè)置進程的狀態(tài)為可運行狀態(tài)（TASK_RUNNING），初始化進程的信號處理函數(shù)、文件系統(tǒng)信息等 。在初始化過程中，它會根據(jù)clone_flags標志來決定新進程如何繼承父進程的資源，是完全復(fù)制還是共享部分資源 。

最后，copy_process函數(shù)會調(diào)用copy_thread函數(shù)來初始化子進程的內(nèi)核棧，為子進程的執(zhí)行做好準備。通過do_fork和copy_process函數(shù)的協(xié)同工作，一個新的進程就誕生了，它帶著自己的使命和資源，開始在 Linux 系統(tǒng)這個大舞臺上展現(xiàn)自己的活力 。

三、Linux進程調(diào)度

3.1調(diào)度策略

在 Linux 的進程調(diào)度舞臺上，有多種調(diào)度策略可供選擇，每種策略都有其獨特的特點和適用場景，就像是不同風格的舞蹈，在不同的音樂節(jié)奏下展現(xiàn)出各自的魅力 。

首先是SCHED_OTHER，它是默認的分時調(diào)度策略，適用于大多數(shù)普通應(yīng)用程序。在這種策略下，系統(tǒng)會根據(jù)進程的nice值（取值范圍為 - 20 到 19，數(shù)值越小優(yōu)先級越高）來分配 CPU 時間。nice值就像是進程的 “好感度”，好感度越高（nice值越?。┑倪M程，獲得 CPU 時間的機會就越大 。例如，一個普通的文本編輯程序，它對實時性要求不高，就可以采用SCHED_OTHER調(diào)度策略，讓系統(tǒng)合理地分配 CPU 時間，保證它能正常運行 。

SCHED_FIFO是實時調(diào)度策略中的先進先出策略，適用于對時間要求嚴格、需要立即執(zhí)行的實時任務(wù) 。一旦一個SCHED_FIFO類型的進程獲得了 CPU，它就會一直運行下去，直到它主動放棄 CPU（比如因為等待 I/O 操作而阻塞）或者被更高優(yōu)先級的進程搶占 。這就好比一場緊張的賽車比賽，一旦賽車駛?cè)胭惖溃蜁恢憋w馳，直到遇到特殊情況才會停下來 。比如，工業(yè)控制系統(tǒng)中的一些實時控制任務(wù)，需要對外部設(shè)備的信號做出快速響應(yīng)，就可以使用SCHED_FIFO策略，確保任務(wù)能及時執(zhí)行，避免因延遲而導(dǎo)致生產(chǎn)事故 。

SCHED_RR也是實時調(diào)度策略，它是時間片輪轉(zhuǎn)調(diào)度策略 。與SCHED_FIFO不同的是，SCHED_RR為每個進程分配一個固定的時間片，當進程的時間片用完后，它會被放到就緒隊列的末尾，等待下一次調(diào)度 。這就像是一場接力賽跑，每個選手都有自己的固定跑步時間，時間一到就把接力棒交給下一位選手 。對于一些對響應(yīng)時間要求嚴格且執(zhí)行時間較短的實時任務(wù)，比如多媒體播放中的音頻和視頻解碼任務(wù)，使用SCHED_RR策略可以保證每個任務(wù)都能得到及時處理，避免出現(xiàn)音頻卡頓或視頻掉幀的情況 。

在優(yōu)先級關(guān)系上，實時進程（采用SCHED_FIFO和SCHED_RR策略）的優(yōu)先級高于普通進程（采用SCHED_OTHER策略） 。這意味著當有實時進程就緒時，系統(tǒng)會優(yōu)先調(diào)度實時進程，確保它們能及時運行，而普通進程則需要等待實時進程執(zhí)行完畢或者主動放棄 CPU 后才有機會運行 。

3.2調(diào)度算法

Linux 內(nèi)核中，完全公平調(diào)度器（CFS）是進程調(diào)度的核心算法之一，它的設(shè)計目標是實現(xiàn)所有進程公平分享 CPU 資源 。CFS 就像是一位公正的裁判，努力讓每個進程都能在 CPU 這個賽場上獲得公平的比賽時間 。

CFS 的工作原理基于虛擬運行時間（vruntime） 。每個進程都有一個vruntime值，它表示進程的虛擬運行時間 。vruntime的計算方式為：vruntime = 實際運行時間 × 1024 / 進程權(quán)重 。這里的進程權(quán)重由進程的nice值決定，nice值越?。▋?yōu)先級越高），權(quán)重越大 。例如，一個nice值為 - 5 的進程，它的權(quán)重會比nice值為 5 的進程大，在相同的實際運行時間下，它的vruntime增長速度會更慢 。

CFS 使用紅黑樹來存儲可運行進程，以vruntime為鍵值 。每次調(diào)度時，CFS 會選擇紅黑樹中最左側(cè)節(jié)點（即vruntime最小的進程）運行 。這就好比在一場比賽中，裁判總是選擇那些 “跑得最慢”（vruntime最?。┑倪x手先上場，讓每個選手都有機會展示自己 。通過這種方式，CFS 保證了每個進程都能公平地獲得 CPU 時間，避免了某些進程長時間占用 CPU 而導(dǎo)致其他進程饑餓的情況 。

實時調(diào)度策略主要包括SCHED_FIFO和SCHED_RR，它們適用于對時間要求嚴格的實時任務(wù) 。實時調(diào)度策略的特點是優(yōu)先級較高，能夠確保實時任務(wù)在規(guī)定的時間內(nèi)完成 。對于SCHED_FIFO策略的任務(wù)，一旦獲得 CPU 就會一直運行，直到主動放棄或被更高優(yōu)先級任務(wù)搶占；而SCHED_RR策略的任務(wù)則是按照時間片輪轉(zhuǎn)的方式運行，每個任務(wù)在自己的時間片內(nèi)運行，時間片用完后會被放到就緒隊列末尾 。

這些實時調(diào)度策略在工業(yè)控制、航空航天等對實時性要求極高的領(lǐng)域有著廣泛的應(yīng)用，比如在航空航天領(lǐng)域，飛行器的飛行控制任務(wù)需要實時處理各種傳感器數(shù)據(jù)，對時間的準確性要求極高，使用實時調(diào)度策略可以確保這些任務(wù)能夠及時、準確地執(zhí)行，保障飛行器的安全飛行 。

3.3調(diào)度時機

進程調(diào)度的時機就像是一場音樂會中節(jié)奏的轉(zhuǎn)換點，把握得恰到好處才能讓整個演出流暢進行 。在 Linux 系統(tǒng)中，進程調(diào)度會在多種情況下發(fā)生 ：

當系統(tǒng)調(diào)用返回時，是一個常見的調(diào)度時機 。系統(tǒng)調(diào)用就像是進程向操作系統(tǒng)發(fā)出的服務(wù)請求，當請求處理完成返回時，系統(tǒng)會檢查是否有更合適的進程需要運行 。比如，一個進程調(diào)用read系統(tǒng)調(diào)用來讀取文件數(shù)據(jù)，在讀取完成返回后，系統(tǒng)可能會發(fā)現(xiàn)有其他進程的優(yōu)先級更高或者等待時間更長，這時就會進行進程調(diào)度，讓更合適的進程獲得 CPU 。

中斷處理完成后也會觸發(fā)進程調(diào)度 。中斷就像是緊急事件的通知，當硬件設(shè)備（如鍵盤、鼠標、網(wǎng)卡等）產(chǎn)生中斷時，操作系統(tǒng)會暫停當前進程的執(zhí)行，去處理中斷事件 。當中斷處理完成后，系統(tǒng)會重新評估當前的進程狀態(tài)，決定是否進行進程調(diào)度 。例如，當用戶按下鍵盤時，會產(chǎn)生鍵盤中斷，操作系統(tǒng)會暫停當前正在運行的進程，去處理鍵盤輸入事件，處理完成后，再根據(jù)情況決定是否調(diào)度其他進程 。

進程主動放棄 CPU 也是調(diào)度的時機之一 。有些進程在執(zhí)行過程中，可能會因為等待某些資源（如等待其他進程發(fā)送信號、等待 I/O 操作完成等）而主動調(diào)用schedule函數(shù)放棄 CPU 。比如，一個進程需要等待另一個進程完成某項任務(wù)后才能繼續(xù)執(zhí)行，它就會主動調(diào)用schedule函數(shù)，將 CPU 讓給其他可運行的進程，直到等待的條件滿足后再重新競爭 CPU 。

另外，當進程的時間片用完時，也會進行進程調(diào)度 。在采用時間片輪轉(zhuǎn)調(diào)度策略（如SCHED_RR）的情況下，每個進程被分配一個固定的時間片，當時間片用完后，進程就會被迫讓出 CPU，等待下一次調(diào)度 。這就像是一場限時演講比賽，每個選手的演講時間一到，就必須下臺，讓下一位選手上臺演講 。通過這些調(diào)度時機的合理把握，Linux 系統(tǒng)能夠高效地管理進程，確保每個進程都能在合適的時間運行，提高系統(tǒng)的整體性能 。

四、Linux進程終止

4.1 終止原因

進程終止是進程生命周期的最后階段，就像是一場演出的落幕。進程終止的原因多種多樣，常見的有以下幾種 。

當進程調(diào)用exit函數(shù)時，它就像是一個演員主動向?qū)а菔疽庋莩鼋Y(jié)束，決定主動終止自己的運行 。在 C 語言中，exit函數(shù)是標準庫函數(shù)，用于正常終止程序的執(zhí)行 。它接受一個整數(shù)參數(shù)，這個參數(shù)通常被稱為退出狀態(tài)碼，用于向父進程或操作系統(tǒng)傳遞進程終止的相關(guān)信息 。比如，退出狀態(tài)碼為 0 通常表示進程正常結(jié)束，就像一場演出完美謝幕；而其他非零值則表示進程在執(zhí)行過程中遇到了問題，比如文件讀取失敗、內(nèi)存分配錯誤等，就像是演出過程中出現(xiàn)了意外狀況 。

進程收到特定信號也會導(dǎo)致其終止 。信號是 Linux 系統(tǒng)中進程間通信的一種方式，它就像是一個緊急通知，當進程收到某些特定信號時，可能會被迫終止 。例如，SIGKILL信號是一個強制終止信號，它就像是一把 “尚方寶劍”，一旦發(fā)送給進程，進程就會立即無條件終止，沒有任何機會進行資源清理或其他善后工作 。SIGTERM信號則相對溫和一些，它是一個正常的終止信號，用于通知進程優(yōu)雅地終止 。當進程收到SIGTERM信號時，它可以選擇捕獲這個信號，并在信號處理函數(shù)中進行一些清理工作，如關(guān)閉打開的文件、釋放內(nèi)存等，然后再正常終止 。就好比一個演員在收到導(dǎo)演的 “謝幕” 通知后，會先整理好自己的道具和服裝，然后再優(yōu)雅地退場 。

4.2終止過程

當進程調(diào)用exit函數(shù)后，會經(jīng)歷一系列復(fù)雜而有序的步驟，最終完成終止過程 。這個過程就像是一場精心安排的閉幕式，每個環(huán)節(jié)都至關(guān)重要 。

exit函數(shù)最終會調(diào)用內(nèi)核中的do_exit函數(shù)，do_exit函數(shù)就像是這場閉幕式的總導(dǎo)演，負責協(xié)調(diào)和執(zhí)行進程終止的各個環(huán)節(jié) 。do_exit函數(shù)首先會設(shè)置進程描述符task_struct的標志成員為PF_EXITING，這個標志就像是一個 “演出結(jié)束” 的牌子，向系統(tǒng)表明該進程正在退出 。

接著，do_exit函數(shù)會調(diào)用del_timer_sync函數(shù)刪除任意內(nèi)核定時器 。內(nèi)核定時器就像是進程演出過程中的定時提醒裝置，在進程終止時，這些定時器不再需要，所以要將它們刪除 。

如果 BSD 的進程記賬功能是開啟的，do_exit函數(shù)會調(diào)用acct_update_integrals函數(shù)來輸出記賬信息 。進程記賬功能就像是一個記錄進程 “演出開銷” 的賬本，記錄了進程占用 CPU 時間等信息，在進程終止時，需要將這些信息輸出 。

然后，do_exit函數(shù)會調(diào)用exit_mm函數(shù)釋放進程占用的mm_struct，如果沒有別的進程使用（即沒有被共享），就會徹底釋放 。mm_struct結(jié)構(gòu)體管理著進程的虛擬內(nèi)存空間，就像是進程的 “演出場地”，在進程終止時，要將這個場地歸還給系統(tǒng) 。

do_exit函數(shù)還會調(diào)用exit_sem函數(shù)，如果進程排隊等待 IPC（進程間通信）信息，則讓它離開該隊列 。IPC 就像是進程之間的 “交流渠道”，在進程終止時，要斷開這些交流渠道 。

調(diào)用exit_files和exit_fs函數(shù)，分別處理文件描述符和文件系統(tǒng)數(shù)據(jù)的引用計數(shù) 。如果引用計數(shù)降為 0，說明沒有其他進程使用這些資源，這時就可以釋放它們 。文件描述符和文件系統(tǒng)數(shù)據(jù)就像是進程演出時使用的 “道具”，在演出結(jié)束后，要將這些道具妥善處理 。

do_exit函數(shù)會把task_struct中的exit_code成員（退出代碼）置為exit函數(shù)傳入的參數(shù)或其他相關(guān)值，這個退出代碼會供父進程檢索，用于了解子進程終止的原因 。就好比演員在退場時，會給導(dǎo)演留下一張便條，說明自己退場的原因 。

do_exit函數(shù)會調(diào)用exit_notify函數(shù)向父進程發(fā)送信號，告知父進程自己即將終止 。同時，會給該進程尋找一個 “養(yǎng)父”，這個 “養(yǎng)父” 可能是線程組的其他線程或init進程 。并且會把進程狀態(tài)改為EXIT_ZOMBIE（僵尸狀態(tài)） 。在僵尸狀態(tài)下，進程雖然已經(jīng)基本停止運行，但它的進程描述符等信息還會被保留，直到父進程對其進行處理 。

do_exit函數(shù)會調(diào)用schedule函數(shù)切換到新的進程 。此時，原進程已經(jīng)完成了大部分的終止工作，系統(tǒng)會調(diào)度其他可運行的進程繼續(xù)執(zhí)行，就像是一場演出結(jié)束后，舞臺會為下一場演出做好準備 。

4.3僵死進程與避免

僵死進程，也被稱為僵尸進程，是 Linux 系統(tǒng)中一種特殊的進程狀態(tài) 。當子進程先于父進程退出，且父進程沒有及時讀取子進程的退出狀態(tài)時，子進程就會進入僵死狀態(tài)，成為僵死進程 。這就好比一個孩子提前離開了舞臺，但家長卻沒有來接他，他只能在舞臺邊等待 。

僵死進程會在系統(tǒng)中保留其進程描述符、進程 ID 等信息，雖然它不再占用大量的系統(tǒng)資源，但如果大量的僵死進程存在，會占用有限的進程 ID 資源，導(dǎo)致系統(tǒng)無法創(chuàng)建新的進程 。這就像是舞臺邊擠滿了等待家長的孩子，使得新的演員無法上臺表演 。

為了避免僵死進程的產(chǎn)生，可以采取以下幾種方法 。父進程可以調(diào)用wait系列函數(shù)（如wait、waitpid）來等待子進程結(jié)束，并獲取子進程的退出狀態(tài) 。wait函數(shù)會使父進程阻塞，直到有子進程退出，然后它會收集子進程的信息，并把它徹底銷毀 。waitpid函數(shù)則更加靈活，它可以指定等待特定的子進程，并且可以設(shè)置非阻塞模式 。這就好比家長在孩子表演結(jié)束后，及時到舞臺邊接孩子，將孩子安全地帶回家 。

父進程可以安裝SIGCHLD信號的處理函數(shù) 。當子進程退出時，系統(tǒng)會向父進程發(fā)送SIGCHLD信號，父進程可以在信號處理函數(shù)中調(diào)用waitpid函數(shù)來處理子進程的退出，這樣可以避免父進程阻塞，提高程序的并發(fā)性能 。這就好比家長給孩子設(shè)置了一個信號器，當孩子表演結(jié)束時，信號器會通知家長，家長可以及時去接孩子 。

還可以使用 “兩次fork” 的技巧 。父進程先fork出一個子進程，然后子進程再fork出一個孫子進程，接著子進程立即exit退出 。這樣，孫子進程就會成為孤兒進程，被init進程收養(yǎng)，init進程會負責清理孫子進程，從而避免了僵死進程的產(chǎn)生 。這就好比家長讓孩子先找到一個臨時監(jiān)護人，然后自己離開，臨時監(jiān)護人會照顧好孩子，確保孩子不會無人照料 。通過這些方法，可以有效地避免僵死進程的產(chǎn)生，保證系統(tǒng)的穩(wěn)定運行 。

五、Linux進程案例分析

Linux的調(diào)度器類主要實現(xiàn)兩類進程調(diào)度算法：實時調(diào)度算法和完全公平調(diào)度算法(CFS)，實時調(diào)度算法SCHED_FIFO和SCHED_RR，按優(yōu)先級執(zhí)行，一般不會被搶占。直到實時進程執(zhí)行完，才會執(zhí)行普通進程。而大多數(shù)的普通進程，用的就是CFS算法。

進程調(diào)度的時機：

①進程狀態(tài)轉(zhuǎn)換時刻：進程終止、進程睡眠；

②當前進程的”時間片”用完；

③主動讓出處理器，用戶調(diào)用sleep()或者內(nèi)核調(diào)用schedule()；

④從中斷，系統(tǒng)調(diào)用或異常返回時。

每個進程task_struct中都有一個struct sched_entity se成員，這就是調(diào)度器的實體結(jié)構(gòu)，進程調(diào)度算法實際上就是管理所有進程的這個se。

結(jié)構(gòu)任務(wù)結(jié)構(gòu){
    揮發(fā)性長狀態(tài)；    / * - 1 不可運行， 0 可以運行， > 0 已停止* /
    無效*堆棧；
    atomic_t 用法；
    無符號整型標志；    / *每個進程標志，定義如下* /
    無符號整型ptrace ；

    int鎖深度；        / * BKL鎖定深度* /

#ifdef CONFIG_SMP
#ifdef __ARCH_WANT_UNLOCKED_CTXSW
    int oncpu ;
＃萬一
＃萬一

    int prio , static_prio ,正常_prio ;
    無符號整數(shù)rt_priority ；
    const struct sched_class * sched_class ;
    struct sched_entity se; //進程調(diào)度實體
    結(jié)構(gòu) sched_rt_entity rt ；
    ……
}

CFS基于一個簡單的理念：所有任務(wù)都應(yīng)該公平的分配處理器。理想情況下，n個進程的調(diào)度系統(tǒng)中，每個進程獲得1/n處理器時間，所有進程的vruntime也是相同的。

CFS完全拋棄了時間片的概念，而是分配一個處理器使用比來度量。每個進程一個調(diào)度周期內(nèi)分配的時間(類似于傳統(tǒng)的“時間片”)跟三個因素有關(guān)：進程總數(shù)，優(yōu)先級，調(diào)度周期

5.1理解CFS的首先要理解vruntime的含義

簡單說vruntime就是該進程的運行時間，但這個時間是通過優(yōu)先級和系統(tǒng)負載等加權(quán)過的時間，而非物理時鐘時間，按字面理解為虛擬運行時間，也很恰當。

每個進程的調(diào)度實體se都保存著本進程的虛擬運行時間。

結(jié)構(gòu)sched_entity {
    struct load_weight 負載；        / * 用于負載均衡* / _
    結(jié)構(gòu) rb_node run_node ;
    struct list_head group_node ;
    無符號整型        on_rq ；

    u64 exec_start ；
    u64 sum_exec_runtime ；
    u64            vruntime; //虛擬運行時間
    u64 prev_sum_exec_runtime ;
……
}

而進程相關(guān)的調(diào)度方法如下：

靜態(tài)常量結(jié)構(gòu) sched_class fair_sched_class = {
    。下一個            = & idle_sched_class ，
    。 enqueue_task         = enqueue_task_fair ,
    。出隊任務(wù)        =出隊任務(wù)公平,
    。產(chǎn)量任務(wù)        =產(chǎn)量任務(wù)公平，

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

    。 rq_online         = rq_online_fair ,
    。 rq_offline         = rq_offline_fair ,

    。任務(wù)喚醒        =任務(wù)喚醒公平，
＃萬一

    。 set_curr_task = set_curr_task_fair ,
    。任務(wù)滴答        =任務(wù)滴答公平,
    。任務(wù)分叉        =任務(wù)分叉公平,

    。 prio_changed         = prio_changed_fair ,
    。 Switched_to         = Switched_to_fair ，

    。 get_rr_interval     = get_rr_interval_fair ,

#ifdef CONFIG_FAIR_GROUP_SCHED
    。任務(wù)移動組    =任務(wù)移動組公平,
＃萬一
} ;

5.2vruntime的值如何跟新？

時鐘中斷產(chǎn)生時，會依次調(diào)用tick_periodic()-> update_process_times()->scheduler_tick()。

無效調(diào)度程序_tick （無效）
{
……
    raw_spin_lock ( & rq- > lock ) ; _
    update_rq_clock ( rq ) ;
    update_cpu_load ( rq ) ;
    curr->sched_class->task_tick(rq, curr, 0); //執(zhí)行調(diào)度器tick，更新進程vruntime
    raw_spin_unlock ( & rq- > lock ) ; _
……
}
task_tick_fair ()調(diào)用entity_tick()如下：
靜態(tài)無效entity_tick （結(jié)構(gòu)cfs_rq * cfs_rq ，結(jié)構(gòu)sched_entity * curr ， int排隊）
{
    update_curr ( cfs_rq ) ;
……
    if ( cfs_rq - > nr_running > 1 | | ! sched_feat ( WAKEUP_PREEMPT ) )
        check_preempt_tick(cfs_rq, curr); //檢查當前進程是否需要調(diào)度
}

這里分析兩個重要函數(shù)update_curr()和check_preempt_tick()。

靜態(tài)無效 update_curr (結(jié)構(gòu) cfs_rq * cfs_rq )
{
    struct sched_entity * curr = cfs_rq - > curr ;
    u64現(xiàn)在 = rq_of ( cfs_rq ) - >時鐘;
    無符號長 delta_exec ；

    如果 （不太可能（！ curr ））
        返回；

// delta_exec獲得最后一次修改后，當前進程所運行的實際時間
    delta_exec = ( unsigned long ) ( now - curr - > exec_start ) ;
    如果 （！ delta_exec ）
        返回；

    __update_curr ( cfs_rq , curr , delta_exec ) ;
    curr->exec_start = now; //運行時間已保存，更新起始執(zhí)行時間

    如果 （ entity_is_task （當前）） {
        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 ) ;
    }
}

主要關(guān)心__update_curr()函數(shù)。

靜態(tài)內(nèi)聯(lián) void __update_curr （ struct cfs_rq * cfs_rq ， struct sched_entity * curr ， unsigned long delta_exec ）
{
    無符號長 delta_exec_weighted ；

    schedstat_set ( curr - > exec_max , max ( ( u64 ) delta_exec , curr - > exec_max ) ) ;

    curr->sum_exec_runtime += delta_exec;//累計實際運行時間
    schedstat_add ( cfs_rq , exec_clock , delta_exec ) ;
    delta_exec_weighted = calc_delta_fair ( delta_exec , curr ) ; //對delta_exec加權(quán)

    curr->vruntime += delta_exec_weighted;//累計入vruntime
    update_min_vruntime(cfs_rq); //更新cfs_rq最小vruntime(保存所有進程中的最小vruntime)
}

關(guān)注calc_delta_fair()加權(quán)函數(shù)如何實現(xiàn)。

/ *
 * δ / = w
 * /
靜態(tài)內(nèi)聯(lián)無符號長整型
calc_delta_fair ( unsigned long delta , struct sched_entity * se )
{
    if (不太可能( se - > load .weight ! = NICE_0_LOAD ) )
        delta = calc_delta_mine ( delta , NICE_0_LOAD , & se - >負載) ;

    返回增量；
}

若當前進程nice為0，直接返回實際運行時間，其他所有nice值的加權(quán)都是以0nice值為參考增加或減少的。

/ *
 * delta * =重量/ lw
 * /
靜態(tài)無符號長整型
calc_delta_mine (無符號長 delta_exec ,無符號長權(quán)重,
        結(jié)構(gòu) load_weight * lw )
{
    u64 tmp ；

    if ( ! lw - > inv_weight ) {
        if ( BITS_PER_LONG > 32 & &不太可能( lw - >權(quán)重> = WMULT_CONST ) )
            lw - > inv_weight = 1 ;
        別的
            lw- > inv_weight = 1 + ( WMULT_CONST - lw- >權(quán)重/ 2 ) _
                / (lw->weight+1);//這公式?jīng)]弄明白
    }

    tmp = ( u64 ) delta_exec *權(quán)重；
    / *
     *檢查64位乘法是否溢出：
     * /
    如果 （不太可能（ tmp > WMULT_CONST ））
        tmp = SRR ( SRR ( tmp , WMULT_SHIFT / 2 ) * lw - > inv_weight ,
            WMULT_SHIFT / 2 ) ;
    別的
        tmp = SRR(tmp * lw->inv_weight, WMULT_SHIFT);//做四舍五入

    返回（無符號長）分鐘（ tmp ， （ u64 ）（無符號長） LONG_MAX ）；
}

當nice!=0時，實際是按公式delta *= weight / lw來計算的weight=1024是nice0的權(quán)重，lw是當前進程的權(quán)重，該lw和nice值的換算后面介紹，上面還書的lw計算公式?jīng)]弄明白，總之這個函數(shù)就是把實際運行時間加權(quán)為進程調(diào)度里的虛擬運行時間，從而更新vruntime。

更新完vruntime之后，會檢查是否需要進程調(diào)度。

返回 static voidentity_tick ( struct cfs_rq * cfs_rq , struct sched_entity * curr , int排隊)
{
    update_curr ( cfs_rq ) ;
……
    if ( cfs_rq - > nr_running > 1 | | ! sched_feat ( WAKEUP_PREEMPT ) )
        check_preempt_tick(cfs_rq, curr); //檢查當前進程是否需要調(diào)度
}

更新完cfs_rq之后，會檢查當前進程是否已經(jīng)用完自己的“時間片”。

/ *
 *如果需要，用新喚醒的任務(wù)搶占當前任務(wù)：
 * /
靜態(tài)無效
check_preempt_tick ( struct cfs_rq * cfs_rq , struct sched_entity * curr )
{
    無符號長的 Ideal_runtime ， delta_exec ；

    ideal_runtime = sched_slice(cfs_rq, curr);//ideal_runtime是理論上的處理器運行時間片    
    delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;//該進程本輪調(diào)度累計運行時間
    if (delta_exec > ideal_runtime) {// 假如實際運行超過調(diào)度器分配的時間，就標記調(diào)度標志
        resched_task ( rq_of ( cfs_rq ) - > curr ) ;
        / *
         *當前任務(wù)運行足夠長的時間，確保它不會得到
         *由于好友的青睞而再次當選。
         * /
        清除好友( cfs_rq , curr ) ;
        返回；
    }

    / *
     *確保錯過喚醒搶占的任務(wù)
     *窄邊距不必等待完整的切片。
     *這也減少了負載下好友引起的延遲。
     * /
    if ( ! sched_feat ( WAKEUP_PREEMPT ) )
        返回；

    if ( delta_exec < sysctl_sched_min_capsularity )
        返回；

    如果 （ cfs_rq - > nr_running > 1 ） {
        struct sched_entity * se = __pick_next_entity ( cfs_rq ) ;
        s64 delta = curr - > vruntime - se - > vruntime ;

        if (增量>理想運行時間)
            resched_task ( rq_of ( cfs_rq ) - > curr ) ;
    }
}

當該進程運行時間超過實際分配的“時間片”，就標記調(diào)度標志resched_task(rq_of(cfs_rq)->curr);，否則本進程繼續(xù)執(zhí)行。中斷退出，調(diào)度函數(shù)schedule()會檢查此標記，以選取新的進程來搶占當前進程。

5.3如何選擇下一個可執(zhí)行進程

CFS選擇具有最小vruntime值的進程作為下一個可執(zhí)行進程，CFS用紅黑樹來組織調(diào)度實體，而鍵值就是vruntime。那么CFS只要查找選擇最左葉子節(jié)點作為下一個可執(zhí)行進程即可。實際上CFS緩存了最左葉子，可以直接選取left_most葉子。

上面代碼跟蹤到timer tick中斷退出，若“ideal_runtime”已經(jīng)用完，就會調(diào)用schedule()函數(shù)選中新進程并且完成切換。

asmlinkage void __sched 時間表( void )
{
    if ( prev - > state && ! ( preempt_count ( ) & PREEMPT_ACTIVE ) ) { _
        if (不太可能( signal_pending_state ( prev - > state , prev ) ) )
            上一個 - >狀態(tài)= TASK_RUNNING ;
        別的
            deactivate_task(rq, prev, 1);//如果狀態(tài)已經(jīng)不可運行，將其移除運行隊列
        switch_count = &上一個- > nvcsw ;
    }

    pre_schedule ( rq ,上一個) ;

    if (不太可能( ! rq - > nr_running ) )
        空閑平衡（ CPU ， RQ ）；

    put_prev_task(rq, prev); //處理上一個進程
    next = pick_next_task(rq);//選出下一個進程
……
    context_switch(rq, prev, next); /* unlocks the rq *///完成進程切換
……
}

如果進程狀態(tài)已經(jīng)不是可運行，那么會將該進程移出可運行隊列，如果繼續(xù)可運行put_prev_task()會依次調(diào)用put_prev_task_fair()->put_prev_entity()。

靜態(tài)無效put_prev_entity （結(jié)構(gòu)cfs_rq * cfs_rq ，結(jié)構(gòu)sched_entity * prev ）
{
    / *
     * 如果仍在運行隊列中，則deactivate_task ( )
     *沒有被調(diào)用并且update_curr ( )必須被完成：
     * /
    if (上一個- > on_rq )
        update_curr ( cfs_rq ) ;

    check_spread ( cfs_rq ,上一個) ;
    如果 （上一個- > on_rq ） {
        update_stats_wait_start ( cfs_rq ,上一個) ;
        / *將“當前”放回樹中。 * /
        __enqueue_entity ( cfs_rq ,上一個) ;
    }
    cfs_rq - > curr = NULL ;
}

__enqueue_entity(cfs_rq, prev) 將上一個進程重新插入紅黑樹(注意，當前運行進程是不在紅黑樹中的)pick_next_task()會依次調(diào)用pick_next_task_fair()。

靜態(tài)結(jié)構(gòu)task_struct * pick_next_task_fair （結(jié)構(gòu)rq * rq ）
{
    結(jié)構(gòu)任務(wù)結(jié)構(gòu)* p ;
    struct cfs_rq * cfs_rq = & rq - > cfs ;
    結(jié)構(gòu) sched_entity * se ;

    if ( ! cfs_rq - > nr_running )
        返回空值；

    做 {
        se = pick_next_entity(cfs_rq);//選出下一個可執(zhí)行進程
        set_next_entity(cfs_rq, se); //把選中的進程(left_most葉子)從紅黑樹移除，更新紅黑樹
        cfs_rq = group_cfs_rq （ se ）；
    } while ( cfs_rq ) ;

    p = task_of ( se ) ;
    htick_start_fair ( rq , p ) ;

    返回 p ；
}

set_next_entity()函數(shù)會調(diào)用__dequeue_entity(cfs_rq, se)把選中的下一個進程即最左葉子移出紅黑樹。最后context_switch()完成進程的切換。

5.4何時更新rbtree

①上一個進程執(zhí)行完ideal_time，還可繼續(xù)執(zhí)行時，會插入紅黑樹；

②下一個進程被選中移出rbtree紅黑樹時；

③新建進程；

④進程由睡眠態(tài)被激活，變?yōu)榭蛇\行態(tài)時；

⑤調(diào)整優(yōu)先級時也會更新rbtree。

5.5新建進程如何加入紅黑樹

新建進程會做一系列復(fù)雜的工作，這里我們只關(guān)心與紅黑樹有關(guān)部分

Linux使用fork，clone或者vfork等系統(tǒng)調(diào)用創(chuàng)建進程，最終都會到do_fork函數(shù)實現(xiàn)，如果沒有設(shè)置CLONE_STOPPED，do_fork會執(zhí)行兩個與紅黑樹相關(guān)的函數(shù): copy_process()和wake_up_new_task()

(1)copy_process()->sched_fork()->task_fork()

static void place_entity ( struct cfs_rq * cfs_rq ， struct sched_entity * se ， int初始值)
{
    u64 vruntime = cfs_rq->min_vruntime;//以cfs的最小vruntime為基準

    / *
     * “當前”期間已承諾當前任務(wù)， _
     *然而，新任務(wù)的額外重量會減慢他們的速度
     *小，放置新任務(wù)，使其適合該插槽
     *最后保持打開狀態(tài)。
     * /
    if (初始&& sched_feat ( START_DEBIT ) ) _
        vruntime += sched_vslice(cfs_rq, se);// 加上一個調(diào)度周期內(nèi)的"時間片"

    / *休眠至單個延遲不計算在內(nèi)。 * /
    if ( ! initial & & sched_feat ( FAIR_SLEEPERS ) ) {
        無符號長閾值= sysctl_sched_latency ；

        / *
         *將休眠閾值轉(zhuǎn)換為虛擬時間。
         * SCHED_IDLE是一個特殊的子類。我們關(guān)心
         *公平性僅相對于其他 SCHED_IDLE 任務(wù)，
         *所有這些都具有相同的重量。
         * /
        if ( sched_feat ( NORMALIZED_SLEEPER ) & & ( ! entity_is_task ( se ) | |
                 task_of ( se ) - >策略！= SCHED_IDLE ) )
            thresh = calc_delta_fair ( thresh , se ) ;

        / *
         *將睡眠時間的影響減半， 以允許
         * 為睡眠者帶來更溫和的效果：
         * /
        如果 （ sched_feat （ GENTLE_FAIR_SLEEPERS ））
            脫粒> > = 1 ;

        vruntime - = 閾值；
    }

    / *確保我們永遠不會因為被排在后面而贏得時間。 * /
    vruntime = max_vruntime ( self - > vruntime , vruntime ) ;

    se - > vruntime = vruntime ;
}

計算新進程的vruntime值，加上一個“平均時間片”表示剛執(zhí)行完，避免新建進程立馬搶占CPU。

(2)調(diào)用wake_up_new_task函數(shù)

無效wake_up_new_task （ struct task_struct * p ，無符號長clone_flags ）
{
……
    rq = task_rq_lock ( p , & flags ) ;
    update_rq_clock ( rq ) ;
    activate_task(rq, p, 0);//激活當前進程，添加入紅黑樹
check_preempt_curr(rq, p, WF_FORK);//確認是否需要搶占
    ……
}

更新時鐘，激活新建的進程activate_task()會調(diào)用。

static void enqueue_task ( struct rq * rq , struct task_struct * p , intwakeup , bool head )
{
    如果 （喚醒）
        p- > se 。_ start_runtime = p - > se 。 sum_exec_運行時；

    sched_info_queued ( p ) ;
    p- > sched_class- > enqueue_task ( rq , p ,喚醒, head ) ; _ _
    p- > se 。_ on_rq = 1 ;
}

將新建的進程加入rbtree。

5.6喚醒進程

調(diào)用try_to_wake_up()->activate_task()->enqueue_task_fair()->enqueue_entity()注意enqueue_entity 函數(shù)調(diào)用place_entity對進程vruntime做補償計算，再次考察place_entity(cfs_rq, se, 0)。

static void place_entity ( struct cfs_rq * cfs_rq ， struct sched_entity * se ， int初始值)
{
    u64 vruntime = cfs_rq->min_vruntime;//以cfs的最小vruntime為基準

    / *
     * “當前”期間已承諾當前任務(wù)， _
     *然而，新任務(wù)的額外重量會減慢他們的速度
     *小，放置新任務(wù)，使其適合該插槽
     *最后保持打開狀態(tài)。
     * /
    if (初始&& sched_feat ( START_DEBIT ) ) _
        vruntime += sched_vslice(cfs_rq, se);//一個調(diào)度周期內(nèi)的"時間片"

    / *休眠至單個延遲不計算在內(nèi)。 * /
    if ( ! initial & & sched_feat ( FAIR_SLEEPERS ) ) {
        無符號長閾值= sysctl_sched_latency ；

        / *
         *將休眠閾值轉(zhuǎn)換為虛擬時間。
         * SCHED_IDLE是一個特殊的子類。我們關(guān)心
         *公平性僅相對于其他 SCHED_IDLE 任務(wù)，
         *所有這些都具有相同的重量。
         * /
        if ( sched_feat ( NORMALIZED_SLEEPER ) & & ( ! entity_is_task ( se ) | |
                 task_of ( se ) - >策略！= SCHED_IDLE ) )
            thresh = calc_delta_fair ( thresh , se ) ;

        / *
         *將睡眠時間的影響減半， 以允許
         * 為睡眠者帶來更溫和的效果：
         * /
        如果 （ sched_feat （ GENTLE_FAIR_SLEEPERS ））
            脫粒> > = 1 ;

        vruntime -= thresh;//對于睡眠進程喚醒，給予vruntime補償
    }

    / *確保我們永遠不會因為被排在后面而贏得時間。 * /
    vruntime = max_vruntime(se->vruntime, vruntime);//避免通過睡眠來獲得運行時間

    se - > vruntime = vruntime ;
}

當initial=1時，新建進程vruntime=cfs最小vruntime值+時間片，放入紅黑樹最右端。

當initial=0時，表示喚醒進程，vruntime要減去一個thresh.這個thresh由調(diào)度周期sysctl_sched_latency加權(quán)得到虛擬時間，這樣做可以對睡眠進程做一個補償，喚醒時會得到一個較小的vruntime, 使它可以盡快搶占CPU(可以快速響應(yīng)I/O消耗型進程)。

注意注釋/* ensure we never gain time by being placed backwards. */這個設(shè)計是為了給睡眠較長時間的進程做時間補償?shù)?，既使其可以快速搶占，又避免因太小的vruntime值而長期占用CPU。但有些進程只是短時間睡眠，這樣喚醒時自身vruntime還是大于min_vruntime的，為了不讓進程通過睡眠獲得額外運行時間補償，最后vruntime取計算出的補償時間和進程本身的vruntime較大者。從這可以看出，雖然CFS不再區(qū)分I/O消耗型，CPU消耗型進程，但是CFS模型對IO消耗型天然的提供了快速的響應(yīng)。

5.7改變進程優(yōu)先級，如何調(diào)整rbtree

Linux中改變進程優(yōu)先級會調(diào)用底層的set_user_nice()。

void set_user_nice （ struct task_struct * p ，長nice ）
{
……
    dequeue_task(rq, p, 0); //把進程從紅黑樹中取出
……
    p->static_prio = NICE_TO_PRIO(nice);//將nice(-20~19)值映射到100~139,0~99是實時進程優(yōu)先級
    設(shè)置負載重量（ p ）；
……
    enqueue_task ( rq , p , 0 , false ) ;
}

set_user_nice把進程從紅黑樹取出，調(diào)整優(yōu)先級(nice值對應(yīng)權(quán)重)，再重新加入紅黑樹。

set_load_weight()函數(shù)是設(shè)置nice值對應(yīng)的權(quán)重。

靜態(tài)無效set_load_weight （結(jié)構(gòu)task_struct * p ）
{
    如果 （ task_has_rt_policy （ p ）） {
        p- > se 。_負載。重量= 0 ；
        p- > se 。_負載。 inv_weight = WMULT_CONST ;
        返回；
    }

    / *
     * SCHED_IDLE 任務(wù)獲得最小權(quán)重：
     * /
    如果 （ p - >政策== SCHED_IDLE ）{ _
        p- > se 。_負載。重量= WEIGHT_IDLEPRIO ；
        p- > se 。_負載。 inv_weight = WMULT_IDLEPRIO ;
        返回；
    }

    p- > se 。_負載。權(quán)重= prio_to_weight [ p - > static_prio - MAX_RT_PRIO ] ;
    p- > se 。_負載。 inv_weight = prio_to_wmult [ p - > static_prio - MAX_RT_PRIO ] ;
}

數(shù)組prio_to_weight[]是將nice值(-20~19)轉(zhuǎn)化為以nici 0(1024)值為基準的加權(quán)值,根據(jù)內(nèi)核注釋每一個nice差值，權(quán)重相差10%，即在負載一定的條件下，每增加或減少一個nice值，獲得的CPU時間相應(yīng)增加或減少10%。

靜態(tài)常量 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 ,
} ;

上面calc_delta_mine()函數(shù)用到這個數(shù)組加權(quán)值，這個轉(zhuǎn)化過程還沒弄明白，有明白的朋友，指點一二，不勝感激。

/ *
 * prio_to_weight [ ]數(shù)組的反( 2^32 / x )值，預(yù)先計算。
 *
 * 在重量不經(jīng)常變化的情況下，我們可以使用
 *預(yù)先計算逆數(shù)以通過轉(zhuǎn)動除法來加速算術(shù)
 *轉(zhuǎn)化為乘法：
 * /
靜態(tài)常量u32 prio_to_wmult [ 40 ] = {
 / * - 20 * / 48388 , 59856 , 76040 , 92818 , 118348 ,
 / * - 15 * / 147320 , 184698 , 229616 , 287308 , 360437 ,
 / * - 10 * / 449829 , 563644 , 704093 , 875809 , 1099582 ,
 / * - 5 * / 1376151 , 1717300 , 2157191 , 2708050 , 3363326 ,
 / * 0 * / 4194304、5237765、6557202、8165337、10153587 、 _ _ _ _ _ _ _ _
 / * 5 * / 12820798、15790321、19976592、24970740、31350126 、_ _ _ _ _ _ _ _
 / * 10 * / 39045157、49367440、61356676、76695844、95443717 、 _ _ _ _ _ _ _ _
 / * 15 * / 119304647、148102320、186737708、238609294、286331153 、 _ _ _ _ _ _ _ _
} ;

最后，說下對CFS “完全公平” 的理解：

①不再區(qū)分進程類型，所有進程公平對待

②對I/O消耗型進程，仍然會提供快速響應(yīng)(對睡眠進程做時間補償)

③優(yōu)先級高的進程，獲得CPU時間更多(vruntime增長的更慢)

可見CFS的完全公平，并不是說所有進程絕對的平等，占用CPU時間完全相同，而是體現(xiàn)在vruntime數(shù)值上，所有進程都用虛擬時間來度量，總是讓vruntime最小的進程搶占，這樣看起來是完全公平的，但實際上vruntime的更新，增長速度，不同進程是不盡一樣的。CFS利用這么個簡單的vruntime機制，實現(xiàn)了以往需要相當復(fù)雜算法實現(xiàn)的進度調(diào)度需求，高明！