陳國良，朱艷軍

(武漢理工大學(xué) 機電工程學(xué)院，武漢 430070)

0 引言

隨著計算機的發(fā)展，實時調(diào)度被廣泛應(yīng)用于實時性強的眾多領(lǐng)域，如電子商務(wù)、交通管制、航空航天等，要求操作系統(tǒng)能夠及時高效地處理多任務(wù)的運行。在該領(lǐng)域中，搶占式調(diào)度方式被普遍使用，然而搶占多任務(wù)時往往會增加內(nèi)存的總開銷和浪費CPU的帶寬。

實時調(diào)度算法主要有RM(Rate-Monotonic)調(diào)度[1]、EDF調(diào)度[2]、LLF調(diào)度[3]等，其中EDF調(diào)度算法從Linux-3.14版本開始加入調(diào)度策略。RM與EDF算法在單核方面調(diào)度性能最佳，但在多核調(diào)度中存在Dhall效應(yīng)，即存在正規(guī)化資源利用率總和任意接近于0的任務(wù)集不可調(diào)度。Linux中可以通過區(qū)域劃分的方式避免Dhall效應(yīng)，但需要人為地劃分任務(wù)允許運行的CPU核。LLF算法可以規(guī)避Dhall效應(yīng)，其根據(jù)任務(wù)緊迫程度來決定實時任務(wù)的調(diào)度順序，任務(wù)松弛度越小表示任務(wù)越緊急，但當(dāng)同一就緒隊列中兩個任務(wù)的松弛度比較接近時，可能會發(fā)生任務(wù)之間的頻繁搶占。文獻(xiàn)[4]提出使用SchedISA調(diào)度集，將處理器核心分組實現(xiàn)實時任務(wù)與非實時任務(wù)在不同的核心執(zhí)行，來提高EDF調(diào)度實時性。文獻(xiàn)[5-6]提出在就緒隊列中在沒有松弛度為零的任務(wù)時，不搶占當(dāng)前任務(wù)，以此來降低任務(wù)上下文切換頻率，減小系統(tǒng)開銷。文獻(xiàn)[7]提出了LLF與LMCF(最低內(nèi)存消耗優(yōu)先)相結(jié)合的實時調(diào)度算法，當(dāng)所有任務(wù)都相對截止期限松弛度不為0時，從LLF調(diào)度切換到LMCF調(diào)度。文獻(xiàn)[8]提出在SCHED_RR調(diào)度策略與完全公平調(diào)度策略結(jié)合，依據(jù)任務(wù)權(quán)重參數(shù)來分配時間片大小，不能保證任務(wù)在期限內(nèi)完成。其中，文獻(xiàn)[4]和[9]均通過內(nèi)核分組的方式提高EDF算法的調(diào)度性能，但在多核處理器中EDF算法相比LLF算法較差。文獻(xiàn)[5-7]均是在LLF算法的基礎(chǔ)上作出了相應(yīng)改進(jìn)，但在任務(wù)集可調(diào)度的前提下，同一就緒隊列中出現(xiàn)多個等待任務(wù)的松弛度同時減為零時，任務(wù)可能不能在期限內(nèi)調(diào)度執(zhí)行完。

針對以上問題，下文基于現(xiàn)有Linux內(nèi)核中的EDF調(diào)度算法實現(xiàn)原理，對傳統(tǒng)LLF調(diào)度算法提出改進(jìn)，主要通過減小上下文切換次數(shù)以及松弛度的計算，在避免Dhall效應(yīng)的情況下最大程度減小了系統(tǒng)開銷。下文描述基于以下假設(shè)：

1)系統(tǒng)中只有一個處理器；

2)在執(zhí)行狀態(tài)下，系統(tǒng)中每個任務(wù)的所有部分都可能被剝奪執(zhí)行處理器的權(quán)力；

3)所有任務(wù)之間相互獨立，并且無序；

4)任何任務(wù)都不能自己掛起。

1 Linux實時調(diào)度問題

