302
`
`DISTRIBUTED SYSTEMS FOR SYSTEM ARCHITECTS
`
`12.6 FLOW CONTROL
`
`Flow control is a fundamental paradigm of distributed real-time. In fact, given
`that b~al1(dwidth and computational power are finite, it is impossible to guar(cid:173)
`antee timeliness if the load flow on the system is not controlled. The role of
`real-time flow control is to regulate the global load flow of the system and to
`throttle the instantaneous flow of individual source classes in terms of their
`arrival pattern (rate and amount of data), so as to preserve the capacity of the
`system to exhibit bounded response times.
`The control of a periodic flow is a simple task. A sporadic flow, such as
`the one produced by sensors of discrete real-time entities, is harder to treat.
`In Section 12.1 we have discussed the possibility of a bursty sporadic arrival
`pattern being smoothened over a longer interval (see Figure 12.5b), as long as
`this is allowed by the service latency requirements of the arriving requests, and
`the interval is not greater than the burst period, if one exists. The mechanism
`that makes this possible is called rate-based flow control, or rate control, and
`helps balance system load without glitches. Credit control is a load control
`scheme based on allocating a certain amount of credit units (for example octets)
`to sinks (e.g.
`recipients), per flow of information coming from a source (e.g.
`sender or a group of senders). When the credit is over, the recipient refuses to
`accept more information. Credit complements rate control in case of sporadic
`real-time operation, whenever it is necessary to perform resource reservation
`for significant amounts of information of bursty nature.
`Flow control is of little use if the average load is misadjusted in the first place.
`As such, there are measures which can be considered of implicit flow control,
`such as compacting information at the sensor representatives before sending it
`to the core of the system, or eliminating redundant messages corresponding to
`a same event (e.g. fire alarm), that otherwise generate event-message showers.
`
`12.7 SCHEDULING
`
`Real-time is not about having a lot of bandwidth and computational power,
`and even if it were, we would always find ways of exhausting it. Alternatively,
`we may think we solve the problem by letting the critical task always get the
`processor when needed. But the processor power may have to be shared by
`several critical tasks and the problem surfaces again. Even if we think we have
`enough power to guarantee the timely execution of our critical task(s), chanees
`are we are using it up at the wrong moment. Remember La Fontaine's Fable
`of the Hare and the Turtle? Figure 12.8 illustrates this famous tale adapted to
`real-time scheduling!.
`System TURTLE is a slow system, with relative speed s==l, context switch
`delay c==l, scheduling first the task that must finish earlier (this is called earliest
`deadline first, and is a sensible real-time scheduling policy that we are going to
`study). System HARE is a very fast system, with relative speed s==10, almost
`
`1We owe this example to Gerard LeLann.
`
`Exhibit 2026 Page 319
`
`

`

`PARADIGMS FOR REAL-TIME
`
`303
`
`negligible context switch delay c==O.Ol, scheduling first the task that comes first
`(this is called first-come-first-served, and is a not so sensible scheduling policy
`for real-time). The work presented to either system at time t is:
`two task
`execution requests arrive at approximately the same time t, task A before task
`B; task A, execution time Xa==270 relative time units, deadline Da==t+290;
`task B, execution time Xb==15, deadline Db==t+28.
`
`TURTLE:
`
`HARE:
`
`A
`B
`A
`~ '~1.~;;rffiPJi 1/~dW ~ , ~ ~ "~;j~'wJ. ~
`,<-- ~. /·~/h /
`.'. I:://~,.i ········i
`r.
`t+16 t+17
`t+287
`t+1
`
`/
`
`i
`
`i
`
`Figure 12.8.
`
`The Hare and the Turtle Schedulers
`
`Let us analyze how system TURTLE serves the job. Observing the figure, we
`see that it starts by releasing A, then switches right after to B, because it has
`the earliest deadline, B executes during 15 time units, terminating before the
`deadline. Then, it switches to A again, finishing after 270 time units, before
`the deadline.
`What happens when system HARE serves the job? We see that it starts
`serving A immediately it arrives, and A will run to completion, according to
`the first-come-first-served policy. The rationale behind the HARE approach is
`that the system is so fast that it serves any request "quickly" enough to get
`ready for the next. However, A executes in 27 time units (speed of 10), the
`context switches in almost negligible time to B, B executes in 1.5 time units,
`and ... it misses the deadline by half a time unit!
`The lesson to be learned is that real-time is about determinism and guar(cid:173)
`antees, rather than speed, and in this context the scheduling paradigm is
`concerned with using the available resources in the right way in order to help
`the system (its programs, its algorithms) achieve timeliness guarantees.
`
`12.7.1 Types of Scheduling
`
`Scheduling assumes several facets, according to the objectives of the system,
`and to the problems posed, such as the load assumptions. Most non real-time
`scheduling policies aim at fairness and reasonable performance, in the access
`to resources by the several users. Real-time systems, on the other hand, aim at
`fulfilling timeliness requirements, if need be in detriment of the performance of
`less important tasks. Let us define some terminology before advancing further.
`Table 12.1 introduces some generic parameters specifying instants and intervals
`(that is, events and durations) related with task execution timing. Figure 12.9
`depicts a task execution.
`The main classes of real-time tasks are: aperiodic, periodic, and sporadic,
`named according to their main pattern of execution request arrivals (see Ar(cid:173)
`rival Distributions in Section 12.1). Aperiodic tasks are impossible to treat
`deterministically, the best that can be done is service on a best-effort man-
`
`Exhibit 2026 Page 320
`
`

`

`304
`
`DISTRIBUTED SYSTEMS FOR SYSTEM ARCHITECTS
`
`Table 12.1.
`
`Task Execution Timing Parameters
`
`Not.
`
`Designation
`
`Description
`
`trigger instant
`deferral time
`request instant
`min. inter-req. time
`
`min. termin. time
`max. termin. time
`worst-case exec. time
`laxity
`earliest term. instant
`typo termin. instant
`latest term. instant
`max. interfere time
`max. blocking time
`priority
`max. utilization factor
`
`arrival instant of event causing the execution
`delay introduced before execution request (offset)
`instant of execution request (release)
`minimum interval between any two consecutive re-
`quests (equals request period TR, for periodic tasks)
`minimum elapsed time from request to termin. event
`worst-case elapsed time from request to termin. event
`maximum task duration in continuous execution
`slack time available for execution (Tx max - Tw C ET )
`earliest that task may complete, also called liveline
`desired instant of completion (targetline)
`latest that task may complete, also called deadline
`max. time task can be suspended by higher pri. tasks
`max.
`time task can be blocked b).' lower pri. tasks
`importance of task w.r.t timing (highest is often 0)
`max. percent. of CPU utilization (TWCET/Txmax)
`
`TXmin
`TXmax
`TWCET
`T1ax
`Tzive
`Ttrgt
`T dead
`Tint
`Tblk
`
`pU
`
`ner. Periodic tasks are the workhorse of static schedule design. Sporadic tasks
`serve applications that do not have a regular behavior (request arrival is not
`periodic).
`
`Figure 12.9.
`
`Task Execution Timings
`
`We say scheduling is static, if all the scheduling plans or scheduling condi(cid:173)
`tions are elaborated beforehand. Static scheduling is also called off-line schedul(cid:173)
`ing, as it assumes predicting timing variables such as execution times, request
`times, resource conflicts, and so forth, and/or assigning static levels of impor(cid:173)
`tance to tasks (e.g., fixed priorities). On the other hand, dynamic scheduling,
`also called on-line, computes the schedule at run-timje,.~ based on the analysis
`of a list of tasks ready for execution.
`Fixed-priority scheduling was very common in earlier real-time operating
`systems, and is still widely used. With dynamic-priority scheduling, priority
`may change during execution, to reflect the varying importance of tasks, e.g.
`as deadlines approach.
`When the scheduler can interrupt the execution of a task in order to sched(cid:173)
`ule a new one, normally of higher priority, we say scheduling is preemptive.
`
`Exhibit 2026 Page 321
`
`

`

`PARADIGMS FOR REAL-TIME
`
`305
`
`Otherwise, if tasks once scheduled run to completion, we say the scheduler is
`non-preemptive.
`Centralized scheduling is performed at a central point, which is normal in
`single-processor systems. In distributed systems scheduling, this point would
`also become a single point of failure. In consequence, decentralized scheduling
`is preferred for distributed systems.
`
`12.7.2 Schedulability
`The usual scheduling scenario is that there is a set of N tasks with several
`deadlines, to be executed in the processor, over a maximum interval T xmax ,
`corresponding to the latest deadline. In a periodic task set, the interval corre(cid:173)
`sponds to the least common multiple of the periods. This situation is presented
`to the designer or design tool at design time for off-line schedulers, or to the
`scheduler itself for on-line or dynamic schedulers. One has to determine if the
`schedule is feasible. This action is termed schedulability testing and is an
`important step of scheduling. There are three classes of schedulability tests:
`
`• sufficient- passing it indicates that the task set is schedulable
`• necessary- failing it indicates that the task set is not schedulable
`• exact- passing indicates schedulability; failing indicates non-schedulability
`
`We say a scheduler is optimal, when it always finds a feasible schedule if one
`exists. Sufficient or necessary schedulability tests have an error margin but are
`simpler than exact ones, and sometimes the only reasonable solution. Obvious
`such tests are checking that T xmax - TWCET 2:: 0, or TRmin - TXmax 2::. o.
`The simplest tests are utilization-based schedulability tests, which fail if the
`schedule will be using the CPU more than a certain percentage. Consider a set
`of N periodic tasks, each with an individual utilization factor of TWCET/TR :
`the schedulability test expression for this set is E~l (TWCET/TR)
`:::; Umax ,
`where Umax depends on the algorithm being used (ultimately, the CPU cannot
`be used more than 100%!).
`Utilization-based schedulability tests are go-no-go sufficient tests. An al(cid:173)
`ternative approach is the response-time-based test, explained as follows. The
`individual WCET of each task is computed. Then,
`it is used to derive the
`actual worst-case termination (or response) time, by adding to the WCET the
`total time the task must yield to all other tasks (e.g. higher priority ones) on
`account of the scheduling policy, Le., the interference time (Tint). The process
`is repeated for each task. The schedulability test finalizes by simply comparing
`the computed with the desired maximum termination times. The response(cid:173)
`time-based analysis has the advantage of being an exact test, and of giving a
`quantitative output.
`
`12.7.3 Static Scheduling
`
`Static or off-line scheduling has to take into account worst-case execution times,
`and urgency, resources, causal precedence, synchronization and deadline re(cid:173)
`quirements of all tasks involved. The schedule is computed by determining
`
`Exhibit 2026 Page 322
`
`

`

`306
`
`DISTRIBUTED SYSTEMS FOR SYSTEM ARCHITECTS
`
`the exact points in time where each task or code module should be launched
`to meet its deadline. Schedulability testing here means: can the schedule be
`constructed? Once constructed, the schedule is executed repeatedly, Le., in a
`periodic way.
`With static schedules, a way of improving schedulability is by using mode
`changes. A mode is a well-contained phase of the system operation (e.g., take(cid:173)
`off, cruise, landing in a plane) such that only the necessary tasks, resources and
`respective requirements are considered for scheduling.
`A widely known algorithm for static scheduling of independent periodic tasks
`in a single processor is rate-monotonic (Liu and Layland, 1973). It is a pre(cid:173)
`emptive algorithm based on fixed or static priorities, with the following addi(cid:173)
`tional characteristics:
`• optimal when maximum termination time equals period (Txmax = TR)
`• all worst-case execution times (TweET) are known
`• priorities are assigned in inverse order of the period
`
`The scheduler, exemplified in Figure 12.10, wakes-up at every start of period,
`and schedules the highest priority ready task, preempting the running task
`task T1 , period TR == 1, duration
`if necessary.
`In the example, we have:
`TWCET == 0.5; task T2 , TR == 5, TWCET == 1; and task T 3 , TR == 10, TWCET ==
`3. When all periods are multiples of the smallest, Umax == 100%, which is
`the case of the example, so the schedulability test goes: L::~=l (TWCET /TR ) ==
`0.5/1 + 1/5 + 3/10 == 1, which means it is OK.
`
`T1
`
`[;3 T2 D T3
`
`5
`
`10 t
`
`Figure 12.10.
`
`Rate Monotonic Scheduler in Action
`
`12.7.4 Scheduling of Sporadic Tasks
`
`Testing schedulability is easy for periodic tasks, since the arrival pattern of the
`future (period) is known. Attaining and analyzing the schedulability of task
`sets where periodic tasks coexist with sporadic tasks is a difficult "task" per se,
`because: (a) we may no longer make decisions completely off-line; (b) it may
`be hard problem, even when done on-line. Of course, we may consider that
`a sporadic task is a pseudo-periodic task whose period is the minimum inter(cid:173)
`arrival time (TB »T]). This has the consequence that most of the service
`periods are empty, leading to a very low processor utilization.
`Another approach is the sporadic server, for patterns where T xmax « T/,
`that is, single, rare, but very urgent sporadics (i.e., burst length is NB == 1,
`and TB ~ T]). The server task is a periodic task with high priority, scheduled
`
`Exhibit 2026 Page 323
`
`

`

`PARADIGMS FOR REAL-TIME
`
`307
`
`in competition with all the other tasks of the system. When it runs, it serves
`any pending sporadic request until exhausting its allocated execution time.
`The dynamic scheduling approach applies well to task sets containing spo(cid:173)
`radic tasks. There is an algorithm based on dynamic priorities which is ad(cid:173)
`It is called earliest(cid:173)
`equate for sporadics, and optimal for periodic tasks.
`deadline-first (EDF). When the scheduler wakes-up it evaluates the time-to(cid:173)
`deadline of every task, and orders their priorities by the inverse of that value:
`the task that has the earliest deadline receives the highest priority. This algo(cid:173)
`rithm is very elegant and intuitive, and can achieve a maximum utilization of
`Umax = 100%.
`Dynamic deadline-oriented algorithms, such as EDF, are very adequate for
`scheduling of sporadics, since they adapt the priorities of the task set to newly
`requested sporadic tasks.
`
`12.7.5 Resource Conflicts and Priority Inversion
`
`If two or more tasks compete for resources other than the processor itself,
`such as a mutual exclusion semaphore or critical section, they become inter(cid:173)
`dependent. This happens frequently in distributed systems, so we give a bit
`of attention to this problem.
`In most of these cases the exact schedulability
`test becomes an NP-complete problem, that is, it exhibits a computationally
`infeasible complexity. However, the computational powerxtime concerned with
`finding a schedule should be much lower than the power x time required to run
`the tasks themselves. In consequence, on-line scheduling resorts to simpler but
`inexact tests that sometimes have consequences.
`For example, the scheduling of periodic tasks with or without sporadics may
`suffer what is known as priority inversion: a task loses the processor during
`a non-negligible and non-desirable amount of time, called blocking time (Tblk ),
`blocked on a resource held by lower priority tasks. Consider the following
`example of a communications and telemetry system:
`• A scheduler provides preemptive scheduling based on fixed priorities. The
`system has three tasks. Two of them compete for an information channel, a
`critical resource accessed in mutual exclusion (mutex semaphor).
`• The highest priority task is an information dispatcher task, which takes care
`of dispatching all data to and from the channel, so that it does not overrun.
`• The lowest priority task is a meteorological data gathering task, running
`infrequently with low priority, to publish data on the channel.
`• The middle priority task is a communications task, handling system's com(cid:173)
`munications. It does not compete for the information channel.
`Now the "scene of the crime", depicted in Figure 12.11a:
`
`• 1. The meteo task (L) acquires the mutex and publishes its information.
`• 2. The dispatcher task (H) runs: H preempts L, tries to acquire the mutex
`and blocks on it, awaiting for the meteo task to release it. L runs again.
`
`Exhibit 2026 Page 324
`
`

`

`308
`
`DISTRIBUTED SYSTEMS FOR SYSTEM ARCHITECTS
`
`in the meantime, the communications task (M) requests ser(cid:173)
`• 3. However,
`vice: M preempts L, and runs to completion.
`• Conclusion: H was blocked, first by L then by M through L.
`
`H M L
`
`a~q
`.<:{:{:X~:}::}::}?~??};:::::II
`
`~rel
`
`H
`
`M
`
`et--Tblk---+--i
`(a)
`~.m Running
`
`t~
`
`® @ @) @
`
`'t
`
`c:JCJ Priority p inherited
`
`(b)
`..~ Mutex Acquired
`
`c=J Suspended
`
`[',::',:,.',·1 Blocked
`
`Figure 12.11. Resource Conflicts: (a) Priority Inversion; (b) Priority Inheritance
`
`Is this example realistic? You should have replied yes, because this is what
`happened with the on-board computer of the NASA Mars Pathfinder probe
`that landed on that planet in 1997. Shortly after the Sojourner Rover- the
`small autonomous guided vehicle (AGV) released from the probe- started
`collecting data, the spacecraft began experiencing total system resets. These
`were caused by a watchdog mechanism that reacted to absence of activity from
`the (blocked) dispatcher task, and the system was re-initialized. Fortunately,
`this recovery strategy was acceptable at that point of the mission, otherwise,
`it could have been a catastrophe.
`What happened was a classical case of priority inversion, a syndrome identi(cid:173)
`fied long ago (Lauer and Satterwaite, 1979), which also occurs with networking
`(Peden and Weaver, 1988). Solutions for it were first addressed in (Cornhill
`et aI., 1987; Sha et aI., 1990).
`In order to remedy the problem, the authors
`proposed a mechanism which introduces dynamic priority setting to a set of
`tasks with initial fixed priorities, called priority inheritance:
`•
`the dynamic priority of a process is the maximum of its initial priority and
`the priorities of any process blocked on account of it
`With priority inheritance, the Mars Pathfinder scene would be scheduled as in
`Figure 12.11b:
`• 1. The meteo task (L) runs with priority l, acquires the mutex and publishes
`• 2. The dispatcher task (H) runs with priority h: H preempts L,
`tries to
`acquire the mutex and blocks on it, awaiting for the meteo task L, which
`runs again inheriting H's priority, h.
`• 3. The communications task (M), with priority m, becomes ready for exe(cid:173)
`cution: M waits for L, since h (current pri. of L) is higher than m.
`• 4. L finishes and releases the mutex unblocking H, which grabs the processor
`(h > m), acquires the mutex, and runs to completion. Then, M runs.
`• Conclusion: H had the minimum blocking possible: waiting for L to finish.
`
`Exhibit 2026 Page 325
`
`

`

`PARADIGMS FOR REAL-TIME
`
`309
`
`12.7.6 Scheduling in Distributed Systems
`
`Some single processor algorithms behave well in distributed systems, but others
`are inadequate or have to be enhanced for distributed operation. Processors are
`separated by communication links, which themselves are shared and thus have
`to be scheduled as well. It is difficult to perform scheduling of these distributed
`resources. Some approaches have relied on heuristics for the cooperation of
`the distributed system nodes in finding a schedule (Ramamritham et aI., 1989).
`Holistic approaches to the problem have also been considered, where a global
`scheduling complying with system-wide constraints is constructed from the tim(cid:173)
`ing analysis of each module. This has been attempted namely in the embedded
`systems area, relying on simplifying assumptions on the communications in(cid:173)
`frastructure, and assuming a periodic behavior of the system (Tindell et aI.,
`1995; Kopetz et aI., 1989a). On the other hand, the best known examples of
`distributed scheduling are the local area network medium access control al(cid:173)
`gorithms, e.g., FDDI, Token Bus, Token Ring, CAN. Some of them exhibit
`real-time operation, such as the timed-token protocol used in the Token Bus
`and FDDI networks, or the priority scheduling based on the frame identifier of
`CAN.
`Scheduling in distributed systems is still a subject of research. However,
`systems are built every day, and apparently, two main approaches can be taken
`to scheduling in distributed systems with the current state-of-the-art:
`
`• constructing distributed systems whose hardware works in a lock-step fash(cid:173)
`ion, synchronized with the network subsystem also in lock-step (e.g., TDMA)
`or bit-synchronized (e.g., CAN), and scheduled in a globally periodic man(cid:173)
`ner (e.g., time-triggered cyclic schedules running over TDMA or CAN-like
`channels). These systems are normally small-scale hard real-time.
`• constructing distributed systems whose hardware choices are dictated by
`the availability of existing COTS (commercial off-the-shelf components),
`and whose scale and dynamics are dictated by the problem being solved.
`These systems have better be designed such that tighter (hard real-time)
`schedules are ensured inside each microscopic component (e.g., nodes, net(cid:173)
`work), and that
`the cooperative scheduling of the macroscopic system
`ensures the prosecution of the system's timeliness requirements with the
`best possible coverage. These systems are normally medium-scale mission(cid:173)
`critical real-time.
`
`12.8 CLOCK SYNCHRONIZATION
`
`Observe Figure 12.12a: in the center (dashed line), it depicts a perfect clock,
`one that always represents real time. However, it also depicts real hardware
`clocks that are not perfect, Le., they deviate from real time by a certain amount
`each second, called rate of drift. We studied the properties of global clocks made
`of local hardware clocks (see Time and Clocks in Chapter 2) and saw that if
`nothing is done, individual clocks will drift apart with the passing of time. The
`reader is referred to that section for all basic definitions concerning clocks.
`
`Exhibit 2026 Page 326
`
`

