李智翔，李 赟，賀 亮

LI Zhixiang,LI Yun,HE Liang

盲信號處理重點(diǎn)實(shí)驗(yàn)室，成都 610041

National Key Laboratory of Science and Technology on Blind Signal Processing,Chengdu 610041,China

1 引言

對單處理器實(shí)時系統(tǒng)而言，通常存在多個不同的任務(wù)，同一時刻只能對一個任務(wù)進(jìn)行處理；不同的任務(wù)有不同的開始時間、執(zhí)行時間、截止時間等等約束因素；當(dāng)存在多個任務(wù)時，如何通過合理安排不同任務(wù)的執(zhí)行時間，使得單處理器實(shí)時系統(tǒng)能夠?qū)@些任務(wù)進(jìn)行處理，這就是調(diào)度方法需要解決的問題[1]。

周期任務(wù)調(diào)度問題是當(dāng)前研究的熱點(diǎn)問題之一[2-4]。Liu和Layland提出了一種通用的周期任務(wù)模型[5]，該模型假設(shè)任務(wù)之間相互獨(dú)立，并根據(jù)不同的調(diào)度情況，可以將調(diào)度問題分成靜態(tài)調(diào)度問題和動態(tài)調(diào)度問題。RM（Rate Monotonic）算法[6]和 EDF（Earliest Deadline First）算法[7]分別是這兩類調(diào)度算法中的典型代表。其中，EDF算法總是優(yōu)先選擇截止期最早的任務(wù)進(jìn)行調(diào)度，而RM算法則根據(jù)任務(wù)的周期進(jìn)行優(yōu)先級調(diào)度，周期越小，優(yōu)先級越高。

當(dāng)任務(wù)開始執(zhí)行后，如出現(xiàn)其他優(yōu)先級更高的任務(wù)，按照是否可以替換當(dāng)前正在執(zhí)行任務(wù)，將調(diào)度問題劃分成可搶占式（preemptive）調(diào)度問題和非搶占式（non-preemptive）調(diào)度問題。對可搶占式調(diào)度問題，學(xué)界已有較為充分的研究和理論成果[8]。在實(shí)際系統(tǒng)中，由于硬件條件的限制以及效率和性能的考慮，存在非常多的系統(tǒng)并不支持可搶占式調(diào)度，如控制器局域網(wǎng)絡(luò)（Control Area Network，CAN）的總線消息傳遞問題[9]。與可搶占式調(diào)度問題不同，非搶占式調(diào)度問題已經(jīng)被證明是NP難問題[10]，可搶占式調(diào)度問題中得到的可調(diào)度條件在非搶占式調(diào)度問題中最多也僅為必要條件[11]。學(xué)者針對不同實(shí)際場景的特點(diǎn)，提出了解決相應(yīng)非搶占式調(diào)度問題的一系列優(yōu)秀算法[12-14]。

對通常研究的周期性調(diào)度問題而言，如控制系統(tǒng)中的采樣、計算、輸出等周期性任務(wù)，需要在給定的任務(wù)執(zhí)行周期中分配一定時長的處理資源，這里的任務(wù)執(zhí)行周期是固定不變的，每次任務(wù)執(zhí)行時間只要包含在任務(wù)執(zhí)行周期中即可，特定任務(wù)的相鄰兩次執(zhí)行之間不存在關(guān)聯(lián)和約束，如圖1（a）所示。在現(xiàn)實(shí)世界中存在這樣的一類特殊的周期任務(wù)調(diào)度問題，如監(jiān)視類問題、資源補(bǔ)給類問題、溫度控制類問題等，其調(diào)度的資源在使用上具有一定的時效性，故要求特定任務(wù)相鄰兩次執(zhí)行的時間間隔不得大于某給定值，否則必然存在一段時間該任務(wù)未被分配資源，如圖1（b）所示，本文關(guān)注此類調(diào)度問題。舉例說明，對某監(jiān)視類調(diào)度任務(wù)而言，對某特定目標(biāo)需要至少每10 s執(zhí)行一次2 s的掃描操作，以保證對可能出現(xiàn)的異常情況進(jìn)行及時處理。在實(shí)際調(diào)度時必須保證任意連續(xù)兩次掃描之間的時間間隔不大于10 s，若采用通常的非搶占式周期任務(wù)調(diào)度模型和算法，只約束每10 s有2 s的掃描，則前后兩次掃描之間的時間間隔可能大于10 s（如圖1（a）中第1、2周期任務(wù)執(zhí)行之間的間隔大于周期長度），這樣的調(diào)度結(jié)果不符合這里監(jiān)視任務(wù)的實(shí)際要求。也就是說，通常的非搶占式周期任務(wù)調(diào)度模型和相應(yīng)算法在此類資源使用具有時效性的調(diào)度問題上不適用，需要為此類問題研究新的調(diào)度模型和相應(yīng)算法。

