# 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:

• At least one thread trying to enter level i succeeds
• If more than one thread is trying to enter level i, at least one is blocked.

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() {
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() {
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. #### 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() {
flag[i] = true; //I want to enter my critical section
label[i] = max(label, ..., 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() { 