Deadlocks and Prevention

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

                    ┌─────────────────────────┐
                    │ Need deadlock prevention │
                    └───────────┬─────────────┘
                                │
                    ┌───────────▼─────────────┐
                    │ Can resources be ordered?│
                    └───────────┬─────────────┘
                          │     │
                    Yes───┘     └───No
                     │               │
         ┌───────────▼────┐   ┌─────▼──────────────┐
         │ USE LOCK       │   │ Can operation be   │
         │ ORDERING       │   │ made lock-free?    │
         │ (Preferred)    │   └─────┬──────────────┘
         └────────────────┘         │     │
                              Yes───┘     └───No
                               │               │
                   ┌───────────▼────┐   ┌─────▼──────────────┐
                   │ USE LOCK-FREE  │   │ USE TIMEOUT +      │
                   │ ALGORITHMS     │   │ ROLLBACK/RETRY     │
                   │ (If possible)  │   │ (Fallback approach)│
                   └────────────────┘   └────────────────────┘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

/**
 * Lock with explicit ordering for deadlock prevention.
 * Includes runtime enforcement and debugging support.
 */
class OrderedLock {
    private static nextGlobalOrder = 0;
    
    readonly name: string;
    readonly order: number;
    private locked = false;
    private owner: string | null = null;
    private waitQueue: Array<() => void> = [];
    
    constructor(name: string, explicitOrder?: number) {
        this.name = name;
        this.order = explicitOrder ?? OrderedLock.nextGlobalOrder++;
    }
    
    async acquire(context: LockContext): Promise<void> {
        // Enforce ordering: cannot acquire lower-order lock
        this.validateOrdering(context);
        
        if (!this.locked) {
            this.locked = true;
            this.owner = context.threadId;
            context.addHeldLock(this);
            return;
        }
        
        // Wait for lock to become available
        return new Promise(resolve => {
            this.waitQueue.push(() => {
                this.locked = true;
                this.owner = context.threadId;
                context.addHeldLock(this);
                resolve();
            });
        });
    }
    
    release(context: LockContext): void {
        if (this.owner !== context.threadId) {
            throw new Error(`Thread ${context.threadId} does not own lock ${this.name}`);
        }
        
        context.removeHeldLock(this);
        this.owner = null;
        
        if (this.waitQueue.length > 0) {
            const next = this.waitQueue.shift()!;
            next();
        } else {
            this.locked = false;
        }
    }
    
    private validateOrdering(context: LockContext): void {
        const violations = context.heldLocks.filter(lock => lock.order > this.order);
        
        if (violations.length > 0) {
            const violationNames = violations.map(l => `${l.name}(${l.order})`).join(', ');
            throw new LockOrderingViolation(
                `Cannot acquire ${this.name}(${this.order}) while holding ` +
                `higher-order locks: ${violationNames}. \n` +
                `This would create potential for circular wait (deadlock).`
            );
        }
    }
}
 
/**
 * Context tracking locks held by a thread.
 * Passed through call chain to enable ordering validation.
 */
class LockContext {
    readonly threadId: string;
    readonly heldLocks: OrderedLock[] = [];
    
    constructor(threadId: string) {
        this.threadId = threadId;
    }
    
    addHeldLock(lock: OrderedLock): void {
        this.heldLocks.push(lock);
    }
    
    removeHeldLock(lock: OrderedLock): void {
        const index = this.heldLocks.indexOf(lock);
        if (index !== -1) {
            this.heldLocks.splice(index, 1);
        }
    }
    
