摘 要　由于Linux在耗盡的、機(jī)會(huì)均等的調(diào)度策略方面不利于實(shí)時(shí)性的增強(qiáng)，結(jié)合目前常用的改造內(nèi)核的方法，提出新的修改方式，針對(duì)目前Linux在實(shí)時(shí)調(diào)度方法方面的缺陷，建立調(diào)度模型，提出新的調(diào)度算法。

關(guān)鍵詞　Linux；實(shí)時(shí)；進(jìn)程；調(diào)度；算法；改進(jìn)

1 嵌入式Linux系統(tǒng)分析

1.1 嵌入式系統(tǒng)

嵌 入式系統(tǒng)（Embedded Systems）是以應(yīng)用為中心，以計(jì)算機(jī)技術(shù)為基礎(chǔ)，軟件硬件可剪裁（可編程、可重構(gòu)），適用于應(yīng)用系統(tǒng)對(duì)功能、可靠性、成本、體積、功耗有嚴(yán)格要求的 專用計(jì)算機(jī)系統(tǒng)。它一般由嵌入式微處理器、外圍硬件設(shè)備、嵌入式操作系統(tǒng)以及用戶的應(yīng)用程序等四個(gè)部分組成，用于實(shí)現(xiàn)對(duì)其它設(shè)備的控制、監(jiān)視或管理等功 能。其中，嵌入式處理器是嵌入式系統(tǒng)中的核心部件。

1.2　實(shí)時(shí)操作系統(tǒng)

實(shí) 時(shí)操作系統(tǒng)（RTOS，Real-Time Operation System）是指一個(gè)能夠在指定的時(shí)間范圍內(nèi)完成特定的功能或者對(duì)外部的異步時(shí)間做出響應(yīng)的操作系統(tǒng)[3]。其操作的正確性不僅依賴于邏輯判斷和邏輯設(shè) 計(jì)的正確程度，而且跟這些操作進(jìn)行的時(shí)間有關(guān)。“在指定的時(shí)間范圍內(nèi)”是這個(gè)定義的核心，也就是說(shuō)，實(shí)時(shí)系統(tǒng)是對(duì)響應(yīng)時(shí)間有嚴(yán)格要求的。這個(gè)定義要求了： 系統(tǒng)應(yīng)該有在事先定義的時(shí)間范圍內(nèi)識(shí)別和處理離散事件的能力；系統(tǒng)能夠處理和存儲(chǔ)控制系統(tǒng)所需要的大量的數(shù)據(jù)。

1.3　嵌入式實(shí)時(shí)操作系統(tǒng)

由 嵌入式系統(tǒng)的概念和特點(diǎn)可以看出，一個(gè)嵌入式系統(tǒng)對(duì)操作系統(tǒng)的可靠性、實(shí)時(shí)性都有很高的要求。尤其在嵌入式技術(shù)廣泛應(yīng)用的工業(yè)控制、航空軍事等領(lǐng)域，對(duì)嵌 入式操作系統(tǒng)的實(shí)時(shí)響應(yīng)能力提出了非常嚴(yán)格的要求，哪怕出現(xiàn)很小的時(shí)間偏差，都有可能造成無(wú)法挽回的損失。這便是為何絕大多數(shù)嵌入式操作系統(tǒng)都采用實(shí)時(shí)操 作系統(tǒng)的主要原因。實(shí)時(shí)操作系統(tǒng)應(yīng)用到嵌入式領(lǐng)域，便出現(xiàn)了嵌入式實(shí)時(shí)操作系統(tǒng)，它是實(shí)時(shí)操作系統(tǒng)與嵌入式系統(tǒng)相結(jié)合的產(chǎn)物，具有實(shí)時(shí)性的同時(shí)又具有嵌入 式系統(tǒng)的特點(diǎn)。

2　實(shí)時(shí)進(jìn)程調(diào)度算法分析

2.1　Linux進(jìn)程調(diào)度相關(guān)概念

