Scheduling slack time in fixed priority pre-emptive systems

Publisher Website
Google Scholar
Abstract
This paper addresses the problem of jointly scheduling tasks with both hard and soft time constraints. We present a new analysis which builds upon previous research into slack stealing algorithms. Our analysis determines the maximum processing time which may be stolen from hard deadline periodic or sporadic tasks, without jeopardising their timing constraints. It extends to tasks with characteristics such as synchronisation, release jitter and stochastic execution times, as well as forming the basis for a family of optimal and approximate slack stealing algorithms. Analysis of fixed priority pre-emptive scheduling has provided a sound theoretical basis for designing predictable hard real-time systems (1, 9). Within this framework, a number of approaches have been developed for scheduling mixed task sets. The simplest and perhaps least effective of these is to execute soft deadline tasks at a lower priority level than any of those with hard deadlines. This effectively relegates the soft tasks to background processing. Alternatively, soft tasks may be run at a higher priority under the control of a pseudo hard real- time server task, such as a simple polling server. A polling server is a periodic task with a fixed priority level (usually the highest) and an execution capacity. The capacity of the server is calculated off-line and is normally set to the maximum possible, such that the hard task set, including server, is schedulable. At run-time, the polling server is released periodically and its capacity is used to service soft real-time tasks. Once this capacity has been exhausted, execution is suspended until it can be replenished at the server's next release. The polling server will usually significantly improve the response times of soft tasks over background processing. However, if the ready soft tasks exceed the capacity of the server, then some of them will have to wait until its next release, leading to potentially long response times. Conversely, no soft tasks may be ready when the server is released, wasting its high priority capacity. This latter drawback is avoided by the Priority Exchange, Deferrable server (8) and Sporadic server (13) algorithms. These are all based on similar principles to the polling server. However, they are able to preserve capacity if no soft tasks are pending when they are released. Due to this property, they are termed "bandwidth preserving algorithms". The three algorithms differ in the ways in which the capacity of the server is preserved and replenished and in the schedulability analysis needed to determine their maximum capacity.

This publication has 10 references indexed in Scilit: