Lably
Skip to content

Lamport's bakery algorithm

Logic for safely sharing computer resources

  • 14 min read
  • 2 chapters

Related on Lably

Through Algorithm, Correctness (computer science) and Mutual exclusion

Lab · Class 8–12Algorithms & SortingLab · Class 11Algorithm VisualizerLab · Class 11Decision Trees & Random ForestsLab · Class 10–11Reinforcement Learning Basics

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

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. This is the equivalent of giving the number ticket to the oldest customer to request it.

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 id="mwLQ">a</sub> - the customer number for thread <i id="mwLg">a</i>, and // i<sub id="mwLw">a</sub> - the thread number for thread <i id="mwMA">a</i>, then (n<sub id="mwMQ">a</sub>, i<sub id="mwMg">a</sub>) < (n<sub id="mwMw">b</sub>, i<sub id="mwNA">b</sub>)

which is equivalent to:

(n<sub id="mwNw">a</sub> < n<sub id="mwOA">b</sub>) or ((n<sub id="mwOQ">a</sub> == n<sub id="mwOg">b</sub>) and (i<sub id="mwOw">a</sub> < i<sub id="mwPA">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.

Sign in to keep reading

One more chapter is free with a Lably account.

More in Computing and communication

ISBNUnique numeric book identifier since 1970X (social network)American social networking serviceWayback MachineDigital archive by the Internet ArchivePython (programming language)General-purpose programming languageMacOSOperating system for Apple computersUnicodeCharacter encoding standard