🚦 File 05: Semaphores — Binary, Counting, and Why Counting Can't Work Here

📖 What is a Semaphore? (Formal Interview Definition)

What to say directly in the interview: "A Semaphore is a synchronization primitive introduced by Edsger Dijkstra to regulate concurrent access to shared resources across multiple threads. Internally, it encapsulates a non-negative integer counter (permits) and a thread wait queue.

It exposes exactly two atomic operations:

wait() (traditionally P() from Dutch proberen 'to test', or acquire()): Atomically decrements the permit counter. If permits > 0, the thread proceeds immediately. If permits == 0, the thread is suspended and enqueued in the wait queue.

signal() (traditionally V() from Dutch verhogen 'to increment', or release()): Atomically increments the permit counter and wakes up a suspended thread from the wait queue.

Crucially, a semaphore is a signaling mechanism that lacks ownership semantics—meaning ANY thread can call release(), even if it never called acquire()."

The Two Types of Semaphores:

Counting Semaphore (Capacity = N, where N > 1):
- Manages access to a pool of $N$ identical resources (e.g., database connection pools, thread pools, throttling concurrent API requests).
- Allows up to $N$ threads into the critical region concurrently.
Binary Semaphore (Capacity = 1, Value ∈ {0, 1}):
- Counter can only be 0 or 1.
- Used for mutual exclusion or signaling completion between two threads.
- Difference from Mutex: Mutex enforces strict thread ownership (only locker can unlock); binary semaphore has no ownership (Thread A can wait, Thread B can signal).

Intuitive Analogy (The Parking Lot)

Think of a Semaphore as an automated parking garage:

Counting Semaphore (capacity = N): A parking lot with $N$ total stalls. Up to $N$ cars park freely. The $(N+1)^{\text{th}}$ car waits at the entry gate until any car exits.
Binary Semaphore (capacity = 1): A single parking spot. Only 1 car can occupy it.

The Internal Counter Trace:

Semaphore(3):  counter = 3  (3 permits available)

Thread A calls acquire():  counter = 2  (Thread A proceeds)
Thread B calls acquire():  counter = 1  (Thread B proceeds)
Thread C calls acquire():  counter = 0  (Thread C proceeds)
Thread D calls acquire():  counter = 0  → Thread D BLOCKS (added to wait queue)

Thread A calls release():  counter = 1  → Thread D WAKES UP, acquires permit (counter = 0)

🔬 How Does a Semaphore Work Internally?

Internal Structure:

┌──────────────────────────────────────────┐
│              Semaphore                   │
│                                          │
│  ┌──────────────┐                        │
│  │ permits (int)│  ← counter of spots    │
│  └──────────────┘                        │
│  ┌──────────────────┐                    │
│  │ wait queue (FIFO)│  ← sleeping threads│
│  └──────────────────┘                    │
│                                          │
│  acquire() / wait() / P():               │
│    if permits > 0:                       │
│        permits--           (decrement)   │
│        return              (proceed)     │
│    else:                                 │
│        add thread to wait queue          │
│        thread.sleep()      (block)       │
│                                          │
│  release() / signal() / V():             │
│    permits++               (increment)   │
│    if wait queue not empty:              │
│        wake up first thread              │
│                                          │
└──────────────────────────────────────────┘

OS-Level Implementation:

acquire() uses a system call if blocking is needed → same futex/kernel overhead as mutex
The counter modification itself uses an atomic operation (CAS or similar)
The wait queue is managed by the OS kernel

🆚 Semaphore vs Mutex — The Critical Differences

Feature	Mutex	Binary Semaphore
Ownership	✅ Only the locking thread can unlock	❌ ANY thread can release
Purpose	Protect a critical section	Signal between threads
Count	Always 0 or 1	Always 0 or 1 (for binary)
Priority Inheritance	✅ OS can boost low-priority holder	❌ No
Can Thread B release Thread A's lock?	❌ No (undefined behavior)	✅ Yes!

Why the Ownership Difference Matters:

// WITH MUTEX (correct behavior):
Thread A: mutex.lock()
Thread B: mutex.unlock()  // ❌ EXCEPTION! Only A can unlock.

// WITH BINARY SEMAPHORE (dangerous):
Thread A: semaphore.acquire()
Thread B: semaphore.release()  // ✅ Allowed! But now the critical 
                                //    section is "unlocked" even though
                                //    A is still inside it!

