Bakery Algorithm in Operating System

Introduction to Bakery Algorithm

The Bakery algorithm is a mutual exclusion algorithm that allows multiple processes to access a shared resource without interference. The algorithm was first introduced by Leslie Lamport in 1974, and it has been widely used in various operating systems since then.

The Bakery algorithm is a simple yet powerful algorithm that provides a fair and efficient solution to the critical section problem. It ensures that processes enter the critical section in the order in which they request access, thus preventing any process from being starved of the resource indefinitely.

In this article, we will discuss the Bakery algorithm in detail, including its implementation, advantages, and limitations.

Critical Section Problem

The critical section problem is a fundamental problem in operating system design. It arises when two or more processes need to access a shared resource or a critical section of code concurrently. The problem is how to ensure that these processes do not interfere with each other's operations and do not produce incorrect or inconsistent results.

To solve the critical section problem, we need to provide mutual exclusion, which means that only one process can access the shared resource or critical section of code at a time. There are many algorithms for providing mutual exclusion, and the Bakery algorithm is one of them.

Implementation of Bakery Algorithm

The Bakery algorithm is a simple algorithm that uses a ticketing system to determine the order in which processes can enter the critical section.

The algorithm is based on the following two principles:

1. A process can request access to the critical section by obtaining a ticket.
2. A process can enter the critical section only when its ticket number is called.

The implementation of the Bakery algorithm is straightforward. Each process is assigned a unique integer number, which represents its ticket. When a process wants to enter the critical section, it first obtains a ticket by incrementing a shared integer variable called "ticket."

Once a process has obtained its ticket, it waits until its turn comes. The turn is determined by the order of the ticket numbers. For example, if process 1 obtains ticket 1, and process 2 obtains ticket 2, process 1 has to wait until process 2 completes its critical section before it can enter.

To ensure fairness, the Bakery algorithm uses a second shared variable called "turn," which indicates the process whose turn it is to enter the critical section. The turn variable is initially set to 0, and processes take turns by checking whether their ticket number matches the turn variable.

Deadlock Prevention in Bakery Algorithm

To prevent deadlock in the Bakery algorithm, it is important to ensure that processes release the resource after they have finished using it. In other words, processes must be careful to release the critical section before waiting for their turn to enter it again.

Additionally, it is important to ensure that the order in which processes request access to the critical section is fair and consistent. One way to achieve this is to use a priority queue, which orders processes based on their priority level.

The priority level can be based on various factors, such as the length of time a process has been waiting, the number of times it has been denied access, or the urgency of its task. By prioritizing processes based on these factors, the Bakery algorithm can ensure that processes are granted access to the critical section in a fair and efficient manner.

Bakery Algorithm Example

Let's consider an example to illustrate how the Bakery algorithm works. Suppose we have two processes, P1 and P2 that need to access a shared resource or critical section.

• Initially, the ticket and turn variables are both set to zero. When P1 requests access to the critical section, it first obtains a ticket by incrementing the ticket variable to 1. The turn variable is then set to 1, indicating that it is P1's turn to enter the critical section.
• P1 enters the critical section and completes its task. It then releases the resource and resets its ticket number to zero. The turn variable is set to 2, indicating that it is now P2's turn to enter the critical section.
• P2 requests access to the critical section and obtains a ticket by incrementing the ticket variable to 1. However, it cannot enter the critical section immediately because its ticket number does not match the turn variable, which is currently set to 2.
• P2 waits until its turn comes, which happens when P1 completes its critical section and releases the resource. P2 then enters the critical section, completes its task, and releases the resource.
• The Bakery algorithm ensures that processes enter the critical section in the order in which they request access, which prevents any process from being starved of the resource indefinitely.

Advantages of Bakery Algorithm

• The Bakery algorithm provides a fair and efficient solution to the critical section problem. It ensures that no process is starved of the resource indefinitely and that all processes have an equal chance of accessing the critical section.
• The algorithm is also simple and easy to implement, making it a popular choice for many operating systems. The Bakery algorithm is widely used in real-time systems, where fairness and efficiency are critical.
• Another advantage of the Bakery algorithm is that it does not require any special hardware or software support, making it highly portable and compatible with a wide range of systems.

Limitations of Bakery Algorithm

• Although the Bakery algorithm is a powerful solution to the critical section problem, it has some limitations. One of the main limitations is that it is not scalable. As the number of processes increases, the overhead of maintaining the ticket and turn variables also increases, which can result in performance degradation.
• Another limitation of the Bakery algorithm is that it can be affected by the order in which processes request access to the critical section. In some cases, this can lead to a situation where some processes are unfairly delayed, while others are given priority.
• Finally, the Bakery algorithm can be prone to deadlock if not implemented correctly. Deadlock occurs when two or more processes are waiting for each other to release a resource, resulting in a situation where none of the processes.

Conclusion

The Bakery algorithm is a simple and powerful algorithm for providing mutual exclusion in operating systems. It provides a fair and efficient solution to the critical section problem, ensuring that processes access the shared resource or critical section in a consistent and orderly manner.

Although the Bakery algorithm has some limitations, such as scalability and susceptibility to deadlock, it remains a popular choice for many operating systems, particularly in real-time systems where efficiency and fairness are critical.

Overall, the Bakery algorithm is a valuable tool for ensuring that concurrent processes can access shared resources or critical sections without interference, making it an essential component of modern operating systems.