應(yīng)用映射與任務(wù)調(diào)度綜述

于千城

摘要：應(yīng)用映射是CPS系統(tǒng)設(shè)計(jì)的關(guān)鍵步驟之一，是近年來國內(nèi)外CPS系統(tǒng)研究、開發(fā)和應(yīng)用的熱門課題。應(yīng)用映射工具的出現(xiàn)簡化了CPS系統(tǒng)的設(shè)計(jì)過程，縮短了設(shè)計(jì)周期。應(yīng)用映射理論的研究和任務(wù)調(diào)度算法的改進(jìn)，對于提高CPS系統(tǒng)設(shè)計(jì)非常重要。該文主要關(guān)注應(yīng)用映射中調(diào)度和分配兩個(gè)關(guān)鍵步驟的優(yōu)化問題。為了適應(yīng)實(shí)時(shí)系統(tǒng)具有多種任務(wù)類型、約束復(fù)雜性的新特點(diǎn)和新要求，該文在分析了傳統(tǒng)的常規(guī)可調(diào)度理論和方法的基礎(chǔ)上，以任務(wù)特點(diǎn)為橫軸，任務(wù)調(diào)度策略為縱軸討論了各種任務(wù)調(diào)度方法（EDD，EDF，LDF，RM）。著重對實(shí)時(shí)調(diào)度理論中的任務(wù)調(diào)度技術(shù)進(jìn)行了研究，并在此基礎(chǔ)上闡述了評價(jià)任務(wù)調(diào)度算法的各種標(biāo)準(zhǔn)，如可行性分析，可調(diào)度性分析，資源利用率等。最后對多處理器調(diào)度進(jìn)行了介紹，并從多處理器分組調(diào)度及全局調(diào)度兩方面分析了多處理調(diào)度的算法設(shè)計(jì)及可調(diào)度性分析。

關(guān)鍵詞：實(shí)時(shí)調(diào)度；可調(diào)度性分析；調(diào)度算法；多處理器調(diào)度

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2015）03-0248-04

Application Mapping and Task Scheduling

YU Qian-cheng

（Beifang University of Nationalities， Yinchuan 750021， China）

Abstract： Application mapping is a key step in CPS system design， and it has been one of the hot research point in the research， development and application of CPS system. The emergence application mapping tool simplifies the CPS system design process and shorten the design cycle. Theoretical research and application mapping task scheduling algorithm for improving the CPS system design is very important. This article focuses on the application mapping scheduling and allocation of two key steps of optimization problems.In order to adapt to new features and requirements of real-time systems with a variety of mission types， constraints and complexity. This article discusses kinds of task scheduling method （EDD，EDF， LDF，RM），base on the analysis of the traditional scheduling theory ， take task characteristics as the horizontal axis， scheduling strategy as the longitudinal axis. Focus on task scheduling techniques in real-time scheduling theory and elaborated evaluation of task scheduling algorithm， such as feasibility analysis， schedulability analysis， and resource utilization. At last it introduces multiprocessor scheduling， and analysis the multiprocessor scheduling algorithms and schedulability from multiprocessor division scheduling and global scheduling.

Key words：real-time scheduling；schedulability analysis；scheduling algorithm；multiprocessor scheduling

實(shí)時(shí)系統(tǒng)是指必須在精確時(shí)間約束內(nèi)對外部環(huán)境事件做出響應(yīng)的計(jì)算系統(tǒng)。因此實(shí)時(shí)系統(tǒng)的正確性不僅依賴于計(jì)算結(jié)果的正確性，同時(shí)也依賴于產(chǎn)生計(jì)算結(jié)果的時(shí)間。對實(shí)時(shí)系統(tǒng)的一個(gè)普遍的誤解是“實(shí)時(shí)”即“快速”。事實(shí)上，快速計(jì)算以給定任務(wù)集的平均響應(yīng)時(shí)間最小為目標(biāo)，而實(shí)時(shí)計(jì)算則需要滿足每個(gè)任務(wù)個(gè)體的時(shí)限需求。例如，文獻(xiàn)[1]證明了，提高處理器的計(jì)算速度和縮短計(jì)算時(shí)間并不意味著系統(tǒng)新能的提升，在某些情況下甚至?xí)档拖到y(tǒng)的性能。