實時任務(wù)是指任務(wù)執(zhí)行能在截止期限內(nèi)完成，按照任務(wù)周期可以分為周期性任務(wù)、偶發(fā)性任務(wù)和非周期性任務(wù)[10]。對于偶發(fā)性與非周期性任務(wù)，其周期為相鄰任務(wù)之間到達(dá)時刻的最小時間間隔，所以一般使用任務(wù)運行時間、截止期限、周期來描述一個實時任務(wù)。在Linux內(nèi)核中實時任務(wù)主要通過DL調(diào)度類創(chuàng)建，與其他調(diào)度類相比具有更高的優(yōu)先級，是基于EDF調(diào)度算法實現(xiàn)。實時任務(wù)集只有在可調(diào)度的情況下才能在滿足期限約束，因此有如下定義。

定義1：假設(shè)M個周期性實時任務(wù)運行在N個CPU核的處理器上，每個任務(wù)的處理時間是Ci，周期時間是Pi，1≤i≤M。若任務(wù)利用率總和不超過N，則任務(wù)集可調(diào)度，即：

(1)

EDF是一種基于截至?xí)r間最短優(yōu)先調(diào)度的算法，每一個實時任務(wù)包含3個參數(shù)：WCET、D、P，其中WCET(worst-case execution time)是任務(wù)在最壞情況一個周期運行的時間，D是相對截至期限，P是周期時間，因此實時任務(wù)可以表示為(WCET，D，P)。在Linux內(nèi)核中，EDF屬于全局調(diào)度，任務(wù)可以在任意CPU核上執(zhí)行，必要時進(jìn)行核間遷移，提高了多核CPU的整體利用率。絕對截止期限等于相對截至期限加上CPU墻上時間，任務(wù)按絕對截止期限的大小排列，系統(tǒng)總是選取截止期限最小的任務(wù)運行。

例子E1：假設(shè)在M個CPU上，有M+1個實時任務(wù)需要運行，任務(wù)描述如下：

第一個任務(wù)T1=(P,P,P)；

剩余M個任務(wù)Ti=(e,P-1,P-1).

其中e是具有任意小的最壞情況任務(wù)運行時間，一次調(diào)度就能運行完。在某一時刻t0這M+1個任務(wù)被同時激活，因為第一個任務(wù)的截止期限等于t0+P，而后面M個任務(wù)的截止期限都是t0+P-1，按照EDF調(diào)度規(guī)則，后面M個任務(wù)會優(yōu)先在M個CPU上調(diào)度，而第一個任務(wù)需要等待時間e后才能被調(diào)度，執(zhí)行完任務(wù)1后的時刻位于(t0+e+P)，超過了其截止期限P，如圖1所示。但如果能在最開始分配一個CPU給任務(wù)1運行，那么M+1個任務(wù)都能在截止期限內(nèi)運行。

圖1 Dhall效應(yīng)

2 實時調(diào)度策略

在多核處理器系統(tǒng)中，LLF調(diào)度比EDF具有更好的調(diào)度性能[7]。LLF算法一定程度上可以解決多核中出現(xiàn)的Dhall效應(yīng)，任務(wù)加入就緒隊列時松弛度S=D-WCET，如果得不到及時調(diào)度或任務(wù)已經(jīng)運行了一部分時間，松弛度S=絕對截止時間-當(dāng)前時間-任務(wù)剩余運行時間。其中，松弛度最小的任務(wù)獲得優(yōu)先調(diào)度，當(dāng)松弛度為0時任務(wù)立即被調(diào)度；當(dāng)出現(xiàn)兩個任務(wù)的松弛度相同時，按“最近最久未調(diào)度”原則調(diào)度。那么，例子E1中的(M+1)個任務(wù)的松弛度分別是：

S1=0，Si(i=2,3,...,m+1)=P-1-e

按松弛度最小的調(diào)度順序，任務(wù)1最先得到調(diào)度，在截止期限內(nèi)(M+1)個任務(wù)都得到了調(diào)度。任務(wù)調(diào)度順序如圖2所示。

圖2 改進(jìn)后的調(diào)度順序

最小松弛度優(yōu)先調(diào)度在多核情況下仍然不是最優(yōu)的調(diào)度算法，當(dāng)同一就緒隊列上兩個任務(wù)的松弛度比較接近時，會發(fā)生頻繁的上下文切換；同時，每次tick周期到來都需要更新就緒隊列中任務(wù)的松弛度，當(dāng)系統(tǒng)中實時任務(wù)較多時，計算量相對較大。鑒于以上問題，提出以下改進(jìn)方法：