`

`310
`
`DISTRIBUTED SYSTEMS FOR SYSTEM ARCHITECTS
`
`Observe how clocks deviate from the perfect clock in Figure 12.12a: the out(cid:173)
`side thick dashed lines represent the bound on the rate of drift, a fundamental
`assumption for deterministic clock synchronization, since it allows us to predict
`the maximum deviation after a given interval. The amount of deviation be(cid:173)
`tween any clock and the perfect clock (which follows real time) at a given time,
`e.g. at tick tk, is given by drawing a horizontal straight line passing through
`tk in the clock time axis:
`the length of the line segment connecting the two
`clock timelines, measured in the real time axis, is the deviation. The current
`accuracy of the clock set is given by the maximum such deviation. As we see,
`this difference increases as time passes. If the desired accuracy of the clock set
`is a, no clock may drift to the outside of the grey band, of width a to either
`side of the perfect clock timeline, as depicted in Figure 12.12a. However, we
`see that the slowest clock (Cs ) will leave the band from tick tk on (point A),
`so it should have been re-synchronized before that.
`
`Crt)
`clock
`time
`
`i'
`
`I
`
`I
`
`Crt)
`clock
`time
`
`perfect
`c~pck
`.•....
`
`®
`
`real time t
`
`(a)
`
`real time t
`
`(b)
`
`Figure 12.12. Behavior of a Clock with Time: (a) Accuracy Drift; (b) Precision Drift
`
`Figure 12.12b represents the relative deviation among a set of clocks. The
`amount of relative deviation between the same tick tk at any two clocks is found
`by drawing a horizontal straight line passing through tk in the clock time axis:
`the length of the line segment connecting the clock timelines, measured in the
`real time axis, is the deviation. The current precision of the clock set is given
`by the deviation between the two outmost clocks. This difference increases
`as time passes as well. However, note that their absolute deviation from real
`time is irrelevant for determining precision:
`in the example, the set of clocks
`deviated considerably from the perfect clock, nevertheless they kept within
`the desired precision 1f until tick tk, where the slowest clock got out of the 1f
`envelope (point B), as depicted in Figure 12.12b. Obviously, they should have
`been re-synchronized before that.
`The process of maintaining the properties of Precision, Rate, Envelope Rate
`and Accuracy of a clock set is called clock (re)synchronization. Precision is se-
`
`Exhibit 2026 Page 327
`
`

