許元飛

XU Yuan-fei

（西安科技大學(xué) 計(jì)算機(jī)學(xué)院，西安 710054）

0 引言

計(jì)算機(jī)控制系統(tǒng)中關(guān)于實(shí)時(shí)調(diào)度的問題，傳統(tǒng)上是由控制系統(tǒng)工程師與實(shí)時(shí)系統(tǒng)工程師通過各自理解進(jìn)行調(diào)度設(shè)計(jì)的，這種設(shè)計(jì)思想在計(jì)算機(jī)資源富足時(shí)其計(jì)算機(jī)控制系統(tǒng)的運(yùn)行效果是良好的，而在資源有限時(shí)會(huì)出現(xiàn)資源共享問題[1]。在計(jì)算機(jī)控制中，由于控制任務(wù)的并行性，我們需要考慮控制性與計(jì)算機(jī)資源的均衡，同時(shí)由于實(shí)時(shí)系統(tǒng)工程師根據(jù)控制系統(tǒng)工程師提供的相關(guān)數(shù)據(jù)信息進(jìn)行調(diào)度設(shè)計(jì)，而控制系統(tǒng)工程師所提供的數(shù)據(jù)信息本身就含有很大的不精確性，這將導(dǎo)致計(jì)算機(jī)資源利用率大大降低，從而影響整個(gè)控制系統(tǒng)[2]。計(jì)算機(jī)控制系統(tǒng)中，某些任務(wù)通常是模糊不定的，具有小范圍的隨機(jī)波動(dòng)，例如由時(shí)鐘的精確性引起的采樣期誤差等，這些因素導(dǎo)致計(jì)算機(jī)在進(jìn)行控制執(zhí)行時(shí)產(chǎn)生延遲和抖動(dòng)[3]，從而影響整個(gè)系統(tǒng)的性能和穩(wěn)定。基于解決以上問題，本文提出了一種基于計(jì)算機(jī)控制中模糊調(diào)度設(shè)計(jì)的方案，并進(jìn)行了仿真研究。

1 計(jì)算機(jī)控制系統(tǒng)任務(wù)調(diào)度設(shè)計(jì)

1.1 計(jì)算機(jī)控制回路

計(jì)算機(jī)控制器在每個(gè)采樣周期都會(huì)對(duì)系統(tǒng)的輸入輸出參數(shù)進(jìn)行對(duì)比，對(duì)控制量進(jìn)行權(quán)衡，將新的控制量作為輸入?yún)?shù)來(lái)控制系統(tǒng)，使系統(tǒng)的輸出在滿足條件的情況下，盡可能的與實(shí)時(shí)需求相接近，且控制量更新與系統(tǒng)運(yùn)算過程組成計(jì)算機(jī)控制回路。在這個(gè)回路中涉及到模擬信號(hào)與數(shù)字信號(hào)的相互轉(zhuǎn)換及其相應(yīng)的控制算法。

1.2 計(jì)算機(jī)控制任務(wù)

在整個(gè)計(jì)算機(jī)系統(tǒng)中，計(jì)算機(jī)控制任務(wù)主要是控制算法程序調(diào)度，具有周期性、反復(fù)性，而模態(tài)量的轉(zhuǎn)換對(duì)計(jì)算機(jī)控制任務(wù)影響不太大，因此本文僅對(duì)計(jì)算機(jī)控制任務(wù)的算法調(diào)度問題進(jìn)行研究，并約束假設(shè)計(jì)算機(jī)系統(tǒng)輸出算法對(duì)整個(gè)計(jì)算機(jī)控制系統(tǒng)的影響遠(yuǎn)小于控制調(diào)度算法。

1.3 調(diào)度步驟

假設(shè)現(xiàn)由N個(gè)系統(tǒng)G構(gòu)成了多任務(wù)控制系統(tǒng)，并且每個(gè)控制器控制各自所屬對(duì)象，n個(gè)控制器任務(wù)參與計(jì)算機(jī)資源的競(jìng)爭(zhēng)。設(shè)Q為控制器任務(wù)按照優(yōu)先級(jí)大小排列的隊(duì)列。調(diào)度過程如下：