圖1 調(diào)度模型

2 特殊的非搶占式周期任務(wù)調(diào)度問題

在本文涉及的非搶占式周期調(diào)度問題中，對任意任務(wù)oi，記任務(wù)執(zhí)行時間為Ci，任務(wù)執(zhí)行周期為Ti，其關(guān)系如圖1（b）所示。對可行的調(diào)度方案作以下規(guī)定：

（1）特定時刻最多只能調(diào)度一個任務(wù)；

（2）允許處理器空閑；

（3）任意任務(wù)的任意一次執(zhí)行時間嚴(yán)格等于Ci；

（4）對任意任務(wù)，其任意連續(xù)兩次執(zhí)行開始時刻之間的間隔不大于Ti。

本文研究單處理器可調(diào)度問題，對單處理器可調(diào)度問題定義如下：

定義1（單處理器可調(diào)度問題）給定n個任務(wù){(diào)o1,o2,…,on}及相應(yīng)參數(shù) {Ci,Ti}?i∈{0,1,…,n}，找出對這n個任務(wù)的單處理器可行調(diào)度方案。所有任務(wù)最小的重復(fù)周期稱為調(diào)度周期，記作R。

本文關(guān)注的是此類特殊調(diào)度問題的可行解。舉例說明，假設(shè)需要對4個任務(wù)進(jìn)行調(diào)度，其參數(shù){Ci,Ti}分別為{1，3}，{1，4}，{1，5}，{1，9}，單位：s。如圖2所示，為可行調(diào)度方案的一個調(diào)度周期。從圖中可以看出，每個任務(wù)均滿足調(diào)度參數(shù)的要求，圖2給出的調(diào)度方案是可行調(diào)度方案。

圖2 調(diào)度問題示例

下面對本文研究的調(diào)度問題的計算復(fù)雜度進(jìn)行證明。

定理1（NP完全性定理）本文研究的單處理器可調(diào)度問題為NP完全問題。

證明 首先證明問題為NP問題。任意給定一種調(diào)度方案，顯然可以在多項(xiàng)式時間內(nèi)判斷該調(diào)度方案是否可行。故該問題為NP問題。

其次，需要將一個已知的NP完全問題在多項(xiàng)式時間內(nèi)規(guī)約到該問題上。這里參考文獻(xiàn)[15]對3-PARTITION問題的規(guī)約。3-PARTITON問題已經(jīng)被證明是NP完全問題[16]。

首先對3-PARTITON問題進(jìn)行說明：一個3-PARTITION問題包含3m個元素，這些元素構(gòu)成一個有限集合A；給定一個常數(shù)B∈Z+，對集合A中的任意元素a∈A，有 B/4＜a＜B/2，且。問題即判斷集合A是否能夠劃分成m個兩兩交集為空的子集S1,S2,…,Sm，且滿足對根據(jù)上述定義，顯然每個子集中應(yīng)包含3個元素，故該問題被稱為3-PARTITON問題。

下面進(jìn)行規(guī)約。首先構(gòu)造一個單處理器可調(diào)度問題，該問題包含任務(wù)集合{o1,o2,…,o3m,o3m+1}，參數(shù){Ci,Ti}如下：