進(jìn)程調(diào)度分成兩個(gè)部分，一個(gè)是調(diào)度的時(shí)機(jī)，即什么時(shí)候調(diào)度；一個(gè)是調(diào)度的算法，即如何調(diào)度和調(diào)度哪個(gè)進(jìn)程。

Linux進(jìn)程調(diào)度時(shí)機(jī)[1]：

調(diào)度時(shí)機(jī)是指在什么情況下運(yùn)行調(diào)度程序來(lái)選擇進(jìn)程運(yùn)行。在Linux系統(tǒng)中調(diào)度程序是通過(guò)函數(shù)schedule（）來(lái)實(shí)現(xiàn)的，這個(gè)函數(shù)被調(diào)用的頻率很高，由它來(lái)決定要運(yùn)行的進(jìn)程。

Linux 調(diào)度時(shí)機(jī)主要分兩種情況[2]：主動(dòng)調(diào)度和被動(dòng)調(diào)度。主動(dòng)調(diào)度是指當(dāng)進(jìn)程狀態(tài)發(fā)生變化時(shí)直接調(diào)用schedule（）來(lái)實(shí)現(xiàn)調(diào)度。被動(dòng)調(diào)度是指當(dāng)一個(gè)進(jìn)程 運(yùn)行時(shí)間片到或就緒隊(duì)列中增加了一個(gè)進(jìn)程，此時(shí)系統(tǒng)并不立即進(jìn)行調(diào)度，而僅僅是將當(dāng)前進(jìn)程的調(diào)度標(biāo)志位置1，當(dāng)系統(tǒng)由核心態(tài)向用戶態(tài)轉(zhuǎn)變之前檢查當(dāng)前進(jìn)程 的調(diào)度標(biāo)志是否為1，若為1，則調(diào)用schedule（）進(jìn)行調(diào)度。

2.2　進(jìn)程調(diào)度的原理

進(jìn)程調(diào)度分成兩個(gè)部分，一個(gè)是調(diào)度的時(shí)機(jī)，即什么時(shí)候調(diào)度；一個(gè)是調(diào)度的算法，即如何調(diào)度和調(diào)度哪個(gè)進(jìn)程。

調(diào) 度程序運(yùn)行時(shí)，要在所有可運(yùn)行的進(jìn)程中選擇最值得運(yùn)行的進(jìn)程。選擇進(jìn)程的依據(jù)主要有進(jìn)程的調(diào)度策略（policy）、靜態(tài)優(yōu)先級(jí)（priority）、動(dòng) 態(tài)優(yōu)先級(jí)（counter）、以及實(shí)時(shí)優(yōu)先級(jí)（rt-priority）四個(gè)部分。首先，Linux從整體上區(qū)分為實(shí)時(shí)進(jìn)程和普通進(jìn)程，二者調(diào)度算法不 同，實(shí)時(shí)進(jìn)程優(yōu)先于普通進(jìn)程運(yùn)行。進(jìn)程依照優(yōu)先級(jí)的高低被依次調(diào)用，實(shí)時(shí)優(yōu)先級(jí)級(jí)別最高[3]。

2.3　實(shí)時(shí)調(diào)度算法及缺陷

目 前，實(shí)時(shí)調(diào)度算法主要可以分為三大類：時(shí)間驅(qū)動(dòng)調(diào)度、優(yōu)先級(jí)驅(qū)動(dòng)調(diào)度、比例共享調(diào)度。三者各有優(yōu)缺點(diǎn)，時(shí)間驅(qū)動(dòng)調(diào)度、優(yōu)先級(jí)驅(qū)動(dòng)調(diào)度側(cè)重于硬實(shí)時(shí)任務(wù)，比 例共享調(diào)度更為適合于軟實(shí)時(shí)任務(wù)，在網(wǎng)絡(luò)系統(tǒng)中應(yīng)用較多。比例共享調(diào)度基本思想就是按照一定的權(quán)重比例對(duì)一組需要調(diào)度的任務(wù)進(jìn)行調(diào)度，讓它們的執(zhí)行時(shí)間與 它們的權(quán)重成正比，是一種加權(quán)輪轉(zhuǎn)調(diào)度[4]。

