The power of migration in multi-processor scheduling of real-time systems
Gilad Koren, Amihood Amir, Emanuel Dar · 1998
In this paper we study the performance of off-line multiprocessor real-time schedules that allows task migration compared to those that forbid migration. We consider an off-line scheduling problem in which a given collection of tasks each with release time, computation time and deadline are to be run on a multi-processor system. A preemptive schedule allows the execution of a task to be temporarily suspended and resumed at a later time. A migrative schedule allows the task to resume on any processor whereas the non-migrative schedule allows the task to resume only on the processor it was initially started. A schedule value is the summation of all the values of all the tasks that were completed by their deadlines. In this paper we assume that a task value is proportional to its computation time. We present lower and upper bound results. For a system with n processors, We construct a non-migrative schedule that is guaranteed to achieve at least 1 \\Gamma \\Gamma 1 \\Gamma 1 2n...