A NEW APPROACH FOR SCHEDULING OF PARALLELIZABLE TASKS IN REAL-TIME MULTIPROCESSOR SYSTEMS

In a parallelizable task model, a task can be parallelized and the com ponent tasks can be executed concurrently on multiple processors. We u se this parallelism in tasks to meet their deadlines and also obtain b etter processor utilisation compared to non-parallelized tasks. Non-pr eemptive parallelizable task scheduling combines the advantages of hig her schedulability and lower scheduling overhead offered by the preemp tive and non-preemptive task scheduling models, respectively. We propo se a new approach to maximize the benefits from task parallelization. It involves checking the schedulability of periodic tasks (if necessar y, by parallelizing them) off-line and run-time scheduling of the sche dulable periodic tasks together with dynamically arriving aperiodic ta sks. To avoid the run-time anomaly that may occur when the actual comp utation time of a task is less than its worst case computation time, w e propose efficient run-time mechanisms. We have carried out extensive simulation to study the effectiveness of the proposed approach by com paring the schedulability offered by it with that of dynamic schedulin g using Earliest Deadline First (EDF), and by comparing its storage ef ficiency with that of the static table-driven approach. We found that the schedulability offered by parallelizable task scheduling is always higher than that of the EDF algorithm for a wide variety of task para meters and the storage overhead incurred by it is less than 3.6% of th e static table-driven approach even under heavy task loads.