基于半劃分調(diào)度的Linux 實(shí)時(shí)調(diào)度算法改進(jìn)*

李 輝 劉志紅

（1.中國電子科技集團(tuán)公司第二十八研究所 南京 210007）（2.武漢達(dá)夢數(shù)據(jù)庫股份有限公司 武漢 430073）

1 引言

實(shí)時(shí)系統(tǒng)在工業(yè)控制、航空航天、自動(dòng)駕駛等眾多領(lǐng)域扮演著重要角色。不同于一般的操作系統(tǒng)，實(shí)時(shí)系統(tǒng)的目標(biāo)不是高的吞吐量，而是保證任務(wù)在特定時(shí)間內(nèi)完成。在實(shí)時(shí)系統(tǒng)中，實(shí)時(shí)調(diào)度算法處于核心位置，實(shí)時(shí)調(diào)度算法為實(shí)時(shí)任務(wù)能在截止期限前完成提供保證。

傳統(tǒng)的多處理器實(shí)時(shí)調(diào)度算法分為劃分調(diào)度（Partitioned Scheduling）算法和全局調(diào)度（Global Scheduling）算法［1～2］。在全局調(diào)度中，所有實(shí)時(shí)任務(wù)都存儲在一個(gè)按照優(yōu)先級排序的隊(duì)列中，全局調(diào)度程序從該隊(duì)列中選擇優(yōu)先級最高的任務(wù)執(zhí)行。在分區(qū)調(diào)度中，每個(gè)任務(wù)被分配給一個(gè)處理器，其中每個(gè)任務(wù)將在其上執(zhí)行，并且處理器之間是獨(dú)立調(diào)度的。全局調(diào)度能夠帶來較高的系統(tǒng)利用率，但是因?yàn)槿蝿?wù)可能會(huì)頻繁地在處理器間切換，所以會(huì)帶來較高的系統(tǒng)開銷；劃分調(diào)度可以比較容易地應(yīng)用已有的單處理機(jī)調(diào)度算法，但是系統(tǒng)利用率低［3］。Anderson 等首次提出了半劃分調(diào)度（Semi-partitioned Scheduling）算法EDF-fm［4～5］，該算法中大部分任務(wù)采用劃分調(diào)度的思想被劃分到指定處理器上運(yùn)行，而另一部分任務(wù)采取全局調(diào)度的思想，允許在多個(gè)處理器上遷移。這種方法可以提升系統(tǒng)可調(diào)度性并相比全局調(diào)度降低了上下文切換次數(shù)，降低了系統(tǒng)負(fù)載，相比純粹的劃分調(diào)度提升了處理器利用率。隨后，文獻(xiàn)［6］提出半劃分調(diào)度算法EKG，不同于EDF-fm，EKG設(shè)定遷移任務(wù)在特定的時(shí)間段內(nèi)執(zhí)行，而固定任務(wù)則根據(jù)EDF 進(jìn)行調(diào)度，實(shí)現(xiàn)了硬實(shí)時(shí)系統(tǒng)上的可調(diào)度性保障。Kato 和Yamasaki 在文獻(xiàn)［7～11］中提出了EDDHP、EDDP、RMDP、DMPM 和EDF-WM 算法，這些算法旨在使用任務(wù)拆分的方法實(shí)現(xiàn)高可調(diào)度性和低搶占次數(shù)，其中EDDP 的最壞資源利用率界限為65%，基于固定優(yōu)先級的RMDP 和DMPM 則達(dá)到了50%的最壞資源利用率界限，EDF-WM 由DMPM 方法擴(kuò)展而來。文獻(xiàn)［12］提出的SPA1 和SPA2 算法首次將單個(gè)處理器上的最壞資源利用率界限提高到了Liu&Layland 提出的使用率上限［13］。文獻(xiàn)［14］提出了一種多處理器EDF調(diào)度的任務(wù)分割方案，不同于上述其他方案，該方案有著易于實(shí)施和低負(fù)載的特點(diǎn)。

Linux 于3.14 版本引入了基于GEDF 實(shí)現(xiàn)的deadline 調(diào)度器，該調(diào)度器能夠保證實(shí)時(shí)任務(wù)在最壞截止期限前完成，但是多核全局調(diào)度會(huì)遇到Dhall效應(yīng)［15］。針對該問題和上述半劃分調(diào)度算法的研究，文章基于半劃分調(diào)度對Linux 內(nèi)核中實(shí)時(shí)調(diào)度算法做了改進(jìn)；在EDF 算法的基礎(chǔ)上，加入半劃分調(diào)度的思想，在實(shí)時(shí)任務(wù)處理器利用率差別較大時(shí)也能成功調(diào)度，提高Linux 實(shí)時(shí)任務(wù)可調(diào)度性的同時(shí)降低了上下文切換頻率，從而降低了上下文切換帶來的系統(tǒng)開銷。

2 任務(wù)模型

EDF算法基于這樣一個(gè)周期任務(wù)模型：一個(gè)周期性任務(wù)（或簡稱任務(wù)）τi是一個(gè)三元組(Ci,Di,Pi)，其中各元素定義為

