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

1、隨著信息技術(shù)產(chǎn)業(yè)的快速發(fā)展，實(shí)時(shí)嵌入式系統(tǒng)的應(yīng)用日益廣泛。由于受研發(fā)設(shè)備成本、體積、能耗、資源利用率等因素的多重約束，在同一個(gè)硬件平臺(tái)上集成多種不同關(guān)鍵性級(jí)別功能應(yīng)用已經(jīng)成為現(xiàn)代嵌入式系統(tǒng)的流行趨勢(shì)。對(duì)不同關(guān)鍵性級(jí)別的功能應(yīng)用，其驗(yàn)證方法和可靠性級(jí)別都有不同。對(duì)系統(tǒng)中不同重要程度的功能賦予不同的關(guān)鍵性級(jí)別的混合關(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)問(wè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è)問(wèn)題，有學(xué)者提出了LB算法，LB采用忙碌周期的技術(shù)將OCBP拓展到更為通用的混合關(guān)鍵性偶發(fā)性任務(wù)模型中。然而LB算法的運(yùn)行時(shí)時(shí)間復(fù)雜度為偽多項(xiàng)式級(jí)別，這對(duì)嵌入式系統(tǒng)而言難以接受。

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

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