RATE-MONOTONIC SCHEDULING FOR HARD-REAL-TIME SYSTEMS

Hard-real-time computing systems are widely used in our society, for e xample, in nuclear and industrial plants, telecommunications, avionics and robotics. In such systems, almost all tasks occur infinitely ofte n and have time deadlines, namely, their correctness relies not only o n their logical results, but also on the time at which the results are available. A scheduling algorithm specifies an order in which all the tasks are to be executed, in a way that all the time deadlines are me t. This paper provides a review on deterministic scheduling algorithms for hard-real-time systems, focusing mainly on fixed priority, preemp tive scheduling of periodic tasks on a single processor and, in partic ular, on the Rate-Monotonic algorithm. After presenting some basic res ults, several generalisations, aimed at relaxing some constraints and facing more realistic cases, are described. Issues covered include uni processor and multiprocessor systems, periodic and non-periodic tasks, restricted and arbitrary deadlines, fixed and dynamic priorities, ind ependent and synchronised tasks, as well as fault-free and fault-toler ant systems.