１　前言

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

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

２　Linux進程調(diào)度分析

2.1　Linux進程狀態(tài)的描述

Linux將進程狀態(tài)描述為如下五種：

TASK_RUNNING：可運行狀態(tài)。處于該狀態(tài)的進程可以被調(diào)度執(zhí)行而成為當前進程。

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

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

TASK_ZOMBIE：僵尸狀態(tài)。表示進程結(jié)束且已釋放資源，但其task_struct仍未釋放。

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

2　調(diào)度方式

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

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

3 調(diào)度策略

3.1　三種調(diào)度策略

（1）SCHED_OTHER。SCHED_OTHER是面向普通進程的時間片輪轉(zhuǎn)策略。采用該策略時，系統(tǒng)為處于TASK_RUNNING狀態(tài)的每個進程分配一個時間片。當時間片用完時，進程調(diào)度程序再選擇下一個優(yōu)先級相對較高的進程，并授予CPU使用權(quán)。

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

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

3.2 　進程調(diào)度依據(jù)

Linux只有一個可運行隊列，處于TASK_RUNNING狀態(tài)的實時進程和普通進程都加入到這個可運行隊列中。Linux的進程調(diào)度采用了動態(tài)優(yōu)先級 和權(quán)值調(diào)控的方法，既可實現(xiàn)上述三種調(diào)度策略，又能保證實時進程總是比普通進程優(yōu)先使用CPU。描述進程的數(shù)據(jù)結(jié)構(gòu)task_struct中用以下幾個數(shù) 據(jù)作為調(diào)度依據(jù)：

Struct task_struct {

……

volatile long need_resched; /*是否需要重新調(diào)度*/

long counter; /*進程當前還擁有的時間片*/

long nice; /*普通進程的動態(tài)優(yōu)先級，來自UNIX系統(tǒng)*/

unsigned long policy; /*進程調(diào)度策略*/

unsigned long rt_priority; /*實時進程的優(yōu)先級*/

……

}；

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

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

Static inline goodness （struct task_struct * pint this_cpu， struct mm_struct *this_mm）

{

Int weight;

Weight=-1;

/*判斷如果任務的調(diào)度策略被置為SCHED_YIELD的話，則置權(quán)值為－1，返回。系統(tǒng)調(diào)用SCHED_YIELD表示為“禮讓”進程，其權(quán)值為最低*/

If （p-》policy & SCHED_YIELD）

goto out;

/*先對普通進程進行處理（由于多數(shù)是普通進程，這樣做有利于提高系統(tǒng)效率）*/

If （p-》policy==SCHED_OTHER）{

weight=p-》counter; /*返回權(quán)值為進程的counter值*/

/*如果當前進程的counter為0，則表示當前進程的時間片已用完，直接返回*/

If （！ weight）

Goto out;

#Ifdef CONFIG_SMP

If （p-》processor==this_cpu）

Weight+=PROC_CHANGE_PENALTY;

#Endif

/*對進程權(quán)值進行微調(diào)，如果進程的內(nèi)存空間使用當前正在運行的進程的內(nèi)存空間，則權(quán)值額外加1*/

If （p-》mm==this_mm||！ p-》mm）

Weight+=1;

/*將權(quán)值加上20與進程優(yōu)先級nice的差。普通進程的權(quán)值主要由counter值和nice值組成*/

Weight+=20-p-》nice;

Goto out;

}

/*對實時進程進行處理，返回權(quán)值為rt_priority+1000，確保優(yōu)先級高于普通進程*/

Weight=1000+p-》rt_priority;

Out：

return weight;

}

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

由此可以看出，通過goodness（）函數(shù)，Linux從優(yōu)先考慮實時進程出發(fā)，實現(xiàn)了多種調(diào)度策略的統(tǒng)一處理，其設(shè)計思想可謂非常巧妙。

3.3 進程調(diào)度

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

if （prev-》policy==SCHED_RR） /*如果是輪轉(zhuǎn)調(diào)度，先作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，就要從可執(zhí)行隊列runqueue中當前的位置移到末尾，宏操 作NICE_TO_TICKS根據(jù)系統(tǒng)時鐘的精度將進程的優(yōu)先級別換算成可以運行的時間配額，即恢復其初始的時間配額。把該進程移到末尾意味著：如果沒有 權(quán)值更高的進程，但是有一個權(quán)值與這相同的進程存在，那么，那個權(quán)值相同而排列在前的進程就會被選中，從而顧全了大局。

接下來調(diào)度函數(shù)查詢當前運行進程的狀態(tài)是否改變：

Move_rr_back：

switch（prev-》state）{ /*查看進程當前的狀態(tài)*/

Case TASK_INTERRUPTIBLE：

if （signal pending（prev））{ /*判斷運行期間是否收到信號*/

Prev-》state=TASK_RUNNING;

Break;

}

default： /*當前運行進程處于非TASK_RUNNING狀態(tài)*/

Del_from_runqueue （prev）;

Case TASK_RUNNING：

}

Prev-》need_resched=0;

容易理解：如果發(fā)現(xiàn)進程處于TASK_INTERRUPTIBLE狀態(tài)且有信號等待處理，則內(nèi)核將其狀態(tài)設(shè)為TASK_RUNNING，讓其處理完信號， 接下來仍有機會獲得CPU；如果沒有信號等待，則將其從可運行隊列中撤下來；如果處于TASK_RUNNING狀態(tài)，則繼續(xù)進行。然后，將 prev-》need_resched的值恢復成0，因為所需的調(diào)度已經(jīng)在運行。

Repeat schedule （）：

next=idle_task（this_cpu）; /*next指向最佳候選進程*/

c=-1000; 　/*進程的綜合權(quán)值，初始時是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指向的進程的權(quán)值*/

Int weight=goodness （p， this_cpu， prev-》active_mm）;

if （weight》c） /*比較權(quán)值大小*/

C=weight， next=p;

}

}

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

Still_running：

C=goodness （prev， this_cpu， prev-》active_mm）;

Next=prev;

Goto still_running_back;

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

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

3 結(jié)束語

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