Java公平信号量

Question

我试图理解这个古老的考试任务的答案，应该让学生使用javas reentrantlock实现一个公平的二进制信号量。我不理解这些计数器的意义：

int next = 0;
int nextToGo = 0;
int myNumber; 

它在任务描述中说：“您可以假设使用信号量的程序中最多有20个线程。而且，在程序的一次运行中最多可以进行1000万次信号量的操作。” 在任务的解决方案中说：“每个尝试获取信号量的线程都必须将自己注册到队列中，并且仅在线程离开队列之后才离开队列。每个线程都使用32位内存来记住其在队列中的位置位计数器。计数器将不会回绕，因为最多可以对信号量执行一千万次操作，但是即使计数器可以回绕，代码也可以工作。”

在我看来，老师在解决方案中没有保留1000万个线程的限制，但是我的主要问题是，为什么在将线程放入lock（）和await（）语句的队列中时需要计数器，正在检查的自由变量。而且ReentrantLock（true）不能保证公平吗？

解：

public class FairSemaphore {

    ReentrantLock l = new ReentrantLock(true);
    Condition c = l.newCondition();
    int next = 0;
    int nextToGo = 0;
    boolean free = true;

    public void aqcuire() throws InterruptedException {
            l.lock();
            int myNumber = next++; 

            while(!(free && myNumber == nextToGo)) {
                    c.await();
            }
            free = false;
            nextToGo++;
            l.unlock();
    }

    public void release() {
            l.lock();
            free = true;
            c.signalAll();
            l.unlock();     
    }
}

Answer 1

尽管您可能认为ReentrantLock上阻塞的线程已排队，但不能保证该队列的行为与FIFO队列相当。该文档明确告诉您：

...此锁不保证任何特定的访问顺序。...但是请注意，锁的公平性不能保证线程调度的公平性。...

阅读整个文档，即使您创建公平的ReentrantLock，也不能保证它是公平的。

但是，由于计数器使线程按FIFO顺序获取锁，因此显示的代码确实运行正常。

该代码是票证锁，因此也请查看https://en.wikipedia.org/wiki/Ticket_lock