📖 File 09: Read-Write Locks — `shared_mutex`, `shared_lock` vs `unique_lock`

From your actual interview: "We will Acquire a Read Write lock for Parent Nodes which will allow multiple reads and single write."

📖 What is a Read-Write Lock? (Simple Explanation)

A Read-Write Lock allows:

Multiple readers at the same time (they don't modify anything, so they can't conflict)
Only ONE writer at a time (and NO readers while writing)

Analogy: A Wikipedia article.

Many people can READ the article simultaneously → no problem
Only ONE editor can WRITE at a time → must lock others out
While someone is editing, readers must wait for the edit to finish

Why It's Better Than a Plain Mutex for Our Tree:

With plain mutex on Asia:
  Thread 1: lock(China) → needs to CHECK if Asia is locked → needs Asia's mutex
  Thread 2: lock(India) → needs to CHECK if Asia is locked → needs Asia's mutex
  → Thread 2 WAITS for Thread 1, even though BOTH are just READING Asia's state!

With Read-Write Lock on Asia:
  Thread 1: lock(China) → SHARED READ LOCK on Asia → reads Asia's state
  Thread 2: lock(India) → SHARED READ LOCK on Asia → reads Asia's state
  → Both proceed simultaneously! ✅
  Thread 3: lock(Asia)  → EXCLUSIVE WRITE LOCK → must wait for readers to finish

🔧 How Read-Write Locks Work Internally

┌──────────────────────────────────────────────────┐
│              Read-Write Lock State               │
│                                                  │
│  ┌──────────────┐   ┌──────────────────┐         │
│  │ reader_count │   │ writer_active    │         │
│  │ (int)        │   │ (bool)           │         │
│  └──────────────┘   └──────────────────┘         │
│                                                  │
│  shared_lock (READ):                             │
│    if writer_active == false:                    │
│        reader_count++                            │
│        ALLOWED ✅ (multiple readers OK)           │
│    else:                                         │
│        BLOCK ❌ (writer is active)                │
│                                                  │
│  unique_lock (WRITE):                            │
│    if reader_count == 0 && writer_active == false:│
│        writer_active = true                      │
│        ALLOWED ✅ (exclusive access)              │
│    else:                                         │
│        BLOCK ❌ (readers or another writer active) │
│                                                  │
└──────────────────────────────────────────────────┘

Compatibility Matrix:

	Read held	Write held
Read request	✅ Allowed	❌ Blocked
Write request	❌ Blocked	❌ Blocked

💻 C++ Implementation

Using `std::shared_mutex` (C++17):

#include <shared_mutex>

std::shared_mutex rwLock;

// READER (shared access — multiple threads can do this simultaneously)
{
    std::shared_lock<std::shared_mutex> readLock(rwLock);
    // Read shared data here
    // Multiple threads can be here at the same time
}

// WRITER (exclusive access — only one thread)
{
    std::unique_lock<std::shared_mutex> writeLock(rwLock);
    // Modify shared data here
    // No other thread (reader OR writer) can be here
}

Key Types:

Type	Lock Mode	Purpose
`std::shared_lock<shared_mutex>`	READ (shared)	Multiple threads can hold simultaneously
`std::unique_lock<shared_mutex>`	WRITE (exclusive)	Only one thread, no readers allowed

☕ Java Implementation

Using `ReentrantReadWriteLock`:

import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

ReadWriteLock rwLock = new ReentrantReadWriteLock();

// READER
rwLock.readLock().lock();
try {
    // Read shared data
} finally {
    rwLock.readLock().unlock();
}

// WRITER
rwLock.writeLock().lock();
try {
    // Modify shared data
} finally {
    rwLock.writeLock().unlock();
}

🌳 Tree of Space with Read-Write Locks

The Insight from Your Interview:

When locking node X:

