Pitt CS 2510 - Clock Synchronization (9 pages)

Previewing pages 1, 2, 3 of 9 page document
View Full Document

Clock Synchronization

Previewing pages 1, 2, 3 of actual document.

View Full Document
View Full Document

Clock Synchronization

28 views

Other

Pages:
9
School:
University of Pittsburgh
Course:
Cs 2510 - Computer Operating Systems
Computer Operating Systems Documents
• 12 pages

• 31 pages

• 14 pages

• 26 pages

• 16 pages

Unformatted text preview:

Clock Synchronization Physical clocks Logical clocks Vector clocks Physical Clocks Problem Suppose we have a distributed system with a UTCreceiver somewhere in it we still have to distribute its time to each machine UTC is Universal Coordinated Time based on some atomic element Cs Basic principle Every machine has a timer that generates an interrupt H times per second There is a clock in machine p that ticks on each timer interrupt Denote the value of that clock by Cp t where t is UTC time Ideally we have that for each machine p Cp t t or in other words dC dt 1 1 Clock Synchronization Algorithms In practice 1 dC dt 1 for some small constant drift Goal Never let two clocks in any system differ by more than time units synchronize at least every 2 seconds Clock Synchronization Idea 1 Every machine asks a time server for the accurate time at least once every d 2r seconds Good solution but need an accurate measure of round trip delay including interrupt handling and processing incoming messages Idea 2 Let the time server scan all machines periodically calculate an average and inform each machine how it should adjust its time relative to its present time Another good solution you ll probably get every machine in sync Fundamental problem You ll have to take into account that setting the time back is never allowed smooth adjustments Note you don t even need to propagate UTC time Why not 2 The Berkeley Algorithm a b c The time daemon asks all the other machines for their clock values The machines answer The time daemon tells everyone how to adjust their clock The Happened Before Relationship Problem We first need to introduce a notion of ordering before we can order anything The happened before relation on the set of events in a distributed system is the smallest relation satisfying If a and b are two events in the same process and a comes before b then a b If a is the sending of a message and b is the receipt of that message then a b If a b and b c then a c Is this a

View Full Document

Unlocking...