Bakery Algorithm in OS

What is Bakery Algorithm in the Operating System?

The Bakery Algorithm is a simple solution for the critical section problem. To recall, the critical section is a section of the code that can be accessed by more than one process. If the critical section is accessed and changed by two or more processes at the same time, this would lead to inconsistency in the data as both processes will try to change the same data at the same time.

Hence, this is a very important concern when dealing with two or more processes that can access a section of the code. The Bakery Algorithm provides a way to make sure that only one process can access the critical section at a time to ensure consistency. The Bakery Algorithm provides a general solution to the critical section problem, which means it provides a solution when there are N processes that can access the critical section.

Let us take a look at what exactly the algorithm is.

Original Bakery Algorithm

Before moving on to the code let’s see the pseudocode of the original Bakery Algorithm and address some of the rules which are followed in the code.

Lexicographical Timestamp order: Process(#Ticket,#Process -Id) - When comparing the processes we will first compare their ticket numbers and arrange them. If two processes have the same ticket numbers equal, then they will be ordered according to their process ID. The process with a smaller process-id will be placed first.

The process has two shared variable arrays:

Choosing[i] and number[i] are changeable by the process[i] only. Before entering the critical section, the process attains a number. The process with the smallest number is allowed to enter the critical section first followed by the process with the second smallest number and so on. If two processes like Process[i] and Process[j] receive the same number, they are arranged on the basis of lexicographical timestamp order, i.e. the one which occured first is served first.

Let us now take a look at the pseudocode and then understand the logic behind it.

When the process[i] wants to access the Critical Section, we will first assign number[i] to be one greater than the maximum of all the other process numbers. This is done to ensure that if there are other processes waiting to enter the critical section, they are served first as they arrived first. After this, the process[i] waits for each process[j] (where j is 0<=j<N) until all process[j] is not in the middle of choosing a number, then it busy waits until all process[j]'s number i.e number[j] is greater than equal to zero(in lexicographical timestamp order). After getting past all the other processes the process[i] finally enters the critical section.

When process[i] exits from the critical section we change the number[i] to 0, so as to allow some other process to enter the critical section.

This is the original bakery algorithm, let us now take a look at a more simplified version of the same.

Simplified Bakery Algorithm

The simplified Bakery algorithm is just the simplified version of the previously defined Bakery algorithm.

Similar to the previous algorithm we have N processes, but in the simplified bakery algorithm, the processes have only one shared variable array:

This array of integers can be read by all processes but only one process is allowed to change one index of the array, which corresponds to the number assigned to that process.

Let us look at what happens in this algorithm by taking a look at its pseudocode, and then go into its details.

Basically, whenever process[i] wants to enter its critical section, we will assign number[i] to be 1 higher than the maximum of the current values of number[j] of all other processes. This is a way of assigning itself the last place in a hypothetical queue of processes waiting to execute their critical section.

Now we check all other processes, that is process[j] where 0<=j<=n-1 and j is not equal to i,process[i] will wait until number[j] either becomes 0 or becomes greater than number[i]. This is basically the current process trying to analyze when it comes to the head of the hypothetical queue because at this point either all other processes in the queue will have number[j] > number[i] or number[j] = 0. Hence, the process[i] will essentially be at the top of the queue at this point.

Hence, now the process[i] can enter the critical section, and when process[i] leaves the critical section, we set number[i] to 0, so that any other process waiting can access the critical section. This means this process[i] is basically out of the waiting queue now.

How can the Critical Section Problem be Solved in the Bakery Algorithm?

As we saw in the description of the Bakery algorithm above, each process is given a number, sort of like a token, which determines when the process can enter the critical section. Only one process is allowed to enter the critical section which has the smallest token number and the smallest process ID in case of a clash in values of the token numbers.

In this way the Bakery algorithm ensures that only one process is allowed to access the critical section at a time, thus maintaining consistency of data and helping to solve the critical section problem. When a process is done with its critical section, the process is assigned the token number 0 so that it is no longer in the waiting queue, and the next process with the smallest token number is allowed to enter the critical section.

Hence, the Bakery Algorithm is a simple and effective way to solve the critical section problem for a generalized case of N processes.