Java公平信号量

Question

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

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

在任务描述中提到：“您可以假设在使用信号量的程序中最多会有20个线程。此外，在单次运行程序时，最多会执行1000万次信号量操作。” 在解决方案中提到：“每个试图获取信号量的线程必须在队列中注册，并且只有在线程之前离开队列后才能离开队列。每个线程都使用32位计数器记住它在队列中的位置。计数器不会循环，因为在信号量上最多只会执行1000万次操作，但即使计数器可能会循环，代码仍会生效。”

对我来说，似乎老师在解决方案中省略了10百万线程的限制，但我的主要问题是：当线程被放置在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();     
    }
}

- TheEagle

---

引用Javadoc：但请注意，锁的公平性并不保证线程调度的公平性。 请参见https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/locks/ReentrantLock.html#ReentrantLock(boolean)。 - GhostCat

如果任务要求实现一个公平的互斥锁，那么允许学生使用公平互斥锁就有点无意义了。关于“ReentrantLock(true)难道不能保证公平性”的问题，是否公平取决于实现方式。 - Solomon Slow

Answer 1

虽然您可能认为在ReentrantLock上阻塞的线程是排队的，但不能保证队列按照公平的FIFO顺序运行。文档明确告诉您：

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

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

然而，所示代码确实是公平的，因为计数器使线程以FIFO顺序获取锁。

该代码是Ticket Lock，因此还要查看https://en.wikipedia.org/wiki/Ticket_lock。

- nos