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

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

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

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