Linux 排程總結

排程：

作業系統的排程程式的兩項任務：

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

------------------------------------------分割線------------------------------------------

本文永久更新連結地址：http://www.linuxidc.com/Linux/2015-06/118518.htm