Critical Section for n Processes
When Processes need to share one source, they must run without disturbing each other knowing only one process can use a source. To achieve this Critical Section concept has been developed and it was tried to solve this by various C.S. algorithms. Bakery Algorithms is a solution to this for n processes.
Bakery Algorithm
For n processes algorithm works like this:
Before entering C.S. a process is given a number. A process having minimum number enters into C.S. if Pi and Pj has same number and i<j then Pi enters C.S. in first order. Otherwise Pj enters C.S.
Number giving is always in
increasing order (i.e.1,2,3,3,3,3,4,5
).
max (a0, , an-1) : is the biggest number in number[n] for Pi.
boolean choosing[n]; // initially
false
int number[n]; // initially 0
do
{
choosing[i] = true;
number[i] =
max(number[0], number[1],
, number [n 1])+1;
choosing[i] = false;
for (j = 0; j < n;
j++)
{
while (choosing[j]) ;
while ((number[j] != 0)
&& (number[j] < number[i])) ;
}
CRITICAL SECTION
number[i] = 0;
REMAINDER SECTION
} while (1); // exit when false
How Bakery Algorithm Convenient?
a) Mutual Exclusion: Arrays choosing[] and number[] is used to guarantee only one process will enter C.S. in any time. Form array number[n] minimum process number is selected. When Pi=Pj, smallest number is selected from i, j.
b) Progress: Time quantum mechanism tq is used to ensure that process will exit at most in tq seconds.
c) Bounded Waiting: Processes waiting to enter C.S. will wait n unit times in extreme conditions.
References
[1] Silberschatz, Galvin and Gagne, Operating System Concepts, John Wiley
and Sons Inc., Chapter 7, Pages 194-196, 2002.