大多數(shù)實(shí)時(shí)系統(tǒng)都是基于一個(gè)實(shí)時(shí)的內(nèi)核構(gòu)建的，而這些內(nèi)核最核心的功能就是任務(wù)管理和任務(wù)調(diào)度。任務(wù)調(diào)度作為決定實(shí)時(shí)系統(tǒng)性能的重要技術(shù)，一直被各學(xué)科專家廣泛的研究。任務(wù)調(diào)度的分類方法按照其分類依據(jù)而有所不同：按照任務(wù)實(shí)時(shí)性要求可分為硬實(shí)時(shí)調(diào)度和軟實(shí)時(shí)調(diào)度；根據(jù)任務(wù)是在一個(gè)還是多個(gè)處理器上運(yùn)行可分為單處理器實(shí)時(shí)調(diào)度和多處理器實(shí)時(shí)調(diào)度，其中多處理器實(shí)時(shí)調(diào)度又可分為集中式調(diào)度和分布式調(diào)度；根據(jù)調(diào)度算法和可調(diào)度性判定是在任務(wù)運(yùn)行時(shí)進(jìn)行的還是任務(wù)運(yùn)行前進(jìn)行的，又分為靜態(tài)調(diào)度、動態(tài)調(diào)度和混合調(diào)度；根據(jù)被調(diào)度任務(wù)是否可以相互搶占，可分為搶占式調(diào)度和非搶占式調(diào)度；根據(jù)任務(wù)請求到達(dá)的特性，可分為周期性任務(wù)調(diào)度和非周期性任務(wù)調(diào)度。 本文以任務(wù)的特點(diǎn)（周期性任務(wù)和非周期性任務(wù)）為橫軸，以任務(wù)調(diào)度策略（包括時(shí)鐘驅(qū)動的調(diào)度，固定優(yōu)先級調(diào)度，動態(tài)優(yōu)先級調(diào)度）為縱軸來討論各種任務(wù)調(diào)度方法。在此基礎(chǔ)上闡述了評價(jià)任務(wù)調(diào)度算法的各種標(biāo)準(zhǔn)，如可行性分析，可調(diào)度性分析，資源利用率等等。

1 時(shí)鐘驅(qū)動的調(diào)度

時(shí)鐘驅(qū)動的調(diào)度（clock-driven）是指在系統(tǒng)開始執(zhí)行之前，選擇一個(gè)特定的時(shí)刻來決定哪一個(gè)作業(yè)在何時(shí)執(zhí)行。在一個(gè)典型的時(shí)鐘驅(qū)動系統(tǒng)里，所有實(shí)時(shí)任務(wù)的參數(shù)都是固定且已知的。作業(yè)的調(diào)度時(shí)間表被脫機(jī)計(jì)算并保存下來，并在運(yùn)行時(shí)使用[2]。根據(jù)該調(diào)度算法，調(diào)度程序在每一個(gè)調(diào)度決策時(shí)刻調(diào)度作業(yè)運(yùn)行。