Linux 進(jìn)程采用的是多級(jí)輪轉(zhuǎn)調(diào)度算法，盡管Linux通過(guò)將進(jìn)程劃分為實(shí)時(shí)進(jìn)程和普通進(jìn)程，按照優(yōu)先級(jí)進(jìn)行調(diào)度來(lái)實(shí)現(xiàn)實(shí)時(shí)的特性，但是僅能獲得秒級(jí)響應(yīng)時(shí) 間，Linux雖然給實(shí)時(shí)進(jìn)程提供了較高的優(yōu)先級(jí)，但是沒(méi)有加入時(shí)間限制，在高實(shí)時(shí)響應(yīng)情況下還不能滿足要求。當(dāng)進(jìn)程進(jìn)入核心態(tài)時(shí)，其它進(jìn)程不管優(yōu)先級(jí)多 高也必須等待。

3　實(shí)時(shí)調(diào)度算法的改進(jìn)

3.1　實(shí)時(shí)模型

作為實(shí)時(shí)系統(tǒng)調(diào)度算法應(yīng)綜合考慮進(jìn)程的價(jià)值和截止兩個(gè)概念，以保證實(shí)時(shí)進(jìn)程在截止期內(nèi)盡可能多地完成，在這里提出新的調(diào)度算法，改進(jìn)Linux的實(shí)時(shí)性。

即： 進(jìn)程的優(yōu)先級(jí)數(shù)（Vi）=該進(jìn)程重要程度（Wi）+其緊迫度（pi/（d-Ti））*系數(shù)k。緊迫度的值越大，說(shuō)明從時(shí)間上看這個(gè)任務(wù)越緊迫。優(yōu)化后調(diào)度 算法仍以進(jìn)程的價(jià)值為基礎(chǔ)，同時(shí)也關(guān)注了完成進(jìn)程的緊迫度，對(duì)于優(yōu)先級(jí)相同的進(jìn)程，采用FIFO調(diào)度策略。進(jìn)程的價(jià)值越大說(shuō)明該進(jìn)程越重要，CPU越應(yīng)完 成它。

優(yōu) 化后調(diào)度算法仍以進(jìn)程的價(jià)值為基礎(chǔ)，同時(shí)也關(guān)注了完成進(jìn)程的緊迫度，對(duì)于優(yōu)先級(jí)相同的進(jìn)程，采用FIFO調(diào)度策略。進(jìn)程的價(jià)值越大說(shuō)明該進(jìn)程越重 要，CPU越應(yīng)完成它，可是對(duì)一些價(jià)值和它相差不多，而緊迫度要比它大得多的進(jìn)程來(lái)說(shuō)，就不公平了。例如，有兩個(gè)進(jìn)程A，B同時(shí)提交，A的價(jià)值是 1001，估計(jì)執(zhí)行時(shí)間是1ms，相對(duì)截止期是5ms，B的價(jià)值是1000，估計(jì)執(zhí)行時(shí)間是1ms，相對(duì)截止期是2ms，假設(shè)這里的系數(shù)因子k是10，則 更應(yīng)該執(zhí)行進(jìn)程B。這是因?yàn)檫M(jìn)程A，B的價(jià)值相近，而B(niǎo)的緊迫度要比A的大一些，A的優(yōu)先級(jí)＝1001+1/5*10=1003，B的優(yōu)先 級(jí)=1000+1/2*10=1005，因此選擇B先運(yùn)行，以防止B的夭折（注：Linux中實(shí)時(shí)進(jìn)程的值設(shè)為從1000到1099，非實(shí)時(shí)進(jìn)程的值設(shè)為 從1到99，因此選擇系數(shù)因子k為10）優(yōu)化后的調(diào)度算法依然采用時(shí)間片輪轉(zhuǎn)策略，依照Linux分配給進(jìn)程的時(shí)間片為20次時(shí)鐘滴噠，也就是200ms =20*10ms[5]。

