An Optimal Scheduling Algorithm with a Competitive Factor for Real-Time Systems

We consider real-time systems in which the value of a task is proportional to its computation time. The system obtains the value of a given task if the task completes by its deadline. Otherwise, the system obtains no value for the task. When such a system is underloaded i.e. there exists a schedule for which all tasks meet their deadlines, Dertouzos 6 showed that the earliest deadline first algorithm will achieve 100 of the possible value. We consider the case of a possibly overloaded system and present an algorithm which 1. behaves like the earliest deadline first algorithm when the system is underloaded. 2. obtains at least 14 of the maximum value that an optimal clairvoyant algorithms could obtain even when the system is overloaded. We implement our algorithm with an amortized cost of Olog n time per task, where n bounds the number of tasks in the system at any instant.