Linux進程調度時機概念分析

Linux在眾多進程中是怎么進行調度的，這個牽涉到Linux進程調度時機的概念，由Linux內核中Schedule（）的函數來決定是否要進行進程的切換，如果要切換的話，切換到哪個進程等等。

Linux進程調度時機主要有：

1、進程狀態轉換的時刻：進程終止、進程睡眠；

2、當前進程的時間片用完時（current->counter=0）；

3、設備驅動程序

4、進程從中斷、異常及系統調用返回到用戶態時；

時機1，進程要調用sleep（）或exit（）等函數進行狀態轉換，這些函數會主動調用調度程序進行進程調度；

時機2，由于進程的時間片是由時鐘中斷來更新的，因此，這種情況和時機4是一樣的。

時機3，當設備驅動程序執行長而重復的任務時，直接調用調度程序。在每次反復循環中，驅動程序都檢查need_resched的值，如果必要，則調用調度程序schedule()主動放棄CPU。

時機4，如前所述，不管是從中斷、異常還是系統調用返回，最終都調用ret_from_sys_call（），由這個函數進行調度標志的檢測，如果必要，則調用調用調度程序。那么，為什么從系統調用返回時要調用調度程序呢？這當然是從效率考慮。從系統調用返回意味著要離開內核態而返回到用戶態，而狀態的轉換要花費一定的時間，因此，在返回到用戶態前，系統把在內核態該處理的事全部做完。

對于直接執行調度程序的時機，我們不討論，因為后面我們將會描述調度程序的工作過程。前面我們討論了時鐘中斷，知道了時鐘中斷的重要作用，下面我們就簡單看一下每個時鐘中斷發生時內核要做的工作，首先對這個最頻繁的調度時機有一個大體了解，然后再詳細討論調度程序的具體工作過程。

每個時鐘中斷（timer interrupt）發生時，由三個函數協同工作，共同完成進程的選擇和切換，它們是：schedule（）、do_timer（）及ret_form_sys_call（）。我們先來解釋一下這三個函數：

schedule（）：進程調度函數，由它來完成進程的選擇（調度）；

do_timer（）：暫且稱之為時鐘函數，該函數在時鐘中斷服務程序中被調用，是時鐘中斷服務程序的主要組成部分，該函數被調用的頻率就是時鐘中斷的頻率即每秒鐘100次（簡稱100赫茲或100Hz）；

ret_from_sys_call（）：系統調用返回函數。當一個系統調用或中斷完成時，該函數被調用，用于處理一些收尾工作，例如信號處理、核心任務等等。

這三個函數是如何協調工作的呢？

前面我們看到，時鐘中斷是一個中斷服務程序，它的主要組成部分就是時鐘函數do_timer（），由這個函數完成系統時間的更新、進程時間片的更新等工作，更新后的進程時間片counter作為調度的主要依據。

在時鐘中斷返回時，要調用函數ret_from_sys_call（），前面我們已經討論過這個函數，在這個函數中有如下幾行：

cmpl $0, _need_resched

jne reschedule

……

restore_all:

RESTORE_ALL

reschedule:

call SYMBOL_NAME(schedule)

jmp ret_from_sys_call

這幾行的意思很明顯：檢測 need_resched 標志，如果此標志為非0，那么就轉到reschedule處調用調度程序schedule（）進行進程的選擇。調度程序schedule（）會根據具體的標準在運行隊列中選擇下一個應該運行的進程。當從調度程序返回時，如果發現又有調度標志被設置，則又調用調度程序，直到調度標志為0，這時，從調度程序返回時由RESTORE_ALL恢復被選定進程的環境，返回到被選定進程的用戶空間，使之得到運行。

以上就是時鐘中斷這個最頻繁的調度時機。討論這個的主要目的使讀者對時機4有個大致的了解。

另外，TIF_NEED_RESCHED的設置時機 :

設置這個標志的函數主要有兩個: resched_task(),set_tsk_need_resched().主要是resched_task,而resched_task的調用者 check_preempt_curr更是通過:try_to_wake_up/wake_up_new_task/pull_task /__migrate_task 這些被廣泛使用的函數, 從而分布在內核中大量的檢查點有機會搶占進程.

最后要說明的是，系統調用返回函數ret_from_sys_call（）是從系統調用、異常及中斷返回函數通常要調用的函數，但并不是非得調用，對于那些要經常被響應的和要被盡快處理的中斷請求信號，為了減少系統開銷，處理完成后并不調用 ret_from_sys_call（）（因為很顯然的，從這些中斷處理程序返回到的用戶空間肯定是那個被中斷的進程，無需重新選擇），并且，它們作的工作要盡可能少，因為響應的頻率太高了。

