Mixed-criticality Scheduling of Sporadic Task Systems

Baruah, Sanjoy; Bonifaci, Vincenzo; D'Angelo, Gianlorenzo; Marchetti-Spaccamela, Alberto; van der Ster, Suzanne; Stougie, Leen

doi:10.1007/978-3-642-23719-5_47

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

会議論文

Mixed-criticality Scheduling of Sporadic Task Systems

MPS-Authors

/persons/resource/persons44160

Bonifaci, Vincenzo
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

公開されているフルテキストはありません

付随資料 (公開)

There is no public supplementary material available

引用

Baruah, S., Bonifaci, V., D'Angelo, G., Marchetti-Spaccamela, A., van der Ster, S., & Stougie, L. (2011). Mixed-criticality Scheduling of Sporadic Task Systems. In C., Demetrescu, & M. M., Halldórsson (Eds.), Algorithms - ESA 2011 (pp. 555-566). Berlin: Springer. doi:10.1007/978-3-642-23719-5_47.

引用: https://hdl.handle.net/11858/00-001M-0000-0010-1259-0

要旨

We consider the scheduling of mixed-criticality task systems, that is, systems where each task to be scheduled has multiple levels of worst-case execution time estimates. We design a scheduling algorithm, EDF-VD, whose effectiveness we analyze using the processor speedup metric: we show that any 2-level task system that is schedulable on a unit-speed processor is correctly scheduled by EDF-VD using speed $\phi$; here $\phi < 1.619$ is the golden ratio. We also show how to generalize the algorithm to $K > 2$ criticality levels. We finally consider 2-level instances on $m$ identical machines. We prove speedup bounds for scheduling an independent collection of jobs and for the partitioned scheduling of a 2-level task system.