Another software approach to mutual exclusion is Lamport\'s bakery algorithm , s

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].

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.