即若該問題存在可行調(diào)度方案，則該方案剛好將單處理器資源分配完，沒有處理器空閑。首先對任務(wù)o3m+1進(jìn)行調(diào)度分配，易知最優(yōu)方案為每2B時長中包含一個長度為B的空閑時間片段，如圖3所示。

進(jìn)一步考慮對任務(wù){(diào)o1,o2,…,o3m}進(jìn)行調(diào)度規(guī)劃。此時應(yīng)有通道周期R=2Bm。從圖3中可以看出，當(dāng)前空閑時間片段為[2B(k-1),2Bk]，對?k=1,2,…,m。這m個時間片段是互不相交的，并且每個時間片段的長度為B。若存在能夠?qū)θ蝿?wù){(diào)o1,o2,…,o3m,o3m+1}可行的調(diào)度方案，那么任務(wù){(diào)o1,o2,…,o3m}一定能夠分配到上述m個互不相交的時間片段中。又已知對集合A中的任意元素a∈A，有 B/4＜a＜B/2，由式（2），所以此可行調(diào)度方案一定是為上述m個互不相交的時間片段中的每個時間片段均分配3個任務(wù)，且對每個時間片段分配的任務(wù)有∑Ci/Ti=B，即∑ai=B，從而實(shí)際上將{o1,o2,…,o3m}對應(yīng)的{C1,C2,…,C3m}進(jìn)行了3-PARTITON問題中的劃分。也就是說，本文的調(diào)度問題的解也是3-PARTITON問題的解。故該問題是NP完全問題。證畢。

圖3 對特殊任務(wù)的最優(yōu)分配

由于本文研究調(diào)度問題的計算復(fù)雜度較高，為NP完全問題，后續(xù)章節(jié)將從兩個角度對該問題的求解算法進(jìn)行分析：一方面采用剪枝的思想，盡可能降低搜索的復(fù)雜度，在此基礎(chǔ)上提出一種模式剪枝算法；另一方面研究問題可調(diào)度的充分條件和必要條件，給出一種快速求解算法。

3 模式剪枝算法

考慮對本文研究調(diào)度問題進(jìn)行暴力搜索的情形。假設(shè)n個任務(wù)的執(zhí)行時間的最大公約數(shù)為1，設(shè)為基本時間單位。若允許處理器空閑，每個基本時間單位需要對n+1種可能性進(jìn)行搜索，假設(shè)需要搜索的基本時間單位個數(shù)為m，那么在最差情況下的搜索復(fù)雜度為(n+1)m，為m的指數(shù)級，效率是無法接受的。若需要對可調(diào)度問題進(jìn)行準(zhǔn)確判別，則必須對搜索過程進(jìn)行剪枝。

定義2（模式）給定任務(wù){(diào)o1,o2,…,on}和調(diào)度參數(shù){Ci,Ti}?i∈{0,1,…,n}，模式是指任務(wù)執(zhí)行時間 Ci的序列，任務(wù)執(zhí)行時間稱作模式的元素。一個正確的模式必須滿足以下條件：

（2）模式中Ck僅在起始位置出現(xiàn)一次；

（3）模式的長度不能超過Tk。

將模式的起始元素限制為任務(wù)執(zhí)行周期最大的任務(wù)的執(zhí)行時間，是為了使不同模式的數(shù)量盡可能的大，模式的長度盡可能長，減少無效搜索的數(shù)量。

在定義模式的基礎(chǔ)上，還需要對搜索過程進(jìn)行剪枝。首先從以下兩個方面考慮對模式進(jìn)行剪枝：

（1）不滿足任意元素對應(yīng)任務(wù)的執(zhí)行周期約束；

（2）調(diào)度冗余。

其中，調(diào)度冗余是指若模式中存在三個相同元素，且第一個和第三個元素之間的時間間隔滿足對應(yīng)任務(wù)的執(zhí)行周期約束，那么第二個元素是冗余的，該模式是無意義的，應(yīng)當(dāng)剪枝。

