Lamport's Bakery Algorithm | Operating System - Computer Science Engineering (CSE) PDF Download

What do you mean by Lamport's bakery algorithm?

Lamport proposed a bakery algorithm, a software solution, for the n process mutual exclusion problem. This algorithm solves a critical problem, following the fairest, first come, first serve principle.

Why is it called the bakery algorithm?

• This algorithm is known as the bakery algorithm as this type of scheduling is adopted in bakeries where token numbers are issued to set the order of customers. When a customer enters a bakery store, he gets a unique token number on its entry. The global counter displays the number of customers currently being served, and all other customers must wait at that time. Once the baker finishes serving the current customer, the next number is displayed. The customer with the next token is now being served.
• Similarly, in Lamport's bakery algorithm, processes are treated as customers. In this, each process waiting to enter its critical section gets a token number, and the process with the lowest number enters the critical section. If two processes have the same token number, the process with a lower process ID enters its critical section.

Algorithm of Lamport's bakery algorithm

do  

{  

    entering[i] :=  true; // show interest in critical section  

   // get a token number  

    number[i] := 1 + max(number[0],  number[1], ..., number[n - 1]);     

    entering [i] :=  false;  

    for ( j :=  0 ;  j<n; j++)  

    {  

 // busy wait until process Pj receives its token number  

        while (entering [j])  

        { ; } // do nothing  

       while (number[j] !=  0 &&  (number[j], j) < (number[i], i)) // token comparison   

         { ; } // do nothing  

       }  

        // critical section  

         number[i] :=  0;  // Exit section  

        // remainder section  

    } while(1);  

Structure of process Pi for Lamport's bakery algorithm to critical section problem.

Explanation -
This algorithm uses the following two Boolean variables.

boolean entering[n];  
int number[n];

All entering variables are initialized to false, and n integer variables numbers are all initialized to 0. The value of integer variables is used to form token numbers.
When a process wishes to enter a critical section, it chooses a greater token number than any earlier number.

Consider a process Pi wishes to enter a critical section, it sets
entering[i] to true to make other processes aware that it is choosing a token number. It then chooses a token number greater than those held by other processes and writes its token number. Then it sets entering[i] to false after reading them. Then It enters a loop to evaluate the status of other processes. It waits until some other process Pj is choosing its token number.
Pi then waits until all processes with smaller token numbers or the same token number but with higher priority are served fast.
When the process has finished with its critical section execution, it resets its number variable to 0.

The Bakery algorithm meets all the requirements of the critical section problem.

• Mutual Exclusion: we know that when no process is executing in its critical section, a process with the lowest number is allowed to enter its critical section. Suppose two processes have the same token number. In that case, the process with the lower process ID among these is selected as the process ID of each process is distinct, so at a particular time, there will be only one process executing in its critical section. Thus the requirement of mutual Exclusion is met.
• Progress: After selecting a token, a waiting process checks whether any other waiting process has higher priority to enter its critical section. If there is no such process, P will immediately enter its critical section. Thus meeting progress requirements.
• Bounded Waiting: As awaiting, the process will enter its critical section when no other process is in its critical section and
  • If its token number is the smallest among other waiting processes.
  • If token numbers are the same, it has the lowest process ID among other waiting processes.

Advantages of Lamport's bakery algorithm

• Lamport's bakery algorithms are free from starvation.
• Lamport's Bakery algorithm follows a FIFO.
• Lamport's Bakery algorithm works with atomic registers.
• Lamport's Bakery algorithm is one of the simplest known solutions to the mutual exclusion problem for the general case of the N process.
• This algorithm ensures the efficient use of shared resources in a multithreaded environment.

Disadvantages of Lamport's bakery algorithm

• Lamport's bakery algorithm is unreliable as a failure of any one of the processes will halt progress. It has a high message complexity of 3(N - 1) messages per entry/exit into the critical section.