Since the execution process of threads is inherently unpredictable, synchronization mechanisms are essential to coordinate access to the mutable state of objects. Without proper synchronization, race conditions and data inconsistency can occur when multiple threads attempt to modify shared resources simultaneously.

Classification of Locks in Java

Java provides two primary categories of locks: explicit locks and implicit locks.

• Explicit Locks: Require manual management by the developer. For instance, ReentrantLock necessitates explicit calls to lock() and unlock() methods.
• Implicit Locks: Managed automatically by the JVM. The synchronized keyword serves as an implicit lock, where the JVM handles the acquisition and release of the monitor lock.

The Synchronized Keyword

Every object created in Java has an associated Monitor (monitor lock). Its implementation relies on the underlying operating system's Mutex Lock, making it a heavyweight lock by nature. However, starting from Java 1.6, the JVM introduced several optimizations for built-in locks, including lock coarsening, lock elimination, biased locking, lightweight locking, and adaptive spinning.

When compiled into bytecode, the synchronized keyword translates to monitorenter and monitorexit instructions, which handle the acquisition and release of the monitor lock respectively.

How Objects Store Lock Status

Lock status information is stored in the object header, specifically within the Mark Word. Understanding the memory layout of an object is crucial to grasping how locking works at a low level.

Object Memory Layout in HotSpot

In the HotSpot virtual machine, the memory layout of an object consists of three distinct regions:

• Object Header (Header): Contains metadata such as the hash code, generational age, lock status, biased lock thread ID, and the length of the array (if the object is an array).
• Instance Data (Instance Data): Holds the actual data of the object, including member variables and references.
• Padding (Padding): Ensures the total size of the object is a multiple of 8 bytes for alignment purposes.

AbstractQueuedSynchronizer (AQS) Core Features

AQS serves as the foundation for building locks and synchronization containers in the java.util.concurrent package. Its primary characteristics include:

• Blocking wait queue management
• Support for both fair and unfair acquisition modes
• Reentrant locking capabilities
• Shared and exclusive lock modes
• Interruptibility support

Synchronizers such as ReentrantLock, CountDownLatch, and CyclicBarrier are built upon the AQS framework. Typically, these implementations define an internal class that extends AQS and map all synchronization operations to the corresponding methods.

Fair vs Non-Fair Lock Implementation

The difference between fair and non-fair locks lies in the order of lock acquisition when a lock is released. Below is an example of a non-fair lock implementation:

static final class NonfairSync extends Sync {
    
    final void lock() {
        // Non-fair: attempt to acquire immediately
        if (compareAndSetState(0, 1)) {
            setExclusiveOwnerThread(Thread.currentThread());
        } else {
            acquire(1);
        }
    }

    protected final boolean tryAcquire(int acquires) {
        return nonfairTryAcquire(acquires);
    }
}

In contrast, a fair lock ensures that threads acquire the lock in the order they requested it:

static final class FairSync extends Sync {
    
    final void lock() {
        acquire(1);
    }

    protected final boolean tryAcquire(int acquires) {
        Thread currentThread = Thread.currentThread();
        int currentState = getState();
        if (currentState == 0) {
            // Fair: check if there are other waiting threads first
            if (!hasQueuedPredecessors() && compareAndSetState(0, acquires)) {
                setExclusiveOwnerThread(currentThread);
                return true;
            }
        } else if (currentThread == getExclusiveOwnerThread()) {
            int newState = currentState + acquires;
            if (newState < 0) {
                throw new Error("Maximum lock count exceeded");
            }
            setState(newState);
            return true;
        }
        return false;
    }
}

State Variable and Reentrancy

The state variable is central to AQS. When state is 0, the lock is available. A successful lock acquisition changes state to 1 via a CAS operatino. For reentrant locks, each subsequent acquisition by the same thread increments state, while each release decrements it. Only when state returns to 0 does the lock become available for other threads.

Acquisition Flow

public final void acquire(int arg) {
    if (!tryAcquire(arg) && 
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) {
        selfInterrupt();
    }
}

The acquisition process follows these steps:

1. tryAcquire(arg): Attempts to acquire the lock and update the state. If unsuccessful, the lock is held by another thread.
2. addWaiter(Node.EXCLUSIVE): Creates a node and adds it to the wait queue (a doubly linked list) in exclusive mode.
3. acquireQueued(): The node attempts to acquire the lock. If the predecessor node is the head, the current node becomes the new head upon success. Otherwise, the thread is parked.

Release Flow

public final boolean release(int arg) {
    if (tryRelease(arg)) {
        Node headNode = head;
        if (headNode != null && headNode.waitStatus != 0) {
            unparkSuccessor(headNode);
        }
        return true;
    }
    return false;
}

During release, the state is decremented. When state reaches 0, the exclusiveOwnerThread is set to null, and the successor node in the queue is unparked.

BlockingQueue Implementation Analysis

ArrayBlockingQueue demonstrates why AQS requires both a synchronization queue and a condition queue. Here is the constructor:

public ArrayBlockingQueue(int capacity, boolean fair) {
    if (capacity <= 0) {
        throw new IllegalArgumentException();
    }
    this.items = new Object[capacity];
    lock = new ReentrantLock(fair);
    notEmpty = lock.newCondition();
    notFull = lock.newCondition();
}

The implementation uses a ReentrantLock and two condition queues (Condition objects) to manage full and empty states.

Put Operation

public void put(E element) throws InterruptedException {
    Objects.requireNonNull(element);
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        while (count == items.length) {
            notFull.await();
        }
        enqueue(element);
    } finally {
        lock.unlock();
    }
}

When the queue is full, the current thread is blocked via await().

Condition Queue - await() Method

public final void await() throws InterruptedException {
    if (Thread.interrupted()) {
        throw new InterruptedException();
    }
    Node waitNode = addConditionWaiter();
    int savedState = fullyRelease(waitNode);
    int interruptMode = 0;
    while (!isOnSyncQueue(waitNode)) {
        LockSupport.park(this);
        if ((interruptMode = checkInterruptWhileWaiting(waitNode)) != 0) {
            break;
        }
    }
    if (acquireQueued(waitNode, savedState) && interruptMode != THROW_IE) {
        interruptMode = REINTERRUPT;
    }
    if (waitNode.nextWaiter != null) {
        unlinkCancelledWaiters();
    }
    if (interruptMode != 0) {
        reportInterruptAfterWait(interruptMode);
    }
}

Key steps in the await() method:

• addConditionWaiter(): Adds the current thread to the condition queue.
• fullyRelease(): Releases the held lock completely and wakes up the head node of the sync queue.
• isOnSyncQueue(): Checks if the node has been transferred to the synchronization queue.
• acquireQueued(): Attempts to re-acquire the lock after being signaled.

Take Oepration

public E take() throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        while (count == 0) {
            notEmpty.await();
        }
        return dequeue();
    } finally {
        lock.unlock();
    }
}

The take() method blocks when the queue is empty and waits for the notEmpty condition to be signaled, transferring the node to the synchronization queue for lock re-acquisition.