ADDING TIME-OFFSETS TO SCHEDULABILITY ANALYSIS

Ken Tindell1,
Real-Time Systems Research Group,
Department of Computer Science
University of York, England

ABSTRACT

This paper discusses the addition of so-called time offsets to task
sets dispatched according to fixed priorities. The motivation for
this work is two-fold: firstly, direct expression of time offsets is a
useful structuring approach for designing complex hard real-time
systems. Secondly, analysis directly addressing time offsets can
be very much less pessimistic than extant analysis. In this report
we extend our current fixed priority schedulability analysis, and
then present two major worked examples, illustrating the
approach.

1. INTRODUCTION

Previous work has addressed the problem of determining the worst-case timing behaviour of tasks dispatched according to fixed priority scheduling [11, 10]. Much of this work has been aimed at determining the worst-case case response time of a given task; of course, the worst-case response time is, by definition, the response time of the task in the worst-case scheduling scenario. So far, in all these previous pieces of work, tasks have been assumed to be scheduled independently ? there are no forced relationships between the release of any pair of tasks. Consequently, the worst-case task release pattern has been assumed; the resulting analysis is therefore sufficient for any task release pattern. In many cases, however, it is advantageous to specify timing constraints on release patterns for certain groups of tasks in a task set. In this report we are concerned with time offset relationships, where there is a fixed interval in time between the arrivals of sets of tasks. We seek to show how it is desirable to include time offsets into the computational model, and to extend the analysis to take account of these time offsets. Clearly, the existing analysis is sufficient to permit time offsets, but by taking account of time offsets we can reduce the pessimism when bounding the timing behaviour of a system. Section 8 gives an extended example that clearly shows the offset analysis bounds response times much less pessimistically.

It is important that any analysis we derive is in the same ?family? of analysis that has already been derived (for example, arbitrary deadlines [23, 21], communications scheduling [16], mode changes [22], and so on). This enables us to adapt existing

1The author can be contact via e-mail at [email protected]