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

Scheduling in Real-Time Systems. Francis Cottet, Joe¨lle Delacroix, Claude Kaiser and Zoubir Mammeri Copyright  2002 John Wiley & Sons, Ltd. 3 Scheduling of ISBN: 0-470-84766-2 Dependent Tasks In the previous chapter, we assumed that tasks were independent, i.e. with no rela-tionships 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. 3.1 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 τi and τj, denoted by τi → τj, if the execution of task τi precedes that of task τj. In other words, task τj must await the completion of task τi 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 3.1. This precedence acyclic graph represents a partial order on the task set. If task τi is connected by a path to task τj in the precedence graph then τi → τ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 3.2 gives an example where the rates of the communicating tasks are not equal. To facilitate the description of the precedence constraint problem, we only consider the case of simple precedence constraint, i.e. if a task τi has to communicate the result of its processing to another task τj, these tasks have to be scheduled in such a way that the execution of the kth instance of task τi precedes the execution of the kth instance of task τj. Therefore, these tasks have the same rate (i.e. Ti = Tj). So all tasks belonging to a connected component of the precedence graph must have the same period. On the graph represented in Figure 3.1, tasks τ1 to τ5 have the same period and tasks τ6 to τ9 also have the same period. If the periods of the tasks are different, these tasks will run 52 3 SCHEDULING OF DEPENDENT TASKS t2 t5 t8 t1 t4 t6 t7 t3 t9 Figure 3.1 Example of two precedence graphs related to a set of nine tasks t Temperature measurement task T2 = 4T1 t Average temperature over four samples calculation task Figure 3.2 Example of a generalized precedence relationship between two tasks with differ-ent periods at the lowest rate sooner or later. As a consequence the task with the shortest period will miss its deadline. We do not consider cyclical asynchronous message buffers. An answer to the first question was given by Blazewicz (1977): if we have to get τi → τj, then the task parameters must be in accordance with the following rules: • rj ≥ ri • Prioi ≥ Prioj in accordance with the scheduling algorithm In the rest of this chapter, we are interested in the validation context. This problem can be studied from two points of view: execution and validation. First, in the case of preemptive scheduling algorithms based on priority, the question is: which modification of the task parameters will lead to an execution that respects the precedence constraints? Second, is it possible to validate a priori the schedulability of a dependent task set? 3.1.1 Precedence constraints and fixed-priority algorithms (RM and DM) The rate monotonic scheduling algorithm assigns priorities to tasks according to their periods. In other words, tasks with shorter period get higher priorities. Respecting this rule, the goal is to modify the task parameters in order to take account of precedence constraints, i.e. to obtain an independent task set with modified parameters. The basic idea of these modifications is that a task cannot start before its predecessors and cannot preempt its successors. So if we have to get τi → τj, then the release time and the priority of task parameters must be modified as follows: • r∗ ≥ Max(rj,r∗) r∗ is the modified release time of task τi • Prioi ≥ Prioj in accordance with the RM algorithm 3.1 TASKS WITH PRECEDENCE RELATIONSHIPS 53 t3 t1 t2 t5 t4 t6 Figure 3.3 Precedence graphs of a set of six tasks Table 3.1 Example of priority mapping taking care of precedence constraints and using the RM scheduling algorithm Task τ1 τ2 τ3 τ4 τ5 τ6 Priority 6 5 4 3 2 1 It is important to notice that, as all tasks of a precedence graph share the same period, according to RM policy there is a free choice concerning the priorities that we use to impose the precedence order. Let us consider a set of six tasks with simultaneous release times and two graphs describing their precedence relationships (Figure 3.3). The priority mapping, represented in Table 3.1, handles the precedence constraint and meets the RM algorithm rule. The deadline monotonic scheduling algorithm assigns priorities to tasks according to their relative deadline D (tasks with shorter relative deadline get higher priorities). The modifications of task parameters are close to those applied for RM scheduling except that the relative deadline is also changed in order to respect the priority assignment. So if τi → τj, then the release time, the relative deadline and the priority of the task parameters must be modified as follows: • r∗ ≥ Max(rj,r∗) r∗ is the modified release time of task τi • D∗ ≥ Max(Dj,D∗) D∗ is the modified relative deadline of task τi • Prioi ≥ Prioj in accordance with the DM scheduling algorithm This modification transparently enforces the precedence relationship between two tasks. 3.1.2 Precedence constraints and the earliest deadline first algorithm In the case of the earliest deadline first algorithm, the modification of task parameters relies on the deadline d. So the rules for modifying release times and deadlines of tasks are based on the following observations (Figure 3.4) (Blazewicz, 1977; Chetto et al., 1990). 54 3 SCHEDULING OF DEPENDENT TASKS t1 t2 t3 Modification of r* Modification of d* C1 C3 t r1 r2 r* d* d2 d3 Figure 3.4 Modifications of task parameters in the case of EDF scheduling First, if we have to get τi → τj, the release time r∗ of task τj must be greater than or equal to its initial value or to the new release times r∗ of its immediate predecessors τi increased by their execution times Ci: r∗ ≥ Max((r∗ + Ci),rj) Then, if we have to get τi → τj, the deadline d∗ of task τi has to be replaced by the minimum between its initial value di or by the new deadlines dj of the immediate successors τj decreased by their execution times Cj: d∗ ≥ Min((d∗ − Cj),di) Procedures that modify the release times and the deadlines can be implemented in an easy way as shown by Figure 3.4. They begin with the tasks that have no predecessors for modifying their release times and with those with no successors for changing their deadlines. 3.1.3 Example Let us consider a set of five tasks whose parameters (ri,Ci,di) are indicated in Table 3.2. Note that all the tasks are activated simultaneously except task τ2. Their precedence graph is depicted in Figure 3.5. As there is one precedence graph linking Table 3.2 Set of five tasks and the modifications of parameters according to the precedence constraints (4 is the highest priority) Initial task parameters Modifications to use RM Modifications to use EDF Task τ1 τ2 τ τ5 ri Ci di r∗ Prioi r∗ d∗ 0 1 5 0 3 0 3 5 2 7 5 4 5 7 0 2 5 0 2 1 5 0 1 10 5 1 7 9 0 3 12 5 0 8 12 3.2 TASKS SHARING CRITICAL RESOURCES 55 t3 t1 t5 t4 t2 Figure 3.5 Precedence graph linking five tasks all the tasks of the application, we assume that all these tasks have the same rate. Table 3.2 also shows the modifications of task parameters in order to take account of the precedence constraints in both RM and EDF scheduling. Let us note that, in the case of RM scheduling, only the release time parameters are changed and the precedence constraint is enforced by the priority assignment. Under EDF scheduling, both parameters (ri,di) must be modified. 3.2 Tasks Sharing Critical Resources This section describes simple techniques that can handle shared resources for dynamic preemptive systems. When tasks are allowed to access shared resources, their access needs to be controlled in order to maintain data consistency. Let us consider a critical resource, called R, shared by two tasks τ1 and τ2. We want to ensure that the sequences of statements of τ1 and τ2, which perform on R, are executed under mutual exclusion. These pieces of code are called critical sections or critical regions. Specific mechanisms (such as semaphore, protected object or monitor), provided by the real-time kernel, can be used to create critical sections in a task code. It is important to note that, in a non-preemptive context, this problem does not arise because by definition a task cannot be preempted during a critical section. In this chapter, we consider a preemptive context in order to allow fast response time for high-priority tasks which correspond to high-safety software. Let us consider again the small example with two tasks τ1 and τ2 sharing one resource R. Let us assume that task τ1 is activated first and uses resource R, i.e. enters its critical section. Then the second task τ2, having a higher priority than τ1, asks for the processor. Since the priority of task τ2 is greater, preemption occurs, task τ1 is blocked and task τ2 starts its execution. However, when task τ2 wants access to the shared resource R, it is blocked due to the mutual exclusion process. So task τ1 can resume its execution. When task τ1 finishes its critical section, the higher priority task τ2 can resume its execution and use resource R. This process can lead to an uncontrolled blocking time of task τ2. On the contrary, to meet hard real-time requirements, an application must be controlled by a scheduling algorithm that can always guarantee a predictable system response time. The question is how to ensure a predictable response time of real-time tasks in a preemptive scheduling mechanism with resource constraints. ... - tailieumienphi.vn