Design and Timing Guarantee for Non-Preemptive Gang Scheduling

Due to its efficient and predictable utilization of modern computing units, recent studies have paid attention to gang scheduling in which all threads of a real-time task should be concurrently executed on different processors. However, the studies have been biased to preemptive gang scheduling, although non-preemptive gang scheduling (NPG) is practical for inherently non-preemptive tasks and tasks that incur large preemption overhead. In this paper, focusing on a new type of priority-inversion incurred by NPG, we design a generalized NPG framework, called NPG∗, under which each task has an option to allow or disallow the situation that incurs the priority-inversion specialized for NPG. To demonstrate the effectiveness of NPG∗ in terms of timing guarantees, we target NPG∗-FP by employing fixed-priority scheduling (FP) as a prioritization policy, and develop the first NPG∗-FP schedulability test and its improved version under a given assignment of the allowance/disallowance option to each task. We then develop the optimal allowance/disallowance assignment algorithm, which finds an assignment (if exists) that makes a target task set schedulable by the proposed schedulability tests. Via simulations, we demonstrate that the assignment algorithm associated with the schedulability tests for NPG∗-FP can find a number of additional schedulable task sets, each of which has not been covered by the traditional NPG framework.