Advanced

On-line schedulability tests for adaptive reservations in fixed priority scheduling

Santos, Rodrigo; Lipari, Giuseppe; Bini, Enrico LU and Cucinotta, Tommaso (2012) In Real-Time Systems 48(5). p.601-634
Abstract
Adaptive reservation is a real-time scheduling technique in which each application is associated a fraction of the computational resource (a reservation) that can be dynamically adapted to the varying requirements of the application by using appropriate feedback control algorithms. An adaptive reservation is typically implemented by using an aperiodic server (e.g. sporadic server) algorithm with fixed period and variable budget. When the feedback law demands an increase of the reservation budget, the system must run a schedulability test to check if there is enough spare bandwidth to accommodate such increase. The schedulability test must be very fast, as it may be performed at each budget update, i.e. potentially at each instance of a... (More)
Adaptive reservation is a real-time scheduling technique in which each application is associated a fraction of the computational resource (a reservation) that can be dynamically adapted to the varying requirements of the application by using appropriate feedback control algorithms. An adaptive reservation is typically implemented by using an aperiodic server (e.g. sporadic server) algorithm with fixed period and variable budget. When the feedback law demands an increase of the reservation budget, the system must run a schedulability test to check if there is enough spare bandwidth to accommodate such increase. The schedulability test must be very fast, as it may be performed at each budget update, i.e. potentially at each instance of a task; yet, it must be as efficient as possible, to maximize resource usage. In this paper, we tackle the problem of performing an efficient on-line schedulability test for adaptive resource reservations in fixed priority schedulers. In the literature, a number of algorithms have been proposed for on-line admission control in fixed priority systems. We describe four of these tests, with increasing complexity and performance. In addition, we propose a novel on-line test, called Spare-Pot algorithm, which has been specifically designed for the problem at hand, and which shows a good cost/performance ratio compared to the other tests. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Resource reservation, Adaptive scheduling, Fixed priority
in
Real-Time Systems
volume
48
issue
5
pages
601 - 634
publisher
Kluwer
external identifiers
  • wos:000306338900004
  • scopus:84865312168
ISSN
1573-1383
DOI
10.1007/s11241-012-9156-y
language
English
LU publication?
yes
id
61d8b5b6-3a62-409c-97df-a65181258408 (old id 2994825)
date added to LUP
2012-08-22 12:41:32
date last changed
2017-07-30 04:25:03
@article{61d8b5b6-3a62-409c-97df-a65181258408,
  abstract     = {Adaptive reservation is a real-time scheduling technique in which each application is associated a fraction of the computational resource (a reservation) that can be dynamically adapted to the varying requirements of the application by using appropriate feedback control algorithms. An adaptive reservation is typically implemented by using an aperiodic server (e.g. sporadic server) algorithm with fixed period and variable budget. When the feedback law demands an increase of the reservation budget, the system must run a schedulability test to check if there is enough spare bandwidth to accommodate such increase. The schedulability test must be very fast, as it may be performed at each budget update, i.e. potentially at each instance of a task; yet, it must be as efficient as possible, to maximize resource usage. In this paper, we tackle the problem of performing an efficient on-line schedulability test for adaptive resource reservations in fixed priority schedulers. In the literature, a number of algorithms have been proposed for on-line admission control in fixed priority systems. We describe four of these tests, with increasing complexity and performance. In addition, we propose a novel on-line test, called Spare-Pot algorithm, which has been specifically designed for the problem at hand, and which shows a good cost/performance ratio compared to the other tests.},
  author       = {Santos, Rodrigo and Lipari, Giuseppe and Bini, Enrico and Cucinotta, Tommaso},
  issn         = {1573-1383},
  keyword      = {Resource reservation,Adaptive scheduling,Fixed priority},
  language     = {eng},
  number       = {5},
  pages        = {601--634},
  publisher    = {Kluwer},
  series       = {Real-Time Systems},
  title        = {On-line schedulability tests for adaptive reservations in fixed priority scheduling},
  url          = {http://dx.doi.org/10.1007/s11241-012-9156-y},
  volume       = {48},
  year         = {2012},
}