• scheduling algorithms
• kernel mechanisms
• resource reservation
• real-time
• linux

This thesis is part of an ongoing research activity at the Real-Time Systems
Laboratory (ReTiS Lab), regarding the study and development of scheduling
algorithms for real-time systems.

The purpose of this work is the design and development of a new bandwidth
reservation scheduling algorithm for managing time-critical tasks that may
temporarily suspend their execution, waiting for events (self-suspending
tasks). The resulting algorithm has been implemented in the Linux kernel.

The current scheduling algorithm used in Linux to manage CPU bandwidth
reservation (SCHED_DEADLINE) is based on a server mechanism called Hard
Constant Bandwidth Server (H-CBS). However, this mechanism was not designed to
manage self-suspending tasks and may lead to possible deadline misses. To solve
this problem, a new server mechanism, called the H-CBS-SO algorithm, has been
studied. This thesis addresses the design and implementation of a Linux
scheduling algorithm based on the H-CBS-SO reservation server.

The introduction illustrates the basic notions of real-time systems and
presents an overview the actual SCHED_DEADLINE policy and its implementation.
Then, the thesis focuses on the explanation of the H-CBS-SO algorithm and how
it is developed in the Linux kernel. A multiprocessor version of the algorithm
is also reviewed, given the large success and diffusion of Symmetric
MultiProcessor (SMP) systems.

The full exploitation of the scheduling policy developed in the thesis requires
an infrastructure for handling "periodic tasks" that is currently missing in
Linux. Therefore, this thesis proposes a new mechanism for managing periodic
tasks inside the Linux kernel and a user-space library for exploiting such a
new feature.

Special attention is dedicated to the description of the debugging techniques
used for checking the correctness of the kernel functions and the tools
developed for measuring the achieved performance.