Real-time scheduling by queue automata

Real-time schedulers are modelled by finite-state transition systems using FIFO queues as auxiliary memory. The intuitive notion of hard real time is related to the definition of quasi-real-time behaviour of an automaton. Then, starting with simple schedulers for independent tasks, a modular approach to the design of schedulers (FIFO, static priority based, preemptive, dynamic priorities) is presented. This is based on recent results on recognition power and closure properties of quasi-real-time queue automata w.r.t. intersection, shuffle and reverse homomorphism. The treatment of readers-writers schedulers is compared with recent proposals based on intersections of context-free languages. Possible developments are in the conclusion.