A Utilization-based Test for Non-preemptive Gang Tasks on Multiprocessors

Real-time gang task scheduling has received much recent attention due to the emerging trend of applying highly parallel accelerators (e.g., GPU) and parallel programming models (e.g., OpenMP) in many real-time computing domains. However, existing works on gang task scheduling mainly focus on the preemptive scheduling case, which contradicts a bit with the non-preemptive executing nature of applying gang scheduling techniques in practice. In this paper, we present a set of non-trivial techniques that can analyze the schedulability of scheduling a hard real-time sporadic gang task system under non-preemptive GEDF on multiprocessors. A utilization-based schedulability test (first-of-its-kind) is derived, which is shown to be rather effective via experiments. Rather interestingly, for a special case where each gang task becomes an ordinary sporadic task, our developed test is shown by experiments that it improves schedulability by 75% on average upon a state-of-the-art utilization-based test designed for non-preemptive scheduling of ordinary sporadic tasks on multiprocessors.