`

`PARADIGMS FOR REAL-TIME
`
`311
`
`cured by internal synchronization, whereas external synchronization secures
`both accuracy and precision, since by securing accuracy, it guarantees that pre(cid:173)
`cision remains within 1r == 2a. Internal clock synchronization is normally based
`on convergence functions, whereby the several clocks attempt to converge to a
`same value at the end of the re-synchronization run. External synchronization
`is normally based on having all local clocks periodically read from and adjust
`to one or more clocks containing an absolute time reference. Figure 12.13 ex(cid:173)
`emplifies the latter: clocks are brought together and never deviate more than a
`from the perfect clock. With either internal or external clock synchronization,
`it often important to maintain the clock set within the envelope of drift from
`real time (the thick dashed lines in Figure 12.13). This has to do with securing
`the Envelope Rate property. The Rate property will be discussed ahead.
`
`Crt)
`clock
`time
`
`real time t
`
`at
`s
`
`Figure 12.13.
`
`Clock Synchronization
`
`Clock-Reading Error The precision achieved immediately after the syn(cid:173)
`chronization, which we have called Convergence, 6v , is a very important prop(cid:173)
`erty of clock synchronization algorithms, since the quality of an algorithm is
`measured, amongst other things, by how close it brings the clocks together.
`Unfortunately, 6v cannot be made arbitrarily small, and this was defined by a
`fundamental result in clock synchronization (Lundelius and Lynch, 1984b):
`Basic Clock Imprecision - Given n clock processors on a network with
`maximum and minimum message delivery delays T Dmax and T Dmin ,
`the convergence of any synchronization function is 6v 2: (TDmax (cid:173)
`lin)
`TDmin)(1 -
`The number of processors n is normally large enough that a good working
`bound for 6v is ~r == T Dmax - T Dmin . The intuition behind this result is that
`in order to synchronize their clocks, processes need to exchange messages. Un(cid:173)
`fortunately, the variance in message-passing delays introduces a remote clock(cid:173)
`reading error, that is, we never know whether the clock value we have just
`received concerns t now - T Dmax or t now - T Dmin .
`
`Exhibit 2026 Page 328
`
`

`

`312
`
`DISTRIBUTED SYSTEMS FOR SYSTEM ARCHITECTS
`
`A second order effect on the quality of synchronization that we neglected
`in the expressions above is that after reading and while the synchronization is
`in course, clocks continue to drift apart at a rate pp.
`If the synchronization
`algorithm duration is r s, then the additional error in precision caused by this
`phenomenon is 2ppr s (observed between by the fastest and slowest hardware
`clocks). This can normally be neglected. However, we advise the architect to
`always double check this term before deciding to do it.
`
`Reducing the Clock Reading Error We cannot contradict the Basic Clock
`Imprecision result, but we can create conditions for achieving a reduced vari(cid:173)
`ance in communication delays during the critical steps of the execution of the
`algorithm. In essence, trying to get to a ~r' == T.bmax - T.bmin « ~r, such
`that tJv ~ ~r' (instead of tJv ~ ~r). To ways of achieving this rely on: trying
`synchronization enough times until obtaining a run where the variance of the
`messages involved is small (Cristian, 1989; Mills, 1991); canceling the message
`delay terms that exhibit greater variance, either algorithmically (Halpern and
`Suzuki, 1991; Drummond and Babaoglu, 1993; Verissimo and Rodrigues, 1992),
`or through special hardware support (Kopetz and Ochsenreiter, 1987).
`
`12.8.1 Clock Synchronization in Action
`
`A clock synchronization algorithm has the following tasks:
`
`• generating a periodic resynchronization event
`• providing each correct process with a value to adjust the virtual clocks
`
`The time interval between successive synchronizations is called the resyn(cid:173)
`chronization interval, denoted Ts . At the end of synchronization, clocks are
`adjusted so that they become separated by at most tJv . For the sake of conve(cid:173)
`nience, the clock adjustment is usually modeled by the start of a new virtual
`clock upon each resynchronization event. It can be applied instantaneously, see
`the instant t s in Figure 12.13, where the clocks are brought suddenly nearer,
`and then start drifting again in the next interval. However, this neatly violates
`the Rate property. One clock is even brought backwards, which is unaccept(cid:173)
`able. So the alternative is to spread the adjustment over a time interval, by
`simulating a clock with a slightly different rate, as exemplified by the dotted
`timelines of the clocks after ts: the fast clocks become slower, the slow clocks
`become faster, so that they converge. This is called amortization and it is
`the way synchronization is usually applied:
`instead of changing the clock, a
`rate correction factor is applied in software when it is read. For a desired pre(cid:173)
`cision 7f, the value of the resynchronization interval Ts can be extracted from
`the expression 1r == 8v + 2ppT s . Adjusting clocks by changing their values is
`It can be combined with another method, rate
`called state synchronization.
`synchronization, which consists of adjusting the rate at which the hardware
`clock ticks, and even adjusting the instant (phase) of the ticks. These methods
`are employed when ultra accurate synchronization is desired.
`
`Exhibit 2026 Page 329
`
`

`

`PARADIGMS FOR REAL-TIME
`
`313
`
`Is clock synchronization a difficult task? The answer is yes, but. Design(cid:173)
`ing clock synchronization algorithms in the presence of communication delay
`variance and faults is a complex task. However, once deployed, the mission of
`the architect is selecting the adequate protocol, and simply using time services
`supported by those algorithms. However, she should understand the limitations
`of the use of time and timestamps that have been discussed earlier.
`
`12.8.2 Internal Synchronization
`
`Internal clock synchronization algorithms are normally cooperative, where each
`process reads the values of every other process, and applies a convergence func(cid:173)
`there is agreement on the
`tion to the set of remote readings. At the end,
`adjustment.
`In what follows, we will use 'clock' and 'processor' interchange(cid:173)
`ably. Known internal clock synchronization algorithms are of the agreement
`class, and fall essentially into one of three types:
`
`• averaging (AVG)
`• non-averaging (NAV)
`• hybrid averaging-non-averaging (ANA)
`
`A veraging Clock Synchronization The principle of averaging algorithms,
`of which there are many examples (Lamport and Melliar-Smith, 1985; Lundelius
`and Lynch, 1984a) is shown in Figure 12.14a. Clocks start a synchronization
`run when a number of them reach the end of the period, or resynchronization
`interval, before the current precision 1ri - 1 exceeds the allowed worst-case pre(cid:173)
`cision. Each clock disseminates its value to all others. The values received
`form a clock-readings vector, used as input to a convergence function, which
`computes the value to be applied to the new virtual clock launched in the next
`period. Assuming that clocks receive the same vector, the same value is applied
`at the end of this process to each clock, and the initial convergence or precision
`enhancement of the next period, measured by lSi in the figure, is dictated by
`the jitter with which this action is performed.
`
`Both forming the clock-readings vector and reaching agreement on the new
`clock value can be done in a local manner, or may involve a minimum number
`of interactions among a minimum number of clock processors. This depends on
`the fa