linux內(nèi)核源代碼分析-進程管理及調(diào)度

1、進程管理、調(diào)度 進程管理任務 進程管理與其他模塊的依賴關系 進程描述符及任務隊列 進程的創(chuàng)建(FORK,copy-on-write) 線程實現(xiàn) 進程的終止 進程調(diào)度進程管理的任務 允許進程復制自己 （真正作到一個應用多進程） 確定哪個進程能夠擁有CPU 接受中斷并將中斷導向響應的內(nèi)核子系統(tǒng) 向用戶進程發(fā)送信號 管理時鐘硬件 當一個進程結束時，釋放其資源 動態(tài)裝載執(zhí)行模塊進程模塊與其他模塊的依賴關系在整個內(nèi)核中的功能位置和源碼依賴關系 進程模塊與其他模塊的依賴關系進程調(diào)度模塊的內(nèi)外界面 對用戶進程提供了一組簡單的系統(tǒng)調(diào)用接口； 對內(nèi)核的其他模塊提供了豐富的接口功能。 進程模塊與其他模塊的依賴關系

2、進程調(diào)度模塊和其他模塊的相互依賴關系 內(nèi)存管理模塊：當一個進程被調(diào)度的時候，為它建立內(nèi)存映射。 IPC子模塊：bottom-half處理使用了其中的信號量隊列。 文件系統(tǒng)模塊：在裝載module的時候為進程調(diào)度提供實際設備的 訪問途徑。所有的其他模塊都依賴于進程調(diào)度模塊，因為當要進行硬件訪問的時候它們需要CPU掛起用戶進程，切換到系統(tǒng)態(tài)進行處理。. 進程描述符及任務隊列 分配進程描述符（http:/lxr.linux.no） 預分配描述符（SLAB機制），把動態(tài)分配的過程省略掉一部分（不需要頻繁調(diào)用內(nèi)存管理響應功能），相當于一種高級緩存，提高效率。最后的操作主要是直接填寫結構。 進程描述符的存

3、放 PID(為兼容原來的PID為unsigned short,最大32767，可以通過/proc修改設置) 獲得當前進程描述符的指針（CURRENT宏、專門寄存器）進程描述符及任務隊列進程狀態(tài)#define TASK_RUNNING 0（進程是可執(zhí)行的或正在執(zhí)行） #define TASK_INTERRUPTIBLE 1（進程睡眠或阻塞，等待某一事件到來中斷它）#define TASK_UNINTERRUPTIBLE 2（進程睡眠或阻塞，不能其他進程的信號打斷，直接等待硬件條件）#define TASK_ZOMBIE 4（僵尸，呆傻狀態(tài)，已結束，但其父進程未接到通知，描述符未釋放） #defi

4、ne TASK_STOPPED 8（進程停止，接受到SIGSTP信號） #define TASK_SWAPPING 16 （進程頁面被兌換出內(nèi)存）進程描述符及任務隊列進程狀態(tài)轉換圖 設置當前進程狀態(tài)（有很多情況會設置進程狀態(tài)（思考）set_task_state(task,state)）進程的上下文（進程環(huán)境：用戶、資源等）系統(tǒng)調(diào)用時，內(nèi)核“代表進程”執(zhí)行，上下文有效進程之間的聯(lián)系也屬進程的環(huán)境（INIT為第一個進程，描述符中Parent,Children指針將這種環(huán)境連接起來，可以從任一個進程出發(fā)遍歷系統(tǒng)的所有進程）進程描述符及任務隊列索引組織形式之一：隊列進程描述符及任務隊列索引組織形式之二

5、：樹進程的創(chuàng)建(FORK,copy-on-write) 進程創(chuàng)建過程描述 Linux中，進程的創(chuàng)建是通過拷貝已存在進程來實現(xiàn)的。在Linux內(nèi)核啟動的時候，首先由start_kernel()初始化各個系統(tǒng)數(shù)據(jù)結構，同時生成了和系統(tǒng)共存亡的后臺進程：init。init進程通過拷貝自身，產(chǎn)生了若干內(nèi)核子進程。然后這些進程就可以通過系統(tǒng)調(diào)用fork()生成它們的子進程，當然這些子進程的原始數(shù)據(jù)都是他們的父親的副本。進程的終止是通過系統(tǒng)調(diào)用_exit()實現(xiàn)的。LINUX中的進程創(chuàng)建FORK()：進程復制自身產(chǎn)生其子進程EXEC()：加載可執(zhí)行代碼模塊覆蓋自身代碼COPY_ON_WRITE ：寫時co

