Real-Time Systems. Design Principles for Distributed Embedded Applications. Herman Kopetz. Second Edition (811374), страница 66
Текст из файла (страница 66)
Coordinated task schedules2. The non-blocking write protocol3. Semaphore operations9.4.1Coordinated Static SchedulesIn a time-triggered system, the task schedules can be constructed in such a way thatcritical sections of tasks do not overlap. This is a very effective way to solve theproblem, because:1. The overhead of guaranteeing mutual exclusion is minimal and predictable.2. The solution is deterministic.Wherever possible, this solution should be selected.9.4.2The Non-blocking Write ProtocolIf, however, the tasks with the critical sections are event-triggered, we cannotdesign conflict-free coordinated task schedules a priori. The non-blocking write(NBW) protocol is an example for a lock-free real-time protocol [Kop93a] thatensures data integrity of one or more readers if only a single task is writing into thecritical region of data.Let us analyze the operation of the NBW for the data transfer across the interfacefrom the communication system to the host computer.
At this interface, there is one9.4 Inter-task Interactions225initialization: CCF := 0;writer:reader:start: CCF_old := CCF;start: CCF_begin := CCF;CCF := CCF_old + 1;if CCF_begin = odd<write to data structure>then goto start;CCF := CCF_old + 2;<read data structure>CCF_end := CCF;if CCF_end ¹ CCF_beginthen goto start;Fig.
9.4 The non-blocking write (NBW) protocolwriter, the communication system, and many readers, the tasks of the component.A reader does not destroy the information written by a writer, but a writer caninterfere with the operation of the reader. In the NBW protocol, the real-time writeris never blocked. It will thus write a new version of the message into the critical dataregion whenever a new message arrives. If a reader reads the message while thewriter is writing a new version, the retrieved message will contain inconsistentinformation and must be discarded. If the reader is able to detect the interference,then the reader can retry the read operation until it retrieves a consistent version ofthe data.
It must be shown that the number of retries performed by the reader isbounded.The protocol requires a concurrency control field, CCF, for every critical dataregion. Atomic access to the CCF must be guaranteed by the hardware. Theconcurrency control field is initialized to zero and incremented by the writer beforethe start of the write operation.
It is again incremented by the writer after thecompletion of the write operation. The reader starts by reading the CCF at the startof the read operation. If the CCF is odd, then the reader retries immediately becausea write operation is in progress. At the end of the read operation, the reader checkswhether the writer has changed the CCF during the read operation. If so, it retriesthe read operation again until it can read an uncorrupted version of the datastructure (see Fig.
9.4).It can be shown that an upper bound for the number of read retries exists if thetime between write operations is significantly longer than the duration of a write orread operation. The worst-case extension of the execution time of a typical realtime task caused by the retries of the reader is only a few percent of the originalworst-case execution time (WCET) of the task [Kop93a].Non-locking synchronization has been implemented in other real-time systems,e.g., in a multimedia system [And95]. It has been shown that systems with nonlocking synchronization achieve better performance than systems that lock the data.9.4.3Semaphore OperationsThe classic mechanism to avoid data inconsistency is to enforce mutual exclusiveexecution of the critical task sections by a WAIT operation on a semaphore variable2269 Real-Time Operating Systemsthat protects the resource.
Whenever one task is in its critical section, the other taskmust wait in a queue until the critical section is freed (explicit synchronization).The implementation of a semaphore-initialize operation is expensive, bothregarding memory requirements and operating system processing overhead. If aprocess runs into a blocked semaphore, a context switch must be made.
The processis put into a queue and is delayed until the other process finishes its critical section.Then, the process is dequeued and another context switch is made to reestablish theoriginal context. If the critical region is very small (this is the case in many realtime applications), the processing time for the semaphore operations can takesignificantly longer than the actual reading or writing of the common data.Both the NBW protocol and semaphore operation can lead to a loss of replicadeterminism.
The simultaneous access to CCF or a semaphore variable leads to arace condition that is resolved in an unpredictable manner in the replicas.9.5Process Input/OutputA transducer is a device that forms the interface between the plant (the physicalworld) and the computer (the cyber world). On the input side, a sensor transforms amechanical or electrical quantity to a digital form, whereby the discreteness of thedigital representation leads to an unavoidable error if the domain of the physicalquantity is dense. The last bit of any digital representation of an analog quantity(both in the domain of value and time) is non-predictable, leading to potentialinconsistencies in the cyber world representation if the same quantity is observed bytwo independent sensors.
On the output side, a digital value is transformed to anappropriate physical signal by an actuator.9.5.1Analog Input/OutputIn a first step, many sensors of analog physical quantities produce analog signals inthe standard 4–20 mA range (4 mA meaning 0% of the value range and 20 mAmeaning 100% of the value range) that is then transformed to its digital form by ananalog-to-digital (AD) converter. If a measured value is encoded in the 4–20 mArange, it is possible to distinguish a broken wire, where no current flows (0 mA),from a measured value of 0% (4 mA).Without special care, the electric-noise level limits the accuracy of any analogcontrol signal to about 0.1%. Analog-to-digital (AD) converters with a resolution ofmore than 10 bits require a carefully controlled physical environment that is notavailable in typical industrial applications.
A 16-bit word length is thus more thansufficient to encode the value of an RT entity measured by an analog sensor.The time interval between the occurrence of a value in the RT entity and thepresentation of this value by the sensor at the sensor/computer interface is9.5 Process Input/Outputvalue at RT entityin controlled objecttime delayat sensor227computer interfaceinputoutputdelay withincomputer systemvalue at RT entityin controlled objecttime delayat actuatorreal-timeFig. 9.5 Time delay of a complete I/O transactiondetermined by the transfer function of the particular sensor.
The step response of asensor (see Fig. 1.4), denoting the lag time and the rise time of the sensor, gives anapproximation of this transfer function. When reasoning about the temporal accuracyof a sensor/actuator signal, the parameters of the transfer functions of the sensors andthe actuators must be considered (Fig. 9.5). They reduce the available time intervalbetween the occurrence of a value at the RT entity and the use of this value for anoutput action by the computer. Transducers with short lag times increase the length ofthe temporal accuracy interval that is available to the computer system.In many control applications, the instant when an analog physical quantity isobserved (sampled) is in the sphere of control of the computer system.
In order toreduce the dead time of a control loop, the instant of sampling, the transmission ofthe sampled data to the control node and the transmission of the set-point data to theactuator node should be phase-aligned (see Sect. 3.3.4).9.5.2Digital Input/OutputA digital I/O signal transits between the two states TRUE and FALSE. In manyapplications, the length of the time interval between two state changes is ofsemantic significance. In other applications, the moment when the transition occursis important.If the input signal originates from a simple mechanical switch, the new stablestate is not reached immediately but only after a number of random oscillations(Fig. 9.6), called the contact bounce, caused by the mechanical vibrations of theswitch contacts.
This contact bounce must be eliminated either by an analog lowpass filter or, more often, within the computer system by software tasks, e.g.,debouncing routines. Due to the low price of a microcontroller, it is cheaper todebounce a signal by software techniques than by hardware mechanisms (e.g., a lowpass filter).A number of sensor devices generate a sequence of pulse inputs, where each pulsecarries information about the occurrence of an event. For example, distance measurements are often made by a wheel rolling along the object that must be measured. Everyrotation of the wheel generates a defined number of pulses that can be converted tothe distance traveled.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
