Bakery Algorithm

The new idea is one used by people sharing a resource requiring mutual exclusion, which is to take a ticket on arrival and wait until that ticket is chosen for service.

For example

In a bakery, in a bakery, people take a ticket on arrival and then wait for exclusive service. In fact, Lamport’s algorithm is often referred to as the bakery algorithm. If the tickets are serviced in increasing order by ticket number, the people are serviced in FIFO order (in contrast to the cyclic order in the previous algorithm). However, Lamport’s version of tickets is quite different from that used by people in a store. This algorithm uses M intention states (tickets), needing B bits (usually the size of an integer), and N intents.

• Entry protocol has 2 steps
• First step: thread_i takes a ticket and stores it at position $i$ in the shared array ticket. The ticket array is initialized to 0, where 0 means a thread has retracted its intent.
• Selecting ticket is very weird. A thread computes a unique ticket based on the current ticket values held by any waiting threads. Ticket generation is accomplished by finding the maximum ticket value of the waiting threads and creating a new ticket value one greater, which requires an $O(N)$ search.
  • does not guarantee uniqueness of the ticket value since two ore more threads can simultaneously compute the same maximum ticket value and add one to it!
  • to solve this, we use the same trick for the N-Thread Mutual Exclusion/N-thread prioritize-retract-intent solution $\to$ assign a priority to each position in the intent array.
  • Now if two threads have the same ticket value, their position in the intent array will be used to break the tie!
• Second step of entry protocol: a thread linearly searches through all the waiting threads (including itself) and waits for any thread with higher priority, because it has a lower ticket value or lower subscript for equal tickets.
• a thread sets its position in this choosing array before starting to compute a ticket, and resets it only after assigning its new ticket.
• search in the second step is now composed of two checks.
• first, determine if a thread is computing a ticket, if so, wait for the ticket to be assigned. second, check if the thread wants in, if so, is it higher priority.
• now a lower-priority thread knows if a higher-priority thread is computing a ticket and waits for the new ticket value to appear.
• When the ticket value appears, it is either less, equal, or greater than the checking thread’s ticket, and it proceeds or waits appropriately.

Assignments MUST be atomic for the bakery algorithm $\to$ since choosing and ticket values can be read by other threads.

Simplified Lamport’s algorithm: (Hehner and Shyamasundar)

• Fold’s the choosing array into the ticket array.
• Two tickets values are set aside to indicate that either a thread does not want into the CS or it is computing a ticket.
• A non-waiting thread is identified by the maximum possible ticket value, INT_MAX $\to \infty$, meaning lowest priority, and all elements of the ticket array are initialized to this maximum value.
• Computing a ticket is identified by the minimum ticket value, 0, implying highest priority.
  • A thread starts computing its ticket by setting its ticket value to zero, which is the highest-priority ticket-value. No thread can have a ticket value of zero because the maximum value found is always incremented.
• Notice, during the computation of a thread’s ticket-value, the INT_MAX value must be ignored.
• when a thread is searching in the second step, it cannot proceed if a thread is computing a ticket because of the temporary high-priority value. Only after the new ticket value is assigned does the searching thread make progress.
• Finally, while busy waiting in the second step, it is unnecessary to explicitly check for non-waiting threads because they all have a priority lower than the searching thread, i.e., INT_MAX.

No starvation

because the ticket values are always increasing as long as there are waiting threads. Hence, if a thread exits the critical section and tries to rush in again ahead of other waiting threads, it must generate a ticket value greater than any waiting thread because it examines all their ticket values.

Because no thread retracts its intent in the entry protocol, this new maximal ticket value ensures the arriving thread cannot enter before any of the other waiting threads and establishes its bound with respect to any waiting threads.

• Lamport RW-safe
• Hehner/Shyamasundar RW-unsafe
  • assignment ticket[priority] = max can flickers to INT_MAX $\Rightarrow$ other tasks proceed