Linux的程序排程時機（Schedule函數何時調用）

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 排程序程在互動性方面表現很出色，當然了，這是以犧牲一部分“吞吐量”為代價的。