通過對模式剪枝減少了不同模式的數(shù)量，通過對模式之間的連接可行性進(jìn)行判別，可以進(jìn)一步減少搜索范圍。對任意模式維護(hù)一個可行的后續(xù)模式集合，對不可行的后續(xù)模式，按照以下條件進(jìn)行剪枝：

（1）兩個模式組成的序列中，不滿足任意元素對應(yīng)任務(wù)的執(zhí)行周期約束；

（2）調(diào)度冗余。

通過上述條件的剪枝，進(jìn)一步對模式的可行后續(xù)模式集合大小進(jìn)行縮減，使得搜索空間進(jìn)一步縮小。由此，本文給出了合法的模式集合以及每個模式的可行后續(xù)模式集合。下面給出模式剪枝算法的基本步驟：

步驟1生成所有可行模式。

步驟2生成所有可行模式的可行后續(xù)模式集合。

步驟3根據(jù)模式及其可行后續(xù)模式按照深度優(yōu)先的方式依次遍歷，直到出現(xiàn)已遍歷的模式，分情況判斷。

步驟3.1若該模式與第一個模式相同，則找到可行調(diào)度方案，輸出從該模式之前的序列，作為一個調(diào)度周期，算法結(jié)束；

步驟3.2若該模式與其他模式相同，則進(jìn)行剪枝，繼續(xù)其他搜索。

模式剪枝算法給出了一種對本文調(diào)度問題精確求解的方法。當(dāng)任務(wù)集合足夠復(fù)雜時，尤其是對一些需要快速反應(yīng)且可以接受次優(yōu)解的實(shí)際應(yīng)用場景，需要更快的算法進(jìn)行計算。下一章將給出近似解的快速求解算法。

4 快速求解算法

首先給出一個可行調(diào)度的充分條件。

定理2（充分條件）給定一組任務(wù){(diào)o1,o2,…,on}及其調(diào)度參數(shù){Ci,Ti}?i∈{0,1,…,n}，另一組任務(wù)及其調(diào)度參數(shù)。若對，有：

下面給出快速求解算法的基本流程。

步驟1按照式（4）對任務(wù){(diào)o1,o2,…,on}的調(diào)度參數(shù)進(jìn)行變化，得到新任務(wù)集合及其調(diào)度參數(shù)。

步驟3取調(diào)度周期為TK，將調(diào)度周期劃分成K個相等的基本單元，并維護(hù)一個大小為K的數(shù)組V，其中V(i)=K,?i=1,2,…,n，表示各單元可分配時間長度。

步驟4將任務(wù)ok分配到K個單元的開始位置，令V(i)=K-Ck,?i=1,2,…,n。

步驟5將其他n-1個任務(wù)按照其變化后的攻擊參數(shù)依次填入，根據(jù)數(shù)組V的值對能否填入進(jìn)行判斷；若某任務(wù)無法填入，則判定不可調(diào)度，算法結(jié)束；若可以填入，則依次填入并更新數(shù)組V的值，再對下一個任務(wù)進(jìn)行資源分配。

步驟6若所有任務(wù)均已填入，輸出結(jié)果，算法結(jié)束。

5 實(shí)驗(yàn)

5.1 實(shí)驗(yàn)設(shè)置

本節(jié)對本文提出的模式剪枝算法、快速求解算法以及基本的暴力搜索法進(jìn)行對比測試，選用仿真測試函數(shù)和實(shí)際應(yīng)用場景對算法進(jìn)行評測。測試用計算機(jī)處理器為Intel?Xeon?CPU E5-2667 v3@3.2 GHz，內(nèi)存為4 GB，操作系統(tǒng)為Windows 7專業(yè)版。相關(guān)仿真測試用例見表1所示。將三種算法的最大搜索時間設(shè)置為1 000 s，超過最大搜索時間視為算法無法對問題求解。

表1 測試用例屬性

