☕ File 04: Java `synchronized` Keyword & `ReentrantLock`

The Java-specific thread safety primitives. Every Java candidate MUST know these.

📖 What is `synchronized`? (Simple Explanation)

synchronized is Java's built-in mutex. It's the simplest way to make code thread-safe.

Analogy: Every Java object has an invisible "meeting room" attached to it. synchronized means "only one person can be in this meeting room at a time." The meeting room has a door with a lock, and the key is called a monitor.

// When Thread A enters this block, it grabs the key (monitor).
// Thread B tries to enter → the door is locked → Thread B waits.
// Thread A exits → drops the key → Thread B picks it up and enters.
synchronized (someObject) {
    // Only ONE thread can be here at a time
    // This is the "critical section"
}

🔬 How Does `synchronized` Work Internally?

The Monitor (Object Header)

Every Java object has a hidden structure called the object header. Part of this header is the mark word, which stores lock information.

┌─────────────────────────────────────────────┐
│           Java Object in Memory             │
│                                             │
│  ┌─────────────────────────────────┐        │
│  │       Mark Word (64 bits)       │        │
│  │  Contains:                      │        │
│  │  - Lock state (biased/thin/fat) │        │
│  │  - Thread ID of lock owner      │        │
│  │  - Hash code                    │        │
│  │  - GC age                       │        │
│  └─────────────────────────────────┘        │
│  ┌─────────────────────────────────┐        │
│  │     Class Pointer (Klass*)      │        │
│  └─────────────────────────────────┘        │
│  ┌─────────────────────────────────┐        │
│  │        Instance Fields          │        │
│  └─────────────────────────────────┘        │
└─────────────────────────────────────────────┘

