負載均衡
? ? ? ? 我們先前提到過，schedule()和運行隊列等等都是針對于單個處理器而言的。那么，是否存在某種機制來解決多處理器系統(tǒng)中負載不均的狀況呢？想象某個擁有五個處理器的系統(tǒng)，Acpu上處理5個進程，而Bcpu僅僅處理1個，毋庸置疑地浪費了Bcpu中大量的計算資源，卻又使得Acpu苦不堪言，導致整個系統(tǒng)的性能下降。所以內核提供了負載均衡器(load balancer)解決該難題。在<kernel/sched.c>中能看到相關代碼。
? ? ? ? 負載均衡器的核心函數是load_balance()，該函數可以通過兩種渠道被調用。一種是在schedule()中，當schedule()檢測到當前CPU運行隊列中的進程數為零時，負載均衡函數被調用。還有一種是因為定時器而被調用——比如每過一毫秒且CPU相對空閑的時候，以及類似的時候。在load_balance()運行時，將會給當前運行隊列上鎖，以及確保中斷禁用，防止并發(fā)地訪問運行隊列。
? ? ? ? 兩種方式的調用結果存在差異。schedule()的調用里，工作十分簡單——因為當前隊列是空的。所以我們只需要尋找到某個不為空的核，將其進程拉過來即可。在定時器的調用里，我們需要解決任何運行隊列中的不平衡。
? ? ? ? 接下來是load_balance()的執(zhí)行步驟。
? ? ? ? 1.調用find_busiest_queue()尋找最繁忙的運行隊列。如果最繁忙的隊列中進程的數目至少比當前運行隊列中多25%，則程序繼續(xù)，否則返回。
? ? ? ? 2.尋找其試圖遷移的優(yōu)先隊列，一般來說推薦過氣隊列，因為過氣隊列中的進程已經有一段時間沒有運行了，也更有可能不在當前CPU的CACHE中。如果過氣隊列為空，那么搜尋活動隊列。
? ? ? ? 3.搜尋選定隊列中的最高優(yōu)先級進程的列表。這些進程更重要因此更迫切地需要運行。當然之間有一些小插曲，詳細看下面的代碼:
? ? ? ? 在這里稍微提一下已經多次出現的list_entry()函數，這實際上是一個雙向鏈表相關的函數。在Linux內核中，提供了一個用來創(chuàng)建雙向循環(huán)鏈表的結構 list_head。雖然Linux內核是用C語言寫的，但是list_head的引入，使得內核數據結構也可以擁有面向對象的特性，通過使用操作list_head 的通用接口很容易實現代碼的重用，有點類似于C++的繼承機制。詳情見Linux 內核list_head 學習（一）。
? ? ? ? 4.每個給定優(yōu)先級列表中的任務都被分析，以此來尋找適當的任務進行遷移?！斑m當”指的（1）是不在當前CPU的CACHE中。（2）不被禁止遷移。（3）不是當前運行的任務。這一步驟通過調用can_migrate_task()來實現:
? ? ? ? 5.如果不平衡情況依舊存在，則跳轉繼續(xù)處理。否則退出函數。
進程搶占和上下文切換
? ? ? ? 上下文切換是指從當前運行進程切換到其他可執(zhí)行進程。通過定義在<kernel/sched.c>的context_switch()來實現。當某個新的進程被選擇而即將被運行時，該函數被schedule()調用。該函數執(zhí)行了以下兩個基本工作:
? ? ? ? 1.調用<asm/mmu_context.h>中定義的switch_mm()函數，切換虛擬內存映射。
? ? ? ? 2.調用<asm/system.h>定義的switch_to()函數。保存當前進程的上下文，并進行上下文切換。
? ? ? ? 進程上下文，就是進程執(zhí)行時的環(huán)境。具體來說就是各個變量和數據，包括所有的寄存器變量、進程打開的文件、內存信息等。
? ? ? ? （1）用戶級上下文: 正文、數據、用戶堆棧以及共享存儲區(qū)；
? ? ? ? （2）寄存器上下文: 通用寄存器、程序寄存器(IP)、處理器狀態(tài)寄存器(EFLAGS)、棧指針(ESP)；
? ? ? ? （3）系統(tǒng)級上下文: 進程控制塊task_struct、內存管理信息(mm_struct、vm_area_struct、pgd、pte)、內核棧。
? ? ? 當發(fā)生進程調度時，進行進程切換就是上下文切換(context switch).操作系統(tǒng)必須對上面提到的全部信息進行切換，新調度的進程才能運行。而系統(tǒng)調用進行的模式切換(mode switch)。模式切換與進程切換比較起來，容易很多，而且節(jié)省時間，因為模式切換最主要的任務只是切換進程寄存器上下文的切換。詳情查看用戶空間與內核空間，進程上下文與中斷上下文[總結]一文。
? ? ? ? 回歸主題，那么對于內核來說。內核必須知道什么時候該執(zhí)行schedule()。如果只在代碼顯示地調用時調用，那么用戶空間的程序就會無休無止地運行下去。所以，內核提供了nead_resched(該標志似乎存儲在thread_info結構的flags里,其對應與flags取值為TIF_NEED_RESCHED)標志來表示是否需要執(zhí)行調度。如果要設定這個標志，就要調用scheduler_tick()，而調用只會發(fā)生在（1）當一個進程耗盡其時間片。（2）在try_to_wake_up()函數里——當一個比當前進程優(yōu)先級更高的任務被喚醒時。
? ? ? ? 以下介紹三個用于nead_resched的函數:
? ? ? ? 1.set_tsk_need_resched()
? ? ? ? 2.clear_tsk_need_resched()
? ? ? ? 3.need_resched()
? ? ? ? 除上述，當從用戶空間返回，或者是從中斷函數中返回的時候，nead_resched就會被檢查。該標志存儲在每個進程的thread_info結構中的flags成員里。如果flags的值為TIF_NEED_RESCHED時，就等價于nead_resched被置位。
?
用戶搶占
? ? ? ? 用戶級的進程搶占發(fā)生在內核將要返回用戶空間時，并且nead_resched被設置時。? ?
? ? ? ? 總而言之，用戶級進程搶占可能發(fā)生在：
? ? ? ? ? ? 1.從系統(tǒng)調用返回用戶空間時。
? ? ? ? ? ? 2.從中斷處理函數返回用戶空間時。
內核搶占
? ? ? ? Linux和其他大多數的Unix系統(tǒng)以及其他派別的系統(tǒng)不同，Linux是一個完全可搶占的(先發(fā)制人的)操作系統(tǒng)。在不是完全可搶占的系統(tǒng)中，內核代碼會持續(xù)執(zhí)行直到全部完成。也就是說，調度進程沒有能力去打斷一個正在內核中運行的任務。內核進程是合作地進行(平均分配時間？)，而不是引入搶占機制的。內核代碼會運行直到它完成并返回到用戶空間，或者是顯式地阻塞。但是，我們的Linux系統(tǒng)是完全可搶占的：一個進程可能在任何時間點被搶占，只要任務處在安全的可切換的狀態(tài)。
? ? ? ? 什么時候適合重新安排呢？當內核任務不占用“鎖”時，內核就具備搶占其的能力。也就是說，如果一個內核進程不擁有鎖，那么該進程就是可重入的，并且是可被搶占的。
? ? ? ? 與用戶級搶占不同，內核級別的搶占引入了新的標志，就是thread_info結構中的preempt_count成員。其初始值為0，當進程每每獲得鎖時就增加1，每每釋放鎖時就減1。所以當該值為0時，內核是可搶占的。下面討論從中斷里返回的情況:如果返回的是內核空間，內核會檢查當前的進程的preempt_count和nead_resched的值。如果都滿足需求——這意味著某任務繼續(xù)調度，并且當前進程處在安全(可以重新調度)的狀態(tài)，就會調用schedule()。如果不滿足上述條件。中斷程序結束后，將會常規(guī)地返回被中斷處繼續(xù)執(zhí)行。當前內核進程釋放完所有鎖時，也會檢查nead_resched是否被設置。
? ? ? ? 總而言之，內核級搶占可能發(fā)生在：
? ? ? ? 1.當中斷進程返回到內核空間時。
? ? ? ? 2.當內核程序再次變得可搶占時。
? ? ? ? 3.內核態(tài)運行的任務顯示調用schedule()時。
? ? ? ? 4.內核態(tài)進程阻塞時。（是任務代碼的自我實現嗎？還是某種機制檢測到該任務阻塞后啟動調度進程？）
實時
? ? ? ? Linux提供了兩種實時調度算法SCHED_FIFO和SCHED_RR。前者就是簡單地先到先執(zhí)行原則，在該調度算法中不存在時間片的說法，當這樣的任務變?yōu)榭蛇\行狀態(tài)，會一直運行直到它阻塞或者是顯式地放棄cpu。并且用SCHED_FIFO的進程總比SCHED_NORMAL的優(yōu)先調度。采用SCHED_FIFO算法的進程只能被同為SCHED_FIFO的或者是SCHED_RR的進程搶占。兩個以上的具有相同優(yōu)先級的FIFO類進程才用輪流執(zhí)行的方式。如果一個SCHED_FIFO的進程執(zhí)行，那么所有優(yōu)先級低于它的進程無法翻身，直到該進程結束。
? ? ? SCHED_RR與SCHED_FIFO的區(qū)別在于，使用該算法的進程擁有時間片。進程們只能在耗盡自己預定義的時間片前運行。同一優(yōu)先級的進程輪流執(zhí)行。因此在SCHED_RR中時間片僅對相同優(yōu)先級的進程有意義。一個較低優(yōu)先級的進程永遠不可能搶占一個SCHED_RR的進程，盡管這個進程耗盡了自己的時間片（但未結束）。
? ? ? ? SCHED_NORMAL就是我們先前討論的一般進程調度方法。
? ? ? ? 我們用實時優(yōu)先級表示實時進程的優(yōu)先級。正如先前提到，其值為[0，99（MAX_RT_PRIO－1）]。而我們知道常規(guī)的進程優(yōu)先級是[-20，19]。后來為了體系里表示的簡單，我們將Nice的值映射到了[MAX_RT_PRIO，MAX_RT_PRIO＋40]。