In the Tree of Space problem: If Thread B could accidentally release a lock that Thread A holds on a node, the entire tree invariant breaks. This is why mutexes are preferred over binary semaphores.

💻 Java Semaphore Code

import java.util.concurrent.Semaphore;

// === BINARY SEMAPHORE (permits = 1) ===
Semaphore binarySem = new Semaphore(1);

// Acquire (like mutex.lock())
binarySem.acquire();     // If permits == 0 → blocks
// ... critical section ...
binarySem.release();     // Increment permits

// Non-blocking try:
if (binarySem.tryAcquire()) {
    try {
        // got the permit
    } finally {
        binarySem.release();
    }
}

// === COUNTING SEMAPHORE (permits = 5) ===
Semaphore pool = new Semaphore(5);  // e.g., 5 database connections

// Up to 5 threads can proceed simultaneously:
pool.acquire();
try {
    // use one connection
} finally {
    pool.release();
}

C++ Semaphore (C++20):

#include <semaphore>

// Binary semaphore
std::binary_semaphore bsem{1};
bsem.acquire();
// ... critical section ...
bsem.release();

// Counting semaphore
std::counting_semaphore<5> csem{5};
csem.acquire();
// ... use resource ...
csem.release();

✅ Binary Semaphore with Flat Vectors (No Structs, No Pointers)

In performance-critical systems and Juspay Part B, representing a tree using flat contiguous vectors (indexed 0 to N-1) is far superior to pointer-based struct Node* trees:

Cache Locality: Vectors store node attributes contiguously in RAM, maximizing L1/L2 cache prefetching.
Zero Pointer Chasing: Accessing parentArr[u] is a direct $O(1)$ memory offset with no pointer dereferencing.
Simpler Memory Management: No dynamic allocation per node; cleanup is automatic.

⚠️ C++ Technical Nuance: Semaphores in `std::vector`

In C++20, std::binary_semaphore deletes its copy and move constructors (binary_semaphore(const binary_semaphore&) = delete). Therefore, you cannot write std::vector<std::binary_semaphore> v(N);.

The two clean industry-standard patterns are:

std::vector<std::unique_ptr<std::binary_semaphore>> (each semaphore allocated on heap, pointers held contiguously).
A Custom Spin-Based Binary Semaphore (using std::atomic_flag or std::atomic<int>).

Below is the complete C++ implementation using flat vectors:

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <memory>
#include <semaphore>

using namespace std;

class TreeOfSpaceSemaphores {
private:
    int n; // total nodes
    int m; // children per node
    
    // ================= FLAT VECTOR STORAGE =================
    // nodeSem[i] manages mutual exclusion for node index i
    vector<unique_ptr<binary_semaphore>> nodeSem;
    
    vector<int> parentArr;                 // parentArr[i] = parent node index (-1 for root)
    vector<int> lockedArr;                 // lockedArr[i] = UID of owner, or -1 if unlocked
    vector<unordered_set<int>> descLocked; // descLocked[i] = set of locked descendant node indices
    unordered_map<string, int> nameMap;    // node name -> node index (0 to n-1)

    // Helper: Collect path from node up to root
    vector<int> getPathToRoot(int node) {
        vector<int> path;
        for (int cur = node; cur != -1; cur = parentArr[cur]) {
            path.push_back(cur);
        }
        return path;
    }

public:
    TreeOfSpaceSemaphores(int totalNodes, int mAry, const vector<string>& names) 
        : n(totalNodes), m(mAry) {
        
        parentArr.resize(n, -1);
        lockedArr.resize(n, -1);
        descLocked.resize(n);
        
        // Initialize binary semaphores with 1 permit (unlocked state)
        nodeSem.reserve(n);
        for (int i = 0; i < n; i++) {
            nameMap[names[i]] = i;
            nodeSem.push_back(make_unique<binary_semaphore>(1));
            
            // Build M-ary tree parent relationships
            if (i > 0) {
                parentArr[i] = (i - 1) / m;
            }
        }
    }

