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

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

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

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

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

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

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

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

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