Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Bakery Algorithm in the Operating System?
3.
How does the Bakery Algorithm work?
3.1.
Analogy
3.2.
Threads and bakery analogy 
3.3.
Algorithm pseudocode
3.4.
Explanation
3.5.
Implementation in C
3.6.
C
3.6.1.
Output
4.
Advantages of Bakery Algorithm in OS
5.
Disadvantages of Bakery Algorithm in OS
6.
Frequently Asked Questions
6.1.
What is the use of the bakery algorithm?
6.2.
Why is it called the bakery algorithm?
6.3.
What is the other name for Bakery Algorithm?
6.4.
What is the difference between Peterson's algorithm and the Bakery Algorithm?
7.
Conclusion
Last Updated: Jul 9, 2024
Medium

Bakery Algorithm in OS

Author Sanjana Yadav
0 upvote
Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

Bakery Algorithm

Lamport's bakery algorithm is a computer technique developed by computer scientist Leslie Lamport that uses mutual exclusion to increase safety in the use of shared resources across several threads. Multiple threads accessing the same resources at the same time are frequent in computer science.

Data corruption can occur when two or more threads attempt to write into the same memory region simultaneously or when one thread accesses a memory location before another has finished writing into it. 

Lamport's bakery algorithm is one of many mutual exclusion algorithms meant to prevent concurrent threads from entering critical sections of code simultaneously, hence reducing the risk of data corruption.

For N processes, the Bakery Algorithm in OS is a critical section solution. The algorithm maintains the first-come, first-served principle.

Also Read - Threads in Operating System

What is Bakery Algorithm in the Operating System?

The Bakery Algorithm is a synchronization algorithm used in operating systems to ensure the ordered access of multiple processes or threads to shared resources. It was developed to prevent resource conflicts and enforce mutual exclusion. The algorithm assigns each process a unique integer ticket when it requests access to the critical section and it guarantees fairness and avoids problems like starvation but can be less efficient than other synchronization methods due to its ticket-based approach.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

How does the Bakery Algorithm work?

The Bakery Algorithm uses tickets or numbers to handle the ordered access of critical resources. When a process or thread requests access to a critical section, it is assigned a unique number. Then, processes compare their numbers and the lowest ticket gains access first. This ensures fairness and prevents resource conflicts. It is effective in guaranteeing mutual exclusion and fairness but can be less efficient than other synchronization techniques.

Let's discuss about the algorithm in more detail.

Analogy

  • a bakery with a numbering machine
  • each customer receives a unique number
  • numbers increase by one as customers enter
  • global counter displays the number of customers currently being served
  • all others wait inline 
  • after the baker is finished serving the customer, the following number is displayed 
  • served customer leaves


Threads and bakery analogy 

  • The thread is assigned a number before entering its critical section. The recipient of the lowest number proceeds to the critical section.
  • If threads Ti and Tj receive the same number,
     
if i < j 
Ti is served first; 
else 
Tj is served first.

 

  • The numbering scheme always generates numbers in ascending enumeration sequence, i.e., 1, 2, 3, 3, 3, 4, 5, etc...
     

Notation – lexicographical order (ticket number, process id number) – 

The ticket number is first compared. 

If they are the same, the process ID is compared next, i.e.

- (a, b) < (c, d) if a < c or if a = c and b <d

-  max(a [0], . . ., a [n-1]) is a number, k, such that k >= a[i] for i = 0, . . ., n - 1

Shared data-selecting is an array of boolean values [0..n – 1], and num is an array of integer values [0..n – 1].  Both are set to False and Zero, respectively.

Algorithm pseudocode

repeat
    selecting[i] := true;
    num[i] := max(num[0], num[1], ..., num[n - 1])+1;
    selecting[i] := false;
    for j := 0 to n - 1
        do begin
            while selecting[j] do no-op;
            while num[j] != 0
                and (num[j], j) < (num[i], i) do no-op;
        end;
        critical section
    num[i] := 0;
    
        remainder section

until false;

Explanation

To begin, the process sets its "selecting" variable to TRUE, signifying its intention to enter the critical section.

The highest ticket number related to other processes is then allocated to it. The variable "selecting" is then set to FALSE, indicating that it now has a new ticket number. This is the most important and confusing aspect of the algorithm.

It is, in fact, a small critical section in itself! The aim of the first three lines is that whenever a process changes its TICKET value, no other process should be permitted to verify its previous ticket value, which is now expired. This is why, before verifying the ticket value inside the for loop, we first ensure that all other processes have the "selecting" variable set to FALSE.

Following that, we examine the ticket values of processes, ensuring that the process with the lowest ticket number/process id is included in the critical section. The ticket value is simply reset to zero at the exit section.

Implementation in C

  • C

C

