Understanding Lamport Algorithm for Mutual Exclusion
Lamport Algorithm, presented by Prafulla Santosh Patil, is a permission-based algorithm utilizing timestamps to order critical section requests and resolve conflicts. It employs three types of messages: REQUEST, REPLY, and RELEASE, where each site manages a queue to store requests. By ensuring communication in FIFO order, Lamport Algorithm achieves mutual exclusion. The process involves requesting, accessing, and releasing the critical section in a coordinated manner to maintain order and prevent conflicts.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
LAMPORT ALGORITHM LAMPORT ALGORITHM Presented By : Prafulla Santosh Patil 203050070 CS 766 Analysis of Concurrent Programs Instructor Prof. Ashutosh Gupta IIT Bombay Date : 9thFeb , 2021
LAMPORT ALGORITHM LAMPORT ALGORITHM Permission based algorithm (and it is non token based algorithm). Timestamp is used to order critical section requests and to resolve conflict between requests(Using Lamport Clock algorithm). Three Types of messages : 1. REQUEST 2. REPLY 3. RELEASE Every site (process) keeps a queue (RQ) to store critical section requests along with timestamp. This algorithm requires communication channels to deliver messages the FIFO order.
LAMPORT ALGORITHM LAMPORT ALGORITHM RQ1={TS:1,P3} RQ1={} S1 Reply Release Request RQ2={TS:1,P3} RQ2={} S2 Request Reply Release S3 CR RQ3={} RQ3={TS:1,P3} Accessing Critical Region
Accessing Critical Section Accessing Critical Section RQ1={TS:2,P1} RQ1={TS:2,P1} RQ1={TS:1,P3; TS:2,P1} RQ1={} S1 CS RQ2={TS:1,P3; TS:2,P1} RQ2={TS:2,P1} RQ2={TS:1,P3} S2 RQ2={} S3 CS RQ3={} RQ3={TS:1,P3; TS:2,P1} RQ3={TS:2,P1} RQ3={TS:1,P3}
LAMPORT ALGORITHM LAMPORT ALGORITHM Requesting the critical section When a site Si wants to enter the CS, it broadcasts a REQUEST(tsi , i) message to all other sites and places the request on RQi(tsi , i). When a site Sj receives the REQUEST(tsi , i) message from site Si ,places site Si request on RQj and it returns a timestamped REPLY message to Si . Executing the critical section Site Si enters the CS when the following two conditions hold: L1: Si has received a message with timestamp larger than (tsi , i) from all other sites. L2: Si s request is at the top of request RQi .
LAMPORT ALGORITHM LAMPORT ALGORITHM Releasing the critical section: Site Si, upon exiting the CS, removes its request from the top of its RQi and broadcasts a timestamped RELEASE message to all other sites. When a site Sj receives a RELEASE message from site Si , it removes Si s request from its RQj.
correctness arguments correctness arguments Lamport s algorithm achieves mutual exclusion: Proof is by contradiction. Two sites Si and Sj are executing the CS concurrently. For this to happen conditions L1 and L2 must hold at both the sites concurrently. At some instant in time, both Si and Sj have their own requests at the top of their RQs and condition L1 holds at them. (Si s has smaller timestamp than Sj) From condition L1 and FIFO property of the communication channels, it is clear that at instant t the request of Si must be present in RQj when Sj was executing its CS. This implies that Sj s own request is at the top of its own RQ when a smaller timestamp request, Si s request, is present in the RQi a contradiction! SOURCE : https://www.cs.uic.edu/~ajayk/Chapter9.pdf
Safety Safety RQj={TS:2,j; TS:1,i} RQi={TS:1,i; TS:2,j} Sj Si CS Sj Sj in CS but Si have lower TS CONTRADICTION!!!! TSi < TSj L1: Si has received a message with timestamp larger than (tsi , i) from all other sites L2: Si s request is at the top of request RQi
correctness arguments Liveness: if process made a request to access the critical section should eventually get chance to access the critical section. Fairness: Critical Section request are executed in order they generated.
correctness arguments Liveliness and Fairness : Suppose a site Si s request has a smaller timestamp than the request of another site Sj and Sj is able to execute the CS before Si . For Sj to execute the CS, it has to satisfy the conditions L1 and L2. This implies that, Sj has its own request at the top of its queue and it has also received a message with timestamp larger than the timestamp of its request from all other sites. But request queue at a site is ordered by timestamp, and according to our assumption Si has lower timestamp. So Si s request must be placed ahead of the Sj s request in the request RQj . This is a contradiction! SOURCE : https://www.cs.uic.edu/~ajayk/Chapter9.pdf
Liveness and Fairness Liveness and Fairness RQj={} RQi={} RQj={TS:2,j} RQi={TS:2,j} RQj={TS:2,j; TS:1,i} Sj RQi={TS:1,i; TS:2,j} Si CS Si Sj TSi < TSj L1: Si has received a message with timestamp larger than (tsi , i) from all other sites L2: Si s request is at the top of request RQi
cost of the protocol cost of the protocol For each CS execution, Lamport s algorithm requires (N 1) REQUEST messages, (N 1) REPLY messages, and (N 1) RELEASE messages. Thus, Lamport s algorithm requires 3(N 1) messages per CS invocation. Algorithm can be optimized to 2(N 1) messages by omitting the REPLY message.
Drawbacks of Lamports aLgorithm Drawbacks of Lamport s aLgorithm Unreliable approach: failure of any one of the processes will halt the progress of entire system. High message complexity: Algorithm requires 3(N-1) messages per critical section invocation.
REFERENCES REFERENCES https://www.cs.uic.edu/~ajayk/Chapter9.pdf https://www.geeksforgeeks.org/lamports-algorithm-for-mutual- exclusion-in-distributed-system https://www.cs.fsu.edu/~xyuan/cop5611/lecture8.html
THANK YOU !!!!! THANK YOU !!!!!
