LIP6, INRIA project Regal

Bossa - A Framework for Scheduler Development



What is Bossa ?

Emerging applications, such as multimedia applications and real-time applications, have increasingly specialized scheduling requirements. Nevertheless, developing a new scheduling policy and integrating it into an existing OS is complex, because it requires understanding (often implicit) OS conventions. Bossa is a kernel-level event-based framework to facilitate the implementation and integration of new scheduling policies. Advantages of Bossa are: Concretely, a complete Bossa kernel comprises three parts: We have developed a complete Bossa kernel derived from the Linux 2.4.24 kernel.

Process schedulers

The following are some sample process schedulers that have been written in Bossa.
Linux
A scheduler that employs a mix of round-robin and priority-based scheduling.
(based on Linux kernel version 2.4.24 without multiprocessing support). Updated November 28, 2004.

BVT
Borrowed Virtual Time scheduling by Duda and Cheriton. This is for use with the version of Bossa based on Linux 2.4.24. Updated April 11, 2005.

Best
Best scheduling by Banachowski and Brandt. This is a best-effort policy that tries to infer process periods and give priority to periodic processes. This is for use with the version of Bossa based on Linux 2.4.24. Updated November 28, 2004.

The following policies are for use with the version of Bossa providing high-resolution timers:

Earliest Deadline First
This scheduler only implements an EDF algorithm. It does not treat ordinary processes, and thus can only be used in a hierarchy with at least one other process scheduler that manages ordinary processes. One possible hierarchy is the fixed priority virtual scheduler defined below with Linux and EDF, such that EDF has a higher priority than Linux. This version is for use with the MPlayer demo as described in the Bossa lab. Updated November 28, 2004.

Rate Monotonic
This policy uses high-resolution timers to maintain the period. The period and worst-case execution time are provided in terms of numbers of cycles. This policy must be used in a hierarchy. Last updated November 28, 2004.

Modular scheduling policies
A collection of policies written using the modular Bossa Nova language are available here. Last modified December 28, 2004.

Virtual schedulers

When particular classes of applications require specific scheduling properties, a mechanism is needed to manage the interaction between multiple scheduling policies. Bossa permits the development of a virtual scheduler, a scheduler that controls other schedulers. Virtual schedulers can be composed in a hierarchy. Some examples are:
Fixed priority
A virtual scheduler that elects a child scheduler based on static priority values. Last updated November 28, 2004.

Proportional virtual schedule
A virtual scheduler that allocates each child scheduler a minimum proportion of the virtual scheduler's CPU time. Last updated November 28, 2004.

 

Documentation

Miscellaneous information about the Bossa language can be found in the release notes (pdf).

Availability

The Bossa implementation comprises the following:

The following are some tools for use with Bossa:


Demos

The following are some demos that use Bossa. These are for use with Linux 2.4 only.
Hierarchy demo
A simple program that illustrates the construction and use of a hierarchy.
Hourglass
Hourglass is a program written by John Regehr that allows one to observe scheduling behavior. This version has been modified for use with Bossa. The original version is available here. Note that we use version 0.5 of Hourglass, which is not the latest version. This only works with the Bossa compiler dated December 20, 2003 and later. This was most recently updated November 28, 2004.

Hourglass makes graphs using jgraph, which can be obtained here.

Lab
A collection of small projects using Bossa, suitable for a laboratory course.
Mplayer
A version of MPlayer for use with Bossa and the Earliest Deadline First policy. More information about this demo is contained in the Bossa lab. The official version of MPlayer may be found here. Last updated November 28, 2004.

Personnel

The following people worked on Bossa:
Previous contributors are Arnaud Denoual, Hervé Duchesne, Asger Henriksen, Mads Hvelplund, Varun Kohli, Luciano Porto Barreto, and Rickard A. Åberg.


Selected papers about Bossa