時(shí)鐘驅(qū)動的調(diào)度策略的實(shí)現(xiàn)方式是利用一個(gè)可編程的時(shí)鐘發(fā)出的周期性時(shí)鐘中斷來控制調(diào)度器運(yùn)行，并且調(diào)度器維護(hù)一個(gè)內(nèi)部的時(shí)間值來計(jì)算任務(wù)周期和決定何時(shí)調(diào)用這些任務(wù)，這種實(shí)現(xiàn)方式可以繼續(xù)被細(xì)分為時(shí)鐘驅(qū)動調(diào)度和有計(jì)數(shù)器的時(shí)鐘驅(qū)動調(diào)度。時(shí)鐘驅(qū)動調(diào)度使用一個(gè)周期時(shí)鐘發(fā)出的中斷來中斷系統(tǒng)運(yùn)行并調(diào)用調(diào)度器來更新系統(tǒng)時(shí)間，并在需要時(shí)重新調(diào)度。有計(jì)數(shù)器的時(shí)鐘驅(qū)動調(diào)度維護(hù)一個(gè)計(jì)數(shù)器用來限制調(diào)度點(diǎn)的數(shù)量。在每一個(gè)調(diào)度點(diǎn)，計(jì)數(shù)器的值被初始化為到達(dá)下一個(gè)任務(wù)截止期限的時(shí)鐘周期數(shù)。當(dāng)每一次時(shí)鐘中斷發(fā)生時(shí)，計(jì)數(shù)器的值都會遞減；當(dāng)計(jì)數(shù)器的值減為[0]時(shí)，調(diào)度器被觸發(fā)。

時(shí)鐘驅(qū)動的調(diào)度是一種靜態(tài)調(diào)度，其調(diào)度開銷非常小，概念簡單，可預(yù)測性好，對于實(shí)時(shí)任務(wù)參數(shù)非常清楚且穩(wěn)定的情況下，時(shí)間驅(qū)動調(diào)度是很好的選擇。但也有不足之處，包括：作業(yè)的釋放時(shí)間必須固定，所有周期任務(wù)組合必須事先預(yù)知，因此缺乏靈活性；另外，如果系統(tǒng)環(huán)境在運(yùn)行時(shí)出現(xiàn)一些變化，就可能引起整個(gè)系統(tǒng)調(diào)度失敗。

2 非周期性任務(wù)的優(yōu)先級驅(qū)動調(diào)度

2.1 最早完成期限算法（Earliest Due Date）

EDD算法針對的是最簡單的任務(wù)模型，即一個(gè)非周期的任務(wù)集合在單個(gè)處理器上調(diào)度，要求讓最大延遲最小化。所有的任務(wù)都在同一時(shí)間到達(dá)，但是這些任務(wù)所需的CPU時(shí)間以及任務(wù)期限（deadline）是不相同的。除此以外沒有其他的約束，因此任務(wù)之間是沒有依賴關(guān)系的，即任務(wù)是各自獨(dú)立的，并且任務(wù)沒有互斥訪問資源的限制。由于所有的任務(wù)都是在同一時(shí)刻到達(dá)的，因此不存在任務(wù)的搶占問題。

Jackson[3]在1955年發(fā)明了一個(gè)簡單的算法，來解決這種任務(wù)模型，即最早完成期限算法（EDD算法）：給定一個(gè)相互獨(dú)立的任務(wù)集合，從最小化最大延遲的標(biāo)準(zhǔn)來看，只要按照非降序的任務(wù)完成期限來執(zhí)行這些任務(wù)，則這種調(diào)度必然是最優(yōu)的。用EDD算法構(gòu)造最優(yōu)調(diào)度的復(fù)雜度在于根據(jù)任務(wù)的完成期限對任務(wù)排序，因此構(gòu)造包含[n]個(gè)任務(wù)的EDD算法的復(fù)雜度為[O（nlogn）]。

2.2 最早期限優(yōu)先算法（Earliest Date Frist）

EDD算法解決的是最簡單的任務(wù)模型的調(diào)度，若任務(wù)的到達(dá)時(shí)間不相同，即任務(wù)會在執(zhí)行期的任意時(shí)刻到達(dá)，則必定會發(fā)生搶占的情況。Horn在1974年發(fā)明了最早期限優(yōu)先算法（EDF）來解決包含[n]個(gè)相互獨(dú)立的任務(wù)的任務(wù)集在單處理器上的調(diào)度問題，系統(tǒng)中的任務(wù)到達(dá)時(shí)間是動態(tài)的，且任務(wù)可被搶占。Dertouzos在1974年證明了EDF算法的最優(yōu)性[4]。EDF算法的復(fù)雜度要根據(jù)就緒隊(duì)列的數(shù)據(jù)結(jié)構(gòu)來計(jì)算：如果就緒隊(duì)列用列表來實(shí)現(xiàn)，則每個(gè)任務(wù)的復(fù)雜度是[O（n）]；若就緒隊(duì)列使用堆來實(shí)現(xiàn)，則每個(gè)任務(wù)的算法復(fù)雜度是[O（nlogn）]。