    // ================= LOCK =================
    bool lock(const string& name, int uid) {
        int node = nameMap[name];
        vector<int> path = getPathToRoot(node);

        // 1. Acquire binary semaphores in leaf-to-root order (prevents deadlock)
        for (int p : path) {
            nodeSem[p]->acquire(); // decrements permit: 1 -> 0 (blocks if busy)
        }

        bool success = true;

        // 2. Critical Section checks:
        // Rule a: Node itself must not be locked
        if (lockedArr[node] != -1) success = false;

        // Rule b: Node must not have any locked descendants (O(1) set check)
        if (success && !descLocked[node].empty()) success = false;

        // Rule c: No ancestor in the path can be locked
        if (success) {
            for (size_t i = 1; i < path.size(); i++) {
                if (lockedArr[path[i]] != -1) {
                    success = false;
                    break;
                }
            }
        }

        // 3. Apply lock and update ancestors
        if (success) {
            lockedArr[node] = uid;
            for (size_t i = 1; i < path.size(); i++) {
                descLocked[path[i]].insert(node);
            }
        }

        // 4. Release semaphores in REVERSE order (root-to-leaf)
        for (auto it = path.rbegin(); it != path.rend(); ++it) {
            nodeSem[*it]->release(); // increments permit: 0 -> 1 (wakes waiter)
        }

        return success;
    }

    // ================= UNLOCK =================
    bool unlock(const string& name, int uid) {
        int node = nameMap[name];
        vector<int> path = getPathToRoot(node);

        // 1. Acquire semaphores leaf-to-root
        for (int p : path) {
            nodeSem[p]->acquire();
        }

        bool success = false;

        // 2. Critical Section check: Node must be locked by THIS uid
        if (lockedArr[node] == uid) {
            success = true;
            lockedArr[node] = -1;
            // Remove from all ancestors' descendant sets
            for (size_t i = 1; i < path.size(); i++) {
                descLocked[path[i]].erase(node);
            }
        }

        // 3. Release semaphores in reverse order (root-to-leaf)
        for (auto it = path.rbegin(); it != path.rend(); ++it) {
            nodeSem[*it]->release();
        }

        return success;
    }

    // ================= UPGRADE LOCK =================
    bool upgradeLock(const string& name, int uid) {
        int node = nameMap[name];
        vector<int> path = getPathToRoot(node);

        // 1. First acquire ancestor path semaphores
        for (int p : path) {
            nodeSem[p]->acquire();
        }

        bool success = true;

        // Check a: Node itself must not be locked
        if (lockedArr[node] != -1) success = false;

        // Check b: Must have at least one locked descendant
        if (success && descLocked[node].empty()) success = false;

        // Check c: No ancestor can be locked
        if (success) {
            for (size_t i = 1; i < path.size(); i++) {
                if (lockedArr[path[i]] != -1) {
                    success = false;
                    break;
                }
            }
        }

        // Check d: All locked descendants must belong to THIS uid
        vector<int> toUnlock;
        if (success) {
            for (int desc : descLocked[node]) {
                // Must acquire descendant's semaphore to verify lockedBy safely
                nodeSem[desc]->acquire();
                if (lockedArr[desc] != uid) {
                    success = false;
                    nodeSem[desc]->release();
                    break;
                }
                toUnlock.push_back(desc);
                nodeSem[desc]->release();
            }
        }

        // If checks pass, perform the upgrade
        if (success) {
            // Unlock all locked descendants
            for (int desc : toUnlock) {
                lockedArr[desc] = -1;
                // Remove from ancestors of desc up to node
                for (int cur = parentArr[desc]; cur != node; cur = parentArr[cur]) {
                    descLocked[cur].erase(desc);
                }
            }
            descLocked[node].clear();

            // Lock this node
            lockedArr[node] = uid;
            for (size_t i = 1; i < path.size(); i++) {
                descLocked[path[i]].insert(node);
            }
        }

        // Release ancestor path semaphores in reverse order
        for (auto it = path.rbegin(); it != path.rend(); ++it) {
            nodeSem[*it]->release();
        }

        return success;
    }
};

Java Equivalent with Flat Arrays (`Semaphore[]`):

If interviewing in Java, you use primitive flat arrays and a flat Semaphore[] array:

import java.util.*;
import java.util.concurrent.Semaphore;

class TreeOfSpaceSemaphoresJava {
    int n, m;
    
    // Flat arrays instead of Node objects:
    Semaphore[] nodeSem;
    int[] parentArr;
    int[] lockedArr;
    HashSet<Integer>[] descLocked;
    HashMap<String, Integer> nameMap;

