多特征協(xié)調(diào)的實(shí)時(shí)調(diào)度算法

滿 立，朱瑞龍

(1.紅塔遼寧煙草有限責(zé)任公司營(yíng)口卷煙廠，遼寧 營(yíng)口 115002;2.中國(guó)科學(xué)院沈陽(yáng)自動(dòng)化研究所，遼寧 沈陽(yáng) 110016)

0 引言

實(shí)時(shí)調(diào)度算法作為目前的一個(gè)研究熱點(diǎn)，已經(jīng)廣泛地應(yīng)用到各個(gè)領(lǐng)域，同時(shí)也取得了很多研究成果。根據(jù)調(diào)度對(duì)象的時(shí)間規(guī)律，可以分為周期性調(diào)度和非周期性調(diào)度;根據(jù)任務(wù)截止時(shí)間的要求，可以分為硬實(shí)時(shí)調(diào)度和軟實(shí)時(shí)調(diào)度;根據(jù)任務(wù)的優(yōu)先分配方法，可以分為靜態(tài)優(yōu)先級(jí)調(diào)度、動(dòng)態(tài)優(yōu)先級(jí)調(diào)度和混合優(yōu)先級(jí)調(diào)度。其中比較典型的是靜態(tài)優(yōu)先級(jí)調(diào)度算法中的RM 調(diào)度算法(Rate-Monotonic Scheduling)［1］和動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法中的EDF(Earliest Deadline First)調(diào)度算法［2］，它們都是最優(yōu)調(diào)度算法，并且具有很高的應(yīng)用價(jià)值。RM 調(diào)度算法根據(jù)任務(wù)執(zhí)行的周期決定調(diào)度的優(yōu)先級(jí)，執(zhí)行周期小的任務(wù)分配給較高的優(yōu)先級(jí)。為了提高RM 調(diào)度算法的處理器利用率，人們繼續(xù)對(duì)其進(jìn)行研究，提出了一些改進(jìn)算法，例如DM 調(diào)度算法［3］。DM 調(diào)度算法假設(shè)所有任務(wù)具有確定的截止期和周期，而且截止期不大于周期，任務(wù)按照截止期確定優(yōu)先級(jí)，截止期越小，優(yōu)先級(jí)越高。當(dāng)截止期等于周期，則DM 調(diào)度算法退化為RM 調(diào)度算法。EDF 調(diào)度算法對(duì)隊(duì)列中的任務(wù)優(yōu)先級(jí)進(jìn)行比較，優(yōu)先級(jí)最高的任務(wù)獲得資源進(jìn)行處理，距離截止期最近的任務(wù)被分配最高優(yōu)先級(jí)，具有較小的調(diào)度開(kāi)銷。作為最優(yōu)的動(dòng)態(tài)調(diào)度算法，也有很多人展開(kāi)了更深入的研究，為了提高它的性能。例如LST(Least Slack Time)調(diào)度算法［4］，它計(jì)算松弛時(shí)間，就是當(dāng)前時(shí)刻距離截止期的時(shí)間與任務(wù)執(zhí)行時(shí)間之差，并按照時(shí)間的大小排序，最短時(shí)間具有最高優(yōu)先級(jí)。這種調(diào)度算法被證明也是最優(yōu)動(dòng)態(tài)優(yōu)先級(jí)算法。但是EDF調(diào)度算法存在一個(gè)嚴(yán)重缺陷，一個(gè)錯(cuò)過(guò)時(shí)限的遲到作業(yè)具有比時(shí)限未到的作業(yè)更高的優(yōu)先級(jí)。所以，當(dāng)系統(tǒng)處于超載狀態(tài)時(shí)，EDF 調(diào)度算法的性能將出現(xiàn)明顯的下滑。針對(duì)這一問(wèn)題，Jensen 等提出了HVF(Highest Value First)調(diào)度算法［5］，將最高優(yōu)先級(jí)分配給價(jià)值最高的任務(wù)，面對(duì)系統(tǒng)超載時(shí)，相對(duì)EDF 調(diào)度算法有更好表現(xiàn)。在此基礎(chǔ)上，HVDF(Highest Value Density First)調(diào)度算法也被提出［6］，在系統(tǒng)超載時(shí)它的性能好于HVF 調(diào)度算法。但是HVDF 調(diào)度算法是一種貪婪算法，在系統(tǒng)沒(méi)有超載時(shí)，系統(tǒng)消耗較大，容易導(dǎo)致任務(wù)錯(cuò)過(guò)截止期，調(diào)度性差。

