24 Why Choose Non-Fair Locks over Fair Locks #
In this lecture, we will mainly talk about fair locks and non-fair locks, and why they are “non-fair”.
What are Fair and Non-Fair #
First, let’s take a look at what fair locks and non-fair locks are. A fair lock refers to the allocation of locks in the order of thread requests. On the other hand, a non-fair lock does not strictly adhere to the order of requests and allows for some instances of queue jumping. However, it’s important to note that “non-fair” here does not mean completely random. It doesn’t mean that threads can jump the queue whenever they want. Instead, they can only jump the queue at the “appropriate time”.
So when is the appropriate time? Suppose a thread requests a lock and coincidentally the previous thread holding the lock releases it at that moment. In this case, the current thread can skip the waiting threads and acquire the lock immediately. However, if the previous thread does not release the lock at that moment, the current thread will still enter the waiting queue.
To better understand fair locks and non-fair locks, let’s use an example from everyday life. Let’s say we are studying at school and queuing up at the cafeteria for lunch. I am the second person in line, with one person in front of me. However, at that moment, instead of thinking about lunch, I am deeply immersed in a math problem from the morning. So when it’s my turn after the person in front of me finishes getting their food, I’m still lost in thought and don’t realize it’s my turn. Suddenly, the person in front of me comes back and jumps the queue, saying, “Sorry, can you add a chicken leg for me, Auntie?”. This behavior can be compared to fair locks and non-fair locks.
By now, you may be wondering why the non-fair strategy is necessary, especially since it is the default strategy for ReentrantLock. If we don’t set it explicitly, it defaults to non-fair. Does this mean all the time I spent waiting in line was wasted? Why do others have priority over me? After all, fairness is a good thing, and unfairness is a bad thing.
Let’s consider a scenario: Thread A holds a lock and Thread B requests the same lock. Since Thread A already holds the lock, Thread B will have to wait. While waiting, Thread B will be blocked, meaning it will enter a blocked state. So when Thread A releases the lock, it is supposed to be Thread B’s turn to wake up and acquire the lock. However, if at this moment Thread C suddenly jumps the queue and requests the lock, according to the non-fair strategy, the lock will be given to Thread C. This is because waking up Thread B requires a significant overhead, and it is possible that before it is awakened, Thread C has already acquired and released the lock. Compared to the long process of waking up Thread B, the act of queue jumping allows Thread C to skip the blocking process. If the code executed by Thread C is not too lengthy, it can quickly complete its task and release the lock before Thread B is fully awakened. This is a win-win situation: Thread C’s efficiency is improved because it does not have to wait, and Thread B’s time to acquire the lock is not delayed because when it is awakened, Thread C has already released the lock. Since Thread C’s execution speed is faster than Thread B’s awakening speed, the Java designers chose to design non-fair locks in order to improve overall runtime efficiency.
Fair Scenario #
Next, let’s illustrate the scenarios of fairness and unfairness using diagrams. First, let’s look at the fair scenario. Suppose we create a fair lock and 4 threads request the lock in order. Thread 1 acquires the lock, and Threads 2, 3, and 4 start waiting in the queue. After Thread 1 releases the lock, Threads 2, 3, and 4 will take turns to acquire the lock. Thread 2 gets it first because it has been waiting the longest.
Non-Fair Scenario #
Now let’s look at the non-fair scenario. Suppose Thread 1 releases the lock and Thread 5 tries to acquire the lock at that moment. According to our non-fair strategy, Thread 5 can acquire the lock even though it has not entered the waiting queue, and Threads 2, 3, and 4 have been waiting longer than Thread 5. However, from an overall efficiency perspective, the lock is still given to Thread 5.
Code Example: Demonstrating the Effects of Fair and Non-Fair #
Now let’s use code to demonstrate the actual effects of fair and non-fair locks. Here is the code:
/**
* Description: Showcases fair locks and non-fair locks, where non-fair locks give priority to the thread holding the lock.
* Code borrowed from "Java Concurrency in Practice" by Brian Goetz et al.
*/
public class FairAndUnfair {
public static void main(String args[]) {
PrintQueue printQueue = new PrintQueue();
Thread thread[] = new Thread[10];
for (int i = 0; i < 10; i++) {
thread[i] = new Thread(new Job(printQueue), "Thread " + i);
}
for (int i = 0; i < 10; i++) {
thread[i].start();
}
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
class Job implements Runnable {
private PrintQueue printQueue;
public Job(PrintQueue printQueue) {
this.printQueue = printQueue;
}
@Override
public void run() {
System.out.printf("%s: Going to print a job\n", Thread.currentThread().getName());
printQueue.printJob(new Object());
System.out.printf("%s: The document has been printed\n", Thread.currentThread().getName());
}
}
class PrintQueue {
private final Lock queueLock = new ReentrantLock(false);
public void printJob(Object document) {
queueLock.lock();
try {
Long duration = (long) (Math.random() * 10000);
System.out.printf("%s: PrintQueue: Printing a Job during %d seconds\n",
Thread.currentThread().getName(), (duration / 1000));
Thread.sleep(duration);
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
queueLock.unlock();
}
queueLock.lock();
try {
Long duration = (long) (Math.random() * 10000);
System.out.printf("%s: PrintQueue: Printing a Job during %d seconds\n",
Thread.currentThread().getName(), (duration / 1000));
Thread.sleep(duration);
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
queueLock.unlock();
}
We can set a fair/non-fair lock by changing the parameter in new ReentrantLock(false). The output of the above code in the case of a fair lock is as follows:
Thread 0: Going to print a job
Thread 0: PrintQueue: Printing a Job during 5 seconds
Thread 1: Going to print a job
Thread 2: Going to print a job
Thread 3: Going to print a job
Thread 4: Going to print a job
Thread 5: Going to print a job
Thread 6: Going to print a job
Thread 7: Going to print a job
Thread 8: Going to print a job
Thread 9: Going to print a job
Thread 1: PrintQueue: Printing a Job during 3 seconds
Thread 2: PrintQueue: Printing a Job during 4 seconds
Thread 3: PrintQueue: Printing a Job during 3 seconds
Thread 4: PrintQueue: Printing a Job during 9 seconds
Thread 5: PrintQueue: Printing a Job during 5 seconds
Thread 6: PrintQueue: Printing a Job during 7 seconds
Thread 7: PrintQueue: Printing a Job during 3 seconds
Thread 8: PrintQueue: Printing a Job during 9 seconds
Thread 9: PrintQueue: Printing a Job during 5 seconds
Thread 0: PrintQueue: Printing a Job during 8 seconds
Thread 0: The document has been printed
Thread 1: PrintQueue: Printing a Job during 1 seconds
Thread 1: The document has been printed
Thread 2: PrintQueue: Printing a Job during 8 seconds
Thread 2: The document has been printed
Thread 3: PrintQueue: Printing a Job during 2 seconds
Thread 3: The document has been printed
Thread 4: PrintQueue: Printing a Job during 0 seconds
Thread 4: The document has been printed
Thread 5: PrintQueue: Printing a Job during 7 seconds
Thread 5: The document has been printed
Thread 6: PrintQueue: Printing a Job during 3 seconds
Thread 6: The document has been printed
Thread 7: PrintQueue: Printing a Job during 9 seconds
Thread 7: The document has been printed
Thread 8: PrintQueue: Printing a Job during 5 seconds
Thread 8: The document has been printed
Thread 9: PrintQueue: Printing a Job during 9 seconds
Thread 9: The document has been printed
It can be seen that in the case of fair mode, the order in which the threads acquire the lock is completely fair, with the first come first served rule.
In the above code, under unfair mode, the output is as follows:
Thread 0: Going to print a job
Thread 0: PrintQueue: Printing a Job during 6 seconds
Thread 1: Going to print a job
Thread 2: Going to print a job
Thread 3: Going to print a job
Thread 4: Going to print a job
Thread 5: Going to print a job
Thread 6: Going to print a job
Thread 7: Going to print a job
Thread 8: Going to print a job
Thread 9: Going to print a job
Thread 0: PrintQueue: Printing a Job during 8 seconds
Thread 0: The document has been printed
Thread 1: PrintQueue: Printing a Job during 9 seconds
Thread 1: PrintQueue: Printing a Job during 8 seconds
Thread 1: The document has been printed
Thread 2: PrintQueue: Printing a Job during 6 seconds
Thread 2: PrintQueue: Printing a Job during 4 seconds
Thread 2: The document has been printed
Thread 3: PrintQueue: Printing a Job during 9 seconds
Thread 3: PrintQueue: Printing a Job during 8 seconds
Thread 3: The document has been printed
Thread 4: PrintQueue: Printing a Job during 4 seconds
Thread 4: PrintQueue: Printing a Job during 2 seconds
Thread 4: The document has been printed
Thread 5: PrintQueue: Printing a Job during 2 seconds
Thread 5: PrintQueue: Printing a Job during 5 seconds
Thread 5: The document has been printed
Thread 6: PrintQueue: Printing a Job during 2 seconds
Thread 6: PrintQueue: Printing a Job during 6 seconds
Thread 6: The document has been printed
Thread 7: PrintQueue: Printing a Job during 6 seconds
Thread 7: PrintQueue: Printing a Job during 4 seconds
Thread 7: The document has been printed
Thread 8: PrintQueue: Printing a Job during 3 seconds
Thread 8: PrintQueue: Printing a Job during 6 seconds
Thread 8: The document has been printed
Thread 9: PrintQueue: Printing a Job during 3 seconds
Thread 9: PrintQueue: Printing a Job during 5 seconds
Thread 9: The document has been printed
It can be seen that in unfair mode, there is a phenomenon of “jumping the queue”, for example, Thread 0 can acquire the lock again after releasing it, even though Thread 1 ~ Thread 9 are already waiting in the queue.
Comparison of advantages and disadvantages of fair and unfair lock modes #
Next, let’s compare the advantages and disadvantages of fair and unfair lock modes, as shown in the table.
The advantage of fair mode is that each thread has an equal opportunity to execute after waiting for a certain period of time, while the disadvantage is that the overall execution speed is slower and the throughput is smaller. On the contrary, the advantage of unfair mode is that the overall execution speed is faster and the throughput is larger, but it may also cause thread starvation, which means that if threads keep jumping the queue, the threads in the waiting queue may not have a chance to run for a long time.
Source code analysis #
Next, let’s analyze the source code of fair and unfair locks to see how they are implemented. We can see that the ReentrantLock class contains a Sync class, which inherits from AQS (AbstractQueuedSynchronizer), as shown in the following code:
public class ReentrantLock implements Lock, java.io.Serializable {
private static final long serialVersionUID = 7373984872572414699L;
/** Synchronizer providing all implementation mechanics */
private final Sync sync;
The code of the Sync class is as follows:
abstract static class Sync extends AbstractQueuedSynchronizer {...}
According to the code, Sync has two subclasses: FairSync for fair locks and NonfairSync for unfair locks, as shown below:
static final class NonfairSync extends Sync {...}
static final class FairSync extends Sync {...}
Next, let’s take a look at the source code of the lock acquisition methods for fair and unfair locks.
The lock acquisition source code for fair locks is as follows:
protected final boolean tryAcquire(int acquires) {
final Thread current = Thread.currentThread();
int c = getState();
if (c == 0) {
if (!hasQueuedPredecessors() && // This checks hasQueuedPredecessors()
compareAndSetState(0, acquires)) {
setExclusiveOwnerThread(current);
return true;
}
} else if (current == getExclusiveOwnerThread()) {
int nextc = c + acquires;
if (nextc < 0) {
throw new Error("Maximum lock count exceeded");
}
setState(nextc);
return true;
}
return false;
}
The lock acquisition source code for unfair locks is as follows:
final boolean nonfairTryAcquire(int acquires) {
final Thread current = Thread.currentThread();
int c = getState();
if (c == 0) {
if (compareAndSetState(0, acquires)) { // This does not check hasQueuedPredecessors()
setExclusiveOwnerThread(current);
return true;
}
} else if (current == getExclusiveOwnerThread()) {
int nextc = c + acquires;
if (nextc < 0) // overflow
throw new Error("Maximum lock count exceeded");
setState(nextc);
return true;
}
return false;
}
By comparing the code, we can clearly see that the only difference between fair and unfair locks in the lock() method is that fair locks have an additional condition: hasQueuedPredecessors() is false. This method checks whether there are threads already waiting in the queue. This is also the core difference between fair and unfair locks. If it is a fair lock, once there are threads already waiting in the queue, the current thread will not attempt to acquire the lock. In contrast, for unfair locks, regardless of whether there are threads already waiting in the queue, the current thread will attempt to acquire the lock and only join the queue if it fails to acquire the lock.
There is a special case that we need to pay attention to. For the tryLock() method, it does not follow the set fairness rule.
For example, when a thread is executing the tryLock() method, once another thread releases the lock, the thread currently trying to lock can acquire the lock, even in fair mode and even if there are other threads already waiting in the queue. In simpler terms, tryLock can jump the queue.
If we look at its source code, we will find:
public boolean tryLock() {
return sync.nonfairTryAcquire(1);
}
It calls nonfairTryAcquire(), indicating that it is unfair and is not related to whether the lock itself is in fair mode.
To sum up, fair locks acquire locks in the order in which multiple threads request locks, thereby achieving fairness. Unfair locks do not consider the waiting queue and directly attempt to acquire the lock, so it is possible for a later thread to acquire the lock first, but it also improves overall efficiency.