嵌入式Linux系統實(shí)時(shí)進(jìn)程調度算法改進(jìn)

1 嵌入式Linux系統分析
1.1 嵌入式系統
嵌入式系統（Embedded Systems）是以應用為中心，以計算機技術(shù)為基礎，軟件硬件可剪裁（可編程、可重構），適用于應用系統對功能、可靠性、成本、體積、功耗有嚴格要求的專(zhuān)用計算機系統。它一般由嵌入式微處理器、外圍硬件設備、嵌入式操作系統以及用戶(hù)的應用程序等四個(gè)部分組成，用于實(shí)現對其它設備的控制、監視或管理等功能。其中，嵌入式處理器是嵌入式系統中的核心部件。
1.2　實(shí)時(shí)操作系統
實(shí)時(shí)操作系統（RTOS，Real-Time Operation System）是指一個(gè)能夠在指定的時(shí)間范圍內完成特定的功能或者對外部的異步時(shí)間做出響應的操作系統[3]。其操作的正確性不僅依賴(lài)于邏輯判斷和邏輯設計的正確程度，而且跟這些操作進(jìn)行的時(shí)間有關(guān)?！霸谥付ǖ臅r(shí)間范圍內”是這個(gè)定義的核心，也就是說(shuō)，實(shí)時(shí)系統是對響應時(shí)間有嚴格要求的。這個(gè)定義要求了：系統應該有在事先定義的時(shí)間范圍內識別和處理離散事件的能力；系統能夠處理和存儲控制系統所需要的大量的數據。
1.3　嵌入式實(shí)時(shí)操作系統
由嵌入式系統的概念和特點(diǎn)可以看出，一個(gè)嵌入式系統對操作系統的可靠性、實(shí)時(shí)性都有很高的要求。尤其在嵌入式技術(shù)廣泛應用的工業(yè)控制、航空軍事等領(lǐng)域，對嵌入式操作系統的實(shí)時(shí)響應能力提出了非常嚴格的要求，哪怕出現很小的時(shí)間偏差，都有可能造成無(wú)法挽回的損失。這便是為何絕大多數嵌入式操作系統都采用實(shí)時(shí)操作系統的主要原因。實(shí)時(shí)操作系統應用到嵌入式領(lǐng)域，便出現了嵌入式實(shí)時(shí)操作系統，它是實(shí)時(shí)操作系統與嵌入式系統相結合的產(chǎn)物，具有實(shí)時(shí)性的同時(shí)又具有嵌入式系統的特點(diǎn)。
2　實(shí)時(shí)進(jìn)程調度算法分析
2.1　Linux進(jìn)程調度相關(guān)概念
進(jìn)程調度分成兩個(gè)部分，一個(gè)是調度的時(shí)機，即什么時(shí)候調度；一個(gè)是調度的算法，即如何調度和調度哪個(gè)進(jìn)程。
Linux進(jìn)程調度時(shí)機[1]：
調度時(shí)機是指在什么情況下運行調度程序來(lái)選擇進(jìn)程運行。在Linux系統中調度程序是通過(guò)函數schedule（）來(lái)實(shí)現的，這個(gè)函數被調用的頻率很高，由它來(lái)決定要運行的進(jìn)程。
Linux調度時(shí)機主要分兩種情況[2]：主動(dòng)調度和被動(dòng)調度。主動(dòng)調度是指當進(jìn)程狀態(tài)發(fā)生變化時(shí)直接調用schedule（）來(lái)實(shí)現調度。被動(dòng)調度是指當一個(gè)進(jìn)程運行時(shí)間片到或就緒隊列中增加了一個(gè)進(jìn)程，此時(shí)系統并不立即進(jìn)行調度，而僅僅是將當前進(jìn)程的調度標志位置1，當系統由核心態(tài)向用戶(hù)態(tài)轉變之前檢查當前進(jìn)程的調度標志是否為1，若為1，則調用schedule（）進(jìn)行調度。
2.2　進(jìn)程調度的原理
進(jìn)程調度分成兩個(gè)部分，一個(gè)是調度的時(shí)機，即什么時(shí)候調度；一個(gè)是調度的算法，即如何調度和調度哪個(gè)進(jìn)程。
調度程序運行時(shí)，要在所有可運行的進(jìn)程中選擇最值得運行的進(jìn)程。選擇進(jìn)程的依據主要有進(jìn)程的調度策略（policy）、靜態(tài)優(yōu)先級（priority）、動(dòng)態(tài)優(yōu)先級（counter）、以及實(shí)時(shí)優(yōu)先級（rt-priority）四個(gè)部分。首先，Linux從整體上區分為實(shí)時(shí)進(jìn)程和普通進(jìn)程，二者調度算法不同，實(shí)時(shí)進(jìn)程優(yōu)先于普通進(jìn)程運行。進(jìn)程依照優(yōu)先級的高低被依次調用，實(shí)時(shí)優(yōu)先級級別最高[3]。
2.3　實(shí)時(shí)調度算法及缺陷
目前，實(shí)時(shí)調度算法主要可以分為三大類(lèi)：時(shí)間驅動(dòng)調度、優(yōu)先級驅動(dòng)調度、比例共享調度。三者各有優(yōu)缺點(diǎn)，時(shí)間驅動(dòng)調度、優(yōu)先級驅動(dòng)調度側重于硬實(shí)時(shí)任務(wù)，比例共享調度更為適合于軟實(shí)時(shí)任務(wù)，在網(wǎng)絡(luò )系統中應用較多。比例共享調度基本思想就是按照一定的權重比例對一組需要調度的任務(wù)進(jìn)行調度，讓它們的執行時(shí)間與它們的權重成正比，是一種加權輪轉調度[4]。
Linux進(jìn)程采用的是多級輪轉調度算法，盡管Linux通過(guò)將進(jìn)程劃分為實(shí)時(shí)進(jìn)程和普通進(jìn)程，按照優(yōu)先級進(jìn)行調度來(lái)實(shí)現實(shí)時(shí)的特性，但是僅能獲得秒級響應時(shí)間，Linux雖然給實(shí)時(shí)進(jìn)程提供了較高的優(yōu)先級，但是沒(méi)有加入時(shí)間限制，在高實(shí)時(shí)響應情況下還不能滿(mǎn)足要求。當進(jìn)程進(jìn)入核心態(tài)時(shí)，其它進(jìn)程不管優(yōu)先級多高也必須等待。
3　實(shí)時(shí)調度算法的改進(jìn)
3.1　實(shí)時(shí)模型
作為實(shí)時(shí)系統調度算法應綜合考慮進(jìn)程的價(jià)值和截止兩個(gè)概念，以保證實(shí)時(shí)進(jìn)程在截止期內盡可能多地完成，在這里提出新的調度算法，改進(jìn)Linux的實(shí)時(shí)性。
即：進(jìn)程的優(yōu)先級數（Vi）=該進(jìn)程重要程度（Wi）+其緊迫度（pi/（d-Ti））*系數k。緊迫度的值越大，說(shuō)明從時(shí)間上看這個(gè)任務(wù)越緊迫。優(yōu)化后調度算法仍以進(jìn)程的價(jià)值為基礎，同時(shí)也關(guān)注了完成進(jìn)程的緊迫度，對于優(yōu)先級相同的進(jìn)程，采用FIFO調度策略。進(jìn)程的價(jià)值越大說(shuō)明該進(jìn)程越重要，CPU越應完成它。
優(yōu)化后調度算法仍以進(jìn)程的價(jià)值為基礎，同時(shí)也關(guān)注了完成進(jìn)程的緊迫度，對于優(yōu)先級相同的進(jìn)程，采用FIFO調度策略。進(jìn)程的價(jià)值越大說(shuō)明該進(jìn)程越重要，CPU越應完成它，可是對一些價(jià)值和它相差不多，而緊迫度要比它大得多的進(jìn)程來(lái)說(shuō)，就不公平了。例如，有兩個(gè)進(jìn)程A，B同時(shí)提交，A的價(jià)值是1001，估計執行時(shí)間是1ms，相對截止期是5ms，B的價(jià)值是1000，估計執行時(shí)間是1ms，相對截止期是2ms，假設這里的系數因子k是10，則更應該執行進(jìn)程B。這是因為進(jìn)程A，B的價(jià)值相近，而B(niǎo)的緊迫度要比A的大一些，A的優(yōu)先級＝1001+1/5*10=1003，B的優(yōu)先級=1000+1/2*10=1005，因此選擇B先運行，以防止B的夭折（注：Linux中實(shí)時(shí)進(jìn)程的值設為從1000到1099，非實(shí)時(shí)進(jìn)程的值設為從1到99，因此選擇系數因子k為10）優(yōu)化后的調度算法依然采用時(shí)間片輪轉策略，依照Linux分配給進(jìn)程的時(shí)間片為20次時(shí)鐘滴噠，也就是200ms =20*10ms[5]。
3.2　結構定義
本文給出實(shí)時(shí)進(jìn)程的結構定義，非實(shí)時(shí)進(jìn)程依然采用原有的動(dòng)態(tài)優(yōu)先級調度策略，其結構定義略去。
#define SCHED RR
typedef struct TaskNode {
int dtime； //進(jìn)程的截止期
int T；//進(jìn)程提交時(shí)間
int ptime；//進(jìn)程尚未完成時(shí)間，初值等于任務(wù)的執行時(shí)間估計
int flag； //其值為1時(shí)說(shuō)明是實(shí)時(shí)進(jìn)程，為0時(shí)說(shuō)明是非實(shí)時(shí)進(jìn)程
int v；//進(jìn)程的優(yōu)先級數
int w；//進(jìn)程的價(jià)值
struct TaskNode *next
}TaskNode *prior，*next；
3.3　鏈表定義
整個(gè)調度算法可以用雙鏈表來(lái)描述，即兩級隊列，分別用兩個(gè)指針指向。最初，這兩部分的頭指針都指向“0”，表明這兩個(gè)隊列均為空。其中實(shí)時(shí)進(jìn)程的就緒等待隊列用一個(gè)循環(huán)單鏈表完成。
開(kāi)始時(shí)的一級隊列，是新到的比當前運行進(jìn)程優(yōu)先級低的實(shí)時(shí)進(jìn)程。如果一個(gè)進(jìn)程由于時(shí)間片到時(shí)或被更高優(yōu)先級任務(wù)搶占，根據它的優(yōu)先級將其插入到第二級隊列。
若當前進(jìn)程的時(shí)間片到時(shí)，CPU便選擇當前隊列中第二個(gè)節點(diǎn)的進(jìn)程來(lái)判斷，如果它的緊迫度大于1的話(huà)，說(shuō)明這個(gè)進(jìn)程在規定時(shí)間內不能完成，它必定夭折，將其放入普通進(jìn)程隊列中，再選擇鏈表的第三個(gè)節點(diǎn)判斷，如果緊迫度小于等于1便運行它，情況如圖１所示。

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

