ALGORITHMS AND OPTIMALITY OF SCHEDULING SOFT APERIODIC REQUESTS IN FIXED-PRIORITY PREEMPTIVE SYSTEMS

In this paper, we investigate the problem of scheduling soft aperiodic requests in systems where periodic tasks are scheduled on a fixed-pri ority, preemptive basis. First, we show that given any queueing discip line for the aperiodic requests, no scheduling algorithm can minimize the response time of every aperiodic request and guarantee that the de adlines of the periodic tasks are met when the periodic tasks are sche duled on a fixed-priority, preemptive basis. We then develop two algor ithms: Algorithm L is locally optimal in that it minimizes the respons e time of the aperiodic request at the head of the aperiodic service q ueue. Algorithm G is globally optimal in that it completes the current backlog of work in the aperiodic service queue as early as possible.