Design and Analysis of Hard Real-Time Applications in a Uniprocessor Environment
Jiang Zhu, Theodore Gyle Lewis, Weldon Jackson, Russel L. Wilson · 1993
We examine the problem of designing and analyzing hard real-time applications with deterministic behavior in a uniprocessor environment. We introduce a design diagram for capturing requirements. A hard real-time application under such a design is defined by a control flow network and a data flow network. The control flow network is driven by timers and external events where timers are semantic specifications and may or may not have physical correspondences in implementation. The advantage of our design diagram is that it is quite intuitive, and yet it can be automatically analyzed for scheduleability. We present a systematic method for deriving a set of precedence-constrained periodic tasks from a design diagram which together meet the requirements. Sporadic tasks are transformed into their equivalent behavior if and only if the periodic task set derived from its design can be scheduled on one processor such that both the timing and precedence constraints are met. Such a task set is said to be scheduleable. We study the scheduling problem derived from the design diagram which consists of a set of periodic tasks and a directed acyclic graph defining the precedence constraints. The question is whether such a periodic task set is sheduleable. We give one optimal preemptive and one optimal non-preemptive scheduling algorithm. The latter is with respect to those algorithms which do not idle the processor as long as there are tasks ready to execute. We compare various scheduling methods through an example hard real-time application from [1]. Key Words: real-time, hard real-time, hard real-time system design, real-time control, scheduling, real-time scheduling, hard real-time scheduling.