當一級隊列為空時(shí)，二級隊列便升成一級隊列。
普通進(jìn)程的調度通過(guò)單鏈表來(lái)實(shí)現。如果新來(lái)的進(jìn)程屬于普通進(jìn)程，則根據優(yōu)先級高低插入普通隊列。只有實(shí)時(shí)隊列（一級和二級隊列）為空時(shí)，普通隊列才能被調度。
3.4　實(shí)時(shí)進(jìn)程的調度策略算法描述
1）實(shí)時(shí)就緒隊列的初始化
#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指向當前運行的實(shí)時(shí)進(jìn)程。
新來(lái)的進(jìn)程是實(shí)時(shí)進(jìn)程：
if（（*pnew）.flag ==1）
{
當前運行的進(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））
{
當前運行進(jìn)程插入二級隊列：
move last runqueue（Head2，pnow）；
新來(lái)的進(jìn)程搶占CPU：
pnow=pnew；
}
else
將新來(lái)的進(jìn)程插入到等待鏈表的一級隊列：
move last runqueue（Head1，pnow）；
}
Else
當前運行的進(jìn)程是非實(shí)時(shí)進(jìn)程，將當前進(jìn)程插入非實(shí)時(shí)隊列，非實(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í)隊列插入算法略
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）//插入一級隊列
while（（*p）.w=（*p2）.wpl!=Head2）//優(yōu)先級相同的進(jìn)程采用FIFO調度策略
{
pl=p2；
p2=（*p2）.next；
}
（*p）.next=p2；
（*p1）.next=P；
if（P1==Head2）//該節點(diǎn)插入到一級隊列的末尾，則該節點(diǎn)便成了一級隊列的末尾
Head2=P；
else
{
While((*p).w=(*p2).w) //插入二級隊列
{
P1=p2；
p2=（*p2）.next；
（*p）.next=p2；
（*p1）.next=P；
}
}
}
說(shuō)明：根據傳來(lái)的h值，決定在一級隊列h的值是Headl時(shí)還是在二級隊列h的值是Head2時(shí)中查找插入的合適位置。
當P是新來(lái)的任務(wù)時(shí)，h的值是Head1，p被括入一級隊列。p2是p1的后繼節點(diǎn)。在循環(huán)體中，當新來(lái)的進(jìn)程P高于一級隊列的進(jìn)程p2時(shí)，停止循環(huán)，將P插入到p1的后面；當p1等于Head2時(shí)，說(shuō)明一級隊列的節點(diǎn)的優(yōu)先級都比P節點(diǎn)的高，停止循環(huán)，把P插在p1的后面，則該節點(diǎn)便成了一級隊列的末尾。
當P是被搶占的任務(wù)時(shí)，h的值是Head2，p被插入二級隊列。在循環(huán)體中，當P的優(yōu)先級高于二級隊列的進(jìn)程p2時(shí)，停止循環(huán)，將P插入到p1的后面；如果P高于二級隊列的所有進(jìn)程時(shí)，也會(huì )在p2指向Head時(shí)，因（*p）.w=（*p2） .w而停止，則該節點(diǎn)便成了二級隊列的末尾。因為（（head1）.w=-1，而任何進(jìn)程的優(yōu)先級數都不會(huì )小于1因此當p1，p2在這二級隊列中遍歷時(shí)，一定能有機會(huì )停止。
4） 調度等待鏈表中的一級隊列
當前進(jìn)程完成或時(shí)間片到時(shí)，調度等待鏈表中的一級隊列中最前面的實(shí)時(shí)進(jìn)程：
PnowTime；//當前的時(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)程插入到 二級隊列
else
pnow； //被夭折
else
move last（pnow）； //將未完成的非實(shí)時(shí)進(jìn)程插入到非實(shí)時(shí)隊列
}
p=get node（ ）；從就緒鏈表中獲得優(yōu)先級最大的進(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ìn)程
p=get node；
}
else//實(shí)時(shí)就緒鏈表中無(wú)等待的進(jìn)程調用非實(shí)時(shí)就緒隊列
return p；
}
5）實(shí)時(shí)進(jìn)程刪除策略
//curtime是當前的時(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í)間大于相對截止期，該進(jìn)程夭折
{
（Head1）.next=（*p）.next；
if（p= =Head2）//刪除的節點(diǎn)是一級隊列的尾節點(diǎn)時(shí)
{
Head2=Head3；//二級隊列榮升為一級隊列
Head3=Head2；//新二級隊列為空
}
}
else
else //p進(jìn)程可以在規定時(shí)間完成
return p； //無(wú)進(jìn)程等待
return NULL；
針對目前Linux實(shí)時(shí)系統調度算法中僅用進(jìn)程的價(jià)值來(lái)確定優(yōu)先級的現象，本文提出了綜合考慮進(jìn)程的重要性和緊迫度來(lái)決定優(yōu)先級的調度算法。算法將進(jìn)程的截止期和價(jià)值兩個(gè)不相關(guān)的概念，通過(guò)公式結合在一起，用來(lái)計算就緒等待隊列中進(jìn)程的優(yōu)先級數。
該算法通過(guò)雙鏈表來(lái)實(shí)現。在CPU正常負載的情況下，優(yōu)化后的調度算法體現了更優(yōu)的實(shí)時(shí)性能。