基于Linux的多核實時任務調度算法改進

陳國良，朱艷軍

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

0 引言

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

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

針對以上問題，下文基于現有Linux內核中的EDF調度算法實現原理，對傳統LLF調度算法提出改進，主要通過減小上下文切換次數以及松弛度的計算，在避免Dhall效應的情況下最大程度減小了系統開銷。下文描述基于以下假設：

1)系統中只有一個處理器；

2)在執行狀態下，系統中每個任務的所有部分都可能被剝奪執行處理器的權力；

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

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

1 Linux實時調度問題

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

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

(1)

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

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

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

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

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

圖1 Dhall效應

2 實時調度策略

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

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

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

圖2 改進后的調度順序

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

1)只有當任務被激活加入就緒隊列前或當前任務運行完觸發主調度器時，更新該CPU就緒隊列中所有任務的松弛度；

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

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

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

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

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

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

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

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

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

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

圖3 任務K與Q時間參數

3 實時調度實現細節

本節將說明如何在實時調度實體中調度ILLF(改進的LLF)任務，對Linux內核進行必要修改并包括其他系統調用，可以從SCHED_DEADLINE調度類中獲取新實時調度類的實現，并且新調度類在內核所有調度類中具有最高優先級。

在任務的創建階段，新創建任務的WCET，截止期限和周期作為參數傳遞，新任務通過這些參數計算其初始松弛度。更新新加入任務所在就緒隊列上所有調度實體的松弛度，按松弛度大小將新任務實體new_task加入就緒隊列。其中，入隊列函數除了使用rb_leftmost與rb_left2most分別記錄松弛度最小的任務M與松弛度僅大于M的任務。Algorithm 1說明了入隊列過程，新任務實體所在就緒隊列的根節點是rb_root_of_new，當新任務實體松弛度最小或僅大于當前rb_leftmost對應調度實體時，需要更新記錄值，最后函數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當前任務執行完或有新任務加入就緒隊列后，考慮任務交換。如下Algorithm2所示，參數K、Q分別是原始任務與插隊任務。對于新加入任務，K指當前任務，Q指新加入任務；對于當前任務執行完，K指rb_leftmost所指任務，Q指rb_left2most所指任務。其中big_load=1表示任務是大活任務，下一時刻調度函數pick_next_laxity_entity返回的調度實體。

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周期到來時，僅更新等待運行任務中松弛度最小的任務的松弛度。rb_leftmost指針關聯的任務如果是當前任務，則待運行任務中松弛度最小的任務與rb_left2most指針相關聯，偽代碼如下：

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，當任務執行完，函數dequeue_sched_entity從就緒隊列移除當前任務cur_task時，需要更新rb_leftmost與rb_left2most記錄的任務。

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 實驗結果與分析

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

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

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

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

定義4：在1 s時間內平均每個核上任務上下文切換次數稱為任務上下文切換頻率。

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

圖4 不同任務利用率上下文切換頻率

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

Ti=((5i)ms,(5i)ms+S0,(5i)ms+S0)總任務利用率：

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

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

上面實驗例子中的任務都是小活任務，為了體現改進方法4)帶來的影響，依此創建并激活如下任務：

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算法調度下任務上下文切換頻率如表1所示，在Linux負載均衡的作用下，任務T1,T5,T9被放在同一CPU核上運行，在僅使用方法3)時，在任務T1運行過程中，任務T5和T9的松弛度同時到達0，沒辦法在截止期限內完成任務，而方法4)使得任務T5和T9在任務T1之前運行，既保證了任務能在截止期限內完成，又減少了任務上下文切換次數。

表1 上下文切換次數頻率

5 結束語

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