Invited application paper: language design for implementing process scheduling hierarchies

ABSTRACT

Standard operating systems provide only a single fixed scheduler, which does not meet all possible application scheduling needs. More flexibility can be achieved using a hierarchy of schedulers, allowing multiple schedulers to coexist in a single operating system (OS). Bossa is a framework for facilitating the implementation and deployment of OS process schedulers. In this paper, we describe the features of Bossa that enable the creation and management of a scheduling hierarchy. These features include a domain-specific language for implementing schedulers and a type system for describing requirements on scheduler behavior. The use of the domain-specific language eases scheduler development and enables scheduler verification. We have found that the approach allows programmers, even students who are not kernel or scheduling experts, to easily and safely implement and deploy schedulers that meet specific application needs.

REFERENCES

• 1: R. A. Åberg, J. L. Lawall, M. Südholt, G. Muller, and A.-F. Le Meur. On the automatic evolution of an OS kernel using temporal logic and AOP. In Proceedings of the 18th IEEE International Conference on Automated Software Engineering (ASE 2003), pages 196--204, Montreal, Canada, Oct. 2003. IEEE.
• 2: L. P. Barreto and G. Muller. Bossa: a language-based approach to the design of real-time schedulers. In 10th International Conference on Real-Time Systems (RTS'2002), pages 19--31, Paris, France, Mar. 2002.
• 3: G. M. Candea and M. B. Jones. Vassal: Loadable scheduler support for multi-policy scheduling. In Proceedings of the 2nd USENIX Windows NT Symposium, pages 157--166, Seattle, WA, Aug. 1998.
• 4: Bryan Ford , Sai Susarla, CPU inheritance scheduling, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.91-105, October 29-November 01, 1996, Seattle, Washington, United States
• 5: Paolo Gai , Luca Abeni , Massimiliano Giorgi , Giorgio Buttazzo, A New Kernel Approach for Modular Real-Time Systems Development, Proceedings of the 13th Euromicro Conference on Real-Time Systems, p.199, June 13-15, 2001
• 6: Robert Glück , Andrei V. Klimov, Occam's Razor in Metacompuation: the Notion of a Perfect Process Tree, Proceedings of the Third International Workshop on Static Analysis, p.112-123, September 22-24, 1993
• 7: J. Lawall, G. Muller, and L. P. Barreto. Capturing OS expertise in a modular type system: the Bossa experience. In ACM SIGOPS European Workshop 2002 (EW'2002), pages 54--61, Saint-Emilion, France, Sept. 2002.
• 8: J. L. Lawall, A.-F. Le Meur, and G. Muller. On designing a target-independent DSL for safe OS process-scheduling components. In Third International Conference on Generative Programming and Component Engineering (GPCE'04), Oct. 2004. To appear.
• 9: F. Nielson. A denotational framework for data flow analysis. Acta Informatica, 18:265--287, 1982.
• 10: John David Regehr , John A. Stankovic, Using hierarchical scheduling to support soft real-time applications in general-purpose operating systems, 2001
• 11: John Regehr , John A. Stankovic, HLS: A Framework for Composing Soft Real-Time Schedulers, Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS'01), p.3, December 03-06, 2001

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Specialized application languages

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling
      D.4.7 Organization and Design

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.1 Specifying and Verifying and Reasoning about Programs

General Terms:
Languages, Verification

Keywords:
domain-specific languages, operating system extension, process scheduling, scheduling hierarchies, verification