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

Scheduling in Real-Time Systems. Francis Cottet, Joe¨lle Delacroix, Claude Kaiser and Zoubir Mammeri Copyright  2002 John Wiley & Sons, Ltd. ISBN: 0-470-84766-2 8 Software Environment This chapter presents some software components relevant to real-time applications. The first part of the chapter is concerned with operating systems. Real-time requirements for operating system behaviour forbid the use of standard Unix, although the Posix/Unix interface is very useful for software engineering. Three approaches are presented. In the first one, the real-time executive has been customized to provide a Posix interface. This is illustrated by VxWorks, the executive of the Mars Pathfinder rover, which is the second case study which will be presented in Chapter 9. The second approach is that of RT-Linux where a small companion kernel is attached to a Unix-like system. In the third approach, a system based on a Unix architecture has been engineered from scratch in order to fulfil real-time requirements. This is illustrated by LynxOs, the executive of the rolling mill acquisition system, which will be presented in Chapter 9 as the first case study. The second part of the chapter deals with programming languages designed with real-time potential. Some of them provide asynchronous programming. The Ada programming language is largely developed with the example of a mine pump control implementation. Real-time Java is outlined. Synchronous languages that make the assumption of instantaneously reacting to external events are also presented. The last part of the chapter is an overview of the real-time capabilities which are being added to distributed platforms that provide standardized middleware for non-real-time distributed applications. The challenge is to be able to use distributed objects and components and common-off-the-shelf hardware and software components that are developed extensively for non-real-time distributed applications. The chapter ends by summarizing the real-time capabilities of these software environments. 8.1 Real-Time Operating System and Real-Time Kernel 8.1.1 Overview Requirements A modern real-time operating system should provide facilities to fulfil the three major requirements of real-time applications. These are: • guarantee of response from the computing system; • promptness of a response, once it has been decided; • reliability of the application code. 178 8 SOFTWARE ENVIRONMENT In interactive operating systems, the CPU activity is optimized to provide maximum throughput with the constraint of favouring some class of tasks. The primary concern is resource utilization instead of time constraints. All tasks are considered as aperiodic with unknown date of arrival and unknown execution times. They have no compulsory execution deadlines. A real-time operating system must be able to take into account periodic tasks with fixed period and fixed deadlines, as well as sporadic tasks with unknown dates of occurrence but with fixed deadlines. The system must be controlled such that its timing behaviour is understandable, bounded and predictable. These properties can be aimed at by a layered approach based on a real-time task scheduler and on a real-time kernel. The operating system kernel must enforce the real-time behaviour assumed by the real-time task scheduler, i.e. promptness and known latency. Timing predictions must include the insurance that the resources are available on time and therefore cope with access conflicts and fault tolerance. The real-time kernel must provide efficient mechanisms for data acquisition from sensors, data processing and output to activators or display devices. Let us emphasize some of them. 1. I/O management and control – a fast and flexible input and output processing power in order to rapidly capture the data associated with the priority events, or to promptly supply the actuators or the display devices; – the absence of I/O latency caused by file granularity and by I/O buffer man-agement, and therefore the capability of predicting transfer delays of prioritized I/O. 2. Task management and control – concurrency between kernel calls, limited only by the mutual exclusion to sensi-tive data, i.e. a fully preemptive and reentrant kernel; – fast and efficient synchronization primitives which will avoid unnecessary con-text switching; – a swift task context switch; – an accurate granularity of time servers; – a task scheduling which respects the user-defined priority, and which does not cause unexpected task switching or priority inversion. 3. Resource management and control – contention reduction with predictable timings when concurrent tasks access sha-red resources such as memory busses, memory ports, interrupt dispatcher, kernel tables protected by mutual exclusion; – priority inversion avoidance; – deadlock prevention and watchdog services in the kernel. 8.1 REAL-TIME OPERATING SYSTEM AND REAL-TIME KERNEL 179 Appraisal of real-time operating systems The appraisal of a real-time operating system relies mainly on real-time capabilities such as: • promptness of response by the computer system; • predictability of kernel call execution times; • tuning of scheduling policies; • assistance provided for program debugging in the real-time context when the appli-cation is running in the field; • performance recorded in case studies. Let us develop two aspects. 1. Promptness of response The promptness of the response of a real-time kernel may be evaluated by two parameters, interrupt latency and clerical latency. Interrupt latency is the delay between the advent of an event in the application and the instant this event is recorded in the computer memory. This interrupt latency is caused by: • the propagation of the interrupt through the hardware components: external bus, interrupt dispatcher, interrupt board of the processor, interrupt selection; • the latency in the kernel software resulting from non-preemptive resource utiliza-tion: masking interrupts, spin lock action; • the delay for context switching to an immediate task. This interrupt latency is usually reduced by a systematic use of the hardware priorities of the external bus, by kernel preemptivity and context switch to immediate tasks. Clerical latency is the delay which occurs between the advent of an event in the application and the instant this event is processed by its target application task. This clerical latency is caused by: • the interrupt latency; • the transfer of data from the interrupt subroutine to the application programs context; • the notification that the target application task is already eligible; • the return to the current application task, which may be using some non-preemptive resource and, in that situation, must be protected against the election of another application task; • the delay the target application task waits before being elected for running; • the installation of the context of the target application task. 2. Predictability of kernel call execution times A real-time kernel includes a com-plete set of methods for reducing time latency, which are reentrance, preemption, 180 8 SOFTWARE ENVIRONMENT priority scheduling and priority inheritance. Therefore the execution time of each ker-nel call can be evaluated exactly when it is executed for the highest priority task. This time is that of the call itself plus the delay of the longest critical section in the kernel. Standard Unix unfitness for real-time Facilities to easily equip a board level system with standard de facto interfaces such as network interfaces or graphical users interfaces like the X Window system, as well as program compatibility and therefore access to widely used packages and tools, are arguments for adopting a system like Unix. However, Unix presents a mix of corporate requirements and technical solutions which reflect the state of the art of the early 1970s when it was designed and which do not fit for real-time. The shell program interprets the commands typed by the user and usually creates another task to provide the requested service. The shell then hangs up, waiting for the end of its child task before continuing with the shell script. The Unix kernel schedules tasks on a modified time-sliced round-robin basis; the priority is ruled by the scheduler and is not defined by the user. The standard Unix kernel is not particularly interested in interrupts, which usually come from a terminal and from memory devices. Data coming into the system do not drive the system as they do in real-time systems. The kernel is, by design, not preemptive. Once an application program makes an operating system call, that call runs to completion. As an example of this, when a task is created by a fork the data segment of the created task is initialized by copying the data segment of the creator task; this is done within the system call and may last as long as some hundred milliseconds. Thus, all standard Unix I/O requests are synchronous or blocked and a task cannot issue an I/O request and then continue with other processing. Instead, the requesting task waits until the I/O call is completed. A task does not communicate with I/O devices directly and turns the job over to the kernel, which may decide to simply store the data in a buffer. Early Unix designers optimized the standard file system for flexibility, not speed, or security, and consequently highly variable amounts of time may be spent finding a given block of data depending on its position in the file. Standard Unix allows designers to implement their own device drivers and to make them read or write data directly into the memory of a dedicated task. However, this is kernel code and the kernel then has to be relinked. Standard Unix does not include much interprocess communication and control. The ‘pipe’ mechanism allows the output of a task to be coupled to the input of another task of the same family. The other standard interprocess communication facility is the ‘signal’. The signal works like a software interrupt. Standard Unix permits programmers to set up shared memory areas and disk files. Later versions have a (slow) semaphore mechanism for protecting shared resources. Real-time standards The challenge for real-time standards is between real-time kernels which are stan-dardized by adopting the Unix standard interface and standard non-real-time Unixes modified for real-time enhancements. 8.1 REAL-TIME OPERATING SYSTEM AND REAL-TIME KERNEL 181 A set of application programming interfaces (API) extending the Unix interface to real-time have been proposed as the Posix 1003.1b standards. These interfaces, which allow the portability of applications with real-time requirements, are: • timer interface functions to set and read high resolution internal timers; • scheduling functions which allow getting or setting scheduling parameters. Three policies are defined: SCHED FIFO, a preemptive, priority-based scheduling, SCHED RR, a preemptive, priority-based scheduling with quanta (round-robin), and SCHED OTHER, an implementation-defined scheduler. • file functions which allow creation and access of files with deterministic perfor-mance; • efficient synchronization primitives such as semaphores and facilities for syn-chronous and asynchronous message passing; • asynchronous event notification and real-time queued signals; • process memory locking functions and shared memory mapping facilities; • efficient functions to perform asynchronous or synchronous I/O operations. 8.1.2 VxWorks Some real-time operating systems have been specifically built for real-time applica-tions. They are called real-time executives. An example is VxWorks .1 VxWorks has a modular design which allows mapping of several hardware architec-tures and enables scalability. It provides a symmetric system kernel to multiprocessor architectures of up to 20 processors. It provides services for creating and managing tasks, priority scheduling, periodic tasks release by signalling routines, binary or counting semaphore synchronization, asynchronous signalization, mailbox-based, pipe or socket communication, time-outs and watchdogs management, attachment of routines to interrupts, exceptions or time-outs, interrupt to task communication allowing triggering of sporadic tasks, and several fieldbus input–output protocols and interfaces. Mutual exclusion semaphores can be refined (1) to include a priority inheritance protocol in order to prevent priority inver-sion, (2) to defer the suppression of a task which is in a critical section, and (3) to detect the cross-references of routines that use the same semaphore (this allows avoid-ing deadlock by embedded calls). All tasks share a linear address space which allows short context switches and fast communication by common data and code sharing. When a paging mechanism, usually called a memory management unit (MMU), is supported by the hardware architecture, it can be managed at the task level to imple-ment local or global virtual memory, allowing better protection among tasks. However, since VxWorks is targeted to real-time applications, all tasks programs remain resident and there is no paging on demand or memory swapping. A library of interfaces has been customized to provide a Posix interface. Among numerous available development tools are a GNU interface and an Ada compiler, native as well as cross-development environments, instrumentation and analysis tools. 1 means an Internet link which is given at the end of the chapter. ... - tailieumienphi.vn