6、py進程的創(chuàng)建(FORK,copy-on-write)FORK()FORK（）、VFORK（）、_CLONE()=CLONE()=DO_FORK()(在kernel/fork.c中) =COPY_PROCESS(),并執(zhí)行dup_task_struct(建內(nèi)核棧、thread_info、task_struct); 檢查進程數(shù)目限制； 描述符設置，以區(qū)別于父進程； 子進程狀態(tài)設置為TASK_UNINTERRUPTIBLE copy_flags get_pid 資源引用復制 父子進程平分剩余時間片 返回指向子進程的指針（一般子進程先執(zhí)行）（注意：此時并未復制代碼）進程的創(chuàng)建(FORK,copy-o

7、n-write) EXEC() 對應內(nèi)核中一族函數(shù)：execve(),execv(),execlp(),execvp()負責加載可執(zhí)行的代碼，覆蓋本進程的代碼、數(shù)據(jù)。 COPY_ON_WRITE ：寫時copy LINUX的FORK()過程并未為新生成的進程馬上復制代碼，開始的進程僅僅讀共享父進程代碼。 直到進程第一次要對進程空間有寫請求時，再復制代碼。 這樣做的好處：效率高（一般新進程要有自己的代碼，第一條就是EXEC()）進程的創(chuàng)建(FORK,copy-on-write) FORK()應用實例main()pid_tpid;pintf(“this location in parent pro

8、cessn”);if (pid=fork()= =0) printf(“this location in child processn”);execlv(.);進程的創(chuàng)建(FORK,copy-on-write)VFORK() 除不拷貝父進程的頁表項和FORK（）完全相同。 目前已基本不用。 體會一下書上20頁有關VFORK（）主要過程的描述線程實現(xiàn) Linux沒有真正的線程（線程與進程的比較） 僅僅是進程之間資源直接共享的一種機制通過CLONE時參數(shù)實現(xiàn)：請看一下書的有關描述（有些參數(shù)標明共享打開文件）。 相當于實現(xiàn)了線程概念的一部分（資源共享）。 內(nèi)核線程 獨立運行在內(nèi)核的標準進程（后面章節(jié)

9、再做討論）進程的終止 進程運行結束時要釋放相應的資源，通過EXIT()調(diào)用實現(xiàn)（顯式或隱式） EXIT()實現(xiàn)時調(diào)用了do_exit()完成以下工作 Task_struct中標志成員設為：PF_EXITING 調(diào)用_exit_mm() 調(diào)用sem_exit() 調(diào)用_exit_files(),_exit_fs(),exit_name_space,exit_sighand 退出代碼替換為EXIT()提供的代碼 調(diào)用Exit_notify()向父進程發(fā)信號，（標為ZOOMBIE) 調(diào)用shedule切換到其他進程進程的終止 刪除進程描述符 父進程得知子進程終止的消息后才能刪除子進程的描述符。（思考

10、：若父進程異常終止，將會發(fā)生什么情況） 父進程WAIT()，返回時可以根據(jù)代碼做相應動作（或者IGNORE），動作完成后真正釋放描述符（調(diào)用release_task） 調(diào)用free_uid:進程記數(shù) Unhash_process()：刪除pidhash中的項同時刪除task_list中的項 若有trace刪除ptrace_list對應項 調(diào)用put_task_struct釋放描述符，（內(nèi)核棧、threadinfo所占的頁、slab高速緩存。進程調(diào)度 搶占式（preemtive）和非搶占式（cooprative） 進程調(diào)度的策略 IO消耗型和CPU消耗型進程 UNIX系列的傾向于IO消耗型優(yōu)先

