If Account A transfers $100 to B while Account B simultaneously transfers $50 to A, Thread 1 locks A and requests B, while Thread 2 locks B and requests A. Without a total lock acquisition ordering (or database deadlock detection graphs like PostgreSQL's wait-for graph cycle detector), both transactions hang forever.
// POSIX Mutex vs Counting Semaphore in C
#include <pthread.h>
#include <semaphore.h>
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
sem_t sem_pool;
void* worker(void* arg) {
// 1. Mutex: Mutual exclusion with ownership
pthread_mutex_lock(&lock);
// Critical Section: Access shared counter
pthread_mutex_unlock(&lock);
// 2. Semaphore: Resource pool permit signaling
sem_wait(&sem_pool); // Decrement count (P / wait)
// Access pooled resource (e.g., DB Connection)
sem_post(&sem_pool); // Increment count (V / signal)
return NULL;
}Visual representation of control loops, memory layout, and execution flow for Process Synchronization, Critical Sections & Deadlocks.
Any valid synchronization solution must satisfy: 1) Mutual Exclusion (only one process in critical section at a time), 2) Progress (only processes waiting to enter participate in deciding who enters next), 3) Bounded Waiting (limit on how many times others enter before a waiting process is granted access).
Modern CPUs provide hardware-atomic instructions like Test-and-Set and Compare-and-Swap (CAS), forming the foundation for spinlocks and lock-free data structures.
Deadlock can ONLY occur if ALL 4 conditions hold simultaneously: 1) Mutual Exclusion, 2) Hold and Wait, 3) No Preemption, 4) Circular Wait.
Strategies: 1) Prevention (eliminate 1 Coffman condition), 2) Avoidance (Banker's Algorithm safe state checking), 3) Detection & Recovery (Resource Allocation Graph cycle detection + process termination), 4) Ignorance (Ostrich Algorithm used by Windows/Linux).
| Feature / Dimension | Mutex (Mutual Exclusion) | Counting Semaphore |
|---|---|---|
| Ownership Principle | Strict ownership: MUST be unlocked by the exact same thread that acquired it. | No ownership: Can be signaled (sem_post) by ANY thread or interrupt handler. |
| Value / Capacity | Binary state only (0 = locked, 1 = unlocked). | Non-negative integer counter representing available resource permits ($N$). |
| Waiting Mechanism | Thread is put to sleep by OS scheduler (context switched until awakened). | Thread sleeps if count is 0 until another thread signals `sem_post()`. |
| Primary Use Case | Protecting a single shared critical section variable or structure. | Managing a bounded pool of resources (e.g., 10 DB connections) or producer-consumer signaling. |
Detailed answers, interviewer pro tips, key takeaway summaries, and code examples formulated for technical rounds.
✅ Correction: In a Deadlock, two or more processes are permanently stuck in circular wait and NO progress is possible without external intervention. In Starvation (indefinite postponement), the system as a whole makes progress, but an unlucky low-priority process is perpetually bypassed.
✅ Correction: If a producer calls wait(mutex) before wait(empty), and the buffer happens to be full, the producer locks the buffer and sleeps waiting for empty space. The consumer cannot enter to consume because mutex is locked, causing a permanent deadlock.
Synchronization coordinates shared resource access; Deadlock is a state of permanent circular waiting.