國立屏東大學 即時與嵌入式系統實驗室
Adaptive Mixed-Criticality (AMC) Scheduling (可調適混合關鍵性排程法)
Highlights
- MCS領域的第一篇論文
- FP工作回應時間迭代分析式
- OPA最佳優先權給定方法
- Priority Transformed
AMC方法[Baruah2011b]則同樣是針對Dual-Criticality MCS所提出,在系統開始時會先設定為低關鍵性執行模式,此時接受所有關鍵層級的工作執行(當然會挑選優先權最高者加以執行);當一個高關鍵層級的工作$\tau_h$執行超過其低關鍵層級的WCET(也就是$C_h(L_{low})$)仍未完成時,系統就會切換為高關鍵性執行模式,不再接受任何低關鍵層級的工作(不論其優先權為何),只會從高關鍵層級的工作中挑選優先權最高者執行1)。與SMC相比,只要系統的關鍵層級未提升以前,AMC可以讓低關鍵層級的工作將有較多的機會被執行。
ACM排程方法為MCS工作排程研究,提供了一個嶄新的方向,後續有許多學者投入此方法的強化或延伸,例如[Zhao2013a], [Zhao2013b], [BurnsDavis2014], [Huang2014a], [Ali2014], [FlemingBurns2013], [Baruah2013], [Chen2016],其中Fleming與Burns的研究則是從原本考慮的Dual-Criticality MCS,延伸應用至具有兩個以上多個關鍵層級的系統[FlemingBurns2013]。Chen等學者[Chen2016]則為工作提供不同關鍵層級時的優先權(換句話說,同一個工作在不同關鍵層級時可以使用不同的優先權),以及另外針對關鍵性執行模式切換時,再使用另一個模式轉換時的優先權。透過在[Baruah2013] {[Chen2016]的此種做法,將可以讓工作使用AMC方法排程時,得到更好的可排程性保證。除了上述方法外,亦有學者利用工作執行時的Slack Time來執行其它關鍵層級的工作[Niz2009], [Huang2012], [Niz2013], [NizPhan2014],或是結合預算(Budget)的概念,來管理不同關鍵層級工作可使用處理器的時間配額[Neukirchner2013a], [Neukirchner2013b], [Hu2016b], [Volp2015], [GuEaswaran2016],這些方法都有助於提升了排程的可預測性。
但是AMC方法存在著當切換到高關鍵性執行模式後(當高關鍵層級的工作執行超出了其低關鍵層級的執行時間時),就不允許系統降回至低關鍵層級運行,導致低關鍵層級的工作再也無法被執行的缺點,因此UNC的Baruah教授和約克大學的Burns教授共同提出了ACM+方法[Bate2017],為原始的AMC方法增加了Bailout Protocol(贖回協定),允許當系統切換到高關鍵性執行模式後,還可在未來當處理器閒置(意即沒有待執行的工作時)再切換回低關鍵層級的執行模式,讓低關鍵層級的工作能得到更多使用處理器的機會。AMC+不但能確保原本對高關鍵層級工作的可排程性保證,同時也是更符合實際應用的真實情境。目前此方面最新的研究成果是英國約克大學的研究團隊所提出的(Compensating Adaptive Mixed Criticality Scheduling,C-AMC)[Davis2022],修改了原本AMC方法進入高關鍵層級運行時,禁止低關鍵層級工作進入系統的做法。原始的AMC方法,在系統進入高關鍵層級運行時,為確保高關鍵層級的工作能夠順利完成,因此禁止低關鍵層級工作進入系統。但這有可能造成維持系統基本功能的一些低關鍵層級工作無法執行,導致系統無法正常運行。C-AMC為低關鍵層級的工作增加只提供基本但能維持系統正常運行的精簡版本,並在系統進入高關鍵層級時,不再禁止低關鍵層級的工作執行,但改為執行它們的較為精簡的實作版本以降低系統整體的負載,讓所有的工作(含高關鍵層級與低關鍵層級的工作)都能在系統在高關鍵層級時仍能維持正常地運行。