Explain the Filter Lock

The Art of Multiprocess Programming is great, but occasionally you find an explanation which is needlessly complex. I hope this clarifies things Use this example execution and graphic alongside the code to better understand the filter lock. If you have any questions or are confused, feel free to reach out to me.

First, here's the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#!/bin/usr/java
class Filter implements Lock {
  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)) {};
    }
  }
  public void unlock() {
    int me = ThreadID.get();
    level[me] = 0;
  }
}

Example Execution

Suppose we have a filter lock for 4 threads. If a single thread wants to acquire the lock then the process is simple. Let this thread be Thread 0.

1. Sets level[0] = 1
2. Sets victim[1] = 0
3. The while loop immediately breaks since no threads exist at a higher level
4. Repeat steps 1-3 until the thread exits the for loop.
5. The thread has acquired the lock, State at this point: level[0] = 3 and victim array is all zeros since nothing has reset it.

Suppose a second thread wants to acquire the lock. Let this thread be Thread 1.

1. Sets level[1] = 0
2. Sets victim[0] = 1
3. The while loop holds because the condition level[k] >= i is true for k=0, and no one has changed the victim at level 0. This halts Thread 1's progress.

Suppose a third thread wants to acquire the lock. Let this thread be Thread 2.

1. Sets level[2] = 0
2. Sets victim[0] = 2
3. ...

HOLD UP!

Thread 1 breaks out of the while loop. victim[0] == 1 is no longer true. Thread 1 passes to the next step of the for loop and does the following:

1. Sets level[1] = 1
2. Sets victim[1] = 0
3. The while loop holds because the condition level[k] >= i is still true for k=0 and now victim[1] = 0 is true until something changes.

BACK TO THREAD 2

1. Thread 3 spins on the while loop because the condition level[k] >= i is true for both k=0 and k=1 (only one is necessary), and victim[0] = 1

To be continued...

Explanatory Graphic

Finally, here's the graphic. It's pretty big, so feel free to open it in another window.