posted by Christophe Augier on Thu 8th Jul 2004 18:52 UTC
IconThis article is a quick overview of scheduling in operating systems and presents Bossa, a research project on operating system schedulers and domain-specific languages.

Overview

The recent activity in Linux kernel development caused by the introduction of a new scheduler by Ingo Molnar has emphasized for ordinary Linux users the importance of schedulers in modern operating systems. In this article, we give you a glimpse of what scheduling development is like by letting you implement your own Linux scheduler thanks to Bossa, a framework for scheduler development.

Bossa, a framework for scheduler development

Scheduling

Most commodity computers can only run one process at a time, and yet the user will have the impression that many programs run in parallel. This illusion is created by the operating system scheduler. To do so, the scheduler causes the system to switch quickly between processes. Each process runs for a certain time, and when a process times out the scheduler chooses which process to execute next on the CPU. Therefore, the behavior of a system mainly depends on the scheduler. Fairness, efficiency, latency; the scheduler must balance these properties to offer the appropriate behavior. Hence while a scheduler aimed to desktop applications should emphasize the interactivity, server-oriented schedulers should emphasize efficiency and respond correctly to scalability issues. When implementing a scheduling algorithm the developer must take into account that each property has an impact on the others.

Today's common operating systems are general-purpose and while they can run on different architectures (server, desktop, embedded devices), they generally implement a unique scheduler, which consequently needs to perform well in all these environments. This is exactly what has been done with the new Linux scheduler. The introduction of O(1) algorithms and the re-writing of the multi-processor scheduling code permit better scalability for Linux 2.6 servers. On the other hand the new scheduler offers mechanisms to estimate the interactivity of processes which improve system feel on desktop utilization.

In parallel with the industrial world, research on schedulers has been a hot topic since the first days of multi-tasking environments and it has witnessed a revival with the growth of multimedia applications. Although many new algorithms have been developed, there has been little change in the schedulers used by commercial operating systems. The needs are clear: multimedia, real-time, resource control, etc, and yet the existing scheduling algorithms are not widely adopted. Surprising? No. One of the main obstacles that scheduler developers face is the implementation of a scheduling policy in a standard OS: developing and implementing a scheduling policy require two different kinds of expertise. Therefore a scheduler developer needs both to master kernel hacking and to be knowledgeable in the scheduling research field.

Bossa

Bossa is a framework to facilitate the implementation and integration of new scheduling policies. This framework has been developed at the Ecole des Mines de Nantes and the University of Copenhagen. The main idea behind Bossa is: let people do their job. If one's job is to develop scheduling algorithms, then one shouldn't have to hack kernel code.

The current framework is based on Linux and replaces scheduling code scattered throughout the kernel by a fixed interface of scheduling events. Integration of a new policy amounts to linking a module defining handlers for these events with the kernel. The re-engineering of the kernel is done only once (for each OS) and then it simplifies the integration of schedulers.

For the scheduler developer, Bossa includes a domain-specific language (DSL) that provides high-level scheduling abstractions. The developer uses this language to write scheduling policies which is more suitable for this job than C. Then, a dedicated compiler checks the Bossa DSL code for compatibility with the target kernel and translates the code into C, which is then compiled into a Linux kernel module.

Apart from simplifying the implementation of scheduling policies, the use of a DSL provides better safety guarantees. The Bossa DSL is more constrained than C or C++ in that, for example, pointers (known for being the cause of many bugs) are absent and infinite loops can't be defined. Moreover, the Bossa compiler performs verifications of the policy.

The Bossa framework also brings hierarchical scheduling to the Linux kernel. This concept consists of building a tree of schedulers, that allow different classes of applications to run under different scheduling policies. The leaves of the tree are schedulers of processes and nodes are schedulers of schedulers (a.k.a. virtual schedulers).

The diagram shows an example of a hierarchy of schedulers. In this example there are two classes of applications: normal and real-time. While the normal applications will be scheduled with the default Linux scheduler, the real-time applications will be scheduled by a real-time scheduler. Finally these two schedulers of processes are scheduled by a virtual scheduler (scheduler of schedulers).

 

scheduling tree

 

Bossa is free and you can access material at http://www.emn.fr/x-info/bossa/.

Here are direct links to download :

Table of contents
  1. "Bossa, Page 1/4"
  2. "Bossa, Page 2/4"
  3. "Bossa, Page 3/4"
  4. "Bossa, Page 4/4"
e p (0)    12 Comment(s)

Technology White Papers

See More