🎮 File 08: Custom Thread Scheduler — The "No Primitives At All" Approach

The most elegant approach: skip synchronization entirely. Coordinate at the scheduler level. This is YOUR Attempt3 Java solution, explained and refined.

📖 The Core Idea (Simple Explanation)

Instead of making the lock() function thread-safe (with mutexes, atomics, etc.), we ask:

"What if we never let conflicting threads run at the same time?"

If two threads want to lock nodes that are on the same root-to-node path (ancestor-descendant), they WILL conflict. But if they want to lock sibling nodes (neither is ancestor/descendant of the other), they can run safely in parallel.

Solution: Build a custom scheduler that:

Takes all queries into a queue
Before launching a thread, checks if ALL currently-running threads are working on sibling nodes
If YES → launch the thread (no conflict possible)
If NO → put the query back in the queue and try later

No mutexes. No atomics. No synchronized. The tree itself stays mutex-free.

🌳 What Are "Sibling" Nodes? (Not Just Direct Siblings)

In this context, "siblings" means neither is an ancestor/descendant of the other. They could be at any level of the tree.

              World
            /       \
         Asia       Africa
        /    \     /     \
     China  India SA     Egypt
     
China and India → siblings ✅ (same parent, neither is ancestor of other)
China and Egypt → siblings ✅ (different subtrees entirely)
China and Asia  → NOT siblings ❌ (Asia is China's parent/ancestor)
China and World → NOT siblings ❌ (World is China's ancestor)
Asia and Africa → siblings ✅ (same level, neither is ancestor of other)

How to Check if Two Nodes Are Siblings:

Walk up from node A to root, collecting all ancestors into a set.
Walk up from node B to root.
If any of B's ancestors (including B itself) is in A's ancestor set:
  → They share a path. NOT siblings (unless the common node is neither A nor B).
  
More precisely:
  A and B are siblings if their paths to root share NO node
  EXCEPT a common ancestor that is neither A nor B.

💻 The Complete Java Code (Your Attempt3, Explained)

import java.util.*;

// ============ HELPER CLASSES ============

// Pairs a running thread with the node name it's working on
class Pair {
    public Thread th;
    public String name;
    
    Pair(Thread t, String n) {
        this.th = t;
        this.name = n;
    }
}

// Represents one query from input
class Query {
    int op;       // 1=lock, 2=unlock, 3=upgrade
    String name;  // node name
    int uid;      // user id
    
    Query(int op, String name, int uid) {
        this.op = op;
        this.name = name;
        this.uid = uid;
    }
}

// ============ NODE STRUCTURE ============
class Node {
    String name;
    Node parent;
    Set<Node> childs = new HashSet<>();
    volatile boolean isLocked = false;  // volatile for thread visibility
    
    Node(String name, Node parent) {
        this.name = name;
        this.parent = parent;
    }
}

// ============ LOCKING TREE (NO SYNCHRONIZATION INSIDE!) ============
class LockingTree {
    Node root;
    Map<String, Node> nodeMap = new HashMap<>();
    Map<String, Boolean> areSibling = new HashMap<>();
    
    // Build the M-ary tree from BFS-order input
    LockingTree(List<String> names, int m) {
        int n = names.size();
        root = new Node(names.get(0), null);
        nodeMap.put(names.get(0), root);
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        int idx = 1;
        
        while (!q.isEmpty() && idx < n) {
            Node cur = q.poll();
            for (int i = idx; i < idx + m && i < n; i++) {
                Node child = new Node(names.get(i), cur);
                nodeMap.put(names.get(i), child);
                cur.childs.add(child);
                q.add(child);
            }
            idx += m;
        }
    }
    
    // ════════════════════════════════════════════
    // PRECOMPUTE: Build sibling relationship table
    // Key: "nodeA|nodeB"  Value: true/false
    // ════════════════════════════════════════════
    public void buildSiblingsStructure(List<String> names) {
        List<Node> nodeVec = new ArrayList<>();
        for (String name : names) {
            nodeVec.add(nodeMap.get(name));
        }
        
        // O(N²) precomputation — done once before any queries
        for (int i = 0; i < nodeVec.size(); i++) {
            for (int j = 0; j < nodeVec.size(); j++) {
                String pair1 = nodeVec.get(i).name + "|" + nodeVec.get(j).name;
                String pair2 = nodeVec.get(j).name + "|" + nodeVec.get(i).name;
                boolean val = areSiblings(nodeVec.get(i), nodeVec.get(j));
                areSibling.put(pair1, val);
                areSibling.put(pair2, val);
            }
        }
    }
    
    // Check if two nodes are "siblings" (no ancestor-descendant relationship)
    private boolean areSiblings(Node a, Node b) {
        // Collect all ancestors of A (including A itself)
        Set<String> aPath = new HashSet<>();
        Node temp = a;
        while (temp != null) {
            aPath.add(temp.name);
            temp = temp.parent;
        }
        
        // Walk up from B. If we find a common node:
        temp = b;
        while (temp != null) {
            if (aPath.contains(temp.name)) {
                // Common ancestor found.
                // They're siblings ONLY IF the common node is NEITHER a NOR b
                // (i.e., they diverge before reaching each other)
                return !temp.name.equals(a.name) && !temp.name.equals(b.name);
            }
            temp = temp.parent;
        }
        return false;  // shouldn't happen in a connected tree
    }
    
    // ════════════════════════════════════════════
    // LOCK FUNCTION — NO SYNCHRONIZATION NEEDED!
    // Because the scheduler guarantees no conflicting threads run together.
    // ════════════════════════════════════════════
    public boolean lock(String nodeName, int uid) {
        Node node = nodeMap.get(nodeName);
        
        // Check descendants (BFS)
        Queue<Node> q = new LinkedList<>();
        q.add(node);
        while (!q.isEmpty()) {
            Node cur = q.poll();
            if (cur.isLocked) return false;
            q.addAll(cur.childs);
        }
        
        // Check ancestors
        for (Node p = node.parent; p != null; p = p.parent) {
            if (p.isLocked) return false;
        }
        
        // Lock it (single write — safe because scheduler prevents conflicts)
        node.isLocked = true;
        return true;
    }
}

// ============ MAIN — THE CUSTOM SCHEDULER ============
public class TreeOfSpaceScheduler {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt(), q = sc.nextInt();
        List<String> names = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            names.add(sc.next());
        }
        
        LockingTree tree = new LockingTree(names, m);
        tree.buildSiblingsStructure(names);
        
        // Read all queries into a queue
        Queue<Query> queryQueue = new LinkedList<>();
        Set<Pair> activeThreads = new HashSet<>();
        
        for (int i = 0; i < q; i++) {
            int op = sc.nextInt();
            String name = sc.next();
            int uid = sc.nextInt();
            queryQueue.add(new Query(op, name, uid));
        }
        
        // ════════════════════════════════════════════
        // CUSTOM THREAD SCHEDULING ALGORITHM
        //
        // Key idea: Allow a thread to start ONLY IF
        // every currently-alive thread is targeting a sibling node.
        // Otherwise, the query must wait.
        // ════════════════════════════════════════════
        
        while (!queryQueue.isEmpty()) {
            Query curQuery = queryQueue.poll();
            String curName = curQuery.name;
            boolean canRun = true;
            
            // Check against ALL currently running threads
            for (Pair active : activeThreads) {
                Thread alreadyCalled = active.th;
                String alreadyCalledName = active.name;
                
                // If the thread is still alive AND not a sibling → conflict!
                if (alreadyCalled.isAlive() && 
                    !tree.areSibling.getOrDefault(
                        alreadyCalledName + "|" + curName, false)) {
                    canRun = false;
                    break;
                }
            }
            
            if (canRun) {
                // No conflict! Launch the thread.
                int uid = curQuery.uid;
                Thread tr = new Thread(() -> {
                    boolean result = tree.lock(curName, uid);
                    System.out.println(curName + " " + result);
                });
                activeThreads.add(new Pair(tr, curName));
                tr.start();
            } else {
                // Conflict! Put the query back and try later.
                queryQueue.add(curQuery);
            }
        }
    }
}

🔍 Why This Works (The Proof)

Why No Race Condition?

For a race condition to happen, two threads must concurrently access overlapping state. In the tree problem, overlapping state exists when:

Two threads lock the same node (they both write isLocked)
One thread locks an ancestor, another locks a descendant (they check each other's state)

Our scheduler ensures: A new thread only starts if ALL running threads are on sibling nodes. Siblings share NO ancestor-descendant relationship, so:

They never check each other's isLocked state
They never write to the same variables
They operate on completely independent parts of the tree

Why No Synchronization Primitives?

The lock() function itself has:

No mutex — the function is plain code
No atomics — uses volatile boolean for visibility only
No synchronized — no monitor locks

The coordination happens at a higher level — the scheduler — which runs on the main thread and is inherently single-threaded (no concurrent modification of the queue or active set).

⚠️ Limitations and Trade-offs

Pro	Con
Zero synchronization overhead inside `lock()`	O(N²) precomputation for sibling table
Maximum parallelism for sibling operations	Non-sibling queries are serialized (requeued)
Simple `lock()` code (no rollback, no CAS)	Scheduler itself must be single-threaded
Easy to understand and explain	May starve queries in adversarial input
Elegant — moves coordination out of data path	Thread creation overhead per query

When This Approach Shines:

When most queries are on sibling nodes (independent branches)
When the tree is wide (many children per node) → most pairs are siblings

When This Approach Suffers:

When queries frequently target ancestor-descendant pairs
When the tree is tall and narrow → few siblings, lots of conflicts

💡 Improvements Over the Basic Version

1. Clean Up Dead Threads

// Before checking canRun, remove finished threads
activeThreads.removeIf(pair -> !pair.th.isAlive());

2. Add Unlock and Upgrade Support

if (canRun) {
    Thread tr = new Thread(() -> {
        boolean result;
        switch (curQuery.op) {
            case 1: result = tree.lock(curName, uid); break;
            case 2: result = tree.unlock(curName, uid); break;
            case 3: result = tree.upgrade(curName, uid); break;
            default: result = false;
        }
        System.out.println(result ? "true" : "false");
    });
    activeThreads.add(new Pair(tr, curName));
    tr.start();
}

3. Fairness — Prevent Starvation

// Track how many times a query has been requeued
int retryCount = 0;
// After MAX_RETRIES, force-run it by waiting for all active threads to finish
if (retryCount > MAX_RETRIES) {
    for (Pair active : activeThreads) {
        active.th.join();  // wait for all to finish
    }
    activeThreads.clear();
    // Now run it — guaranteed no conflict
}

📝 What to Say to the Interviewer

"The most elegant approach avoids synchronization primitives entirely. Instead of making lock() thread-safe, I build a custom scheduler that only allows a thread to start if all currently-running threads are targeting sibling nodes — nodes with no ancestor-descendant relationship.

I precompute a sibling table in O(N²) so runtime lookups are O(1). The lock() function itself has zero synchronization overhead — no mutex, no atomic, no synchronized — because the scheduler guarantees non-conflicting threads.

The trade-off is that non-sibling queries get requeued and may wait, reducing parallelism for ancestor-descendant conflicts. But for wide trees where most queries target independent branches, this gives maximum throughput with zero coordination cost.

This approach was presented in your Java-based Attempt3 code and is closest to a clean 'no synchronization primitives' answer that's been shared publicly."

08_custom_scheduler.md