BibTeX
  • Formal methods meet Domain Specific Languages
    Jean-Paul Bodeveix, Mamoun Filali, Julia Lawall, and Gilles Muller.
    Fifth International Conference on Integrated Formal Methods, Lecture Notes in Computer Science, volume 3771, pp. 187-206, 29 November - 2 December 2005 in Eindhoven, The Netherlands.

  • A Framework for Simplifying the Development of Kernel Schedulers: Design and Performance Evaluation.
    Gilles Muller, Julia Lawall, and Herve Duchesne.
    HASE'05 - The 9th IEEE International Symposium on High Assurance Systems Engineering Conference, pp. 56-65, Heidelberg, Germany, October, 2005.

  • Bossa Nova: Introducing modularity into the Bossa domain-specific language.
    Julia L. Lawall, Herve Duchesne, Gilles Muller, and Anne-Francoise Le Meur.
    Fourth International Conference on Generative Programming and Component Engineering (GPCE'05), Lecture Notes in Computer Science, volume 3676, pp. 78-93, Tallinn, Estonia. September, 2005. (slides)

  • On Designing a Target-Independent DSL for Safe OS Process-Scheduling Components
    J.L. Lawall, A.-F. Le Meur, and G. Muller.
    Third International Conference on Generative Programming and Component Engineering (GPCE'04), Vancouver, Canada, October 2004. pages 436-455. (
    slides, Springer version).

  • Constructing Component-Based Extension Interfaces in Legacy Systems Code
    G. Muller, J.L. Lawall, J.-M. Menaud, and M. Sudholt
    11th ACM SIGOPS European Workshop, Leuven, Belgium, September 2004. pages 80-85 (slides)

  • Language Design for Implementing Process Scheduling Hierarchies (Invited Paper)
    J.L. Lawall, G. Muller, and H. Duchesne
    ACM SIGPLAN 2004 Symposium on Partial Evaluation and Program Manipulation - PEPM'04, Verona, Italy, August 2004. pages 80-91. (slides)

  • On the automatic evolution of an OS kernel using temporal logic and AOP
    R.A. Åberg, J.L. Lawall, M. Südholt, G. Muller, A.-F. Le Meur
    Automated Software Engineering 2003 (ASE 2003), Montreal, Canada, October, 2003, pages 196-204. slides

  • Capturing OS expertise in an Event Type System: the Bossa experience.
    J. Lawall, G. Muller, and L.P. Barreto.
    In ACM SIGOPS European Workshop 2002 (EW'2002 ), Saint-Emilion, France, September 2002. pages 54-61.

  • Bossa: a Language-based Approach for the Design of Real Time Schedulers
    L. Barreto and G. Muller.
    In RTS'2002, pp. 19-31, Paris, France, March 2002.

  • Towards Robust OSes for Appliances: A New Approach Based on Domain-Specific Languages
    G. Muller, C. Consel, R. Marlet, L.P. Barreto, F. Mérillon, and L. Réveillère.
    In ACM SIGOPS European Workshop 2000 (EW'2000), Denmark, September 2000.

  • Architecturing software using a methodology for language development.
    C. Consel and R. Marlet.
    In Proceedings of the 10th International Symposium on Programming Languages, Implementations, Logics and Programs PLILP/ALP '98), pp. 170-194, Pisa, Italy, September 1998.

  • Papers using Bossa

  • BOSSA et le Concert Virtuel Réparti, intégration et paramètrage souple d'une politique d'ordonnancement spécifique pour une application multimédia distribuée
    J. Cordry, N. Bouillot, and S. Bouzefrane.
    13th International Conference on Real-Time Systems, Paris, France, April 2005.


  • Acknowledgements

    The development of Bossa has been supported in part by France Telecom under the grant CTI 991B726, by a Microsoft Embedded Systems IFP Award, and by the Danish Research Council.


    Last modified: July 27, 2009 - Contact:
    Julia.Lawall@inria.fr