摘 要:本文結合源代碼著重分析了Linux進程調度的依據、策略和調度程序schedule()。

關鍵詞: 嵌入式Linux；進程調度；實時進程；調度策略。

１　前言

處理機（CPU）是整個計算機系統的核心資源，在多進程的操作系統中，進程數往往多于處理機數，這將導致各進程互相爭奪處理機。進程調度對系統功能的實現及各方面的性能都有著決定性的影響，其實質就是把處理機公平、合理、高效地分配給各個進程。調度是實現多任務并發執行的必要手段，不同的操作系統有著不同的調度目標。在傳統的Unix類分時系統中，保證多個進程公平地使用系統資源，提供較好的響應時間是調度的主要目標；而在強實時操作系統中，總是優先級高的任務優先獲得處理機的使用權。

Linux具有內核穩定、功能強大、可裁減、低成本等特點，非常適合嵌入式應用。但是Linux內核本身并不具備強實時特性，且內核體積較大，因此，想要把Linux用于嵌入式系統，必須對Linux進行實時化、嵌入式化。Linux 結合實時進程和非實時進程（普通進程）自身的特點，綜合了上述幾種調度策略，實現了高效、靈活的進程調度。

２　Linux進程調度分析

2.1　Linux進程狀態的描述

Linux將進程狀態描述為如下五種：

TASK_RUNNING：可運行狀態。處于該狀態的進程可以被調度執行而成為當前進程。

TASK_INTERRUPTIBLE：可中斷的睡眠狀態。處于該狀態的進程在所需資源有效時被喚醒，也可以通過信號或定時中斷喚醒。

TASK_UNINTERRUPTIBLE：不可中斷的睡眠狀態。處于該狀態的進程僅當所需資源有效時被喚醒。

TASK_ZOMBIE：僵尸狀態。表示進程結束且已釋放資源，但其task_struct仍未釋放。

TASK_STOPPED：暫停狀態。處于該狀態的進程通過其他進程的信號才能被喚醒。

2　調度方式

Linux中的每個進程都分配有一個相對獨立的虛擬地址空間。該虛存空間分為兩部分：用戶空間包含了進程本身的代碼和數據；內核空間包含了操作系統的代碼和數據。

Linux采用“有條件的可剝奪”調度方式。對于普通進程，當其時間片結束時，調度程序挑選出下一個處于TASK_RUNNING狀態的進程作為當前進程（自愿調度）。對于實時進程，若其優先級足夠高，則會從當前的運行進程中搶占CPU 成為新的當前進程（強制調度）。發生強制調度時，若進程在用戶空間中運行，就會直接被剝奪CPU；若進程在內核空間中運行，即使迫切需要其放棄CPU，也仍要等到從它系統空間返回的前夕才被剝奪CPU。

3 調度策略

3.1　三種調度策略

(1)SCHED_OTHER。SCHED_OTHER是面向普通進程的時間片輪轉策略。采用該策略時，系統為處于TASK_RUNNING狀態的每個進程分配一個時間片。當時間片用完時，進程調度程序再選擇下一個優先級相對較高的進程，并授予CPU使用權。

（２）SCHED_FIFO。SCHED_FIFO策略適用于對響應時間要求比較高，運行所需時間比較短的實時進程。采用該策略時，各實時進程按其進入可運行隊列的順序依次獲得CPU。除了因等待某個事件主動放棄CPU，或者出現優先級更高的進程而剝奪其CPU之外，該進程將一直占用CPU運行。

(3)SCHED_RR。SCHED_RR策略適用于對響應時間要求比較高，運行所需時間比較長的實時進程。采用該策略時，各實時進程按時間片輪流使用CPU。當一個運行進程的時間片用完后，進程調度程序停止其運行并將其置于可運行隊列的末尾。

3.2 　進程調度依據

Linux只有一個可運行隊列，處于TASK_RUNNING狀態的實時進程和普通進程都加入到這個可運行隊列中。Linux的進程調度采用了動態優先級和權值調控的方法，既可實現上述三種調度策略，又能保證實時進程總是比普通進程優先使用CPU。描述進程的數據結構task_struct中用以下幾個數據作為調度依據：

Struct task_struct {
    ……
    volatile long need_resched;  /*是否需要重新調度*/
　　long counter;  /*進程當前還擁有的時間片*/
long nice;  /*普通進程的動態優先級，來自UNIX系統*/
unsigned long policy; /*進程調度策略*/
unsigned long rt_priority;  /*實時進程的優先級*/
……
}；


counter的值是動態變化的，進程運行時，每一個時鐘滴答后，其值減1。當counter值為0時，表示該進程時間片已用完，該進程回到可運行隊列中，等待再次調度。

為保證實時進程優于普通進程，Linux采取加權處理法。在進程調度過程中，每次選取下一個運行進程時，調度程序首先給可運行隊列中的每個進程賦予一個權值weight。普通進程的權值就是其counter和優先級nice的綜合，而實時進程的權值是它的rt_priority的值加1000，確保實時進程的權值總能大于普通進程。調度程序檢查可運行隊列中所有進程的權值，選取權值最大者作為下一個運行進程，保證了實時進程優先于普通進程獲得CPU。Linux使用內核函數goodness()對進程進行加權處理：

