Linux實時性分析-schedule-排程器

1． 排程類型  

每個Linux程序總是按照下面的排程類型被排程：

l SCHED_FIFO 

這是先進先出的實時程序。當排程程式把CPU配置設定給程序的時候，它把該程序描述符保留在運作隊列連結清單的目前位置。如果沒有其它可運作的更高優先級實時程序，程序就繼續使用CPU，想用多久就用多久，即使還有其他具有相同優先級的實時程序處于可運作狀态。

l SCHED_RR  

時間片輪轉的實時程序。當排程程式把CPU配置設定給程序的時候，它把該程序的描述符放在運作隊列連結清單的末尾。這種政策保證對所有<b>具有相同優先級</b>的SCHED_RR實時程序公平地配置設定CPU時間。

l SCHED_NORMAL 

普通的分時程序。當程序使用完成CPU時間片後，就會被退出活動隊列，而加入到過期隊列。隻有當過期隊列變成活動隊列時，普通的時分程序才有機會獲得CPU使用權。

2． 程序的優先級

在Linux，程序是分優先級的。程序排程器在排程程序時，會先選擇最高優先級的程序運作。也是說，高優先級的程序會獲得更多的運作機會。Linux-2.6程序的優先級分為0 ~ 139級，0級為最高優先級，139級為最低先級。在實時程序的優先級是在0 ~ 99之間。

程序的優先級可以用sched_setscheduler系統調用設定程序的靜态優先級。

在程序排程時，選擇程序是根據程序的動态優先級。SCHED_NORMAL程序的動态優先級是根據其靜态優先級和程序的運作情況決定。也是說，SCHED_NORMAL程序的動态優先級會在運作時動态改變。使用sched_setscheduler設定SCHED_NORMAL程序的優先級後，在初始時，程序的動态優先級等于其靜态優先級。

使用sched_setscheduler設定SCHED_RR或SCHED_FIFO的優先級後，其動态優級等于其靜态優先級。在程序運作的過程中，其動态優先級不會發生改變。

我們都知道Linux程序的運作都基于時間片的。每個程序分一個時間片。當程序占用CPU并用完時間片後，排程程式會重設其時間片，然後排程下一個程序使用CPU。而程序的時間片設定與其靜态優先級密切相關，一般能成正比關系。

3．運作狀态程序的組織方法 

   在Linux-2.6摒棄了之前使用一個連結清單組織所有處于運作狀态程序的方法。在Linux-2.6把運作隊列分0 ~ 139的優先級，每個優先級維護一個連結清單。那麼處于運作狀态的程序就放在其動态優先級對應的連結清單中。另外，時間片已經用完的程序就放在過期隊列中，過期隊列與活動隊列是一樣的資料結構，圖下所示：

排程程式選擇程序使用CPU時，隻在活動隊列中找。隻有活動隊列中沒有了任何程序，才把過期隊列變成活動隊列，原活動隊列變成過期隊列。空集用于接收過期程序。

在SMP系統中，每個CPU都獨立維持一個運作隊列。

還有每個CPU都有自己的swapper程序，其PID等于0。但它不在進行隊列中。若排程程式不能在運作隊列中找到可排程的程序，才運作swapper程序。

<a>1．遞減時間片</a>

當SCHED_RR或SCHED_NORMAL程序獲得CPU使用權時，需要不斷遞減其時間片。下面就介紹在标準Linux下是如何遞減程序的時間片。

在Linux的0号中斷是一個定時器中斷。在固定的時間間隔都發生一次中斷，也是說每秒發生該中斷的頻率都是固定的。該頻率是常量HZ，該值一般是在100 ~ 1000之間。該中斷的作用是為了定時更新系統日期和時間，使系統時間不斷地得到跳轉。另外該中斷的中斷處理函數除了更新系統時間外，還需要更新本地CPU統計數。指的是調用scheduler_tick遞減程序的時間片，若程序的時間片遞減到0，程序則被排程出去而放棄CPU使用權。具體情形如下圖所示：

在Linux的每個中斷号都有自己的irq_desc_t描述符。所有的這些描述符組織在一起形成irq_desc數組，如下圖所示：

   現在我們再看看，當n号中斷發生時，我們的中斷處理函數是如何被啟動的。在很多單片機系統中，每個中斷向量都指向不同的中斷服務函數。但是在Linux，大多的外部中斷向量指向同一中斷服務函數do_IRQ。

  當我們使用request_irq在n中斷号安裝中斷處理函數時，實際上是生成一個irqaction對象，該對象的中斷服務例程指針指向我們的中斷處理函數。然後把irqaction對象插到irq_desc數組第n個元素的action指向（irq_desc[n].action）的irqaction連結清單中的未尾。

中斷産生後，核心代碼将由中斷向量導航到do_IRQ函數。在do_IRQ 調用函數__do_IRQ，并傳入中斷号n作為參數。在__do_IRQ函數把irq_desc數組的第n個元素action指向的中斷處理函數全部啟動，包括我們之前注冊的中斷處理函數，如 REF _Ref206988749 \h 圖下所示。由此可知，在Linux實作了可以在同一個中斷号中安裝多個中斷處理函數。也是說實作了中斷複用。