在對(duì)生產(chǎn)過(guò)程進(jìn)行控制的實(shí)時(shí)系統(tǒng)中，需要處理各種類型的任務(wù)，其中報(bào)警類事件和某些周期性事件需要具有較高的優(yōu)先級(jí)，并且不被其他的任務(wù)搶占。這類調(diào)度對(duì)象具有混合特性，在設(shè)計(jì)調(diào)度算法時(shí)需要綜合考慮多方因素的影響［7-14］。現(xiàn)有的實(shí)時(shí)調(diào)度算法并不能完全滿足系統(tǒng)調(diào)度的需要，所以本文提出一種基于多特征協(xié)調(diào)(Multi-Feature Synthesis，MFS)的實(shí)時(shí)調(diào)度算法，來(lái)解決目前存在的問(wèn)題。

1 調(diào)度策略

多特征協(xié)調(diào)的實(shí)時(shí)調(diào)度算法主要針對(duì)實(shí)際生產(chǎn)中對(duì)生產(chǎn)過(guò)程控制過(guò)程中所產(chǎn)生的任務(wù)，所以它的調(diào)度對(duì)象與一般的實(shí)時(shí)調(diào)度算法并不一樣，具有自己的特點(diǎn)。在生產(chǎn)過(guò)程中產(chǎn)生的事件處理任務(wù)并不會(huì)因?yàn)殄e(cuò)過(guò)截止期而對(duì)系統(tǒng)的性能產(chǎn)生較大影響，但是有一類事件除外，那就是報(bào)警事件。如果在生產(chǎn)過(guò)程中出現(xiàn)了報(bào)警事件，那就必須在盡量短的時(shí)間內(nèi)進(jìn)行處理，所以這一類事件應(yīng)該賦予固定的最高優(yōu)先級(jí)，排在任務(wù)隊(duì)列的最前端優(yōu)先處理［15］。

多特征協(xié)調(diào)的實(shí)時(shí)調(diào)度算法的目標(biāo)是在調(diào)度任務(wù)時(shí)滿足固定最高優(yōu)先級(jí)的任務(wù)能夠隨時(shí)被調(diào)度，而且不影響其他任務(wù)得的調(diào)度效率。其中固定最高優(yōu)先級(jí)的任務(wù)是一類特殊任務(wù)，是需要盡快被處理的任務(wù)，且越快越好。剩余的任務(wù)綜合考慮任務(wù)的相對(duì)截止期和系統(tǒng)的負(fù)載情況后，確定優(yōu)先級(jí)并進(jìn)行調(diào)度。

2 多特征協(xié)調(diào)調(diào)度算法

多特征協(xié)調(diào)，主要體現(xiàn)在調(diào)度對(duì)象特征復(fù)雜上。因?yàn)樵趯?shí)際生產(chǎn)過(guò)程中，調(diào)度的對(duì)象是生產(chǎn)過(guò)程事件，具有不確定性，以及實(shí)時(shí)性非實(shí)時(shí)性要求共存。任務(wù)屬性具有多種特征，并且需要協(xié)調(diào)不同實(shí)時(shí)性要求和優(yōu)先級(jí)要求。例如，加工工序完成時(shí)生成的事件，需要與其他沒(méi)有實(shí)時(shí)性要求的事件一同被調(diào)度，當(dāng)出現(xiàn)報(bào)警事件這類具有實(shí)時(shí)性要求的事件時(shí)，需要讓出資源，使報(bào)警事件優(yōu)先處理。這個(gè)過(guò)程體現(xiàn)了調(diào)度任務(wù)具有的多特征這一特性，同時(shí)需要協(xié)調(diào)其處理順序。協(xié)調(diào)不同任務(wù)之間的調(diào)度順序，制定調(diào)度策略是本算法需要解決的主要問(wèn)題。

2.1 任務(wù)建模

針對(duì)生產(chǎn)過(guò)程中的任務(wù)調(diào)度處理問(wèn)題，假設(shè)系統(tǒng)中存在N 個(gè)獨(dú)立的任務(wù)T 組成的任務(wù)集TA，TA={T1，T2，T3，…，Tn}，其中任務(wù)集中的任務(wù)同時(shí)存在周期任務(wù)和非周期任務(wù)。每一個(gè)任務(wù)都由一個(gè)五元組Ti(ai，di，wi，hi，ui)構(gòu)成。ai為任務(wù)已經(jīng)等待時(shí)間，di為任務(wù)距離截止期的時(shí)間，wi為任務(wù)執(zhí)行需要的時(shí)間，hi為任務(wù)的價(jià)值系數(shù)，ui為任務(wù)綜合優(yōu)先級(jí)。(di-wi)為任務(wù)松弛時(shí)間。如果di＜wi，則任務(wù)沒(méi)有足夠的剩余時(shí)間完成，任務(wù)失敗。

為了便于確定調(diào)度算法的調(diào)度對(duì)象和范圍，作出如下假設(shè):

1)任務(wù)是獨(dú)立的，不因?yàn)橘Y源共享而阻塞，也不會(huì)自動(dòng)掛起;

2)任務(wù)之間可以搶占，并且搶占的代價(jià)可以忽略;

3)任務(wù)為隨機(jī)生成的非周期任務(wù);

4)處理器只響應(yīng)任務(wù)調(diào)度請(qǐng)求。

2.2 算法設(shè)計(jì)

多特征協(xié)調(diào)的實(shí)時(shí)調(diào)度算法的設(shè)計(jì)目標(biāo):

1)優(yōu)先保證關(guān)鍵任務(wù)的運(yùn)行;

2)盡量控制截止期錯(cuò)失率DMR。

因?yàn)楸疚脑O(shè)計(jì)的算法面向的是生產(chǎn)過(guò)程事件所生成的調(diào)度任務(wù)，所以不同類型任務(wù)的實(shí)時(shí)性要求已經(jīng)被確定下來(lái)，已經(jīng)被分為關(guān)鍵任務(wù)和非關(guān)鍵任務(wù)。如生產(chǎn)過(guò)程中的開(kāi)工完工事件就是非關(guān)鍵任務(wù)，即使被延遲一段時(shí)間處理也不會(huì)有問(wèn)題，但是報(bào)警事件就需要被即時(shí)處理，具有實(shí)時(shí)性要求，保證生產(chǎn)的安全。

本算法的調(diào)度體系框架如圖1 所示。

圖1 多特征協(xié)調(diào)算法的調(diào)度體系框架

多特征協(xié)調(diào)調(diào)度算法的調(diào)度規(guī)則如下:

1)任務(wù)到達(dá)后首先進(jìn)行判斷，如果為關(guān)鍵任務(wù)隊(duì)列，則進(jìn)入關(guān)鍵任務(wù)隊(duì)列H，否則進(jìn)入非關(guān)鍵任務(wù)隊(duì)列L;

2)調(diào)度時(shí)首先判斷關(guān)鍵任務(wù)隊(duì)列H 是否為空，如果非空，對(duì)H 中按照FIFO(First In First Out)規(guī)則調(diào)度;如果為空，則選擇非關(guān)鍵任務(wù)隊(duì)列L 中優(yōu)先級(jí)最高的任務(wù)進(jìn)行處理;

3)在對(duì)非關(guān)鍵任務(wù)隊(duì)列L 中的任務(wù)進(jìn)行調(diào)度時(shí)，監(jiān)控負(fù)載情況，并根據(jù)結(jié)果調(diào)整調(diào)度算法。

2.3 調(diào)度策略的選擇和設(shè)計(jì)

在進(jìn)行調(diào)度時(shí)，負(fù)載監(jiān)視器對(duì)非關(guān)鍵任務(wù)隊(duì)列L中的隊(duì)列進(jìn)行監(jiān)控，并將結(jié)果傳給調(diào)度策略選擇器，對(duì)調(diào)度策略進(jìn)行簡(jiǎn)單調(diào)整。定義監(jiān)視器返回結(jié)果為K，K 的值為:

假設(shè)非關(guān)鍵任務(wù)Ti按照EDF 算法調(diào)度時(shí)的優(yōu)先級(jí)系數(shù)為ei，按照HVF 算法調(diào)度時(shí)的價(jià)值系數(shù)為hi，則Ti在隊(duì)列L 中的優(yōu)先級(jí)系數(shù)ui為，

