郭鳳釗，郭銳鋒，丁萬夫，，秦承剛，

(1.中國科學院研究生院，北京 100039;2.中國科學院沈陽計算技術研究所高檔數控國家工程研究中心，沈陽 110171)

面向數控系統(tǒng)的反饋調度算法的研究*

郭鳳釗1，郭銳鋒2，丁萬夫1，2，秦承剛1，2

(1.中國科學院研究生院，北京 100039;2.中國科學院沈陽計算技術研究所高檔數控國家工程研究中心，沈陽 110171)

傳統(tǒng)的數控系統(tǒng)使用靜態(tài)的、開環(huán)的任務調度策略，在其運行過程中系統(tǒng)的資源不能被充分地利用。為提高數控系統(tǒng)的資源利用率，論文設計了一種針對軟實時任務的閉環(huán)反饋調度算法。該反饋調度算法通過監(jiān)控當前系統(tǒng)的負載和任務的截止期錯失率，能夠自動調整軟實時任務的時間參數，使系統(tǒng)資源可以被充分利用，并使系統(tǒng)在各種負載的情況下都能獲得較好的性能。通過實驗對該反饋調度算法進行驗證，結果表明，該調度算法能夠顯著提升數控系統(tǒng)的CPU利用率，同時還能保證數控系統(tǒng)的穩(wěn)定性。

數控系統(tǒng);實時系統(tǒng);自適應調度算法;反饋控制

0 引言

隨著開放式數控系統(tǒng)概念的引入，具有自適應性質的實時系統(tǒng)引起人們越來越多的研究。在傳統(tǒng)的調度模型下，系統(tǒng)的可調度性取決于每一個任務(Task)在最壞情況下的執(zhí)行時間(WCET，Worst-Case Execution Time)，使用WCET可以簡化系統(tǒng)的操作，但由于WCET是在最壞情況下的時間需求，故不能充分利用CPU，對系統(tǒng)資源造成比較大的浪費，并且很多實時程序的WCET是無法被準確預知的［1］。

自適應的實時調度算法可以監(jiān)控當前系統(tǒng)的負載情況，動態(tài)地對實時任務進行時間參數的調整，使系統(tǒng)在無需預知任務時間參數的情況下穩(wěn)定的工作。文獻［1］首次提出了基于EDF算法的反饋模型，其中每個實時任務都擁有多個服務級，每一個服務級都代表著不同的服務質量(QoS，Quality of Service)和執(zhí)行時間。算法通過檢測系統(tǒng)的時限錯失率(DMR，Deadline Miss Ratio)和系統(tǒng)負載情況來調整任務的服務級。此反饋模型的缺點是系統(tǒng)無法監(jiān)測某一任務的錯失率是否太大或CPU利用率是否太高。文獻［4］中的反饋模型為每一個實時任務分配了一個反饋控制器，監(jiān)測每一個實時任務的錯失率和CPU利用率，然而該模型忽略了任務各自的重要性是不同的。文獻［2］為實時任務提出一個重要性參數概念，根據重要性的不同，為每個任務分配不同的周期。文獻［2］的缺陷是假定實時任務的執(zhí)行時間是固定的，只對任務周期進行了調節(jié)。

結合數控系統(tǒng)的特點，本文設計了一種針對數控系統(tǒng)中軟實時任務的反饋調度算法。該反饋調度算法根據當前系統(tǒng)的負載情況和各個任務的錯失率來對任務的服務級別進行調整，每個服務級都有相應的執(zhí)行時間和任務周期。在調整時，根據各個任務的重要性大小，依次對它們的服務級進行調整。通過這種動態(tài)地調整，系統(tǒng)資源得到充分地利用，保證系統(tǒng)在各種負載的情況下都能保證其較好的性能。

1 數控系統(tǒng)的調度模型

1.1 傳統(tǒng)數控系統(tǒng)的調度模型

數控系統(tǒng)是一個專用的實時系統(tǒng)。在數控系統(tǒng)中，根據任務對實時性的要求不同，可以把任務分為硬實時任務、軟實時任務和非實時任務。硬實時任務指必須滿足最后截止時刻限制的任務，否則會給系統(tǒng)帶來不可接受的破壞或者致命的錯誤，體現(xiàn)在數控系統(tǒng)中主要是插補計算、采樣控制，軟PLC等。一般對硬實時任務的調度算法都會以滿足其時限(Deadline)為目的。軟實時任務主要包括解釋器任務、文件服務通信任務和監(jiān)測與報警任務。這些任務對實時性的要求不高，偶爾丟失實現(xiàn)并不會對數控的性能造成影響，故可以采用反饋算法對軟實時任務的時間參數進行動態(tài)地調節(jié)。非實時任務包括圖形顯示、參數管理等對實時性沒有要求的任務，此類任務的丟失不會對數控系統(tǒng)的加工質量造成任何影響。

在傳統(tǒng)數控系統(tǒng)中，對于混合任務的調度采用前后臺方法，即系統(tǒng)只有在沒有硬實時任務就緒的情況下，才會執(zhí)行軟實時或非實時任務。這種方法的優(yōu)點是易于實現(xiàn)，但也可能出現(xiàn)問題。例如，在數控系統(tǒng)中，解釋器對G代碼進行解釋，然后把解釋后的數據放入解釋器緩沖區(qū)，使插補器可以從解釋器緩沖區(qū)中取解釋數據。由于共享內存空間有限，如果解釋器錯失率太高，插補任務將可能會產生“數據饑餓”，因等待數據而延緩執(zhí)行，從而影響到加工的質量［7］。

1.2 任務模型的基本定義

根據任務模型的定義，選取模型任務集為偶發(fā)性任務集。偶發(fā)任務的釋放時間是隨機的，但是其相鄰作業(yè)到達的時間間隔大于等于某個最小值，這個最小值被當做偶發(fā)任務集的周期。偶發(fā)任務是強時限的，這一模擬任務類型在如數控系統(tǒng)中具有代表性。

本文使用以下符號對任務模型進行描述:

2 反饋調度模型

2.1 反饋模型設計思想

系統(tǒng)中每一個任務都有多個服務級，每一個服務級都代表一個QoS，擁有自己的周期p(Ti)和執(zhí)行時間e(Ti)，服務級越大代表QoS越好。由p(Ti)和e(Ti)可以確定該服務級的權重，代表該任務名義上對系統(tǒng)利用率的要求［1］。在［1］中，若任務在某一服務級別，系統(tǒng)便使用該服務級的權重作為該任務的估計權重。對于某些實時系統(tǒng)，這樣靜態(tài)地分配估計權重是可行的，但是對于數控系統(tǒng)而言，由于無法事先得知任務的執(zhí)行時間，故預知一個任務的權重是不現(xiàn)實的。本論文采用動態(tài)計算估計權重，而非靜態(tài)分配任務的估計權重的方法。

本文為反饋模型引入了“重要性參數”概念，認為在實時系統(tǒng)中，軟實時任務的“重要性”是不相同的。例如在數控系統(tǒng)中，軟實時任務有解釋器任務、文件服務通信任務以及監(jiān)測與報警任務，通常我們認為解釋器任務比文件服務通信任務和監(jiān)測與報警任務更為重要。

在反饋模型中，所有的任務都可以被加載到系統(tǒng)中，系統(tǒng)監(jiān)測每一個任務的權重和整個系統(tǒng)的負載情況。如果某一任務的估計權重和實際權重相差過大或系統(tǒng)負載過高，則需要對系統(tǒng)進行服務級的調整。在進行調整時，根據它們的重要性參數排序，依次分配每個任務的服務級，給予最重要的任務盡可能高的服務級。模型使用EDF算法，每次調度時選擇最高優(yōu)先級即最早時限的任務進行調度。

反饋模型主要由反饋控制器和優(yōu)化器(Optimizer)構成，反饋控制器根據當前任務實例的實際權重來計算下一個任務實例的估計權重。優(yōu)化器用來給系統(tǒng)中的每個實時任務分配合適的服務級別。反饋模型如圖1所示。

