Scheduling with Augmented BNF Grammars
S.CRESPI REGHIZZI, L. BREVEGLIERI, A. CHERUBINI
IBP-Litp
1996/28:
Rapport de Recherche Litp /
Litp research reports
19 pages - Juillet/July 1996 -
Document en anglais.
PostScript :
Ko /Kb
Titre / Title: Scheduling with Augmented BNF Grammars
Résumé : Résumé : Les grammaires ABNF (ou algébriques augmentées), un formalisme récent, sont ici proposées pour la définition des séquences ou langages d'ordonnancement. Ces grammaires engendrent des mots par des dérivations gauches qui peuvent procéder en largeur ou en profondeur. Les machines correspondantes possèdent une mémoire organisée en une ou plusieurs bandes FIFO ou LIFO totalement ordonnées. Les exemples comprennent les politiques d'ordonnancement plus courantes : FIFO (ou langage AntiDyck), temps-partagé, ordonnancement par priorité statique et dynamique, mutex et lecteurs/écrivens. Un lemma d'itération permet de prouver que deux queues sont nécessaires pour le langage des services prioritaires. Les exemples se relient l'un à l'autre par le recours aux propriétés de clôture de la classe ABNF.
Abstract : Abstract : The recently introduced class of ABNF grammars is here applied to scheduling problems. ABNF grammars derivations proceed left-to-right and breadth-first of depth-first. Their recognizers are equiped with a finite, ordered set of FIFO or LIFO tapes. The examples cover all basic scheduling disciplines : FIFO, time-slicing, static and dynamic priorities, mutex, readers/writers. A pumping lemma is used to prove that two queues are needed for priority services. The examples are systematically presented, by building on top of the previous ones by means of closure properties of the ABNF family.
Publications
internes Litp 1996 /
Litp research reports
1996