K 作為一個(gè)平衡因子，當(dāng)系統(tǒng)負(fù)載沒(méi)有達(dá)到超載時(shí)，K=1，則ui=ei;若系統(tǒng)負(fù)載達(dá)到超載，則K=0，ui=hi。因?yàn)镋DF 調(diào)度算法在系統(tǒng)超載時(shí)性能下降太快，而在這種情況下HVF 算法的性能優(yōu)于EDF 算法，所以，綜合2 種算法的優(yōu)點(diǎn)，可以較好地提高系統(tǒng)處理效率。

算法的調(diào)度策略選擇規(guī)則如下:

1)通過(guò)監(jiān)視器判斷非關(guān)鍵任務(wù)隊(duì)列L 是否超載，如果超載跳至2)執(zhí)行，否則跳至3);

2)按照EDF 算法計(jì)算隊(duì)列L 中任務(wù)的優(yōu)先級(jí);

3)按照HVF 算法計(jì)算隊(duì)列L 中的任務(wù)優(yōu)先級(jí);

4)按照優(yōu)先級(jí)排序執(zhí)行任務(wù)。

3 算法驗(yàn)證和比較

Cheddar 是一個(gè)免費(fèi)實(shí)時(shí)調(diào)度仿真軟件，用來(lái)查看實(shí)時(shí)系統(tǒng)任務(wù)的時(shí)限。所分析的系統(tǒng)可以用AADL(Architecture Analysis and Design Language，一種基于模型工程的語(yǔ)言標(biāo)準(zhǔn))或?yàn)镃heddar 專門的語(yǔ)言描述［16］。該軟件可以快速為實(shí)時(shí)調(diào)度建模。本文采用實(shí)時(shí)調(diào)度仿真工具Cheddar 進(jìn)行仿真實(shí)驗(yàn)，其中Task1 任務(wù)為需要優(yōu)先處理的關(guān)鍵任務(wù)，在測(cè)試結(jié)果中，如圖2 所示，即使其他任務(wù)出現(xiàn)延期，Task1 的任務(wù)也被保證執(zhí)行，實(shí)現(xiàn)了本算法設(shè)計(jì)的目的。對(duì)比測(cè)試中，Task1 為非關(guān)鍵隊(duì)列。通過(guò)對(duì)比可以得出結(jié)論，關(guān)鍵隊(duì)列的調(diào)度對(duì)其他隊(duì)列沒(méi)有明顯影響。

圖2 仿真測(cè)試結(jié)果

圖3 截止期錯(cuò)失率的對(duì)比

在保證關(guān)鍵任務(wù)執(zhí)行的情況下，也要保證非關(guān)鍵任務(wù)的執(zhí)行。對(duì)此筆者也進(jìn)行了仿真測(cè)試。

在保證了關(guān)鍵任務(wù)不會(huì)對(duì)搶占資源，對(duì)其余任務(wù)的執(zhí)行造成影響后，還需要測(cè)試算法的性能，這一點(diǎn)主要從截止期錯(cuò)失率(MDP，Missed Deadline Percentage)來(lái)考慮［17］。MDP 越低，能夠得到及時(shí)響應(yīng)的任務(wù)和操作就越多，主要對(duì)比EDF 算法、HVF 算法和MFS 算法，如圖3 所示。

圖3 中的縱坐標(biāo)為截止期錯(cuò)失率MDP，橫坐標(biāo)為系統(tǒng)負(fù)載。從圖中可以看出，MFS 算法在系統(tǒng)沒(méi)有超載時(shí)，同EDF 有幾乎一樣的性能，顯示出最優(yōu)性;當(dāng)系統(tǒng)超載時(shí)，具有比EDF 算法更低的MDP，很好地避免了EDF 算法的多米諾效應(yīng)，性能有明顯提高。

實(shí)現(xiàn)價(jià)值率HVR 是指調(diào)度算法調(diào)度執(zhí)行任務(wù)滿足截止期所實(shí)現(xiàn)的積累價(jià)值與所有提交任務(wù)價(jià)值總和的比率［18］:

圖4 給出EDF、HVF 和MFS 算法的HVR 在不同負(fù)載情況下的變化。其中橫坐標(biāo)是負(fù)載，縱坐標(biāo)是HVR 的值。

圖4 HVR 的對(duì)比

4 結(jié)束語(yǔ)

