Real-Time Systems. Design Principles for Distributed Embedded Applications. Herman Kopetz. Second Edition (811374), страница 21
Текст из файла (страница 21)
1.2.1).Delivery Order. A weaker order relation that is often provided by distributedcommunication systems is a consistent delivery order. The communicationsystem guarantees that all nodes see a defined set of related events in thesame delivery order. This delivery order is not necessarily related to thetemporal order of event occurrences or the causal relationship between events.Some distributed algorithms, e.g., atomic broadcast algorithms require a consistent delivery order.3.1.2ClocksIn ancient history, the measurement of durations between events was mainly basedon subjective judgment. With the advent of modern science, objective methods formeasuring the progression of time by using physical clocks have been devised.Digital Physical Clock. A (digital physical) clock is a device for measuring time.
Itcontains a counter and a physical oscillation mechanism that periodically generates543 Global Timean event to increase the counter. The periodic event is called the microtick of theclock. (The term tick is introduced in Sect. 3.2.1 to denote the events generated bythe global time).Granularity. The duration between two consecutive microticks of a digital physicalclock is called a granule of the clock. The granularity of a given clock can bemeasured only if there is a clock with a finer granularity available. The granularityof any digital clock leads to a digitalization error in time measurement.There also exist analog physical clocks, e.g., sundials that do not have granularity.
In the following, we only consider digital physical clocks.In subsequent definitions, we use the following notation: clocks are identified bynatural numbers 1, 2, . . ., n. If we express properties of clocks, the property isidentified by the clock number as a superscript with the microtick or tick number asa subscript. For example, microtick i of clock k is denoted by microtickik .Reference Clock. Assume an omniscient external observer who can observe allevents that are of interest in a given context (remember that relativistic effects aredisregarded).
This observer possesses a unique reference clock z with frequency f z,which is in perfect agreement with the international standard of time. The counter ofthe reference clock is always the same as that of the international time standard. Wecall 1/f z the granularity gz of clock z. Let us assume that f z is very large, say1015 microticks/s, so that the granularity gz is 1 fs (1015 s). Since the granularity ofthe reference clock is so small, the digitalization error of the reference clock isconsidered a second order effect and disregarded in the following analysis.Absolute Time-Stamp.
Whenever the omniscient observer perceives the occurrenceof an event e, she/he will instantaneously record the current state of the referenceclock as the time of occurrence of this event e, and, will generate a time-stamp for e.Clock(e) denotes the time-stamp generated by the use of a given clock to timestamp an event e. Because z is the single reference clock in the system, z(e) is calledthe absolute time-stamp of the event e.The duration between two events is measured by counting the microticks of thereference clock that occur in the interval between these two events. The granularity gk of a given clock k can now be measured and is given by the nominal numbernk of microticks of the reference clock z between 2 microticks of this clock k.The temporal order of events that occur between any two consecutive microticksof the reference clock, i.e., within the granularity gz, cannot be reestablished fromtheir absolute time-stamps.
This is a fundamental limit in time measurement.Clock Drift. The drift of a physical clock k between microtick i and microtick i + 1is the frequency ratio between this clock k and the reference clock, at the instant ofmicrotick i. The drift is determined by measuring the duration of a granule of clockk with the reference clock z and dividing it by the nominal number nk of referenceclock microticks in a granule:driftki ¼kzðmicrotickiþ1Þ zðmicrotickik Þnk3.1 Time and Order55Because a good clock has a drift that is very close to 1, for notational conveniencethe notion of a drift rate rki is introduced askzðmicrotickiþ1Þ zðmicrotickik Þk 1:ri ¼ knA perfect clock will have a drift rate of 0.
Real clocks have a varying drift rate that isinfluenced by environmental conditions, e.g., a change in the ambient temperature, achange in the voltage level that is applied to a crystal oscillator, or aging of the crystal.Within specified environmental parameters, the drift rate of an oscillator is bounded bythe maximum drift rate rkmax , which is documented in the data sheet of the resonator.Typical maximum drift rates rkmax are in the range of 102 to 107 s/s, or better, dependingon the quality (and price) of the oscillator.
Because every clock has a non-zero driftrate, free-running clocks, i.e., clocks that are never resynchronized, leave any boundedrelative time interval after a finite time, even if they are fully synchronized at startup.Example: During the Gulf war on February 25, 1991, a Patriot missile defense system failedto intercept an incoming Scud rocket. The clock drift over a 100-h period (which resulted in atracking error of 678 m) was blamed for the Patriot missing the Scud missile that hit anAmerican military barracks in Dhahran, killing 29 and injuring 97. The original requirementwas a 14-h mission. The clock drift during a 14-h mission could be handled [Neu95, p.
34].Failure Modes of a Clock. A physical digital clock can exhibit two types of failures.The counter could be mutilated by a fault so that the counter value becomes erroneous,or the drift rate of the clock could depart from the specified drift rate (the shaded areaof Fig. 3.1) because the clock starts ticking faster (or slower) than specified.3.1.3Precision and AccuracyOffset. The offset at microtick i between two clocks j and k with the samegranularity is defined astime of the reference clockoffsetijk ¼ zðmicrotickij Þ zðmicrotickik ÞFig.
3.1 Failure modes of aphysical clockerror in drift(rate error)perfect clockerror in counter(state error)a good clock witha bounded driftrate ρ stays withinthe shaded areatime of the local clock563 Global TimeThe offset denotes the time difference between the respective microticks of the twoclocks, measured in the number of microticks of the reference clock.Precision. Given an ensemble of n clocks {1, 2, . . ., n}, the maximum offsetbetween any two clocks of the ensemblenojkPi ¼8lbmaxj; kbn offsetiis called the precision Pof the ensemble at microtick i. The maximum of Pi over aninterval of interest is called the precision P of the ensemble. The precision denotesthe maximum offset of respective microticks of any two clocks of the ensembleduring a duration of interest. The precision is expressed in the number of microticksof the reference clock.Because of the drift rate of any physical clock, the clocks of an ensemble willdrift apart if they are not resynchronized periodically (i.e., brought closer together).The process of mutual resynchronization of an ensemble of clocks to maintain abounded precision is called internal synchronization.Accuracy.
The offset of clock k with respect to the reference clock z at microtick iis called the accuracyki . The maximum offset over all microticks i that is of interestis called the accuracyk of clock k. The accuracy denotes the maximum offset of agiven clock from the external time reference during a duration of interest.To keep a clock within a bounded interval of the reference clock, it must beperiodically resynchronized with an external time reference. This process of resynchronization of a clock with an external time reference is called external synchronization.If all clocks of an ensemble are externally synchronized with an accuracy A,then the ensemble is also internally synchronized with a precision of at most 2A.The converse is not true.
An ensemble of internally synchronized clocks will driftfrom the external time if the clocks are never resynchronized with the externaltime base.3.1.4Time StandardsIn the last decades, a number of different time standards have been proposed tomeasure the time difference between any two events and to establish the position ofan event relative to some commonly agreed origin of a time base, the epoch. Twoof these time bases are relevant for the designer of a distributed real-time computersystem, the International Atomic Time (TAI) and the Universal Time Coordinated(UTC).International Atomic Time (TAI – Temps Atomique Internationale). The needfor a time standard that can be generated in a laboratory gave birth to theInternational Atomic Time (TAI).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