11、進程的優(yōu)先級動態(tài)優(yōu)先級（調(diào)度程序根據(jù)情況增或減其優(yōu)先數(shù)-20-19） 時間片 長短定義是個很矛盾的事情（默認一個值） LINUX提供可變長的時間片 進程搶占 LINUX用搶占式調(diào)度（一個新的進程進入時，要看優(yōu)先級別） 調(diào)度策略的活動（一個編輯程序和一個后臺程序比較）進程調(diào)度 調(diào)度算法-LINUX調(diào)度在2.5以后的實現(xiàn)目標 O(1)調(diào)度 SMP的可擴展性 強化SMP的親和力（盡量將相關的一組任務分配給一個CPU） 加強交互性 保證公平 對多CPU的支持增強（忙時每個CPU都有進程執(zhí)行）主要問題：怎樣實現(xiàn)了O(1)調(diào)度？進程調(diào)度 LINUX圍繞以下幾個方面對調(diào)度算法進行改進 運行隊列在 2.4 內(nèi)

12、核中，就緒進程隊列是一個全局數(shù)據(jù)結構，調(diào)度器對它的所有操作都會因全局自旋鎖而導致系統(tǒng)各個處理機之間的等待，使得就緒隊列成為一個明顯的瓶頸。在 2.6 中，就緒隊列定義為一個復雜得多的數(shù)據(jù)結構 struct runqueue，并且，尤為關鍵的是，每一個 CPU 都將維護一個自己的就緒隊列，-這將大大減小競爭。 1）prio_array_t *active, *expired, arrays2 每個 CPU 的就緒隊列按時間片是否用完分為兩部分，分別通過 active 指針和 expired 指針訪問，active 指向時間片沒用完、當前可被調(diào)度的就緒進程，expired 指向時間片已用完的就緒進

13、程。每一類就緒進程都用一個 struct prio_array 的結構表示： 進程調(diào)度圖中的 task 并不是 task_struct 結構指針，而是 task_struct:run_list，這是一個小技巧，詳見下面 run_list 的解釋。 2.4版本里選擇最佳侯選進程是schedule（）進行的（O(n)）,在新的 O(1) 調(diào)度中，這一查找過程分解為 n 步，每一步所耗費的時間都是 O(1) 量級的。 prio_array 中包含一個就緒隊列數(shù)組，數(shù)組的索引是進程的優(yōu)先級（共 140 級，詳見下 “static_prioqueue 中。調(diào)度時直接給出就緒隊列 active 中具有最高

14、優(yōu)先級的鏈表中的第一項作為候選進程（參見”調(diào)度器“），而優(yōu)先級的計算過程則分布到各個進程的執(zhí)行過程中進行” 屬性的說明），相同優(yōu)先級的進程放置在相應數(shù)組元素的鏈表。為了加速尋找存在就緒進程的鏈表，2.6 核心又建立了一個位映射數(shù)組來對應每一個優(yōu)先級鏈表，如果該優(yōu)先級鏈表非空，則對應位為 1，否則為 0。核心還要求每個體系結構都構造一個 sched_find_first_bit() 函數(shù)來執(zhí)行這一搜索操作，快速定位第一個非空的就緒進程鏈表。 采用這種將集中計算過程分散進行的算法，保證了調(diào)度器運行的時間上限，同時在內(nèi)存中保留更加豐富的信息的做法也加速了候選進程的定位過程。這一變化簡單而又高效，是

15、2.6 內(nèi)核中的亮點之一。 arrays 二元數(shù)組是兩類就緒隊列的容器，active 和 expired 分別指向其中一個。active 中的進程一旦用完了自己的時間片，就被轉移到 expired 中，并設置好新的初始時間片；而當 active 為空時，則表示當前所有進程的時間片都消耗完了，此時，active 和 expired 進行一次對調(diào)，重新開始下一輪的時間片遞減過程 進程調(diào)度struct prio_array int nr_active; /* 本進程組中的進程數(shù) */ struct list_head queueMAX_PRIO; /* 以優(yōu)先級為索引的 HASH 表，見下 */ u

