基于偶發(fā)性任務模型的混合關鍵性實時調(diào)度算法研究.pdf

1、近年來隨著信息技術(shù)產(chǎn)業(yè)的飛速發(fā)展，嵌入式系統(tǒng)集成的功能日益復雜，應用也愈發(fā)廣泛，但同時受到系統(tǒng)體積、成本、能耗、利用率等約束。為了克服這些問題，在現(xiàn)代嵌入式系統(tǒng)設計中采用在一個共享處理器平臺中集合多種不同關鍵性級別功能應用的方案成為流行趨勢。這種混合關鍵性系統(tǒng)為現(xiàn)代嵌入式實時系統(tǒng)的設計提供了有效的方案，但其中實時調(diào)度算法的設計，以該系統(tǒng)正確性的驗證都頗具挑戰(zhàn)性，并成為當今學術(shù)界和工業(yè)界研究的熱點和難點。
　　在已有的混合關鍵性調(diào)度

2、策略中，適用于有限作業(yè)系統(tǒng)的OCBP算法具有很多優(yōu)秀的性質(zhì)并被學術(shù)界廣泛關注。LB算法將OCBP擴展到更為通用的混合關鍵性偶發(fā)性任務模型中，但其偽多項式級別的時間復雜度對嵌入式系統(tǒng)而言難以接受。后來的PLRS算是利用在離線計算的優(yōu)先級計劃表和運行時抽象數(shù)據(jù)結(jié)構(gòu)將系統(tǒng)的時間復雜度降為平方級別，但對于嵌入式系統(tǒng)來說依然過高。
　　針對上述不足，本文提出新調(diào)度算法LPA，該算法核心思想:當系統(tǒng)運行中發(fā)生搶占時，LPA調(diào)度算法不是立刻對各

3、個任務的所有作業(yè)進行優(yōu)先級調(diào)整，相反，僅僅讓各個任務記錄搶占發(fā)生時被搶占任務的優(yōu)先級值，在后續(xù)作業(yè)釋放并需要設定優(yōu)先級時才通過相關判斷來決定是否需要對當前任務進行優(yōu)先級調(diào)整。這就將集中而繁重的優(yōu)先級調(diào)整工作分散到各個作業(yè)釋放時刻進行，不但降低了單次優(yōu)先級調(diào)整的復雜度，也避免了大量冗余的計算量進而顯著提升了運行時調(diào)度的性能。
　　另外，LB、PLRS算法在將無限作業(yè)數(shù)轉(zhuǎn)化為有限作業(yè)數(shù)時采用了忙碌周期概念，但是在計算其上界時采用的算法