Bakery Algorithm

Bakery algorithm is an algorithm for multiprocessing units which share the same resouces that i discovered while i was studying for my OS exam.Here is some information about it:

Definiton of the problem:
Lamport's bakery algorithm is a computer algorithm devised by computer scientist Dr Leslie Lamport which is intended to improve the robustness of multiple thread-handling processes by means of mutual exclusion.

it is common for multiple threads to simultaneously access the same resources. They either try to write into the same memory location, or one thread reads a location before another has finished writing into it. This is undesirable as it can end in hazardous loss

Algorithm to solve the problem:

• Notation <= lexicographical order (ticket # , process id #)

1. (a , b)<(c,d) if (a)<(c) or if a=c and (b)<(d). Here we compare the process numbers and the values.The process which has a less process will access the resource.If they are same we will compare the values.
2. max (a0,…, an-1) is a number, k, such that k ≥ ai for i - 0, …, n – 1

Shared data

boolean choosing[n];
int number[n];
Data structures are initialized to false and 0 respectively

The pseudocode:

do {
choosing[i] = true;
number[i] = max(number[0], number[1], …, number [n – 1])+1;
choosing[i] = false;
j=0;
while(j is smaller than n)
while (choosing[j]) ;
while ((number[j] != 0)&& ( (number[j],j)<(number[i],i)) }
j++;
}
critical section
number[i] = 0;
reminder section}while (1);