02-11-2012, 12:45 PM
Lamport’s Algorithm (1978)
Lamport’s.pdf (Size: 81.47 KB / Downloads: 23)
• each process maintains a request queue, ordered by timestamp value
• requesting the CS:
– when a process wants to enter the CS, it:
• sends a timestamped request to all processes (including self)
– when a process receives a request, it:
• adds the request to timestamp-ordered request queue
• returns a reply
• executing the CS:
– a process enters the CS when both:
1. its request is at the top of its request queue (its request is earliest)
2.
– variant 1 – it has received a reply with greater timestamp form every
process it the system
– variant 2 – it has received any message with greater timestamp
• Releasing the CS:
– when a process leaves the CS, it:
• sends a timestamped release message to all processes in the system
(including self
– when a process receives a release message, it:
• removes the (satisfied) request from its request queue
– note that that brings the next request to the head of the queue
• evaluation:
– message comlexity - 3(N–1)
• (N–1) release, (N–1) request, (N–1) reply
– synchronization delay - 1T
Maekawa’s Algorithm
Deadlock Avoidance
• To avoid deadlock process recalls permission if it is granted out of timestamp
order
– if Pj receives a request from Pi with higher timestamp than the request
granted permission, Pj sends failed to Pi
– If Pj receives a request from Pi with lower timestamp than the request
granted permission (deadlock possibility), Pj sends inquire to Pi
– when Pi receives inquire it replies with yield if it did not succeed getting
permissions from other processes
• got failed