Guaranteeing X in Y: On-line Acceptance Tests for Hard
Aperiodic Tasks Scheduled by the Slack Stealing Algorithm.

Robert Davis

Real-Time Systems Research Group,
Department of Computer Science, University of York, Y01 5DD, England.

Email: [email protected]

ABSTRACT

In this paper, we show that two recently published on-line acceptance tests for guaranteeing hard deadline aperiodic tasks scheduled under the Slack Stealing algorithm are insufficient: they may guarantee tasks which will then miss their deadlines. Further, we derive a sufficient acceptance test which is both efficient and effective. An evaluation of the performance of this acceptance test is given in the paper.

1. Introduction

In a recent paper [6], Ramos-Thuel and Lehoczky presented a method of scheduling hard deadline aperiodic tasks within the context of real-time systems scheduled using a fixed priority pre-emptive dispatcher. The provision of an efficient on-line acceptance test for hard deadline aperiodics is an important issue in the field of fixed priority scheduling theory. This is because it provides enabling technology for scheduling recovery from transient overloads, software fault recovery and the use of approximate processing [3] to improve the utility of hard tasks.

In [6], the approach taken by Ramos-Thuel and Lehoczky focused on using the Slack Stealing algorithm [4] to provide aperiodic service opportunities whilst ensuring that hard periodic tasks do not miss their deadlines. The Slack Stealing algorithm was combined with an acceptance test which enabled on-line guarantees to be given to aperiodic tasks with hard deadlines. The acceptance test operates as follows: first, the aperiodic processing time available between the release and the deadline of a hard aperiodic task is calculated. This is then compared to the execution requirements of the task to determine if it can be guaranteed.

Unfortunately, the analysis given by Ramos-Thuel and Lehoczky in the published paper [6] leads to an acceptance test which is insufficient: hard aperiodic tasks may be guaranteed and yet still miss their deadlines. This problem was discovered by Davis and Burns and pointed out in a private communication, enabling Ramos-Thuel and Lehoczky to formulate a correction which was presented at the 1993 Real-Time Systems Symposium [7]. However, subsequent investigation of the revised acceptance test revealed that it too is insufficient.