BibTeX key 'Liu1973' could not be found. Possible typo?

BibTeX key 'BaruahVestal2008' could not be found. Possible typo?

BibTeX key 'ParkKim2011' could not be found. Possible typo?

BibTeX key 'Guan2011' could not be found. Possible typo?

BibTeX key 'EkbergYi2012' could not be found. Possible typo?

BibTeX key 'Yao2014' could not be found. Possible typo?

BibTeX key 'EkbergYi2014' could not be found. Possible typo?

BibTeX key 'BaruahFohler2011' could not be found. Possible typo?

BibTeX key 'Baruah2015' could not be found. Possible typo?

BibTeX key 'Baruah2011a' could not be found. Possible typo?

BibTeX key 'Baruah2012b' could not be found. Possible typo?

BibTeX key 'EkbergYi2012li' could not be found. Possible typo?

BibTeX key 'LipariButtazzo2013' could not be found. Possible typo?

BibTeX key 'Ali2014' could not be found. Possible typo?

BibTeX key 'SuZhu2013' could not be found. Possible typo?

BibTeX key 'Su2013' could not be found. Possible typo?

國立屏東大學即時與嵌入式系統實驗室

Tags: MCS, DP

Citation

@inproceedings{Baruah2011a, 
        IDS={EDF-VD, EDF-VD-1},
	author={S. {Baruah} and V. {Bonifaci} and G. {D\'{a}ngelo} and A. {Marchetti-Spaccamela} and S. {van der Ster} and L. {Stougie}},
	booktitle={19th Annual European Symposium on Algorithms},
	title={{Mixed-Criticality Scheduling of Sporadic Task Systems}},
	year={2011},
	pages={555-566}
}

@article{Baruah2015,
        IDS={EDF-VD-2},
	author={S. {Baruah} and V. {Bonifaci} and G. {D\'{a}ngelo} and H. {Li} and A. {Marchetti-Spaccamela} and S. {Van Der Ster} and L. {Stougie}},
	journal={Journal of the ACM},
	title={{Preemptive Uniprocessor Scheduling of Mixed-Criticality Sporadic Task Systems}},
	Volume = {62},
	Issue ={2},
	Number = {14},
	year={2015},
	month=may}

Earliest Deadline First with Virtual Deadlines(EDF-VD)

Highlights

Dual-Criticality系統中最佳的動態排程方法

在混合關鍵性即時工作的動態優先權排程方法方面，幾乎所有的研究成果都是採用著名的最早截限時間優先(Earliest Deadline First，EDF)[Liu1973]¹⁾方法進行工作排程，其中以美國北卡羅來納大學教堂山分校(UNC)以Sanjoy Baruah教授為首的研究團隊是此研究方向的先驅，他們率先發表了以EDF方法為基礎的排程方法[BaruahVestal2008]。後續Park與Kim[ParkKim2011]則針對Dual-Criticality系統，提出了結合EDF方法與寬裕時間(Slack Time)的排程方法，在確保工作能滿足截限時間的要求之下，儘可能地延後高關鍵層級工作的執行，從而創造出可供低關鍵層級工作執行的寬裕時間。Guan等學者[Guan2011]以及Ekberg與Yi[EkbergYi2012]同樣針對EDF方法與Dual-Criticality系統，進行了更完整的可排程性學理分析，提出了一個為每一個高關鍵層級工作$\tau_i$增設一個假的截限時間$D'_i$的做法(當然$D'_i \leq D_i$)。由於採用了EDF方法，因此這個增設的(較短的)截限時間，將可以讓高關鍵層級工作先於低關鍵層級工作執行。但是當高關鍵層級工作執行超出其低關鍵層級的執行時間預算時，則不允許低關鍵層級工作執行並且讓高關鍵層級工作回復到原本的截限時間。此做法後續由Yao等學者[Yao2014]透過更嚴謹的可排程系學理分析，進一步提出了更佳的假截限時間的計算方法。Ekberg與Yi[EkbergYi2014]則進一步將此做法延伸應用到L-Criticality系統。同樣針對Dual-Criticality系統的非週期性即時工作，Baruah與Fohler進一步，提出了一個非工作保留模式(non-work-conserving)²⁾的排程方法[BaruahFohler2011]，利用處理器的加速以減少工作執行時間進而提升可排程性。

後續美國北卡羅來納大學教堂山分校(UNC)以Sanjoy Baruah教授為首的研究團隊，針對Dual-Criticality系統，提出了一個名為Earliest Deadline First with Virtual Deadlines(EDF-VD)[Baruah2015]的排程方法最為重要。EDF-VD方法將系統內所有的高關鍵層級工作的截限時間都依一個相同的比率進行調整(調整後的新截限時間被稱為Virtual Deadline)，然後再使用EDF方法進行排程。Baruah還進一步提出一個時間複雜度為$\mathcal{O}$($n$)的可排程性測試方法[Baruah2011a]，並在[Baruah2012b]計算出其Speedup Factor為1.333³⁾ ，且證明EDF-VD是Dual-Criticality系統中最佳的排程方法(其Speedup Factor最低)⁴⁾。

後續在EDF相關的排程方法的研究方面，Ekberg與Yi提出了一個針對Dual-Criticality系統的EDF排程方法[EkbergYi2012li]，針對每個關鍵層級分別制定其需求函式，在確保每個關鍵層級中的工作需求不會超出供給的前題下，為每個高關鍵層級工作給定一個調整後的截限時間並使用EDF為所有工作進行排程。Lipari與Buttazzo則同樣針對Dual-Criticality系統提出了一個Reservation-Based的方法[LipariButtazzo2013]，預先為高關鍵層級的工作保留充足的預算(Budget)，只有在高關鍵層級的預算沒有使用完時，才會轉為提供給低關鍵層級使用。Ali與Kim[Ali2014]則提出了一個組合式的方式，與AMC方法類似但在低關鍵層級模式時，讓所有工作透過週期轉換後以RM方法進行排程，一旦切換到高關鍵層級模式時，則改以EDF的策略執行工作。另外，Su等學者[SuZhu2013], [Su2013]則進一步探討如何應用EDF排程方法於週期會變動的工作之上。

Cited By

Plugin Backlinks: 沒找到任何結果。

References

¹⁾

Earliest Deadline First排程方法是在執行階段，依據工作距離其截限時間的遠近決定工作的優先權，較為急迫的工作將取得較高的優先層級；換句話說，EDF方法永遠挑選距離截限時間最近的工作進行排程。

²⁾

Non-Work-Conserving係指可以在系統中有可以被執行的工作時，選擇讓處理器閒置的排程方法。

³⁾

Speedup Factor ($\phi$)可用以比較不同排程方法的優劣，$\phi$的數值愈小就表示該方法愈好。依據定義，Speedup Factor $\phi$係指使用排程方法$\mathcal{A}$時，針對混合關鍵性工作的排程問題，需要將處理器速度調整到何種程度才能夠確保其可排程性。具體來說，若將處理器執行速度視為1，當$\phi=1$時表示無須調整即可確保可排程性；$\phi<1$表示該組工作不但可以被$\mathcal{A}$方法成功地排程且處理器速度還可以放慢至$\phi$；至於$\phi>1$則表示$\mathcal{A}$只有在處理器加速至$\phi$時，才能確保工作的可排程性。

⁴⁾

此最佳性僅針對截限時間等於週期時間的工作，意即$T_i=D_i$ $\forall \tau_i\in\mathcal{T}$。