1）對(duì)于新接收到的控制任務(wù)，首先對(duì)其優(yōu)先級(jí)進(jìn)行配置，并將其任務(wù)插入到Q隊(duì)列中，對(duì)于優(yōu)先級(jí)越高的任務(wù)T優(yōu)先獲取CPU的資源進(jìn)行執(zhí)行。

2）對(duì)于完全搶占式調(diào)度，其Q隊(duì)列等待執(zhí)行任務(wù)與CPU正在執(zhí)行任務(wù)T進(jìn)行資源競(jìng)爭(zhēng)，若某個(gè)等待執(zhí)行的任務(wù)的優(yōu)先級(jí)高于CPU正在執(zhí)行的任務(wù)，則該任務(wù)搶占CPU資源進(jìn)行調(diào)度執(zhí)行，正在CPU執(zhí)行的任務(wù)退出，并按照優(yōu)先級(jí)順序插回Q隊(duì)列。

3）由于調(diào)度器本身不知道任務(wù)的實(shí)際截止期，它將會(huì)按照任務(wù)的最晚截止期判斷任務(wù)是否錯(cuò)失截止期，當(dāng)任務(wù)T未錯(cuò)失自身的最晚截止期時(shí)仍可繼續(xù)對(duì)CPU資源進(jìn)行競(jìng)爭(zhēng)，或者按照優(yōu)先級(jí)排序于隊(duì)列Q中等待調(diào)度；當(dāng)任務(wù)T或Q中某些任務(wù)錯(cuò)失自身的最晚截止期時(shí)，調(diào)度器將終止該任務(wù)的執(zhí)行或等待。

4）所有CPU執(zhí)行完成的任務(wù)或者錯(cuò)失最晚截止期而被終止的任務(wù)由調(diào)度器發(fā)送到相應(yīng)隊(duì)列中，任務(wù)被執(zhí)行的實(shí)例控制量進(jìn)行更新，錯(cuò)失昨晚截止期的任務(wù)實(shí)例不再執(zhí)行更新。

1.4 計(jì)算機(jī)控制環(huán)的計(jì)算

基于模糊調(diào)度設(shè)計(jì)的計(jì)算機(jī)控制環(huán)計(jì)算方法中，假設(shè)以下情況：1）計(jì)算機(jī)控制任務(wù)的采樣周期是穩(wěn)定的；2）在每個(gè)采樣循環(huán)中判斷當(dāng)前任務(wù)是否得到執(zhí)行或因錯(cuò)失最晚截止期而放棄執(zhí)行。若當(dāng)前任務(wù)執(zhí)行已經(jīng)完成，則說明當(dāng)前采樣環(huán)內(nèi)控制算法計(jì)算時(shí)間早于最晚截止期完成，此時(shí)對(duì)任務(wù)控制量進(jìn)行更新；若當(dāng)前任務(wù)錯(cuò)失最晚截止期而放棄執(zhí)行，則說明當(dāng)前采樣控制算法計(jì)算不能在截止期完成前結(jié)束計(jì)算，此時(shí)維持控制量不變。

2 基于搶占閾值的最大奉獻(xiàn)優(yōu)先調(diào)度策略

2.1 奉獻(xiàn)度

奉獻(xiàn)度是指在計(jì)算機(jī)控制任務(wù)集中每個(gè)任務(wù)盡可能的在各自任務(wù)執(zhí)行的許可范圍內(nèi)進(jìn)行延遲調(diào)度，以便更加緊急的任務(wù)被優(yōu)先調(diào)度，從而提高整個(gè)計(jì)算機(jī)控制系統(tǒng)的執(zhí)行效率。奉獻(xiàn)度的前提是每個(gè)任務(wù)確保即使在最壞情況下自身仍然能夠被調(diào)度執(zhí)行，事實(shí)上，計(jì)算機(jī)控制系統(tǒng)在進(jìn)行任務(wù)調(diào)度時(shí)本身具有一定的延遲性，該性質(zhì)確保了任務(wù)進(jìn)程可以實(shí)現(xiàn)奉獻(xiàn)精神，以確保計(jì)算機(jī)系統(tǒng)控制調(diào)度過程中可以進(jìn)行更加有效的優(yōu)先級(jí)任務(wù)配置。

