Another software approach to mutual exclusion is Lamport\'s bakery algorithm , s
ID: 3871871 • Letter: A
Question
Another software approach to mutual exclusion is Lamport's bakery algorithm, so called because it is based on the practice in bakeries and other shops in which every customer receives a numbered ticket on arrival, allowing each to be served in turn. The algorithm is as follows:
}
The arrays choosing and number are initialized to false and 0 respectively. The ith element of each array may be read and written by process i but only read by other processes. The notation (a,b) < (c,d) is defined as
(a < c) or (a = c and b < d)
a. Describe the algorithm in words
b. Show that this algorithm avoids deadlock
c. Show that it enforces mutual exclusion
Explanation / Answer
The processes are numbered 0, 1, ..., N-1. Each process i has an integer variable num[i], initially 0, that is readable by all processes but writeable by process i only.
When process i is thinking, num[i] equals zero. When process i becomes hungry, it sets num[i] to a value higher than the num of every other process; this operation is assumed to be atomic in this simplified algorithm. Then process i scans the other processes in order. For each process j, process i waits until num[j] is either zero or greater than num[i]. After going past every process, process i enters the critical section. Upon leaving the critical section, process i zeroes num[i].