Concurrency P5: Keep them all out with locks for many threads

24 Sep 2018

Last time we looked at implementations of locks that worked for 2 threads, but that’s often not useful because we’ll most likely have to deal with multiple threads trying to access the same resource. As long as we know how many threads we’re dealing with, these two algorithms are going to get the job done.

Filter lock

This algorithm is a generalization of the Peterson lock from the previous blog post, where n-1 waiting rooms are created with the following properties:

Here’s the pseudo code.

int[] level;
int[] victim;
public Filter(int n) {
   level = new int[n];
   victim = new int[n]; // use 1..n-1
   for (int i = 0; i < n; i++) {
       level[i] = 0;
   }
}
public void lock() {
   int me = ThreadID.get();
   for (int i = 1; i < n; i++) { //attempt level 1
   level[me] = i;
   victim[i] = me;
   // spin while conflicts exist
  while ((k != me) (level[k] >= i && victim[i] == me)) {}; //Wait while there exists some thread that's not me
                                                            // and their level is higher or equal to mine AND I'm the // victim.
   }
}
public void unlock() {
   int me = ThreadID.get();
   level[me] = 0;
}

So here each thread has to go through n - 1 levels of waiting rooms to be allowed into their critical section. To be allowed to move to the next level, there cannot exist another thread at a level higher than or equal to the thread in question as long as the thread is the victim. This algorithm is deadlock free.

Filter lock illustration

Bakery lock

The thing about the filter lock is that is doesn’t let threads through in the order they enter, so we want a lock with a so called first come first served property. Lucky for us there’s one called the Bakery algorithm, which assigns numbers to threads and they can’t access their critical section as long as there are other threads with a lower number. Kind of like queuing at the bakery where you pull a number and wait until it’s called.

boolean flag[];
Label label[];

public Bakery(int n) {
  flag = new boolean[n];
  label = new Label[n];
  for(int i = 0; i < n; i++) {
    flag[i] = false;
    label[i] = 0;
  }
}

public void lock() {
  int i = ThreadID.get();
  flag[i] = true; //I want to enter my critical section
  label[i] = max(label[0], ..., label[n-1]) + 1; //Find the maximum label value and pick the one above
  while((k != i) (flag[k] && (label[k] << label[i]))) {}; //Wait while there is another thread that's interested and it has a label that's strictly smaller than yours
}

public void unlock() {
  flag[ThreadID.get()] = false;
}

In this algorithm, the trick is to ensure that a thread picks a number that’s strictly bigger than all the other numbers, so to ensure this a thread must check that no other thread has the same label as itself. This algorithm is both first come first served and deadlock free.

Bakery lock illustration

Phew, we made it through. Next up is concurrent objects.

-----------------------------------------------------------------