Thread Mutual Exclusive Section

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 wh开发者_开发百科ich 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
     }
   }
 }

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!)

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)

You can use ReentrantLock with fairness parameter set to true. Then the next thread served will be the thread waiting for the longest time i.e. the one that arrived first.

Here is my attempt. The idea to give a ticket number for each thread. Threads are entered based on the order of their ticket numbers. I am not familiar with Java, so please read my comments:

 public class Test {
    public static final Object obj = new Object();
    unsigned int count = 0;  // unsigned global int
    unsigned int next  = 0;  // unsigned global int

    public void doSomething() {
       unsigned int my_number;  // my ticket number

       // the critical section is small. Just pick your ticket number. Guarantee FIFO
       synchronized (obj) { my_number = count ++; } 

       // busy waiting
       while (next != my_number);

       // mutual exclusion

       next++;  // only one thread will modify this global variable
    }
 }

The disadvantage of this answer is the busy waiting which will consume CPU time.

Using only Object's method and synchronized, in my point of view is a little difficult. Maybe, by setting each thread a priority, you can garantee an ordered access to the critical section.