Multi-threading and Concurrency Patterns

1. Producer-Consumer Pattern (Concurrency)

Component	Purpose	Synchronization	Key Insight
Shared Buffer	Queue to hold items between producer/consumer	Mutex lock for thread safety	Bounded buffer prevents overflow
Producer	Creates items, adds to buffer	Wait when buffer is full	Signal consumer when item added
Consumer	Removes items from buffer, processes them	Wait when buffer is empty	Signal producer when item removed
Condition Variables	notFull, notEmpty signals	Coordinate producer/consumer	Avoid busy waiting

Example: Producer-Consumer with bounded buffer

// JavaScript simulation using Promises and async/await
class BoundedBuffer {
    constructor(capacity) {
        this.capacity = capacity;
        this.buffer = [];
        this.mutex = new Promise(resolve => resolve());
        this.notFull = [];   // Wait queue for producers
        this.notEmpty = [];  // Wait queue for consumers
    }
    
    async produce(item) {
        // Acquire lock
        await this.mutex;
        
        // Wait while buffer is full
        while (this.buffer.length >= this.capacity) {
            await new Promise(resolve => this.notFull.push(resolve));
        }
        
        // Add item to buffer
        this.buffer.push(item);
        console.log(`Produced: ${item}, Buffer: [${this.buffer}]`);
        
        // Signal consumer that buffer is not empty
        if (this.notEmpty.length > 0) {
            const resolve = this.notEmpty.shift();
            resolve();
        }
    }
    
    async consume() {
        // Acquire lock
        await this.mutex;
        
        // Wait while buffer is empty
        while (this.buffer.length === 0) {
            await new Promise(resolve => this.notEmpty.push(resolve));
        }
        
        // Remove item from buffer
        const item = this.buffer.shift();
        console.log(`Consumed: ${item}, Buffer: [${this.buffer}]`);
        
        // Signal producer that buffer is not full
        if (this.notFull.length > 0) {
            const resolve = this.notFull.shift();
            resolve();
        }
        
        return item;
    }
}

// Conceptual implementation showing the pattern
class ProducerConsumer {
    constructor(bufferSize) {
        this.buffer = [];
        this.capacity = bufferSize;
    }
    
    produce(item) {
        while (this.buffer.length >= this.capacity) {
            // Wait (in real threading: condition variable wait)
        }
        
        this.buffer.push(item);
        // Signal consumers (notEmpty.notify())
    }
    
    consume() {
        while (this.buffer.length === 0) {
            // Wait (in real threading: condition variable wait)
        }
        
        const item = this.buffer.shift();
        // Signal producers (notFull.notify())
        return item;
    }
}

// Usage pattern:
// Producer thread:
//   while (true) {
//     item = produceItem()
//     buffer.produce(item)
//   }
//
// Consumer thread:
//   while (true) {
//     item = buffer.consume()
//     processItem(item)
//   }

Note: Producer-Consumer pattern decouples production from consumption. Bounded buffer prevents producer from overwhelming consumer. Critical: lock before checking condition, wait atomically releases lock and sleeps.

2. Print in Order Problem (Thread Synchronization)

Approach	Mechanism	Complexity	Use Case
Semaphores	Binary semaphores, initial count controls order	O(1) time, O(1) space	Simple ordering
Condition Variables	Wait/notify on shared counter	O(1) time, O(1) space	Complex predicates
Locks with Flags	Boolean flags + busy waiting or sleep	O(1) space, inefficient	Not recommended
Promises/Futures	Chain promises for sequential execution	JavaScript pattern	Async coordination

Example: Print in order using semaphores

// Conceptual semaphore implementation
class Semaphore {
    constructor(count) {
        this.count = count;
        this.waitQueue = [];
    }
    
    async acquire() {
        if (this.count > 0) {
            this.count--;
        } else {
            await new Promise(resolve => this.waitQueue.push(resolve));
        }
    }
    