2.2 搶占閥值

在計(jì)算機(jī)控制系統(tǒng)中，每個(gè)任務(wù)的奉獻(xiàn)度是逐漸遞增的，因此一旦在某個(gè)時(shí)刻ti，某個(gè)等待執(zhí)行的任務(wù)Ti的奉獻(xiàn)度就會(huì)大于正在執(zhí)行的任務(wù)Tj的奉獻(xiàn)度，等待執(zhí)行的任務(wù)Ti將搶占正在執(zhí)行的任務(wù)Tj的資源，等待執(zhí)行的任務(wù)Ti被執(zhí)行時(shí)，其奉獻(xiàn)度不變，但原來(lái)正在執(zhí)行的任務(wù)Tj由于出現(xiàn)了等待，它的奉獻(xiàn)度將遞增。一直都某個(gè)時(shí)刻tj，任務(wù)Tj的奉獻(xiàn)度大于Ti，其又開始搶占Ti的資源，造成任務(wù)間的不斷切換形成顛簸現(xiàn)象，因此為了節(jié)約CPU的資源，我們提出了搶占閥值的最大奉獻(xiàn)優(yōu)先調(diào)度策略。由于優(yōu)先級(jí)P[0，1]，設(shè)h[p，1]，任務(wù)的完成率定義為任務(wù)完成時(shí)間與任務(wù)總執(zhí)行時(shí)間之比，對(duì)于某個(gè)給定的任務(wù)完成率a，當(dāng)任務(wù)完成率小于a時(shí)，搶占閥值為h=p，此時(shí)執(zhí)行完全搶占CPU資源，否則，h=1，即非搶占方式。

基于此，基于搶占閾值的最大奉獻(xiàn)優(yōu)先調(diào)度策略其調(diào)度步驟需要對(duì)1.3 調(diào)度步驟中的2）進(jìn)行修改：

對(duì)于等待的任務(wù)是否搶占當(dāng)前CPU正在執(zhí)行任務(wù)的資源，其判別條件是p＞h，即當(dāng)h=p時(shí)，等待任務(wù)完全搶占CPU資源進(jìn)行任務(wù)的執(zhí)行，而當(dāng)h=1時(shí)，Q隊(duì)列中的等待任務(wù)只有在當(dāng)前任務(wù)執(zhí)行完成后才有機(jī)會(huì)競(jìng)爭(zhēng)CPU資源。

3 仿真

3.1 仿真條件

表1給出了計(jì)算機(jī)系統(tǒng)控制參數(shù)值，同時(shí)約定控制器進(jìn)行計(jì)算機(jī)資源競(jìng)爭(zhēng)時(shí)， TS=2000，控制系統(tǒng)的輸入設(shè)為階躍函數(shù)，當(dāng)T≤500或者1000≤T≤1500時(shí)，R (T)＝1，其余時(shí)間段內(nèi)R(T)＝－1。單位為ms。

表1 計(jì)算機(jī)系統(tǒng)控制參數(shù)

3.2 計(jì)算機(jī)控制性能比較

在進(jìn)行計(jì)算機(jī)控制性能比較時(shí)，我們參考文獻(xiàn)[4]中的控制性能損失指標(biāo)來(lái)衡量。根據(jù)表1中所給的數(shù)據(jù)，T1、T2所有的任務(wù)實(shí)例分別為166、200，任務(wù)的截止期為模糊量，考慮到可行性問題，我們使用最晚截止期B來(lái)代替模糊截止期D，則利用率的下界為

因此，計(jì)算機(jī)控制系統(tǒng)仍然會(huì)發(fā)生過載現(xiàn)象。

計(jì)算機(jī)控制系統(tǒng)在基于搶占閾值的調(diào)度策略的計(jì)算機(jī)控制性能如圖1所示：

