SNS: A Simple Model for Understanding Optimal Hard Real-Time Multiprocessor Scheduling
Greg Levin, Caitlin Sadowski, Ian Pye, Scott Brandt · 2009
We consider the problem of optimal real-time schedul-ing of periodic tasks for multiprocessors. A number of recent papers have used the notion of fluid scheduling to guarantee optimality and improve performance. In this pa-per, we examine exactly how fluid scheduling techniques overcome inherent problems faced by greedy scheduling algorithms such as EDF. Based on these foundations, we describe a simple and clear optimal scheduling algorithm which serves as a least common ancestor to other recent al-gorithms. We provide a survey of the various fluid schedul-ing algorithms in this novel context. 1.