2.3 不可搶占的調(diào)度

在不允許搶占的、有任意到達(dá)時(shí)間的任務(wù)集進(jìn)行調(diào)度時(shí)，最小化最大延遲以及找到一個(gè)可行調(diào)度算法是NP難解的。在這種情況下，EDF算法不再是最優(yōu)算法，而且就算存在可行的調(diào)度，也不可能由EDF算法來生成。但是Martel 證明了在不允許空閑的算法（non-idle algorithm，即當(dāng)系統(tǒng)中存在活動的任務(wù)時(shí)就不允許處理器空閑 ）前提下，EDF算法對于非搶占的任務(wù)模型是最優(yōu)的[5]。

若任務(wù)到達(dá)時(shí)間是已知的，則非搶占的調(diào)度可用分支限界法來解決，但這種算法只在平均計(jì)算時(shí)間上較優(yōu)，而在最壞情況下則為指數(shù)復(fù)雜度。Bratley等人[6]給出了一個(gè)建議的算法，能在非搶占，任意到達(dá)的任務(wù)集上找到一個(gè)可行的調(diào)度算法。但前提是必須知道所有的任務(wù)參數(shù)，包括到達(dá)時(shí)間。

2.4 帶優(yōu)先約束的調(diào)度

對存在優(yōu)先約束關(guān)系的，同一時(shí)間到達(dá)的任務(wù)集，尋找一個(gè)最優(yōu)的調(diào)度算法通常是NP難解的。但是對任務(wù)做了一定的假設(shè)之后，可以找出在多項(xiàng)式時(shí)間內(nèi)解決問題的最優(yōu)算法。例如最遲期限算法和帶優(yōu)先約束的EDF算法。

2.4.1 最遲期限算法（Latest Deadline First）

LDF是Lawler在1973年發(fā)明的算法[7]，其任務(wù)模型是任務(wù)在相同時(shí)間到達(dá)，且任務(wù)之間存在優(yōu)先約束。其思路是將所有任務(wù)的優(yōu)先約束關(guān)系用有向無環(huán)圖（DAG）來表示，用尾插隊(duì)列來對任務(wù)排序。從圖中的葉子節(jié)點(diǎn)（即沒有后繼的節(jié)點(diǎn)或者其后繼都已經(jīng)被選擇了的節(jié)點(diǎn)）開始搜索，尋找完成期限最遲的任務(wù)放入隊(duì)尾。這個(gè)過程一直重復(fù)到所有的任務(wù)節(jié)點(diǎn)都被放入隊(duì)列。在運(yùn)行時(shí)，任務(wù)被從隊(duì)頭取出執(zhí)行，這樣就能保證最早放入隊(duì)列的任務(wù)最后被執(zhí)行。在同樣的優(yōu)先約束條件下，使用EDF算法所得到的最大任務(wù)延遲大于使用LDF算法得到的最大任務(wù)延遲。

2.4.2 帶優(yōu)先約束的EDF算法

只有在任務(wù)是可搶占的情況下，對帶有優(yōu)先約束關(guān)系且動態(tài)變化的任務(wù)設(shè)計(jì)多項(xiàng)式時(shí)間復(fù)雜度的算法才是可能的。1990年，Chetto，Silly，和Bouchentouf設(shè)計(jì)了一個(gè)算法解決了這個(gè)問題[8]。其基本思路是將帶有優(yōu)先約束的原始任務(wù)集的任務(wù)的時(shí)間參數(shù)進(jìn)行適當(dāng)?shù)男薷模惯@些任務(wù)變成相互獨(dú)立的任務(wù)，然后對這些任務(wù)使用EDF算法。從原始任務(wù)集到新任務(wù)集的轉(zhuǎn)換算法能夠保證在遵循原始任務(wù)集的優(yōu)先約束關(guān)系的基礎(chǔ)上，新的任務(wù)集與原始任務(wù)集在可調(diào)度性上保持一致性。一般來說是對任務(wù)到達(dá)時(shí)間和任務(wù)完成期限進(jìn)行修改，以保證每個(gè)任務(wù)都不可能在它的前驅(qū)之前執(zhí)行，并且不可能搶占它的后繼任務(wù)。

