Real-Time Systems. Design Principles for Distributed Embedded Applications. Herman Kopetz. Second Edition (811374), страница 41
Текст из файла (страница 41)
Additionally, the following mechanisms and inadequacies mustbe considered that can cause a loss of the temporal dimension of determinism, evenif the system is L-deterministic:1. Task preemption and blocking. Task preemption and blocking extend the execution time of tasks and may delay a result until the acceptance window has beenclosed.2. Retry mechanisms. Any retry mechanism in hardware or software leads to anextension of the execution time and can cause an unacceptable delay of a valuecorrect result.3. Race conditions. A semaphore wait operation can give rise to non-determinism,because of the uncertain outcome regarding the process that will win the race forthe semaphore.
The same argument applies to communication protocols thatresolve the access conflict by relying on the outcome of non-determinate temporal decisions, such as CAN or, to a lesser degree, ARINC 629.1305 Temporal RelationsIn some designs where NDDCs are present, an attempt is made to reestablishreplica determinism by explicitly coordinating the decisions that could lead to a lossof determinism among the replicas, e.g., by distinguishing between a leader processand a follower process [Pow91]. If at all possible, inter-replica coordination shouldbe avoided because it compromises the independence of the replicas, and requiresadditional time and additional communication bandwidth.5.6.4Recovery of DeterminismA loss of determinism in an L-deterministic system can be avoided if the acceptance window is extended such that the probability of a deadline miss (i.e., that theresult is available at the end of the acceptance window) is reduced to an acceptablylow value.
This technique is often used to reestablish determinism at the macrolevel, even if the precise temporal behavior at the micro-level cannot be predicted.The main disadvantage of this technique is the increased delay until a result isdelivered, which causes an increase in the dead-time of control loops and thereaction time of reactive systems.Example: Many natural laws at the level of Newtonian physics are considered to bedeterministic, although the underlying quantum-mechanical processes at the micro-levelare non-deterministic.
The abstraction of deterministic behavior at the macro-level ispossible because the large number of involved particles and the large time-spans at themacro-level, relative to the duration of the processes at the micro-level, makes it highlyimprobable that non-deterministic behavior can be observed at the macro-level.Example: In a server farm of a cloud, where more than 100,000 L-deterministic VirtualMachines (VM) can be active at any instant, a failed VM can be reconfigured and restartedsuch that the intended result is still made available within the specified acceptance window.Such a system will have a deterministic behavior at the external level (see the FourUniverse Model in Sect. 2.3.1), although the implementation at the lower informationallevel behaves non-deterministically.The recovery of determinism at the external level (see the Four Universe Modelin Sect.
2.3.1) of systems that behave non-deterministically at the level of theimplementation is an important strategy when developing an understandablemodel of the behavior of a system-of-systems at the user level.Points to RememberlAn observation of an RT entity is an atomic triple < Name, tobs,Value > consisting of the name of the RT entity, the point in real time whenthe observation was made (tobs), and the observed value of the RT entity.A continuous RT entity has always a defined value set and can be observed atany instant, whereas a discrete RT entity can only be observed between theL_event and the R_event.Points to Rememberllllllllllllll131An observation is a state observation if the value of the observation contains theabsolute state of the RT entity. The time of the state observation refers to thepoint in real time when the RT entity was sampled.An observation is an event observation if it contains information about thechange of value between the old state and the new state.
The time of the eventobservation denotes the best estimate of the instant of this event.A real-time (RT) image is a current picture of an RT entity. An RT image is validat a given instant if it is an accurate representation of the corresponding RTentity, both in the value domain and time domain.A real-time (RT) object is a container within a node of the distributed computersystem holding an RT image or an RT entity. A real-time clock with a specifiedgranularity is associated with every RT object.The present value of a temporally accurate RT image is a member of the set ofvalues that the RT entity had in its recent history.The delay between the observation of the RT entity and the use of the RT imagecan cause, in the worst-case, a maximum error error(t) of the RT image that canbe approximated by the product of the maximum gradient of the value v of theRT entity multiplied by the length of the accuracy interval.Every phase-sensitive RT image imposes an additional constraint on the scheduling of the real-time task that uses this RT image.State estimation involves the building of a model of an RT entity inside an RTobject to compute the probable state of an RT entity at a selected future instant,and to update the corresponding RT image accordingly.If the behavior of an RT entity can be described by a continuous and differentiable variable v(t), the first derivative dv/dt is sometimes sufficient to get areasonable estimate of the state of the RT entity at the point tuse in the neighborhood of the point of observation.To decrease the coupling between sender and receiver the state estimation can beperformed in two steps: the sender performs a state estimation for the interval[tobs, tarr], and the receiver performs a state estimation for the interval [tarr, tuse].A particular message becomes permanent at a given node at that instant whenthe node knows that all the related messages that were sent to it, prior to the sendtime of this message, have arrived (or will never arrive).The time interval between the start of transmission of a message and the instantwhen this message becomes permanent at the receiver is called the action delay.To avoid incorrect behavior, the receiver must delay any action on the messageuntil after the action delay has passed.An RT image may only be used if the message that transported the image hasbecome permanent, and the image is temporally accurate.
In a system withoutstate estimation, both conditions can be satisfied only in the time window[tpermanent, tobs + dacc].No matter whether the receiver receives one or more out of set of replicatedidempotent messages, the result will always be the same.132lll5 Temporal RelationsDeterminism is a desired property of a computation that enables the prediction ofthe output at a future instant on the basis of a given initial state and timed inputs.The basic causes for replica non-determinism are: inconsistent inputs, a difference between the computational progress and the progress of the physical time inthe replicas (caused by differing oscillator drifts), and NDDCs.If at all possible, inter-replica coordination should be avoided because it compromises the independence of the replicas, and requires additional time andadditional communication bandwidth.Bibliographic NotesThe concept of temporal accuracy of a real-time object has been introduced in thereal-time object model presented in [Kop90].
Kim has extended this model andanalyzed the temporal properties of real-time applications using this model[Kim94]. The problem of replica determinism has been extensively studied in[Pol95]. An interesting philosophical treatment of the topics of causality anddeterminism can be found in [Bun08] and [Hoe10].Review Questions and Problems5.1 Give examples of RT entities that are needed to control an automotive engine.Specify the static and dynamic attributes of these RT entities, and discuss thetemporal accuracy of the RT images associated with these RT entities.5.2 What is the difference between a state observation and an event observation?Discuss their advantages and disadvantages.5.3 What are the problems with event observations?5.4 Give an informal and a precise definition of the concept of temporal accuracy.What is the recent history?5.5 What is the difference between a parametric RT image and a phase-sensitiveRT image? How can we create parametric RT images?5.6 What are the inputs to a state estimation model? Discuss state estimation in asystem with and without a global time-base.5.7 Discuss the interrelationship between state estimation and composability.5.8 What is a hidden channel? Define the notion of permanence.5.9 Calculate the action delay in a distributed system with the following parameters: dmax ¼ 20 ms, dmin ¼ 1 ms:(a) No global time available, and the granularity of the local time is 10 ms(b) Granularity of the global time 20 ms5.10 What is the relationship between action delay and temporal accuracy?5.11 Define the notion of determinism! What is L-determinism?Review Questions and Problems1335.12 Give an example that shows that a local time-out can lead to replicanon-determinism.5.13 What mechanisms may lead to replica non-determinism?5.14 How can we build a replica-determinate system?5.15 Why should explicit inter-replica coordination be avoided?5.16 Calculate the action delay in the system of Fig.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
