View source for Lamport's bakery algorithm

{{Short description|Logic for safely sharing computer resources}}
{{see also|Lamport's distributed mutual exclusion algorithm}}
{{Multiple issues|
{{More footnotes needed|date=December 2010}}
{{One source|date=August 2022}}
}}
{{Use dmy dates|date=October 2022}}

'''Lamport's bakery algorithm''' is a computer [[algorithm]] devised by computer scientist [[Leslie Lamport]], as part of his long study of the [[correctness (computer science)|formal correctness]] of [[concurrent system]]s, which is intended to improve the safety in the usage of shared resources among multiple [[thread (computer science)|threads]] by means of [[mutual exclusion]].

In [[computer science]], it is common for multiple threads to simultaneously access the same resources. [[Data corruption]] can occur if two or more threads try to write into the same [[Memory (computers)|memory]] location, or if one thread reads a memory location before another has finished writing into it.  Lamport's bakery algorithm is one of many [[mutual exclusion]] algorithms designed to prevent concurrent threads entering [[critical sections]] of code concurrently to eliminate the risk of data corruption.

== Algorithm ==

=== Analogy ===
Lamport envisioned a bakery with a numbering machine at its entrance so each customer is given a unique number. Numbers increase by one as customers enter the store. A global counter displays the number of the customer that is currently being served. All other customers must wait in a queue until the baker finishes serving the current customer and the next number is displayed. When the customer is done shopping and has disposed of their number, the clerk increments the number, allowing the next customer to be served. That customer must draw another number from the numbering machine in order to shop again.

According to the analogy, the "customers" are threads, identified by the letter ''i'', obtained from a global variable.

Due to the limitations of computer architecture, some parts of Lamport's [[analogy]] need slight modification. It is possible that more than one thread will get the same number ''n'' when they request it; this cannot be avoided (without first solving the mutual exclusion problem, which is the goal of the algorithm). Therefore, it is assumed that the thread identifier ''i'' is also a priority. A lower value of ''i'' means a higher priority and threads with higher priority will enter the [[critical section]] first.

=== Critical section ===
The critical section is that part of code that requires exclusive access to resources and may only be executed by one thread at a time. In the bakery analogy, it is when the customer trades with the baker that others must wait.

When a thread wants to enter the critical section, it has to check whether now is its turn to do so. It should check the number ''n'' of every other thread to make sure that it has the smallest one. In case another thread has the same number, the thread with the smallest ''i'' will enter the critical section first.

In [[pseudocode]] this comparison between threads ''a'' and ''b'' can be written in the form:
 // Let n<sub>a</sub> - the customer number for thread ''a'', and
 // i<sub>a</sub> - the thread number for thread ''a'', then
 
 (n<sub>a</sub>, i<sub>a</sub>) < (n<sub>b</sub>, i<sub>b</sub>) 
which is equivalent to:
 (n<sub>a</sub> < n<sub>b</sub>) or ((n<sub>a</sub> == n<sub>b</sub>) and (i<sub>a</sub> < i<sub>b</sub>))

Once the thread ends its critical job, it gets rid of its number and enters the '''non-critical section'''.

=== Non-critical section ===
The non-critical section is the part of code that doesn't need exclusive access. It represents some thread-specific computation that doesn't interfere with other threads' resources and execution.

This part is analogous to actions that occur after shopping, such as putting change back into the wallet.

== Implementation of the algorithm ==

=== Definitions ===

<!-- from his original paper -->
In Lamport's original paper, the ''entering'' variable is known as ''choosing'', and the following conditions apply:
* Words choosing [i] and number [i] are in the memory of process i, and are initially zero.
* The range of values of number [i] is unbounded.
* A process may fail at any time.  We assume that when it fails, it immediately goes to its noncritical section and halts. There may then be a period when reading from its memory gives arbitrary values. Eventually, any read from its memory must give a value of zero.

=== Code examples ===

==== Pseudocode ====
In this example, all threads execute the same "main" function, ''Thread''.
In real applications, different threads often have different "main" functions.

Note that as in the original paper, the thread checks itself before entering the critical section.
Since the loop conditions will evaluate as ''false'', this does not cause much delay.

<syntaxhighlight lang=c line start="0">
  // declaration and initial values of global variables
  Entering: array [1..NUM_THREADS] of bool = {false};
  Number: array [1..NUM_THREADS] of integer = {0};

  lock(integer i) {
      Entering[i] = true;
      Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);
      Entering[i] = false;
      for (integer j = 1; j <= NUM_THREADS; j++) {
          // Wait until thread j receives its number:
          while (Entering[j]) { /* nothing */ }
          // Wait until all threads with smaller numbers or with the same
          // number, but with higher priority, finish their work:
          while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) { /* nothing */ }
      }
  }
  
  unlock(integer i) {
      Number[i] = 0;
  }

  Thread(integer i) {
      while (true) {
          lock(i);
          // The critical section goes here...
          unlock(i);
          // non-critical section...
      }
  }
