Deadlock(OS) vs Deadlock(DBMS)

Deadlock in Operating Systems (OS)

What it means in OS

Processes (or threads) request resources (mutexes, files, devices, memory pages). A deadlock occurs when processes each hold some resources and wait forever for resources others hold.

Simple OS example (classic)

• Process P1 locks resource A, then tries to lock resource B.
• Process P2 locks resource B, then tries to lock resource A.
• Both block waiting for the other → deadlock.

Detection (OS)

• Build a resource-allocation graph or wait-for graph and detect cycles.
• Cycle detection via DFS. If cycle exists → deadlock.
• Complexity: graph traversal O(V+E).

Prevention & Avoidance (OS)

Prevention: disallow one Coffman condition (e.g., enforce ordering of resource acquisition, or disallow hold-and-wait by forcing processes to request all resources at once).

Avoidance: Banker's algorithm (process claims max resources; OS grants only if system stays in a safe state). Works well only with fixed, known maximums.

Recovery (OS)

• Preemption: forcibly take resources (if safe) and roll back process.
• Kill one or more processes (victim selection: low priority, least work done).
• Rollback and restart.

Deadlock in DBMS (databases)

What it means in DBMS

Transactions acquire locks (row/page/table locks) to ensure isolation. Two (or more) transactions can form a cycle waiting for locks the others hold.

DBMSs commonly use lock managers and wait-for graphs to detect deadlocks and resolve them automatically.
DB-specific concepts

Lock modes: Shared (S) vs Exclusive (X).

• Granularity: row, page, table — coarser locks increase chance of contention.
• Two-Phase Locking (2PL): transactions first acquire, then release only after commit/rollback. Strict 2PL holds exclusive locks until commit to ensure serializability — but increases deadlock chance.
• Wait-for graph: DB creates waits-for graph of transactions; cycles mean deadlock.

Detection (DBMS)

• DB periodically or on demand builds waits-for graph and detects cycles (pick a victim).
• Some systems use timeouts (if a transaction waits too long, abort it).
• Many RDBMS (MySQL/InnoDB, PostgreSQL) detect cycles and rollback one transaction.

Prevention & Avoidance (DBMS)

• Timeouts: simpler but may abort long legitimate waits.
• Ordering: acquire locks in consistent order by key or index (e.g., always acquire locks by primary key order).
• Optimistic concurrency: versioning (MVCC) avoids many locks for readers.
• Deadlock prevention protocols:
• Wait-die and Wound-wait (timestamp-based):
• Wait-die: older transaction waits for younger; younger requesting older will die (abort).
• Wound-wait: older transaction preempts (wounds) younger (younger aborts); younger waits for older otherwise.
• Avoid locking when possible: shorter transactions, proper indexing, accessing rows in deterministic order.

Recovery (DBMS)

• On deadlock detection, DB chooses a victim (roll back that transaction). Criteria: minimal work lost, lowest priority, few locks, etc.
• After rollback, other transactions continue; victim can retry.