<a href="attachment/201112/2/20671839_1322791070GIn1.jpg" target="_blank"></a>

   在do_IRQ函數中調用__do_IRQ完成後，還要調用irq_exit作後步處理才傳回。而irq_exit對我們的程序排程十分重要。

現在我們再分析一下Linux中斷延遲。

所謂中斷延遲是指從外部中斷信号輸入到目的中斷處理函數開始執行第一條指令所經曆的時間。從本小節上文中，我們知道：在Linux中斷向量并不是直接指中斷處理函數。這會對中斷延遲會造成一定的影響。我們現在假設在理想情況下（中斷沒有被禁用，中斷處理時沒有被嵌套，中斷号沒有被複用）分析Linux的中斷延遲。

從中斷信号輸入到中斷處理函數的第一條指令執行，所經曆的時間可以分為三段：從中斷信号輸入到do_IRQ函數的開始執行；從do_IRQ函數開始執行到找到目标irq_desc_t對象；到中斷處理函數的第一條指令開始執行。我們分别對這三段時間加以分析。

由于中斷向量是直接指向do_IRQ函數的，是以從中斷信号輸入到do_IRQ函數開始執行第一條指令的時間固定。這時，核心代碼以中斷号作為參數，調用__do_IRQ函數。在__do_IRQ函數，以中斷号作為下标直接定位到目标中斷處理函數對應的irq_desc_t對象。這段時間也是固定的。而這時，在該irq_desc_t對象下的action元素直接向我們中斷處理函數所在的irqaction對象。也是在理想情況下Linux的中斷延遲是固定的。

   也是說，标準Linux的中斷延遲不是硬體實時的。

然而在Linux的外部中斷是不分優先級的，在執行中斷處理程式時，也可能會被其它中斷所嵌套而造成延緩，在網絡繁忙而CPU主頻不高的情況下尤其明顯。另外在核心代碼是有些執行點關中斷的，這也會造成中斷延遲的不确定性。

1． 排程器

Linux的程序排程器的主函數是schedule。在shedule函數中有兩個重要變量：prev是目前正在使用CPU的程序；next是下一個将要使用CPU的程序。排程程式的一個很大的任務就是找到next。

schedule的主要工作可以分為兩步。

l 找到next

1、schedule()檢查prev的狀态。如果不是可運作狀态，而且它沒有在核心态被搶占，就應該從運作隊列删除prev程序。不過，如果它是非阻塞挂起信号，而且狀态為TASH_INTERRUPTIBLE，函數就把該程序狀态設定為TASK_RUNNING，并将它插入運作隊列。這個操作與把處理器配置設定給prev是不同的，它隻是給prev一次選中執行的機會。在核心搶占的情況下，該步不會被執行。

2、檢查本地運作隊列中是否有程序。如果沒有則在其它CPU的運作隊列中遷移一部份程序過來。如果在單CPU系統或在其它CPU的運作隊列中遷移程序失敗，next隻能選擇swapper程序，然後馬上跳去switch_tasks執行程序切換。

3、若本地運作隊列中有程序，但沒有活動程序隊列為空集。也就是說運作隊列中的程序都在過期程序隊列中。這時把活動程序隊列改為過期程序隊列，把原過期程序隊列改為活動程序隊列。空集用于接收過期程序。

4、現在可以在活動程序隊列中搜尋一個可運作程序了。首先，schedule()搜尋活動程序隊列的集合位掩碼的第一個非0位。當對應的優先級連結清單不空時，就把位掩碼的相應位置1。是以，第一個非0位下标對應包含最佳運作程序的連結清單。随後，傳回該連結清單的第一個程序。值得一提的是，在Linux-2.6下這步能很短的固定的時間内完成。

這時next找到了。

5、檢查next是否<b>不是</b>實時程序以及是否從TASK_INTERRUPTIBLE或TASK_STOPPED狀态被喚醒。如果這兩個條件都滿足，重新計算其動态優先級。然後把next從原來的優先級撒離插入到新的優先級中。

也是說，實時程序是不會改變其優先級的。

l 切換程序

找到next後，就可以實施程序切換了。

1、把next的程序描述符第一部分字段的内容裝入硬體高速緩存。

2、清除prev的TIF_NEED_RESCHED的标志。

3、設定prev的程序切換時刻。

4、重新計算并設定prev的平均睡眠時間。

5、如果prev != next，切換prev和next硬體上下文。

這時，CPU已經開始執行next程序了。

在Linux-2.6，schedule函數在尋找next時，其算法效率得到極大的提高，時間複雜達到O(1)。而schedule函數性能好壞最關鍵也就這裡。整體來說，schedule的時間複雜度為O(1)。

  1．   

場景分析

現在我們分析這種情況：一個實時程序為了等待外部事件而進入休眠；當外部事件發生時産生中斷而觸發中斷處理函數，并在中斷處理函數中喚醒實時程序；當實時程序被喚醒後，占搶目前程序，獲得CPU使用權，響應外部事件。下面我們看看當核心遇到這種情況時，内部是如何動作的，并由此考察标準Linux的搶占延遲。