3.2　結(jié)構(gòu)定義

本文給出實(shí)時(shí)進(jìn)程的結(jié)構(gòu)定義，非實(shí)時(shí)進(jìn)程依然采用原有的動(dòng)態(tài)優(yōu)先級(jí)調(diào)度策略，其結(jié)構(gòu)定義略去。

#define SCHED RR

typedef struct TaskNode {

int dtime； //進(jìn)程的截止期

int T；//進(jìn)程提交時(shí)間

int ptime；//進(jìn)程尚未完成時(shí)間，初值等于任務(wù)的執(zhí)行時(shí)間估計(jì)

int flag； //其值為1時(shí)說(shuō)明是實(shí)時(shí)進(jìn)程，為0時(shí)說(shuō)明是非實(shí)時(shí)進(jìn)程

int v；//進(jìn)程的優(yōu)先級(jí)數(shù)

int w；//進(jìn)程的價(jià)值

struct TaskNode *next

}TaskNode *prior，*next；

3.3　鏈表定義

整個(gè)調(diào)度算法可以用雙鏈表來(lái)描述，即兩級(jí)隊(duì)列，分別用兩個(gè)指針指向。最初，這兩部分的頭指針都指向“0”，表明這兩個(gè)隊(duì)列均為空。其中實(shí)時(shí)進(jìn)程的就緒等待隊(duì)列用一個(gè)循環(huán)單鏈表完成。

開(kāi)始時(shí)的一級(jí)隊(duì)列，是新到的比當(dāng)前運(yùn)行進(jìn)程優(yōu)先級(jí)低的實(shí)時(shí)進(jìn)程。如果一個(gè)進(jìn)程由于時(shí)間片到時(shí)或被更高優(yōu)先級(jí)任務(wù)搶占，根據(jù)它的優(yōu)先級(jí)將其插入到第二級(jí)隊(duì)列。

若當(dāng)前進(jìn)程的時(shí)間片到時(shí)，CPU便選擇當(dāng)前隊(duì)列中第二個(gè)節(jié)點(diǎn)的進(jìn)程來(lái)判斷，如果它的緊迫度大于1的話，說(shuō)明這個(gè)進(jìn)程在規(guī)定時(shí)間內(nèi)不能完成，它必定夭折，將其放入普通進(jìn)程隊(duì)列中，再選擇鏈表的第三個(gè)節(jié)點(diǎn)判斷，如果緊迫度小于等于1便運(yùn)行它，情況如圖１所示。

圖１　優(yōu)化后調(diào)度算法的實(shí)時(shí)進(jìn)程優(yōu)先級(jí)表

當(dāng)一級(jí)隊(duì)列為空時(shí)，二級(jí)隊(duì)列便升成一級(jí)隊(duì)列。

普通進(jìn)程的調(diào)度通過(guò)單鏈表來(lái)實(shí)現(xiàn)。如果新來(lái)的進(jìn)程屬于普通進(jìn)程，則根據(jù)優(yōu)先級(jí)高低插入普通隊(duì)列。只有實(shí)時(shí)隊(duì)列（一級(jí)和二級(jí)隊(duì)列）為空時(shí)，普通隊(duì)列才能被調(diào)度。

3.4　實(shí)時(shí)進(jìn)程的調(diào)度策略算法描述

1）實(shí)時(shí)就緒隊(duì)列的初始化

#define LEN sizeof（TaskNode）

創(chuàng)建空鏈表：

TaskNode*creat new line()

{

TaskNode* head；

head=（TaskNode））malloc（LEN）；

head->w=-1；

Head1=Head2=head：

Head1->next=Head2->next=head；

return head；

}

2） 實(shí)時(shí)進(jìn)程接收策略

#define K 10

void* pnow；