    release() {
        if (this.waitQueue.length > 0) {
            const resolve = this.waitQueue.shift();
            resolve();
        } else {
            this.count++;
        }
    }
}

class Foo {
    constructor() {
        this.sem1 = new Semaphore(0); // Initially locked
        this.sem2 = new Semaphore(0); // Initially locked
    }
    
    async first(printFirst) {
        printFirst(); // Prints "first"
        this.sem1.release(); // Allow second to run
    }
    
    async second(printSecond) {
        await this.sem1.acquire(); // Wait for first
        printSecond(); // Prints "second"
        this.sem2.release(); // Allow third to run
    }
    
    async third(printThird) {
        await this.sem2.acquire(); // Wait for second
        printThird(); // Prints "third"
    }
}

// Usage: Even if threads start in any order,
// output is always "firstsecondthird"
const foo = new Foo();
// Thread A: foo.third(() => console.log('third'))
// Thread B: foo.first(() => console.log('first'))
// Thread C: foo.second(() => console.log('second'))
// Output: "firstsecondthird"

Example: Using promises in JavaScript

class FooPromises {
    constructor() {
        this.promise1 = new Promise(resolve => {
            this.resolve1 = resolve;
        });
        this.promise2 = new Promise(resolve => {
            this.resolve2 = resolve;
        });
    }
    
    async first(printFirst) {
        printFirst();
        this.resolve1(); // Unblock second
    }
    
    async second(printSecond) {
        await this.promise1; // Wait for first
        printSecond();
        this.resolve2(); // Unblock third
    }
    
    async third(printThird) {
        await this.promise2; // Wait for second
        printThird();
    }
}

// Alternative: using counter and condition
class FooCounter {
    constructor() {
        this.counter = 0;
    }
    
    async first(printFirst) {
        printFirst();
        this.counter = 1;
    }
    
    async second(printSecond) {
        while (this.counter !== 1) {
            await new Promise(resolve => setTimeout(resolve, 1));
        }
        printSecond();
        this.counter = 2;
    }
    
    async third(printThird) {
        while (this.counter !== 2) {
            await new Promise(resolve => setTimeout(resolve, 1));
        }
        printThird();
    }
}

3. Dining Philosophers Problem

Solution	Strategy	Deadlock-Free	Trade-off
Resource Ordering	Always pick lower-numbered fork first	✓ Yes	Simple, breaks circular wait
Waiter Solution	Semaphore limits concurrent diners to N-1	✓ Yes	Reduces parallelism
Chandy/Misra	Message passing with dirty/clean forks	✓ Yes	Complex, distributed systems
Timeout	Release forks if can't acquire both	✓ Livelock possible	May waste CPU cycles

Example: Dining philosophers with resource ordering

// 5 philosophers, 5 forks
// Deadlock occurs if each philosopher picks left fork simultaneously
// Solution: Pick lower-numbered fork first

class DiningPhilosophers {
    constructor() {
        this.forks = [
            { locked: false, id: 0 },
            { locked: false, id: 1 },
            { locked: false, id: 2 },
            { locked: false, id: 3 },
            { locked: false, id: 4 }
        ];
    }
    
    async wantsToEat(
        philosopher,
        pickLeftFork,
        pickRightFork,
        eat,
        putLeftFork,
        putRightFork
    ) {
        const leftFork = philosopher;
        const rightFork = (philosopher + 1) % 5;
        
        // Resource ordering: always pick lower-numbered fork first
        const firstFork = Math.min(leftFork, rightFork);
        const secondFork = Math.max(leftFork, rightFork);
        
        // Acquire first fork
        await this.acquireFork(firstFork);
        if (firstFork === leftFork) pickLeftFork();
        else pickRightFork();
        
        // Acquire second fork
        await this.acquireFork(secondFork);
        if (secondFork === leftFork) pickLeftFork();
        else pickRightFork();
        
        // Eat
        eat();
        
        // Release forks
        this.releaseFork(firstFork);
        if (firstFork === leftFork) putLeftFork();
        else putRightFork();
        
        this.releaseFork(secondFork);
        if (secondFork === leftFork) putLeftFork();
        else putRightFork();
    }
    