2.5 非周期性任務(wù)調(diào)度總結(jié)

各種非周期性調(diào)度算法的算法復(fù)雜度及約束條件如圖1所示，EDD算法的約束條件最少，所有任務(wù)在同一時(shí)間到達(dá)，且相互獨(dú)立，其任務(wù)調(diào)度算法的設(shè)計(jì)就相對簡單。如果任務(wù)到達(dá)時(shí)間是不同的，則無法采用靜態(tài)調(diào)度，只能在運(yùn)行時(shí)進(jìn)行調(diào)度，EDF算法就是典型的動態(tài)調(diào)度算法。不可搶占的任務(wù)集的調(diào)度算法設(shè)計(jì)要比可搶占的任務(wù)集難度大，同時(shí)設(shè)計(jì)出的調(diào)度算法復(fù)雜度也高于前者。任務(wù)間的優(yōu)先約束關(guān)系給任務(wù)調(diào)度算法的設(shè)計(jì)帶來更大的難度，對于同時(shí)到達(dá)的任務(wù)，可使用LDF算法，而對于不同時(shí)間到達(dá)的任務(wù)，使用帶約束的EDF算法也能達(dá)到同樣的算法復(fù)雜度。

[＼&sync ，activation＼&preemptive

async ，activation＼&non- preemptive

async ，activation＼&

Independent＼&EDD（Jackson55）

[O（nlogn）]

Optimal＼&EDF（Horn74）

[O（n2）]

Optimal＼&Tree search

（Bratley71）

[O（nn?。

Optimal ＼&

Precedence

constraints＼&LDF（Lawler73）

[O（n2）]

Optimal＼&EDF*

（Chetto et al.90）

[O（n2）]

Optimal＼&Spring

（Stankovic&Ramamritham87）

[O（n2）]

Heuristic＼&]

圖1 Scheduling algorithms for aperiodic tasks.

3 周期性任務(wù)的優(yōu)先級驅(qū)動調(diào)度

周期性任務(wù)是實(shí)時(shí)系統(tǒng)中最重要同時(shí)也是最常用的任務(wù)類型，常用于周期性的采集傳感器數(shù)據(jù)，反饋控制以及系統(tǒng)監(jiān)控等功能的完成。經(jīng)典的周期性任務(wù)調(diào)度算法有速率單調(diào)算法（RM算法）和最早期限優(yōu)先算法（EDF算法）。

3.1單調(diào)速率算法（Rate Monotonic）

RM算法使用了一個(gè)簡單的規(guī)則來安排任務(wù)的優(yōu)先級：讓使用頻率高的任務(wù)具有更高的優(yōu)先級，即周期越短的任務(wù)的優(yōu)先級就越高。由于任務(wù)的周期是一個(gè)常量，因此RM算法是一個(gè)固定優(yōu)先級的算法：任務(wù)的優(yōu)先級在執(zhí)行之前就被分配，并且在執(zhí)行期間不會改變。RM算法本質(zhì)上是可搶占的：當(dāng)前執(zhí)行的任務(wù)會被新來的周期更短的任務(wù)所搶占。

1973年，Liu和Layland[9]明了RM算法在所有的固定優(yōu)先級調(diào)度算法中是最優(yōu)的，并且證明了如果一個(gè)任務(wù)集不能用RM算法調(diào)度，則必定不能用其它的固定優(yōu)先級算法調(diào)度。

對于RM算法的可調(diào)度性判定，Liu和Layland給出了一個(gè)充分條件，即CPU利用率最小上界。隨后，Burchard，Bini等人相繼提出了改進(jìn)的CPU最小上界[10]。然而這些最小上界算法都是在最壞情況下考察可調(diào)度性，是悲觀的考察方法。1997年Han和Tyan提出了時(shí)間復(fù)雜度為多項(xiàng)式的SR算法和DCT算法[11]，這兩種算法基于可調(diào)度的充分但不必要條件，其時(shí)間復(fù)雜度比最小上界算法差，但比確切算法好；使用范圍比最小上界法廣，但不如確切算法。

3.2 EDF算法

最早期限優(yōu)先算法選擇絕對完成期限最早的任務(wù)優(yōu)先執(zhí)行，因此它是一個(gè)動態(tài)調(diào)度算法，并且執(zhí)行在可搶占的模式下。即在當(dāng)前任務(wù)執(zhí)行期間，只要有一個(gè)具有更早的期限的任務(wù)被激活，則當(dāng)前任務(wù)會被搶占。由于EDF算法沒有對任務(wù)的周期性作出任何假設(shè)，所以它既可以用于非周期性任務(wù)調(diào)度，也可以用于周期性任務(wù)調(diào)度?；谕瑯拥脑?，EDF算法的最優(yōu)性也適用于周期性任務(wù)。

3.3 RM算法與EDF算法的比較

對相互獨(dú)立的任務(wù)所構(gòu)成的可搶占的周期性任務(wù)集，固定優(yōu)先級調(diào)度和動態(tài)優(yōu)先級調(diào)度都能夠產(chǎn)生其解決方案。固定優(yōu)先級算法的優(yōu)點(diǎn)在于其實(shí)現(xiàn)上的簡單性，而動態(tài)優(yōu)先級算法則比較適用于任務(wù)量較大的系統(tǒng)或者處理器速度較慢的系統(tǒng)；從可調(diào)度性分析的角度來看，對于簡單的相互獨(dú)立的且任務(wù)期限等于任務(wù)周期的任務(wù)集合。在更一般的情況下，如任務(wù)期限小于等于任務(wù)周期，兩種算法的復(fù)雜度都是多項(xiàng)式時(shí)間。在固定優(yōu)先級算法情況下，任務(wù)集的可行性可以使用響應(yīng)時(shí)間來進(jìn)行分析，而對于動態(tài)優(yōu)先級調(diào)度則可以使用處理器需求標(biāo)準(zhǔn)。從處理器利用率來說，EDF可以最大的利用處理器的帶寬，而RM算法的調(diào)度在最壞情況下只能保證小于69%的利用率。在平均情況下，Lehoczky， Sha和Ding[12]所做的研究證明了對于隨機(jī)產(chǎn)生參數(shù)的任務(wù)集，RM算法能夠達(dá)到88%的處理器利用率。

4 多處理器調(diào)度

多處理器系統(tǒng)已經(jīng)成為處理復(fù)雜實(shí)時(shí)系統(tǒng)應(yīng)用的有效手段，實(shí)時(shí)多處理器系統(tǒng)的調(diào)度算法已經(jīng)成為一個(gè)重要研究課題。對于多處理器系統(tǒng)來說，單處理器系統(tǒng)中的任務(wù)模型并沒有變化，還是可以分為周期性任務(wù)和非周期性任務(wù)。多處理器系統(tǒng)調(diào)度的主要障礙就是其任務(wù)調(diào)度算法要比單處理器系統(tǒng)復(fù)雜，因?yàn)樵诙嗵幚砥飨到y(tǒng)中設(shè)計(jì)調(diào)度算法不僅要對任務(wù)集調(diào)度排序，還需要確定哪些任務(wù)需要使用哪些處理器進(jìn)行調(diào)度。文獻(xiàn)[13]指出基于多處理器的調(diào)度問題主要是確定任務(wù)在哪個(gè)處理器上執(zhí)行，以及何時(shí)執(zhí)行的問題。對于大型周期性的固定優(yōu)先級任務(wù)集在多處理器上的可搶占調(diào)度問題認(rèn)為是NP困難的。因此，需要采用啟發(fā)式方法解決此類問題。對于周期性任務(wù)來說，其各項(xiàng)參數(shù)（到達(dá)時(shí)刻，計(jì)算時(shí)間、截止期限）具有一定的規(guī)律性，因此可以利用單處理器可調(diào)度的充分必要條件對多處理器系統(tǒng)中的周期性任務(wù)進(jìn)行調(diào)度。而對于動態(tài)到達(dá)的非周期性任務(wù)，只能在運(yùn)行時(shí)決定其處理器分配及調(diào)度策略。多處理器系統(tǒng)的調(diào)度機(jī)制一般可分為兩種類型：分組調(diào)度和全局調(diào)度。

