Java公平信号量

Question

我试图理解这个旧考试任务的答案，学生应该使用 javas 重入锁实现一个公平的二进制信号量。我不明白这些计数器的意义:

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

它在任务描述中说“您可以假设程序中最多有 20 个线程使用信号量。此外，在程序的单次运行期间最多将执行 1000 万次信号量操作。 “在任务的解决方案中它说:“每个尝试获取信号量的线程都必须在队列中注册自己，并且只有在之前的线程离开它之后才离开队列。每个线程使用 32- 记住它在队列中的位置位计数器。计数器不会回绕，因为最多会在信号量上执行 1000 万次操作，但即使计数器可能回绕，代码也能正常工作。”

在我看来，老师在解决方案中似乎遗漏了 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 一样队列。文档明确告诉您:

...this lock does not guarantee any particular access order. ... Note however, that fairness of locks does not guarantee fairness of thread scheduling. ...

阅读全文 docs ，即使您创建了一个公平的 ReentrantLock，它也不能保证它是公平的。

然而，显示的代码确实表现得很好，因为计数器使线程以 FIFO 顺序获取锁。

代码是票锁，所以也请查看 https://en.wikipedia.org/wiki/Ticket_lock