16、nsigned long bitmapBITMAP_SIZE; /* 加速以上 HASH 表訪問的位圖，見下 */ ; 進程調(diào)度2）spinlock_t lock runqueue 的自旋鎖，當需要對 runqueue 進行操作時，仍然應該鎖定，但這個鎖定操作只影響一個 CPU 上的就緒隊列，因此，競爭發(fā)生的概率要小多了。 3） task_t *curr本 CPU 正在運行的進程。4）tast_t *idle 指向本 CPU 的 idle 進程，相當于 2.4 中 init_tasksthis_cpu() 的作用。 5）int best_expired_prio 記錄 expired 就緒進程

17、組中的最高優(yōu)先級（數(shù)值最小）。該變量在進程進入 expired 隊列的時候保存。6）unsigned long expired_timestamp 當新一輪的時間片遞減開始后，這一變量記錄著最早發(fā)生的進程耗完時間片事件的時間（jiffies 的絕對值，在 schedule_tick() 中賦），它用來表征 expired 中就緒進程的最長等待時間。它的使用體現(xiàn)在 EXPIRED_STARVING(rq) 宏上。 上面已經(jīng)提到，每個 CPU 上維護了兩個就緒隊列，active 和 expired。一般情況下，時間片結束的進程應該從 active 隊列轉移到 expired 隊列中（schedul

18、e_tick()），但如果該進程是交互式進程，調(diào)度器就會讓其保持在 active 隊列上以提高它的響應速度。這種措施不應該讓其他就緒進程等待過長時間，也就是說，如果 expired 隊列中的進程已經(jīng)等待了足夠長時間了，即使是交互式進程也應該轉移到 expired 隊列上來，排空 active。這個閥值就體現(xiàn)在EXPIRED_STARVING(rq) 上：在 expired_timestamp 和 STARVATION_LIMIT 都不等于 0 的前提下，如果以下兩個條件都滿足，則 EXPIRED_STARVING() 返回真：（當前絕對時間 - expired_timestamp） = （ST

19、ARVATION_LIMIT * 隊列中所有就緒進程總數(shù) + 1），也就是說 expired 隊列中至少有一個進程已經(jīng)等待了足夠長的時間； 正在運行的進程的靜態(tài)優(yōu)先級比 expired 隊列中最高優(yōu)先級要低（best_expired_prio，數(shù)值要大），此時當然應該盡快排空 active 切換到expired 上來。進程調(diào)度7）struct mm_struct *prev_mm保存進程切換后被調(diào)度下來的進程（稱之為 prev）的 active_mm 結構指針。因為在 2.6 中 prev 的 active_mm 是在進程切換完成之后釋放的（mmdrop()），而此時 prev 的 activ

20、e_mm 項可能為 NULL，所以有必要在 runqueue 中預先保留。8）unsigned long nr_running 本 CPU 上的就緒進程數(shù)，該數(shù)值是 active 和 expired 兩個隊列中進程數(shù)的總和，是說明本 CPU 負載情況的重要參數(shù)。9）unsigned long nr_switches 記錄了本 CPU 上自調(diào)度器運行以來發(fā)生的進程切換的次數(shù)。 10）unsigned long nr_uninterruptible記錄本 CPU 尚處于 TASK_UNINTERRUPTIBLE 狀態(tài)的進程數(shù)，和負載信息有關。進程調(diào)度11）atomic_t nr_iowait記錄本

21、 CPU 因等待 IO 而處于休眠狀態(tài)的進程數(shù)。12）unsigned long timestamp_last_tick本就緒隊列最近一次發(fā)生調(diào)度事件的時間，在負載平衡的時候會用到。13）int prev_cpu_loadNR_CPUS記錄進行負載平衡時各個 CPU 上的負載狀態(tài)（此時就緒隊列中的 nr_running 值），以便分析負載情況。進程調(diào)度運行時間片的計算運行時間片的計算 老版本的LINUX的計算for (系統(tǒng)中的每個任務) 重新計算優(yōu)先級 重新計算時間片 新版本不用這樣計算。（見書32頁圖） 1) time_slice 基準值和 counter 類似，進程的缺省時間片與進程的靜態(tài)