4.1多處理器系統(tǒng)分組調(diào)度

多處理器分組調(diào)度方案是指系統(tǒng)中的全部任務(wù)由任務(wù)分配算法預(yù)先劃分到處理器，每一個(gè)處理器可以運(yùn)行不同或者相同的單處理器調(diào)度算法，一個(gè)任務(wù)的所有出現(xiàn)都在同一個(gè)處理器上執(zhí)行，即不允許任務(wù)在多個(gè)處理器上遷移。分組調(diào)度方案主要用于任務(wù)集參數(shù)已知的靜態(tài)優(yōu)先級調(diào)度，對任務(wù)集進(jìn)行脫機(jī)分配。分組調(diào)度方案的性能由兩個(gè)因素決定：給處理器分配任務(wù)的任務(wù)分配算法和每個(gè)處理器上決定任務(wù)執(zhí)行順序的任務(wù)調(diào)度算法。對于已分配到每個(gè)處理器上的任務(wù)來說，其可調(diào)度性判定及利用率可使用單處理器下的方法來進(jìn)行研究。因此對于固定優(yōu)先級的多處理器分組調(diào)度方案來說，核心問題就是任務(wù)分配算法的設(shè)計(jì)。這個(gè)問題是經(jīng)典組合優(yōu)化理論中的裝箱問題的變體，即將[N]種尺寸已知的物品裝入容量已知的[k]個(gè)箱子里。由于裝箱前已經(jīng)獲得所有物品的信息，所以可以先按照物品的某個(gè)屬性排序，按照某種策略裝入某個(gè)箱子?；谝阎獥l件的裝箱策略有下次適合（Next-Fit，NF）算法，最先適合（First-Fit，F(xiàn)F）算法，及任意適合（Any-Fit，AF）算法?；谘b箱問題的NF算法和FF分組方法，文獻(xiàn)[14]提出了兩種多處理器周期性任務(wù)分配算法RMNF和RMFF，這兩種算法的復(fù)雜度都為[O（nlogn）]。

