CS 417 9/24/2014 Paul Krzyzanowski 1 Distributed Systems 05. Clock Synchronization Paul Krzyzanowski Rutgers University Fall 2014 1 September 24, 2014 © 2014 Paul Krzyzanowski What’s it for? • Temporal ordering of events produced by concurrent processes • Synchronization between senders and receivers of messages • Coordination of joint activity • Serialization of concurrent access for shared objects 2 September 24, 2014 © 2014 Paul Krzyzanowski Physical clocks September 24, 2014 © 2014 Paul Krzyzanowski 3 Logical vs. physical clocks • Logical clock keeps track of event ordering – among related (causal) events • Physical clocks keep time of day – Consistent across systems 4 September 24, 2014 © 2014 Paul Krzyzanowski Quartz clocks • 1880: Piezoelectric effect – Curie brothers – Squeeze a quartz crystal & it generates an electric field – Apply an electric field and it bends • 1929: Quartz crystal clock – Resonator shaped like tuning fork – Laser-trimmed to vibrate at 32,768 Hz – Standard resonators accurate to 6 parts per million at 31° C – Watch will gain/lose < ½ sec/day – Stability > accuracy: stable to 2 sec/month – Good resonator can have accuracy of 1 second in 10 years • But … frequency changes with age, temperature, and acceleration 5 September 24, 2014 © 2014 Paul Krzyzanowski Atomic clocks • Second is defined as 9,192,631,770 periods of radiation corresponding to the transition between two hyperfine levels of cesium-133 • Accuracy: better than 1 second in six million years • NIST standard since 1960 6 September 24, 2014 © 2014 Paul KrzyzanowskiCS 417 9/24/2014 Paul Krzyzanowski 2 UTC • UT0 – Mean solar time on Greenwich meridian – Obtained from astronomical observation • UT1 – UT0 corrected for polar motion • UT2 – UT1 corrected for seasonal variations in Earth’s rotation • TAI: International Atomic Time (Temps Atomique International) – Weighted average of ~200 atomic clocks: TAI-UT1 = 0 on Jan 1, 1958 • UTC: Coordinated Universal Time (Temps Universel Coordonné) – Civil time measured on an atomic time scale – Kept within 0.9 seconds of UT1; integral Δ from TAI – Atomic clocks cannot keep mean time (UT0) • Mean time is a measure of Earth’s rotation September 24, 2014 © 2014 Paul Krzyzanowski 7 Physical clocks in computers • Real-time Clock: CMOS clock (counter) circuit driven by a quartz oscillator – Battery backup to continue measuring time when power is off • OS generally programs a timer circuit to generate a periodic interrupt – Timer hardware • Programmable Interval Timer (PIT) – Intel 8253, 8254 • High Precision Event Timer (HPET) • Advanced Programmable Interval Controller (APIC) – E.g., 60, 100, 250, 1000 interrupts per second (Linux 2.6+ adjustable up to 1000 Hz) – Interrupt service procedure increments a counter in memory 8 September 24, 2014 © 2014 Paul Krzyzanowski Problem • Getting two systems to agree on time – Two clocks hardly ever agree – Quartz oscillators oscillate at slightly different frequencies • Clocks tick at different rates – Create ever-widening gap in perceived time – Clock Drift • Difference between two clocks at one point in time – Clock Skew 9 September 24, 2014 © 2014 Paul Krzyzanowski Sept 18 8:00:00 8:00:00 8:00:00 10 September 24, 2014 © 2014 Paul Krzyzanowski Oct 23 8:00:00 8:01:24 8:01:48 Skew = +84 seconds +84 seconds/35 days Drift = +2.4 sec/day Skew = +108 seconds +108 seconds/35 days Drift = +3.1 sec/day 11 September 24, 2014 © 2014 Paul Krzyzanowski Perfect clock UTC time, t Computer’s time, C 12 September 24, 2014 © 2014 Paul Krzyzanowski dCdt=1CS 417 9/24/2014 Paul Krzyzanowski 3 Drift with slow clock UTC time, t Computer’s time, C skew 13 September 24, 2014 © 2014 Paul Krzyzanowski dCdt<1Drift with fast clock UTC time, t Computer’s time, C skew 14 September 24, 2014 © 2014 Paul Krzyzanowski dCdt>1Dealing with drift We want to set the computer to the time of day Not good idea to set a clock back – Illusion of time moving backwards can confuse message ordering and software development environments 15 September 24, 2014 © 2014 Paul Krzyzanowski Dealing with drift Go for gradual clock correction If fast: Make the clock run slower until it synchronizes If slow: Make the clock run faster until it synchronizes 16 September 24, 2014 © 2014 Paul Krzyzanowski Dealing with drift The OS can do this: Change the rate at which it requests interrupts e.g.: if system requests interrupts every 17 ms but clock is too slow: request interrupts at (e.g.) 15 ms Not always practical: we may not have enough precision Easier (software-only) solution → adjust the rate at which the system time is advanced Adjustment changes slope of system time: Linear compensation function 17 September 24, 2014 © 2014 Paul Krzyzanowski Compensating for a fast clock UTC time, t Computer’s time, C Linear compensation function applied Clock synchronized skew 18 September 24, 2014 © 2014 Paul KrzyzanowskiCS 417 9/24/2014 Paul Krzyzanowski 4 Compensating for a fast clock UTC time, t Computer’s time, C Now we’re drifting again! 19 September 24, 2014 © 2014 Paul Krzyzanowski Resynchronizing After synchronization period is reached – Resynchronize periodically – Successive application of a second linear compensating function can bring us closer to true slope – Long-term stability is not guaranteed – the system clock can still drift based on changes in temperature, pressure, humidity, and age of the crystal Keep track of adjustments and apply continuously – e.g., POSIX adjtime system call and hwclock command 20 September 24, 2014 © 2014 Paul Krzyzanowski Going to sleep • RTC keeps on ticking when the system is off (or sleeping) • OS cannot apply correction continually • Estimate drift on wake-up and apply a correction factor 21 September 24, 2014 © 2014 Paul Krzyzanowski Getting accurate time • Attach GPS receiver to each computer – ± 100 ns to 1 μsec of UTC • Attach WWV radio receiver – Obtain time broadcasts from Boulder or DC – ± 3 ms of UTC (depending on distance) • Not practical solution for every machine – Cost, power, convenience, environment 22 September 24, 2014 © 2014 Paul Krzyzanowski Getting accurate time Synchronize from another machine – One with a more accurate