基于Linux的多核實(shí)時(shí)任務(wù)調(diào)度算法改進(jìn)

陳國良，朱艷軍

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

0 引言

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

實(shí)時(shí)調(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ù)允許運(yùn)行的CPU核。LLF算法可以規(guī)避Dhall效應(yīng)，其根據(jù)任務(wù)緊迫程度來決定實(shí)時(shí)任務(wù)的調(diào)度順序，任務(wù)松弛度越小表示任務(wù)越緊急，但當(dāng)同一就緒隊(duì)列中兩個(gè)任務(wù)的松弛度比較接近時(shí)，可能會(huì)發(fā)生任務(wù)之間的頻繁搶占。文獻(xiàn)[4]提出使用SchedISA調(diào)度集，將處理器核心分組實(shí)現(xiàn)實(shí)時(shí)任務(wù)與非實(shí)時(shí)任務(wù)在不同的核心執(zhí)行，來提高EDF調(diào)度實(shí)時(shí)性。文獻(xiàn)[5-6]提出在就緒隊(duì)列中在沒有松弛度為零的任務(wù)時(shí)，不搶占當(dāng)前任務(wù)，以此來降低任務(wù)上下文切換頻率，減小系統(tǒng)開銷。文獻(xiàn)[7]提出了LLF與LMCF(最低內(nèi)存消耗優(yōu)先)相結(jié)合的實(shí)時(shí)調(diào)度算法，當(dāng)所有任務(wù)都相對截止期限松弛度不為0時(shí)，從LLF調(diào)度切換到LMCF調(diào)度。文獻(xiàn)[8]提出在SCHED_RR調(diào)度策略與完全公平調(diào)度策略結(jié)合，依據(jù)任務(wù)權(quán)重參數(shù)來分配時(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)度的前提下，同一就緒隊(duì)列中出現(xiàn)多個(gè)等待任務(wù)的松弛度同時(shí)減為零時(shí)，任務(wù)可能不能在期限內(nèi)調(diào)度執(zhí)行完。

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

圖1 Dhall效應(yīng)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

以上例子E2中，按照定義2在任務(wù)剛被激活時(shí)，任務(wù)1和2都是小活任務(wù)，任務(wù)3 是大活任務(wù)。從以上分析看出，先調(diào)度松弛度較大的小活任務(wù)可能減少任務(wù)上下文切換次數(shù)。由此提出以下任務(wù)交換策略：在任務(wù)交換時(shí)機(jī)到來時(shí)，有原始任務(wù)K(Rk,Dk,Pk,Sk)，插隊(duì)任務(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ù)在核間遷移的情況下會(huì)使任務(wù)K在Q運(yùn)行完之前松弛度減為0。

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

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

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

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

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ù)加入就緒隊(duì)列后，考慮任務(wù)交換。如下Algorithm2所示，參數(shù)K、Q分別是原始任務(wù)與插隊(duì)任務(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ù)，下一時(shí)刻調(diào)度函數(shù)pick_next_laxity_entity返回的調(diào)度實(shí)體。

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

每個(gè)tick周期到來時(shí)，僅更新等待運(yùn)行任務(wù)中松弛度最小的任務(wù)的松弛度。rb_leftmost指針關(guān)聯(lián)的任務(wù)如果是當(dāng)前任務(wù)，則待運(yùn)行任務(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從就緒隊(duì)列移除當(dāng)前任務(wù)cur_task時(shí)，需要更新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 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

上面實(shí)驗(yàn)例子中的任務(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核上運(yùn)行，在僅使用方法3)時(shí)，在任務(wù)T1運(yùn)行過程中，任務(wù)T5和T9的松弛度同時(shí)到達(dá)0，沒辦法在截止期限內(nèi)完成任務(wù)，而方法4)使得任務(wù)T5和T9在任務(wù)T1之前運(yùn)行，既保證了任務(wù)能在截止期限內(nèi)完成，又減少了任務(wù)上下文切換次數(shù)。

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

5 結(jié)束語

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