Synchronization Chapter 5. Clock Synchronization When each machine has its own clock, an event that occurred after another event may nevertheless be assigned. - презентация

1 Synchronization Chapter 5

2 Clock Synchronization When each machine has its own clock, an event that occurred after another event may nevertheless be assigned an earlier time.

3 Physical Clocks (1) Computation of the mean solar day.

4 Physical Clocks (2) TAI seconds are of constant length, unlike solar seconds. Leap seconds are introduced when necessary to keep in phase with the sun.

5 Clock Synchronization Algorithms The relation between clock time and UTC when clocks tick at different rates.

6 Cristian's Algorithm Getting the current time from a time server.

7 The Berkeley Algorithm a)The time daemon asks all the other machines for their clock values b)The machines answer c)The time daemon tells everyone how to adjust their clock

8 Lamport Timestamps a)Three processes, each with its own clock. The clocks run at different rates. b)Lamport's algorithm corrects the clocks.

9 Example: Totally-Ordered Multicasting Updating a replicated database and leaving it in an inconsistent state.

10 Global State (1) a)A consistent cut b)An inconsistent cut

11 Global State (2) a)Organization of a process and channels for a distributed snapshot

12 Global State (3) b)Process Q receives a marker for the first time and records its local state c)Q records all incoming message d)Q receives a marker for its incoming channel and finishes recording the state of the incoming channel

13 The Bully Algorithm (1) The bully election algorithm Process 4 holds an election Process 5 and 6 respond, telling 4 to stop Now 5 and 6 each hold an election

14 Global State (3) d)Process 6 tells 5 to stop e)Process 6 wins and tells everyone

15 A Ring Algorithm Election algorithm using a ring.

16 Mutual Exclusion: A Centralized Algorithm a)Process 1 asks the coordinator for permission to enter a critical region. Permission is granted b)Process 2 then asks permission to enter the same critical region. The coordinator does not reply. c)When process 1 exits the critical region, it tells the coordinator, when then replies to 2

17 A Distributed Algorithm a)Two processes want to enter the same critical region at the same moment. b)Process 0 has the lowest timestamp, so it wins. c)When process 0 is done, it sends an OK also, so 2 can now enter the critical region.

18 A Toke Ring Algorithm a)An unordered group of processes on a network. b)A logical ring constructed in software.

19 Comparison A comparison of three mutual exclusion algorithms. Algorithm Messages per entry/exit Delay before entry (in message times) Problems Centralized32Coordinator crash Distributed2 ( n – 1 ) Crash of any process Token ring 1 to 0 to n – 1 Lost token, process crash

20 The Transaction Model (1) Updating a master tape is fault tolerant.

21 The Transaction Model (2) Examples of primitives for transactions. PrimitiveDescription BEGIN_TRANSACTIONMake the start of a transaction END_TRANSACTIONTerminate the transaction and try to commit ABORT_TRANSACTIONKill the transaction and restore the old values READRead data from a file, a table, or otherwise WRITEWrite data to a file, a table, or otherwise

22 The Transaction Model (3) a)Transaction to reserve three flights commits b)Transaction aborts when third flight is unavailable BEGIN_TRANSACTION reserve WP -> JFK; reserve JFK -> Nairobi; reserve Nairobi -> Malindi; END_TRANSACTION (a) BEGIN_TRANSACTION reserve WP -> JFK; reserve JFK -> Nairobi; reserve Nairobi -> Malindi full => ABORT_TRANSACTION (b)

23 Distributed Transactions a)A nested transaction b)A distributed transaction

24 Private Workspace a)The file index and disk blocks for a three-block file b)The situation after a transaction has modified block 0 and appended block 3 c)After committing

25 Writeahead Log a) A transaction b) – d) The log before each statement is executed x = 0; y = 0; BEGIN_TRANSACTION; x = x + 1; y = y + 2 x = y * y; END_TRANSACTION; (a) Log [x = 0 / 1] (b) Log [x = 0 / 1] [y = 0/2] (c) Log [x = 0 / 1] [y = 0/2] [x = 1/4] (d)

26 Concurrency Control (1) General organization of managers for handling transactions.

27 Concurrency Control (2) General organization of managers for handling distributed transactions.

28 Serializability a) – c) Three transactions T 1, T 2, and T 3 d) Possible schedules BEGIN_TRANSACTION x = 0; x = x + 1; END_TRANSACTION (a) BEGIN_TRANSACTION x = 0; x = x + 2; END_TRANSACTION (b) BEGIN_TRANSACTION x = 0; x = x + 3; END_TRANSACTION (c) Schedule 1x = 0; x = x + 1; x = 0; x = x + 2; x = 0; x = x + 3Legal Schedule 2x = 0; x = 0; x = x + 1; x = x + 2; x = 0; x = x + 3;Legal Schedule 3x = 0; x = 0; x = x + 1; x = 0; x = x + 2; x = x + 3;Illegal (d)

29 Two-Phase Locking (1) Two-phase locking.

30 Two-Phase Locking (2) Strict two-phase locking.

31 Pessimistic Timestamp Ordering Concurrency control using timestamps.