Lock Escalation (The JVM's Optimization Strategy)

The JVM doesn't immediately use a heavy OS lock. It escalates through increasingly expensive mechanisms:

┌──────────────┐     ┌──────────────┐     ┌──────────────┐
│   Biased     │ →   │  Thin Lock   │ →   │  Fat Lock    │
│   Locking    │     │  (CAS-based) │     │  (OS Mutex)  │
│              │     │              │     │              │
│  0 contention│     │  Light       │     │  Heavy       │
│  ~0 ns       │     │  contention  │     │  contention  │
│              │     │  ~10-20 ns   │     │  ~3000 ns    │
└──────────────┘     └──────────────┘     └──────────────┘

Stage 1: Biased Locking (No Contention)

If only ONE thread ever accesses the object, the JVM "biases" the lock to that thread
The thread ID is stored in the mark word
Subsequent lock/unlock by the SAME thread = zero overhead (just check thread ID)
Cost: ~0 nanoseconds

Stage 2: Thin Lock / Lightweight Lock (Light Contention)

If a second thread tries to acquire → bias is revoked
JVM uses a CAS (compare-and-swap) on the mark word to claim the lock
The waiting thread spins briefly (user-space, no OS call)
Cost: ~10-20 nanoseconds

Stage 3: Fat Lock / Heavyweight Monitor (Heavy Contention)

If spinning fails (another thread holds the lock for too long)
JVM creates an OS-level monitor (similar to a futex)
Waiting thread is put to sleep by the OS
Cost: ~1000-5000 nanoseconds (context switch!)

💻 Using `synchronized` for Tree of Space

Method 1: Synchronized Method (❌ Too Coarse)

class TreeOfSpace {
    // This locks the ENTIRE TreeOfSpace object for EVERY call
    // → All threads serialize. Parallelism = 0.
    public synchronized boolean lock(String name, int uid) {
        // ... all checks and updates ...
    }
}

Problem: synchronized on a method uses this as the monitor. Only one thread can call lock() at a time, even if they're locking completely independent nodes.

Method 2: Synchronized Block on Shared Object (❌ Still Too Coarse)

class TreeOfSpace {
    private final Object treeLock = new Object();
    
    public boolean lock(String name, int uid) {
        synchronized (treeLock) {
            // Still serializes everything!
        }
    }
}

Method 3: Per-Node Synchronized (✅ Fine-Grained)

import java.util.*;

class Node {
    String name;
    int lockedBy = -1;
    Node parent;
    List<Node> children = new ArrayList<>();
    Set<Node> lockedDescendants = new HashSet<>();
    
    // Each node IS its own monitor object
    // synchronized(node) locks THIS specific node
    
    Node(String name, Node parent) {
        this.name = name;
        this.parent = parent;
    }
}

class TreeOfSpace {
    Map<String, Node> nodeMap = new HashMap<>();
    Node root;
    
    // Build tree... (same as before)
    
    public boolean lock(String name, int uid) {
        Node node = nodeMap.get(name);
        if (node == null) return false;
        
        // Step 1: Gather path from node to root
        List<Node> path = new ArrayList<>();
        Node cur = node;
        while (cur != null) {
            path.add(cur);
            cur = cur.parent;
        }
        
        // Step 2: Acquire synchronized locks in LEAF-TO-ROOT order
        // We use nested synchronized blocks
        // Java guarantees: if a thread already holds a monitor, 
        // it can enter the same synchronized block again (REENTRANT)
        return lockHelper(path, 0, node, uid);
    }
    
    // Recursive helper to acquire locks one by one
    private boolean lockHelper(List<Node> path, int index, 
                               Node target, int uid) {
        if (index == path.size()) {
            // All locks acquired — perform checks
            return performLockChecks(target, uid, path);
        }
        
        synchronized (path.get(index)) {
            // Lock this node's monitor, then proceed to next
            return lockHelper(path, index + 1, target, uid);
        }
        // Lock auto-releases when synchronized block exits
    }
    
    private boolean performLockChecks(Node target, int uid, 
                                       List<Node> path) {
        // Check 1: Node already locked?
        if (target.lockedBy != -1) return false;
        
        // Check 2: Any descendant locked?
        if (!target.lockedDescendants.isEmpty()) return false;
        
        // Check 3: Any ancestor locked?
        for (int i = 1; i < path.size(); i++) {
            if (path.get(i).lockedBy != -1) return false;
        }
        
        // All pass — lock it
        target.lockedBy = uid;
        for (int i = 1; i < path.size(); i++) {
            path.get(i).lockedDescendants.add(target);
        }
        return true;
    }
}

🔐 `ReentrantLock` — The Advanced Alternative

ReentrantLock is like synchronized but with superpowers:

Feature	`synchronized`	`ReentrantLock`
Automatic release	✅ (exits block)	❌ (must call `unlock()` in `finally`)
Try-lock (non-blocking)	❌	✅ `tryLock()`
Timed lock	❌	✅ `tryLock(5, TimeUnit.SECONDS)`
Interruptible wait	❌	✅ `lockInterruptibly()`
Fair ordering	❌	✅ `new ReentrantLock(true)`
Condition variables	Only `wait()/notify()`	✅ `newCondition()`

What Does "Reentrant" Mean?

A reentrant lock allows the same thread to acquire the lock multiple times without deadlocking itself.

ReentrantLock lock = new ReentrantLock();

void methodA() {
    lock.lock();
    try {
        methodB();  // This would DEADLOCK with a non-reentrant lock!
    } finally {
        lock.unlock();
    }
}

void methodB() {
    lock.lock();      // Same thread already holds the lock → allowed (reentrant)
    try {             // Internal counter: 2 (locked twice)
        // ...
    } finally {
        lock.unlock(); // Counter: 1 (still locked once)
    }
}

synchronized is also reentrant! A thread can enter multiple synchronized blocks on the same object.

Tree of Space with `ReentrantLock`:

import java.util.*;
import java.util.concurrent.locks.ReentrantLock;

class Node {
    String name;
    int lockedBy = -1;
    Node parent;
    List<Node> children = new ArrayList<>();
    Set<Node> lockedDescendants = new HashSet<>();
    ReentrantLock nodeLock = new ReentrantLock();  // Each node has its own lock
    
    Node(String name, Node parent) {
        this.name = name;
        this.parent = parent;
    }
}

class TreeOfSpace {
    Map<String, Node> nodeMap = new HashMap<>();
    
    public boolean lock(String name, int uid) {
        Node node = nodeMap.get(name);
        if (node == null) return false;
        
        // Gather path
        List<Node> path = new ArrayList<>();
        Node cur = node;
        while (cur != null) {
            path.add(cur);
            cur = cur.parent;
        }
        
        // Acquire ReentrantLocks in leaf-to-root order
        for (Node n : path) {
            n.nodeLock.lock();
        }
        
        try {
            // Critical section
            if (node.lockedBy != -1) return false;
            if (!node.lockedDescendants.isEmpty()) return false;
            
            for (int i = 1; i < path.size(); i++) {
                if (path.get(i).lockedBy != -1) return false;
            }
            
            // Lock the node
            node.lockedBy = uid;
            for (int i = 1; i < path.size(); i++) {
                path.get(i).lockedDescendants.add(node);
            }
            return true;
            
        } finally {
            // ALWAYS release in finally block!
            // Release in REVERSE order (root to leaf)
            for (int i = path.size() - 1; i >= 0; i--) {
                path.get(i).nodeLock.unlock();
            }
        }
    }
}

⚡ `volatile` in Java vs C++ (Critical Interview Point!)

Java `volatile`:

volatile boolean isLocked = false;

Guarantees visibility: When Thread A writes true, Thread B will see it
Provides happens-before: All writes before the volatile write are visible to any thread that reads the volatile variable
Does NOT guarantee atomicity of compound operations (x++ is still unsafe with volatile!)
Prevents instruction reordering around volatile reads/writes

C/C++ `volatile`:

volatile bool isLocked = false;

Only prevents compiler optimization (no register caching)
Does NOT guarantee visibility across CPU cores
Does NOT emit memory fences
Much weaker than Java volatile

When to Use Java `volatile`:

// ✅ Good: simple flag read by another thread
volatile boolean stopFlag = false;

// Thread 1:
stopFlag = true;  // atomic write (single variable)

// Thread 2:
while (!stopFlag) { /* work */ }  // will see the update

// ❌ Bad: compound operation
volatile int count = 0;
count++;  // NOT thread-safe! Still read-modify-write

📝 What to Say to the Interviewer

"In Java, synchronized is the built-in mutex mechanism. Every object has a monitor — when a thread enters a synchronized block, it acquires that monitor. The JVM optimizes this through lock escalation: biased locking (no contention, ~0 ns), thin lock with CAS (~10 ns), and fat lock with OS mutex (~3000 ns).

For the tree problem, I'd give each node its own monitor. I acquire synchronized blocks from leaf to root to prevent deadlocks. Siblings in different subtrees don't contend — their paths only overlap at common ancestors.

If I need more control (try-lock, timeouts, fairness), I'd use ReentrantLock instead. It's explicit lock/unlock with try-finally for safety."

04_synchronized_keyword.md

☕ File 04: Java synchronized Keyword & ReentrantLock

📖 What is synchronized? (Simple Explanation)

🔬 How Does synchronized Work Internally?