variables shared between a user process and its agent
state, either wants-in or idle
user-sem and agent-sem, local semaphores, initially 0
token values are timeout, normal or [station-ID]
agent
repeat
| repeat
| await token (m) or timeout after time t
| if m = timeout
| forward token( [my-ID] ) -- initiate election
| else if m = [station-ID]
| if my-ID < station-ID
| forward token( [station-ID] ) -- vote
| else if my-ID > station-ID
| forward token( [my-ID] ) -- vote
| else if my-ID = station-ID
| m = normal -- win!
| endif
| endif
| until m = normal
| forward token(normal)
if state = wants-in
signal user-sem
wait agent-sem
endif
forever
enter-cs
state = wants-in
wait user-sem
await token
exit-cs
state = idle
signal agent-sem
forward token
Part B: The UNIX service that provides the equivalent of "await token(m) or timeout after time n" is called select().
stations on ring = N
token format:
[time[1],time[2], ... time[N]]
algorithm at station i:
repeat
await token(m)
p = t
t = current local time
send token([time[2], ... time[N],t])
-- estimate station-to-station hop-time
h = (t - p) / N
-- estimate current time at each station
for i = 2 to N do
time[i] = time[i] + (((N + 1) - i) * h)
endloop
-- take average of all clocks
sum = t
for i = 2 to N do
sum = sum + time[i]
endloop
a = sum / N
-- compute local error
e = a - t
-- correct the local clock
if e > 0
set local time forward e ticks
else if e < 0
set local time back e ticks
endif
forever