pnew指向新來(lái)的實(shí)時(shí)進(jìn)程，pnow指向當(dāng)前運(yùn)行的實(shí)時(shí)進(jìn)程。

新來(lái)的進(jìn)程是實(shí)時(shí)進(jìn)程：

if（（*pnew）.flag ==1）

{

當(dāng)前運(yùn)行的進(jìn)程是實(shí)時(shí)進(jìn)程：

if （（*pnow）.flag ==1）

{

W =（*pnew）.v+（*pnew）.ptime）/（（*pnew）.dtime-（*pnew）.T））*K；

if（w>（*pnow）.v+（（*pnow）.ptime/（（*pnow）.dtime-（*pnow）.T））*K））

{

當(dāng)前運(yùn)行進(jìn)程插入二級(jí)隊(duì)列：

move last runqueue（Head2，pnow）；

新來(lái)的進(jìn)程搶占CPU：

pnow=pnew；

}

else

將新來(lái)的進(jìn)程插入到等待鏈表的一級(jí)隊(duì)列：

move last runqueue（Head1，pnow）；

}

Else

當(dāng)前運(yùn)行的進(jìn)程是非實(shí)時(shí)進(jìn)程，將當(dāng)前進(jìn)程插入非實(shí)時(shí)隊(duì)列，非實(shí)時(shí)進(jìn)程的插入算法：

move last（pnow）；

move last略

}

else//新來(lái)的進(jìn)程是非實(shí)時(shí)進(jìn)程

move last（pnew）；//將新來(lái)的非實(shí)時(shí)進(jìn)程插入非實(shí)時(shí)隊(duì)列插入算法略

3）實(shí)時(shí)進(jìn)程插入策略

move last runqueue（h，p）；

TaskNode*h，*p；

{

TaskNode*p1，*p2，*t；

P1=h；

P2=pl->next；

if （h==Head1）//插入一級(jí)隊(duì)列

while（（*p）.w<=（*p2）.w&&pl!=Head2）//優(yōu)先級(jí)相同的進(jìn)程采用FIFO調(diào)度策略

{

pl=p2；

p2=（*p2）.next；

}

（*p）.next=p2；

（*p1）.next=P；

if（P1==Head2）//該節(jié)點(diǎn)插入到一級(jí)隊(duì)列的末尾，則該節(jié)點(diǎn)便成了一級(jí)隊(duì)列的末尾

Head2=P；

else

{

While((*p).w<=(*p2).w) //插入二級(jí)隊(duì)列

{

P1=p2；

p2=（*p2）.next；

（*p）.next=p2；

（*p1）.next=P；

}

}

}

說(shuō)明：根據(jù)傳來(lái)的h值，決定在一級(jí)隊(duì)列h的值是Headl時(shí)還是在二級(jí)隊(duì)列h的值是Head2時(shí)中查找插入的合適位置。

當(dāng) P是新來(lái)的任務(wù)時(shí)，h的值是Head1，p被括入一級(jí)隊(duì)列。p2是p1的后繼節(jié)點(diǎn)。在循環(huán)體中，當(dāng)新來(lái)的進(jìn)程P高于一級(jí)隊(duì)列的進(jìn)程p2時(shí)，停止循環(huán)，將P 插入到p1的后面；當(dāng)p1等于Head2時(shí)，說(shuō)明一級(jí)隊(duì)列的節(jié)點(diǎn)的優(yōu)先級(jí)都比P節(jié)點(diǎn)的高，停止循環(huán)，把P插在p1的后面，則該節(jié)點(diǎn)便成了一級(jí)隊(duì)列的末尾。