1)只有當(dāng)任務(wù)被激活加入就緒隊列前或當(dāng)前任務(wù)運行完觸發(fā)主調(diào)度器時，更新該CPU就緒隊列中所有任務(wù)的松弛度；

2)在每個tick周期僅更新待運行任務(wù)中松弛度最小任務(wù)的松弛度；

3)沒有任務(wù)被激活時，直到有任務(wù)的松弛度為0或當(dāng)前任務(wù)運行完，否則不發(fā)生任務(wù)切換；

4)當(dāng)有任務(wù)被激活或需要從就緒隊列選取下一個待調(diào)度的實時任務(wù)時，考慮任務(wù)搶占或交換相鄰松弛度任務(wù)的調(diào)度順序。

以上方法1)和2)用于減小松弛度計算，方法3)、4)用于減少任務(wù)上下文切換次數(shù)，其中方法1)、2)、3)易于實現(xiàn)，為了討論方法4)，在實時任務(wù)集可調(diào)度的條件下設(shè)計如下例子E2:在同一CPU就緒隊列中有3個任務(wù)被同時激活，如下：

T1=(0.05P,0.5P,0.5P)

T2=(0.05P,0.5P,0.5P)

T3=(0.6P,P,P)

松弛度分別是：

S1=S2=0.45P

S3=0.4P

當(dāng)它們同時被激活時，按LLF調(diào)度算法任務(wù)3優(yōu)先得到調(diào)度。經(jīng)過時間S1，任務(wù)1和2如果均未通過負(fù)載均衡遷移至其他CPU核，它們的松弛度將同時減為0，任務(wù)1或2會搶占當(dāng)前CPU。由于它們松弛度都為0，即最緊迫的任務(wù)，無論誰搶占當(dāng)前CPU另一個任務(wù)都無法在截止期限內(nèi)調(diào)度執(zhí)行完。如果交換相鄰松弛度任務(wù)3與1(假設(shè)在就緒隊列中，松弛度按3-1-2從小到大排列)，按1-3-2順序排列任務(wù)，則任務(wù)3運行0.4 P時間時任務(wù)2松弛度減小為0搶占任務(wù)3，即使當(dāng)前CPU核上任務(wù)不發(fā)生遷移，也能按1-3-2-3順序在期限內(nèi)保證3個任務(wù)調(diào)度執(zhí)行完。

定義2：如果任務(wù)剩余運行時間大于其松弛度，則該任務(wù)為大活任務(wù)，否則為小活任務(wù)。

定義3：將任務(wù)搶占與交換相鄰松弛度任務(wù)都稱為任務(wù)交換，其中不發(fā)生任務(wù)交換運行的任務(wù)稱為原始任務(wù)，任務(wù)交換后運行的任務(wù)稱為插隊任務(wù)。

以上例子E2中，按照定義2在任務(wù)剛被激活時，任務(wù)1和2都是小活任務(wù)，任務(wù)3 是大活任務(wù)。從以上分析看出，先調(diào)度松弛度較大的小活任務(wù)可能減少任務(wù)上下文切換次數(shù)。由此提出以下任務(wù)交換策略：在任務(wù)交換時機到來時，有原始任務(wù)K(Rk,Dk,Pk,Sk)，插隊任務(wù)Q(Rq,Dq,Pq,Sq)，如果K是大活任務(wù)且Q是小活任務(wù)，并有Rk>Sq與Rq

接下來對以上調(diào)整策略進(jìn)行分析，如圖3所示，以任務(wù)K為小活任務(wù)和任務(wù)為K大活任務(wù)兩種情況討論。若任務(wù)K為小活任務(wù)，有RkSq與RqSq>Sk，如果交換任務(wù)K與Q調(diào)度順序，在不考慮任務(wù)在核間遷移的情況下會使任務(wù)K在Q運行完之前松弛度減為0。

圖3 任務(wù)K與Q時間參數(shù)

3 實時調(diào)度實現(xiàn)細(xì)節(jié)

本節(jié)將說明如何在實時調(diào)度實體中調(diào)度ILLF(改進(jìn)的LLF)任務(wù)，對Linux內(nèi)核進(jìn)行必要修改并包括其他系統(tǒng)調(diào)用，可以從SCHED_DEADLINE調(diào)度類中獲取新實時調(diào)度類的實現(xiàn)，并且新調(diào)度類在內(nèi)核所有調(diào)度類中具有最高優(yōu)先級。

