Real-Time Systems. Design Principles for Distributed Embedded Applications. Herman Kopetz. Second Edition (811374), страница 69
Текст из файла (страница 69)
At run time, this minimum inter-arrivalperiod must be enforced by the operating system by disabling the interrupt line toreduce the probability of erroneous sporadic interrupts (see Sect. 9.5.3).9.7.3Double Execution of TasksFault-injection experiments have shown that the double execution of tasks and thesubsequent comparison of the results is a very effective method for the detection oftransient hardware faults that cause undetected errors in the value domain [Arl03].The operating system can provide the execution environment for the double execution of application tasks without demanding any changes to the application task perse.
It is thus possible to decide at the time of system configuration which tasks shouldbe executed twice and for which tasks it is sufficient to rely on a single execution.9.7.4WatchdogsA fail-silent node will produce correct results or no results at all. The failure of a failsilent node can only be detected in the temporal domain. A standard technique is theprovision of a watchdog signal (heart-beat) that must be periodically produced by theoperating system of the node. If the node has access to the global time, the watchdogsignal should be produced periodically at known absolute points in time. An outsideobserver can detect the failure of the node as soon as the watchdog signal disappears.A more sophisticated error detection mechanism that also covers part of the valuedomain is the periodic execution of a challenge-response protocol by a node.
An outsideerror detector provides an input pattern to the node and expects a defined response patternwithin a specified time interval. The calculation of this response pattern should involve asmany functional units of the node as possible. If the calculated response pattern deviatesfrom the a priori known correct result, an error of the node is detected.Points to RememberlWe distinguish two levels of system administration in a component-baseddistributed real-time system: (1) the coordination of the message-based communication and resource allocation among the components, and (2) the establishment,236llllllllll9 Real-Time Operating Systemscoordination of, and control of the concurrent tasks within each one of thecomponents.Since the component software is assumed to be a unit of design, and a wholecomponent is the smallest unit of fault-containment, the concurrent tasks withina component are cooperative and not competitive.In an entirely time-triggered system, the static temporal control structure of all tasksis established a priori by off-line scheduling tools.
This temporal control structure isencoded in a Task-Descriptor List (TADL) that contains the cyclic schedule for allactivities of the node. This schedule considers the required precedence and mutualexclusion relationships among the tasks such that an explicit coordination of thetasks by the operating system at run time is not necessary.In a RT operating system that supports task preemption, each occurrence of asignificant event can potentially activate a new task and cause an immediateinterruption of the currently executing task. If components are replicated, caremust be taken that the preemption points at all replicas is at the same statement,otherwise replica determinism may be lost.The timing analysis of a C-task is not a local issue of a single task anymore; itbecomes a global system issue. In the general case it is impossible to give anupper bound for the WCET of a C-task.It is important to distinguish time as data and time as control.
Time as control ismore difficult to handle than time as data, because it may sometimes require adynamic data-dependent modification of the temporal control structure.Care must be taken that the integrity of data that is read or written concurrentlyby more than one task is maintained. In a time-triggered system, the taskschedules can be constructed in such a way that critical sections of tasks donot overlap.In order to reduce the dead time of a control loop, the instant of sampling, thetransmission of the sampled data to the control node, and the transmission of the setpoint data to the actuator node should be phase-aligned in a time-triggered system.In an interrupt driven software system, a transient error on the interrupt line mayupset the temporal control pattern of the complete node and may cause theviolation of important deadlines.A voting actuator may be constructed by assigning a small microcontroller to thephysical actuator that accepts the three input channels of the three lanes of aTMR system and votes on the messages received from the three lanes.Typically, for every output value, about three to seven input values must beobserved, not only to be able to diagnose erroneous measured data elements, butalso to check the proper operation of the actuators.Bibliographic NotesMany of the standard textbooks on operating systems contain sections on realtime operating systems, e.g., the textbook by Stallings [Sta08].
The most recentReview Questions and Problems237research contributions on real-time operating systems can be found in the annualProceedings of the IEEE Real-Time System Symposium and the Journal Real-TimeSystems from Springer Verlag.Review Questions and Problems9.1 Explain the difference between a standard operating system for a personalcomputer and an RT operating system within the node of a safety-critical realtime application!9.2 What is meant by a simple task, a trigger task, and a complex task?9.3 What is the difference between time as data and time as control?9.4 Why is the classical mechanism of semaphore operations sub-optimal for theprotection of critical data in a real-time OS? What alternatives are available?9.5 How is contact-bounce eliminated?9.6 When do we need interrupts? What is the effect of spurious interrupts? Howcan we protect the software from spurious interrupts?9.7 A node of an alarm monitoring system must monitor 50 alarms.
The alarmsmust be reported to the rest of the cluster within 10 ms by a 100 kbit/s CANbus. Sketch an implementation that uses periodic CAN messages (timetriggered with a cycle of 10 ms) and an implementation that uses sporadicevent-triggered messages, one for every occurring alarm. Compare the implementations from these points of view: generated load under the conditions ofno alarm and all alarms occurring simultaneously, guaranteed response time,and detection of a crash failure of the alarm node.9.8 Let us assume that an actuator has a failure rate of 106 FITs. If we construct avoting actuator by adding a microcontroller with a failure rate of 104 FITs tothis actuator, what is the resultant failure rate of the voting actuator?9.9 What is the difference between raw data, measured data, and agreed data?9.10 What is the difference between syntactic agreement and semantic agreement?Which technique is more important in the design of real-time applications?9.11 List some of the generic error-detection techniques that should be supportedby a real-time OS!9.12 Which types of failures can be detected by the double execution of tasks?Chapter 10Real-Time SchedulingOverview Many thousands of research papers have been written about how toschedule a set of tasks in a system with a limited amount of resources such that alltasks will meet their deadlines.
This chapter tries to summarize some importantresults of scheduling research that are relevant to the designer of real-time systems.The chapter starts by introducing the notion of a schedulability test to determinewhether a given task set is schedulable or not. It distinguishes between a sufficient,an exact, and a necessary schedulability test. A scheduling algorithm is optimal if itwill find a schedule whenever there is a solution. The adversary argument showsthat generally it is not possible to design an optimal on-line scheduling algorithm. Aprerequisite for the application of any scheduling technique is knowledge about theworst-case execution time (WCET) of all time-critical tasks.
Section 10.2 presentstechniques to estimate the WCET of simple tasks and complex tasks. Modernprocessors with pipelines and caches make it difficult to arrive at tight bounds forthe WCET. Anytime algorithms that contain a root segment that provides a result ofsufficient (but low) quality and an optional periodic segment that improves on thequality of the previous result point to a way out of this dilemma. They use theinterval between the actual execution time of the root segment of a concrete taskexecution and the deadline, i.e., the worst execution time of the root segment, toimprove the quality of the result. Section 10.3 covers the topic of static scheduling.The concept of the schedule period is introduced and an example of a simple searchtree that covers a schedule period is given. A heuristic algorithm has to examine thesearch tree to find a feasible schedule. If it finds one, the solution can be considereda constructive schedulability test. Section 10.4 elaborates on dynamic scheduling.
Itstarts by looking at the problem of scheduling a set of independent tasks by the ratemonotonic algorithm. Next, the problem of scheduling a set of dependent tasks isinvestigated. The priority-ceiling protocol is introduced and a schedulability test forthe priority ceiling protocol is sketched. Finally, the scheduling problem indistributed systems is touched and some ideas about alternative scheduling strategies such as feedback scheduling are given.H. Kopetz, Real-Time Systems: Design Principles for Distributed Embedded Applications,Real-Time Systems Series, DOI 10.1007/978-1-4419-8237-7_10,# Springer Science+Business Media, LLC 201123924010.110 Real-Time SchedulingThe Scheduling ProblemA hard real-time system must execute a set of concurrent real-time tasks in such away that all time-critical tasks meet their specified deadlines.
Every task needscomputational, data, and other resources (e.g. input/output devices) to proceed. Thescheduling problem is concerned with the allocation of these resources to satisfy alltiming requirements.10.1.1 Classification of Scheduling AlgorithmsThe following diagram (Fig. 10.1) presents a taxonomy of real-time schedulingalgorithms [Che87].Static Versus Dynamic Scheduling. A scheduler is called static (or pre-run-time) ifit makes its scheduling decisions at compile time.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