    async acquireFork(forkId) {
        while (this.forks[forkId].locked) {
            await new Promise(resolve => setTimeout(resolve, 10));
        }
        this.forks[forkId].locked = true;
    }
    
    releaseFork(forkId) {
        this.forks[forkId].locked = false;
    }
}

// Why resource ordering prevents deadlock:
// Philosopher 0: picks fork 0, then fork 1
// Philosopher 1: picks fork 1, then fork 2
// Philosopher 2: picks fork 2, then fork 3
// Philosopher 3: picks fork 3, then fork 4
// Philosopher 4: picks fork 0 (min), then fork 4 (max)
//
// Circular wait broken: Philosopher 4 competes with 0 for fork 0
// At least one philosopher can always acquire both forks

Example: Waiter solution (limit concurrent diners)

class DiningPhilosophersWaiter {
    constructor() {
        this.forks = Array(5).fill(false); // false = available
        this.waiter = new Semaphore(4); // Allow max 4 philosophers
    }
    
    async wantsToEat(
        philosopher,
        pickLeftFork,
        pickRightFork,
        eat,
        putLeftFork,
        putRightFork
    ) {
        const left = philosopher;
        const right = (philosopher + 1) % 5;
        
        // Request permission from waiter
        await this.waiter.acquire();
        
        // Pick up forks
        await this.pickFork(left);
        pickLeftFork();
        
        await this.pickFork(right);
        pickRightFork();
        
        // Eat
        eat();
        
        // Put down forks
        this.putFork(left);
        putLeftFork();
        
        this.putFork(right);
        putRightFork();
        
        // Release permission
        this.waiter.release();
    }
    
    async pickFork(forkId) {
        while (this.forks[forkId]) {
            await new Promise(resolve => setTimeout(resolve, 1));
        }
        this.forks[forkId] = true;
    }
    
    putFork(forkId) {
        this.forks[forkId] = false;
    }
}

// Why this works:
// With 5 philosophers and 5 forks, if all 5 try to eat,
// each picks left fork -> deadlock
//
// With waiter limiting to 4 concurrent diners:
// At most 4 can pick forks simultaneously
// 4 philosophers, 5 forks -> at least one can get both forks
// No circular wait possible

4. Reader-Writer Lock Pattern

Variant	Priority	Fairness	Use Case
Readers-Preference	Readers get priority	Writers may starve	Read-heavy workloads
Writers-Preference	Writers get priority	Readers may starve	Write-heavy workloads
Fair (FIFO)	First-come-first-served	No starvation	Balanced workloads
Key Property	Multiple readers OR single writer	Never both simultaneously	Shared data access

Example: Readers-preference lock

class ReadWriteLock {
    constructor() {
        this.readers = 0;
        this.writers = 0;
        this.writeRequests = 0;
    }
    
    async acquireRead() {
        // Wait if any writer is active or waiting
        while (this.writers > 0 || this.writeRequests > 0) {
            await new Promise(resolve => setTimeout(resolve, 1));
        }
        this.readers++;
    }
    
    releaseRead() {
        this.readers--;
    }
    
    async acquireWrite() {
        this.writeRequests++;
        
        // Wait until no readers and no writers
        while (this.readers > 0 || this.writers > 0) {
            await new Promise(resolve => setTimeout(resolve, 1));
        }
        
        this.writeRequests--;
        this.writers++;
    }
    
    releaseWrite() {
        this.writers--;
    }
}

// Usage:
const rwLock = new ReadWriteLock();

// Reader thread:
async function reader() {
    await rwLock.acquireRead();
    try {
        // Read shared data
        console.log('Reading...');
    } finally {
        rwLock.releaseRead();
    }
}

// Writer thread:
async function writer() {
    await rwLock.acquireWrite();
    try {
        // Write shared data
        console.log('Writing...');
    } finally {
        rwLock.releaseWrite();
    }
}

// Multiple readers can run concurrently
// Writer has exclusive access

Example: Fair reader-writer lock

class FairReadWriteLock {
    constructor() {
        this.readers = 0;
        this.writer = false;
        this.queue = []; // FIFO queue
    }
    
    async acquireRead() {
        const ticket = { type: 'read', resolve: null };
        const promise = new Promise(resolve => {
            ticket.resolve = resolve;
        });
        
        this.queue.push(ticket);
        this.processQueue();
        
        await promise;
        this.readers++;
    }
    
    releaseRead() {
        this.readers--;
        this.processQueue();
    }
    
    async acquireWrite() {
        const ticket = { type: 'write', resolve: null };
        const promise = new Promise(resolve => {
            ticket.resolve = resolve;
        });
        
        this.queue.push(ticket);
        this.processQueue();
        
        await promise;
        this.writer = true;
    }
    
    releaseWrite() {
        this.writer = false;
        this.processQueue();
    }
    
    processQueue() {
        if (this.queue.length === 0) return;
        
        const next = this.queue[0];
        
        if (next.type === 'read') {
            if (!this.writer) {
                // Grant all consecutive readers
                while (this.queue.length > 0 && 
                       this.queue[0].type === 'read') {
                    const ticket = this.queue.shift();
                    ticket.resolve();
                }
            }
        } else { // write
            if (!this.writer && this.readers === 0) {
                const ticket = this.queue.shift();
                ticket.resolve();
            }
        }
    }
}

5. Traffic Light Controller System

Component	State	Synchronization	Constraint
Road A/B/C/D	Green light allows cars to pass	Mutex ensures only one road green	Orthogonal roads can't be green together
Light States	Green, Yellow, Red	State machine transitions	Safety: Yellow before Red
Deadlock Prevention	Round-robin or priority scheduling	Prevent starvation	Fair access to all roads
Conflict Detection	A ⊥ C, B ⊥ D (perpendicular roads)	Mutual exclusion groups	Safety critical

Example: Traffic light synchronization

class TrafficLight {
    constructor() {
        // Four roads: 1 (A), 2 (B), 3 (C), 4 (D)
        // Road 1 and 3 are opposite (can be green together)
        // Road 2 and 4 are opposite (can be green together)
        // Road 1 and 2 are perpendicular (cannot be green together)
        
        this.greenRoad = 1; // Currently green road
        this.locks = {
            1: new Semaphore(1),
            2: new Semaphore(0),
            3: new Semaphore(0),
            4: new Semaphore(0)
        };
    }
    
    async carArrived(carId, roadId, direction, turnGreen, crossCar) {
        // Acquire permission for this road
        await this.locks[roadId].acquire();
        
        try {
            // Turn light green
            turnGreen();
            
            // Car crosses intersection
            crossCar();
        } finally {
            // Release lock for this road
            this.locks[roadId].release();
        }
    }
    
    // Alternative: explicit control
    async controlledCarArrived(carId, roadId, direction, turnGreen, crossCar) {
        // Wait for this road to be green
        while (this.greenRoad !== roadId) {
            await new Promise(resolve => setTimeout(resolve, 10));
        }
        
        turnGreen();
        crossCar();
    }
    
    // Traffic controller cycles through roads
    async trafficController() {
        const sequence = [1, 2, 3, 4]; // Round-robin
        
        while (true) {
            for (const roadId of sequence) {
                this.greenRoad = roadId;
                await new Promise(resolve => setTimeout(resolve, 5000)); // 5s green
            }
        }
    }
}

// Simplified version with semaphores
class TrafficLightSimplified {
    constructor() {
        this.roadA = new Semaphore(1); // Initially green
        this.roadB = new Semaphore(0);
    }
    
    async carArrived(carId, roadId, direction, turnGreen, crossCar) {
        if (roadId === 1) {
            await this.roadA.acquire();
            turnGreen();
            crossCar();
            this.roadA.release();
        } else if (roadId === 2) {
            await this.roadB.acquire();
            turnGreen();
            crossCar();
            this.roadB.release();
        }
    }
}

Example: Advanced traffic light with priorities

class AdvancedTrafficLight {
    constructor() {
        this.state = {
            1: 'green',  // North-South
            2: 'red',    // East-West
            3: 'green',  // South-North (opposite of 1)
            4: 'red'     // West-East (opposite of 2)
        };
        
        this.waiting = {
            1: 0, 2: 0, 3: 0, 4: 0
        };
        
        this.mutex = new Semaphore(1);
    }
    
    async carArrived(carId, roadId, direction, turnGreen, crossCar) {
        await this.mutex.acquire();
        
        // Register waiting car
        this.waiting[roadId]++;
        
        // Wait for green light
        while (this.state[roadId] !== 'green') {
            this.mutex.release();
            await new Promise(resolve => setTimeout(resolve, 100));
            await this.mutex.acquire();
        }
        
        this.waiting[roadId]--;
        this.mutex.release();
        
        // Cross intersection
        turnGreen();
        crossCar();
    }
    
    // Scheduler switches lights based on waiting cars
    async scheduler() {
        while (true) {
            await this.mutex.acquire();
            
            // Find road with most waiting cars
            let maxWait = 0;
            let nextRoad = 1;
            
            for (let road = 1; road <= 4; road++) {
                if (this.waiting[road] > maxWait) {
                    maxWait = this.waiting[road];
                    nextRoad = road;
                }
            }
            
            // Switch to that road (and its opposite)
            this.switchLight(nextRoad);
            
            this.mutex.release();
            
            await new Promise(resolve => setTimeout(resolve, 3000));
        }
    }
    
    switchLight(roadId) {
        // Set perpendicular roads to red
        if (roadId === 1 || roadId === 3) {
            this.state[1] = 'green';
            this.state[3] = 'green';
            this.state[2] = 'red';
            this.state[4] = 'red';
        } else {
            this.state[1] = 'red';
            this.state[3] = 'red';
            this.state[2] = 'green';
            this.state[4] = 'green';
        }
    }
}

Warning: Multi-threading requires careful synchronization. Always acquire locks in consistent order to prevent deadlock. Use condition variables instead of busy-waiting to avoid wasting CPU. Remember: mutual exclusion (only one writer), concurrency (multiple readers), and fairness (no starvation).

Summary: Multi-threading Patterns

Producer-Consumer: Bounded buffer + condition variables (notFull, notEmpty) - decouples production from consumption
Buffer Synchronization: Producer waits when full, consumer waits when empty - signals wake waiting threads
Condition Variable Pattern: Lock → check condition → wait atomically releases lock and sleeps → reacquire lock on wake
Print in Order: Use semaphores initialized to 0 - release() after completion signals next thread to proceed
Semaphore Pattern: Binary semaphore (0 or 1) for mutual exclusion, counting semaphore for resources
Dining Philosophers: Resource ordering breaks circular wait - always acquire lower-numbered resource first
Deadlock Conditions: Mutual exclusion + Hold and wait + No preemption + Circular wait - break any one to prevent
Waiter Solution: Limit concurrent diners to N-1 - guarantees at least one can acquire both forks
Reader-Writer Lock: Multiple readers OR single writer - never both simultaneously
RW Variants: Readers-preference (readers priority), writers-preference (writers priority), fair (FIFO queue)
Starvation Prevention: Fair locks use FIFO queue - process consecutive readers together for efficiency
Traffic Light: Mutual exclusion for perpendicular roads - opposite roads can be green together
Round-Robin Scheduling: Cycle through states to ensure fairness - prevents starvation of any road
Priority Scheduling: Service road with most waiting cars - improves throughput but may cause starvation
Lock Ordering: Always acquire locks in same order globally - prevents deadlock from circular dependencies
Avoid Busy-Waiting: Use condition variables/semaphores instead of while loops - saves CPU cycles

Related Cheat Sheets

Algorithm Patterns