調度：
操作系統的調度程序的兩項任務：
1： 調度：
實現調度策略，決定就緒的進程、線程競爭cpu的次序的裁決原則。說白了就是進程和線程何時應該放棄cpu和選擇那個就緒進程、線程來執行。
2： 分派：
原來實現調度機制如何時分復用cpu，處理好上下文交換的細節、完成進程、線程和cpu的綁定和放棄的具工作。
linux 2.4 調度：
1：policy ：
進程的調度策略：
1）SCHED_FIFO : 實時進程使用的的先進先出策略，進程會一直占用cpu除非其自動放棄cpu。
2）SCHED_RR : 實時進程的輪轉策略，當分配個u進程的時間片用完後，進程會插入到原來優先級的隊列中。
3）SHED_OTHER：普通進程基於優先級的的時間片輪轉調度。
2：priority：進程的靜態優先級。
3：nice：進程用來控制優先級的因子。在-20～19間的整數。增加nice的值會使優先級降低。默認值為0。
4：rt_priority：實時進程的優先級。
5：counter：一個計時器，進程目前的剩余時間片。用來動態計算進程的動態優先級。系統將休眠次數多的進程的剩余時間疊會加起來。
6：schedule()的流程：
1）檢查是否有軟中斷請求。有則先執行。
2）如果當前進程的調度策略為RR並且counter==0,將此進程移到運行進程隊列的尾部。重新計算counter的值。
3）若當前進程的狀態為 TASK_INTERRUPTIBLE 且有信號接收，則將進程狀態設置為TASK_RUNNING，若當前進程的狀態不是TASK_RUNNING,則將進程從可執行的隊列中移出，將其進程描述符的need_resched置為0。
4) 選擇出可運行隊列中最大權值，保存在變量c中，與之對應的進程描述符保存在變量next中。
5）檢查c是否為0,c==0,則隊列中的所有進程的時間片都用完了。此時對隊列中所有進程的時間片重新計算。重新執行第5步。
6）如果netx==當前進程，則結束調度進程。否則，進行進程切換。
過程：2.4的調度算法，將所有的就緒進程組織成一條可運行隊列，不管是單核環境還是smp環境，cpu都只從這條可運行隊列中循環遍歷直到挑選到下一個要運行的進程。如果所有的進程的時間片都用完，就重新計算所有進程的時間片。
2.4調度的數據結構：
2.4調度的不足：
1）一個明顯的缺點就是時間復雜度為O(n)，每次都要遍歷隊列，效率低！。雖然說O(n)的復雜度看起來不是很糟糕，而且系統能容納進程數量也不一定會很大，但復雜度為O(n)還是很難忍受的。
2）由於在smp環境下多個cpu還是使用同一條運行隊列，所以進程在多個cpu間切換會使cpu的緩存效率降低，降低系統的性能。
3）多個cpu共享一條運行隊列，使得每個cpu在對隊列操作的時候需要對運行隊列進行加鎖，這時如果其他空閒cpu要訪問運行隊列，則只能等待了。由2、3兩點可以看出2.4的調度算法對smp環境的伸縮性不高！不能很好地支持smp環境。
4）不支持內核搶占，內核不能及時響應實時任務，無法滿足實時系統的要求（即使linux不是一個硬實時，但同樣無法滿足軟實時性的要求）。
5）進程的剩余時間是除了nice值外對動態優先級影響最大的因素，並且系統將休眠次數多的進程的剩余時間疊加起來，從而得出更大的動態優先級。這體現了系統更傾向優先執行I/O型進程。內核就是通過這種方式來提高交互進程的優先級，使其優先執行。但休眠多的進程就代表是交互型的進程嗎？並不是的，這只能說明它是I/O型進程。I/O型進程需要進行I/O交互，如讀寫磁盤時進程會經常處於休眠的狀態。如果把這種進程當成是交互進程，反而會影響其他真正的交互進程。
6）簡單的負載平衡。那個cpu空閒就把就緒的進程調度到這個cpu上去執行。或者某個cpu的進程的優先級比某個進程低，就調度到那個cpu上去執行。這樣簡單的負載平衡缺點不言而喻。進程遷移比較頻繁，而且出現2、3的情況。這樣的負載平衡弊大於利！
linux 2.6 O(1)調度：
1：policy：調度策略跟2.4的一樣。
2：rt_priority：實時進程的優先級。在0～99之間。MAX_RT_PRIO為100。不參與優先級的計算。
3：static_prio：非實時進程的靜態優先級，由nice值轉換而來，-20
2：優先級數組代碼如圖：
1）nr_active：數組內可運行的進程
2）DECLARE_BITMP(...)：優先級位圖的宏。找出優先級最高的且有就緒進程的隊列。
3）list_head queue：使用通用鏈表，優先級隊列。
linux 2.6 O(1)調度的數據結構（active or expired）：
每個cpu維護一個自己的運行隊列，每個運行隊列有分別維護自己的active隊列與expried隊列。當進程的時間片用完後就會被放入expired隊列中。當active隊列中所有進程的時間片都用完，進程執行完畢後，交換active隊列和expried。這樣expried隊列就成為了active隊列。這樣做只需要指針的交換而已。當調度程序要找出下一個要運行的進程時，只需要根據上面提過的位圖宏來找出優先級最高的且有就緒進程的隊列。這樣的數據組織下，2.6的調度程序的時間復雜度由原來2.4的O(n)提高到O(1)。而其對smp環境具有較好的伸縮性。
數據結構的組織如下：
linux 2.6 O(1) 調度的進程優先級：
2.6調度有140個優先級級別，由0～139, 0～99 為實時優先級，而100～139為非實時優先級。上面的圖有說。
特點：
1）動態優先級是在靜態優先級的基礎上結合進程的運行狀態和進程的交互性來計算。所以真正參與調度的是進程的動態優先級。而進程的交互性是通過進程的睡眠時間來判斷的（這點從根本上來說還是和2.4思想的一樣）。所以動態優先級是通過靜態優先級和進程睡眠時間來計算的。這裡要注意的是，動態優先級是非實時進程插入優先級隊列的依據。但實時進程是根據rt_prioirty來插入隊列的，實時進程的實時優先級由進程被創建到進程結束都是不會改變的。但其執行的時間片是根據靜態優先級來計算的。
2）進程優先級越高，它每次執行的時間片就越長。
3）使用TASK_INTERACTIVE()宏來判斷進程是否為交互進程，該宏是基於nice來判斷的，nice值越高，優先級越低，這樣交互性越低。
4）如果一個進程的交互性比較強，那麼其執行完自身的時間片後不會移到expired隊列中，而是插到原來隊列的尾部。這樣交互性進程可以快速地響應用戶，交互性會提高。如果被移到expired隊列，那麼在交換隊列指針前，交互性進程可能就會發生嚴重的饑餓，從而使交互性嚴重下降
5）在創建新的進程時，子進程會與父進程平分進程的剩余時間片。即在 fork()------>do_fork() 後父子進程的時間片之和等於原來父進程的時間片大小。這樣做的原因是為了防止父進程利用創建子進程來竊取時間片。如果子進程在退出時，從來沒有被重新分配時間片，且還有時間片剩余，則其剩余的時間片會返還給父進程。這樣父進程就不會因為創建子進程而受到時間片上的懲罰。
2.6 O(1)調度動態優先級的計算代碼：
1）effective_prio(p)：
2）normal_prio：
3）__normal_prio：
linux 2.6 O(1)調度的調度與搶占時機：
1：直接調度：當前進程因為阻塞而直接調用schedule()主動放棄cpu。
1）當前進程被放入相應的等待隊列。
2）改變當前進程的進程狀態。由TASK_RUNNING 改為TASK_UNINTERRUPTIBLE 或者 TASK_INTERRUPTIBLE。
3）選擇新的進程運行。調用schedule() 來獲得下一個需要運行的進程。
4）當資源可用時，把當前進程從等待隊列中移除。
2：被動調度：當前進程因為時間片用完，或者被更高優先級的進程搶占，而被逼放棄cpu。這時當前進程不會立刻被調度出去，而是通過設置TIF_NEED_RESCHED位為1來告知kernel需要調度了。在適當的時機kernel會重新調度。
1）問題：為什麼不能立刻調度？
進程在內核裡運行時，可能要申請共享資源，如自旋鎖，如果這個時候去搶占當前進程，使其立刻讓出cpu，如果新進程也需要相同的共享資源的話，那麼會導致死鎖！所以這裡進程只設置了標志位通知內核需要調度。
2）問題：什麼時候才是合適的時機？
內核在即將返回用戶空間時會檢查TIF_NEED_RESCHED，如果設置了就調用schedule()，這樣就會發生用戶搶占。
a：從中斷處理程序返回用戶空間時。
b：從系統調用返回用戶空間時。
linux 2.6 O(1)調度的負載平衡：
復雜！
linux 2.6 O(1)調度的過渡：
1：SD調度器：
O(1)調度的復雜性主要來至於動態優先級的計算。調度器根據一些難以理解的經驗公式和平均休眠時間來決定、修改進程的優先級。這是O(1)調度一個比較大的缺點（甚至可以說是致命的。）。SD調度的特點：
1）數據結構跟O(1)調度差不多，不過少了expired隊列。
2）進程在用完其時間片後不會放到expired隊列，而是放到下一個優先級隊列中（這就是為什麼沒有expired隊列的原因）。當下降到最低一級時，時間片用完，就回到初始優先級隊列去，重新降級的過程！每一次降級就像我們下樓梯的過程，所以這被稱為樓梯算法。
3）兩種時間片：粗粒度、細粒度。粗粒度由多個細粒度組成，當一個粗粒度時間片被用完，進程就開始降級，一個細粒度用完就進行輪回。這樣cpu消耗型的進程在每個優先級上停留的時間都是一樣的。而I/O消耗型的進程會在優先級最高的隊列上停留比較長的時間，而且不一定會滑落到很低的優先級隊列上去。
4）不會饑餓，代碼比O(1)調度簡單，最重要的意義在於證明了完全公平的思想的可行性。
5）相對與O(1)調度的算法框架還是沒有多大的變化，每一次調整優先級的過程都是一次進程的切換過程，細粒度的時間片通常比O(1)調度的時間片短很多。這樣不可避免地帶來了較大的額外開銷，使吞吐量下降的問題。這是SD算法不被采用的主要原因！
2：RSDL調度器：
對SD算法的改進，其核心思想是“完全公平”，並且沒有復雜的動態優先級的調整策略。引進“組時間配額” → tg 每個優先級隊列上所有進程可以使用的總時間 ，”優先級時間配額“ → tp, tp不等於進程的時間片，而是小於進程時間片。當進程的tp用完後就降級。與SD算法相類似。當每個隊列的tg用完後不管隊列中是否有tp沒有用完，該隊列的所有進程都會被強制降級。
linux 2.6 O(1)調度的不足：
1：復雜的難以理解的經驗公式。
2：公平嗎？
3：實時性？
linux 傑出的調度算法 → cfs：
按照cfs的作者的說法：”cfs的 80% 的工作可以用一句話來概括：cfs在真實的硬件上模擬了完全理想的多任務處理器。“ 在完全理想的多任務處理器下，每個進程都能夠同時獲得cpu的執行時間，當系統中有兩個進程時，cpu時間被分成兩份，每個進程占50%。
1：虛擬運行時間。進程的 vt 與其實際的運行時間成正比，與其權重成反比。權重是由進程優先級來決定的，而優先級又參照nice值的大小。進程優先級權重越高，在實際運行時間相同時，進程的vt就越小。所有的非實時的可運行的進程用紅黑樹來組織起來，調度時選擇的vt最小的那個進程。因為這裡的紅黑樹左子樹的鍵值比右邊的小，所以每次調度時都選擇樹的最左下角的那個進程（實體）就可以了。
2：完全公平的思想。cfs不再跟蹤進程的休眠時間、也不再區分交互式進程，其將所有的進程統一對待，在既定的時間內每個進程都獲得了公平的cpu占用時間，這就是cfs裡的公平所在！
3：cfs 引入了模塊化、完全公平調度、組調度等一系列特性。雖說是完全公平調度，但進程之間本來就不公平的（有些內核線程用於處理緊急情況），所以這種完全公平是不能夠實現的。cfs使用weight 權重來區分進程間不平等的地位，這也是cfs實現公平的依據。權重由優先級來決定，優先級越高，權重越大。但優先級與權重之間的關系並不是簡單的線性關系。內核使用一些經驗數值來進行轉化。
如果有a、b、c 三個進程，權重分別是1、2、3,那麼所有的進程的權重和為6, 按照cfs的公平原則來分配，那麼a的重要性為1/6, b、c 為2/6, 3/6。這樣如果a、b、c 運行一次的總時間為6個時間單位，a占1個，b占2個，c占3個。
cfs調度器：
各個部分的數據結構關系圖如下：
虛擬運行時間
在完全理想的多任務處理器下，每個進程都能同時獲得cpu的時間。但實際上當一個進程占用cpu時，其他的進程必須等待，這樣就產生了不公平。所以linux 的cfs調度引入了虛擬運行時間。虛擬運行時間主要由兩個因素決定，一個是實際的運行時間，一個是其權重，它隨自己的實際運行時間增加而增加，但又不等於實際運行時間。上面提過內核采用紅黑樹來對虛擬運行時間來排序，這樣紅黑樹最左邊的進程（調度實體）就是受到了最不公平待遇的進程，需要作為下一個被調度的進程。
進程的虛擬運行時間由calc_delta_fair()來計算。在每次時鐘中斷後都會進行更新。公式為：
if (se.load.weight != NICE_0_LOAD)
vruntime += delta * NICE_0_LOAD / se.load.weight;
else
vruntime += delta;
delta是進程增加的實際的運行時間。 NICE_0_LOAD為nice 0進程的權重。虛擬運行時間與權重成反比，進程的權重越大虛擬運行時間就增加得越慢，位置就越左，越有可能被調度。
對cfs的理解最好就是看源代碼了，下面貼出代碼（網上有人整理得很好了）：
各個函數的調用關系圖：
（1）
tick中斷
在tick中斷處理函數中,會調用scheduler_tick()函數.該函數代碼如下:
在tick中斷處理函數中，會調用scheduler_tick()函數。該函數代碼如下:
void scheduler_tick(void)
{
/*取得當前CPU*/
int cpu = smp_processor_id();
/*取得當前CPU對應的runqueue*/
struct rq *rq = cpu_rq(cpu);
/*當前運行的進程*/
struct task_struct *curr = rq->curr;
sched_clock_tick();
spin_lock(&rq->lock);
/*更新rq的當前時間戳.即使rq->clock變為當前時間戳*/
update_rq_clock(rq);scheduler_tick()
/*更新rq的負載*/
update_cpu_load(rq);
/*調用調度模塊的task_tick函數*/
curr->sched_class->task_tick(rq, curr, 0);
spin_unlock(&rq->lock);
#ifdef CONFIG_SMP
rq->idle_at_tick = idle_cpu(cpu);
trigger_load_balance(rq, cpu);
#endif
}
我們從上面的代碼中可以看到,經過一部份共同處理之後,流程會轉入調度模塊的task_tick()函數.
對應CFS,它的sched_class結構如下:
static const struct sched_class fair_sched_class = {
.next = &idle_sched_class,
.enqueue_task = enqueue_task_fair,
.dequeue_task = dequeue_task_fair,
.yield_task = yield_task_fair,
.check_preempt_curr = check_preempt_wakeup,
.pick_next_task = pick_next_task_fair,
.put_prev_task = put_prev_task_fair,
#ifdef CONFIG_SMP
.select_task_rq = select_task_rq_fair,
.load_balance = load_balance_fair,
.move_one_task = move_one_task_fair,
#endif
.set_curr_task = set_curr_task_fair,
.task_tick = task_tick_fair,
.task_new = task_new_fair,
.prio_changed = prio_changed_fair,
.switched_to = switched_to_fair,
#ifdef CONFIG_FAIR_GROUP_SCHED
.moved_group = moved_group_fair,
#endif
};
即對應task_tick的處理函數為task_tick_fair().代碼如下:
（2）
schedule()的執行過程
當進程需要被搶占或者是進程主運讓出處理器,則會調用schedule()函數.為了減小篇幅,在這裡就不分析schedule()函數代碼.只列出在該函數中調用模塊的主要函數.如下示:
Schedule()---->
sched_class->put_prev_task(rq,prev)---->
sched_class->pick_next_task()
對應到CFS中,put_prev_task()函數為put_prev_task_fair(),該操作就是將進程放回隊列.
（3）
新進程的調度過程
在創建新進程的時候,在do_fork()中有如下過程:
long do_fork(unsigned long clone_flags,
unsigned long stack_start,
struct pt_regs *regs,
unsigned long stack_size,
int __user *parent_tidptr,
int __user *child_tidptr)
{
if (unlikely(clone_flags & CLONE_STOPPED)) {
/*
* We'll start up with an immediate SIGSTOP.
*/
sigaddset(&p->pending.signal, SIGSTOP);
set_tsk_thread_flag(p, TIF_SIGPENDING);
__set_task_state(p, TASK_STOPPED);
} else {
wake_up_new_task(p, clone_flags);
}
｝
即在末帶CLONE_STOPPED標志創建進程時,就會對新進程調用wake_up_new_task().
加上附件，可以下載代碼，其中有注釋（摘自網上一篇很好的文章）。
------------------------------------------分割線------------------------------------------
免費下載地址在 http://linux.linuxidc.com/
用戶名與密碼都是www.linuxidc.com
具體下載目錄在 /2015年資料/6月/8日/Linux 調度總結/
下載方法見 http://www.linuxidc.com/Linux/2013-07/87684.htm
------------------------------------------分割線------------------------------------------