當(dāng) P是被搶占的任務(wù)時(shí)，h的值是Head2，p被插入二級(jí)隊(duì)列。在循環(huán)體中，當(dāng)P的優(yōu)先級(jí)高于二級(jí)隊(duì)列的進(jìn)程p2時(shí)，停止循環(huán)，將P插入到p1的后面；如果 P高于二級(jí)隊(duì)列的所有進(jìn)程時(shí)，也會(huì)在p2指向Head時(shí)，因（*p）.w<=（*p2） .w而停止，則該節(jié)點(diǎn)便成了二級(jí)隊(duì)列的末尾。因?yàn)椋ǎ╤ead1）.w=-1，而任何進(jìn)程的優(yōu)先級(jí)數(shù)都不會(huì)小于1因此當(dāng)p1，p2在這二級(jí)隊(duì)列中遍歷時(shí)， 一定能有機(jī)會(huì)停止。

4） 調(diào)度等待鏈表中的一級(jí)隊(duì)列

當(dāng)前進(jìn)程完成或時(shí)間片到時(shí)，調(diào)度等待鏈表中的一級(jí)隊(duì)列中最前面的實(shí)時(shí)進(jìn)程：

PnowTime；//當(dāng)前的時(shí)間

run list（pnow）；

TaskNode*pnow；

{

if（*pnow）.ptime!=0）//該進(jìn)程未完成

{

if（*pnow）.flag==1）

if（PnowTime-（*pnow）.T>=（*pnow）.dtime）

move-last-runqueue（head2，now）；//將未完成的進(jìn)程插入到 二級(jí)隊(duì)列

else

pnow； //被夭折

else

move last（pnow）； //將未完成的非實(shí)時(shí)進(jìn)程插入到非實(shí)時(shí)隊(duì)列

}

p=get node（ ）；從就緒鏈表中獲得優(yōu)先級(jí)最大的進(jìn)程

while（1）

{

if （p! =NULL）

{

if （（*p）.time <= （*p）.dtime-PnowTime）） //實(shí)時(shí)進(jìn)程并且沒(méi)超過(guò)截止期

pnow=P；

break；

else//該進(jìn)程己經(jīng)不能完成，所以重新從就緒鏈表中獲得優(yōu)先級(jí)最大的進(jìn)程

p=get node；

}

else//實(shí)時(shí)就緒鏈表中無(wú)等待的進(jìn)程調(diào)用非實(shí)時(shí)就緒隊(duì)列

return p；

}

5）實(shí)時(shí)進(jìn)程刪除策略

//curtime是當(dāng)前的時(shí)間

get node()

{

p=（Headl）.next；

while（1）

if （Head1）.next!= Head1）//有進(jìn)程就緒等待

{

p=（Headl）.next；

if（（*p）.ptime>（（*p）.dtime-Pnowllme）） //進(jìn)程未完成的時(shí)間大于相對(duì)截止期，該進(jìn)程夭折

{

（Head1）.next=（*p）.next；

if（p= =Head2）//刪除的節(jié)點(diǎn)是一級(jí)隊(duì)列的尾節(jié)點(diǎn)時(shí)

{

Head2=Head3；//二級(jí)隊(duì)列榮升為一級(jí)隊(duì)列

Head3=Head2；//新二級(jí)隊(duì)列為空

}

}

else

else //p進(jìn)程可以在規(guī)定時(shí)間完成

return p； //無(wú)進(jìn)程等待

return NULL；

針對(duì)目前Linux實(shí)時(shí)系統(tǒng)調(diào)度算法中僅用進(jìn)程的價(jià)值來(lái)確定優(yōu)先級(jí)的現(xiàn)象，本文提出了綜合考慮進(jìn)程的重要性和緊迫度來(lái)決定優(yōu)先級(jí)的調(diào)度算法。算法將進(jìn)程的截止期和價(jià)值兩個(gè)不相關(guān)的概念，通過(guò)公式結(jié)合在一起，用來(lái)計(jì)算就緒等待隊(duì)列中進(jìn)程的優(yōu)先級(jí)數(shù)。

該算法通過(guò)雙鏈表來(lái)實(shí)現(xiàn)。在CPU正常負(fù)載的情況下，優(yōu)化后的調(diào)度算法體現(xiàn)了更優(yōu)的實(shí)時(shí)性能。