Lamport's bakery algorithm

Introduction

In computer science a common situation is one where multiple threads simultaneously access the same resources. They either try to write into the same memory location or one thread reads that location before the other one finished writing into it. Usually, we don't want to allow this, because it can end in hazardous loss of data. There are many solutions to this problem and this article will talk about one of them, Lamport's bakery algorithm, one of many mutual exclusion algorithm.

Algorithm

Dr. Leslie Lamport introduced solution for this problem. His "vision" is bakery with numbering machine at its entrance so every customer gets his own unique number. Numbers increase by one as customers enter the store. There is also a global counter that displays number of current customer that is being served. All other customers wait patiently in a queue until current customer ends his shopping and new number is displayed. When done shopping, customer loses his number and he can do whatever he wants, except doing another shopping without getting a new number.

Due to the limitations of the computer architecture, some elements from upper idea need several slight modifications. First, we will allow that more than one thread can get the same number when they request it. This situation is quite possible and it cannot be avoided. Therefore, we will assume that thread identifier i is also a priority identifier. Smaller i means higher priority and thread with higher priority will first enter the critical section.

Critical section is part of code that needs to be executed by only one thread in some time period. It accesses resources from the beginning of this story so correct management of them can be accomplished. When thread ends its critical job, it gets rid of its number and enters non-critical section.

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

Pseudocode

    // declaration and initial values of global variables
    LastNumber: integer = 0;
    i: array [1..N] of integer;
    
 1  Thread(i) {
 2      while (1) {
 3          Enter[i] = 1;
 4          Number[i] = LastNumber + 1;
 5          LastNumber = Number[i];
 6          Enter[i] = 0;
 7          for (j = 1; j <= N; j++) {
 8              while (Enter[j] == 1) {
 9                  // wait
10              }
11              while ((Number[i] != 0) && ((Number[j],j) < (Number[i],i))) {
12                  // wait
13              }
14          }
15          // critical section...
16          Number[i] = 0;
17          // non-critical section...
18      }
19  }