Virtual Gang Scheduling of Parallel Real-Time Tasks
Waqar Ali1,a, Rodolfo Pellizzoni2 and Heechul Yun1,b
1University of Kansas, Lawrence, USA
awali@ku.edu
bheechul.yun@ku.edu
2University of Waterloo, Ontario, CA
rpellizz@uwaterloo.ca
ABSTRACT
We consider the problem of executing parallel realtime tasks according to gang scheduling on a multicore system in the presence of shared resource interference. Specifically, we consider sets of gang-tasks with precedence constraints in the form of a DAG. We introduce the novel concept of a virtual gang: a group of parallel tasks that are scheduled together as a single entity. Employing virtual gangs allows us to tightly bound the effect of shared resource interference. It also transforms the original, complex scheduling problem into a form that can be easily implemented and is amenable to exact schedulability analysis, further reducing pessimism. We present and evaluate both optimal and heuristic methods for forming virtual gangs based on a known interference model and while respecting all precedence constraints among tasks. When precedence constraints are not considered, we also compare our approach against existing response-time analysis for globally scheduled gang-tasks, as well as general parallel tasks. The results show that our approach significantly outperforms state-of-the-art multicore schedulability analyses when shared-resource interference is considered. Even in the absence of interference, it performs better than the state-ofthe- art for highly parallel tasksets.
Keywords: Real-Time, Gang Scheduling, Precedence Constraints, Safety Critical, Parallel Tasks.
