OSNews

Round Robin Scheduling

To illustrate the implementation of a scheduling policy using Bossa we consider one of the simplest yet most widely used algorithms: round robin. This algorithm assigns each process a time slice, called a quantum, which represents the time the process is allowed to run. If the process is still running after a period of time equal to its quantum then it is preempted by the kernel and the CPU is given to another process. Processes waiting for execution are stored in a queue and the first process enqueued is the first to run. Once preempted, a process is placed at the end of the queue, implying that it has to wait for all of the other processes to execute. The figure below shows the execution of four processes executed under a round-robin algorithm.

Process execution under round-robin with the quantum set to 3 ms.

In the following, we will explain how to write a round robin scheduler using Bossa. We will also show how to load this scheduler into a Bossa-ified Linux kernel and run some test programs to show that it is working.

Implementing the round robin policy using the Bossa language

The Bossa framework introduces a new programming language to write scheduling policies. In this section we present an overview of the Bossa language by using it to implement the round robin algorithm.

Basically a Bossa policy is divided into five parts:

1. The process structure definition
2. The declaration of the different states
3. The ordering criteria used to select the next process to run
4. The handling of the scheduling events
5. The interface allowing user-level programs to control some aspects of the policy

We present each of these parts below.

Process structure definition

As our round-robin policy is a scheduler of processes, we need to declare the process attributes that will be used by the policy.

process = {
    int time_slice;
}

This declaration means that each process has a time_slice attribute, which will be used to store the time remaining. When manipulating a process p we can access its time slice using p.time_slice.

States

Steps in the lifetime of a process

The steps in the lifetime of a process can be summarized as the states running, ready, blocked and terminated. In the Bossa framework, two levels of states are found:

1. State classes: RUNNING, READY, BLOCKED, TERMINATED. These are the basic states in the lifetime of a process from the point of view of the kernel.
2. States: these are states declared by the developer and used in a scheduling policy. A state is always associated with a state class.

Let's see how states are declared with Bossa:

states = {
    RUNNING running : process;
    READY active : sorted fifo queue;
    BLOCKED blocked : queue;
    TERMINATED terminated;
}

In the code above, we declare four states: running, active, blocked, and terminated. The state running is associated with the state class RUNNING and references a unique process. The state active is associated with the state class READY and references a queue of processes which is maintained in fifo (first-in first-out) order (the annotation sorted will be discussed in the next section).

running references the process currently running while active references a queue containing all the processes ready to be executed, blocked references the blocked processes. terminated does not reference any process; instead, it is analogous to /dev/null as changing the state of a process to terminated drops any reference to the process.

Selection

Selection is probably the main part of all schedulers, as the behavior (fairness, interactivity, etc) of a scheduling policy depends on how it selects the next process to run. The Bossa language provides features that try to simplify the specification of the selection process. The language allows the user to define criteria that will be used to select a process from a set of processes. The developer uses the annotation sorted to indicate the state (and data structure) to which the selection criteria should be applied. In the previous section, we declared the queue containing the processes in the state active as sorted. Selection will thus be done from the processes in this state.

Criteria are defined using the keyword ordering_criteria. For instance, if the next process to run must be the process with the highest priority, it should be defined as:

ordering_criteria = { highest priority }

Back to our example. The round robin scheduler just gets the next process from the queue of processes so we don't need to define any ordering criteria.

ordering_criteria = { }

1. "Bossa, Page 1/4"
2. "Bossa, Page 2/4"
3. "Bossa, Page 3/4"
4. "Bossa, Page 4/4"