分組調(diào)度策略的缺點(diǎn)在于：首先，任務(wù)集的特性必須是已知的，而對于很多實(shí)時(shí)應(yīng)用來說這是不可能的；其次，任務(wù)分配算法復(fù)雜度高；最后，會出現(xiàn)某個(gè)處理器空閑而另一個(gè)處理器的任務(wù)來不及處理的情況，造成低的資源利用率。

4.2多處理系統(tǒng)全局調(diào)度

全局調(diào)度策略是指實(shí)時(shí)任務(wù)的每一次出現(xiàn)都在不同的處理器上執(zhí)行，所有處理器上只運(yùn)行同一種調(diào)度算法。任務(wù)在未執(zhí)行完之前可以被搶占并且可以在不同的處理器間遷移，同時(shí)假定多處理器間共享內(nèi)存的開銷非常低，這種方案的主要目標(biāo)是為多處理器系統(tǒng)產(chǎn)生一個(gè)能夠滿足它們各自期限的任務(wù)分配。

對于變化復(fù)雜的動態(tài)系統(tǒng)，采用全局調(diào)度是一個(gè)更好的選擇。這種方式下，待處理任務(wù)被放入一個(gè)全局的隊(duì)列，被調(diào)度器取出并分配給可用的處理器執(zhí)行。這種方式在本質(zhì)上保證了處理器的負(fù)載均衡，并且只要隊(duì)列中存在就緒任務(wù)，就不會有處理器空閑狀態(tài)。

