Lamport\'s bakery algorithm is a software approach to mutual exclusion based on
ID: 3673203 • Letter: L
Question
Lamport's bakery algorithm is a software approach to mutual exclusion based on the ticket based system used in bakeries and meat counters for ensuring that customers are serviced in turn. The algorithm is as follows:
The arrays choosing and number are initialized to false and 0, respectively. The operating system ensures that each element i of each array may be read and written by process i but only read by any other process.
Describe in words how this algorithm works.
Explain how the algorithm avoids deadlock and enforces mutual exclusion.
Explanation / Answer
# N-Thread Mutual Exclusion: Lamport's Bakery Algorithm
System:
/* Array to record which threads are taking a ticket */
boolean choosing[n];
/* Value of the ticket for each thread initialized to 0 */
int tickets[n];
/* Initialize and launch all threads */
startThreads();
Thread Tx:
void main()
{
x = ThreadNumber();
while(!done)
{
/* Take a ticket */
choosing[x] = true; /* begin ticket selection process */
ticket[x] = maxValue(ticket)+1;
choosing[x] = false; /* end ticket selection process */
/* Wait until turn of current ticket comes */
for(i=0; i < n; i++)
{
if(i == x)
continue;
/* Busy wait while Ti is choosing a ticket */
while(choosing[i] != false);
/* Busy wait while current ticket value is lowest */
while(ticket[i] != 0 && ticket[i] < ticket[x]);
/* In case of tie, favor smaller thread number */
if(ticket[i] == ticket[x] && i < x)
{
/* Busy wait until Ti exits critical section*/
while(ticket[i] != 0);
}
}
/* Critical section code */
ticket[x] = 0; /* exitMutualExclusion() */
}
}
1) Describe in words how this algorithm works.
In simple words, When a process wishes to enter its critical section, it is assigneda ticket number. The ticket number assigned is calculated by adding oneto the largest of the ticket numbers currently held by the processes waitingto enter their critical section and the process already in its critical section.The process with the smallest ticket number has the highest precedence forentering its critical section. In case more than one process receives the sameticket number, the process with the smallest numerical name enters its criticalsection. When a process exits its critical section, it resets its ticket numberto zero.
2)
a) how that the algorithm avoids deadlock ?
If each process is assigned a unique process number, then thereis a unique, strict ordering of processes at all times. Therefore, deadlockcannot occur
b) how that it enforces mutual exclusion.
To demonstrate mutual exclusion, we first need to prove the following
lemma:
if Pi is in its critical section, and Pk has calculated its number[k] and is
attempting to enter its critical section, then the following relationship holds:
(number[i], i) < (number[k], k)
To prove the lemma, define the following times:
Tw1 Pi reads choosing[k] for the last time, for j = k, in its first
wait, so we have choosing[k] = false at Tw1.
Tw2 Pi begins its final execution, for j = k, of the second while
loop. We therefore have Tw1 < Tw2 .
Tk1 Pk enters the beginning of the repeat loop.
Tk2 Pk finishes calculating number[k].
Tk3 Pk sets choosing[k] to false. We have Tk1 < Tk2 < Tk3 .
Since at Tw1, choosing[k] = false, we have either Tw1 or Tk1 or Tk3 or Tw1.
In the first case, we have number[i] or number[k], since Pi was assigned its
number prior to Pk; this satisfies the condition of the lemma.
In the second case, we have Tk2 < Tk3 < Tw1 < Tw2 , and therefore Tk2 < Tw2.
This means that at Tw2 , Pi has read the current value of number[k].
Moreover, as Tw2 is the moment at which the final execution of the second
while for j = k takes place, we have (number[i], i) < (number[k], k), which
completes the proof of the lemma.
It is now easy to show the mutual exclusion is enforced. Assume that Pi is
in its critical section and Pk is attempting to enter its critical section. Pk
will be unable to enter its critical section, as it will find number[i] = 0 and
(number[i], i) < (number[k], k).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.