AN OPTIMAL ONLINE SCHEDULING ALGORITHM FOR OVERLOADED UNIPROCESSOR REAL-TIME SYSTEMS

Consider a real-time system in which every task has a value that it ob tains only if it completes by its deadline. The problem is to design a n on-line scheduling algorithm (i.e., the scheduler has no knowledge o f a task until it is released) that maximizes the guaranteed value obt ained by the system. When such a system is underloaded (i.e., there ex ists a schedule for which all tasks meet their deadlines), Dertouzos [ Proceedings IFIF Congress, 1974, pp. 807-813] showed that the earliest deadline first algorithm will achieve 100% of the possible value. Loc ke [Ph.D. thesis, Computer Science Dept., Carnegie-Mellon Univ., Pitts burgh, PA] showed that earliest deadline first performs very badly, ho wever, when the system is overloaded, and he proposed heuristics to de al with overload. This paper presents an optimal on-line scheduling al gorithm for overloaded uniprocessor systems. It is optimal in the sens e that it gives the best competitive ratio possible relative to an off -line scheduler.