Java 公平信号量

Question

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

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

它在任务描述中说 "You may assume that there will be at most 20 threads in the program using the semaphore. Also, at most 10 million semaphore operations will be performed during a single run of the program." 在任务的解决方案中，它说："Each thread that attempts to acquire the semaphore must register itself in a queue, and leave the queue only after the threads before has left it. Each thread remember its place in the queue using a 32-bit counter. The counter will not wrap around, as at most 10 million operations will be ever performed on the semaphore, but the code works even if the counter may wrap around".

对我来说，老师似乎在解决方案中忽略了 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

Java 公平信号量

Java fair semaphore

java

multithreading

semaphore