22、優(yōu)先級（在 2.4 中是 nice 值）相關，使用如下公式得出：MIN_TIMESLICE + (MAX_TIMESLICE - MIN_TIMESLICE) * (MAX_PRIO-1 - (p)-static_prio) / (MAX_USER_PRIO-1) 代入各個宏的值后，結果如下圖所示：核心將 100139 的優(yōu)先級映射到 200ms10ms 的時間片上去，優(yōu)先級數(shù)值越大，則分配的時間片越小。和 2.4 中進程的缺省時間片比較，當 nice 為 0 時，2.6 的基準值 100ms 要大于 2.4 的 60ms。2) time_slice 的變化進程的 time_slice 值代表

23、進程的運行時間片剩余大小，在進程創(chuàng)建時與父進程平分時間片，在運行過程中遞減，一旦歸 0，則按 static_prio 值重新賦予上述基準值，并請求調(diào)度。時間片的遞減和重置在時鐘中斷中進行（sched_tick()），除此之外，time_slice 值的變化主要在創(chuàng)建進程和進程退出過程中： a) 進程創(chuàng)建和 2.4 類似，為了防止進程通過反復 fork 來偷取時間片，子進程被創(chuàng)建時并不分配自己的時間片，而是與父進程平分父進程的剩余時間片。也就是說，fork 結束后，兩者時間片之和與原先父進程的時間片相等。b) 進程退出進程退出時（sched_exit()），根據(jù) first_time_slice

24、 的值判斷自己是否從未重新分配過時間片，如果是，則將自己的剩余時間片返還給父進程（保證不超過 MAX_TIMESLICE）。這個動作使進程不會因創(chuàng)建短期子進程而受到懲罰（與不至于因創(chuàng)建子進程而受到獎勵相對應）。如果進程已經(jīng)用完了從父進程那分得的時間片，就沒有必要返還了（這一點在 2.4 中沒有考慮）。3）time_slice 對調(diào)度的影響在 2.4 中，進程剩余時間片是除 nice 值以外對動態(tài)優(yōu)先級影響最大的因素，并且休眠次數(shù)多的進程，它的時間片會不斷疊加，從而算出的優(yōu)先級也更大，調(diào)度器正是用這種方式來體現(xiàn)對交互式進程的優(yōu)先策略。但實際上休眠次數(shù)多并不表示該進程就是交互式的，只能說明它是 I

25、O 密集型的，因此，這種方法精度很低，有時因為誤將頻繁訪問磁盤的數(shù)據(jù)庫應用當作交互式進程，反而造成真正的用戶終端響應遲緩。2.6 的調(diào)度器以時間片是否耗盡為標準將就緒進程分成 active、expired 兩大類，分別對應不同的就緒隊列，前者相對于后者擁有絕對的調(diào)度優(yōu)先權-僅當active 進程時間片都耗盡，expired 進程才有機會運行。但在 active 中挑選進程時，調(diào)度器不再將進程剩余時間片作為影響調(diào)度優(yōu)先級的一個因素，并且為了滿足內(nèi)核可剝奪的要求，時間片太長的非實時交互式進程還會被人為地分成好幾段（每一段稱為一個運行粒度，定義見下）運行，每一段運行結束后，它都從 cpu 上被剝奪下

26、來，放置到對應的 active 就緒隊列的末尾，為其他具有同等優(yōu)先級的進程提供運行的機會。優(yōu)先級計算方法 在 2.4 內(nèi)核中，優(yōu)先級的計算和候選進程的選擇集中在調(diào)度器中進行，無法保證調(diào)度器的執(zhí)行時間，這一點在前面介紹 runqueue 數(shù)據(jù)結構的時候已經(jīng)提及。2.6 內(nèi)核中候選進程是直接從已按算法排序的優(yōu)先級隊列數(shù)組中選取出來的，而優(yōu)先級的計算則分散到多處進行。這一節(jié)分成兩個部分對這種新的優(yōu)先級計算方法進行描述，一部分是優(yōu)先級計算過程，一部分是優(yōu)先級計算（以及進程入隊）的時機。1）優(yōu)先級計算過程 動態(tài)優(yōu)先級的計算主要由 effect_prio() 函數(shù)完成，該函數(shù)實現(xiàn)相當簡單，從中可見非實時進

