Real-Time Systems. Design Principles for Distributed Embedded Applications. Herman Kopetz. Second Edition (811374), страница 40
Текст из файла (страница 40)
Many natural laws of physical systemsconform to this definition of determinism. In a digital computer model of a physical1265 Temporal Relationssystem there is no dense time. In a deterministic distributed computer system, wemust assume that all events, e.g., the observation of the initial state at instant t andthe timed inputs, are sparse events on a sparse global time base (see Sect. 3.3) inorder that the temporal properties of and the relations (such as simultaneity) amongthe events that occur in the different nodes of the distributed system can beprecisely specified despite the finite precision of the clock synchronization andthe discrete time-base.
This transformation of dense events in the physical world tosparse events in the cyber world (the distributed computer system), performed by anagreement protocol (see Sect. 3.3.1), reduces the faithfulness of the computermodel, since events that are closer than the granularity of the time-base cannot beordered consistently.In a real-time context, the concept of determinism requires that the behavior of asystem is predictable in the domains of values and time. Neglecting the temporaldimension leads to a reduced notion of determinism – we call it logical (L) determinism. L-determinism can be defined as follows: A system behaves L-deterministicallyif, given an initial state and a set of ordered inputs, then the subsequent states andthe values of subsequent outputs are entailed.The use of the word determinism in everyday language relates the futurebehavior of a system as a consequence of its present state.
Since in a time-lesssystem the concept of future does not exist, L-determinism does not capture theeveryday meaning of the word determinism.Example: In the above example of a braking system, it is not sufficient for the establishment of correctness to demand that the braking action will eventually take place. Themaintenance of an upper real-time bound for the start of the braking action (the end point ofthe acceptance window), e.g., that the braking action will start 2 ms after the brake pedalhas been pressed, is an integral part of correct behavior.Deterministic behavior of a component is desired for the following reasons:lllAn entailment relation between initial state, input, output and time simplifies theunderstanding of the real-time behavior of the component (see also Sect.
2.1.1).Two replicated components that start from the same initial state and receive thesame timed inputs will produce the same results at about the same time. Thisproperty is important if the results of a faulty channel are to be masked (outvoted) by the correct results of two correct channels (see Sect. 6.4.2) as exemplified in the above example on the braking system of a car.The testability of the component is simplified, since every test case can bereproduced, eliminating the appearance of spurious Heisenbugs (see Sect. 6.1.2).Determinism is a desired property of behavior.
The implementation of a computation will achieve this desired property with an estimated probability.An implementation can fail to meet this desired property of determinism for thefollowing reasons:1. The initial states of the computations are not precisely defined.2. The hardware fails due to a random physical fault.5.6 Determinism1273.
The notion of time is unclear.4. The system (software) contains design errors or Non-Deterministic DesignConstructs (NDDC) that lead to unpredictable behavior in the value domain orin the temporal domain.From the point of view of fault-tolerance, every loss of determinism of a replicatedchannel is tantamount to a failure of that channel that eliminates the further faultmasking capability of the fault-tolerant system.In order to realize replica-deterministic behavior in an implementation of a faulttolerant distributed real-time computer system, we must ensure that:lllllThe initial state of all involved computations is defined consistently. It isimpossible to build a replica-deterministic distributed real-time system withoutthe establishment of some sort of a sparse global time base for the consistenttime-stamping of the events in order to be able to determine whether an event isincluded in the initial state or not.
Without a sparse global time base and sparseevents, simultaneity cannot be resolved consistently in a distributed system,possibly resulting in an inconsistent temporal order of the replicated messagesthat report about these simultaneous events. Inconsistent ordering results in theloss of replica determinism.The assignment of events to a sparse global time-base can be established at thesystem level by the generation of sparse events or at the application level by theexecution of agreement protocols which assign consistently dense events tosparse intervals.The message transport system among the components is predictable, i.e.,the instants of message delivery can be foreseen and the temporal order of thereceived messages is the same as the temporal order of the sent messages acrossall channels.The computer system and the observer (user) agree on a precise notion ofreal-time.All involved computations are certain, i.e., there are no program constructs inthe implementation that produce arbitrary results or contain NDDCs, and that thefinal result of a computation will be available during the anticipated acceptancewindow.If any one of the above conditions is not satisfied, then the fault-maskingcapability of a fault-tolerant system may be reduced or lost.5.6.2Consistent Initial StatesCorrect replicated channels that are introduced to mask a failure will only produceidentical results if they start from the same initial state and receive the same inputsat the same instants.1285 Temporal RelationsAccording to Sect.
4.2.1, the state of a component can only be defined if there isa consistent separation of past events from future events. The sparse time model,introduced in Sect. 3.3, provides for such a consistent separation of past events fromfuture events and makes it possible to define the instants where the initial state of adistributed system is consistently defined. Without a sparse global time, the establishment of a consistent initial state of replicated components of a distributedsystem is difficult.A sensor is a physical device that will eventually fail.
In order to mask the failureof a sensor, multiple sensors must be provided in a fault-tolerant system that measure,either directly or indirectly, the same physical quantity. There are two reasons whyredundant observations of a physical quantity by replicated sensors will deviate:1. It is impossible to build perfect sensors. Every real sensor has a finite measurement error that limits the accuracy of the observed value.2.
The quantities in the physical world are normally analog values, but their representations in cyber-space are discrete values, leading to a discretization error.It is therefore necessary to execute agreement protocols at the boundary betweenthe physical world and cyber space in order that all replicated channels receive theconsistent (exactly the same) agreed input data (see Sect. 9.6). These agreementprotocols will present the same set of values at the same sparse time interval to allreplicated channels.5.6.3Non-deterministic Design ConstructsA distributed computation that starts from a well-defined initial state can fail toreach the envisioned goal state for the following reasons:1. A hardware fault or design error causes the computation to crash, to deliver anincorrect result, or to delay the computation beyond the end of the agreedtemporal acceptance window.
It is the goal of a fault-tolerant design to maskthese kinds of failures.2. The communication system or the clocking system fails.3. A non-deterministic design constructs (NDDC) destroys the determinism. A lossof determinism, caused by an NDDC, eliminates the fault-masking capability ofa fault-tolerant system.The undesired effect of an NDDC can be in the value domain or in the temporaldomain.
A basic assumption in the design of a fault-tolerant system that masksfailures by comparing the results of replica-determinate channels is the statisticalindependence of failures in different channels. This assumption is violated if anNDDC is the cause of the loss of determinism, because the same NDDC may appearin all replicated channels. This leads to dangerous correlated failures of the replicated channels.5.6 Determinism129The following list is indicative of constructs that can lead to a loss of determinismin the value domain (i.e., L-determinism):1.
Random number generator. If the result of a computation depends on a randomnumber that is different for each channel, then the determinism is lost. Communication protocols that resolve a media-access conflict by reference to a randomnumber generator, such as the bus-based CSMA/CD Ethernet protocol, exhibitnon-determinism.2. Non-deterministic Language Features. The use of a programming languagewith non-deterministic language constructs, such as the SELECT statement inan ADA program, can lead to the loss of replica determinism.
Since theprogramming language does not define which alternative is to be taken at adecision point, it is left up to the implementation to decide the course of action tobe taken. Two replicas may take different decisions.3. Major decision point. A major decision point is a decision point in an algorithmthat provides a choice between a set of significantly different courses of action.If the replicated components select different computational trajectories at amajor decision point, then the states of the replicas will start to diverge.Example: Consider the case where the result of a timeout check determines whether aprocess continues or backtracks. This is an example for a major decision point.4.
Preemptive scheduling. If dynamic preemptive scheduling is used then thepoints in the computations where an external event (interrupt) is recognizedmay differ at the different replicas. Consequently, the interrupting processes seedifferent states at the two replicas at the point of interruption. They may reachdifferent results at the next major decision point.5. Inconsistent message order. If the message order in the replicated communication channels is not identical, then the replicated channels may produce differentresults.Most of the above constructs can also cause a loss of determinism in thetemporal domain.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
