Real-Time Systems. Design Principles for Distributed Embedded Applications. Herman Kopetz. Second Edition (811374), страница 23
Текст из файла (страница 23)
Figure 3.4 depicts how the observed duration of an interval oflength 25 microticks can differ, depending on which node observes the start eventand the terminating event. The global tick, assigned by an observing node to anevent delimiting the interval is marked by a small circle in Fig. 3.4.3.2.3p/D-PrecedenceConsider a distributed computer system that consists of three nodes j, k, and m thatsupport a global time. Every node is to generate an event at its view of the globalinstants 1, 5, and 9.
An omniscient outside observer will see the scenario depictedin Fig. 3.5.All events that are generated locally at the same global clock tick will occurwithin a small interval p, where p P, the precision of the ensemble (because ofthe reasonableness condition). Events that occur at different ticks will be at leastD apart (Fig. 3.5). The outside observer should not order the events that occurwithin p, because these events are supposed to occur at the same instant.
Eventsthat occur at different ticks should be ordered. How many granules of silencemust exist between the event subsets such that an outside observer or anothercluster will always recover the temporal order intended by the sending cluster?Before we can answer this question (in Sect. 3.3.2) we must introduce the notionof p/D precedence.3.2 Time Measurement61microticks 0123456789 referenceclock zrespective macroticks of clocks j, kand m are connected by dotted linesclock jclock kclock mFig.
3.5 p/D precedenceGiven a set of events {E} and two durations p and D where p << D, such that forany two elements ei and ej of this set, the following condition holds:½zðei Þ zðej Þbp v ½zðei Þ zðej Þ>Dwhere z is the reference clock. Such an event set is called p/D-precedent.
p/Dprecedence means that a subset of the events that happen at about the same time(and that are therefore close together within p) is separated by a substantial interval(at least D) from the elements in another subset. If p is zero, then any two events ofthe 0/D-precedent event set occur either at the same instant or are at least a durationD apart.Assume a distributed system with a reasonable global time base with granularityg and two events, e1 and e2, that are produced at the same locally generated globaltick of two different nodes.
Due to the synchronization error, these events can differby up to but less than one granule. These events are observed by some of theother nodes.Because of the synchronization and digitalization error, the two (simultaneousby intention) events can be time-stamped by the observers with two ticks difference. In order to be able to establish the intended temporal order of events fromtheir time-stamps a sufficient duration of silence is needed before the next eventmay occur in order to ensure that the intended simultaneity of the events can alwaysbe recovered by all observers [Ver94].3.2.4Fundamental Limits of Time MeasurementThe above analysis leads to the following four fundamental limits of time measurement in distributed real-time systems with a reasonable global time base withgranularity g.1. If a single event is observed by two different nodes, there is always thepossibility that the time-stamps differ by one tick.
A one-tick difference in thetime-stamps of two events is not sufficient to reestablish the temporal order ofthe events from their time-stamps.623 Global Time2. If the observed duration of an interval is dobs, then the true duration dtrue isbounded byðdobs 2gÞ<dtrue <ðdobs þ 2gÞ3. The temporal order of events can be recovered from their time-stamps if thedifference between their time-stamps is equal to or greater than 2 ticks.4. The temporal order of events can always be recovered from their time-stamps, ifthe event set is at least 0/3g precedent.These fundamental limits of time measurement are also the fundamental limits tothe faithfulness of a digital model of a physical system.3.3Dense Time Versus Sparse TimeExample: It is known a priori that a particular train will arrive at a train station every hour.If the train is always on time and all clocks are synchronized, it is possible to uniquelyidentify each train by its time of arrival.
Even if the train is slightly off, say, by 5 min, andthe clocks are slightly out of synchronization, say, by 1 min, there will be no problem inuniquely identifying a train by its time of arrival. What are the limits within which a traincan still be uniquely identified by its time of arrival?Assume a set {E} of events that are of interest in a particular context. This set {E}could be the ticks of all clocks, or the events of sending and receiving messages. Ifthese events are allowed to occur at any instant of the timeline, then, we call thetime base dense.
If the occurrence of these events is restricted to some activeintervals of duration e, with an interval of silence of duration D between any twoactive intervals, then we call the time base e/D-sparse, or simply sparse for short(Fig. 3.6). If a system is based on a sparse time base, there are time intervals duringwhich no significant event is allowed to occur. Events that occur only in the activeintervals are called sparse events.It is evident that the occurrences of events can only be restricted if the givensystem has the authority to control these events, i.e., these events are in the sphereof control of the computer system [Dav79].
The occurrence of events outside thesphere of control of the computer system cannot be restricted. These external eventsare based on a dense time base and cannot be forced to be sparse events.0123456789microtickstimesparse eventsare only allowedto occure within the intervals pFig. 3.6 Sparse time-base3.3 Dense Time Versus Sparse Time63Example: Within a distributed computing system, the sending of messages can berestricted to some intervals of the timeline and can be forbidden at some other intervals –they can be designed to be sparse events.3.3.1Dense Time-BaseSuppose that we are given two events e1 and e2 that occur on a dense time base. Ifthese two events are closer together than 3g, where g is the granularity of the globaltime, then, it is not always possible to establish the temporal order, or even aconsistent order of these two events on the basis of the time-stamps generated by thedifferent nodes if no agreement protocol (see below) is applied.Example: Consider the scenario of Fig.
3.7 with two events, e1 and e2 which are 2.5granules apart. Event e1 is observed by node j at time 2 and by node m at time 1, while e2 isonly observed by node k that reports its observation “e2 occurred at 3” to node j and node m.Node j calculates a time-stamp difference of one tick and concludes that the events occurredat about the same time and cannot be ordered.
Node m calculates a time-stamp difference of2 ticks and concludes that e1 has definitely occurred before e2. The two nodes j and m havean inconsistent view about the order of event occurrence.Agreement Protocol. To arrive at a consistent view of the order of non-sparseevents within a distributed computer system (which does not necessarily reflect thetemporal order of event occurrence), the nodes must execute an agreement protocol. The first phase of an agreement protocol requires an information interchangeamong the nodes of the distributed system with the goal that every node acquires thediffering local views about the state of the world from every other node. At the endof this first phase, every correct node possesses exactly the same information asevery other node.
In the second phase of the agreement protocol, each node appliesa deterministic algorithm to this consistent information to reach the same conclusion about the assignment of the event to an active interval of the sparse timebase–the commonly agreed value. In the fault-free case, an agreement algorithmrequires an additional round of information exchange as well as the resources forexecuting the agreement algorithm.Agreement algorithms are costly, both in terms of communication requirements,processing requirements, and – worst of all – in terms of the additional delay theyintroduce into a control loop.
It is therefore expedient to look for solutions to theconsistent temporal ordering problem in distributed computer systems that do not01234216789referenceclock zclock j3Fig. 3.7 Different observedorder of two events e1 and e25clock kclock m643 Global Timerequire these additional overheads. The sparse time model, introduced below,provides for such a solution.3.3.2Sparse Time-BaseConsider a distributed system that consists of two clusters: cluster A generatesevents, and cluster B observes these generated events. Each one of the clusters hasits own cluster-wide synchronized time with a granularity g, but these two clusterwide time bases are not synchronized with each other. Under what circumstances isit possible for the nodes in the observing cluster to reestablish consistently theintended temporal order of the generated events without the need to execute anagreement protocol?If two nodes, nodes j and k of cluster A, generate two events at the same clusterwide tick ti, i.e., at tick ti j and at tick tik , then these two events can be, at most, adistance P apart from each other, where g > P, the granularity of the cluster-widetime.
Because there is no intended temporal order among the events that aregenerated at the same cluster-wide tick of cluster A, the observing cluster B shouldnever establish a temporal order among the events that have occurred at about thesame time. On the other hand, the observing cluster B should always reestablish thetemporal order of the events that have been occurred at different cluster-wide ticks.Is it sufficient if cluster A generates a 1g/3g precedent event set, i.e., after everycluster-wide tick at which events are allowed to be generated there will be silencefor at least three granules?If cluster A generates a 1/3g precedent event set, then it is possible that twoevents that are generated at the same cluster-wide granule at cluster A will be timestamped by cluster B with time-stamps that differ by 2 ticks.
The observing clusterB should not order these events (although it could), because they have beengenerated at the same cluster-wide granule. Events that are generated by cluster Aat different cluster-wide granules (3g apart) and therefore should be ordered bycluster B, could also obtain time-stamps that differ by 2 ticks.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
