Timing analysis for fixed-priority scheduling of hard real-time systems

This paper presents a timing analysis for a quite general hard real-time periodic task set on a uniprocessor using fixed-priority methods. Periodic tasks are composed of serially executed subtasks, where each subtask is characterized by an execution time, a fixed priority and a deadline. A method for determining the schedulability of each task and subtask is presented along with its theoretical underpinnings. This method can be used to analyze the schedulability of any task set on a uniprocessor whose priority structure can be modeled as serially executed subtasks, which can lead to a very complex priority structure. Important examples include task sets that involve interrupts, certain synchronization protocols, certain precedence constraints, nonpreemptible sections, and some message-passing systems. The method is illustrated by a robotics example.>