Distributed Operating Systems Synchronization PDF

Distributed Operating Systems Synchronization Chapter 11 1  Clock Synchronization Synchronization based on “Actual Time”. Note: time is really easy on a uniprocessor system. Achieving agreement on time in a DS is not t...

Distributed Operating Systems Synchronization Chapter 11 1  Clock Synchronization Synchronization based on “Actual Time”. Note: time is really easy on a uniprocessor system. Achieving agreement on time in a DS is not trivial. Question: is it even possible to synchronize all the clocks in a Distributed System? With multiple computers, “clock skew” ensures that no two machines have the same value for the “current time”. But, how do we measure time? 2  Clock Synchronization In a centralized system, time is ambiguous – Even though it might not be accurate, but two consecutive time call will be ordered relatively correct – Many examples are present in which accurate timing is required (bank system) Synchronization: – Absolute (with real time) Necessary for real-time applications such as on-line reservation systems – Relative (with each other) Required for those applications that need a consistent view of time across all nodes. Is it possible to synchronize all clocks is a DS? – Physical clocks – Logical clocks – Vector clocks 3  How Do We Measure Time? Turns out that we have only been measuring time accurately with a “global” atomic clock Algorithms based on the current time (from some Physical Clock) have been devised for use within a DS. 4  Physical Clocks (2) TAI seconds are of constant length, unlike solar seconds. Leap seconds are introduced when 5 necessary to keep in phase with the sun  Clock Synchronization Cristian's Algorithm ( passive ) Getting the current time from a “time server”, using periodic client requests. Client time = server time + ( t1-t0) /2 6  The Berkeley Algorithm (active) (a) The time daemon asks all the other machines 7 for their clock values  Other Clock Sync. Algorithms Both Cristian’s and the Berkeley Algorithm are centralized algorithms. Decentralized algorithms also exist, and the Internet’s Network Time Protocol (NTP) is the best known and most widely implemented. NTP can synchronize clocks to within a 1-50 msec accuracy. 8  Network Time Protocol A’s offset relative to B = θ = T3-T4 +[(T2-T1)+(T4-T3)]/2 =[(T2-T1)+(T3-T4)]/2 Θ0 A time is slower than B time Θ=0 A time is equal to B time 9  Logical Clocks Synchronization based on “relative time”. Note that (with this mechanism) there is no requirement for “relative time” to have any relation to the “real time”. What’s important is that the processes in the Distributed System agree on the ordering in which certain events occur. Such “clocks” are referred to as Logical Clocks. 10  Lamport’s Logical Clocks (1) The "happens-before" relation → can be observed directly in two situations: 1. If a and b are events in the same process, and a occurs before b, then a → b is true. 2. If a is the event of a message being sent by one process, and b is the event of the message being received by another process, then a → b. 11  Lamport’s Logical Clocks (2) (a) Three processes, each with its own clock. 12 The clocks run at different rates.  Lamport’s Logical Clocks (3) 13 (b) Lamport’s algorithm corrects the clocks  Problem: Totally-Ordered Multicasting Updating a replicated database and leaving it in an inconsistent state: Update 1 adds 100 euro to an account, Update 2 calculates and adds 1% interest to the same account. Due to network delays, the updates may not happen in the correct 14 order. Whoops!  Vector Clocks (1) 15 Concurrent message transmission using logical clocks