How to write simple fair semaphore?

Question

I found simple realization of semaphore(my CustomSemaphore) and as I understand this is 'not fair' one because into secure block can enter only first thread all time(I am not sure). How can I write fair semaphore(analog of concurrency new Semaphore(1, true);)

   public class SimpleSemaphoreSample2 {
    CustomSemaphore cSem = new CustomSemaphore(1);

    public static void main(String[] args) {
        SimpleSemaphoreSample2 main = new SimpleSemaphoreSample2();
        Semaphore sem = new Semaphore(1, true);
        Thread thrdA = new Thread(main.new SyncOutput(sem, "Thread1"), "Thread1");
        Thread thrdB = new Thread(main.new SyncOutput(sem, "Thread2"), "Thread2");

        thrdA.start();
        thrdB.start();

        try {
            thrdB.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("END");
    }

    class SyncOutput implements Runnable {
        private Semaphore sem;
        private String msg;

        public SyncOutput(Semaphore s, String m) {
            sem = s;
            msg = m;
        }

        @Override
        public void run() {
            while (true) {
                try {
//                  sem.acquire();
                    cSem.acquire();
                    System.out.println("Before");
                    Thread.sleep(500);
                    System.out.println(msg);
                    Thread.sleep(500);
                    System.out.println("After");
                    Thread.sleep(500);
                } catch (Exception exc) {
                    exc.printStackTrace();
                }
//              sem.release();
                cSem.release();
            }
        }
    }

    public class CustomSemaphore {
        private int counter;

        public CustomSemaphore() {
            this(0);
        }

        public CustomSemaphore(int i) {
            if (i < 0)
                throw new IllegalArgumentException(i + " < 0");
            counter = i;
        }

        public synchronized void release() {
            if (counter == 0) {
                this.notify();
            }
            counter++;
        }

        public synchronized void acquire() throws InterruptedException {
            while (counter == 0) {
                this.wait();
            }
            counter--;
        }
    }
}
enter code here

Answer 1

Your semaphore is not fair because it is possible that a thread wait forever. Think about a mutex (binary semaphore) used to write a value by 3 threads. T1 acquire, T2 wait and T3 wait. Now during release, you notify and one between T2 and T3 take the semaphore (let say T2). Now T1 come back and wait. When T2 notify, T1 takes it. It can happen as many times as possible, and T3 will never have the semaphore.

One change can be to use a simple FIFO inside the semaphore. When an thread has to wait, you add his id in the Queue. Now when you notify, you notify to all the threads. The only thread which progress is the one which is at the head of the queue.

Answer 2

According to Java Concurrency In Practice it states that

intrinsic locking offers no deterministic fairness guarantees

Intrinsic locking here is using synchronized. So there is no way you can make this Semaphore example fair without replacing synchronized with Lock lock = new ReentrantLock(true);

Where the true as constructor argument tells the ReentrantLock to be fair

Edit based on a comment by @trutheality

If you really want it to be correct without using the ReentrantLock, you can implement the Semaphore inheriting the synchronization primitives from the AbstractQueuedSynchronizer. This would prove to be quite complicated and if you can correctly write it with ReentrantLock I would suggest that. Note: ReentrantLock delegates its synchronization to the AQS.