We need WRITE access to node X (we're modifying its lockedBy and propagating up)
We need READ access to ancestor nodes (we're only CHECKING if they're locked)

#include <shared_mutex>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <string>

using namespace std;

// Each node has its own read-write lock
vector<shared_mutex> nodeRWLock;
vector<int> locked;
vector<int> par;
vector<unordered_set<int>> lockedDesc;
unordered_map<string, int> nameMap;

bool lockWithRWLock(const string& name, int uid) {
    int node = nameMap[name];
    
    // Step 1: Acquire WRITE lock on the target node
    unique_lock<shared_mutex> writeLock(nodeRWLock[node]);
    
    // Step 2: Check self
    if (locked[node] != -1) return false;
    if (!lockedDesc[node].empty()) return false;
    
    // Step 3: Acquire READ locks on ancestors (leaf to root)
    // Note: We need to hold the write lock on our node while reading ancestors
    vector<shared_lock<shared_mutex>> readLocks;
    int cur = par[node];
    while (cur != -1) {
        readLocks.emplace_back(nodeRWLock[cur]);
        if (locked[cur] != -1) return false;
        cur = par[cur];
    }
    
    // Step 4: All checks pass — lock the node
    locked[node] = uid;
    
    // Step 5: Propagate up — we need WRITE access to ancestor's sets!
    // ⚠️ PROBLEM: We hold READ locks on ancestors but need to WRITE!
    // Option A: Upgrade read→write (not supported in std::shared_mutex)
    // Option B: Release read locks, re-acquire as write locks
    // Option C: Use a separate mutex just for the lockedDesc set
    
    // For simplicity, use a separate per-node mutex for set modification:
    // (In practice, you'd design this more carefully)
    cur = par[node];
    for (auto& rlock : readLocks) {
        rlock.unlock();  // Release read locks
    }
    readLocks.clear();
    
    cur = par[node];
    while (cur != -1) {
        unique_lock<shared_mutex> ancestorWrite(nodeRWLock[cur]);
        lockedDesc[cur].insert(node);
        cur = par[cur];
    }
    
    return true;
    // writeLock on node auto-releases
}

⚠️ The Read-to-Write Upgrade Problem

In the code above, there's a subtle issue:

We take READ lock on ancestor Asia to CHECK if it's locked → OK
We need to INSERT into Asia's lockedDescendants set → need WRITE lock
We can't upgrade a shared_lock to unique_lock in C++!
If we release the read lock and re-acquire as write → 
   TOCTOU gap (Asia might get locked between release and reacquire)

Cleaner Solution: Hybrid Approach

bool lockHybrid(const string& name, int uid) {
    int node = nameMap[name];
    
    // Gather path
    vector<int> path;
    int cur = node;
    while (cur != -1) {
        path.push_back(cur);
        cur = par[cur];
    }
    
    // Acquire WRITE lock on target, READ locks on ancestors
    // Target node (path[0]) → write lock
    unique_lock<shared_mutex> targetLock(nodeRWLock[path[0]]);
    
    // Ancestors → read locks
    vector<shared_lock<shared_mutex>> ancestorLocks;
    for (int i = 1; i < (int)path.size(); i++) {
        ancestorLocks.emplace_back(nodeRWLock[path[i]]);
    }
    
    // Check self
    if (locked[node] != -1) return false;
    if (!lockedDesc[node].empty()) return false;
    
    // Check ancestors (all read-locked, safe to read)
    for (int i = 1; i < (int)path.size(); i++) {
        if (locked[path[i]] != -1) return false;
    }
    
    // All pass — mark node as locked
    locked[node] = uid;
    
    // Release all locks
    ancestorLocks.clear();
    targetLock.unlock();
    
    // Now propagate UP with write locks (separate phase)
    // This creates a brief window — acceptable trade-off for parallelism
    cur = par[node];
    while (cur != -1) {
        unique_lock<shared_mutex> wl(nodeRWLock[cur]);
        lockedDesc[cur].insert(node);
        cur = par[cur];
    }
    
    return true;
}

🆚 When to Use Read-Write Locks vs Plain Mutex

Scenario	Read-Write Lock	Plain Mutex
Many readers, few writers	✅ Better	❌ Over-locks
Mostly writes	❌ Extra overhead	✅ Simpler
Short critical sections	Either works	✅ Simpler
Tree ancestor checks	✅ Multiple threads can check	❌ Serialize checks

For Tree of Space:

Ancestor checks (reading locked[ancestor]) = READ operation → shared lock OK
Locking a node (writing locked[node] = uid) = WRITE operation → exclusive lock needed
Propagating up (inserting into lockedDesc) = WRITE operation → needs upgrade

☕ Java Version with `ReentrantReadWriteLock`

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

class Node {
    String name;
    int lockedBy = -1;
    Node parent;
    List<Node> children = new ArrayList<>();
    Set<Node> lockedDescendants = new HashSet<>();
    ReadWriteLock rwLock = new ReentrantReadWriteLock();
    
    Node(String name, Node parent) {
        this.name = name;
        this.parent = parent;
    }
}

class TreeOfSpace {
    Map<String, Node> nodeMap = new HashMap<>();
    
    boolean lock(String name, int uid) {
        Node node = nodeMap.get(name);
        
        // Write lock on target
        node.rwLock.writeLock().lock();
        
        // Read locks on ancestors
        List<Node> ancestors = new ArrayList<>();
        Node cur = node.parent;
        while (cur != null) {
            cur.rwLock.readLock().lock();
            ancestors.add(cur);
            cur = cur.parent;
        }
        
        try {
            if (node.lockedBy != -1) return false;
            if (!node.lockedDescendants.isEmpty()) return false;
            
            for (Node anc : ancestors) {
                if (anc.lockedBy != -1) return false;
            }
            
            node.lockedBy = uid;
            return true;
            
        } finally {
            // Release all locks
            for (Node anc : ancestors) {
                anc.rwLock.readLock().unlock();
            }
            node.rwLock.writeLock().unlock();
            
            // If successful, propagate (with write locks)
            // (handled separately to avoid holding all locks)
        }
    }
}

📝 What to Say to the Interviewer

"I can improve parallelism using read-write locks. When Thread 1 locks China and Thread 2 locks India, both need to CHECK if their common ancestor Asia is locked. With a plain mutex, one thread blocks the other. With a read-write lock, both acquire SHARED READ locks on Asia simultaneously — they're both just reading, so there's no conflict.

The target node gets an EXCLUSIVE WRITE lock (since we're modifying its state). Ancestors get SHARED READ locks for checking. For propagating up (inserting into ancestor sets), we need to upgrade to write locks — this is the tricky part since C++'s shared_mutex doesn't support atomic upgrade.

The trade-off: better parallelism for ancestor checks, but more complexity in the propagation phase."

09_read_write_locks.md

📖 File 09: Read-Write Locks — shared_mutex, shared_lock vs unique_lock

📖 What is a Read-Write Lock? (Simple Explanation)

Why It's Better Than a Plain Mutex for Our Tree:

🔧 How Read-Write Locks Work Internally

Compatibility Matrix:

💻 C++ Implementation

Using std::shared_mutex (C++17):

Key Types:

☕ Java Implementation

Using ReentrantReadWriteLock:

🌳 Tree of Space with Read-Write Locks

The Insight from Your Interview:

⚠️ The Read-to-Write Upgrade Problem

Cleaner Solution: Hybrid Approach

🆚 When to Use Read-Write Locks vs Plain Mutex

For Tree of Space:

☕ Java Version with ReentrantReadWriteLock

📝 What to Say to the Interviewer

📖 File 09: Read-Write Locks — `shared_mutex`, `shared_lock` vs `unique_lock`

Using `std::shared_mutex` (C++17):

Using `ReentrantReadWriteLock`:

☕ Java Version with `ReentrantReadWriteLock`