在選用測試用例對算法進(jìn)行對比測試的基礎(chǔ)上，本文還將在一種實(shí)際應(yīng)用場景——網(wǎng)站監(jiān)控問題上對本文算法進(jìn)行對比測試。網(wǎng)站監(jiān)控問題，是一種通過對不同網(wǎng)站合理分配監(jiān)控資源，以實(shí)現(xiàn)對大量網(wǎng)站上傳播的黃色、暴力等信息進(jìn)行監(jiān)測和控制的問題。在網(wǎng)站監(jiān)控問題中，為了使特定網(wǎng)站的信息傳播熱度和范圍可控，需要每隔不大于一定的時間對網(wǎng)站高熱度內(nèi)容進(jìn)行一次掃描，即可實(shí)現(xiàn)全時段監(jiān)控。本文提出的調(diào)度模型和相應(yīng)算法適用于此類網(wǎng)站監(jiān)控問題。假設(shè)當(dāng)前只有一個監(jiān)控主機(jī)，需要監(jiān)控的網(wǎng)站數(shù)量為50個，特定時間只能對特定的一個網(wǎng)站進(jìn)行監(jiān)控；按照網(wǎng)站瀏覽量的不同，監(jiān)控網(wǎng)站兩次之間的最大時間間隔不同；按照網(wǎng)站大小的不同，每次監(jiān)控分別需要的時間不同。相應(yīng)參數(shù)取值范圍如表2所示，其中監(jiān)控最大時間間隔范圍為1～3 h，最小單位為0.1 h，對應(yīng)于本文研究調(diào)度問題中的任務(wù)執(zhí)行周期；單次監(jiān)控用時范圍為0.5～2 min，最小單位為0.1 min，對應(yīng)于本文研究調(diào)度問題中的任務(wù)執(zhí)行時間；網(wǎng)站對應(yīng)于調(diào)度的任務(wù)，其參數(shù)依照表2隨機(jī)生成。本文共生成20組網(wǎng)站監(jiān)控問題，對三種不同算法進(jìn)行對比測試。

表2 網(wǎng)站輿論監(jiān)控問題參數(shù)取值范圍

5.2 實(shí)驗(yàn)結(jié)果和分析

圖4為模式剪枝算法和快速求解算法得到的調(diào)度結(jié)果?？梢钥闯?，模式剪枝算法得到結(jié)果的調(diào)度周期長度為14，其中包含2個長度為1的空閑時間片段；快速求解算法得到結(jié)果的調(diào)度周期長度為3，無空閑時間片段?？焖偾蠼馑惴ǖ玫浇Y(jié)果的調(diào)度周期長度較短，形式簡單，但對處理器資源造成了一定的浪費(fèi)，若需要進(jìn)一步對如調(diào)度參數(shù)為{1，10}的任務(wù)進(jìn)行調(diào)度，模式剪枝算法得到結(jié)果的剩余資源還能夠繼續(xù)分配給該任務(wù)，而快速求解算法就必須另外分配處理器了。結(jié)合表3中的算法用時，可以看出兩種算法均比暴力搜索法效率高，而快速求解算法又比模式剪枝算法快3個數(shù)量級。

圖4 測試用例1調(diào)度結(jié)果

表3 測試用例1算法用時對比

