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.

Real-time scheduling by queue automata

BREVEGLIERI, LUCA ODDONE;CHERUBINI, ALESSANDRA;CRESPI REGHIZZI, STEFANO
1992

Abstract

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.
Lecture Notes in Computer Science: Formal Techniques in Real-Time and Fault-Tolerant Systems - n. 571
3540550925
INF; formal languages; queue automata; real time scheduling
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11311/569754
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact