On-line real-time task scheduling on partitionable multiprocessors

Multiprocesssor systems have emerged as an important computing means for real-time applications and have received increasing attention than before. However until now, little research has been done on the problem of on-line scheduling of parallel tasks with deadlines in partitionable multiprocessor systems. In this paper, we propose a new on-line scheduling algorithm, called Deferred Earliest Deadline First (DEDF) for such systems. The main idea of the DEDF algorithm is to defer the scheduling as late as possible, so that a set of jobs is scheduled at a time instead of one at a time. For processor allocation using DEDF, we have introduced a new concept-Available Time Window (ATW). By using ATW the system utilization can be improved and thereby enabling the system to meet the deadline of more number of tasks. Simulation results for a hypercube indicate that the DEDF algorithm performs significantly better than the earlier proposed Buddy/RT and Stacking algorithms for a wide range of work loads.