假設實時程序是next，目前程序是current。

在next程序的核心态中，為了等待外部事件調用wait_event_interruptible使程序進入休眠，這時next程序就被加入到等待隊列。排程程式則排程其它程序使用CPU，該程序暫時稱為current。

當外部事件發生時，産生了中斷信号，觸發了中斷處理函數。在中斷處理函數中，調用wake_up_interruptible把next喚醒。在調用wake_up_interruptible函數時，傳入參數是等待隊列。wake_up_interruptible函數會試圖喚醒等待隊列中的所有程序。為了友善起見，這裡假設等待隊列中隻有一個正處于等待狀态的程序next。在wake_up_interruptible會調用try_to_wake_up試圖把等待程序next喚醒。

在單CPU系統中，try_to_wakey_up把next插入到本地運作隊列中。若next的優先級比目前程序current程序優先級高，則調用set_tsk_need_resched函數設定current程序核心堆棧中的TIF_NEED_RESCHED标志。該标志會強制把目前程序current排程出去。然後把next的運作狀态改為TASK_RUNNING。也是說，當next被喚醒時，若next的優先級比current的優先級高，就允許搶占目前current程序；否則僅是把next插入運列隊列和把運作狀态改為TASK_RUNNING。

正如前面的所述，中斷發生後，在do_IRQ中斷服務函數調用__do_IRQ函數完成後會調用irq_exit函數作後步處理。irq_exit函數退出後，do_IRQ函數也退出。這是核心執行路徑進入一段彙編代碼。這裡有一個核心搶占檢查點，在x86平台該檢查點的代碼如下程式清單所示。

need_resched:

movl 0x8(%ebp), %ecx

testb $(1

jz restore_all

testl $0x00000200, 0x30(%esp)

call preempt_schedule_irq

jmp need_resched

如果目前程序current的TIF_NEED_RESCHED标志為0，說明沒有需要切換的程序，是以，程式跳轉到restore_all處。如果需要進行程序切換，就調用preempt_schedule_irq函數。在preempt_shedule_irq函數中，關掉本地中斷和核心搶占，然後調用schedule()函數實施排程。如果next在運作進行隊列中優先級最高且在其優先級中唯一，next程序獲得CPU使用權。

   下面有三個宏是值得注意的：

核心搶占的情形大緻就是這樣。其中，從<b>實時程式被喚醒到該實時程式真正開始使用</b><b>CPU</b>的這一段時間就是搶占延遲。上述情形也告訴我們，隻有核心在運作中斷/異常程式時才會發生核心搶占。當然若中斷被禁止或核心搶占被禁止，都不可能發生核心搶占。

preempt_disable()

preempt_enable_no_resched()

preempt_enable()

       preempt_disable是遞減核心搶占标志。若該标志被遞減到0核心搶占啟用。

       preempt_enable_no_resched是遞增核心搶占标志。若該标志被遞增到大于0核心搶占禁用。

preempt_enable不但遞減核心搶占标志。它還在遞減完成後，檢查TIF_NEED_RESCHED标志是否被設定。若被設定，會檢查核心搶占标志是否為0及是否允許中斷。如果這些條件都為真，則調用schedule函數實施程序排程。當啟用可延遲函數的時候，preempt_enable會被執行。

由此可見，核心搶占還會發生在啟用可延遲函數的時候。

2．   

搶占延遲分析

我們考察一下在标準Linux-2.6的搶占延遲的情況。

下面我們對搶占延遲一步一步進行分析。核心搶占過程的時間順序如圖下：

<a href="attachment/201112/2/20671839_1322791159IZwQ.jpg" target="_blank"></a>

外部事件發生後，産生中斷信号。這時由中斷向量指向的do_IRQ 會馬上被執行。在do_IRQ函數會執行__do_IRQ函數，并由此去執行我們的中斷處理函數。在中斷處理函數中，喚醒實時程序。這時，搶占延時開始計時。執行完成中斷處理函數後，__do_IRQ函數退出，轉而執行exit_IRQ函數。在exit_irq函數中，會檢查系統中是否有挂起的軟中斷。如果有挂起的軟中斷，就執行挂起的軟中斷處理函數。軟中斷處理完成後，exit_irq退出，do_IRQ函數也退出。由于挂起軟中斷的數目不确定（雖然隻執行小于10個）以及軟中斷處理函數的運作時間不确定，exit_irq函數的運作時間不可預測。然後核心執行路徑進入一段彙編代碼中，調用schedule函數實施排程。由于schedule的時間複雜為O(1)，而且關中斷和禁用搶占，schedule的執行時間可以确定。若實時程序的優先級為最高，實時程序就會被排程執行。這時，搶占延時計時結束。

也是說，在do_IRQ函數中，由于執行完中斷處理函數後就處理軟中斷，而造成搶占延遲的不确定。還有，在處理軟中斷時，系統是不關中斷的，而且處理軟中斷的時間比較長，被其它硬體中斷嵌套的機會比大。這進一步影響了标準Linux核心搶占的實時性。