Français Anglais
Accueil Annuaire Plan du site
Accueil > Production scientifique > Résultat majeur
Production scientifique
Résultat majeur : PROVING FAIRNESS AND IMPLEMENTATION CORRECTNESS OF A MICROKERNEL SCHEDULER
PROVING FAIRNESS AND IMPLEMENTATION CORRECTNESS OF A MICROKERNEL SCHEDULER
05 mai 2009

Matthias Daum , Jan Dörrenbächer et Burkhart Wolff. Journal of Automated Reasoning (JAR), 2009.
We report on the formal proof of a microkernel’s key property, namely that its multi-priority process scheduler guarantees progress, i.e., strong fairness. The proof architecture links a layer of behavioral reasoning over system-trace sets with a concrete, fairly realistic implementation written in C. Our microkernel provides an infrastructure for memory virtualization, for communication with hardware devices, for processes (represented as a sequence of assembly instructions, which are executed concurrently over an underlying, formally defined processor), and for inter-process communication (IPC) via synchronous message passing. The kernel establishes process switches according to IPCs and timer-events; the scheduling of process switches, however, follows a hierarchy of priorities, favoring, e.g., system processes over application processes over maintenance processes. Besides the quite substantial models developed in Isabelle/HOL and the formal clarification of their relationship, we provide a detailed analysis what formal requirements a microkernel imposes on the key ingredients (hardware, timers, machine-dependent code) in order to establish the correct operation of the overall system. On the methodological side, we show how early modeling with foresight to the later verification has substantially helped our project.

In: Journal of Automated Reasoning (JAR), DOI: 10.1007/s10817-009-9119-8, published electronically, print version to appear. Springer, 2009.

Activités de recherche
  [aucun]

Equipe
  ° Test Formel et Exploration de Systèmes

Contact
  ° WOLFF Burkhart
Résultats majeurs
BEST PAPER AWARD: SELF-STABILIZING DISTRIBUTED STABLE MARRIAGE
05 novembre 2017
SSS 2017, M. Laveau, G. Manoussakis, J. Beauquier, T. Bernard, J. Burman, J. Cohen, and L. Pilard

INFORMATION-GEOMETRIC OPTIMIZATION ALGORITHMS: A UNIFYING PICTURE VIA INVARIANCE PRINCIPLES
02 mai 2017
Yann Ollivier, Ludovic Arnold, Anne Auger, Nikolaus Hansen - JMLR 18(18):1−65, 2017.

FORMAL MUTATION TESTING FOR CIRCUS
21 avril 2016
Alex Donizeti Betez Alberto, Ana Cavalcanti, Marie-Claude Gaudel, Adenilso Simao Journal of Infor

CELL-CELL COMMUNICATION ENHANCES THE CAPACITY OF CELL ENSEMBLES TO SENSE SHALLOW GRADIENTS DURING MORPHOGENESIS
09 février 2016
D. Ellison, A. Mugler, M.D. Brennan, S.H. Lee, R.J. Huebner, E.R. Shamir, L.A. Woo, J. Kim, P. Amar,

COMPUTING WITH SYNTHETIC PROTOCELLS
13 mai 2015
Alexis Courbet, Franck Molina and Patrick Amar