圖1 反饋調度模型

2.2 反饋控制器

實時系統(tǒng)一般而言是非線性時變系統(tǒng)，要對其進行精確的建模是很困難的，但由于閉環(huán)反饋控制具有對變化系統(tǒng)模型的健壯性，所以可以采用線性模型來近似一個實時系統(tǒng)，達到簡化控制設計的目的。

反饋系統(tǒng)由輸入值，輸出值，誤差以及控制器組成，PID(比例-積分-微分)控制器是在工業(yè)控制中運用最廣泛的控制器，它由比例單元(P)、積分單元(I)和微分單元(D)組成。其輸入Error(t)與輸出U(t)的關系為:

其中p，i，d分別為比例參數，積分參數以及微分參數。在很多情況下，并不一定需要全部三個單元，可以取其中的一或兩個單元，但比例控制單元是必不可少的。本文使用比例單元(P)和積分單元(I)，沒有選取微分單元是因為控制器的微分功能不適合控制實時系統(tǒng)，微分單元可能會放大因為CPU和帶寬負載的隨機性而造成的系統(tǒng)噪音。由于本反饋系統(tǒng)是周期采樣的，是離散系統(tǒng)，故輸出Ew()與輸入Error(的關系為:

由于本反饋調度模型的傳遞函數建立在z域內，故可使用離散系統(tǒng)根軌跡方法分析系統(tǒng)的系能。在線性離散系統(tǒng)中，系統(tǒng)的動態(tài)性能如連續(xù)系統(tǒng)一樣主要由閉環(huán)特征多項式的根來決定，系統(tǒng)的穩(wěn)定條件是閉環(huán)特征多項式的根都在z域的單位圓內。由反饋模型的閉環(huán)傳遞函數，畫出其根軌跡并取閉環(huán)極點為p1=0.4613，p2=0.4367。由確定的閉環(huán)極點得到PI控制器的參數p=0.102，q=－1.975。由于所選取的閉環(huán)極點都是處于z平面上的單位圓內，所以此離散系統(tǒng)是穩(wěn)定的。

2.3 優(yōu)化器

每一個任務都有一個用戶定義的重要性參數，代表該任務的重要程度，用L來表示，例如用L(Ti)表示Ti的重要程度。在每一次調用優(yōu)化器的時候，都會根據每個任務的L值對任務進行由大到小的排序，依次給各個任務分配合適的服務級別。

假設系統(tǒng)中有n個任務T1，T2，…，Tn，每個任務都分別有m個服務級，每個服務級對應的估計權重分別為w1，w2，…，wm，設w1＜ w2＜ … ＜ wm。每個任務都有自己的重要性參數，分別為 L(T1)，L(T2)，…，L(Tn)。在調用優(yōu)化器進行調整時，首先把n個任務的服務級置為1(最低)，之后按照L值從大到小對任務進行排序，設依次為Tl1，Tl2，…，Tln。根據這個次序，在不超過系統(tǒng)帶寬上限的情況下，為每個任務分配盡可能大的服務級。

例如，系統(tǒng)中有四個任務 T1，T2，T3，T4.假設每個任務都分別有四個服務級，假設每個服務級對應的估計權重分別為2/5，3/10，1/5，1/10，并且已知L(T1)＞L(T2)＞L(T3)＞T(T4)。調度算法使用EDF算法，系統(tǒng)帶寬上限設為1。在進行調整時，把四個任務的服務級置為1(最低)，此時1/10+1/10+1/10+1/10=2/5＜1。依次嘗試分配各個任務的服務級，對于T1，2/5+1/10+1/10+1/10=7/10 ＜1可以被調度，故可以T1的服務級從1升為4(最高)。然后對T2進行嘗試，2/5+2/5+1/10+1/10=1，可滿足T2的最大的權重，把T2的服務級從最低變?yōu)樽罡?。之后對?T3，2/5+2/5+1/5+1/10=11/10＞1，已經超過了系統(tǒng)最大調度能力，故T3的服務級不能提升。同理可計算出T4的服務級仍為最低值，其權重保持為1/10。

