Lamport's bakery algorithm
Encyclopedia
Lamport's bakery algorithm is a computer algorithm
devised by computer scientist Leslie Lamport
, which is intended to improve the safety in the usage of shared resources among multiple 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 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.
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 his or her 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 the Lamport's analogy
need slight modification. It is possible that more than one thread will get the same number when they request it; this cannot be avoided. Therefore, it is assumed that the thread identifier i is also a priority identifier. A lower value of i means a higher priority and threads with higher priority will enter the critical section
first.
When a thread wants to enter the critical section, it has to check whether it is its turn to do so. It should check the numbers 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 will be written in the form:
(a, b) < (c, d)
which is equivalent to:
(a < c) or ((a c) and (b < d))
Once the thread ends its critical job, it gets rid of its number and enters the non-critical section.
This part is analogous to actions that occur after shopping, such as putting change back into the wallet.
Entering: array [1..NUM_THREADS] of bool = {false};
Number: array [1..NUM_THREADS] of integer = {0};
1 lock(integer i) {
2 Entering[i] = true;
3 Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);
4 Entering[i] = false;
5 for (j = 1; j <= NUM_THREADS; j++) {
6 // Wait until thread j receives its number:
7 while (Entering[j]) { /* nothing */ }
8 // Wait until all threads with smaller numbers or with the same
9 // number, but with higher priority, finish their work:
10 while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) {
11 /* nothing */
12 }
13 }
14 }
15 //critical section
16 unlock(integer i) {
17 Number[i] = 0;
18 }
19
20 Thread(integer i) {
21 while (true) {
22 lock(i);
23 // The critical section goes here...
24 unlock(i);
25 // non-critical section...
26 }
27 }
In this example, all threads execute the same "main" function, Thread. In real applications, different threads often have different "main" functions.
Note: The thread also checks itself before entering the critical section, but that doesn't cause any delays since the loop conditions will evaluate as false.
. The original proof shows that for overlapping reads and writes to the same storage cell only the write must be correct. 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 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
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
External links
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
devised by computer scientist Leslie Lamport
Leslie Lamport
Leslie Lamport is an American computer scientist. A graduate of the Bronx High School of Science, he received a B.S. in mathematics from the Massachusetts Institute of Technology in 1960, and M.A. and Ph.D. degrees in mathematics from Brandeis University, respectively in 1963 and 1972...
, which is intended to improve the safety in the usage of shared resources among multiple threads
Thread (computer science)
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...
by means of mutual exclusion
Mutual exclusion
Mutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...
.
In computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, it is common for multiple threads to simultaneously access the same resources. Data corruption
Data corruption
Data corruption refers to errors in computer data that occur during writing, reading, storage, transmission, or processing, which introduce unintended changes to the original data...
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
Mutual exclusion
Mutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...
algorithms designed to prevent concurrent
Concurrency (computer science)
In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other...
threads entering critical sections of code concurrently to eliminate the risk of data corruption.
Analogy
Lamport envisioned a bakeryBakery
A bakery is an establishment which produces and sells flour-based food baked in an oven such as bread, cakes, pastries and pies. Some retail bakeries are also cafés, serving coffee and tea to customers who wish to consume the baked goods on the premises.-See also:*Baker*Cake...
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 his or her 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 the Lamport's analogy
Analogy
Analogy is a cognitive process of transferring information or meaning from a particular subject to another particular subject , and a linguistic expression corresponding to such a process...
need slight modification. It is possible that more than one thread will get the same number when they request it; this cannot be avoided. Therefore, it is assumed that the thread identifier i is also a priority identifier. A lower value of i means a higher priority and threads with higher priority will enter the critical section
Critical section
In concurrent programming a critical section is a piece of code that accesses a shared resource that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task or process will have to wait a fixed time to...
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 and others must wait.When a thread wants to enter the critical section, it has to check whether it is its turn to do so. It should check the numbers 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
Pseudocode
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
this comparison will be written in the form:
(a, b) < (c, d)
which is equivalent to:
(a < c) or ((a c) and (b < d))
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.
Definitions
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.
Pseudocode
// declaration and initial values of global variablesEntering: array [1..NUM_THREADS] of bool = {false};
Number: array [1..NUM_THREADS] of integer = {0};
1 lock(integer i) {
2 Entering[i] = true;
3 Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);
4 Entering[i] = false;
5 for (j = 1; j <= NUM_THREADS; j++) {
6 // Wait until thread j receives its number:
7 while (Entering[j]) { /* nothing */ }
8 // Wait until all threads with smaller numbers or with the same
9 // number, but with higher priority, finish their work:
10 while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) {
11 /* nothing */
12 }
13 }
14 }
15 //critical section
16 unlock(integer i) {
17 Number[i] = 0;
18 }
19
20 Thread(integer i) {
21 while (true) {
22 lock(i);
23 // The critical section goes here...
24 unlock(i);
25 // non-critical section...
26 }
27 }
In this example, all threads execute the same "main" function, Thread. In real applications, different threads often have different "main" functions.
Note: The thread also checks itself before entering the critical section, but that doesn't cause any delays since the loop conditions will evaluate as false.
Discussion
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-swapCompare-and-swap
In computer science, the compare-and-swap CPU instruction is a special instruction that atomically compares the contents of a memory location to a given value and, only if they are the same, modifies the contents of that memory location to a given new value...
. The original proof shows that for overlapping reads and writes to the same storage cell only the write must be correct. 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 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
Number[i]. If the higher-priority process were preempted before setting Number[i], the low-priority process will see that the other process has a number of zero, and enter the critical section; later, the high-priority process will ignore equal Number[i] for lower-priority processes, and also enter the critical section. As a result, two processes can enter the critical section at the same time. The bakery algorithm then uses the Entering variable to make the assignment on line 3 look like it were 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
yield.External links
- Wallace Variation of Bakery Algorithm which overcomes limitations of Javascript language
- Lamport's Bakery Algorithm
- Another JavaScript implementation by a.in.the.k