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

Scheduling in Real-Time Systems. Francis Cottet, Joe¨lle Delacroix, Claude Kaiser and Zoubir Mammeri Copyright  2002 John Wiley & Sons, Ltd. 6 Joint Scheduling and Messages in Systems ISBN: 0-470-84766-2 of Tasks Distributed This chapter and the next one discuss mechanisms to support real-time communica-tions between remote tasks. This chapter deals with some techniques used in multiple access local area networks and Chapter 7 deals with packet scheduling when the communications are supported by packet-switching networks such as ATM or IP-based networks. 6.1 Overview of Distributed Real-Time Systems The complexity of control and supervision of physical processes, the high number of data and events dealt with, the geographical dispersion of the processes and the need for robustness of systems on one hand, and the advent, for several years, on the market of industrial local area networks on the other, have all been factors which resulted in reconsidering real-time applications (Stankovic, 1992). Thus, an information processing system intended to control or supervise operations (for example, in a vehicle assembly factory, in a rolling mill, or in an aircraft) is generally composed of several nodes, which may be central processing units (computers or programmable automata), sensors, actuators, or peripherals of visualization and dialogue with operators. The whole of these nodes is interconnected by a network or by a set of interconnected networks (industrial local area networks, fieldbuses, etc.) (Pimentel, 1990). These systems are called distributed real-time systems (Kopetz, 1997; Stankovic, 1992). Several aspects have to be distinguished when we speak about distributed systems. First of all, it is necessary to differentiate the physical (or hardware) allocation from the software allocation. The hardware allocation is obtained by using several cen-tral processing units which are interconnected by a communication subsystem. The taxonomy is more complex when it is about the software. Indeed, it is necessary to distinguish: • data allocation (i.e. the assignment of data to appropriate nodes); • processing allocation (i.e. the assignment of tasks to appropriate nodes); • control allocation (i.e. the assignment of control roles to nodes for starting tasks; synchronizing tasks, controlling access to data, etc.). 104 6 JOINT SCHEDULING OF TASKS AND MESSAGES IN DISTRIBUTED SYSTEMS Distributed real-time systems introduce new problems, in particular: • computations based on timing constraints which refer to periods of time or to an absolute instant are likely to comprise too significant computational errors, and are therefore not credible, because of too large drifts between the clocks of the various nodes; • the evolution of the various components of the physical process is observed with delays that differ from one node to another because of variable delays of commu-nication; • distributed real-time scheduling requires schedulability analysis (computations to guarantee time constraints of communicating tasks), and this analysis has to cope with clock drifts and communication delays; • fault-tolerance is much more complex, which makes the problem of tolerating faults while respecting time constraints even more difficult. In this book, we are only interested in the scheduling problem. 6.2 Task Allocation in Real-Time Distributed Systems Task scheduling in distributed systems is dealt with at two levels: on the level of each processor (local scheduling), and on the level of the allocation of tasks to processors (global scheduling). Local scheduling consists of assigning the processor to tasks, by taking into account their urgency and their importance. The mission of global scheduling is to guarantee the constraints of tasks by exploiting the processing capabilities of the various processors composing the distributed system (while possibly carrying out migrations of tasks). Thus, a local scheduling aims to answer the question of ‘when to execute a task on the local processor, so as to guarantee the constraints imposed on this task?’. A global scheduling seeks to answer the question ‘which is the node best adapted to execute a given task, so as to guarantee its constraints?’. In distributed real-time applications, task allocation and scheduling are closely related: it is necessary to allocate the tasks to the set of processors so that local scheduling leads imperatively to the guarantee of the time constraints of the critical tasks. Local scheduling uses algorithms like those presented in the preceding chapters (i.e. rate monotonic, earliest deadline first, and so on). We are interested here in global scheduling, i.e. with allocation and migration of tasks, and with support for real-time communications. The problem of allocating n tasks to p processors often consists in initially seeking a solution which respects the initial constraints as much as possible, and then to choose the best solution, if several solutions are found. The search for a task allocation must take into account the initial constraints of the tasks, and the support environment, as well as the criteria (such as maximum lateness, scheduling length, number of processors used) to optimize. 6.3 REAL-TIME TRAFFIC 105 The tasks composing a distributed application can be allocated in a static or dynamic way to the nodes. In the first case, one speaks about static allocation; in the second, of dynamic allocation. In the first case, there cannot be any additional allocations of the tasks during the execution of the application; the allocation of the tasks is thus fixed at system initialization. In the second case, the scheduling algorithm chooses to place each task on the node capable of guaranteeing its time constraints, at the release time of the task. Dynamic allocation algorithms make it possible to find a node where a new task will be executed. If a task allocated to a node must be executed entirely on the node which was chosen for it, one speaks about a distributed system ‘without migration’; if a task can change node during its execution, one speaks about a distributed system ‘with migration’. The migration of a task during its execution consists of transferring its context (i.e. its data, its processor registers, and so on), which continuously changes as the task is executed, and, if required, its code (i.e. the instructions composing the task program), which is invariable. To minimize the migration time of a task, the code of the tasks likely to migrate is duplicated on the nodes on which these tasks can be executed. Thus, in the case of migration, only the context of the task is transferred. Task migration is an important function in a global scheduling algorithm. It enables the evolution of the system to be taken into account by assigning, in a dynamic way, the load of execution of the tasks to the set of processors. In addition, dynamically changing the nodes executing tasks is a means of increasing the fault-tolerance of the system. Many syntheses on task allocation techniques, in the case of non-real-time parallel or distributed systems, have been proposed in the literature. The reader can refer in particular to Eager et al. (1986) and Stankovic (1992). On the other hand, few works have studied task allocation in the case of real-time and distributed systems. The reader can find examples of analysis and experimentation of some task allocation methods in (Chu and Lan, 1987; Hou and Shin, 1992; Kopetz, 1997; Shih et al., 1989; Storch and Liu, 1993; Tia and Liu, 1995; Tindell et al., 1992). In the following, we assume that tasks are allocated to nodes, and we focus on techniques used to support real-time communications between tasks. 6.3 Real-Time Traffic 6.3.1 Real-time traffic types In real-time distributed systems, two attributes are usually used to specify messages: end-to-end transfer delay and delay jitter: • End-to-end transfer delay (or simply end-to-end delay) is the time between the emission of the first bit of a message by the transmitting end-system (source) and its reception by the receiving end-system (destination). • Delay jitter (or simply jitter) is the variation of end-to-end transfer delay (i.e. the difference between the maximum and minimum values of transfer delay). It is a distortion of the inter-message arrival times compared to the inter-message times 106 6 JOINT SCHEDULING OF TASKS AND MESSAGES IN DISTRIBUTED SYSTEMS of the original transmission. This distortion is particularly damaging to multimedia traffic. For example, the playback of audio or video data may have a jittery or shaky quality. In a way similar to tasks, one can distinguish three types of messages: • Periodic (also called synchronous) messages are generated and consumed by peri-odic tasks, and their characteristics are similar to the characteristics of their respec-tive source tasks. Adopting the notation used for periodic tasks, a periodic message Mi is usually denoted by a 3-tuple (Ti,Li,Di). This means that the instances of message Mi are generated periodically with a period equal to Ti, the maximum length of Mi’s instances is Li bits, and each message instance must be delivered to its destination within Di time units. Di is also called end-to-end transfer delay bound (or deadline). Some applications (such as audio and video) require that jitter should be bounded. Thus a fourth parameter Ji may be used to specify the jitter that should be guaranteed by the underlying network. • Sporadic messages are generated by sporadic tasks. In general, a sporadic message Ms may be characterized by a 5-tuple (Ts,ATs,Is,Ls,Ds). The parameters Ts,Ls and Ds are the minimum inter-arrival time between instances of Ms, maximum length and end-to-end deadline of instances of Ms. ATs is the average inter-arrival time, where the average is taken over a time interval of length Is. • Aperiodic messages are generally generated by aperiodic tasks and they are char-acterized by their maximum length and end-to-end delay. In addition to the previous parameters, which are similar to the ones associated with tasks, other parameters inherent to communication networks, such as message loss rate, may be specified in the case of real-time traffic. 6.3.2 End-to-end communication delay Communication delay between two tasks placed on the same machine is often consid-ered to be negligible. It is evaluated according to the machine instructions necessary to access a data structure shared by the communicating tasks (shared variables, queue, etc.). The communication delay between distant tasks (i.e. tasks placed on differ-ent nodes) is much more complex and more difficult to evaluate with precision. The methods of computation of the communication delay differ according to whether the nodes on which the communicating tasks are placed are directly connected — as is the case when the application uses a local area network with a bus, loop or star topol-ogy — or indirectly connected — as is the case when the application uses a meshed network. When the communicating nodes are directly connected, the communication delay between distant tasks can be split into several intermediate delays, as shown in Figure 6.1: • A delay of crossing the upper layers within the node where the sending task is located (d1). The upper layers include the application, presentation and transport layers of the OSI model when they are implemented. 6.3 REAL-TIME TRAFFIC 107 Sending task Receiving task d1 d2 d3 Sending task High layers MAC sublayer Medium d4 d1 d2 d3 High d6 layers MAC d5 sublayer t Receiving task d5 d6 t d4 d4 End-to-end delay Figure 6.1 Components of end-to-end delay of communication between two tasks when tasks are allocated to nodes directly connected by a local area network • A queuing delay in the medium access control (MAC) sublayer of the sending node (d2). This queuing delay is the most difficult to evaluate. • A delay of physical transmission of the message on the medium (d3). • A delay of propagation of a bit on the medium up to the receiving node (d4). • A delay of reception and waiting time in the MAC sublayer of the receiving node (d5). • A delay of crossing the upper layers in the node where the receiving task is located (d6). In order for a task to receive a message in time, it is necessary that the various intermediate delays (d1,...,d6) are determined and guaranteed. The delays d1 and d6 do not depend on the network (or more exactly do not depend on the medium access protocol). The delay d5 is often regarded as fixed and/or negligible, if the assumption is made that any received message is immediately passed to the upper layers. The delays d3 and d4 are easily computable. Transmission delay d3 depends on the network bit rate and the length of the message. Delay d4 depends on the length of the network. Delay ... - tailieumienphi.vn