測試用例2中的任務(wù)執(zhí)行時間、任務(wù)執(zhí)行周期參數(shù)均為小數(shù)。圖5為模式剪枝算法和快速求解算法得到的任務(wù)調(diào)度結(jié)果?？梢钥闯?，模式剪枝算法得到結(jié)果的調(diào)度周期長度為8.2，其中包含1個長度為0.7的空閑時間片段；快速求解算法得到結(jié)果的調(diào)度周期長度為2.8，無空閑時間片段。快速求解算法得到結(jié)果的調(diào)度周期長度較短，形式簡單，但對資源造成了一定的浪費(fèi)，若需要進(jìn)一步對如調(diào)度參數(shù)為{0.7，8.2，0}的任務(wù)分配資源，模式剪枝算法得到結(jié)果剩余的處理器資源還能夠繼續(xù)分配給該任務(wù)，而快速求解算法就必須另外分配處理器了。結(jié)合表4中的算法用時，可以看出三種算法的用時對比與測試用例1類似，具體的，由于調(diào)度問題與測試用例1相比變得更加復(fù)雜（任務(wù)執(zhí)行時間、任務(wù)執(zhí)行周期參數(shù)均為小數(shù)），暴力搜索法的用時提升幅度較大；模式剪枝法的用時也有提升，但提升幅度小于暴力搜索法；而快速求解法則區(qū)別不大。這是因?yàn)閷Ρ┝λ阉鞣ê湍Ｊ郊糁λ惴▉碇v，測試用例2搜索的基本時長單元為0.1，增大了搜索復(fù)雜度，故暴力搜索法的用時顯著增大；而模式剪枝法采用模式的形式對搜索范圍進(jìn)行了有效地剪枝，其用時增大程度低于暴力搜索法；快速求解法用時不受參數(shù)影響，基本保持一致。

圖5 測試用例2調(diào)度結(jié)果

表4 測試用例2算法用時對比

圖6為模式剪枝算法得到的調(diào)度結(jié)果，而快速求解算法在該測試用例上無法得到可行調(diào)度結(jié)果?？梢钥闯觯Ｊ郊糁λ惴ǖ玫浇Y(jié)果的調(diào)度周期長度為12。結(jié)合表5中的算法用時，可以看出暴力搜索法已經(jīng)無法在可接受的時間里對當(dāng)前問題進(jìn)行計算，模式剪枝算法用時與之前兩個測試用例差別不大，而快速求解法無法得到可行調(diào)度結(jié)果。

圖6 測試用例3調(diào)度結(jié)果

表5 測試用例3算法用時對比

圖7為快速求解算法得到的調(diào)度結(jié)果，而模式剪枝算法無法在可接受的時間里對當(dāng)前問題進(jìn)行有效計算。可以看出，快速求解算法得到結(jié)果的通道周期長度為8，無空閑時間片段。結(jié)合表6中的算法用時，可以看出暴力搜索法和模式剪枝算法已無法勝任此類復(fù)雜度的問題，而快速求解法的用時仍與之前三個測試用例基本一致。

圖7 測試用例4調(diào)度結(jié)果

表6 測試用例4算法用時對比

