Scheduling parallel real-time tasks on multi-core processors

Massively multi-core processors are rapidly gaining market share with major chip vendors offering an ever-increasing number of cores per processor. From a pro-gramming perspective, the sequential programming model does not scale very well for such multi-core systems. Paral-lel programming models such as OpenMP present promis-ing solutions for more effectively using multiple processor cores. In this paper, we study the problem of scheduling periodic real-time tasks on multiprocessors under the fork-join structure used in OpenMP. We illustrate the theoretical best-case and worst-case periodic fork-join task sets from a processor utilization perspective. Based on our observa-tions of these task sets, we provide a partitioned preemptive fixed-priority scheduling algorithm for periodic fork-join tasks. The proposed multiprocessor scheduling algorithm is shown to have a resource augmentation bound of 3.42, which implies that any task set that is feasible on m unit speed processors can be scheduled by the proposed algo-rithm on m processors that are 3.42 times faster.