I came across an interesting synchronization problem called the shared bathroom problem. The shared resource is the bathroom. It needs to be shared among males and females. However, the bathroom resource sharing protocol must be implemented in the following manner:

1. Mutual exclusion: persons of opposite sex may not occupy the bathroom simultaneously,
2. Fairness: everyone must wait in line in a civil manner without cutting in line.

Rule #1 lays out similar characteristics compare to the reader/writer problem. But the rules here are slightly relaxed, where there could be multiple male or female occupying the resource at once.

To ensure starvation-freedom, rule #2 enforces fairness such that any person will eventually enter the bathroom.

A Jab at the Problem

I have just started (re)learning Java professionally, so I might as well write it in Java.

Mapping the problem to implementation is fairly straight forward. There are two classes of threads – MaleThread and FemaleThread. Both types of threads will try to enter a resource (class) called Bathroom. Bathroom is consisted of two API – enter(Person p) and leave(Person p), where Person is just a data class that indicates holds the gender and thread information.

So an example of a male thread entering the bathroom could be the following:

Person male = new Person(Thread.currentThread(), Gender.MALE);
bathroom.enter(male);
// do some private business
bathroom.leave(male);

From rule #1, the Bathroom class has the characteristics of a mutex, where pending threads need to be blocked and unblocked efficiently. For this, I chose LockSupport for thread synchronization. For the fairness requirement in rule #2, ConcurrentLinkedQueue is used for the FIFO behavior.

class Bathroom
{
  private AtomicInteger numMale = new AtomicInteger(0);
  private AtomicInteger numFemale = new AtomicInteger(0);
  private Queue waiters = new ConcurrentLinkedQueue();

  public void enter(Person person)
  {
    boolean wasInterrupted = false;

    waiters.add(person);

    // Block while not first in line, or if there is opposite sex in the
    // bathroom.
    while (waiters.peek() != person
        || getOppositeGenderCount(person.getGender()).get() > 0)
    {
      LockSupport.park();

      // ignore interrupts while waiting
      if (Thread.interrupted())
        wasInterrupted = true;
    }

    // Increment the current sex count since this person is first in line
    // and there is no opposite sex in the bathroom.
    getGenderCount(person.getGender()).getAndIncrement();

	// Remove its from the waiting line. This is the linearization point.
    waiters.remove();

	// wake up the next waiter
    Person nextPersonInLine = waiters.peek();
    if (nextPersonInLine != null)
    {
      LockSupport.unpark(nextPersonInLine.getOwnerThread());
    }

    // reassert interrupt status on exit
    if (wasInterrupted)
    {
      person.getOwnerThread().interrupt();
    }
  }

  public void leave(Person person)
  {
	// decrement the gender count, and wake up the next waiter
    getGenderCount(person.getGender()).getAndDecrement();

    Person nextPersonInLine = waiters.peek();
    if (nextPersonInLine != null)
    {
      LockSupport.unpark(nextPersonInLine.getOwnerThread());
    }
  }

  private AtomicInteger getOppositeGenderCount(Gender gender)
  {
    if (gender == Gender.MALE)
      return numFemale;
    else if (gender == Gender.FEMALE)
      return numMale;

    // something is wrong here.
    return numMale;
  }

  private AtomicInteger getGenderCount(Gender gender)
  {
    if (gender == Gender.MALE)
      return numMale;
    else if (gender == Gender.FEMALE)
      return numFemale;
    // something is wrong here.
    return numMale;
  }
}
public class Person
{
  public Person(Thread ownerThread, Gender sex)
  {
    super();
    this.ownerThread = ownerThread;
    this.sex = sex;
  }
  private final Thread ownerThread;
  private final Gender sex;

  public Thread getOwnerThread()
  {
    return ownerThread;
  }

  public Gender getGender()
  {
    return sex;
  }
}

public enum Gender
{
  FEMALE, MALE
}

Some Explanation

The bathroom itself is lock-free. From the high level, every person who tries to enter a bathroom goes through a “test and set” process for two conditions – 1. he/she is the first person in the waiting line, and 2. no opposite sex is in the bathroom. As soon as these two conditions are valid, the person will enter the bathroom by incrementing his gender count, and leave the waiting line. This is the linearization point of the enter() method.

The leave() method simply decrements the gender count and notify the next in line to wake up and re-test the conditions to enter the bathroom.

For suspending and waking up threads, LockSupport’s park() and unpark() method were used. The park() method is simple, where threads are suspended until a “permit” is available through the call to unpark(). However, the unpark() function has a subtle yet beautiful post-condition. It guarantees the following:

Make available the permit for the given thread, if it was not already available. If the thread was blocked on park() then it will unblock. Otherwise, its next call to park() is guaranteed not to block.

Because unpark() guarantees unblocking the next call to park(), the bathroom class does not suffer from lost-wakeup.

Thoughts

To prove the code’s correctness, I was able to identify the linearization point of enter() and leave(). It also passes my unit test. However, I do not claim to have complete confident in the correctness of the algorithm. After all, data race detection is a NP hard problem.

I found two similar blog posts on this problem. This solution is different in the sense that only guarantees starvation-freedom (as oppose to fairness, which is more restrictive). Another solution guarantees fairness (also uses FIFO queue), and is written in a lock-based manner.

Performance was not measured here, as it is only a proof of concept.

The bathroom resource is not recursive (not re-entrant). After all, recursive lock is evil.

The source can be downloaded here. (Written with Java 1.6)