    getMaxOrder(): number {
        return Math.max(...this.heldLocks.map(l => l.order), -1);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

/**
 * For objects with dynamic locks, use object identity for ordering.
 * This works when the same objects are always locked together.
 */
class Entity {
    private static idCounter = 0;
    
    readonly id: number;  // Unique ID serves as lock order
    private lock = new Mutex();
    private data: any;
    
    constructor() {
        this.id = Entity.idCounter++;
    }
    
    /**
     * Lock multiple entities in consistent order to prevent deadlock.
     */
    static async lockMultiple(...entities: Entity[]): Promise<void> {
        // Sort by ID to ensure consistent ordering
        const sorted = [...entities].sort((a, b) => a.id - b.id);
        
        for (const entity of sorted) {
            await entity.lock.acquire();
        }
    }
    
    static unlockMultiple(...entities: Entity[]): void {
        // Release in reverse order (not strictly necessary, but clean)
        const sorted = [...entities].sort((a, b) => b.id - a.id);
        
        for (const entity of sorted) {
            entity.lock.release();
        }
    }
}
 
// Usage: Two different operations on the same entities
async function transfer(from: Entity, to: Entity, data: any) {
    // Both operations will acquire locks in same order (by ID)
    // No deadlock possible
    await Entity.lockMultiple(from, to);
    try {
        // Perform transfer
        const value = from.data;
        from.data = null;
        to.data = value;
    } finally {
        Entity.unlockMultiple(from, to);
    }
}
 
// These can run concurrently safely:
await Promise.all([
    transfer(entityA, entityB, data1),
    transfer(entityB, entityA, data2),  // Same lock order as above!
]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

interface TryLockable {
    tryAcquire(): boolean;
    release(): void;
}
 
/**
 * Attempts to acquire all locks atomically using try-lock.
 * If any lock fails, releases all and retries with exponential backoff.
 */
async function acquireAllOrNone(
    locks: TryLockable[],
    options: {
        maxRetries?: number;
        initialBackoffMs?: number;
        maxBackoffMs?: number;
        jitterFactor?: number;
    } = {}
): Promise<boolean> {
    const {
        maxRetries = 10,
        initialBackoffMs = 10,
        maxBackoffMs = 5000,
        jitterFactor = 0.5
    } = options;
    
    let backoffMs = initialBackoffMs;
    
    for (let attempt = 0; attempt < maxRetries; attempt++) {
        const acquired: TryLockable[] = [];
        let allAcquired = true;
        
        // Try to acquire each lock
        for (const lock of locks) {
            if (lock.tryAcquire()) {
                acquired.push(lock);
            } else {
                allAcquired = false;
                break;
            }
        }
        
        if (allAcquired) {
            return true;  // Success!
        }
        
        // Failed to acquire all - release what we got
        for (const lock of acquired) {
            lock.release();
        }
        
        // Calculate backoff with jitter to avoid thundering herd
        const jitter = 1 + (Math.random() - 0.5) * jitterFactor;
        const sleepMs = Math.min(backoffMs * jitter, maxBackoffMs);
        
        await sleep(sleepMs);
        
        // Exponential backoff for next attempt
        backoffMs = Math.min(backoffMs * 2, maxBackoffMs);
    }
    
    return false;  // Failed after all retries
}
 
// Usage
async function transferWithTryLock(from: Account, to: Account, amount: number) {
    const success = await acquireAllOrNone([from.lock, to.lock], {
        maxRetries: 10,
        initialBackoffMs: 10,
        maxBackoffMs: 1000
    });
    
    if (!success) {
        throw new Error('Could not acquire locks after retries');
    }
    
    try {
        // Perform transfer
        from.balance -= amount;
        to.balance += amount;
    } finally {
        from.lock.release();
        to.lock.release();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

/**
 * Lock-free stack using compare-and-swap (CAS).
 * No locks means no deadlock possible.
 */
class LockFreeStack<T> {
    private head: AtomicReference<Node<T> | null>;
    
    constructor() {
        this.head = new AtomicReference<Node<T> | null>(null);
    }
    
    push(value: T): void {
        const newNode = new Node(value);
        
        while (true) {
            // Read current head
            const currentHead = this.head.get();
            
            // Set new node's next to current head
            newNode.next = currentHead;
            
            // Try to swap head to new node (only if head hasn't changed)
            if (this.head.compareAndSet(currentHead, newNode)) {
                return;  // Success!
            }
            
            // Another thread modified head; retry
        }
    }
    
    pop(): T | null {
        while (true) {
            const currentHead = this.head.get();
            
            if (currentHead === null) {
                return null;  // Stack is empty
            }
            
            const newHead = currentHead.next;
            
            // Try to swap head to next node
            if (this.head.compareAndSet(currentHead, newHead)) {
                return currentHead.value;  // Success!
            }
            
            // Another thread modified head; retry
        }
    }
}
 
class Node<T> {
    value: T;
    next: Node<T> | null = null;
    
    constructor(value: T) {
        this.value = value;
    }
}
 
// Simulated atomic reference (real implementation would use Atomics in JavaScript)
class AtomicReference<T> {
    private value: T;
    
    constructor(initial: T) {
        this.value = initial;
    }
    
    get(): T {
        return this.value;
    }
    
    compareAndSet(expected: T, update: T): boolean {
        // In real implementation, this is an atomic CPU instruction
        if (this.value === expected) {
            this.value = update;
            return true;
        }
        return false;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

/**
 * Stamped reference pairs a value with a version number
 * to prevent ABA problems in lock-free algorithms.
 */
class StampedReference<T> {
    private value: T;
    private stamp: number;
    
    constructor(value: T, stamp: number = 0) {
        this.value = value;
        this.stamp = stamp;
    }
    
    get(): { value: T; stamp: number } {
        return { value: this.value, stamp: this.stamp };
    }
    
    compareAndSet(
        expectedValue: T,
        newValue: T,
        expectedStamp: number,
        newStamp: number
    ): boolean {
        // Both value AND stamp must match for CAS to succeed
        if (this.value === expectedValue && this.stamp === expectedStamp) {
            this.value = newValue;
            this.stamp = newStamp;
            return true;
        }
        return false;
    }
}
 
// Usage in lock-free stack
class ABASafeStack<T> {
    private head: StampedReference<Node<T> | null>;
    
    pop(): T | null {
        while (true) {
            const { value: currentHead, stamp } = this.head.get();
            
            if (currentHead === null) {
                return null;
            }
            
            const newHead = currentHead.next;
            
            // CAS now also checks stamp—ABA prevented
            if (this.head.compareAndSet(currentHead, newHead, stamp, stamp + 1)) {
                return currentHead.value;
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

/**
 * Lock that supports acquisition with timeout.
 */
class TimeoutLock {
    private locked = false;
    private waitQueue: Array<{
        resolve: () => void;
        reject: (err: Error) => void;
        timeoutId: NodeJS.Timeout;
    }> = [];
    
    async acquireWithTimeout(timeoutMs: number): Promise<void> {
        if (!this.locked) {
            this.locked = true;
            return;
        }
        
        return new Promise((resolve, reject) => {
            const timeoutId = setTimeout(() => {
                // Remove from wait queue
                this.waitQueue = this.waitQueue.filter(w => w.resolve !== resolve);
                reject(new LockTimeoutError(`Lock acquisition timed out after ${timeoutMs}ms`));
            }, timeoutMs);
            
            this.waitQueue.push({
                resolve: () => {
                    clearTimeout(timeoutId);
                    resolve();
                },
                reject,
                timeoutId
            });
        });
    }
    
    release(): void {
        if (this.waitQueue.length > 0) {
            const next = this.waitQueue.shift()!;
            next.resolve();
        } else {
            this.locked = false;
        }
    }
}
 
/**
 * Transaction coordinator with timeout-based deadlock prevention.
 */
class TransactionCoordinator {
    private readonly defaultTimeoutMs = 30000;
    
    async executeTransaction<T>(
        locks: TimeoutLock[],
        operation: () => Promise<T>
    ): Promise<T> {
        const acquired: TimeoutLock[] = [];
        
        try {
            // Acquire all locks with timeout
            for (const lock of locks) {
                try {
                    await lock.acquireWithTimeout(this.defaultTimeoutMs);
                    acquired.push(lock);
                } catch (error) {
                    if (error instanceof LockTimeoutError) {
                        // Roll back: release all acquired locks
                        this.releaseAll(acquired);
                        throw new DeadlockPotentialError(
                            'Transaction aborted: potential deadlock detected',
                            error
                        );
                    }
                    throw error;
                }
            }
            
            // All locks acquired—execute operation
            return await operation();
            
        } finally {
            // Release all locks in reverse order
            this.releaseAll(acquired.reverse());
        }
    }
    
    private releaseAll(locks: TimeoutLock[]): void {
        for (const lock of locks) {
            try {
                lock.release();
            } catch (e) {
                // Log but don't throw—ensure other locks are released
                console.error('Failed to release lock:', e);
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

enum TransactionPhase {
    GROWING = 'GROWING',
    SHRINKING = 'SHRINKING',
    COMMITTED = 'COMMITTED',
    ABORTED = 'ABORTED'
}
 
class TwoPhaseLockingTransaction {
    private phase: TransactionPhase = TransactionPhase.GROWING;
    private heldLocks: Set<Lock> = new Set();
    private lockManager: LockManager;
    
    async acquireLock(lock: Lock, mode: 'READ' | 'WRITE'): Promise<void> {
        if (this.phase !== TransactionPhase.GROWING) {
            throw new Error(
                `Cannot acquire lock in ${this.phase} phase. \
                2PL requires all locks to be acquired before any are released.`
            );
        }
        
        await this.lockManager.acquire(lock, mode, this);
        this.heldLocks.add(lock);
    }
    
    releaseLock(lock: Lock): void {
        if (!this.heldLocks.has(lock)) {
            throw new Error('Cannot release lock not held by this transaction');
        }
        
        // Transition to shrinking phase on first release
        if (this.phase === TransactionPhase.GROWING) {
            this.phase = TransactionPhase.SHRINKING;
        }
        
        this.lockManager.release(lock, this);
        this.heldLocks.delete(lock);
    }
    
    async commit(): Promise<void> {
        // Transition through shrinking phase
        this.phase = TransactionPhase.SHRINKING;
        
        // Release all locks
        for (const lock of this.heldLocks) {
            this.lockManager.release(lock, this);
        }
        this.heldLocks.clear();
        
        this.phase = TransactionPhase.COMMITTED;
    }
    
    async abort(): Promise<void> {
        // Roll back changes (implementation-specific)
        await this.rollback();
        
        // Release all locks
        this.phase = TransactionPhase.SHRINKING;
        for (const lock of this.heldLocks) {
            this.lockManager.release(lock, this);
        }
        this.heldLocks.clear();
        
        this.phase = TransactionPhase.ABORTED;
    }
}
 
/**
 * Strict 2PL: All locks held until commit/abort.
 * This is the most common variant in databases.
 */
class Strict2PLTransaction extends TwoPhaseLockingTransaction {
    // Override: Don't allow explicit lock release
    releaseLock(lock: Lock): void {
        throw new Error(
            'Strict 2PL does not allow explicit lock release. ' +
            'All locks are released at commit/abort.'
        );
    }
    
    // All locks released only at transaction end
    async commit(): Promise<void> {
        // Only now transition to shrinking and release
        await super.commit();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

                Lock Count
                    │
                    │        ┌── Maximum locks held
                    │       ╱│╲
                    │      ╱ │ ╲
                    │     ╱  │  ╲
                    │    ╱   │   ╲
                    │   ╱    │    ╲
                    │  ╱     │     ╲
                    │ ╱      │      ╲
                    │╱       │       ╲
          ──────────┼────────┼────────╲──────────── Time
                    │        │         ╲
                    │  GROWING   SHRINKING
                    │  PHASE     PHASE
                    │        │         │
              Transaction   Lock      Transaction
               starts      point       ends
 
    • Growing: Acquire locks, never release
    • Lock point: Maximum locks held
    • Shrinking: Release locks, never acquire
    
    DEADLOCK IS STILL POSSIBLE during growing phase!
    2PL ensures serializability, not deadlock freedom.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

class TimestampedTransaction {
    readonly id: string;
    readonly timestamp: number;  // Lower = older
    
    constructor(id: string) {
        this.id = id;
        this.timestamp = Date.now();
    }
}
 
type ConflictResolution = 'WAIT' | 'ABORT_REQUESTER' | 'ABORT_HOLDER';
 
class WaitDieScheme {
    resolveConflict(
        requester: TimestampedTransaction,
        holder: TimestampedTransaction
    ): ConflictResolution {
        if (requester.timestamp < holder.timestamp) {
            // Requester is OLDER: wait for younger to finish
            return 'WAIT';
        } else {
            // Requester is YOUNGER: abort and restart
            return 'ABORT_REQUESTER';  // "Die"
        }
    }
}
 
class WoundWaitScheme {
    resolveConflict(
        requester: TimestampedTransaction,
        holder: TimestampedTransaction
    ): ConflictResolution {
        if (requester.timestamp < holder.timestamp) {
            // Requester is OLDER: preempt younger holder
            return 'ABORT_HOLDER';  // "Wound"
        } else {
            // Requester is YOUNGER: wait for older to finish
            return 'WAIT';
        }
    }
}
 
// Example usage in lock manager
class DeadlockPreventingLockManager {
    private scheme: WaitDieScheme | WoundWaitScheme;
    private locks: Map<string, {
        holder: TimestampedTransaction;
        waiters: TimestampedTransaction[];
    }> = new Map();
    
    async acquire(
        lockId: string,
        transaction: TimestampedTransaction
    ): Promise<void> {
        const lockState = this.locks.get(lockId);
        
        if (!lockState) {
            // Lock is free
            this.locks.set(lockId, { holder: transaction, waiters: [] });
            return;
        }
        
        // Lock is held—apply conflict resolution
        const resolution = this.scheme.resolveConflict(
            transaction,
            lockState.holder
        );
        
        switch (resolution) {
            case 'WAIT':
                // Add to wait queue
                lockState.waiters.push(transaction);
                await this.waitForLock(lockId, transaction);
                break;
                
            case 'ABORT_REQUESTER':
                throw new AbortedError(`Transaction ${transaction.id} aborted (Wait-Die)`);
                
            case 'ABORT_HOLDER':
                // Preempt holder
                await this.abortTransaction(lockState.holder);
                lockState.holder = transaction;
                break;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

/**
 * Example of a well-designed service that minimizes deadlock risk.
 */
class UserAccountService {
    private lockManager = new OrderedLockManager();
    
    /**
     * Transfer between accounts with proper deadlock prevention.
     */
    async transfer(
        fromUserId: string,
        toUserId: string,
        amount: number
    ): Promise<TransferResult> {
        // 1. MINIMIZE LOCK SCOPE: Validate outside lock
        if (amount <= 0) {
            throw new ValidationError('Amount must be positive');
        }
        
        // 2. CONSISTENT ORDERING: Always lock by user ID order
        const [firstId, secondId] = [fromUserId, toUserId].sort();
        
        // 3. USE TIMEOUTS: Safety net for unforeseen issues
        const locks = await this.lockManager.acquireOrdered(
            [firstId, secondId],
            { timeoutMs: 5000 }
        );
        
        try {
            // 4. MINIMIZE TIME IN LOCK: Only essential operations
            const from = await this.getAccount(fromUserId);
            const to = await this.getAccount(toUserId);
            
            if (from.balance < amount) {
                throw new InsufficientFundsError();
            }
            
            from.balance -= amount;
            to.balance += amount;
            
            await this.saveAccounts([from, to]);
            
            return { success: true, newBalance: from.balance };
            
        } finally {
            // 5. ALWAYS RELEASE: Use finally block
            locks.releaseAll();
        }
    }
    
    /**
     * Read-only operations don't need exclusive locks.
     */
    async getBalance(userId: string): Promise<number> {
        // 6. AVOID LOCKS WHEN POSSIBLE: Read from eventually consistent cache
        const cached = this.cache.get(userId);
        if (cached) {
            return cached.balance;
        }
        
        // Only lock for cache miss
        const lock = await this.lockManager.acquireRead(userId, { timeoutMs: 1000 });
        try {
            const account = await this.getAccount(userId);
            this.cache.set(userId, account);
            return account.balance;
        } finally {
            lock.release();
        }
    }
}