Concurrency P4: Marking your territory with simple locks

20 Sep 2018

Time to dive into some examples of locks now that we know that we want to achieve mutual exclusion. Locks are one of the simpler ways to keep threads critical sections from overlapping and provide good insight into how to solve the problem of mutual exclusion. So without further ado, here are three types of locks you’ll probably ever see anywhere, as they only work for two threads and have some downsides.

LockOne

It doesn’t get more simple than this. The lock one algorithm uses two flags to keep track of whether the threads want to enter their critical section. Calling the lock() and unlock() methods on a LockOne object provides these steps:

private boolean[] flag = new boolean[2];

public void lock() {
  int i = ThreadID.get();
  int j = 1 - i; //The ID of the other thread
  flag[i] = true; //Indicate you want to enter

  while(flag[j]) {} //Means other thread is in CS, so wait till they leave their CS
}

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

This lock, however will deadlock if the two threads are trying to enter their critical section at the same time. Both threads set their flag to true at the same time and go into the while loop where each wait for the other to leave their critical section. So they’re stuck waiting forever. Lock one illustration

LockTwo

Still pretty simple. This time there’s only one shared variable called victim, which each thread sets and waits for the other thread to set itself as a victim. So the thread that isn’t a victim can proceed into their critical section.

private int victim;

public void lock() {
  int i = ThreadID.get();
  victim = i;
  while(victim == i) {} //Wait until the other thread becomes the victim
}

public void unlock() {
}

Funnily enough this lock works perfectly for threads working at the same time, but deadlocks for threads that don’t run at the same time. If one thread locks and makes itself the victim, it’s going to wait forever if the other thread never tries to lock the LockTwo object.

Lock one illustration

Peterson Lock

Now it’s time for the best of the two locks above. One never dealocks if the threads never try to enter their critical section at the same time and the other never deadlocks if the threads try to enter their critical section at the same time. So using both flags and a victim, we have a lock that is starvation (and therefore deadlock)-free.

private boolean[] flag = new boolean[2];
private int victim;

public void lock() {
  int i = ThreadID.get();
  int j = 1 - i; //The ID of the other thread
  flag[i] = true; //Indicate you want to enter
  victim = i;

  while(flag[j] && victim == i) {} //Wait while the other person is interested and you're the victim
}

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

This lock guarantees that both threads eventually enters their critical section. I suggest you read over the code and convince yourself that it is true.

Alright, now that we’ve seen some nice and simple locks, we’re ready to move on to some locks that can manage n threads instead of just two threads.

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