3 實驗研究與分析

3.1 試驗平臺

本文使用了藍天數控系統(tǒng)作為實驗平臺，該系統(tǒng)采用了基于雙內核架構的實時操作系統(tǒng)RTAI(Real-Time Application Interface)。RTAI采用模塊化的方式，作為Linux的模塊插入到內核運行空間，用以實現(xiàn)了Linux內核的實時擴展。為了實現(xiàn)針對軟實時任務的反饋調度器，本文對RTAI的軟實時任務的結構定義及其調度函數進行了修改，在Linux內核空間內實現(xiàn)了一個軟實時調度器，在此基礎上對反饋調度器進行實驗測試。

3.2 實驗方法及參數選定

模型的基本調度策略使用EDF調度算法，該算法使系統(tǒng)的調度上限可達到100%。

試驗參數設置如下，在系統(tǒng)中設定4個軟實時任務，每個任務有4個服務級別，設每個任務最高服務級中的時間參數都為其在數控系統(tǒng)中最大QoS下的執(zhí)行時間和周期。假設服務級別和權重滿足線性關系，隨著服務級的下降，任務的權重隨之變小。線性比例系數由最大QoS下的權重和最小QoS下的權重確定。

假設任務的重要性參數服從［0，1］范圍內的均勻分布，隨機為任務分配其重要性參數。根據3.2節(jié)的分析，置PI控制器參數為p=0.102，q=－1.975。

設定任務估計權重和實際權重之間的最大差值，即Error的上限不超過0.5。如果超過這個值，系統(tǒng)就會調用優(yōu)化器對任務進行新服務級的分配。

通過實驗，本文選擇采樣周期為20μs，在此采樣周期下數控系統(tǒng)具有最好的穩(wěn)態(tài)性能和收斂速度，系統(tǒng)開銷也在可以容忍的范圍內。

3.3 單個任務的權重表現(xiàn)

圖2為其中一個任務在0到20s的時間參數調整的表現(xiàn)。其中Aw為實際權重(ActualWeight)，Ew代表實際權重(EstimateWeight)，Error=Ew－Aw。從粗實線的表現(xiàn)可以看出，在大部分的時間內，Error值都是保持在［－0.2，0.2］之間的。在5.6s的時候，Error值超過其設定上限，系統(tǒng)通過反饋算法對任務的服務級進行調整，降低了該任務的服務級，使Error值迅速恢復到比較小的范圍內。降低此任務的服務級之后，該任務實際權重和估計權重都有了相應的下降。在8.1s時，Error過大再次調整服務級，相應地計算新的估計權重，使Error值再次回到可接受的范圍內。

圖2 單個任務的權重變化

3.4 整個系統(tǒng)的負載情況

根據圖3可以看出，傳統(tǒng)數控系統(tǒng)的調度算法使用任務的WCET來判斷是否可調度，系統(tǒng)的負載在一定時間內穩(wěn)定在0.76附近，雖然可以穩(wěn)定工作，但系統(tǒng)的資源無法得到充分利用;使用反饋調度算法，系統(tǒng)的總負載在1的附近波動，當系統(tǒng)負載超過1之后，反饋模型調用優(yōu)化器迅速調整系統(tǒng)中任務的服務級，使負載下降，保證數控系統(tǒng)不會過載;當系統(tǒng)負載過低時，優(yōu)化器再次被觸發(fā)，調整系統(tǒng)中所有任務的服務級，提高任務的CPU利用率，使系統(tǒng)可以得到充分的利用。

圖3 整個系統(tǒng)的負載情況

4 結束語

