AQuoSA

AQuoSA (Adaptive Quality of Service Architecture) is an open architecture for the provisioning of adaptive Quality of Service functionality into the Linux kernel. The project features a flexible, portable, lightweight and open architecture for supporting QoS related services on the top of a general-purpose operating system as Linux. The architecture is well founded on formal scheduling analysis and control theoretical results.
A key feature of AQuoSA is the Resource Reservation layer that is capable of dynamically adapting the CPU allocation for QoS aware applications based on their run-time requirements. In order to provide such functionality, AQuoSA embeds a kernel-level CPU scheduler implementing a resource reservation mechanism for the CPU based on Earliest Deadline First (EDF). This gives the ability to the Linux kernel to realize (partially) temporal isolation among the tasks running within the system.
AQuoSA is one of a few projects that provides real-time scheduling capabilities to unprivileged users on a multi-user system in a controlled way, by means of a properly designed access-control model.
Description.
The architecture of the project may be summarized as follows:
Patch to the Linux kernel.
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.
Resource Reservations.
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.
Adaptive Reservations.
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.
AQuoSA Access Control Model.
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:
More details can be found in the paper on the topic published at RTAS 2008.