A New Performance Measure for Scheduling Independent Real-Time Tasks

Abstract

A new performance measure for scheduling tasks in hard real-time systems is proposed and analyzed. The proposed measure is the maximum normalized task flowtime over all tasks, called the system hazard, where the normalized flowtime of a real-time task is the flowtime of the task divided by the period between its arrival time and deadline. The system hazard is a better measure than simply meeting task deadlines because it also indicates how early tasks as a whole can be completed before their deadlines. For a single processor with only independent periodic tasks, optimal scheduling algorithms with respect to the system hazard are derived for both static and dynamic cases. Two best bounds of processor utilization for these optimal algorithms are also computed.