Rutgers University CS 417 - Clock Synchronization - Physical Clocks (52 pages)

Previewing pages 1, 2, 3, 25, 26, 27, 28, 50, 51, 52 of 52 page document View the full content.
View Full Document

Clock Synchronization - Physical Clocks



Previewing pages 1, 2, 3, 25, 26, 27, 28, 50, 51, 52 of actual document.

View the full content.
View Full Document
View Full Document

Clock Synchronization - Physical Clocks

74 views


Pages:
52
School:
Rutgers University- The State University of New Jersey
Course:
Cs 417 - Distributed Systems
Unformatted text preview:

Distributed Systems Clock Synchronization Physical Clocks Paul Krzyzanowski pxk cs rutgers edu Except as otherwise noted the content of this presentation is licensed under the Creative Commons Attribution 2 5 License Page 1 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 Page 2 Physical clocks Page 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 Page 4 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 Frequency changes with age temperature and acceleration Page 5 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 Page 6 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 UTC Civil time measured on an atomic time scale Page 7 UTC Coordinated Universal Time Temps Universel Coordonn Kept within 0 9 seconds of UT1 Atomic clocks cannot keep mean time Mean time is a measure of Earth s rotation Page 8 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 an interrupt periodically e g 60 100 250 1000 interrupts per second Linux 2 6 adjustable up to 1000 Hz Programmable Interval Timer PIT Intel 8253 8254 Interrupt service procedure adds 1 to a counter in memory Page 9 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 Page 10 8 00 00 8 00 00 Sept 18 2006 8 00 00 Page 11 8 01 24 Skew 84 seconds 84 seconds 35 days Drift 2 4 sec day 8 01 48 Oct 23 2006 8 00 00 Skew 108 seconds 108 seconds 35 days Drift 3 1 sec day Page 12 Computer s time C Perfect clock UTC time t Page 13 Computer s time C Drift with slow clock skew UTC time t Page 14 Computer s time C Drift with fast clock skew UTC time t Page 15 Dealing with drift Assume we set computer to true time Not good idea to set clock back Illusion of time moving backwards can confuse message ordering and software development environments Page 16 Dealing with drift Go for gradual clock correction If fast Make clock run slower until it synchronizes If slow Make clock run faster until it synchronizes Page 17 Dealing with drift OS can do this Change rate at which it requests interrupts e g if system requests interrupts every 17 msec but clock is too slow request interrupts at e g 15 msec Or software correction redefine the interval Adjustment changes slope of system time Linear compensating function Page 18 Computer s time C Compensating for a fast clock Clock synchronized skew Linear compensating function applied UTC time t Page 19 Computer s time C Compensating for a fast clock UTC time t Page 20 Resynchronizing After synchronization period is reached Resynchronize periodically Successive application of a second linear compensating function can bring us closer to true slope Keep track of adjustments and apply continuously e g UNIX adjtime system call Page 21 Getting accurate time Attach GPS receiver to each computer 1 msec of UTC Attach WWV radio receiver Obtain time broadcasts from Boulder or DC 3 msec of UTC depending on distance Attach GOES receiver 0 1 msec of UTC Not practical solution for every machine Cost size convenience environment Page 22 Getting accurate time Synchronize from another machine One with a more accurate clock Machine service that provides time information Time server Page 23 RPC Simplest synchronization technique Issue RPC to obtain time Set time client what s the time server 3 42 19 Does not account for network or processing latency Page 24 Cristian s algorithm Compensate for delays Note times request sent T0 reply received T1 Assume network delays are symmetric Tserver server request client T0 reply T1 time Page 25 Cristian s algorithm Client sets time to server request client T0 Tserver reply T1 time estimated overhead in each direction Page 26 Error bounds If minimum message transit time Tmin is known Place bounds on accuracy of result Page 27 Error bounds Tserver server request client T0 Tmin Earliest time message arrives reply Tmin T1 time Latest time message leaves range T1 T0 2Tmin accuracy of result Page 28 Cristian s algorithm example Send request at 5 08 15 100 T0 Receive response at 5 08 15 900 T1 Response contains 5 09 25 300 Tserver Elapsed time is T1 T0 5 08 15 900 5 08 15 100 800 msec Best guess timestamp was generated 400 msec ago Set time to Tserver elapsed time 5 09 25 300 400 5 09 25 700 Page 29 Cristian s algorithm example If best case message time 200 msec Tserver server request client T0 5 08 15 100 T1 5 08 15 900 Ts 5 09 25 300 Tmin 200msec T0 reply 200 200 T1 time 800 Error Page 30 Berkeley Algorithm Gusella Zatti 1989 Assumes no machine has an accurate time source Obtains average from participating computers Synchronizes all clocks to average Page 31 Berkeley Algorithm Machines run time d mon Process that implements protocol One machine is elected or designated as the server master Others are slaves Page 32 Berkeley Algorithm Master polls each machine periodically Ask each machine for time Can use Cristian s algorithm to compensate for network latency When results are in compute average Including master s time Hope average cancels out individual clock s tendencies to run fast or slow Send offset by which each clock needs adjustment to each slave Avoids problems with network delays if we send a time stamp Page 33 Berkeley Algorithm Algorithm has provisions for


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Clock Synchronization - Physical Clocks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Clock Synchronization - Physical Clocks and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?