27、程的優(yōu)先級僅決定于靜態(tài)優(yōu)先級（static_prio）和進程的sleep_avg 值兩個因素，而實時進程的優(yōu)先級實際上是在 setscheduler() 中設置的（詳見“調(diào)度系統(tǒng)的實時性能”，以下僅考慮非實時進程），且一經(jīng)設定就不再改變。相比較而言，2.4 的 goodness() 函數(shù)甚至要更加復雜,它考慮的 CPU Cache 失效開銷和內(nèi)存切換的開銷這里都已經(jīng)不再考慮。2.6 的動態(tài)優(yōu)先級算法的實現(xiàn)關鍵在 sleep_avg 變量上，在 effective_prio() 中，sleep_avg 的范圍是 0MAX_SLEEP_AVG，經(jīng)過以下公式轉換后變成-MAX_BONUS/2MAX_

28、BONUS/2 之間的 bonus：(NS_TO_JIFFIES(p)-sleep_avg) * MAX_BONUS / MAX_SLEEP_AVG) - MAX_BONUS/2 如下圖所示： 再用這個 bonus 去減靜態(tài)優(yōu)先級就得到進程的動態(tài)優(yōu)先級（并限制在 MAX_RT_PRIO和MAX_PRIO 之間），bonus 越小，動態(tài)優(yōu)先級數(shù)值越大，優(yōu)先級越低。也就是說，sleep_avg 越大，優(yōu)先級也越高。2) 優(yōu)先級計算時機優(yōu)先級的計算不再集中在調(diào)度器選擇候選進程的時候進行了，只要進程狀態(tài)發(fā)生改變，核心就有可能計算并設置進程的動態(tài)優(yōu)先級： a) 創(chuàng)建進程創(chuàng)建進程在wake_up_fork

29、ed_process()中，子進程繼承了父進程的動態(tài)優(yōu)先級，并添加到父進程所在的就緒隊列中。如果父進程不在任何就緒隊列中（例如它是 IDLE 進程），那么就通過 effect_prio() 函數(shù)計算出子進程的優(yōu)先級，而后根據(jù)計算結果將子進程放置到相應的就緒隊列中。b) 喚醒休眠進程喚醒休眠進程核心調(diào)用 recalc_task_prio() 設置從休眠狀態(tài)中醒來的進程的動態(tài)優(yōu)先級，再根據(jù)優(yōu)先級放置到相應就緒隊列中。c) 調(diào)度到從調(diào)度到從 TASK_INTERRUPTIBLE 狀態(tài)中被喚醒的進程狀態(tài)中被喚醒的進程實際上此時調(diào)度器已經(jīng)選定了候選進程，但考慮到這一類型的進程很有可能是交互式進程，因此此

30、時仍然調(diào)用 recalc_task_prio() 對該進程的優(yōu)先級進行修正（詳見進程平均等待時間 sleep_avg），修正的結果將在下一次調(diào)度時體現(xiàn)。d) 進程因時間片相關的原因被剝奪進程因時間片相關的原因被剝奪 cpu在 schedule_tick() 中（由時鐘中斷啟動），進程可能因兩種原因被剝奪 cpu，一是時間片耗盡，一是因時間片過長而分段。這兩種情況都會調(diào)用effect_prio() 重新計算優(yōu)先級，重新入隊。e) 其它時機其它時機這些其它時機包括 IDLE 進程初始化（init_idle()）、負載平衡（move_task_away()，詳見調(diào)度器相關的負載平衡）以及修改 nice 值（set_user_nice()）、修改調(diào)度策略（setscheduler()）等主動要求改變優(yōu)先級的情況。由上可見，2.6 中動態(tài)優(yōu)先級的計算過程在各個進程運行過程中進行，避免了類似 2.4 系統(tǒng)中就緒進程很