Linux在眾多進(jìn)程中是怎么進(jìn)行調(diào)度的，這個(gè)牽涉到Linux進(jìn)程調(diào)度時(shí)機(jī)的概念，由Linux內(nèi)核中Schedule（）的函數(shù)來決定是否要進(jìn)行進(jìn)程的切換，如果要切換的話，切換到哪個(gè)進(jìn)程等等。

Linux進(jìn)程調(diào)度時(shí)機(jī)主要有：

1、進(jìn)程狀態(tài)轉(zhuǎn)換的時(shí)刻：進(jìn)程終止、進(jìn)程睡眠；

2、當(dāng)前進(jìn)程的時(shí)間片用完時(shí)（current->counter=0）；

3、設(shè)備驅(qū)動(dòng)程序

4、進(jìn)程從中斷、異常及系統(tǒng)調(diào)用返回到用戶態(tài)時(shí)；

時(shí)機(jī)1，進(jìn)程要調(diào)用sleep（）或exit（）等函數(shù)進(jìn)行狀態(tài)轉(zhuǎn)換，這些函數(shù)會(huì)主動(dòng)調(diào)用調(diào)度程序進(jìn)行進(jìn)程調(diào)度；

時(shí)機(jī)2，由于進(jìn)程的時(shí)間片是由時(shí)鐘中斷來更新的，因此，這種情況和時(shí)機(jī)4是一樣的。

時(shí)機(jī)3，當(dāng)設(shè)備驅(qū)動(dòng)程序執(zhí)行長(zhǎng)而重復(fù)的任務(wù)時(shí)，直接調(diào)用調(diào)度程序。在每次反復(fù)循環(huán)中，驅(qū)動(dòng)程序都檢查need_resched的值，如果必要，則調(diào)用調(diào)度程序schedule()主動(dòng)放棄CPU。

時(shí)機(jī)4，如前所述，不管是從中斷、異常還是系統(tǒng)調(diào)用返回，最終都調(diào)用ret_from_sys_call（），由這個(gè)函數(shù)進(jìn)行調(diào)度標(biāo)志的檢測(cè)，如果必要，則調(diào)用調(diào)用調(diào)度程序。那么，為什么從系統(tǒng)調(diào)用返回時(shí)要調(diào)用調(diào)度程序呢？這當(dāng)然是從效率考慮。從系統(tǒng)調(diào)用返回意味著要離開內(nèi)核態(tài)而返回到用戶態(tài)，而狀態(tài)的轉(zhuǎn)換要花費(fèi)一定的時(shí)間，因此，在返回到用戶態(tài)前，系統(tǒng)把在內(nèi)核態(tài)該處理的事全部做完。

對(duì)于直接執(zhí)行調(diào)度程序的時(shí)機(jī)，我們不討論，因?yàn)楹竺嫖覀儗?huì)描述調(diào)度程序的工作過程。前面我們討論了時(shí)鐘中斷，知道了時(shí)鐘中斷的重要作用，下面我們就簡(jiǎn)單看一下每個(gè)時(shí)鐘中斷發(fā)生時(shí)內(nèi)核要做的工作，首先對(duì)這個(gè)最頻繁的調(diào)度時(shí)機(jī)有一個(gè)大體了解，然后再詳細(xì)討論調(diào)度程序的具體工作過程。

每個(gè)時(shí)鐘中斷（timer interrupt）發(fā)生時(shí)，由三個(gè)函數(shù)協(xié)同工作，共同完成進(jìn)程的選擇和切換，它們是：schedule（）、do_timer（）及ret_form_sys_call（）。我們先來解釋一下這三個(gè)函數(shù)：

schedule（）：進(jìn)程調(diào)度函數(shù)，由它來完成進(jìn)程的選擇（調(diào)度）；

do_timer（）：暫且稱之為時(shí)鐘函數(shù)，該函數(shù)在時(shí)鐘中斷服務(wù)程序中被調(diào)用，是時(shí)鐘中斷服務(wù)程序的主要組成部分，該函數(shù)被調(diào)用的頻率就是時(shí)鐘中斷的頻率即每秒鐘100次（簡(jiǎn)稱100赫茲或100Hz）；

ret_from_sys_call（）：系統(tǒng)調(diào)用返回函數(shù)。當(dāng)一個(gè)系統(tǒng)調(diào)用或中斷完成時(shí)，該函數(shù)被調(diào)用，用于處理一些收尾工作，例如信號(hào)處理、核心任務(wù)等等。

這三個(gè)函數(shù)是如何協(xié)調(diào)工作的呢？

前面我們看到，時(shí)鐘中斷是一個(gè)中斷服務(wù)程序，它的主要組成部分就是時(shí)鐘函數(shù)do_timer（），由這個(gè)函數(shù)完成系統(tǒng)時(shí)間的更新、進(jìn)程時(shí)間片的更新等工作，更新后的進(jìn)程時(shí)間片counter作為調(diào)度的主要依據(jù)。

