AQuoSA

At the lowest level, a patch to the Linux kernel adds the ability to notify to dynamically loaded modules any relevant scheduling event. These have been identified in the creation or death of tasks, as well as the block and unblock events. This patch is minimally invasive, in that it consists of a few lines of code properly inserted mainly within the Linux scheduler code (sched.c). It has been called "Generic Scheduler Patch", because it potentially allows to implement any scheduling policy.

The Resource Reservations layer is composed of three components.

The core component is a dynamically loadable kernel module that implements a Resource Reservations scheduling paradigm for the CPU, by exploiting functionality introduced into the Linux kernel through the Generic Scheduler Patch.

Second, a user-level library (QRES library) allows an application to use the new scheduling policy through a complete and well-designed set of API calls. Essentially, these calls allow an application to ask the system to reserve a certain percentage of the CPU to their processes.

Third, a kernel-level component (the Supervisor) mediates all requests made by the applications through the QRES library, so that the total sum of the requested CPU shares does not violate the schedulability condition of the scheduler (less than one, or slightly less than one, due to overhead). The supervisor behaviour is completely configurable by the system administrator, so that it is possible to specify, on a per-user/per-group basis, minimum guaranteed and maximum allowed values for the reservations made on the CPU.

With AQuoSA, applications may use directly the Resource Reservation layer, which allows them to reserve a fraction of the CPU, so to run with the required scheduling guarantees. For example, a multimedia application may ask the operating system to run the application with the guarantee of being scheduled at least for Q milliseconds every P milliseconds, where Q and P depend on the nature of the application.

When registering an application with the Resource Reservation layer, it is possible to specify a minimum guaranteed reservation that the system should always guarantee to the application. Based on the requests of minimum guaranteed reservations, the layer performs admission control, i.e. it allows a new application in only if, after the addition of it, the new set of running applications does not overcome the CPU saturation limit.

For typical multimedia application making use of high compression technologies, it may be quite difficult, impractical or inconvenient to run such applications with a fixed reservation on the CPU. In fact, the most efficient reservation that should be used may vary over time due to varying compression level that results in varying decompression time.

Traditional real-time systems make use of WCET (Worst Case Execution Time) analysis techniques in order to compute what is the maximum time an instance of, for example, a periodic task may execute on the CPU before blocking waiting for the next instance.

Such analysis is very difficult in today's complex multimedia applications, especially when running on general-purpose hardware like standard PCs, where technologies like multi-level caches, CPU execution pipelines, on-bus buffers, multi-master buses, introduce many unpredictable variables in determining the time required for memory accesses.

On such systems, it is much more convenient to tune a system design based on the average expected load of the application. Otherwise, the system may be significantly under-utilized during runtime.

As already mentioned, for certain classes of multimedia applications, such as a video player, it is quite impossible to find an appropriate fixed value for the fraction of CPU required by the application at run-time, due to the heavy fluctuations of the load depending on the actual data that is being processed by the application. A fixed reservation based on the average requirements, or slightly greater than that, results in transient periods of poor quality during runtime (e.g. movie playback). On the other hand, a fixed reservation based on the maximum expected load results in an unneeded over-reservation of the CPU for most of the time, except the periods in which the load really approaches the maximum expected value.

For these classes of applications, it is much more convenient to use the Adaptive Reservation techniques, like the ones provided by the Adaptive Reservation layer of AQuoSA, that performs a continuous on-line monitoring of the computational requirements of the application processes, so that it may dynamically adapt the reservation made on the CPU depending on the monitored data.

The Adaptive Reservation layer exposes to applications an API for using a set of controllers which are of quite general use within a wide set of multimedia applications.

Most real-time variations of Linux require users of real-time capabilities of the modified OS to have root privileges on the system. This is perfectly acceptable in an embedded system context. However, this is excessive for multi-user systems where real-time scheduling features are needed for multimedia applications or similar. Therefore, AQuoSA embeds a dedicated access-control model by which system administrators can:

1. define real-time scheduling quotas to individual users or groups, in terms of maximum values for the minimum guaranteed bandwidth that the OS can grant to individual users or groups as a whole;
2. control how the optional required bandwidth values, in excess to the minimum guaranteed figures, is distributed among competing users, in overload situations;
3. control the maximum scheduling overhead that can be imposed on the system as due to real-time reservations created by individual users or groups; for example, allowing to control what is the minimum period that can be specified in a real-time reservation.

More details can be found in the paper on the topic published at RTAS 2008.[2]