tailieunhanh - Lịch khai giảng trong các hệ thống thời gian thực P3

Scheduling of Dependent Tasks In the previous chapter, we assumed that tasks were independent, . with no relationships between them. But in many real-time systems, inter-task dependencies are necessary for realizing some control activities. In fact, this inter-task cooperation can be expressed in different ways: some tasks have to respect a processing order, data exchanges between tasks, or use of various resources, usually in exclusive mode. | Scheduling in Real-Time Systems. Francis Cottet Joëlle Delacroix Claude Kaiser and Zoubir Mammeri Copyright 2002 John Wiley Sons Ltd. ISBN 0-470-84766-2 3 Scheduling of Dependent Tasks In the previous chapter we assumed that tasks were independent . with no relationships between them. But in many real-time systems inter-task dependencies are necessary for realizing some control activities. In fact this inter-task cooperation can be expressed in different ways some tasks have to respect a processing order data exchanges between tasks or use of various resources usually in exclusive mode. From a behavioural modelling point of view there are two kinds of typical dependencies that can be specified on real-time tasks precedence constraints that correspond to synchronization or communication among tasks mutual exclusion constraints to protect shared resources. These critical resources may be data structures memory areas external devices registers etc. Tasks with Precedence Relationships The first type of constraint is the precedence relationship among real-time tasks. We define a precedence constraint between two tasks Ti and Tj denoted by Ti Tj if the execution of task Ti precedes that of task Tj. In other words task Tj must await the completion of task Ti before beginning its own execution. As the precedence constraints are assumed to be implemented in a deterministic manner these relationships can be described through a graph where the nodes represent tasks and the arrows express the precedence constraint between two nodes as shown in Figure . This precedence acyclic graph represents a partial order on the task set. If task Ti is connected by a path to task t j in the precedence graph then Ti t j .A general problem concerns tasks related by complex precedence relationships where n successive instances of a task can precede one instance of another task or one instance of a task precedes m instances of another task. Figure gives an example where the rates