1）Ci：最壞情況執(zhí)行時(shí)間（Worst Case Execution Time，簡稱WCET），即任務(wù)每次釋放需要的最長執(zhí)行時(shí)間。

2）Di：相對截止期。即τi每次釋放后期望在Di時(shí)間內(nèi)完成執(zhí)行。

3）Pi：最短釋放間隔（也稱為周期）。τi的兩次釋放之間需要至少Pi時(shí)間間隔。

EDF 算法總是最先調(diào)度執(zhí)行deadline 最早到來的那個(gè)任務(wù)。對于有M個(gè)處理器的系統(tǒng)，優(yōu)先級最高的前M 個(gè)任務(wù)（即deadline 最早到來的前M 個(gè)任務(wù)）將被選擇在對應(yīng)M個(gè)處理器上運(yùn)行。

下面按照Linux 中deadline 調(diào)度器的準(zhǔn)入策略，對于運(yùn)行在M 個(gè)處理器上的N 個(gè)周期性任務(wù){(diào)τ1,τ2,…,τN}，給出該任務(wù)集的可調(diào)度性必要條件如定義1。

定義1：假設(shè)有N 個(gè)周期性任務(wù)τ1,τ2,…,τN運(yùn)行在M 個(gè)處理器上，任務(wù)τi的最壞執(zhí)行時(shí)間為Ci，相對截止器為Di，周期為Pi，1 ≤i≤N。若任務(wù)利用率總和不超過M，則任務(wù)集可調(diào)度，即：

Linux 中基于GEDF 算法實(shí)現(xiàn)的deadline 調(diào)度器并不嚴(yán)格遵守上文描述的EDF周期任務(wù)模型，調(diào)度基于如下三個(gè)參數(shù)來調(diào)度任務(wù)：

1）runtime：任務(wù)執(zhí)行時(shí)間，通常設(shè)置為大于等于Ci的值。

2）deadline：相對截止期限，即Di。

3）period：任務(wù)周期，通常設(shè)置為小于等于Pi的值。

Linux 中提供了sched_setattr（）系統(tǒng)調(diào)用對這三個(gè)參數(shù)進(jìn)行設(shè)置。

3 調(diào)度策略

Linux 中deadline 調(diào)度器的調(diào)度過程可以用例1來描述。

例1：對于在具有M 個(gè)CPU 的系統(tǒng)上的M+1個(gè)任務(wù)的集合{τ1,τ2,…,τM+1} ，我們考慮這樣一種情況：其中第一個(gè)任務(wù)τ1=(P,P,P)的WCET、相對截止期和周期都等于P，剩下的M 個(gè)任務(wù)τi=(e,P-1,P-1) 具有任意小的最壞情況執(zhí)行時(shí)間（這里用“e”表示）和比第一個(gè)任務(wù)小的周期。因此，如果所有任務(wù)在同一時(shí)間t 激活，全局EDF 將首先調(diào)度這M 個(gè)任務(wù)（因?yàn)樗鼈兊慕^對期限為t+P-1，小于τ1的絕對期限t+P）。因此，τ1只能在時(shí)間t+e安排執(zhí)行，并將在其絕對截止日期之后的t+e+P時(shí)刻完成。任務(wù)集的總利用率為

對于較小的e 值，這個(gè)值可能變得非常接近1，看起來在M（M＞1）個(gè)處理器上這個(gè)任務(wù)集肯定可以很好地調(diào)度，但是事實(shí)上τ1只能在其他M個(gè)任務(wù)運(yùn)行完畢之后才開始執(zhí)行，因此τ1的deadline 不能得到滿足，這就是Dhall 效應(yīng)，Dhall 效應(yīng)調(diào)度如圖1所示。

圖1 Dhall效應(yīng)

圖1 說明了在任務(wù)集中任務(wù)的處理器利用率相差較大的時(shí)候，即使任務(wù)集的利用率并不高，deadline調(diào)度器有時(shí)并不能保證每一個(gè)實(shí)時(shí)任務(wù)都可調(diào)度。

為了解決上述問題，文章提出新的調(diào)度策略如下：對于有N 個(gè)任務(wù)的隊(duì)列，將N 個(gè)任務(wù)按照利用率進(jìn)行排序，每次找出利用率最大的任務(wù)τtop從隊(duì)列中取出，嘗試將其分配給第m=1 個(gè)處理器，采用單處理器EDF可調(diào)度條件進(jìn)行判斷，如果可調(diào)度就完成分配，否則將其重新放到隊(duì)尾，如此循環(huán)N 次完成第m=1個(gè)處理器的任務(wù)分配，然后對于其他任務(wù)繼續(xù)按照全局EDF 在剩下的其他CPU 上進(jìn)行調(diào)度。具體算法如算法1所示。

算法1 基于半劃分調(diào)度改進(jìn)的調(diào)度算法

input：the task set Γ={τ1,τ2,…,τn}

output：0 if Γ is schedulable and-1 if not

1）sort Γ according to the utilization rate from largest to smallest

2）for i=1，2，……n do