Static inline goodness
(struct task_struct * pint this_cpu, struct mm_struct *this_mm)
{
  Int weight;
  Weight=-1;
/*判斷如果任務的調度策略被置為SCHED_YIELD的話，則置權值為－1，返回。
系統調用SCHED_YIELD表示為“禮讓”進程，其權值為最低*/
　If (p->policy & SCHED_YIELD)
        goto out;

/*先對普通進程進行處理（由于多數是普通進程，這樣做有利于提高系統效率）*/
If (p->policy==SCHED_OTHER){
      weight=p->counter;         /*返回權值為進程的counter值*/
/*如果當前進程的counter為0，則表示當前進程的時間片已用完，直接返回*/
　If (! weight)
        Goto out;
#Ifdef CONFIG_SMP
 If (p->processor==this_cpu)
                 Weight+=PROC_CHANGE_PENALTY;
#Endif
/*對進程權值進行微調，如果進程的內存空間使用當前正在運行的進程的內存空間，
則權值額外加1*/
　     If (p->mm==this_mm||! p->mm)
              Weight+=1;
/*將權值加上20與進程優先級nice的差。普通進程的權值主要由counter值和nice值組成*/
　Weight+=20-p->nice;
  Goto out;
}
 /*對實時進程進行處理，返回權值為rt_priority+1000，確保優先級高于普通進程*/
Weight=1000+p->rt_priority;
 Out:
return weight;　
}

從goodness()函數可以看出，對于普通進程，其權值主要取決于剩余的時間配額和 nice兩個因素。nice的規定取值范圍為19～-20，只有特權用戶才能把nice值設為負數，而表達式（20-p->nice）掉轉方向成為 1～40。所以，綜合的權值在時間片尚未用完時基本上是兩者之和。如果是內核進程，或者其用戶空間與當前進程相同，則權值將額外加1作為獎勵。對于實時進程，其權值為1000＋p->rt_priority，當p->counter達到0時該進程將移到隊列的尾部，但其優先級仍不少于 1000。可見當有實時進程就緒時，普通進程是沒機會運行的。

由此可以看出，通過goodness()函數，Linux從優先考慮實時進程出發，實現了多種調度策略的統一處理，其設計思想可謂非常巧妙。

3.3 進程調度

Linux的進程調度由調度程序schedule()完成，通過對schedule()的分析能更好理解調度的過程。schedule()首先判斷當前運行進程是否具有SCHED_RR 標志，本文取一部分加以分析：

if (prev->policy==SCHED_RR)  /*如果是輪轉調度，先作goto特殊處理*/
     Goto move_rr_last;
　　……
Move_rr_last:
     If (! prev->counter){  /*如果counter減至0*/
          Prev->counter=NICE_TO_TICKS (prev->nice);
          Move_last_runqueue (prev);
}
Goto move_rr_back;

prev->counter代表當前進程的運行時間配額，其值逐漸減小。一旦減至0，就要從可執行隊列runqueue中當前的位置移到末尾，宏操作NICE_TO_TICKS根據系統時鐘的精度將進程的優先級別換算成可以運行的時間配額，即恢復其初始的時間配額。把該進程移到末尾意味著：如果沒有權值更高的進程，但是有一個權值與這相同的進程存在，那么，那個權值相同而排列在前的進程就會被選中，從而顧全了大局。

接下來調度函數查詢當前運行進程的狀態是否改變:

Move_rr_back:
     switch(prev->state){  /*查看進程當前的狀態*/
           Case TASK_INTERRUPTIBLE:
                if (signal pending(prev)){  /*判斷運行期間是否收到信號*/
Prev->state=TASK_RUNNING;
Break;
}
               default:  /*當前運行進程處于非TASK_RUNNING狀態*/
Del_from_runqueue (prev);
               Case TASK_RUNNING:
}
Prev->need_resched=0;


容易理解：如果發現進程處于 TASK_INTERRUPTIBLE狀態且有信號等待處理，則內核將其狀態設為TASK_RUNNING，讓其處理完信號，接下來仍有機會獲得CPU；如果沒有信號等待，則將其從可運行隊列中撤下來；如果處于TASK_RUNNING狀態，則繼續進行。然后，將prev-> need_resched的值恢復成0，因為所需的調度已經在運行。

Repeat schedule ():
　　　next=idle_task(this_cpu);  /*next指向最佳候選進程*/
      c=-1000; 　/*進程的綜合權值，初始時是0號進程，-1000是可能的最低值*/
      If (prev->state==TASK_RUNNING)
           Goto still_running;

Still_running_back:
      List_for_each (tmp, &runqueue_head){
           P=list_entry (tmp, struct task_struct, run_list);
           if (can_schedule(p,this_cpu)){  /*計算p指向的進程的權值*/
Int weight=goodness (p, this_cpu, prev->active_mm);
if (weight>c)  /*比較權值大小*/
C=weight, next=p;
}
}

調度之前，將待調度的進程默認為0號進程，權值置為-1000。0號進程比較特別，既不會睡眠，又不能被殺死。接下來內核遍歷可執行隊列run queue中的每個進程，為每個進程通過goodness()函數計算出它當前所具有的權值，然后與當前的最高值c相比。如果兩個進程具有相同權值的話，那么排在前面的進程勝出。

Still_running:
      C=goodness (prev, this_cpu, prev->active_mm);
      Next=prev;
      Goto still_running_back;

上面的代碼告訴我們，如果當前進程想要繼續運行，那么在挑選進程時以當前進程此刻的權值開始。這意味著，相對于權值相同的其他進程來說，當前進程優先。

若發現當前已選進程的權值為0，則需要重新計算各個進程的時間配額，schedule()將轉入recalculate部分。限于篇幅，在此不再展開。

3 結束語

以上結合代碼簡要介紹了Linux中進程調度的基本思想、依據和策略，容易發現 Linux高效率和較強支持并發進程等特點。近年來，嵌入式Linux的研究正在成為一個熱點，理解Linux進程調度的原理，并在此基礎上改進調度算法可能存在的缺陷，可以進一步增強其對實時性的支持，使之進一步適應在嵌入式系統領域內的應用。