AN OPTIMAL ALGORITHM FOR SCHEDULING SOFT APERIODIC TASKS IN DYNAMIC-PRIORITY PREEMPTIVE SYSTEMS

This paper addresses the problem of jointly scheduling tasks with both hard and soft real-time constraints. We present a new analysis applic able to systems scheduled using a priority preemptive dispatcher, with priorities assigned dynamically according to the EDF policy. Further, we present a new efficient on-line algorithm (the acceptor algorithm) for servicing a periodic work load. The acceptor transforms a soft ap eriodic task into a hard one by assigning a deadline. Once transformed , aperiodic tasks are handled in exactly the same way as periodic task s with hard deadlines. The proposed algorithm is shown to be optimal i n terms of providing the shortest aperiodic response time among fixed- and dynamic-priority schedulers. It always guarantees the proper exec ution of periodic hard tasks. The approach is composed of two parts: a n off-line analysis and a run-time scheduler. The off;line algorithm r uns in pseudopolynomial time O(mn), where n is the number of hard peri odic tasks and in is the hyperperiod/min deadline.