Real-Time Systems. Design Principles for Distributed Embedded Applications. Herman Kopetz. Second Edition (811374), страница 24
Текст из файла (страница 24)
Cluster B cannotdecide whether or not to order events with a time-stamp difference of 2 ticks. Toresolve this situation, cluster A must generate a 1/4g precedent event set. Cluster Bwill not order two events if their time-stamps differ by 2 ticks, but will order twoevents if their time-stamps differ by 3 ticks, thus reestablishing the temporal orderthat has been intended by the sender.3.3.3Space-Time LatticeThe ticks of the global clock can be seen as generating a space-time lattice, asdepicted in Fig. 3.8.
A node is allowed to generate an event (e.g., send a message) atthe filled dots and must be silent at the empty dots. This rule makes it possible for3.3 Dense Time Versus Sparse Time65Fig. 3.8 Sparse time basesilencenodenodenodenodesilenceijklticks with output allowedticks with output not allowedreal-timethe receiver to establish a consistent temporal order of events without executing anagreement protocol. Although a sender is allowed to generate an event only at thefilled dots, this is still much faster than executing an agreement protocol, provided aglobal time base of sufficient precision is available. Events that are generated at thefilled dots of the sparse time lattice are called sparse events.Events that occur outside the sphere of control of the computer system cannot beconfined to a sparse time base: they happen on a dense time base and are thereforenot sparse events.
To generate a consistent view of events that occur in thecontrolled object, and that are observed by more than one node of the distributedcomputer system, the execution of an agreement protocol is unavoidable at theinterface between the computer system and the controlled object or other systemsthat do not participate in the global time.
Such an agreement protocol transforms anon-sparse event into a sparse event.3.3.4Cyclic Representation of TimeMany processes in the technical and biological world are cyclic [Win01]. A cyclicprocess is characterized by a regular behavior, where a similar set of action patternsis repeated in every cycle.Example: In a typical control system, real-time is partitioned into a sequence of controlcycles (Fig.
3.9). Every control cycle starts with reading the state variables of the controlledobject, proceeds with the execution of the control algorithm, and finishes with the output ofnew set-points to the actuators at the interface between the computer system and thecontrolled object.In the cyclic representation of time, the linear time is partitioned into cycles ofequal duration. Every cycle is represented by a circle, where an instant within acycle is denoted by the phase, i.e., the angular deviation of the instant from thebeginning of the cycle.
Cycle and phase thus denote an instant in a cyclic representation. In the cyclic representation of sparse time, the circumference of the circle isnot a dense line, but a dotted line, where the size and the distance between dots isdetermined by the precision of the clock synchronization.A sequence of consecutive processing and communication actions, such asthe actions in Fig. 3.9, are phase-aligned, if the termination of one action isimmediately followed by the start of the next consecutive action. If the actions663 Global Timereal-timelinear model of timecyclic model of time1 start of cycle1A observation of sensor inputA2real-time 1B 2 start of transmission of sensor data3B transmission of input dataA 2C 3 start of processing of control algorithmC processing of control algorithm4B6D 4 termination of processing35ED transmission of output dataEC65 start of output to actuatorsD5E output operation at the actuator46 termination of output operation11 start of next cycleFig.
3.9 Linear versus cyclic representation of time in a control systemwithin a RT-transaction (see Sect. 1.7.3) are phase-aligned, then the overallduration of the RT transactions is minimized.If we look at Fig. 3.9, we see that communication services in a typical controlloop are periodically required only in the intervals B and D of a cycle. The shorterthese intervals B and D, the better, since the dead time of the control loop isreduced.
This requirement leads to the model of pulsed data streams, where, in atime-triggered system, the highest possible bandwidth is allocated periodically inthe intervals B and D, while, during the rest of the cycle, the communicationbandwidth can be allocated to other requests [Kop06].An extension of the cyclic representation is the spiral representation of time,where a third axis is introduced to depict the linear progression of the cycles.3.4Internal Clock SynchronizationThe purpose of internal clock synchronization is to ensure that the global ticks of allcorrect nodes occur within the specified precision P, despite the varying drift rateof the local real-time clock of each node. Because the availability of a proper globaltime base is crucial for the operation of a distributed real-time system, the clocksynchronization should not depend on the correctness of a single clock, i.e., itshould be fault-tolerant.Every node of a distributed system has a local oscillator that (micro)ticks with afrequency determined by the physical parameters of the oscillator.
A subset of thelocal oscillator’s microticks called the ticks (or macroticks – see Sect. 3.2.1) isinterpreted as the global time ticks at the node. These global time ticks incrementthe local node’s global time counter.3.4.1The Synchronization ConditionThe global time ticks of each node must be periodically resynchronized withinthe ensemble of nodes to establish a global time base with specified precision.3.4 Internal Clock Synchronization67Fig. 3.10 SynchronizationconditionThe period of resynchronization is called the resynchronization interval Rint.
At theend of each resynchronization interval, the clocks are adjusted to bring them intobetter agreement with each other. The convergence function F denotes the offset ofthe time values immediately after the resynchronization. Then, the clocks driftagain apart until they are resynchronized at the end of the next resynchronizationinterval Rint (Fig. 3.10). The drift offset G indicates the maximum accumulateddivergence of any two good clocks from each other during the resynchronizationinterval Rint, where the clocks are free running. The drift offset Gdepends on thelength of the resynchronization interval Rint and the maximum specified drift rate rof the clock:G ¼ 2r RintAn ensemble of clocks can only be synchronized if the following synchronizationcondition holds between the convergence function F, the drift offset Gand theprecision P:F þ GbPAssume that at the end of the resynchronization interval, the clocks have divergedso that they are at the edge of the precision interval P (Fig.
3.10). The synchronization condition states that the synchronization algorithm must bring the clocks soclose together that the amount of divergence during the next free-running resynchronization interval will not cause a clock to leave the precision interval.Byzantine Error. The following example explains how, in an ensemble of threenodes, a malicious node can prevent the other two nodes from synchronizing theirclocks since they cannot satisfy the synchronization condition [Lam82]. Assume anensemble of three nodes, and a convergence function where each of the three nodessets its clock to the average value of the ensemble. Clocks A and B are good, whileclock C is a malicious two-faced clock that disturbs the other two good clocks in683 Global Timegood clock Aview at AB 4:05A 4:00C 3:55good clock B4:004:053:55view at BA 4:00B 4:05C 4:104:10“two-faced”malicious clock CFig. 3.11 Behavior of a malicious clocksuch a manner that neither of them will ever correct their time value (Fig.
3.11), andwill thus eventually violate the synchronization condition.Such a malicious, two-faced manifestation of behavior is sometimes called amalicious error or a Byzantine error (see also Sect. 6.1.3). During the exchange ofthe synchronization messages, a Byzantine error can lead to inconsistent viewsof the state of the clocks among the ensemble of nodes.
A special class ofalgorithms, the interactive-consistency algorithms [Pea80], inserts additionalrounds of information exchanges to agree on a consistent view of the time valuesat all nodes. These additional rounds of information exchanges increase the qualityof the precision at the expense of additional communication overhead. Otheralgorithms work with inconsistent information, and establish bounds for the maximum error introduced by the inconsistency. An example of such an algorithm is theFault-Tolerant-Average algorithm, described later in this section.
It has been shown[Lam85] that clock synchronization can only be guaranteed in the presence ofByzantine errors if the total number of clocks N (3k + 1), where k is the numberof Byzantine faulty clocks.3.4.2Central Master SynchronizationThis is a simple non-fault tolerant synchronization algorithm. A unique node, thecentral master, periodically sends the value of its time counter in synchronizationmessages to all other nodes, the slave nodes.
As soon as a slave node receives a newsynchronization message from the master, the slave records the time-stamp ofmessage arrival. The difference between the master’s time, contained in the synchronization message, and the recorded slave’s time-stamp of message arrival,corrected by the known latency of the message transport, is a measure of thedeviation of the clock of the master from the clock of the slave. The slave thencorrects its clock by this deviation to bring it into agreement with the master’s clock.3.4 Internal Clock Synchronization69The convergence function F of the central master algorithm is determined by thedifference between the fastest and slowest message transmission to the slave nodesof the ensemble, i.e., the latency jitter e between the event of writing the synchronization time value by the master and the events of message arrival time-stampingat all slaves.Applying the synchronization condition, the precision of the central masteralgorithm is given by:Pcentral ¼ e þ GThe central master synchronization is often used in the startup phase of a distributed system.
It is simple, but not fault tolerant, since a failure of the master endsthe resynchronization, causing the free-running clocks of the slaves to leave theprecision interval soon thereafter. In a variant of this algorithm, a multi-masterstrategy is followed: if the active master fails silently and the failure is detected by alocal time-out at a shadow master, one of the shadow masters assumes the role ofthe master and continues the resynchronization.3.4.3Fault-Tolerant Synchronization AlgorithmsTypically, distributed fault-tolerant clock resynchronization proceeds in three distinct phases.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
