國立屏東大學 即時與嵌入式系統實驗室
Vestal2007 - Preemptive Scheduling of Multi-criticality Systems with Varying Degrees of Execution Time Assurance
Highlights
- MCS領域的第一篇論文
- FP工作回應時間迭代分析式
- OPA最佳優先權給定方法
- Priority Transformed
為了因應不同關鍵層級的安全性要求，工作通常必須被設計為多個不同的實作版本，例如用以維持車輛行駛安全的循跡防滑控制工作，可以針對低安全性與高安全性要求分別實作兩個不同的版本供低關鍵層級與高關鍵層級運行時使用。當車輛處於低速與高速行駛時，車用MCS將會分別切換至對應的低與高關鍵層級並切換使用不同的工作實作版本。當MCS運行在低速行駛的低關鍵層級時，低安全性的工作實作版本在計算車輛行進軌跡時，只需要精確至小數點後2位；但是當車輛以高速行駛時，我們對於安全性的要求將會大幅提升，MCS將會切換至高關鍵層級運行，並且改為使用高安全性的工作版本計算行進軌跡至小數點後5位，同時還需要進行冗餘計算以確保計算結果的正確性。上述概念首見於Steve Vestal於2007年 IEEE RTSS會議(以即時系統的週期性工作模型為基礎)所發表的工作模型[Vestal2007]，其假設工作的執行時間與其關鍵性成正比，工作的關鍵層級愈高、其執行時間愈長，我們將其稱為「關鍵性相依的執行時間(Criticality-Dependent Execution Time)」。換句話說，Vestal認為工作的執行時間和其關鍵性是相依的 — 當工作的關鍵性愈高時，考慮到高關鍵性所代表 的是「高安全性」需求，因此必須增加執行時間來計算更為精確的結果(或是反覆進行多次運算以確保結果的正確性)。在Vestal提出此假設及工作模型後，許多學者與研究團隊陸續投入相關的研究工作，並提出一些相關的衍生模型[Burns2022]，例如假設工作的週期與其關鍵性成反比，也就是當工作的關鍵層級愈高、其週期時間愈短 。例如當車輛從低速改變為高速行駛時，用以保持與前方車輛安全間距的車距調節工作，其工作的執行頻率將會從原本的每秒5次提升為20次(意即將工作週期從200ms 縮短為50ms)，以反映不同關鍵層級時對於車輛行駛的安全性要求。在此情況下，此車距調節工作將僅需要實作單一版本，但可以透過參數或其它設定來滿足不同層級的安全性要求。我們將此假設稱為「關鍵性相依的週期(Criticality-Dependent Period)」。儘管此衍生的假設與模型與Vestal原始的版本已不盡相同，但考量Vestal在此研究領域的創新貢獻，我們後續所指稱的Vestal工作模型，是以其原始發表的版本[Vestal2007]為基礎，再加上其它學者的修改而成[Burns2022]。
Steve Vestal首先證明了傳統的即時工作排程方法，並不適用於MCS工作[Vestal2007]，接著Vestal以Joseph與Pandy所提出的回應時間分析方法(Response Time Analysis，RTA)方法[Joseph1986]為基礎1)，提出了適用於MCS工作的最差情況下的回應時間(Worst-Case Response Time，WCRT)分析迭代式。
\begin{equation} \label{VestalIteration} R_i=\sum\limits_{j:P_j\leq P_i} \left\lceil \dfrac{R_i}{T_i} \right\rceil C_j(L_i) \end{equation}
其中$R_i$代表工作$\tau_i$在最差情況下的回應時間，在計算時先令$R_i=C_i(L_i)$，接著反覆迭代回式子\eqref{VestalIteration}直到$R_i$的數值收斂(意即不再改變)為止，其值即為$\tau_i$的WCRT；但在過程中只要$R_i>D_i$就終止計算，因為這表示該工作將無法成功地排程(意即該工作的WCRT將會超過其截限時間要求)。從概念上來說，此迭代式考慮$\tau_i$在最差情況下的工作實例，針對在其截限時間內所有優先權不小於$P_i$(也就是$\tau_i$的優先權)的任務，計算它們所產生的所有工作實例的執行時間總和(即為$\tau_i$的WCRT)。要特別注意的是在此迭代式子中，每一個優先權大於$\tau_i$的工作$\tau_j$，都會被視為以$\tau_i$所要求的關鍵層級$L_i$來執行，而不是其原本所要求的關鍵層級$L_j$。我們分別考慮兩種情況：(1)$L_i \geq L_j$：在此情況下，具有高優先權但關鍵層級較低的$\tau_j$必須將自己提升到$L_i$的關鍵層級執行，因為兩個不同關鍵層級的工作必須要使用兩者間較高的關鍵層級運行；(2)$L_i < L_j$：在$\tau_i$的優先權與關鍵層級都較低的情況下，我們不必保證其執行能滿足時間限制，除非在最差情況下原本應執行$C_j(L_j)$的$\tau_j$實際上只執行不超過$C_j(L_i)$，$\tau_j$就可以被視為是一個運行在$L_i$關鍵層級的工作。基於以上兩種情況，所以在分析最差情況下的回應時間時，只需要考慮優先權較高的工作都運行在$L_i$關鍵層級的情況。
此迭代式不但可用於計算每個工作的WCRT，還可據以進行工作的可排程性檢測(Schedulability Test)2)。以此可排程性檢測法為基礎，Vestal進一步提出了兩個適用於固定優先權的MCS工作優先權給定(Priority Assignment)方法：
- Period Transform：
以Sha等學者的研究成果[Sha1986]為基礎，將每個高關鍵層級的MCS工作$\tau_i$轉換為$K$個週期性即時工作$\tau_i^1, \tau_i^2, \cdots, \tau_i^K$，其中每個$\tau_i^j$的週期與執行時間皆設定為原本MCS工作的1/$K$ ，後續就可以使用固定優先權的即時工作排程方法(例如RM[Liu1973]加以排程。然而此一方法在找尋適切的$K$的時間複雜度相當高，且還有造成Context Switch次數大幅增加的問題，因此並不具有實際上的應用價值，後續僅有少數研究繼續探討週期轉換的方法於MCS工作排程的應用，例如[FlemingBurns2013 Baruah2013]。
- Optimal Priority Assignment(OPA)：
OPA方法已被Dorin等學者證明為MCS工作最佳(Optimal)的固定優先權給定方法[Dorin2010]3)，且對於一組$n$個MCS工作，僅需$n(n+1)/2$個步驟即可得到可確保MCS工作可排程性的優先權給定方式[Baruah2011b]。OPA方法原本是由英國約克大學的Neil Audsley教授針對即時工作所提出[Audsley1991]，Vestal將其中用以計算工作回應時間的RTA迭代式[Joseph1986]，改為Vestal自己所提出的回應時間分析迭代式。假定每個工作的優先權等級都不會重複4)，將進行$n$個回合從低到高逐次決定所有工作的優先權等級。首先在第一個回合任意挑選一個工作，並將其優先權假定為系統中最低的優先權，接著使用Vestal的回應時間分析迭代式計算其WCRT與進行可排程性檢測；若檢測的結果為可排程，則表示該工作符合所給定的最低優先權等級，否則重新挑選下一個尚未給定優先權的其它工作重複上述過程，直至其可排程為止。一旦所挑選的工作通過可排程性檢測，就表示其在給定最低優先權的情況下能夠順利地被排程。成功地決定了最低先權的工作後，就再進行下一個回合，從尚未給定優先權的工作當中挑選一個給定更高一等級的優先權$n-1$，重複進行前述程序。如此反覆進行，最終就可以為所有工作分配適切的優先權；但若是在某一回合無法將優先權等級成功地指定給工作時，則此組工作是不可排程的(Infeasible)。