在時(shí)鐘中斷返回時(shí)，要調(diào)用函數(shù)ret_from_sys_call（），前面我們已經(jīng)討論過這個(gè)函數(shù)，在這個(gè)函數(shù)中有如下幾行：

cmpl $0, _need_resched

jne reschedule

……

restore_all:

RESTORE_ALL

reschedule:

call SYMBOL_NAME(schedule)

jmp ret_from_sys_call

這幾行的意思很明顯：檢測(cè) need_resched 標(biāo)志，如果此標(biāo)志為非0，那么就轉(zhuǎn)到reschedule處調(diào)用調(diào)度程序schedule（）進(jìn)行進(jìn)程的選擇。調(diào)度程序schedule（）會(huì)根據(jù)具體的標(biāo)準(zhǔn)在運(yùn)行隊(duì)列中選擇下一個(gè)應(yīng)該運(yùn)行的進(jìn)程。當(dāng)從調(diào)度程序返回時(shí)，如果發(fā)現(xiàn)又有調(diào)度標(biāo)志被設(shè)置，則又調(diào)用調(diào)度程序，直到調(diào)度標(biāo)志為0，這時(shí)，從調(diào)度程序返回時(shí)由RESTORE_ALL恢復(fù)被選定進(jìn)程的環(huán)境，返回到被選定進(jìn)程的用戶空間，使之得到運(yùn)行。

以上就是時(shí)鐘中斷這個(gè)最頻繁的調(diào)度時(shí)機(jī)。討論這個(gè)的主要目的使讀者對(duì)時(shí)機(jī)4有個(gè)大致的了解。

另外，TIF_NEED_RESCHED的設(shè)置時(shí)機(jī) :

設(shè)置這個(gè)標(biāo)志的函數(shù)主要有兩個(gè): resched_task(),set_tsk_need_resched().主要是resched_task,而resched_task的調(diào)用者 check_preempt_curr更是通過:try_to_wake_up/wake_up_new_task/pull_task /__migrate_task 這些被廣泛使用的函數(shù), 從而分布在內(nèi)核中大量的檢查點(diǎn)有機(jī)會(huì)搶占進(jìn)程.

最后要說明的是，系統(tǒng)調(diào)用返回函數(shù)ret_from_sys_call（）是從系統(tǒng)調(diào)用、異常及中斷返回函數(shù)通常要調(diào)用的函數(shù)，但并不是非得調(diào)用，對(duì)于那些要經(jīng)常被響應(yīng)的和要被盡快處理的中斷請(qǐng)求信號(hào)，為了減少系統(tǒng)開銷，處理完成后并不調(diào)用 ret_from_sys_call（）（因?yàn)楹茱@然的，從這些中斷處理程序返回到的用戶空間肯定是那個(gè)被中斷的進(jìn)程，無需重新選擇），并且，它們作的工作要盡可能少，因?yàn)轫憫?yīng)的頻率太高了。

Linux進(jìn)程調(diào)度和其他的UNIX進(jìn)程調(diào)度不同，尤其是在“nice level”優(yōu)先級(jí)的處理上，與優(yōu)先權(quán)調(diào)度（priority高的進(jìn)程最先運(yùn)行）不同，Linux用的是時(shí)間片輪轉(zhuǎn)調(diào)度（Round Robing），但同時(shí)又保證了高優(yōu)先級(jí)的進(jìn)程運(yùn)行的既快、時(shí)間又長(zhǎng)（both sooner and longer）。而標(biāo)準(zhǔn)的UNIX調(diào)度程序都用到了多級(jí)進(jìn)程隊(duì)列。大多數(shù)的實(shí)現(xiàn)都用到了二級(jí)優(yōu)先隊(duì)列：一個(gè)標(biāo)準(zhǔn)隊(duì)列和一個(gè)實(shí)時(shí)（“real time”）隊(duì)列。一般情況下，如果實(shí)時(shí)隊(duì)列中的進(jìn)程未被阻塞，它們都要在標(biāo)準(zhǔn)隊(duì)列中的進(jìn)程之前被執(zhí)行，并且，每個(gè)隊(duì)列中，“nice level”高的進(jìn)程先被執(zhí)行。

總體上，Linux 調(diào)度序程在交互性方面表現(xiàn)很出色，當(dāng)然了，這是以犧牲一部分“吞吐量”為代價(jià)的。

Linux schedule框架(調(diào)度的時(shí)刻)

1.1、中心是rq(runqueue)

rq其實(shí)是runnable queue，即本cpu上所有可運(yùn)行進(jìn)程的隊(duì)列集合。每個(gè)cpu每種類型的rq(cfs/rt)只有一個(gè)，一個(gè)rq包含多個(gè)runnable的task，但是rq當(dāng)前正在運(yùn)行的進(jìn)程(current running task)只有一個(gè)。

