面向非自監(jiān)測系統(tǒng)的混合關(guān)鍵性實(shí)時(shí)調(diào)度算法研究.pdf

1、隨著信息技術(shù)產(chǎn)業(yè)的快速發(fā)展，實(shí)時(shí)嵌入式系統(tǒng)的應(yīng)用日益廣泛。由于受研發(fā)設(shè)備成本、體積、能耗、資源利用率等因素的多重約束，在同一個(gè)硬件平臺上集成多種不同關(guān)鍵性級別功能應(yīng)用已經(jīng)成為現(xiàn)代嵌入式系統(tǒng)的流行趨勢。對不同關(guān)鍵性級別的功能應(yīng)用，其驗(yàn)證方法和可靠性級別都有不同。對系統(tǒng)中不同重要程度的功能賦予不同的關(guān)鍵性級別的混合關(guān)鍵性系統(tǒng)為現(xiàn)代實(shí)時(shí)嵌入式系統(tǒng)的設(shè)計(jì)提供了有效的方案。隨著混合關(guān)鍵性系統(tǒng)模型的的提出，混合關(guān)鍵性實(shí)時(shí)調(diào)度算法的研究與設(shè)計(jì)也成為實(shí)

2、時(shí)嵌入式系統(tǒng)領(lǐng)域的熱點(diǎn)問題。
　　在混合關(guān)鍵性領(lǐng)域已有的調(diào)度算法中，OCBP(Own Criticality Based Priority)算法具有很多優(yōu)秀的性質(zhì)并引起了混合關(guān)鍵性領(lǐng)域?qū)W者的廣泛關(guān)注。但是OCBP算法只適用于有限數(shù)量作業(yè)的系統(tǒng)，為了解決這個(gè)問題，有學(xué)者提出了LB算法，LB采用忙碌周期的技術(shù)將OCBP拓展到更為通用的混合關(guān)鍵性偶發(fā)性任務(wù)模型中。然而LB算法的運(yùn)行時(shí)時(shí)間復(fù)雜度為偽多項(xiàng)式級別，這對嵌入式系統(tǒng)而言難以接受。

3、后來的PLRS算法利用優(yōu)先級計(jì)劃表和運(yùn)行時(shí)抽象數(shù)據(jù)結(jié)構(gòu)將系統(tǒng)的時(shí)間復(fù)雜度降為平方級別，但對于嵌入式系統(tǒng)來說還是過高。最近提出的LPA(Lazy Priorities Adjustment)算法在作業(yè)發(fā)生搶占時(shí)盡可能晚的調(diào)整優(yōu)先級，從而大大降低了算法的時(shí)間復(fù)雜度。
　　LPA等算法離線優(yōu)先級分配都是基于OCBP算法，并且都是面向自監(jiān)測系統(tǒng)的。自監(jiān)測系統(tǒng)要求時(shí)刻監(jiān)視著系統(tǒng)作業(yè)的執(zhí)行時(shí)間，這就帶來嚴(yán)重的運(yùn)行時(shí)負(fù)載，因此本文提出面向非自監(jiān)

4、測系統(tǒng)的混合關(guān)鍵性調(diào)度算法LPA*。非自監(jiān)測系統(tǒng)不要求時(shí)刻監(jiān)視作業(yè)的執(zhí)行時(shí)間，雖然可能導(dǎo)致某些作業(yè)執(zhí)行過載，但極低的運(yùn)實(shí)行調(diào)度開銷使其更容易應(yīng)用到實(shí)際系統(tǒng)中。本文提出了更為精確的離線作業(yè)固定優(yōu)先級分配算法，提高系統(tǒng)資源利用率，并提出了性能良好的非自監(jiān)測系統(tǒng)混合關(guān)鍵性實(shí)時(shí)調(diào)度算法LPA*。實(shí)驗(yàn)結(jié)果表明，采用本文的離線優(yōu)先級分配算法，LPA*算法相對LPA算法有顯著的資源利用率提升。特別地，LPA*在非自監(jiān)測系統(tǒng)任務(wù)接受率性能下降不明顯，甚