Multiprocessor Scheduling of Real-Time Tasks with Resource Requirements
In this paper, we present a new synchronization strategy for real-time tasks executed in a parallel environment. This strategy makes the timing properties of the system predictable since one is able to determine analytically whether the timing requirement
- PDF / 189,697 Bytes
- 8 Pages / 431 x 666 pts Page_size
- 45 Downloads / 198 Views
Abstract. In this paper, we present a new synchronization strategy for real-time tasks executed in a parallel environment. This strategy makes the timing properties of the system predictable since one is able to determine analytically whether the timing requirements of a task set will be met, and if not, which task timing requirements will fail. The proposed synchronization protocol is based on the on-demand paradigm where resources are assigned only when actually required so that the system never wastes unused assignments. Simple formulae for the worst-case determination of task blocking durations as well as for the schedulability analysis of a set of tasks are described. A schedulability analysis example is also presented that illustrates the concepts of scheduling and resource allocation of a set of time critical tasks.
1
Introduction
The term scheduling of real-time tasks actually refers to the concept of sequencing the use of any shared resource whose use involves meeting application time constraints [2]. Alternatively, real-time scheduling is defined as the ordering of the execution of the tasks such that their timing constraints are met and the consistency of resources is maintained. Thus, the objective of any scheduling algorithm is to find a feasible schedule whenever one exists for a given set of tasks such that each completes its computation before its deadline, and a given set of resource requirements is satisfied. We have to emphasize here that the cpu scheduling is not the main problem of real-time systems but both cpu scheduling and resource allocation. In this paper, we present a new synchronization strategy for real-time tasks executed in a parallel environment, where each task may have resource requirements, i.e. it can require the use of non-preemptable resources or access shared data. Thus, we focus mainly on the resource allocation part of the scheduling process. This strategy is a continuation of our previous work on synchronization methods for real-time systems [4] where more intelligent techniques and less pessimistic formulae have been investigated and introduced in the current version. The proposed strategy is analyzable and understandable at a high level, meaning that given a set of tasks we know in advance if they will meet their deadlines or not. It is based on the rate monotonic algorithm [6, 1] in the way the priorities P. Amestoy et al. (Eds.): Euro-Par’99, LNCS 1685, pp. 497–504, 1999. c Springer-Verlag Berlin Heidelberg 1999
498
Costas Mourlas
are assigned to tasks, and which also effectively creates an integrated resource allocation model. Thus, we consider our work as a fixed priority architecture based upon the rate-monotonic scheduling, which is the optimal static priority scheduling algorithm with good performance, low complexity and minimal implementation overhead. The most well known synchronization protocol used by the rate monotonic algorithm is that of priority ceiling protocol described in [7, 5] where the blocking time is deterministic and bounded. It has many a
Data Loading...