#include "pthread.h" /*Importing the thread library */
#include "stdio.h"
#include "unistd.h" /*Importing POSIX Operating System API library*/
#include "string.h"
#define MEMBAR __sync_synchronize() /* memory barrier instruction*/
#define THREAD_COUNT 8
volatile int num[THREAD_COUNT]; /*volatile prevents the compiler
from applying any optimizations.*/
volatile int selecting[THREAD_COUNT];
volatile int res;
void lock_thread(int thread)
{
   // Before getting the ticket number
   //"selecting" variable is set  true
   selecting[thread] = 1;
   MEMBAR;
   // Memory barrier applied
   int max_num = 0;
   // Finding Maximum ticket value among current threads
   for (int i = 0; i < THREAD_COUNT; ++i)
   {
       int ticket = num[i];
       max_num = ticket > max_num ? ticket : max_num;
   }
   // Allotting new ticket value as maximum+ 1
   num[thread] = max_num + 1;
   MEMBAR;
   selecting[thread] = 0;
   MEMBAR;
   //ENTRY Section starts
   for (int other = 0; other < THREAD_COUNT; ++other)
   {
       // Applying the bakery algorithm conditions
       while (selecting[other])
       {
       }
       MEMBAR;
       while (num[other] != 0 && (num[other] < num[thread] || (num[other] == num[thread] && other < thread)))
       {
       }
   }
}
// EXIT Section
void unlock_thread(int thread)
{
   MEMBAR;
   num[thread] = 0;
}
// CRITICAL Section
void use_res(int thread)
{

   if (res != 0)
   {
       printf("The Resource was acquired by %d, but is still in-use by %d!\n",  thread, res);
   }
   res = thread;
   printf("%d is using resource...\n", thread);

   MEMBAR;
   sleep(2);
   res = 0;
}

//Simplified function to show the implementation
void *thread_body(void *arg)
{

   long thread = (long)arg;
   lock_thread(thread);
   use_res(thread);
   unlock_thread(thread);
   return NULL;
}

int main(int argc, char **argv)
{

   memset((void *)num, 0, sizeof(num));
   memset((void *)selecting, 0, sizeof(selecting));
   res = 0;

   // Declaring the thread variables
   pthread_t threads[THREAD_COUNT];

   for (int i = 0; i < THREAD_COUNT; ++i)
   {
       // Creating a new thread with the function
       //"thread_body" as its thread routine
       pthread_create(&threads[i], NULL, &thread_body, (void *)((long)i));
   }
   for (int i = 0; i < THREAD_COUNT; ++i)
   {
       // Reaping the resources used by
       // all threads once their task is completed.
       pthread_join(threads[i], NULL);
   }
   return 0;
}

Output

1 is using resource...
0 is using resource...
2 is using resource...
3 is using resource...
4 is using resource...
6 is using resource...
7 is using resource...
5 is using resource...

Advantages of Bakery Algorithm in OS

  • For the general case of the N process, Bakery algorithm in OS is one of the simplest known solutions to the mutual exclusion problem.
  • This algorithm ensures that shared resources are used efficiently in a multithreaded environment.
  • It is free from starvation.
  • It uses FIFO.
  • It works with atomic registers.

Disadvantages of Bakery Algorithm in OS

Lamport's bakery algorithm in OS is unreliable because any one of the processes can fail and halt progress. The message complexity is substantial, with 3(N - 1) messages for each entry/exit into the critical section.

Also Read - Dekker's Algorithm

Frequently Asked Questions

What is the use of the bakery algorithm?

Lamport's bakery method is one of many mutual exclusion algorithms meant to prevent concurrent threads from entering key parts of code at the same time, hence reducing the risk of data corruption.

Why is it called the bakery algorithm?

This algorithm is called as the Bakery algorithm because of the ticketing system. Like tokens are given to customers in a bakery, each process is assigned a unique number, and based on this number access to the critical section is provided.

What is the other name for Bakery Algorithm?

The Bakery Algorithm is also known as Lamport's Bakery Algorithm, and it is a concurrency control method that is used for mutual exclusion in shared resources among processes and threads.

What is the difference between Peterson's algorithm and the Bakery Algorithm?

Both Peterson's and the Bakery Algorithm provide mutual exclusion in concurrent processes. The key difference is implementation -- Peterson's is suitable for two processes, while the Bakery Algorithm is better for multiple processes.

Conclusion

Cheers if you reached here! In this blog, we learned about Lamport's Bakery Algorithm in OS. We covered the basic idea behind the algorithm, how it works and its implementation with c code.
 

Also, check out some of the Guided Paths on topics such as Data Structures and Algorithms, Operating Systems, etc. as well as some Test Series and Interview Bundles only on Coding Ninjas Studio.

Live masterclass