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

郭鳳釗，郭銳鋒，丁萬(wàn)夫，，秦承剛，

(1.中國(guó)科學(xué)院研究生院，北京 100039;2.中國(guó)科學(xué)院沈陽(yáng)計(jì)算技術(shù)研究所高檔數(shù)控國(guó)家工程研究中心，沈陽(yáng) 110171)

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

郭鳳釗1，郭銳鋒2，丁萬(wàn)夫1，2，秦承剛1，2

(1.中國(guó)科學(xué)院研究生院，北京 100039;2.中國(guó)科學(xué)院沈陽(yáng)計(jì)算技術(shù)研究所高檔數(shù)控國(guó)家工程研究中心，沈陽(yáng) 110171)

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

數(shù)控系統(tǒng);實(shí)時(shí)系統(tǒng);自適應(yīng)調(diào)度算法;反饋控制

0 引言

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

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

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

1 數(shù)控系統(tǒng)的調(diào)度模型

1.1 傳統(tǒng)數(shù)控系統(tǒng)的調(diào)度模型

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

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

1.2 任務(wù)模型的基本定義

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

本文使用以下符號(hào)對(duì)任務(wù)模型進(jìn)行描述:

2 反饋調(diào)度模型

2.1 反饋模型設(shè)計(jì)思想

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

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

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

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

圖1 反饋調(diào)度模型

2.2 反饋控制器

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

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

其中p，i，d分別為比例參數(shù)，積分參數(shù)以及微分參數(shù)。在很多情況下，并不一定需要全部三個(gè)單元，可以取其中的一或兩個(gè)單元，但比例控制單元是必不可少的。本文使用比例單元(P)和積分單元(I)，沒(méi)有選取微分單元是因?yàn)榭刂破鞯奈⒎止δ懿贿m合控制實(shí)時(shí)系統(tǒng)，微分單元可能會(huì)放大因?yàn)镃PU和帶寬負(fù)載的隨機(jī)性而造成的系統(tǒng)噪音。由于本反饋系統(tǒng)是周期采樣的，是離散系統(tǒng)，故輸出Ew()與輸入Error(的關(guān)系為:

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

2.3 優(yōu)化器

每一個(gè)任務(wù)都有一個(gè)用戶定義的重要性參數(shù)，代表該任務(wù)的重要程度，用L來(lái)表示，例如用L(Ti)表示Ti的重要程度。在每一次調(diào)用優(yōu)化器的時(shí)候，都會(huì)根據(jù)每個(gè)任務(wù)的L值對(duì)任務(wù)進(jìn)行由大到小的排序，依次給各個(gè)任務(wù)分配合適的服務(wù)級(jí)別。

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

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

3 實(shí)驗(yàn)研究與分析

3.1 試驗(yàn)平臺(tái)

本文使用了藍(lán)天數(shù)控系統(tǒng)作為實(shí)驗(yàn)平臺(tái)，該系統(tǒng)采用了基于雙內(nèi)核架構(gòu)的實(shí)時(shí)操作系統(tǒng)RTAI(Real-Time Application Interface)。RTAI采用模塊化的方式，作為L(zhǎng)inux的模塊插入到內(nèi)核運(yùn)行空間，用以實(shí)現(xiàn)了Linux內(nèi)核的實(shí)時(shí)擴(kuò)展。為了實(shí)現(xiàn)針對(duì)軟實(shí)時(shí)任務(wù)的反饋調(diào)度器，本文對(duì)RTAI的軟實(shí)時(shí)任務(wù)的結(jié)構(gòu)定義及其調(diào)度函數(shù)進(jìn)行了修改，在Linux內(nèi)核空間內(nèi)實(shí)現(xiàn)了一個(gè)軟實(shí)時(shí)調(diào)度器，在此基礎(chǔ)上對(duì)反饋調(diào)度器進(jìn)行實(shí)驗(yàn)測(cè)試。

3.2 實(shí)驗(yàn)方法及參數(shù)選定

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

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

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

設(shè)定任務(wù)估計(jì)權(quán)重和實(shí)際權(quán)重之間的最大差值，即Error的上限不超過(guò)0.5。如果超過(guò)這個(gè)值，系統(tǒng)就會(huì)調(diào)用優(yōu)化器對(duì)任務(wù)進(jìn)行新服務(wù)級(jí)的分配。

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

3.3 單個(gè)任務(wù)的權(quán)重表現(xiàn)

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

圖2 單個(gè)任務(wù)的權(quán)重變化

3.4 整個(gè)系統(tǒng)的負(fù)載情況

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

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

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

本文根據(jù)數(shù)控系統(tǒng)的特點(diǎn)，設(shè)計(jì)了一種針對(duì)數(shù)控系統(tǒng)中軟實(shí)時(shí)任務(wù)的反饋調(diào)度模型。該反饋調(diào)度算法通過(guò)監(jiān)控當(dāng)前數(shù)控系統(tǒng)的負(fù)載情況和各個(gè)任務(wù)的錯(cuò)失率，來(lái)自動(dòng)調(diào)整軟實(shí)時(shí)任務(wù)的周期和執(zhí)行時(shí)間。在系統(tǒng)負(fù)載不足時(shí)，對(duì)軟實(shí)時(shí)任務(wù)進(jìn)行時(shí)間參數(shù)的調(diào)整，使系統(tǒng)資源得到充分利用。在系統(tǒng)負(fù)載過(guò)大時(shí)，反饋調(diào)節(jié)也可以對(duì)系統(tǒng)中任務(wù)進(jìn)行調(diào)整，從而保證了其穩(wěn)定性。通過(guò)實(shí)驗(yàn)對(duì)該反饋調(diào)度算法的性能進(jìn)行了驗(yàn)證，通過(guò)對(duì)比實(shí)驗(yàn)的結(jié)果，可看出反饋調(diào)度算法可以很好地滿足數(shù)控系統(tǒng)中軟實(shí)時(shí)任務(wù)的調(diào)度要求，提升系統(tǒng)資源的利用率，并在此基礎(chǔ)上保證數(shù)控系統(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］秦承剛，于東，吳文江，等.一種面向數(shù)控系統(tǒng)的動(dòng)態(tài)反饋調(diào)度模型［J］.小型微型計(jì)算機(jī)系統(tǒng)，2010，31(4):788－792.

［8］王保勝，吳文江，馬躍，等.開(kāi)放式數(shù)控系統(tǒng)任務(wù)調(diào)度模型［J］.組合機(jī)床與自動(dòng)化加工技術(shù)，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

“高檔數(shù)控機(jī)床與基礎(chǔ)制造裝備”國(guó)家科技重大專項(xiàng)－開(kāi)放式數(shù)控系統(tǒng)支撐技術(shù)創(chuàng)新平臺(tái)建設(shè)(2011ZX04016－071)

郭鳳釗(1987—)，男，河北邯鄲人，中國(guó)科學(xué)院研究生院碩士研究生，主要研究方向?yàn)閷?shí)時(shí)調(diào)度算法，(E－mail)guofengzhao@sict.ac.cn;郭銳鋒(1968—)，男，沈陽(yáng)人，中國(guó)科學(xué)院研究生院博士生導(dǎo)師，主要研究方向數(shù)控技術(shù)與實(shí)時(shí)系統(tǒng)，(E－mail):grf@sict.ac.cn。