Efficient on-line schedulability tests for priority driven real-time systems

Many computer systems, such as those for open system environments or multimedia services, need an efficient schedulability test for online admission control of new jobs. Although various polynomial-time schedulability tests have been proposed, they often fail to decide the schedulability of the system precisely when the system is heavily loaded. This paper presents efficient online schedulability tests which are are shown to be more precise and efficient than any existing polynominal-time schedulability tests. Moreover, our proposed tests can be used for the multiframe model, where a task may have different computation times in different periods. We show the performance of the proposed schedulability tests in several simulation experiments.