</syntaxhighlight>

Each thread only writes its own storage, only reads are shared. It is remarkable that this algorithm is not built on top of some lower level "atomic" operation, e.g. [[compare-and-swap]]. The original proof shows that for overlapping reads and writes to the same storage cell only the write must be correct.{{elaborate|reason=This is hard to believe; throw us a bone, here.|date=August 2020}} The read operation can return an arbitrary number. Therefore, this algorithm can be used to implement mutual exclusion on memory that lacks synchronisation primitives, e.g., a simple SCSI disk shared between two computers.

The necessity of the variable ''Entering'' might not be obvious as there is no 'lock' around lines 7 to 13. However, suppose the variable was removed and two processes computed the same <code>Number[i]</code>.  If the higher-priority process was preempted before setting <code>Number[i]</code>, the low-priority process will see that the other process has a number of zero, and enters the critical section; later, the high-priority process will ignore equal <code>Number[i]</code> for lower-priority processes, and also enters the critical section.  As a result, two processes can enter the critical section at the same time. The bakery algorithm uses the ''Entering'' variable to make the assignment on line 6 look like it was atomic; process ''i'' will never see a number equal to zero for a process ''j'' that is going to pick the same number as ''i''.

When implementing the pseudo code in a single process system or under [[cooperative multitasking]], it is better to replace the "do nothing" sections with code that notifies the operating system to immediately switch to the next thread. This primitive is often referred to as <code>yield</code>.

Lamport's bakery algorithm assumes a sequential consistency memory model. Few, if any, languages or multi-core processors implement such a memory model. Therefore, correct implementation of the algorithm typically requires inserting fences to inhibit reordering.<ref>Chinmay Narayan, Shibashis Guha, S.Arun-Kumar [https://arxiv.org/abs/1304.2936 Inferring Fences in a Concurrent Program Using SC proof of Correctness]</ref>

==== [[PlusCal]] code ====

We declare N to be the number of processes, and we assume that N is a natural number.

<syntaxhighlight lang=text>
CONSTANT N
ASSUME N \in Nat
</syntaxhighlight>

We define P to be the set {1, 2, ... , N} of processes.
<syntaxhighlight lang=text>
P == 1..N 
</syntaxhighlight>

The variables num and flag are declared as global.

