Scheduling in Real-Time Systems / Edition 1 available in Hardcover
Scheduling in Real-Time Systems / Edition 1
- ISBN-10:
- 0470847662
- ISBN-13:
- 9780470847664
- Pub. Date:
- 11/22/2002
- Publisher:
- Wiley
Scheduling in Real-Time Systems / Edition 1
Hardcover
Buy New
$193.95Overview
Product Details
| ISBN-13: | 9780470847664 |
|---|---|
| Publisher: | Wiley |
| Publication date: | 11/22/2002 |
| Pages: | 288 |
| Product dimensions: | 6.85(w) x 9.74(h) x 0.81(d) |
About the Author
Read an Excerpt
Scheduling in Real-Time Systems
By Francis Cottet Joelle Delacroix Claude Kaiser Zoubir Mammeri
John Wiley & Sons
ISBN: 0-470-84766-2Chapter One
Basic Concepts
1.1 Real-Time Applications 1.1.1 Real-time applications issues
In real-time applications, the timing requirements are the main constraints and their mastering is the predominant factor for assessing the quality of service. Timing constraints span many application areas, such as industrial plant automation, embedded systems, vehicle control, nuclear plant monitoring, scientific experiment guidance, robotics, multimedia audio and video stream conditioning, surgical operation monitoring, and stock exchange orders follow-up.
Applications trigger periodic or random events and require that the associated computer system reacts before a given delay or a fixed time. The timing latitude to react is limited since transient data must be caught, actions have a constraint on both start and finish times, and responses or commands must be sent on time.
The time scale may vary largely, its magnitude being a microsecond in a radar, a second in a human-machine interface, a minute in an assembly line, or an hour in a chemical reaction.
The source of timing constraints leads to classifying them as hard or soft. A real-time system has hard timing constraints when a timing fault (missing a deadline, delivering a message too late, sampling data irregularly, too large a scatter in data supposed to be collectedsimultaneously) may cause some human, economic or ecological disaster. A real-time system has soft timing constraints when timing faults can be dealt with to a certain extent.
A real-time computer system is a computer system whose behaviour is fixed by the dynamics of the application. Therefore, a real-time application consists of two connected parts: the controlling real-time computer system and the controlled process (Figure 1.1).
Time mastery is a serious challenge for real-time computer systems, and it is often misunderstood. The correctness of system reactions depends not only on the logical results of the computations, but also on the time at which the results are produced. Correct data which are available too late are useless; this is a timing fault (Burns and Wellings, 1997; Lelann, 1990; Stankovic, 1988).
A controlling real-time computer system may be built as:
a cyclic generator, which periodically samples the state of the controlled process, computes the measured data and sends orders to the actuators (this is also called synchronous control);
a reactive system, which responds instantaneously to the stimuli originating in the controlled process and thus is triggered by its dynamics;
a union of both aspects, which schedules periodic and aperiodic tasks; this results in an asynchronous system.
1.1.2 Physical and logical architecture, operating systems
Software design of a real-time application
Several steps are usually identified to analyse and implement real-time applications. Some of them are:
requirements analysis and functional and timing specifications, which result in a functional view (the question to answer is: what should the system do?).
preliminary design, which performs an operational analysis (the question is: how to do it?) and leads to the choice of logical components of a logical architecture.
specific hardware and software development. They are often developed concurrently with similar design processes. The hardware analysis (the question is: with which hardware units?) leads to a physical architecture, to the choice of commercial off-the-shelf components and to the detailed design and development of special hardware. The conceptual analysis (the question is: with which software modules?) leads to a software architecture, to the choice of standard software components and to the implementation of customized ones. These acquisition and realization steps end with unit testing.
integration testing, which involves combining all the software and hardware components, standard ones as well as specific ones, and performing global testing.
user validation, which is carried out by measurements, sometimes combined with formal methods, and which is done prior to acceptance of the system.
These steps are summarized in Figure 1.2, which gives an overview of the main design and implementation steps of real-time applications. Once the logical and hardware architecture is defined, an allocation policy assigns the software modules to the hardware units. In distributed fault-tolerant real-time systems, the allocation may be undertaken dynamically and tasks may migrate. The operational analysis must define the basic logical units to map the requirements and to express concurrency in the system, which is our concern. The operational behaviour of the application is produced by their concurrent execution.
The major computing units are often classified as:
passive objects such as physical resources (devices, sensors, actuators) or logical resources (memory buffers, files, basic software modules);
communication objects such as messages or shared variables, ports, channels, network connections;
synchronization objects such as events, semaphores, conditions, monitors (as in Modula), rendezvous and protected objects (as in Ada);
active objects such as processes, threads, tasks;
structuring, grouping and combining objects such as modules, packages (as in Ada), actors (as in Chorus), processes (as in Unix, Mach).
In real-time systems, the word task is most often used as the unit for representing concurrent activities of the logical architecture. The physical parallelism in the hardware architecture and the logical parallelism in the application requirements are usually the base for splitting an application into concurrent tasks. Thus a task may be assigned to each processor and to each input-output device (disk reader, printer, keyboard, display, actuator, sensor), but also to each distinct functional activity (computing, acquisition, presentation, client, server, object manager) or to each distinct behavioural activity (periodic, aperiodic, reactive, cyclic, according to deadline or importance).
Physical architecture
Real-time systems hardware architectures are characterized by the importance of input-output streams (for example the VME bus in Figure 1.3). An example of physical architecture, the robot engine of the Pathfinder mission, will be presented in Chapter 9. The configuration of the embedded architecture is given in Figure 9.10. Figure 1.3 shows an example of a symmetric multiprocessor architecture with shared memory (Banino et al., 1993).
Distributed architectures over networks are being developed more and more. Chapter 6 is devoted to message scheduling, which is a major element in the mastery of timing constraints. We shall use the term interconnected sites. Figure 1.4 summarizes an architecture using local networks to interconnect several sites.
Logical architecture and real-time computing systems
Operating systems In order to locate real-time systems, let us briefly recall that computing systems may be classified, as shown by Figure 1.5, into transformational, interactive and reactive systems, which include asynchronous real-time systems.
The transformational aspect refers to systems where the results are computed with data available right from the program start and usable when required at any moment. The relational aspect between programming entities makes reference to systems where the environment-produced data are expected by programs already started; the results of these programs are input to other programs. The timing aspect refers to systems where the results must be given at times fixed by the controlled process dynamics.
A system is centralized when information representing decisions, resource sharing, algorithms and data consistency is present in a shared memory and is directly accessible by all tasks of the system. This definition is independent of the hardware architecture. It refers to a uniprocessor or a shared memory multiprocessor architecture as well as to a distributed architecture where all decisions are only taken by one site. A system is distributed when the decisions are the result of a consensus among sites exchanging messages.
Distributed programming has to cope with uncertainty resulting from the lack of a common memory and common clock, from the variations of message transfer delays from one site to another as well as from one message to another, and from the existence of an important fault rate. Thus, identical information can never be captured simultaneously at all sites. As the time is one of these pieces of information, the sites are not able to read a common clock simultaneously and define instantaneously whether or not 'they have the same time'.
Computing systems are structured in layers. They all contain an operating system kernelas shown in Figure 1.6. This kernel includes mechanisms for the basic management of the processor, the virtual memory, interrupt handling and communication. More elaborate management policies for these resources and for other resources appear in the higher layers.
Conventional operating systems provide resource allocation and task scheduling, applying global policies in order to optimize the use of resources or to favour the response time of some tasks such as interactive tasks. All tasks are considered as aperiodic: neither their arrival times nor their execution times are known and they have no deadline.
In conventional operating systems the shared resources dynamically allocated to tasks are the main memory and the processor. Program behaviour investigations have indicated that the main memory is the sensitive resource (the most sensitive are demand paging systems with swapping between main memory and disk). Thus memory is allocated first according to allocation algorithms, which are often complicated, and the processor is allocated last. This simplifies processor scheduling since it concerns only the small subset of tasks already granted enough memory (Bawn, 1997; Silberscharz and Galvin, 1998; Tanenbaum, 1994; Tanenbaum and Woodhull, 1997). Conventional operating systems tend to optimize resource utilization, principally the main memory, and they do not give priority to deadline observances. This is a great difference with real-time operating systems.
Real-time operating systems In real-time systems, resources other than the processor are often statically allocated to tasks at their creation. In particular, time should not be wasted in dynamic memory allocation. Real-time files and databases are not stored on disks but reside in main memory; this avoids the non-deterministic disk track seeking and data access. Input-output management is important since the connections with the controlled process are various. Therefore, the main allocation parameter is processor time and this gives importance to the kernel and leads to it being named the real-time operating system (Figure 1.7). Nevertheless, conventional operating system services are needed by real-time applications that have additional requirements such as, for example, management of large data sets, storing and implementing programs on the computer also used for process control or management of local network interconnection. Thus, some of these conventional operating systems have been reengineered in order to provide a reentrant and interruptible kernel and to lighten the task structure and communication. This has led to real-time Unix implementations. The market seems to be showing a trend towards real-time systems proposing a Posix standard interface (Portable Operating System Interface for Computer Environments; international standardization for Unix-like systems).
1.2 Basic Concepts for Real-Time Task Scheduling
1.2.1 Task description
Real-time task model
Real-time tasks are the basic executable entities that are scheduled; they may be periodic or aperiodic, and have soft or hard real-time constraints. A task model has been defined with the main timing parameters. A task is defined by chronological parameters denoting delays and by chronometric parameters denoting times. The model includes primary and dynamic parameters. Primary parameters are (Figure 1.8):
r, task release time, i.e. the triggering time of the task execution request.
ITLITL, task worst-case computation time, when the processor is fully allocated to it.
D, task relative deadline, i.e. the maximum acceptable delay for its processing.
T, task period (valid only for periodic tasks).
when the task has hard real-time constraints, the relative deadline allows computation of the absolute deadline d = r + D. Transgression of the absolute deadline causes a timing fault.
The parameter T is absent for an aperiodic task. A periodic task is modelled by the four previous parameters. Each time a task is ready, it releases a periodic request. The successive release times (also called request times, arrival times or ready times) are request release times at [r.sub.k] = [r.sub.0] + kT, where [r.sub.0] is the first release and [r.sub.k] the k + 1th release; the successive absolute deadlines are [d.sub.k] = [r.sub.k] + D. If D = T, the periodic task has a relative deadline equal to period. A task is well formed if 0 < C [less than or equal to] D [less than or equal to] T.
The quality of scheduling depends on the exactness of these parameters, so their determination is an important aspect of real-time design. If the durations of operations like task switching, operating system calls, interrupt processing and scheduler execution cannot be neglected, the design analysis must estimate these durations and add them to the task computation times. That is why a deterministic behaviour is required for the kernel, which should guarantee maximum values for these operations.
Other parameters are derived:
u = C/T is the processor utilization factor of the task; we must have u [less than or equal to] 1.
ch = C/D is the processor load factor; we must have ch [less than or equal to] 1.
The following dynamic parameters help to follow the task execution:
s is the start time of task execution.
e is the finish time of task execution.
D(t) = d - t is the residual relative deadline at time t: 0 [less than or equal to] D(t) [less than or equal to] D.
ITLITL(t) is the pending execution time at time t: 0 [less than or equal to] ITLITL(t) [less than or equal to] ITLITL.
Continues...
Excerpted from Scheduling in Real-Time Systems by Francis Cottet Joelle Delacroix Claude Kaiser Zoubir Mammeri Excerpted by permission.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.