Lamport’s bakery algorithm [LAMP74] is a software approach to mutual exclusion t

Question

Lamport’s bakery algorithm [LAMP74] is a software approach to mutual exclusion that supports an arbitrary number of processes (unlike Peterson’s solution, which supports only two processes). Lamport’s algorithm is called the “bakery algorithm” because it is based on a practice in bakeries, delicatessens, and other shops: Every customer is given a numbered ticket on arrival, allowing each customer to be served in turn.

The pseudocode for Lamport’s algorithm is as follows:

choosing[n];

number[n];

(true)

choosing[i] = true;

number[i] = 1 + getmax(number[], n);

choosing[i] = false;

(int j = 0; j < n; j++)

(choosing[j]) { };

((number[j]!= 0)

   && (number[j], j) < (number[i], i)) { };

/* critical section */

number[i] = 0;

/* remainder section */

The arrays choosing and number are initialized by default to false and 0, respectively. The ith element of each array may be read and written by process i , but other processes may only read it. The notation (a, b) < (c, d) is defined as:

(a < c) || ((a = c) && (b < d))

Explain Lamport’s algorithm in words.

[LAMP74] Lamport, L. “A New Solution to Dijkstra’s Concurrent Programming Problem.” Communications of the ACM, August 1974.

Explanation / Answer

#include "pthread.h" #include "stdio.h" #include "unistd.h" #include "string.h" #define MEMBAR __sync_synchronize() #define THREAD_COUNT 8 volatile int tickets[THREAD_COUNT]; volatile int choosing[THREAD_COUNT]; volatile int resource; void lock(int thread) { choosing[thread] = 1; MEMBAR; int max_ticket = 0; for (int i = 0; i max_ticket ? ticket : max_ticket; } tickets[thread] = max_ticket + 1; MEMBAR; choosing[thread] = 0; MEMBAR; for (int other = 0; other

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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