<syntaxhighlight lang=text>
--algorithm AtomicBakery {
variable num = [i \in P |-> 0], flag = [i \in P |-> FALSE];
</syntaxhighlight>

The following defines {{code|LL(j, i)}} to be true iff {{mono|<<num[j], j>>}} is less than or equal to {{mono|<<num[i], i>>}} in the usual [[lexicographical order]]ing.   
<syntaxhighlight lang=text>
define { LL(j, i) == \/ num[j] < num[i]
                     \/ /\ num[i] = num[j]
                        /\ j =< i
       }
</syntaxhighlight>

For each element in P there is a process with local variables unread, max and nxt. Steps between consecutive labels p1, ..., p7, cs are considered atomic. The statement with {{code|(x \in S) { body }|tex}} sets id to a nondeterministically chosen element of the set S and then executes body. A step containing the statement await expr can be executed only when the value of expr is {{mono|TRUE}}.

<syntaxhighlight lang=text>
process (p \in P)
  variables unread \in SUBSET P, 
            max \in Nat, 
            nxt \in P;
{
p1: while (TRUE) {
      unread := P \ {self} ;
      max := 0;
      flag[self] := TRUE;
p2:   while (unread # {}) {
        with (i \in unread) { unread := unread \ {i};
                              if (num[i] > max) { max := num[i]; }
         }
       };
p3:   num[self] := max + 1;
p4:   flag[self] := FALSE;
      unread := P \ {self} ;
p5:   while (unread # {}) {
        with (i \in unread) { nxt := i ; };
        await ~ flag[nxt];
p6:     await \/ num[nxt] = 0
              \/ LL(self, nxt) ;
        unread := unread \ {nxt};
        } ;
cs:   skip ;  \* the critical section;
p7:   num[self] := 0;
 }}
}
</syntaxhighlight>

==== Java code ====

We use the AtomicIntegerArray class not for its built in atomic operations but because its get and set methods work like volatile reads and writes. Under the [[Java Memory Model]] this ensures that writes are immediately visible to all threads.

<syntaxhighlight lang="java" line="1">
AtomicIntegerArray ticket = new AtomicIntegerArray(threads); // ticket for threads in line, n - number of threads
// Java initializes each element of 'ticket' to 0
 
AtomicIntegerArray entering = new AtomicIntegerArray(threads); // 1 when thread entering in line
// Java initializes each element of 'entering' to 0
 
public void lock(int pid) // thread ID
{
    entering.set(pid, 1);
    int max = 0;
    for (int i = 0; i < threads; i++)
    {
        int current = ticket.get(i);
        if (current > max)
        {
            max = current;
        }
    }
    ticket.set(pid, 1 + max); 
    entering.set(pid, 0);
    for (int i = 0; i < ticket.length(); ++i)
    {
        if (i != pid)
        {
            while (entering.get(i) == 1) { Thread.yield(); } // wait while other thread picks a ticket
            while (ticket.get(i) != 0 && ( ticket.get(i) < ticket.get(pid) ||
                    (ticket.get(i) == ticket.get(pid) && i < pid)))
            { Thread.yield(); }
        }
    }
    // The critical section goes here...
}

public void unlock(int pid)
{
    ticket.set(pid, 0);
}
</syntaxhighlight>

== See also ==
* [[Dekker's algorithm]]
* [[Eisenberg & McGuire algorithm|Eisenberg &amp; McGuire algorithm]]
* [[Peterson's algorithm]]
* [[Szymański's algorithm]]
* [[Semaphore (programming)|Semaphores]]

== References ==
{{Reflist}}
* [https://lamport.azurewebsites.net/pubs/bakery.pdf Original Paper]
* On his [https://lamport.azurewebsites.net/pubs/pubs.html#bakery publications page], Lamport has added some remarks regarding the algorithm.

==External links==
* [http://www.onjava.com/pub/a/onjava/2006/04/05/ajax-mutual-exclusion.html Wallace Variation of Bakery Algorithm] which overcomes limitations of Javascript language. [https://web.archive.org/web/20180506193927if_/http://www.onjava.com/pub/a/onjava/2006/04/05/ajax-mutual-exclusion.html Archived] from the original on 2018-05-06.
* [https://lamport.azurewebsites.net/pubs/pubs.html#bakery Lamport's Bakery Algorithm]
* [https://github.com/ainthek/bakery Another JavaScript implementation] by a.in.the.k

[[Category:Concurrency control algorithms]]
[[Category:Articles with example pseudocode]]