基于區(qū)間劃分的實時系統(tǒng)節(jié)能調(diào)度.pdf

1、大部分嵌入式設(shè)備由于設(shè)備體積和使用環(huán)境等原因，使得為設(shè)備充電變得異常困難，甚至在一些應(yīng)用場景中，嵌入式設(shè)備的電能使用時間也即設(shè)備的生命周期。嵌入式設(shè)備的能耗管理近些年已經(jīng)發(fā)展成為嵌入式系統(tǒng)相關(guān)研究中最重要的研究方向之一。在過去十年里，學(xué)術(shù)界在低能耗系統(tǒng)設(shè)計相關(guān)領(lǐng)域取得了巨大的成就。工業(yè)界將高級配置與能耗接口（ACPI）標(biāo)準(zhǔn)植入了操作系統(tǒng)，并增加了能耗管理模塊，通過提供系統(tǒng)調(diào)用將一些系統(tǒng)設(shè)備轉(zhuǎn)換為低能耗狀態(tài)，從而達(dá)到節(jié)能的目的。許多在嵌入

2、式設(shè)備上運(yùn)行的應(yīng)用也存在嚴(yán)格的時間限制，這些應(yīng)用必須在截止期前完成，例如嵌入式控制器。嵌入式實時系統(tǒng)中，在滿足任務(wù)在截止期前完成(實時性)要求的前提下，盡可能的降低整個嵌入式系統(tǒng)的能耗，是一個需要迫切解決的問題。
　　本文對基于區(qū)間劃分的實時系統(tǒng)節(jié)能調(diào)度問題進(jìn)行了探討。將系統(tǒng)中小的空閑時間片段合并，增加空閑時間片段的平均長度，是解決嵌入式實時系統(tǒng)能耗問題的一個行之有效的策略?；谶@種策略，提出了一種區(qū)間劃分的能耗管理策略，由于劃分

3、的區(qū)間在形狀上類似于垛的形狀，因此將其稱為Crenel-Interval（CI）。劃分CI需要滿足兩個條件：將一個CI中所有的空閑時間片段合并后，CI中最多只能出現(xiàn)一個空閑時間片段；在滿足1的條件下，CI的長度盡可能的長。在每個CI中，任務(wù)實例只能在CI的兩端執(zhí)行，而CI中所有的空閑時間片段都集中在CI的中間，因此在每個CI中最多只會存在一個CI。通過分析CI與任務(wù)實例之間的關(guān)系，CI中的任務(wù)實例被分為強(qiáng)制任務(wù)實例和可選任務(wù)實例，其中強(qiáng)

4、制實例必須在當(dāng)前的CI中完成，且在CI的前端執(zhí)行，可選任務(wù)實例的部分工作量可以被推遲到后續(xù)的CI中執(zhí)行，且在當(dāng)前CI中執(zhí)行的部分工作量需要在CI的后端執(zhí)行。由于在每個CI中都形成了一個連續(xù)且較長的空閑時間片段，CI能夠輔助一些調(diào)度算法降低系統(tǒng)能耗。DPM（Dynamic Power Management）技術(shù)可以將系統(tǒng)中的空閑設(shè)備轉(zhuǎn)換為低能耗狀態(tài)，從而達(dá)到節(jié)能的目的。利用DPM技術(shù)，基于不同的設(shè)備模型，提出了兩種采用EDF（Earlie

5、st Deadline First）優(yōu)先級分配策略的動態(tài)優(yōu)先級節(jié)能調(diào)度算法。在單設(shè)備模型中，系統(tǒng)中只有一個設(shè)備，所有的任務(wù)都使用這個設(shè)備，基于此模型提出了CI-EDF調(diào)度算法。針對按照CI規(guī)則劃分的可選任務(wù)實例的推遲問題，在保證任務(wù)集（任務(wù)集利用率U滿足U≤1）可被CI-EDF調(diào)度的條件下，給出了每個可選任務(wù)實例在CI中的執(zhí)行時間以及所有可選任務(wù)實例可被開始調(diào)度執(zhí)行的時間點。CI-EDF的算法復(fù)雜度為O(n2)（n是系統(tǒng)中任務(wù)的個數(shù)）。

6、在多設(shè)備模型中存在多個設(shè)備，一個任務(wù)可以使用多個設(shè)備，一個設(shè)備可以被多個任務(wù)使用，基于此模型提出了CI-EDFm算法。CI-EDFm為每個設(shè)備提供了一個CI（DCI），DCI是根據(jù)訪問該設(shè)備的所有任務(wù)的周期計算而來。考慮到一個任務(wù)實例可能會訪問多個設(shè)備，設(shè)計了一個基于權(quán)重因子的策略來判斷任務(wù)實例是否應(yīng)該被推遲，這個策略綜合考慮了任務(wù)實例訪問的所有設(shè)備的DCI以及這些DCI對能耗的影響，同時給出了計算任務(wù)實例可被推遲的最長時間的方法。CI

7、-EDFm的時間復(fù)雜度為O(nm)（m是系統(tǒng)中設(shè)備的個數(shù)）。為了進(jìn)一步的降低系統(tǒng)的能耗，提出了將DVFS技術(shù)集成到CI-EDF和CI-EDFm中的方法?？紤]到任務(wù)在實際執(zhí)行的過程中需要執(zhí)行的時間要小于最壞情況的執(zhí)行時間，對CI-EDF和CI-EDFm進(jìn)行了修訂，使得它們能夠通過回收動態(tài)空閑時間來進(jìn)一步節(jié)省系統(tǒng)能耗?，F(xiàn)代處理器中，晶體管的尺寸變的越來越小，晶體管需要的閾值電壓也在降低。由于亞閾值漏電流（Subthreshold Leaka

8、ge，處理器漏電流的主要來源）隨著閾值電壓的降低而呈指數(shù)級增長，導(dǎo)致更多的電流消耗在晶體管的基底中。晶體管閾值電壓的降低也使得處理器在較低的供應(yīng)電壓下也能獲得較高的頻率，導(dǎo)致處理器的動態(tài)功耗的減少。這說明在很多現(xiàn)代處理器中，能夠用DVFS（Dynamic Voltage and Frequency Scaling）技術(shù)降低的動態(tài)能耗在減少，處理器的漏電流功耗（靜態(tài)功耗）卻在增加，漏電流功耗在處理器的功耗中占有的比例呈增大趨勢。為了降低處

9、理器的漏電流功耗，提出了基于CI的CI-RM算法。CI-RM算法為每個任務(wù)設(shè)置了一個閾值參數(shù)，這個參數(shù)和任務(wù)的周期以及任務(wù)集的利用率有關(guān)。如果任務(wù)實例的周期區(qū)間和CI的重疊區(qū)域的長度大于該任務(wù)的閾值參數(shù)，那么這個任務(wù)實例必須在當(dāng)前的CI中完成其所有的工作量，反之，這個任務(wù)實例必須被推遲到下一個CI中執(zhí)行。為了保證任務(wù)集在CI-RM算法下的可調(diào)度性，給出了可調(diào)度性證明以及CI-RM算法適用的任務(wù)集的利用率范圍。CI-RM的時間復(fù)雜度為O(