Transcript ppt

CS533 Concepts of Operating Systems
Class 8
Time, Clocks, and the Ordering of
Events in a Distributed System
By Constantia Tryman
What will be covered




Concept of events ordering in distributed
system
Synchronization of logical clocks to order events
totally
Specialized synchronization using physical clocks
Bound on how far synchrony clocks can drift
apart
CS533 - Concepts of Operating Systems
2
Partial Ordering


 : “happened before”
Definition:
o
o
o

If a and b are events from Pi, a comes before b
then a  b
(same process)
If a is sending message m by Pi and b is receiving m by Pj
then a  b
(b/t 2 processes)
If a  b and b c, then a  c (1 or more processes)
“space-time” diagram
o
o
o
Horizontal: space
Vertical: time
Wavy lines: message
CS533 - Concepts of Operating Systems
3
Space-time Diagram
CS533 - Concepts of Operating Systems
4
Logical Clocks




Clock: a way of assigning number to an event
Logical Clock: order in which events occur
Ci<a> : define clock Ci to process Pi for event a
System of clock represented by:
C<b> = Cj<b>
CS533 - Concepts of Operating Systems
5
Space-Time diagram
CS533 - Concepts of Operating Systems
6
Clock Condition



Clock Condition (CC):
For events a,b:
if a  b then C<a>  C<b>
Converse condition will not hold => concurrent events
happen at the same time
CC is satisfied by:
o
o
C1: if a & b are events by Pi, a comes before b,
then Ci<a>  Ci<b>
C2: if a sends message m by Pi, b is a receipt of m by Pj,
then Ci<a>  Cj<b>
CS533 - Concepts of Operating Systems
7
Implementation Rule



To guarantee that system of clocks satisfies CC
IR1: Each process Pi increments Ci between any two
successive events
(tick is occurring between P’s events)
IR2: (each message contains Tm = time msg sent)
o
o

A. if a is sending message m by Pi
then m contains timestamp Tm = Ci<a>
B. upon receiving m, Pj sets Cj  its present value and  Tm
IR1 and 2 imply that CC is satisfied
CS533 - Concepts of Operating Systems
8
Ordering Events Totally


Define  :
If event a in Pi and b in Pj
then a  b if either
•
•


Ci<a>  Cj<b> or
Ci<a> = Cj<b> and Pi < Pj
a  b means Ci<a>  Cj<b>
 extends 
CS533 - Concepts of Operating Systems
9
Total Ordering of Events
Algorithm for solving mutex problem:

I.
II.
III.

Process which granted the resource must release before
granting resource to another Process
Different requirements for resource must be granted in
order they’re made
Every Process granted with resource will eventually
release it so every request is eventually granted
Issue: doesn’t tell which Process granted if
request resource concurrently with another
Process
CS533 - Concepts of Operating Systems
10
Scheduling Issue


Cannot be solved by Central Scheduling Process
Ex: P1 requests P0, P1 sends message P2,
P2 requests P0
If P2 is granted first, violate II
(granted in the order they make)
CS533 - Concepts of Operating Systems
11
Algorithm Rules
1)
Resource Request by Pi
o
o
2)
When Message Received by Pj
o
o
3)
Pi sends message, M: “Tm: Pi request resource” to every
Processes
Pi puts message M to its request Queue
Pj places M on request Queue
Sends acknowledgement message to Pi
Releasing Resource
o
o
Pi removes any M from request Queue
Pi sends message, M3: “Tm3: Pi releases resource” to every
Processes
CS533 - Concepts of Operating Systems
12
Algorithm Rules Cont.
4)
When Pj received Pi release resource
o
5)
Removes any M: “Tm: Pi requests resource” from request
Queue
Pi is granted the resource
i.
ii.
 M in request Queue ordered before any other requests
defined by 
Pi has received M2 from every other process time stamped
Tm2 (where Tm2  Tm)
CS533 - Concepts of Operating Systems
13
Anomalous Behavior


Resource scheduling algorithm ordered request by 
total ordering will result in Anomalous Behavior
Strong Clock Condition:
 event a,b in :
if a  b then C<a>  C<b>


: events in all systems
 uses physical clocks to eliminate anomalous behavior
CS533 - Concepts of Operating Systems
14
Physical Clocks




Ci(t): reading of clock Ci at physical time t
dCi(t)/dt = rate of clock is running  1
PC1:  a constant K << 1 such that
i: | dCi(t)/dt - 1| < k, where k  10-6
PC2: i,j: |Ci(t) – Cj(t)| < 
CS533 - Concepts of Operating Systems
15
Physical Clocks Cont.

a  b Cj<a> = t, Cj<b> = t + 

  shortest transmission time for interprocess messages



i,j,t Cj (t+ ) – Ci (t) > 0
By PC1
Ci (t+ ) – Ci (t) > (1 - k) 
By PC2
Ci (t+ ) – Cj (t) > 0
if  / (1-k)  
CS533 - Concepts of Operating Systems
16
Implementation Rules


IR1’: i if Pi doesn’t receive a message at physical time t
then Ci is differentiable at t and dCi(t)/dt  0
IR2’
a.
b.
If Pi sends message M at physical time t,
then M contains Tm = Ci(t)
Upon receiving M at time t’
Pj sets Cj(t’) = max ( Cj(t’ – 0), Tm +
m )
CS533 - Concepts of Operating Systems
17
Theorem
Theorem: Assume strongly connected graph of
Processes with diameter d obeying IR1’ and IR2’
Assume m,  m  
for constant 
and t  t0
a)
PC1 holds
b)
 constant  and  such that every  seconds a
message sent over every arch (m  )
PC2 is satisfied by:
  d (2k  + )
t ≳ t0 + d
Assumption:  +  ≪ 
CS533 - Concepts of Operating Systems
18