Bakery Algorithm in Process Synchronization a lecture...... by ramu dayinaboyina

 

 The Bakery algorithm is one of the simplest known solutions to the mutual exclusion problem for the general case of N process. Bakery Algorithm is a critical section solution for N processes. The algorithm preserves the first come first serve property.

Bakery Algorithm working process

In the Bakery Algorithm, each process is assigned a number (a ticket) in a lexicographical order. Before entering the critical section, a process receives a ticket number, and the process with the smallest ticket number enters the critical section. If two processes receive the same ticket number, the process with the lower process ID is given priority.

Algorithm  fairness
The Bakery Algorithm ensures fairness by assigning a unique ticket number to each process based on a lexicographical order. This ensures that processes are served in the order they arrive, which guarantees that all processes will eventually enter the critical section.

• Before entering its critical section, the process receives a number. Holder of the smallest number enters the critical section.
• If processes Pi and Pj receive the same number,

if i < j 
Pi is served first; 
else 
Pj is served first.

• The numbering scheme always generates numbers in increasing order of enumeration; i.e., 1, 2, 3, 3, 3, 3, 4, 5, …

Notation – lexicographical order (ticket #, process id #) – Firstly the ticket number is compared. If same then 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 – choosing is an array [0..n – 1] of boolean values; & number is an array [0..n – 1] of integer values. Both are initialized to False & Zero respectively. Algorithm Pseudocode –

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