Thread Mutual Exclusive Section

Question

Hello I just had phone interview I was not able to answer this question and would like to know the answer, I believe, its advisable to reach out for answers that you don't know. Please encourage me to understand the concept.

His question was:

"The synchronized block only allows one thread a time into the mutual exclusive section. When a thread exits the synchronized block, the synchronized block does not specify which of the waiting threads will be allowed next into the mutual exclusive section? Using synchronized and methods available in Object, can you implement first-come, first-serve mutual exclusive section? One that guarantees that threads are let into the mutual exclusive section in the order of arrival? "

 public class Test {
   public static final Object obj = new Object();

   public void doSomething() {
     synchronized (obj) {
          // mutual exclusive section
     }
   }
 }

Answer 1

Here's a simple example:

public class FairLock {
    private int _nextNumber;
    private int _curNumber;

    public synchronized void lock() throws InterruptedException {
        int myNumber = _nextNumber++;
        while(myNumber != _curNumber) {
            wait();
        }
    }

    public synchronized void unlock() {
        _curNumber++;
        notifyAll();
    }
}

you would use it like:

public class Example {
  private final FairLock _lock = new FairLock();

  public void doSomething() {
    _lock.lock();
    try {
      // do something mutually exclusive here ...
    } finally {
      _lock.unlock();
    }
  }
}

(note, this does not handle the situation where a caller to lock() receives an interrupted exception!)

Answer 2

what they were asking is a fair mutex

create a FIFO queue of lock objects that are pushed on it by threads waiting for the lock and then wait on it (all this except the waiting in a synchronized block on a separate lock)

then when the lock is released an object is popped of the queue and the thread waiting on it woken (also synchronized on the same lock for adding the objects)