5 總結(jié)與展望

實(shí)時(shí)系統(tǒng)的調(diào)度理論一直是實(shí)時(shí)系統(tǒng)的核心研究課題。對實(shí)時(shí)系統(tǒng)的理論研究集中在如何提高資源利用率，如何設(shè)計(jì)好的調(diào)度算法，如何進(jìn)行可調(diào)度性分析。適用于單處理器調(diào)度的某些經(jīng)典調(diào)度算法，如RM算法，EDF算法等也被運(yùn)用于多處理器調(diào)度。但多處理器調(diào)度并不是單處理器調(diào)度算法的簡單擴(kuò)充。對于動態(tài)到達(dá)的偶發(fā)任務(wù)的調(diào)度，需要使用各種啟發(fā)式的方法來設(shè)計(jì)近似最優(yōu)的調(diào)度算法。本文討論了幾個(gè)典型的、經(jīng)典的單處理器調(diào)度算法，并對多處理器調(diào)度進(jìn)行了介紹。認(rèn)為多處理器的調(diào)度算法設(shè)計(jì)以及可調(diào)度性分析方面雖然已經(jīng)有眾多的研究，但也還存在很多未解決的問題。因此多處理器調(diào)度是當(dāng)前實(shí)時(shí)系統(tǒng)調(diào)度的研究熱點(diǎn)。

參考文獻(xiàn)：

[1] Stankovic J A. Misconceptions about real-time computing[J]. IEEE Computer， 1988，21（10）.

[2] Jane W S.實(shí)時(shí)系統(tǒng)[M]. 姬孟洛，李軍，譯.北京：高等教育出版社， 2003：12 .

[3] Jackson J R. Scheduling a production line to minimize maximum tardiness[C]. Management Science Research Project 43， University of California， Los Angeles， USA， 1955.

[4] Dertouzos M L. Control robotics： the procedural control of physical processes. Information Processing， 1974：74.

[5] Bini G， Buttazzo C， Buttazzo G. A hyperbolic bound for the rat e monotonic algorithm[C]// IEEE Proc. 13th Euromicro Conf. Real Time Systems. Oakland： IEEE Computer Society Press， 2011 ：59–68.

[6] Bratley P， Florian M， obillard P R. Scheduling with earliest start and due date constraints. Naval Research Quarterly， 1971， 18（4）.

[7] Lawler E L. Optimal sequencing of a single machine subject to precedence constraints[J]. Managements Science， 1973， 19.

[8] Chetto H， Silly M， Bouchentouf T. Dynamic scheduling of real–time tasks under precedence constraints[J]. Journal of Real–Time Systems， February， 1990.

[9] Liu C L， Layland J W.eduling algorithms for multiprogramming in a hard–real–time environment[J]. Journal of the Association for Computing Machinery， 1973， 20（1）.

[10] Burchard A， Liebeherr J，Oh Y， et al. New strategies f or assigning real time t asks to multiprocessor systems[J]. IEEE Trans. Computers， 1995， 44（12） ： 1429–1442.

[11] Han C C， Tyan H Y. A better polynomial time schedulability test for real time fixed– priority scheduling algorithm .In： Proc[C].18th IEEE Real Time Systems Symposium. Oakland： IEEE Computer Society Press， 1997：36–45.

[12] Lehoczky J P， Sha L， Ding Y. The rate monotonic scheduling algorithm： Exact characterization and average case behavior [C]// Proc. 10th IEEE Real Time Systems Symposium. Oakland： IEEE Computer Society Press， 1989：166–171.

[13] Ramamritham K. Scheduling algorithms and operating systems support for Real Time Systems[C]. Proceeding of IEEE， 1994，82（1）：55–67.

[14] Dhall S K， Liu C L. On a real–time scheduling problem[J].Operations Research， 1978， 26（l）：127–140.