Weekly flashcard - Lamport's Backery Algorithm

• What is this algorithm for?
• How does it work?

Download: OpenDocument, PDF

Lamport's Backery Algorithm

The algorithm good to add synchronization to you application without the usage of any hardware or software support. Because it's a very simple and robust algorithm, it's a preferred in distributed systems (Cloud Computing)

Properties:

• Each thread writes only its own space.
• Only write must be correct, the read operation can return arbitrary value(boolean or number).

The algorithm

// declaration and initial values of 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..NUM_THREADS]);
  Entering[i] = false;

  for (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 and with smaller
    // sequence number to finish their work:
    while ((Number[j] != 0) 
           && (Number[j] < Number[i]
           || Number[j] = Number[i] && j < i) {
           /* nothing */ 
    }
  }
}

unlock(integer i) {
  Number[i] = 0;
}

Explanation

Base algorithm:

The main idea that a thread must wait there is a higher priority thread in the system. (NUM[curr] > NUM[j]). The system calculate the priority as the highest existing + 1.

After the thread got the priority, no one else can get higher priority (smaller number).

Though, because of the concurrent behavior, the threads can get the same priority. In this case the thread with smaller sequence number will get the resource.

Purpose of Entering:

It helps avoid to get the same Number with smaller sequence number when the current thread already stepped through it.

It will always wait for the other thread which is picking up it's number simultaneously.