    @SuppressWarnings("unchecked")
    public TreeOfSpaceSemaphoresJava(int n, int m, String[] names) {
        this.n = n;
        this.m = m;
        this.nodeSem = new Semaphore[n];
        this.parentArr = new int[n];
        this.lockedArr = new int[n];
        this.descLocked = new HashSet[n];
        this.nameMap = new HashMap<>();

        for (int i = 0; i < n; i++) {
            nameMap.put(names[i], i);
            nodeSem[i] = new Semaphore(1); // binary semaphore per node index
            lockedArr[i] = -1;
            descLocked[i] = new HashSet<>();
            parentArr[i] = (i == 0) ? -1 : (i - 1) / m;
        }
    }

    public boolean lock(String name, int uid) {
        int node = nameMap.get(name);
        List<Integer> path = new ArrayList<>();
        for (int cur = node; cur != -1; cur = parentArr[cur]) {
            path.add(cur);
        }

        // Acquire leaf-to-root
        for (int p : path) {
            try {
                nodeSem[p].acquire();
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
                return false;
            }
        }

        try {
            if (lockedArr[node] != -1) return false;
            if (!descLocked[node].isEmpty()) return false;
            for (int i = 1; i < path.size(); i++) {
                if (lockedArr[path.get(i)] != -1) return false;
            }

            lockedArr[node] = uid;
            for (int i = 1; i < path.size(); i++) {
                descLocked[path.get(i)].add(node);
            }
            return true;
        } finally {
            // Release in REVERSE order (root-to-leaf)
            for (int i = path.size() - 1; i >= 0; i--) {
                nodeSem[path.get(i)].release();
            }
        }
    }
}

Key Advantages of Flat Vector Semaphores:

Feature	Pointer / Object Based (`Node*`)	Flat Vector Based (`vector<int>`, `vector<unique_ptr<Sem>>`)
Node Representation	Heap object allocated via `new Node()`	Contiguous arrays indexed `0` to `N-1`
Memory Locality	Random memory addresses $\to$ many cache misses	Contiguous arrays $\to$ optimal hardware prefetching
Parent Traversal	Pointer dereferences: `cur = cur->parent`	Direct array lookup: `cur = parentArr[cur]`
Locking by Index	Dereference: `node->sem.acquire()`	Indexed vector: `nodeSem[p]->acquire()`

❌ Can Counting Semaphore Be Used? NO!

Why Counting Semaphore Fundamentally Cannot Work:

The tree invariant says:

If node X is locked:
  - NO ancestor of X can be locked
  - NO descendant of X can be locked

A counting semaphore just counts: "up to N threads can access this."

Counting Semaphore(3) on a node:
  → Allows 3 threads to "lock" the same node simultaneously
  → VIOLATES mutual exclusion!

Even if you set count = 1 (making it binary), the semaphore tracks a single number. It cannot represent:

Which specific paths are locked
Ancestor-descendant relationships between nodes
Whether two threads conflict (same path) or are independent (different subtrees)

Example:
    World
   /     \
  Asia   Africa
 /   \
China India

Counting semaphore on World initialized to 2:
- Thread 1 locks China → acquire() on World → counter = 1
- Thread 2 locks India → acquire() on World → counter = 0
- This blocks Africa from doing anything, even though Africa is independent!

OR:
- Thread 1 locks World → acquire() on World → counter = 1
- Thread 2 locks Asia → acquire() on World → counter = 0
- Both World AND Asia are "locked" → INVARIANT VIOLATED!

The fundamental mismatch: Counting semaphores control how many threads access a resource. The tree problem controls which threads can access based on tree relationships. These are fundamentally different constraints.

📝 What to Say to the Interviewer

"Technically, a binary semaphore can be used per-node as a substitute for a mutex — it would work mechanically. However, it's discouraged because:

Semaphores lack ownership semantics — any thread can release, which could accidentally break the locking invariant.

They have the same OS sleep overhead as mutexes (same futex under the hood).

They provide no advantage over mutexes for mutual exclusion.

A counting semaphore cannot work at all — it controls the NUMBER of concurrent accessors, but our tree problem requires controlling WHICH threads can access based on ancestor-descendant relationships. A simple counter can't distinguish between conflicting locks on the same path and independent locks on separate branches."

05_semaphores.md