Interface Lock has a useful boolean fairness parameter to guarantee fairness in locking - thread that waits for lock the longest, gets the lock first. And I thought I wanted to use it everywhere as it prevents starvation. Well, not before I read that it can cost us performance.
I couldn't find an answer this question, so I hope someone can clear this up. Meaning, what is the difference between taking threads that "honor" fairness and threads that don't? Aren't they both stored in some "ordinary" queue where other waiting threads are?
When a lock is released, and when more than one thread is waiting for it, the thread that's been waiting the longest is the one that's most likely to find that memory pages that it's going want have been swapped out while it was "sleeping." The thread that's been sleeping for the least amount of time is the most likely to be "ready-to-go."
Apologies to @xingbin if that's what you were trying to say.
First of all it's not the interface Lock that has that fairness, but it's ReentrantLock.
The threads that issue Lock::lock might not be put into a queue at all, be that in fair or unfair mode.
The unfair mode is slightly easier to understand. In this mode, the thread that requests the lock (via calling Lock::lock), tries to get it immediately without getting enqueued. If that succeeds - done. It is not put into any queue, since it could get the lock. Notice that this does not care if there are already waiting threads in the queue, thus it is "unfair" (to the other already waiting threads). If it could not acquire the lock (meaning someone else has it), it is put on the queue.
On the other hand, in fair mode, the thread that calls lock, first has to check if there are already threads waiting for this lock. If there are no such threads and it can take the lock: no enqueue and take the lock. If it can't - it is enqueued.
One last point is that in both fair and unfair mode, the threads are put on the same queue; that is: fair/unfair is not about the internal representation of the queue.