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

Question

我发现信号量的简单实现(我的CustomSemaphore),据我所知这是'不公平',因为进入安全块只能一次输入第一个线程(我不确定).如何编写公平的信号量(并发模拟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.现在,当您通知时,您将通知所有线程.进度的唯一线程是位于队列头部的线程.

Answer 2

根据Java Concurrency In Practice, 它说明了这一点

内在锁定不提供确定性公平性保证

这里使用内在锁定synchronized.因此,如果不替换它synchronized,你就无法使这个Semaphore示例公平Lock lock = new ReentrantLock(true);

凡true作为构造参数告诉ReentrantLock的是公平

根据@trutheality的评论进行编辑

如果您确实希望它在不使用ReentrantLock的情况下正确,则可以实现Semaphore从AbstractQueuedSynchronizer继承同步原语.这将证明是非常复杂的,如果你能用ReentrantLock正确地写它,我会建议.注意:ReentrantLock将其同步委托给AQS.