對網(wǎng)站監(jiān)控的實(shí)際問題，本文依照表2中的參數(shù)范圍隨機(jī)生成了20組問題，并應(yīng)用不同算法進(jìn)行求解。由于任務(wù)數(shù)量過多，調(diào)度結(jié)果圖過于冗雜，這里直接給出實(shí)驗(yàn)統(tǒng)計結(jié)果如表7所示。在20組問題中，暴力求解法和模式剪枝算法均沒有成功求解，而快速求解算法成功求解了20組問題中的19組；從調(diào)度周期長度可以看出，快速求解法的調(diào)度周期長度為3 h，調(diào)度方案較為簡單；從平均用時可以看出，由于該問題的復(fù)雜性較上述測試用例有了明顯提升，快速求解算法的用時較上述測試用例提升了大約一個數(shù)量級，這是因?yàn)樵谡{(diào)度周期長度基本保持不變的前提下，需要調(diào)度的任務(wù)數(shù)量提升了大約一個數(shù)量級。對于此類實(shí)際的復(fù)雜任務(wù)調(diào)度問題，只有快速求解算法能夠在短時間內(nèi)得到形式簡單的調(diào)度方案。

表7 網(wǎng)站輿論監(jiān)視問題算法對比

綜上可以看出，針對本文研究的調(diào)度問題，模式剪枝算法和快速求解算法的算法執(zhí)行效率均較暴力搜索法有了若干數(shù)量級的提升，而快速求解法的用時遠(yuǎn)優(yōu)于其他兩種方法，并且對不同問題的求解時間基本保持穩(wěn)定。對于一些任務(wù)占用處理器資源較多的情況，此時快速求解法由于對問題進(jìn)行了簡化，可能無法得到解，而此時模式剪枝算法可以確保對最優(yōu)解的求解。當(dāng)任務(wù)數(shù)量較多，或空閑時間較多時，模式剪枝算法無法在可接受時間里求得解。故對于離線有充分時間求解的情況，可以選擇模式剪枝算法；對于實(shí)時需要快速反應(yīng)的情況，可以選擇快速求解算法。

6 結(jié)束語

本文針對一種具有時效性的特殊的非搶占式周期任務(wù)調(diào)度問題開展研究，證明了該問題為NP完全問題，并根據(jù)不同的使用場景提出了模式剪枝和快速求解兩種算法，分別適用于在時間充裕條件下精確求解的情況以及對時間效率要求較高時快速近似求解的情況。相關(guān)實(shí)驗(yàn)表明了本文提出算法的有效性。在未來，筆者將對模式剪枝法進(jìn)行深入分析，嘗試進(jìn)一步提升算法的效率。

參考文獻(xiàn)：

[1]Audsley N C，Burns A，Richardson M F，et al.Hard realtime scheduling：The deadline-monotonic approach[J].Ifac Proceedings Volumes，1991，24（2）：127-132.

[2]Ripoll I，Ballester-Ripoll R.Period selection for minimal hyperperiod in periodic task systems[J].IEEE Transactions on Computers，2013，62（9）：1813-1822.

[3]Nasri M，F(xiàn)ohler G.An efficient method for assigning harmonic periods to hard real-time tasks with period Ranges[C]//27th Euromicro Conference on Real-Time Systems，2015：149-159.

[4]Nasri M，F(xiàn)ohler G，Kargahi M.A framework to construct customized harmonic periods for real-time systems[C]//26th Euromicro Conference on Real-Time Systems，2014：211-220.

[5]Liu C L，Layland J W.Scheduling algorithms for multiprogramming in a hard-real-time environment[J].Readings in Hardware/Software Co-Design，2002，20（1）：179-194.

[6]Bertossi A A，F(xiàn)usiello A.Rate-monotonic scheduling for hard-real-time systems[J].European Journal of Operational Research，1997，96（3）：429-443.

[7]Bastoni A，Brandenburg B B，Anderson J H.An empirical comparison of global，partitioned，and clustered multiprocessor EDF schedulers[C]//IEEE Real-Time Systems Symposium，2010：14-24.

[8]Leung J Y T，Whitehead J.On the complexity of fixedpriority scheduling of periodic，real-time tasks[J].Performance Evaluation，1982，2（4）：237-250.

[9]Andersson B，Tovar E.The utilization bound of nonpreemptive rate-monotonic scheduling in controller area networks is 25%[C]//IEEE International Symposium on Industrial Embedded Systems，2009：11-18.

[10]Baruah S K.The non-preemptive scheduling of periodic tasks upon multiprocessors[J].Real-Time Systems，2006，32（1/2）：9-20.

[11]George L.Preemptive and non-preemptive real-time uniprocessor scheduling，RR-2966[R].HAL-INRIA，1996.

[12]Nasri M，Brandenburg B B.Offline equivalence：A nonpreemptive scheduling technique for resource-constrained embedded real-time systems[C]//Real-Time and Embedded Technology and Applications Symposium，2017.

[13]Lee J.Improved schedulability analysis using carryin limitation for non-preemptive fixed-priority multiprocessor scheduling[J].IEEE Transactions on Computers，2017，66（10）：1816-1823.

[14]Andrei S，Cheng A M K，Radulescu V.An improved upperbound algorithm for non-preemptive task scheduling[C]//International Symposium on Symbolic and Numeric Algorithms for Scientific Computing，2015：153-159.

[15]Jeffay K，Stanat D F，Martel C U.On non-preemptive scheduling of period and sporadic tasks[C]//Proceedings of Twelfth Real-Time Systems Symposium，1991：129-139.

[16]Garey M R，Johnson D S.Computers and intractability：A guide to the theory of NP-completeness[M].New York，N Y：W H Freeman&Co，1979.