Analysis of Burns Algorithm for Concurrent Program Correctness

Burns' algorithm
   
Presented By:
  
   Shubham Raju Chaudhari
   
  
203050093
      CS 766 Analysis of Concurrent Programs
 
Instructor
Prof.  Ashutosh Gupta
Plan:-
Burns Algorithm
Correctness of algorithm (Mutual Exclusion)
Progress
 Deadlock
Limitation
No Lockout freedom
Bounded waiting
Algorithm:-
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
Each process goes through 3 loops, sequentially:
1. Check flags of processes with smaller indices.
2. Check flags of processes with smaller indices.
3. Check flags of processes with larger indices.
 • If it passes all tests  
 C.
  • Otherwise, drops back:
 
L
M
Algorithm:-
Process
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
 
Why double Checking for Smaller indices???
P1 and P2 are two process want critical region, take following scenario
 1.Suppose P2 wants to enter first so it will check 1
st
 for
loop.
 2.After 1
st
 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.
ME not Guaranteed…
Algorithm:-
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
 
Mutual exclusion:
Assume that two process are in critical section.
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…
Correctness Algorithm :-
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
Process P(a) 
{
Lower index
}
 
 
W
af 
= 0
 
 
 
W
af =
1
 
R
bf = 0
          
Critical section
Process P(b) {
Higher index
}
 
W
bf 
= 0
 
R
af 
= 0
 
W
bf 
= 1
 
R
af 
= 0
 
 
Critical Section
 
rf
 
rf
 
rf
 
fr
 
fr
 
fr
Progress :-
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
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.
Progress Guaranteed……….
Deadlock:-
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
For Deadlock four condition has to be true
 ME , Hold and wait , Non-Premption, Circular wait
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 2
nd
 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…
Lockout freedom:-
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
1.Suppose P2 after setting its flap(P2)=
1 
got prompted.
2. Now P1 comes and it will execute 1
st
 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….
Bounded waiting:-
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
1.
Suppose P1 ,P2 ,P3 are contenders.
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……
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
Thank  You!!!
Slide Note
Embed
Share

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

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.

E N D

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!!!

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#