MOCA: a multiprocessor on-line competitive algorithm for real-time system scheduling

We study competitive on-line scheduling in multiprocessor real-time environments. In our model, every task has a deadline and a value that it obtains only if it completes by its deadline. A task can be assigned to any processor, all of which are equally powerful. The problem is to design an on-line scheduling algorithm (i.e. one in which the scheduler has no knowledge of a task unit it is released) with worst-case guarantees as to the total value obtained by the system. We study systems with two or more processors. We present an inherent limit on the best competitive guarantee that any on-line parallel real-time scheduler can give. Then we present a competitive algorithm that achieves a worst-case guarantee which is within a small factor from the best possible guarantee in many cases. These are the most general results yet known for competitive scheduling of multiprocessor real-time systems.