linux核心--程序排程

      排程程是核心的組成部分，它負責選擇下一個要運作的程序。程序排程程式可看作在可運作态程序之間配置設定有限的處理器時間的核心子系統。Linux是一個多任務作業系統，隻有通過排程程式的合理排程，系統資源才能最大限制的發揮作用，多程序才會有并發執行的效果。

       多任務作業系統分為非搶占式多任務和搶占式多任務。linux是一個搶占式的多任務作業系統，由排程程式決定什麼時候停止一個程序的運作以便其它程序能夠得到執行機會，這個強制的挂起動作就叫做搶占。程序在被搶占之前能夠運作的時間是預先設定好的，叫程序的時間片。時間片實際是配置設定給每個可運作的程序的處理器時間段。而在非搶占式多任務模式下，除非程序自己主動停止，否則它會一直執運作。

政策

      政策決定排程程式在何時讓什麼程序運作。程序可以分為I/O消耗型和處理器消耗型。前者指程序的大部分時間用來送出I/O請求或等待I/O請求。是以，這樣的程序經常處理可運作狀态，但通常都是運作短短一會兒，因為它在等待更多的I/O請求時最後總會阻塞。相反，處理消耗型程序把時間大多用在執行代碼上。除非被搶占，否則它們通常一直不停地運作，因為它們沒有太多的I/O需求。對于這類處理消耗型的程序，排程政策是盡量降低它們的運作頻率，對于它們而言，延長其運作時間會更合适些。

      排程政策通常在兩個沖突的目标中間尋找平衡：程序響應迅速（響應時間短）和最大系統使用率（高吞吐量）。排程算法中最基本的一類就是基于優先級的排程。優先級高的先運作，低的後運作，相同優先級的程序按輪轉方式進去調 度（一個接一個，重複進行）。在包括Linux在内的某些作業系統中，優先級高的程序使用的時間片也較長。排程程式總是選擇時間片未用盡且優先級高的程序運作。使用者和系統都可以通過設定程序的優先級來影響系統的排程。

      Linux根據以上思想實作了一種基于動态優先級的排程方法。一開始，該方法先設定基本的優先級，然而它允許排程程式根據需要來加、減優先級。舉個例子，如果一個程序在I/O等待上耗費的時候多于其運作時間，那麼該程序顯屬于I/O消耗型程序。它的優先級會被動态提高。相反，如果一個程序的全部時間片一下就被耗盡，那麼該程序屬于處理器消耗型程序，它的優先級會被動态降低。

      時間片是一個數值，它表時程序在被搶占前所能持續運作的時間。調 度政策必須規定一個預設的時間片，時間片過長會導緻系統對互動的響應表現欠佳；讓人覺得系統無法并發執行應用程式；時間片過短會明顯增大程序切換帶來的消耗，因為肯定會有相當一部分系統時間用在程序切換上，而這些程序能夠用來運作的時間片卻很短。當一個程序的時間片耗盡時，就認為這個程序到期了。

       linux系統是搶占式的，當一個程序進入task_running狀态，核心會檢查它的優先級是否高于目前正在執行的程序。如果是這樣，排程程式會被喚醒，搶占目前正在運作的程序并運作新的可運作程序。此外，當一個程序的時間片變為0時，它會被搶占，排程程式被響醒以選擇一個新的程序。

排程程式的可執行隊列

      排程程式中最基本的資料結構是運作隊列，可執行隊列是給處理器上的可執行程序的連結清單，每個處理器一個。每個可投入執行的程序都惟一歸屬于一個可執行隊列。每個運作隊列都有兩個優先級數組，一個活躍的和一個過期的。優先級數組使可運作處理器的每一種優先級都包含一個相應的隊列，而這些隊列包含對應優先級上的可執行程序連結清單。

       許多作業系統在所有程序的時間片用完時，都采用一種顯式的方法來重新計算每個程序的時間片。當一個程序的時間片耗盡時，它會被移至過期數組，但在此之前，時間片已經給它重新計算好了。

       標明一個程序并切換到它去執行是通過schedule()函數來實作的。當核心想要休眠時，會直接調用函數，另外，如果有哪個程序被搶占，那麼該函數也會被喚起執行。schedule()函數獨立于每一個處理器運作。是以，每個處理器對下一次該運作哪個程序做出自己的判斷。

       排程程式通過程序的休眠時間來判斷一個程序到底是I/O消耗型還是處理消耗型。為了支援這種推斷機制，linux記錄了一個程序用于休眠和用于執行的時間，這個值存在于task_struct的sleep_avg域中。

       休眠（被阻塞）的程序處理一個特殊的不可執行狀态。程序休眠有各種原因，但肯定是為了等待一些事件。事件可能是一段時間、從檔案I/O讀更多資料，或者是某個硬體事件。休眠的一個常見原因就是檔案I/O--如程序對一個檔案執行了read()操作，而這需要從磁盤裡讀取。還有，程序在擷取鍵盤輸入的時候也需要等待。無論哪種情況，核心的操作都相同：程序把它自己标記為休眠狀态，把自己從可執行隊列移出，放入等待隊列，然後調用schedule()選擇和執行一個其它程序。喚醒的過程剛好相反：程序被設定為可執行狀态，然後再從等待隊列中移到可執行隊列。

休眠和喚醒狀态圖

負載平衡程式

搶占和上下文切換

實時