java - 如何编写简单的公平信号量？

Question

我发现信号量(我的 CustomSemaphore)的简单实现，据我所知，这是“不公平”的，因为进入安全 block 始终只能进入第一个线程(我不确定)。我如何编写公平的信号量(并发性的模拟 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

你的信号量是不公平的，因为线程有可能永远等待。想一想用于由 3 个线程写入值的互斥量(二进制信号量)。 T1 获取，T2 等待，T3 等待。现在在发布期间，您通知 T2 和 T3 之间的一个信号量(假设 T2)。现在T1回来等着。当T2通知时，T1接受它。它可以发生尽可能多的次数，并且 T3 永远不会有信号量。

一个变化可以是在信号量内使用一个简单的 FIFO。当一个线程必须等待时，您将他的 id 添加到队列中。现在，当您通知时，您会通知所有线程。唯一取得进展的线程是位于队列头部的线程。