生產(chǎn)過(guò)程管理中的事件處理系統(tǒng)不同于一般的實(shí)時(shí)任務(wù)使系統(tǒng)，具有軟實(shí)時(shí)的特性，現(xiàn)有的實(shí)時(shí)操作系統(tǒng)的調(diào)度算法不能直接使用。本文通過(guò)對(duì)實(shí)時(shí)調(diào)度算法的研究，提出了一種多特征綜合的實(shí)時(shí)調(diào)度算法，并且進(jìn)行了測(cè)試和比較。通過(guò)實(shí)驗(yàn)結(jié)果的對(duì)比，本算法很好地實(shí)現(xiàn)了設(shè)計(jì)的初衷，關(guān)鍵任務(wù)沒(méi)有搶占過(guò)多的系統(tǒng)資源，對(duì)其余任務(wù)沒(méi)有影響，具有應(yīng)用價(jià)值。

［1］Burchard A，Liebeherr J，Oh Y F，et al.New strategies for assigning real-time tasks to multiprocessor systems［J］.IEEE Transactions on Computers，1995，44(12):1429-1442.

［2］Kieckhafer R M，Walter C J，F(xiàn)inn A M，et al.The MAFT architecture for distributed fault tolerance［J］.IEEE Transactions on Computers，1988，37(4):398-405.

［3］龐麗萍.操作系統(tǒng)原理［M］.第3 版.武漢:華中科技大學(xué)出版社，2000:110-150.

［4］Gopalan K.Real-Time Support in General Purpose Operating Systems［R］.ECSL Technical Report TR92，State University of New York at Stony Brook，2001:63-71.

［5］韓忠華，史海波，劉昶，等.客車生產(chǎn)中可重入倒排產(chǎn)應(yīng)用研究［J］.沈陽(yáng)建筑大學(xué)學(xué)報(bào)(自然科學(xué)版)，2010，26(6):1219-1224.

［6］Isovic D，F(xiàn)ohler G.Efficient scheduling of sporadic，aperiodic，and periodic tasks with complex constraints［C］//Proceedings of the 21st IEEE Real-Time Systems Symposium.Florida，USA，2000:1153-1161.

［7］Liu C L，Layland J W.Scheduling algorithms for multiprogramming in a hard-real-time environment［J］.Journal of ACM，1973，20(1):46-61.

［8］劉懷，費(fèi)樹(shù)岷.基于EDF 的分布式控制系統(tǒng)容錯(cuò)調(diào)度算法［J］.軟件學(xué)報(bào)，2003，14(8):1371-1378.

［9］張擁軍，張怡，彭宇行，等.一種基于多處理機(jī)的容錯(cuò)實(shí)時(shí)任務(wù)調(diào)度算法［J］.計(jì)算機(jī)研究與發(fā)展，2000，37(4):425-429.

［10］Hamdaoui M，Ramanathan P.A dynamic priority assignment technique for streams with (m，k)-firm deadlines［J］.IEEE Transactions on Computers，1995，44(12):1443-1451.

［11］Cen Shanwei，Pu C，Staehli R，et al.A distributed realtime MPEG video audio player［C］// Proceedings of the 5th International Workshop on Network and Operating System Support of Digital Audio and Video.Durham，New Hampshire，USA，1995，1018:142-153.

［12］Yau D K Y，Lam S S.Adaptive rate-controlled scheduling for multimedia applications［J］.IEEE/ACM Transactions on Networking，1997，5(4):475-488.

［13］Nieh J，Lam M S.Integrated processor scheduling for multimedia［C］// Proceedings of the 5th International Workshop on Network and Operating System Support for Digital Audio and Video.1995:215-218.

［14］何軍，孫玉方.提高軟非周期任務(wù)相應(yīng)性能的調(diào)度算法［J］.軟件學(xué)報(bào)，1998，9(10):721-727.

［15］涂剛，陽(yáng)富明，盧炎生.基于動(dòng)態(tài)優(yōu)先級(jí)策略的最優(yōu)軟非周期任務(wù)調(diào)度算法［J］.計(jì)算機(jī)研究與發(fā)展，2004，41(11):2026-2034.

［16］Bernat G，Burns A.Combining (n，m)-hard deadlines with dual priority scheduling［C］// Proceedings of the 18th IEEE Real-Time Systems Symposium.San Francisco USA，1997:46-57.

［17］Guillem Bernat Nicolau.Specification and Analysis of Weakly Hard Real-Time Systems［D］.Universitat de les Illes Balears，Spain，1998.

［18］Damir Isovic.Handling Sporadic Tasks in Real-time Systems-CombinedOffline and Online Approach［D］.Malardalen University，Sweden，2001.