本文根據數控系統(tǒng)的特點，設計了一種針對數控系統(tǒng)中軟實時任務的反饋調度模型。該反饋調度算法通過監(jiān)控當前數控系統(tǒng)的負載情況和各個任務的錯失率，來自動調整軟實時任務的周期和執(zhí)行時間。在系統(tǒng)負載不足時，對軟實時任務進行時間參數的調整，使系統(tǒng)資源得到充分利用。在系統(tǒng)負載過大時，反饋調節(jié)也可以對系統(tǒng)中任務進行調整，從而保證了其穩(wěn)定性。通過實驗對該反饋調度算法的性能進行了驗證，通過對比實驗的結果，可看出反饋調度算法可以很好地滿足數控系統(tǒng)中軟實時任務的調度要求，提升系統(tǒng)資源的利用率，并在此基礎上保證數控系統(tǒng)的穩(wěn)定性。

［1］C.Lu，J.Stankovic，G.Tao and S.Son.Feedback Control real-time Scheduling:framework modeling and algorithms［J］.Real-time Systems，2002，23(9):85 －126.

［2］P.Marti，C.Lin，S.Brandt，M.Velasco，and J.Fuertes.Optimal State Feedback Based Resource Allocation for Resource-Constrained Control Tasks［C］.In Proc.of the 25th IEEE Real-Time Systems Symp.，2004:161 －172.

［3］T.Abdelzaher，J.stankovic，C.Lu，R.Zhang，and Y.Lu.Feedback performance control in software services［J］.IEEE Control Systems，2003，23(6):74 －90.

［4］L.Abeni，L.Palopoli，G.Lipari，and J.Walpole.Analysis of a reservation-based feedback scheduler［C］.In Proc.of the 23rd IEEEReal-Time Systems Symp.，2002:71 －80.

［5］A.Block，B.Brandenburg，J.Anderson，and S.Quint.An Adaptive Framework for Multiprocessor Real-Time System［J］.Real-Time Systems，2008(7):23－33.

［6］ G.Buttazzo，L.Abeni.Adaptive workload management through elastic scheduling［J］.Real-time Systems，2002，23(1－2):7－24.

［7］秦承剛，于東，吳文江，等.一種面向數控系統(tǒng)的動態(tài)反饋調度模型［J］.小型微型計算機系統(tǒng)，2010，31(4):788－792.

［8］王保勝，吳文江，馬躍，等.開放式數控系統(tǒng)任務調度模型［J］.組合機床與自動化加工技術，2010(6):37－42.

(編輯 李秀敏)

An Adaptive Scheduling Algorithm for CNC System

GUO Feng-zhao1，2，GUO Rui-feng2，DINGWan-fu1，2，QIN Cheng-gang1，2
(1.Graduate University of Chinese Academy of Sciences，Beijing 100039，China;2.National Engineering Research Center For High-End CNC，Shenyang Institute of Computing Technology，CAS，Shenyang 110171，China)

Traditional CNC system uses static,open-loop scheduling strategy.The system resources can not be fully utilized.To improve the utilization of CNC system,we present a Feedback Control EDF scheduling algorithm for soft real-time tasks.By monitoring the current system load and themiss rate of each task,the feedback scheduling algorithm automatically adjust the time parameters of the soft realtime tasks.The system resources can be fully utilized,and have a better performance in various conditions.We elaborate some experiments to test the performance of the presented feedback control scheduling,the result illustrate that the algorithm can effective improve the utilization of system,and ensure the stability of the CNC system.

CNC System;real-time system;adaptive scheduling algorithm;feedback control

TH16;TG65

A

1001－2265(2011)06－0044－04

2010－11－12

“高檔數控機床與基礎制造裝備”國家科技重大專項－開放式數控系統(tǒng)支撐技術創(chuàng)新平臺建設(2011ZX04016－071)

郭鳳釗(1987—)，男，河北邯鄲人，中國科學院研究生院碩士研究生，主要研究方向為實時調度算法，(E－mail)guofengzhao@sict.ac.cn;郭銳鋒(1968—)，男，沈陽人，中國科學院研究生院博士生導師，主要研究方向數控技術與實時系統(tǒng)，(E－mail):grf@sict.ac.cn。