Linux進程調度和其他的UNIX進程調度不同，尤其是在“nice level”優先級的處理上，與優先權調度（priority高的進程最先運行）不同，Linux用的是時間片輪轉調度（Round Robing），但同時又保證了高優先級的進程運行的既快、時間又長（both sooner and longer）。而標準的UNIX調度程序都用到了多級進程隊列。大多數的實現都用到了二級優先隊列：一個標準隊列和一個實時（“real time”）隊列。一般情況下，如果實時隊列中的進程未被阻塞，它們都要在標準隊列中的進程之前被執行，并且，每個隊列中，“nice level”高的進程先被執行。

總體上，Linux 調度序程在交互性方面表現很出色，當然了，這是以犧牲一部分“吞吐量”為代價的。

Linux schedule框架(調度的時刻)

1.1、中心是rq(runqueue)

rq其實是runnable queue，即本cpu上所有可運行進程的隊列集合。每個cpu每種類型的rq(cfs/rt)只有一個，一個rq包含多個runnable的task，但是rq當前正在運行的進程(current running task)只有一個。

既然rq是中心，那么以下幾點就是關鍵路徑：

1、什么時候task入rq？

2、什么時候task出rq？

3、rq怎么樣從多個可運行的進程(runnable tasks)中選取一個進程作為當前的運行進程(current running task)？

我們下面就逐一解答這些疑問，理解了這些關鍵路徑，你就對linux的進程調度框架有了一個清晰的認識。

1.2、入rq(enqueue)

只有task新創建/或者task從blocked狀態被喚醒(wakeup)，task才會被壓入rq。涉及到進程調度相關的步驟如下：

1、把task壓入rq(enqueue)，且把task->state設置為TASK_RUNNING；

2、判斷壓入新task以后rq的負載情況，當前task需不需要被調度出去，如果需要把當前task的thread_info->flags其中TIF_NEED_RESCHED bit置位。

重點在這里：如果當前進程需要重新調度的條件成立，這里只是會設置TIF_NEED_RESCHED標志，并不會馬上調用schedule()來進行調度。真正的調度時機發生在從中斷/異常返回時，會判斷當前進程有沒有被設置TIF_NEED_RESCHED，如果設置則調用schedule()來進行調度。

為什么喚醒涉及到調度不會馬上執行？而是只設置一個TIF_NEED_RESCHED，等到中斷/異常返回的時候才執行？

我理解有幾點：(1)喚醒操作經常在中斷上下文中執行，在這個環境中直接調用schedule()進行調度是不行的；(2)為了維護非搶占內核以來的一些傳統，不要輕易中斷進程的處理邏輯除非他主動放棄；(3)在普通上下文中，喚醒后接著調用schedule()也是可以的，我們看到一些特殊函數就是這么干的(調用smp_send_reschedule()、resched_curr()的函數)。

3、等待中斷/異常的發生、返回，在返回時判讀有TIF_NEED_RESCHED，則調用schedule()進行調度；

1.3、出rq(dequeue)

在當前進程調用系統函數進入blocked狀態是，task會出rq(dequeue)。具體的步驟如下：

1、當前進程把task->state設置為TASK_INTERRUPTIBLE/TASK_UNINTERRUPTIBLE;

2、立即調用schedule()進行調度；

這里block是和wakeup、scheduler_tick最大的不同，block是馬上調用schedule()進行調度，而wakeup、scheduler_tick是設置TIF_NEED_RESCHED標志，等待中斷/異常返回時才執行真正的schedule()操作；

3、調用schedule()后，判斷當前進程task->state已經非TASK_RUNNING，則進行dequeue操作，并且調度其他進程到rq->curr。

1.4、定時調度rq(scheduler_tick)

前面說了在rq的enqueue、dequeue時刻會計算rq負載，來決定把哪個runnable task放到current running task。除了enqueue/dequeue時候，系統還會周期性的計算rq負載來進行調度，確保多進程在1個cpu上都能得到服務。具體的步驟如下：

1、每1 tick，local timer產生一次中斷。中斷中調用scheduler_tick()，計算rq的負載重新調度；

2、如果當前進程需要被調度，則設置TIF_NEED_RESCHED標志；

3、在local timer中斷返回的時候，時判讀有TIF_NEED_RESCHED，則調用schedule()進行調度；

1.5、中斷/異常返回(Interrupt/Exception)

在前面幾節中有一個重要的概念，wakeup、scheduler_tick操作后，如果需要調度只會設置TIF_NEED_RESCHED，在中斷/異常返回時才執行真正的調度schedule()操作；