3）take out the first task from Γ asτ

4）utili0 ←0

5）for task in CPU0.tasks do

6） utili0+=task.runtime/task.period

7）end

8）utili0+=τ.runtime/τ。period

9）if utili0 ＜=1

10） assignτto CPU0（partitioned EDF）

11）else

12） putτat the end of Γ

13）end

14）assign tasks in Γ to the other CPUs（global EDF）

對算法一繼續(xù)用例1 中的情況進(jìn)行分析：任務(wù)集{τ1,τ2,…,τM+1} 運(yùn)行在M 個(gè)處理器上，其中第一個(gè)任務(wù)τ1=(P,P,P)的WCET、相對截止期和周期都等于P，剩下的M 個(gè)任務(wù)τi=(e,P-1,P-1) 具有任意小的最壞情況執(zhí)行時(shí)間（這里用“e”表示）和比第一個(gè)任務(wù)小的周期。根據(jù)我們的算法τ1會(huì)被分配到CPU0 上，此時(shí)CPU0 的利用率達(dá)到1，所以其他任務(wù)無法再分配給CPU0，{τ2,…,τM+1} 將被分配到剩下的M-1 個(gè)CPU 上根據(jù)GEDF 策略進(jìn)行調(diào)度。此時(shí)的調(diào)度順序如圖2所示。

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

可以看到在文章提出的算法中，所有任務(wù)的截止期限都被滿足了，處理器利用率最高的τ1獨(dú)占一個(gè)CPU，其他M 個(gè)任務(wù)在M-1 個(gè)CPU 上繼續(xù)按照全局調(diào)度的策略進(jìn)行調(diào)度。

4 實(shí)驗(yàn)結(jié)果與分析

首先使用實(shí)時(shí)多處理器體系結(jié)構(gòu)的調(diào)度模擬器SimSo 進(jìn)行仿真，對于例1 所述情況使用GEDF進(jìn)行調(diào)度時(shí)，繪制甘特圖，如圖3所示。其中任務(wù)1的WCET、相對截止期、周期均為10ms，其他任務(wù)WCET=1ms，相對截止期、周期均為10ms?？梢园l(fā)現(xiàn)在第一個(gè)周期，任務(wù)1 只能在任務(wù)3 完成后開始執(zhí)行，在執(zhí)行9ms 后被任務(wù)5 搶占，并且在后續(xù)每一個(gè)周期都會(huì)被提前搶占，任務(wù)不能保證完成。使用基于半劃分調(diào)度改進(jìn)過的算法進(jìn)行調(diào)度時(shí)，繪制甘特圖，如圖4 所示，任務(wù)一獨(dú)占CPU2，其他任務(wù)在另外三個(gè)CPU 上按照GEDF 算法進(jìn)行調(diào)度，所有任務(wù)都能在截止期限前保證完成。

圖3 GEDF調(diào)度結(jié)果

圖4 改進(jìn)后的調(diào)度結(jié)果

然后在具有四個(gè)核心的Loongson-3A R4 處理器上進(jìn)行測試，Linux 內(nèi)核版本為Linux 4.19.0-12-loongson-3 mips64。使用隨機(jī)的runtime、period和deadline創(chuàng)建總利用率固定的任務(wù)集分別使用Linux 中的deadline 調(diào)度器和文章改進(jìn)的EDF調(diào)度器進(jìn)行調(diào)度，繪制出任務(wù)集調(diào)度成功率與任務(wù)集總利用率關(guān)系的圖像，如圖5所示。

圖5 不同利用率的任務(wù)集調(diào)度成功率

在任務(wù)集總利用率較低時(shí)，deadline 調(diào)度器與基于半劃分調(diào)度改進(jìn)的調(diào)度都能滿足所有任務(wù)的截止期限，但當(dāng)任務(wù)集總利用率接近甚至超過處理器總數(shù)時(shí)，基于半劃分調(diào)度改進(jìn)的調(diào)度對任務(wù)集的可調(diào)度性明顯優(yōu)于deadline調(diào)度器。

由于部分任務(wù)被固定到一單獨(dú)處理器上運(yùn)行，改進(jìn)后的調(diào)度算法能明顯降低上下文切換次數(shù)，如圖6所示。

圖6 不同利用率的任務(wù)集上下文切換次數(shù)

5 結(jié)語

實(shí)時(shí)任務(wù)的調(diào)度算法在許多重要系統(tǒng)中發(fā)揮著關(guān)鍵作用，Linux 操作系統(tǒng)也一直在實(shí)時(shí)性上做出各種嘗試，現(xiàn)有的Linux 實(shí)時(shí)調(diào)度算法是基于全局EDF 調(diào)度實(shí)現(xiàn)的，在多核處理器上容易出現(xiàn)Dhall 效應(yīng)，本文針對此問題提出了一種基于半劃分調(diào)度改進(jìn)的調(diào)度算法，避免了全局EDF調(diào)度帶來的Dhall效應(yīng)，同時(shí)提高了調(diào)度器的可調(diào)度性，降低了上下文切換次數(shù)和系統(tǒng)開銷。