AQuoSA (Adaptive Quality of Service Architecture) [1] 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
editThe architecture of the project may be summarized as follows:
Patch to the Linux kernel
editAt 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
editThe 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
editFor 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
editMost 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:
- 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;
- control how the optional required bandwidth values, in excess to the minimum guaranteed figures, is distributed among competing users, in overload situations;
- 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]
Later Evolution
editAQuoSA submitted the first proposed EDF patch to the Linux Kernel was submitted in 2009, released as SCHED_EDF.
Shortly after this, the patch was renamed to SCHED_DEADLINE
Numerous subsequent patches were released by the developers over the following years. With EDF also becoming the foundation of the IRMOS project, with the subsequent evolution being contributed to the project.
In 2012 SCHED_DEADLINE evolved into PREEMPT RT.
PREEMT_RT continued to evolve, though still as a patch, and remained the canonical implementation of EDF scheduling within Linux until Kernel 6.x in 2023.
Up until this time EDF scheduling was still usually only available as a Kernel compile time option that was rarely enabled within common Linux distributions. However, there was a simple, almost automated, Kernel compilation procedure available for Linux users to make use of it, if and/or when required.
In October 2023, the release of Kernel 6.6 finally saw the default use of EDF in the stock Linux Kernel. With what was now known as EEVDF (EEVDF being a direct descendent of the original EDF project). This was incorporated into the mainline Kernel as a replacement for the long-standing CFS scheduler, that being the stock, 'soft' real-time, preemtive scheduler used by most Linux installations since its adoption in Kernel 2.6.23 back in 2007 and also perhaps as a final replacement for PREEMPT_RT, though as of 2024 this is not certain.
External links
editReferences
edit- ^ Palopoli, Luigi; Cucinotta, Tommaso; Marzario, Luca; Lipari, Giuseppe (April 2008). "AQuoSA - Adaptive Quality of Service Architecture". Software: Practice and Experience. 39: 1–31. CiteSeerX 10.1.1.149.8231. doi:10.1002/spe.883. hdl:11382/361474. S2CID 3056232.
- ^ Cucinotta, Tommaso (2008). "Access Control for Adaptive Reservations on Multi-User Systems". 2008 IEEE Real-Time and Embedded Technology and Applications Symposium. pp. 387–396. doi:10.1109/RTAS.2008.16. ISBN 978-0-7695-3146-5. S2CID 1008365.