實時系統(tǒng)的基于優(yōu)先級的實時重構和不基于優(yōu)先級的條件剝奪調度算法.pdf

1、在過去四十年中，實時系統(tǒng)調度與重構作為一大熱點，已經(jīng)被深入而廣泛地研究過，成果豐碩。目前，在此研究領域里，已經(jīng)建立了比較完善的基礎理論體系。通常，實時系統(tǒng)的調度算法主要可以分為兩大類:基于靜態(tài)優(yōu)先級與基于動態(tài)優(yōu)先級的調度。最早截止時間優(yōu)先算法是目前最為廣泛使用的基于動態(tài)優(yōu)先級的調度算法。相應地，最為常見的靜態(tài)優(yōu)先級的調度算法是固定優(yōu)先級調度。此外，在實時系統(tǒng)的調度過程中，任務的執(zhí)行方式可以分為可剝奪和不可剝奪兩種方式。基于此，用戶可以對

2、實時系統(tǒng)進行動態(tài)的重構，以保證系統(tǒng)的正常運行。
　　近年來，國內外學者對實時系統(tǒng)的低能耗動態(tài)重構進行了大量的研究與探討。本畢業(yè)論文所要實現(xiàn)的第一個貢獻就是，通過對實時系統(tǒng)進行低能耗的動態(tài)重構，以達到降低系統(tǒng)的能量消耗的重要目標。此部分主要是對具有實時周期任務和隨機任務的系統(tǒng)執(zhí)行低能耗重構。這些任務的運行與系統(tǒng)的內外部事件相對應。具體涉及對周期性任務和有硬/軟截止時間的隨機任務執(zhí)行調度。這種基于事件的重構方案允許動態(tài)地添加/刪除由系

3、統(tǒng)指派的周期性任務或隨機任務。但在任務增加之后，其中一些任務可能錯過他們的硬截止時間，使調度失敗。同時，系統(tǒng)的能耗也有可能會增加。為了使系統(tǒng)能夠重新滿足其調度的可行性與靈活性，并且節(jié)約系統(tǒng)的能耗，本文提出了一種基于智能代理的軟件架構。此種智能代理構架，可以提供四種實時重構系統(tǒng)的解決方案。這些解決方案可以動態(tài)地修改系統(tǒng)中任務的時間參數(shù)，以保證其運行正常。此外，為了有效地執(zhí)行隨機任務并且降低系統(tǒng)的能耗，本代理通過動態(tài)地擴展周期性任務的運行周

4、期，提供了三個虛擬處理器。最終，基于仿真研究，我們驗證了該智能代理的有效性。
　　過去三十年以來，離散事件系統(tǒng)的監(jiān)督控制理論從誕生以來，一直受到廣泛的關注和認可?；陔x散事件系統(tǒng)，系統(tǒng)的行為可以被描述成形式語言。基于形式語言，用戶可以方便地定義系統(tǒng)的行為約束。通常情況下，監(jiān)督控制理論可以找到一組最優(yōu)解，該最優(yōu)解對系統(tǒng)的行為有最少的約束。用戶對系統(tǒng)的行為可以提出一定的限制。結合這些限制，監(jiān)督控制理可以設計控制器并找出最優(yōu)解，使該控制

5、問題可以被全面而有效的解決。時間離散事件系統(tǒng)的監(jiān)督控制理論，通過在考慮時間因素的情況下，可尋找到系統(tǒng)的最優(yōu)解。眾所周知，傳統(tǒng)的實時系統(tǒng)調度不能提供所有的安全運行路徑。文獻[32]通過將實時任務的基于動態(tài)優(yōu)先級的調度和時間離散事件系統(tǒng)的監(jiān)督控制進行結合，最終生成的控制器可以提供給系統(tǒng)所有的調度運行路徑。以此文獻為基礎，本畢業(yè)論文的第二個貢獻是:提出了一種能運行在單處理機上的實時系統(tǒng)動態(tài)調度重構技術。這種新模型可用來分配給每個周期性任務一組

6、不同的周期。通過利用監(jiān)督控制理論，在實時系統(tǒng)最初始的安全執(zhí)行序列集合為空時，它可被動態(tài)地重構。在這個重構過程中，基于多周期的環(huán)境，監(jiān)督控制器可以提供所有的安全執(zhí)行路徑。本部分還通過計算兩個實例來進一步闡明，相較于最早截至時間優(yōu)先調度算法，這種新調度方法可以提供的更多的安全執(zhí)行路徑的數(shù)量。
　　由于時間離散事件系統(tǒng)中的時間是由唯一的時間事件表示，所以對實時系統(tǒng)行為的描述有一定的局限性。因此導致了其所建立的控制模型只能對靜態(tài)（固定）優(yōu)

7、先級實時系統(tǒng)進行建模、調度和重構。為了能夠提出一套更為普遍，更為完善的實時調度理論，本畢業(yè)論文的第三個貢獻是:與基于優(yōu)先級的實時調度方法相比，本文提出了一種更一般的基于離散事件系統(tǒng)的硬周期實時系統(tǒng)調度模型。該調度模型的調度過程是通過監(jiān)督控制理論，而不是以任務的優(yōu)先級去進行決策調度。該調度方法可用來處理單處理機或多處理機上運行的所有任務。其中，各實時任務的剝奪關系比基于優(yōu)先級的剝奪更加一般化。在調度過程中，首先，計算機形式語言可以被用來描

8、述各實時任務執(zhí)行時所關聯(lián)的處理器行為;其次，所有的計算機語言是用離散事件系統(tǒng)所生成的控制器來表示;第三，在離散事件系統(tǒng)控制器生成的同時，全局控制器也將產生。在此基礎上，本部分創(chuàng)新地提出了一個新的調度策略——條件剝奪。在處理器和實時任務兩個層面上，分別構建了兩種條件剝奪的方式。此外，為了能夠有效、無阻礙地控制系統(tǒng)，并且限制任務的最壞響應時間，本部分還提出了另外兩組約束方式。在產生全局控制器后，通過執(zhí)行監(jiān)督控制理論，計算出的監(jiān)控器可以提供所