page 1  (20 pages)
2to next section

HOLISTIC1 SCHEDULABILITY ANALYSIS

FOR DISTRIBUTED HARD REAL-TIME SYSTEMS

Ken Tindell2
Department of Computer Science
University of York, England

ABSTRACT

This report extends the current analysis associated with static priority
pre-emptive based scheduling to address the wider problem of
analysing schedulability of a distributed hard real-time system; in
particular it derives analysis for a distributed system where tasks with
arbitrary deadlines communicate by message passing and shared data
areas. A simple TDMA protocol is assumed, and analysis developed to
bound not only the communications delays, but also the delays and
overheads incurred when messages are processed by the protocol stack
at the destination processor. The report illustrates how a windowbased
analysis technique can be used to find the worst-case response
times of a distributed task set. An extended example illustrating the
application of the analysis is presented.

1. INTRODUCTION

A common way of constructing a hard real-time system is to compose the system from a number of hard real-time tasks dispatched according to static priorities. Analysis is done a priori to determine the worst-case response times of each of the tasks, and the system is only deployed if these response times meet the timing requirements of the system. Hitherto, this approach has not been applied well to distributed embedded hard real-time systems: the priority ceiling protocol, for example, has been successfully implemented only on a singleprocessor architecture (although some work on a less successful parallel implementation has been done). One of the barriers to applying fixed priority scheduling to distributed systems has been the lack of integrated schedulability analysis that can be applied a priori to bound the timing behaviour of a distributed system (including both processing delays and communications delays). This report is concerned with developing such analysis for a simple computational model (space considerations prohibit the addressing of a more complex, and powerful, computational model).

One of the most important problems with a priori analysis for distributed fixed priority systems has been the complications introduced by communications costs: the delays for messages being sent between processors must be accurately bounded, and the overheads due to communications must be strictly bounded. Other overheads also need to be addressed: for example, the overheads due to operating a so-called tick scheduler [18, 20] have been bounded accurately.

1Holism, n. the theory that the fundamental principle of the universe is the creation of wholes, i.e. complete and self-contained systems [From Chambers 20th Century Dictionary]
2The author can be contacted via e-mail as [email protected]