在任務(wù)的創(chuàng)建階段，新創(chuàng)建任務(wù)的WCET，截止期限和周期作為參數(shù)傳遞，新任務(wù)通過這些參數(shù)計算其初始松弛度。更新新加入任務(wù)所在就緒隊列上所有調(diào)度實體的松弛度，按松弛度大小將新任務(wù)實體new_task加入就緒隊列。其中，入隊列函數(shù)除了使用rb_leftmost與rb_left2most分別記錄松弛度最小的任務(wù)M與松弛度僅大于M的任務(wù)。Algorithm 1說明了入隊列過程，新任務(wù)實體所在就緒隊列的根節(jié)點是rb_root_of_new，當(dāng)新任務(wù)實體松弛度最小或僅大于當(dāng)前rb_leftmost對應(yīng)調(diào)度實體時，需要更新記錄值，最后函數(shù)enqueue_sched_entity將new_task加入就緒隊列。

Algorithm 1：

function

enqueue_laxity_entity_function(new_task) do

leftmost ← 1;

link ← rb_root_of_new;

while link do

parent ← link;

if new_task.laxity < parent.laxity then

link ← parent.letf;

else

link ← parent.right;

leftmost ← 0;

end if

end while

if leftmost=1 then

rb_left2most← rb_leftmost;rb_leftmost ← new_task;elseif parent = rb_leftmost then

rb_left2most ← new_task;

end if

enqueue_sched_entity (new_task, parent, link);

end function

在CPU當(dāng)前任務(wù)執(zhí)行完或有新任務(wù)加入就緒隊列后，考慮任務(wù)交換。如下Algorithm2所示，參數(shù)K、Q分別是原始任務(wù)與插隊任務(wù)。對于新加入任務(wù)，K指當(dāng)前任務(wù)，Q指新加入任務(wù)；對于當(dāng)前任務(wù)執(zhí)行完，K指rb_leftmost所指任務(wù)，Q指rb_left2most所指任務(wù)。其中big_load=1表示任務(wù)是大活任務(wù)，下一時刻調(diào)度函數(shù)pick_next_laxity_entity返回的調(diào)度實體。

Algorithm 2：

function pick_next_laxity_entity(K,Q) do

if K.big_load = 1 and Q.big_load = 0 then

if K.runtime > Q.laxity and K.laxity ≥ Q.runtime then

return Q;

end if

end if

return K;

end function

每個tick周期到來時，僅更新等待運行任務(wù)中松弛度最小的任務(wù)的松弛度。rb_leftmost指針關(guān)聯(lián)的任務(wù)如果是當(dāng)前任務(wù)，則待運行任務(wù)中松弛度最小的任務(wù)與rb_left2most指針相關(guān)聯(lián)，偽代碼如下：

left_task ← rb_leftmost;

if left_task = cur_task then

left_task ← rb_left2most;

end if

left_task.laxity ← left_task.deadline - left_task.runtime - cur_time;

如下Algorithm 3，當(dāng)任務(wù)執(zhí)行完，函數(shù)dequeue_sched_entity從就緒隊列移除當(dāng)前任務(wù)cur_task時，需要更新rb_leftmost與rb_left2most記錄的任務(wù)。

Algorithm 3：

function dequeue_laxity_entity(cur_task) do

if rb_leftmost = cur_task then

rb_leftmost ← rb_left2most;

rb_left2most ← rb_left2most.next;

else if rb_left2most = cur_task then

rb_left2most ← rb_left2most.next;

end if

dequeue_sched_entity (cur_task);

end function

4 實驗結(jié)果與分析

為了驗證上述ILLF調(diào)度算法效果，選擇標(biāo)準(zhǔn)Linux-3.14版本內(nèi)核，在擁有四核同構(gòu)處理器的tiny4412開發(fā)板上進(jìn)行實驗。其中，標(biāo)準(zhǔn)Linux為了避免實時任務(wù)長時間占用CPU，默認(rèn)情況下在1 s時間內(nèi)留出5%的CPU時間給非實時任務(wù)。實驗選擇一組運行時間在[5 ms, 80 ms]上的周期任務(wù)，最大任務(wù)利用率不能超過4*95%=380%?？紤]到Linux內(nèi)核中中斷、軟中斷、自旋鎖以及任務(wù)上下文切換帶來的系統(tǒng)開銷，任務(wù)利用率控制在4*80%=320%以內(nèi)。

為了簡化，假設(shè)每個任務(wù)的截止期限與周期相等，任務(wù)運行時間為毫秒的整數(shù)倍，并配置Hz等于1 000(tick周期時間是1 ms)。創(chuàng)建16個實時任務(wù):

Ti=((5i)ms,Di,Pi)(i=1,2,...,16)

分別考慮2種情況下任務(wù)調(diào)度：1)每個任務(wù)的任務(wù)利用率相同，松弛度差別較大；2)每個任務(wù)的松弛度相同，任務(wù)利用率不同。

定義4：在1 s時間內(nèi)平均每個核上任務(wù)上下文切換次數(shù)稱為任務(wù)上下文切換頻率。

使用vmstat命令監(jiān)控任務(wù)活動，其中cs列顯示每秒進(jìn)程上下文切換次數(shù)。對于情況1)，每個CPU平均任務(wù)利用率分別從10%～80%，EDF、LLF與ILLF算法的任務(wù)上下文切換頻率如圖4所示，由圖可以看出，在處理器任務(wù)利用率較低的情況下，3種調(diào)度算法對應(yīng)的上下文切換次數(shù)基本一樣，在任務(wù)利用率達(dá)到60%以上時，改進(jìn)的LLF調(diào)度算法的優(yōu)勢得到顯現(xiàn)。

圖4 不同任務(wù)利用率上下文切換頻率

對于情況2)，松弛度為S0，16個實時任務(wù)分別為：

Ti=((5i)ms,(5i)ms+S0,(5i)ms+S0)總?cè)蝿?wù)利用率：

總?cè)蝿?wù)利用率最大320%時，對應(yīng)最小松弛度約為180 ms，取松弛度為200～270 ms，EDF、LLF與ILLF算法任務(wù)上下文切換頻率如圖5所示，由圖可以看出，隨著松弛度的變化，平均上下文切換次數(shù)變化不大，但由于實時任務(wù)集的松弛度相同，LLF調(diào)度算法帶來了頻繁的上下文切換，遠(yuǎn)多于EDF調(diào)度算法和ILLF調(diào)度算法帶來的上下文切換次數(shù)。

圖5 不同松弛度上下文切換頻率

上面實驗例子中的任務(wù)都是小活任務(wù)，為了體現(xiàn)改進(jìn)方法4)帶來的影響，依此創(chuàng)建并激活如下任務(wù)：

Ti(i=1,2,3,4)=(60 ms,100 ms,100 ms)；

Tj(j=5,6,...,12)=(5 ms,60 ms,60 ms)。

在EDF、LLF與ILLF算法調(diào)度下任務(wù)上下文切換頻率如表1所示，在Linux負(fù)載均衡的作用下，任務(wù)T1,T5,T9被放在同一CPU核上運行，在僅使用方法3)時，在任務(wù)T1運行過程中，任務(wù)T5和T9的松弛度同時到達(dá)0，沒辦法在截止期限內(nèi)完成任務(wù)，而方法4)使得任務(wù)T5和T9在任務(wù)T1之前運行，既保證了任務(wù)能在截止期限內(nèi)完成，又減少了任務(wù)上下文切換次數(shù)。

表1 上下文切換次數(shù)頻率

5 結(jié)束語

多核處理器的使用逐漸成為一種趨勢，在實時性發(fā)方面具有很多優(yōu)點?；贚inux的實時任務(wù)調(diào)度算法一直在實時性方面做出改進(jìn)，現(xiàn)有的Linux內(nèi)核已經(jīng)實現(xiàn)了EDF調(diào)度算法，但在多核方面容易出現(xiàn)Dhall效應(yīng)，本文針對此問題提出了一種改進(jìn)的LLF調(diào)度算法，它既避免了EDF調(diào)度算法帶來的Dhall效應(yīng)，同時在LLF算法的基礎(chǔ)上采取了一定的優(yōu)化措施減少了任務(wù)上下文切換次數(shù)以及松弛度的計算，使得系統(tǒng)能根據(jù)任務(wù)的緊急程度以盡可能小的系統(tǒng)開銷在截止期限內(nèi)完成任務(wù)的調(diào)度。