linux內(nèi)核進程調(diào)度以及定時器實現(xiàn)機制（看完悟了！）
一、2.6版以前內(nèi)核進程調(diào)度機制簡介
Linux的進程管理由進程控制塊、進程調(diào)度、中斷處理、任務隊列、定時器、bottom half隊列、系統(tǒng)調(diào)用、進程通信等等部分組成。
進程調(diào)用分為實時進程調(diào)度和非實時進程調(diào)度兩種。前者調(diào)度時，可以采用基于動態(tài)優(yōu)先級的輪轉(zhuǎn)法（RR），也可以采用先進現(xiàn)出算法（FIFO）。后者調(diào)度時，一律采用基于動態(tài)優(yōu)先級的輪轉(zhuǎn)法。某個進程采用何種調(diào)度算法由改進程的進程控制塊中的某些屬性決定，沒有專門的系統(tǒng)用來處理關于進程調(diào)度的相關事宜。Linux的進程調(diào)度由schedule（）函數(shù)負責，任何進程，當它從系統(tǒng)調(diào)用返回時，都會轉(zhuǎn)入schedule（），而中斷處理函數(shù)完成它們的響應任務以后，也會進入schedule（）。
1、進程控制塊數(shù)據(jù)結(jié)構
Linux系統(tǒng)的進程控制塊用數(shù)據(jù)結(jié)構task_struct表示，這個數(shù)據(jù)結(jié)構占用1680個字節(jié)，具體的內(nèi)容不在這里介紹，詳細內(nèi)容見《Linux內(nèi)核2.4版源代碼分析大全》第二頁。
進程的狀態(tài)主要包括如下幾個：
TASK_RUNNING ? 正在運行或在就緒隊列run-queue中準備運行的進程，實際參與進程調(diào)度。
TASK_INTERRUPTIBLE ? ? ? 處于等待隊列中的進程，待資源有效時喚醒，也可由其它進程通過信號或定時中斷喚醒后進入就緒隊列run-queue。
TASK_UNINTERRUPTIBLE ? ? ? ? 處于等待隊列的進程，待資源有效時喚醒，不也可由其它進程通過信號或者定時中斷喚醒。
TASK_ZOMBIE ? ? ?表示進程結(jié)束但尚未消亡的一種狀態(tài)（僵死），此時，進程已經(jīng)結(jié)束運行并且已經(jīng)釋放了大部分資源，但是尚未釋放進程控制塊。
TASK_STOPPED ? ?進程暫停，通過其它進程的信號才能喚醒。
所有進程（以PCB形式）組成一個雙向列表。next_task和prev_task就是鏈表的前后向指針。鏈表的頭尾都是init_task（init進程）。不過進程還要根據(jù)其進程ID號插入到一個hash表當中，目的是加快進程搜索速度。
【文章福利】小編推薦自己的Linux內(nèi)核技術交流群:【891587639】整理了一些個人覺得比較好的學習書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書、實戰(zhàn)項目及代碼)? ??
2、進程調(diào)度
Linux進程調(diào)度由schedule（）執(zhí)行，其任務是在run-queue隊列中選出一個就緒進程。
每個進程都有一個調(diào)度策略，在它的task_struct中規(guī)定（policy屬性），或為SCHED_RR,SCHED_FIFO，或為SCHED_OTHER。前兩種為實時進程調(diào)度策略，后一種為普通進程調(diào)度策略。
用戶進程由do_fork（）函數(shù)創(chuàng)建，它也是fork系統(tǒng)調(diào)用的執(zhí)行者。do_fork（）創(chuàng)建一個新的進程，繼承父進程的現(xiàn)有資源，初始化進程時鐘、信號、時間等數(shù)據(jù)。完成子進程的初始化后，父進程將它掛到就緒隊列，返回子進程的pid。
進程創(chuàng)建時的狀態(tài)為TASK_UNINTERRUPTIBLE，在do_fork（）結(jié)束前被父進程喚醒后，變?yōu)門ASK_RUNNING。處于TASK_RUNNING狀態(tài)的進程被移到就緒隊列中，當適當?shù)臅r候由schedule（）按CPU調(diào)度算法選中，獲得CPU。
如果進程采用輪轉(zhuǎn)法，當時間片到時（10ms的整數(shù)倍），由時鐘中斷觸發(fā)timer_interrupt（）函數(shù)引起新一輪的調(diào)度，把當前進程掛到就緒隊列的尾部。獲得CPU而正在運行的進程若申請不到某個資源，則調(diào)用sleep_on（）或interruptible_sleep_on（）睡眠，并進入就緒隊列尾。狀態(tài)尾TASK_INTERRUPTIBLE的睡眠進程當它申請的資源有效時被喚醒，也可以由信號或者定時中斷喚醒，喚醒以后進程狀態(tài)變?yōu)門ASK_RUNNING，并進入就緒隊列。
首先介紹一下2.6版以前的的調(diào)度算法的主要思想，下面的schedule（）函數(shù)是內(nèi)核 2.4.23 中摘錄的：
3、進程上下文切換
首先進程切換需要做什么？它做的事只是保留正在運行進程的"環(huán)境"，并把將要運行的進程的"環(huán)境"加載上來，這個環(huán)境也叫上下文。它包括各個進程"公用"的東西，比如寄存器。
下一個問題，舊的進程環(huán)境保存在那，新的進程環(huán)境從那來，在i386上，有個tss段，是專用來保存進程運行環(huán)境的。在Linux來說，在結(jié)構task_struct中有個類型為struct thread_struct的成員叫tss，如下：
然后下面就是load進程next的ldt，頁表，fs，gs，debug寄存器。
因為Linux一般并不使用ldt，所以它們一般會指向一個共同的空的ldt段描述符，這樣就可能不需要切換ldt了，如果進程next和prev是共享內(nèi)存的話，那么頁表的轉(zhuǎn)換也就不必要了（這一般發(fā)生在clone時）。
二、2.6版內(nèi)核對進程調(diào)度的優(yōu)化
1.新調(diào)度算法簡介
2.6版本的Linux內(nèi)核使用了新的調(diào)度器算法，稱為O（1）算法，它在高負載的情況下執(zhí)行得非常出色，并在有多個處理器時能夠很好地擴展。
2.4版本的調(diào)度器中，時間片重算算法要求在所有的進程都用盡它們的時間片后，新時間片才會被重新計算。在一個多處理器系統(tǒng)中，當進程用完它們的時間片后不得不等待重算，以得到新的時間片，從而導致大部分處理器處于空閑狀態(tài)，影響SMP的效率。此外，當空閑處理器開始執(zhí)行那些時間片尚未用盡的、處于等待狀態(tài)的進程時，會導致進程開始在處理器之間“跳躍”。當一個高優(yōu)先級進程或交互式進程發(fā)生跳躍時，整個系統(tǒng)的性能就會受到影響。
新調(diào)度器解決上述問題的方法是，基于每個CPU來分布時間片，并取消全局同步和重算循環(huán)。調(diào)度器使用了兩個優(yōu)先級數(shù)組，即活動數(shù)組和過期數(shù)組，可以通過指針來訪問它們?；顒訑?shù)組中包含所有映射到某個CPU且時間片尚未用盡的任務。過期數(shù)組中包含時間片已經(jīng)用盡的所有任務的有序列表。如果所有活動任務的時間片都已用盡，那么指向這兩個數(shù)組的指針互換，包含準備運行任務的過期數(shù)組成為活動數(shù)組，而空的活動數(shù)組成為包含過期任務的新數(shù)組。數(shù)組的索引存儲在一個64位的位圖中，所以很容易找到最高優(yōu)先級的任務。
新調(diào)度器的主要優(yōu)點包括：
SMP效率如果有工作需要完成，所有處理器都會工作。 等待進程沒有進程需要長時間地等待處理器，也沒有進程會無端地占用大量的CPU時間。SMP進程映射進程只映射到一個CPU，而且不會在CPU之間跳躍。SMP進程映射進程只映射到一個CPU，而且不會在CPU之間跳躍。 負載平衡調(diào)度器會降低那些超出處理器負載能力的進程的優(yōu)先級。 交互性能即使在高負載的情況下，系統(tǒng)花費很長時間來響應鼠標點擊或鍵盤輸入的情況也不會再發(fā)生。
2.6版內(nèi)核中，進程調(diào)度經(jīng)過重新編寫，調(diào)度程序不需每次都掃描所有的任務，而是在一個任務變成就緒狀態(tài)時將其放到一個名為“當前”的隊列中。當進程調(diào)度程序運行時，只選擇隊列中最有利的任務來執(zhí)行。這樣，調(diào)度可以在一個恒定的時間里完成。當任務執(zhí)行時，它會得到一個時間段，或者在其轉(zhuǎn)到另一線程之前得到一段時間的處理器使用權。當時間段用完后，任務會被轉(zhuǎn)移到另一個名為“過期”的隊列中。在該隊列中，任務會根據(jù)其優(yōu)先級進行排序。
從某種意義上說，所有位于“當前”隊列的任務都將被執(zhí)行，并被轉(zhuǎn)移到“過期”隊列中。當這種事情發(fā)生時，隊列就會進行切換，原來的“過期”隊列成為“當前”隊列，而空的“當前”隊列則變成“過期”隊列。由于在新的“當前”隊列中，任務已經(jīng)被排列好，調(diào)度程序現(xiàn)在使用簡單的隊列算法，即總是取當前隊列的第一個任務進行執(zhí)行。這個新過程要比老過程快得多。
2、2.6版新調(diào)度算法分析
2.2.6版新調(diào)度算法分析
3、2.6版新調(diào)度算法流程圖
三、內(nèi)核中斷及定時器實現(xiàn)分析
定時器是Linux提供的一種定時服務的機制。它在某個特定的時間喚醒某個進程，來做一些工作。Linux初始化時，init_IRQ（）函數(shù)設定8253的定時周期為10ms（一個tick值）。同樣，在初始化時，time_init（）用setup_irq（）設置時間中斷向量irq0，中斷服務程序為timer_interrupt。
在2.4版內(nèi)核及較早的版本當中，定時器的中斷處理采用底半機制，底半處理函數(shù)的注冊在start_kernel（）函數(shù)中調(diào)用sechd_init（），在這個函數(shù)中又調(diào)用init_bh(TIMER_BH, timer_bh)注冊了定時器的底半處理函數(shù)。然后系統(tǒng)才調(diào)用time_init（）來注冊定時器的中斷向量和中斷處理函數(shù)。
在中斷處理函數(shù)timer_interrupt（）中，主要是調(diào)用do_timer（）函數(shù)完成工作。do_timer（）函數(shù)的主要功能就是調(diào)用mark_bh（）產(chǎn)生軟中斷，隨后處理器會在合適的時候調(diào)用定時器底半處理函數(shù)timer_bh（）。在timer_bh（）中，實現(xiàn)了更新定時器的功能。 2.4.23 版的do_timer（）函數(shù)代碼如下（經(jīng)過簡略）：
四、系統(tǒng)調(diào)用的實現(xiàn)過程
Linux系統(tǒng)調(diào)用的形式與POSIX兼容，也是一套C語言函數(shù)名的集合，入fock（），read（）等等共221個。系統(tǒng)調(diào)用是通過INT 0x80軟中斷調(diào)用進入內(nèi)核，然后根據(jù)系統(tǒng)調(diào)用號分門別類的進行服務。
系統(tǒng)調(diào)用號：文件include/asm-i386/unistd.h為每一個系統(tǒng)調(diào)用規(guī)定了唯一的編號，這個編號與真正的響應函數(shù)之間的關系是利用系統(tǒng)調(diào)用號為數(shù)組的下標，可以在sys_call_table（系統(tǒng)調(diào)用表數(shù)組）中查找對應的響應函數(shù)的sys_name的入口地址。
系統(tǒng)調(diào)用表：系統(tǒng)調(diào)用表sys_call_table是一組宏定義，將系統(tǒng)調(diào)用的編號和相應的內(nèi)核系統(tǒng)調(diào)用處理函數(shù)的入口地址綁定。
內(nèi)核宏定義syscallN（）用于系統(tǒng)調(diào)用的格式轉(zhuǎn)換和參數(shù)的傳遞。其中N取0～6之間的任意整數(shù)。參數(shù)個數(shù)為N的系統(tǒng)調(diào)用由syscallN負責格式轉(zhuǎn)換和參數(shù)傳遞。對系統(tǒng)調(diào)用的初始化，即是對INT 0x80的初始化。系統(tǒng)啟動時，匯編子程序setup_idt準備了256項的idt表。設置0x80號軟中斷服務程序system_call，這個就是所有系統(tǒng)調(diào)用的總?cè)肟凇?/p>
當進程需要進行系統(tǒng)調(diào)用時，必須以C語言函數(shù)的形式寫一句系統(tǒng)調(diào)用命令。該命令如果已經(jīng)在某個頭文件中由相應的syscallN（）展開，則用戶程序必須包含該頭文件。當進程執(zhí)行到系統(tǒng)調(diào)用命令時，實際上執(zhí)行的是syscallN（）展開的函數(shù)。系統(tǒng)調(diào)用的參數(shù)由個寄存器傳遞，然后執(zhí)行INT 0x80中斷，以內(nèi)核態(tài)進入入口地址system_call。
從system_call入口的匯編程序的主要功能是：
保存寄存器當前值； 檢驗是否為合法的系統(tǒng)調(diào)用 根據(jù)系統(tǒng)調(diào)用表sys_call_table和EAX持有的系統(tǒng)調(diào)用號找出并轉(zhuǎn)入系統(tǒng)調(diào)用響應函數(shù)； 從該響應函數(shù)返回后，讓EAX寄存器保存函數(shù)返回值，跳轉(zhuǎn)至ret_from_sys_call（arch/i386/kernel/entry.S）。
以ret_from_sys_call入口的匯編程序段在Linux進程管理中起著十分重要的作用。所有系統(tǒng)調(diào)用結(jié)束前，以及大部分中斷服務程序返回前，都會跳轉(zhuǎn)至此入口地址。反過來，該段程序也不僅僅為系統(tǒng)調(diào)用服務，它還要處理中斷嵌套、bottom half隊列、CPU調(diào)度、信號等事務。