其中X軸是時(shí)間變化，圖1（a）和（c）為兩個(gè)子系統(tǒng)的測(cè)量比較，控制參考輸入信號(hào)為虛線，實(shí)際測(cè)量為實(shí)線，理想測(cè)量為點(diǎn)線；圖1（b）和（d）為兩個(gè)子系統(tǒng)控制信號(hào)的比較，其中，實(shí)際控制量為實(shí)線，理想控制量為虛線。

仿真結(jié)果表明：

1）計(jì)算機(jī)總系統(tǒng)過載時(shí)產(chǎn)生額外調(diào)度的損失與任務(wù)進(jìn)程完成情況具有無(wú)關(guān)性，但與子系統(tǒng)的控制性能變化呈相關(guān)性。子系統(tǒng)1的控制性能隨著任務(wù)的完成率單調(diào)遞增，而子系統(tǒng)2則相反。

2）對(duì)于完全搶占或較大的任務(wù)完成率，子系統(tǒng)2的控制性能影響較小，T2的所有實(shí)例都完成了進(jìn)程調(diào)度，但子系統(tǒng)1的系統(tǒng)過載時(shí)產(chǎn)生額外調(diào)度的損失與截止期錯(cuò)失率都達(dá)到峰值。

3）CPU的有效利用率是隨著系統(tǒng)的任務(wù)完成率遞減的，而系統(tǒng)任務(wù)未完成但被搶占的次數(shù)隨著系統(tǒng)完成率遞增的。

4）對(duì)于任何一個(gè)控制系統(tǒng)，總的截止期錯(cuò)失率是一定的，與子系統(tǒng)的截止期錯(cuò)失率變化無(wú)關(guān)。

可以看出，通過搶占閾值的最大奉獻(xiàn)優(yōu)先調(diào)度策略，系統(tǒng)任務(wù)的切換次數(shù)減少了，搶占權(quán)限被有條件搶占調(diào)度得到控制。

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

截止期的模糊調(diào)度問題是計(jì)算機(jī)控制系統(tǒng)中影響系統(tǒng)控制性能損失的重要問題之一，對(duì)于不確定截止期的任務(wù)實(shí)現(xiàn)調(diào)度在實(shí)時(shí)系統(tǒng)處理中會(huì)影響運(yùn)算控制效率，從而造成負(fù)載過重現(xiàn)象，在計(jì)算機(jī)計(jì)算資源有限的條件下，對(duì)任務(wù)進(jìn)程之間實(shí)現(xiàn)可控調(diào)度和控制任務(wù)的模糊調(diào)度策略研究，有利于提高計(jì)算機(jī)的資源利用率。本文通過基于搶占閾值的最大奉獻(xiàn)優(yōu)先調(diào)度策略對(duì)這一問題進(jìn)行仿真模擬，實(shí)驗(yàn)表明，該方案有效的提高了計(jì)算機(jī)的利用率，均衡了子系統(tǒng)控制性能，減少了總系統(tǒng)的開銷。

[1] Potkonjak M.,Wolf W. . A methodology and algorithms for the design of hard real-time multitasking Asics. ACM Transactions on Design Automation of Electronic Systems,1999,4(4)： 430-459.

[2] Marti P.,Fuertes J. M. ,Fohler G.,Ramamritham K..Improving quality—of-control using flexible timing constraints： Metric and scheduling. In： Proceedings of the 23rd IEEE Real-Time Systems Symposium,Texas,USA,2002,91-100.

[3] Lopez J. ,Marti P. ,Fuertes J. M. . Control loop scheduling paradigm in distributed control systems. In： Proceedings of the 29th IEEE Annual Conference on Industrial Electronics Society,Virginia,USA,2003,2： 1441-1446.

[4] Jin H,Wang H A,Wang H,Wang D. Scheduling design of controllers with fuzzy deadline. Wang L.,Jin H. eds..Lecture Notes in Artificial Intelligence 3613,Berlin Heidelberg： Springer-Vela,2005,861-864.