Java fair semaphore

Question

I'm trying to understand the answer of this old exam-task where the students is supposed implement a fair binary semaphore using javas reentrantlock. I don't understand the point of these counters:

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

It says in the description of the task that "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." In the solution of the task it says: "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".

To me it seems that the teacher left out the limitations of 10 million threads in the solution but my main question is why the counters are needed when, threads is put in a queue in the lock() and await() statements, and there is a free-variable that is being checked. And doesn't the ReentrantLock(true) take care of the fairness?

Solution:

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

While you might think of threads blocking on a ReentrantLock as being queued, there's no guarantee that queue behaves fairly as a FIFO queue. The documentation explicitly tells you that:

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

Read the entire docs, even when you create a fair ReentrantLock, it doesn't guarantee that it's fair.

The code shown however, does behave fairly, as the counter makes the threads acquire the lock in a FIFO order.

The code is a Ticket Lock, so also check out https://en.wikipedia.org/wiki/Ticket_lock