既然rq是中心，那么以下幾點(diǎn)就是關(guān)鍵路徑：

1、什么時(shí)候task入rq？

2、什么時(shí)候task出rq？

3、rq怎么樣從多個(gè)可運(yùn)行的進(jìn)程(runnable tasks)中選取一個(gè)進(jìn)程作為當(dāng)前的運(yùn)行進(jìn)程(current running task)？

我們下面就逐一解答這些疑問，理解了這些關(guān)鍵路徑，你就對(duì)linux的進(jìn)程調(diào)度框架有了一個(gè)清晰的認(rèn)識(shí)。

1.2、入rq(enqueue)

只有task新創(chuàng)建/或者task從blocked狀態(tài)被喚醒(wakeup)，task才會(huì)被壓入rq。涉及到進(jìn)程調(diào)度相關(guān)的步驟如下：

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

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

重點(diǎn)在這里：如果當(dāng)前進(jìn)程需要重新調(diào)度的條件成立，這里只是會(huì)設(shè)置TIF_NEED_RESCHED標(biāo)志，并不會(huì)馬上調(diào)用schedule()來進(jìn)行調(diào)度。真正的調(diào)度時(shí)機(jī)發(fā)生在從中斷/異常返回時(shí)，會(huì)判斷當(dāng)前進(jìn)程有沒有被設(shè)置TIF_NEED_RESCHED，如果設(shè)置則調(diào)用schedule()來進(jìn)行調(diào)度。

為什么喚醒涉及到調(diào)度不會(huì)馬上執(zhí)行？而是只設(shè)置一個(gè)TIF_NEED_RESCHED，等到中斷/異常返回的時(shí)候才執(zhí)行？

我理解有幾點(diǎn)：(1)喚醒操作經(jīng)常在中斷上下文中執(zhí)行，在這個(gè)環(huán)境中直接調(diào)用schedule()進(jìn)行調(diào)度是不行的；(2)為了維護(hù)非搶占內(nèi)核以來的一些傳統(tǒng)，不要輕易中斷進(jìn)程的處理邏輯除非他主動(dòng)放棄；(3)在普通上下文中，喚醒后接著調(diào)用schedule()也是可以的，我們看到一些特殊函數(shù)就是這么干的(調(diào)用smp_send_reschedule()、resched_curr()的函數(shù))。

3、等待中斷/異常的發(fā)生、返回，在返回時(shí)判讀有TIF_NEED_RESCHED，則調(diào)用schedule()進(jìn)行調(diào)度；

1.3、出rq(dequeue)

在當(dāng)前進(jìn)程調(diào)用系統(tǒng)函數(shù)進(jìn)入blocked狀態(tài)是，task會(huì)出rq(dequeue)。具體的步驟如下：

1、當(dāng)前進(jìn)程把task->state設(shè)置為TASK_INTERRUPTIBLE/TASK_UNINTERRUPTIBLE;

2、立即調(diào)用schedule()進(jìn)行調(diào)度；

這里block是和wakeup、scheduler_tick最大的不同，block是馬上調(diào)用schedule()進(jìn)行調(diào)度，而wakeup、scheduler_tick是設(shè)置TIF_NEED_RESCHED標(biāo)志，等待中斷/異常返回時(shí)才執(zhí)行真正的schedule()操作；

3、調(diào)用schedule()后，判斷當(dāng)前進(jìn)程task->state已經(jīng)非TASK_RUNNING，則進(jìn)行dequeue操作，并且調(diào)度其他進(jìn)程到rq->curr。

1.4、定時(shí)調(diào)度rq(scheduler_tick)

前面說了在rq的enqueue、dequeue時(shí)刻會(huì)計(jì)算rq負(fù)載，來決定把哪個(gè)runnable task放到current running task。除了enqueue/dequeue時(shí)候，系統(tǒng)還會(huì)周期性的計(jì)算rq負(fù)載來進(jìn)行調(diào)度，確保多進(jìn)程在1個(gè)cpu上都能得到服務(wù)。具體的步驟如下：

1、每1 tick，local timer產(chǎn)生一次中斷。中斷中調(diào)用scheduler_tick()，計(jì)算rq的負(fù)載重新調(diào)度；

2、如果當(dāng)前進(jìn)程需要被調(diào)度，則設(shè)置TIF_NEED_RESCHED標(biāo)志；

3、在local timer中斷返回的時(shí)候，時(shí)判讀有TIF_NEED_RESCHED，則調(diào)用schedule()進(jìn)行調(diào)度；

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

在前面幾節(jié)中有一個(gè)重要的概念，wakeup、scheduler_tick操作后，如果需要調(diào)度只會(huì)設(shè)置TIF_NEED_RESCHED，在中斷/異常返回時(shí)才執(zhí)行真正的調(diào)度schedule()操作；