Analysis of Burns Algorithm for Concurrent Program Correctness

The Burns Algorithm is evaluated for correctness in concurrent programs, focusing on mutual exclusion, progress, deadlock limitation, lockout freedom, and bounded waiting. The algorithm involves multiple loops to ensure proper execution order and flag management. The double-checking for smaller indices is explained to prevent race conditions and ensure mutual exclusion. Additionally, the algorithm's correctness is examined by considering scenarios involving process interactions within critical sections, demonstrating the guaranteed mutual exclusion property.

• Burns Algorithm
• Concurrent Programs
• Mutual Exclusion
• Deadlock
• Correctness

memm Follow

Uploaded on Feb 23, 2025 | 0 Views

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.

Presentation Transcript

1. Burns' algorithm Shubham Raju Chaudhari 203050093 Presented By: CS 766 Analysis of Concurrent Programs Instructor Prof. Ashutosh Gupta

2. Plan:- Burns Algorithm Correctness of algorithm (Mutual Exclusion) Progress Deadlock Limitation No Lockout freedom Bounded waiting

3. Algorithm:- Each process goes through 3 loops, sequentially: 1. Check flags of processes with smaller indices. Process L: flag(i) := 0 for j in {1,..,i-1} do if flag(j) = 1 then go to L flag(i) := 1 for j in {1, ,i-1} do if flag(j) = 1 then go to L M: for j {i+1, ,n} do if flag(j) = 1 then go to M Crit(i) Exit(i) Flag(i)=0 2. Check flags of processes with smaller indices. 3. Check flags of processes with larger indices. If it passes all tests C. L Otherwise, drops back: M

4. Algorithm:- Why double Checking for Smaller indices??? Process P1 and P2 are two process want critical region, take following scenario 1.Suppose P2 wants to enter first so it will check 1st for loop. 2.After 1st for loop executed p2 will now set its flag value=1. But before setting it got prompted. 3. Now p1 comes in picture , and execute first for loop successfully and it will direct to M. 4.Since p2 flag=0 p1 can successfully enters to critical section. 5.Again p2 woke-up set its flag =1 and it will also get CS area. L: flag(i) := 0 for j in {1,..,i-1} do if flag(j) = 1 then go to L flag(i) := 1 M: for j {i+1, ,n} do if flag(j) = 1 then go to M Crit(i) Exit(i) Flag(i)=0 ME not Guaranteed

5. Algorithm:- Mutual exclusion: Assume that two process are in critical section. Process L: flag(i) := 0 for j in {1,..,i-1} do if flag(j) = 1 then go to L flag(i) := 1 for j in {1, ,i-1} do if flag(j) = 1 then go to L M: for j {i+1, ,n} do if flag(j) = 1 then go to M Crit(i) Exit(i) Flag(i)=0 If processes i and j are ever in C simultaneously, both must have set their flags := 1. Assume that process i sets flag(i) := 1 first. Keeps flag(i) = 1 until process i leaves C. After flag(i) := 1, must have flag(j) := 1, then j must see flag(i) = 0, before j C. Impossible! So Mutual Exclusion is Guaranteed

6. Correctness Algorithm :- Process P(b) {Higher index} Process P(a) {Lower index} Process L: flag(i) := 0 for j in {1,..,i-1} do if flag(j) = 1 then go to L flag(i) := 1 for j in {1, ,i-1} do s if flag(j) = 1 then go to L M: for j {i+1, ,n} do if flag(j) = 1 then go to M Crit(i) Exit(i) Flag(i)=0 Wbf = 0 Waf = 0 rf Raf = 0 fr Waf =1 fr fr Wbf = 1 rf rf Rbf = 0 Raf = 0 Critical section Critical Section

7. Progress :- Consider fair execution (each process keeps taking steps) Assume for contradiction that, after some point some process is in T, no one is in C, and no one C later. Call the processes in T the contenders. Divide the contenders into two sets: >>P, the contenders that reach label M, and >>Q, the contenders that never reach M Claim P contains at least one process: >> Process with the lowest index among all the contenders is not blocked from reaching M. Let i = largest index of a process in P. Claim process i eventually C: All others with larger indices eventually see a smaller-index contender and drop back to L, setting their flags := 0 So i eventually sees all these = 0 and C. Contradiction. Process L: flag(i) := 0 for j in {1,..,i-1} do if flag(j) = 1 then go to L flag(i) := 1 for j in {1, ,i-1} do if flag(j) = 1 then go to L M: for j {i+1, ,n} do if flag(j) = 1 then go to M Crit(i) Exit(i) Flag(i)=0 Progress Guaranteed .

8. Deadlock:- For Deadlock four condition has to be true ME , Hold and wait , Non-Premption, Circular wait Process L: flag(i) := 0 for j in {1,..,i-1} do if flag(j) = 1 then go to L flag(i) := 1 for j in {1, ,i-1} do if flag(j) = 1 then go to L M: for j {i+1, ,n} do if flag(j) = 1 then go to M Crit(i) Exit(i) Flag(i)=0 Assume Holds true P1 P2 1. So P1 depends upon P2 only when P1 stuck at M and flag(P2)=1, flag(P1)=1. 2. Since Stuck just before the 2nd for loop and next step it is depends upon P1. 3. Since flag(P1)=1 , P2 will go back to L state and Flag(P2)=0 4.Now P1 in no more dependent upon P2 so our assumption is wrong 5.Deadlock is not possible

9. Lockout freedom:- 1.Suppose P2 after setting its flap(P2)=1 got prompted. Process L: flag(i) := 0 for j in {1,..,i-1} do if flag(j) = 1 then go to L flag(i) := 1 for j in {1, ,i-1} do if flag(j) = 1 then go to L M: for j {i+1, ,n} do if flag(j) = 1 then go to M Crit(i) Exit(i) Flag(i)=0 2. Now P1 comes and it will execute 1st two for loop successfully but it will stuck at M. 3. CS is free but P1 is not able to go into that. No Lockout freedom .

10. Bounded waiting:- 1. Suppose P1 ,P2 ,P3 are contenders. Process L: flag(i) := 0 for j in {1,..,i-1} do if flag(j) = 1 then go to L flag(i) := 1 for j in {1, ,i-1} do if flag(j) = 1 then go to L M: for j {i+1, ,n} do if flag(j) = 1 then go to M Crit(i) Exit(i) Flag(i)=0 2. P1 set its flag=1 3. Since P2,P3 gets stuck at L only with flag =0 4. Suppose P1 came out and set its flag=0 now P2 will enter into CS. 5. Now suppose P1 comes again and set its flag =1 , P3 again stuck and go back to L. 6. P3 starve here. Bounded Waiting not possible

11. References:- 1. https://ocw.mit.edu/courses/electrical-engineering-and-computer- science/6-852j-distributed-algorithms-fall-2009/lecture-notes/ 2. http://groups.csail.mit.edu/tds/papers/Jensen/burnspaper.pdf

12. Thank You!!!