How to write a simple honest semaphore?

Question

I found a simple semaphore implementation (my CustomSemaphore), and, as I understand it, this is "unfair" because only the first thread for the whole time can be included in a safe block (I'm not sure). How to write a fair semaphore (analogue 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 the thread is waiting forever. Think of a mutex (binary semaphore) used to write values ​​in three threads. T1, wait T2 and wait T3. Now during release you are notifying, and one between T2 and T3 takes a semaphore (let them say T2). Now T1 will be back and waiting. When T2 notifies, T1 takes it. This can happen as many times as possible, and T3 will never have a semaphore.

One change might be to use a simple FIFO inside the semaphore. When a thread needs to wait, you add its identifier to the queue. Now that you are notifying, you are notifying all streams. The only thread that moves forward is the one that is at the head of the queue.

Answer 2

According to Java Concurrency In Practice it says

internal locking gives no guarantee of determinism

The internal lock here is used synchronized . Thus, you cannot make this Semaphore example fair without replacing synchronized with Lock lock = new ReentrantLock(true);

Where the constructor argument true indicates that ReentrantLock will be honest

Edit based on @trutheality comment

If you really want this to be correct without using ReentrantLock, you can implement a Semaphore that inherits synchronization primitives from AbstractQueuedSynchronizer . This would prove to be quite complex, and if you can write it correctly using ReentrantLock, I would suggest this. Note. ReentrantLock delegates its AQS synchronization.

Answer 3

I have an example of a repeated semaphore, but it is intended for only 2 applicants. If you want to extend the code by more than 2, you must implement a simple list and make some changes, including the test for wait() in the aquire() method.

 package nmscd.utils; /** * A simple, non-reentrant, one permit, FAIR semaphore * @author cosmo */ public class SimpleSemaphore { private boolean aquired = false; private Thread currThread; private Thread releasedThread; private int pretendersCount = 0; public synchronized void aquire() throws InterruptedException { while ((Thread.currentThread() != currThread && aquired) || (pretendersCount > 0 && Thread.currentThread() == releasedThread)) { pretendersCount++; try { wait(); } finally { pretendersCount--; } } aquired = true; currThread = Thread.currentThread(); } public synchronized void release() { if (Thread.currentThread() == currThread) { aquired = false; currThread = null; releasedThread = Thread.currentThread(); notifyAll(); } } } 

The key in this class is to check in the aquire method to find out if the thread you want is needed, all other threads must wait. Therefore, if you have enough information to determine this stream, you can choose which stream is returned from aquire()