Questions
3–5 questions per university paper
Difficulty
Medium-Hard
Importance
High yield for core OS semester exams
Overview
Synchronization and Deadlocks are fundamental concepts in Operating Systems that manage concurrent process execution and resource allocation. Understanding these is critical for exams as they address how to prevent data inconsistency and system freezes when multiple processes access shared resources simultaneously.
The Critical Section Problem
The critical section is the part of code where a process accesses shared variables or resources that could lead to a race condition. To solve this, a protocol must satisfy three requirements: mutual exclusion, progress, and bounded waiting.
- Mutual Exclusion: Only one process enters its critical section at a time.
- Progress: If no process is in its critical section, only those outside can decide who enters next.
- Bounded Waiting: There exists a limit on the number of times other processes are allowed to enter their critical section after a request is made.
- Race Condition: Situation where output depends on the sequence or timing of uncontrollable events.
Semaphores & Mutex
Semaphores are integer variables used for process synchronization, while Mutex provides a locking mechanism to ensure mutual exclusion. Mutex is essentially a binary semaphore with ownership, meaning only the thread that locked it can unlock it.
- Binary Semaphore: Integer value ranges only between 0 and 1.
- Counting Semaphore: Integer value can range over an unrestricted domain.
- Wait (P) operation: Decrements the semaphore value.
- Signal (V) operation: Increments the semaphore value.
- Busy Waiting: A process remains in a loop checking the condition repeatedly.
Deadlock Detection & Prevention
Deadlock occurs when a set of processes are blocked because each process is holding a resource and waiting for another resource held by another process. Prevention involves ensuring that at least one of the four Coffman conditions cannot hold.
- Coffman Conditions: Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait.
- Deadlock Prevention: Negating one of the four Coffman conditions.
- Banker's Algorithm: Used for deadlock avoidance by simulating allocation for safe states.
- Resource Allocation Graph (RAG): Visual tool to detect potential circular waits.
- Deadlock Recovery: Terminating processes or preempting resources.
Formula Sheet
Wait(S): while(S <= 0); S--;
Signal(S): S++;
Exam Tip
Always draw a Resource Allocation Graph (RAG) when asked about deadlock detection, as it provides instant clarity and demonstrates conceptual mastery to examiners.
Common Mistakes
- Confusing Deadlock Avoidance (Banker's Algorithm) with Deadlock Prevention (restricting conditions).
- Failing to mention the three requirements (Mutual Exclusion, Progress, Bounded Waiting) when defining the Critical Section Problem.
- Assuming Mutex and Semaphores are identical without noting the 'ownership' difference.
More Revision Notes
Ready to test yourself?
Play topic-wise Synchronization & Deadlocks questions in Aspirant Arcade — gamified MCQ practice.
Download Free