Three processes P1, P2, and P3 are created. Two resources R1 and R2 are available but not allocated. All processes start in the ready state.
💡 Setting up the initial state with all processes ready and resources free is essential to observe how resource requests lead to concurrency problems.
Line:processes = ['P1', 'P2', 'P3']
resources = {'R1': None, 'R2': None}
process_states = {p: 'ready' for p in processes}
💡 Initial conditions are clear: no resource is held, no process is waiting or blocked.
insert
P1 Requests Resource R1
Process P1 requests resource R1. Since R1 is free, it is allocated to P1 immediately. P1 continues running.
💡 Resource allocation on request is the first step to see how processes acquire resources and how contention might arise later.
Line:if resources['R1'] is None:
resources['R1'] = 'P1'
process_states['P1'] = 'running'
💡 Resource allocation is granted immediately if free, allowing process to run.
insert
P2 Requests Resource R2
Process P2 requests resource R2. Since R2 is free, it is allocated to P2 immediately. P2 moves to running state.
💡 Another resource allocation shows multiple processes can hold different resources simultaneously.
Line:if resources['R2'] is None:
resources['R2'] = 'P2'
process_states['P2'] = 'running'
💡 Multiple resources can be allocated concurrently to different processes.
insert
P3 Requests Resource R1 (Held by P1)
Process P3 requests resource R1, but R1 is currently held by P1. P3 cannot proceed and moves to waiting state for R1.
💡 This step introduces waiting due to resource contention, a key condition for starvation and deadlock.
Line:if resources['R1'] is not None:
process_states['P3'] = 'waiting'
waiting_queue.append({'pid': 'P3', 'waiting_for': 'R1'})
💡 Processes block when requested resources are unavailable, causing waiting queues.
insert
P1 Requests Resource R2 (Held by P2) - Deadlock Begins
Process P1 requests resource R2, but R2 is held by P2. P1 cannot proceed and moves to waiting state for R2, causing circular wait with P2.
💡 This circular waiting is the hallmark of deadlock, where processes wait indefinitely for each other's resources.
Line:if resources['R2'] is not None:
process_states['P1'] = 'waiting'
waiting_queue.append({'pid': 'P1', 'waiting_for': 'R2'})
💡 Deadlock arises when processes hold resources and wait for others held by each other.
insert
P2 Requests Resource R1 (Held by P1) - Deadlock Confirmed
Process P2 requests resource R1, but R1 is held by P1. P2 cannot proceed and moves to waiting state for R1, completing the circular wait and confirming deadlock.
💡 This step completes the deadlock cycle where P1 waits for P2 and P2 waits for P1, both blocked indefinitely.
Line:if resources['R1'] is not None:
process_states['P2'] = 'waiting'
waiting_queue.append({'pid': 'P2', 'waiting_for': 'R1'})
💡 Deadlock occurs when a cycle of resource waiting exists among processes.
expand
P3 Repeatedly Attempts to Acquire R1 and Releases R2 - Livelock
Process P3 repeatedly tries to acquire R1 but fails because P1 holds it. P3 releases and reacquires other resources in a loop, changing states but making no progress, illustrating livelock.
💡 Livelock differs from deadlock because processes are active but stuck in a cycle of state changes without progress.
Line:while not acquired:
try_acquire('R1')
if fail:
release('R2')
reacquire('R2')
💡 Livelock is a state of continuous activity without progress due to repeated resource release and reacquire.
prune
P1 Starved Waiting for R2 Held by P2
P1 has been waiting for R2 held by P2 for a long time without progress. P1 is starved because P2 never releases R2 due to deadlock.
💡 Starvation occurs when a process waits indefinitely because others monopolize resources or scheduling favors others.
Line:# P1 waits indefinitely for R2
# No resource release from P2 due to deadlock
💡 Starvation is a lopsided waiting condition caused by resource or scheduling unfairness.
compare
Detect Deadlock Cycle
The system detects a circular wait cycle involving P1 and P2 waiting on each other's resources, confirming deadlock.
💡 Detecting deadlock requires identifying cycles in the resource allocation graph.
💡 Deadlock detection algorithms identify cycles in wait-for graphs.
reconstruct
Summary: Starvation, Deadlock, and Livelock States
Final states show P1 starved waiting for R2, P1 and P2 deadlocked waiting on each other, and P3 livelocked cycling resource requests without progress.
💡 This final step consolidates the differences by showing each problem's manifestation in process states and resource allocation.
Line:# Final states reflect starvation, deadlock, and livelock conditions
💡 Starvation is indefinite waiting due to unfairness, deadlock is circular waiting, and livelock is active but unproductive state changes.
processes = ['P1', 'P2', 'P3'] # STEP 1
resources = {'R1': None, 'R2': None} # STEP 1
process_states = {p: 'ready' for p in processes} # STEP 1
# STEP 2
if resources['R1'] is None:
resources['R1'] = 'P1'
process_states['P1'] = 'running'
# STEP 3
if resources['R2'] is None:
resources['R2'] = 'P2'
process_states['P2'] = 'running'
# STEP 4
if resources['R1'] is not None:
process_states['P3'] = 'waiting'
waiting_queue = [{'pid': 'P3', 'waiting_for': 'R1'}]
# STEP 5
if resources['R2'] is not None:
process_states['P1'] = 'waiting'
waiting_queue.append({'pid': 'P1', 'waiting_for': 'R2'})
# STEP 6
if resources['R1'] is not None:
process_states['P2'] = 'waiting'
waiting_queue.append({'pid': 'P2', 'waiting_for': 'R1'})
# STEP 7
# P3 tries repeatedly to acquire R1 but fails, releasing and reacquiring other resources
while True:
acquired = try_acquire('R1')
if not acquired:
release('R2')
reacquire('R2')
else:
break
# STEP 8
# P1 starved waiting for R2 held by P2
# STEP 9
def detect_cycle(waiting_queue):
# Detect circular wait
return True # Deadlock detected
deadlock = detect_cycle(waiting_queue)
# STEP 10
# Final states reflect starvation, deadlock, and livelock
📊
Starvation vs Deadlock vs Livelock - Differences & Examples - Watch the Algorithm Execute, Step by Step
Watching the processes' states and resource allocations step-by-step reveals the subtle differences between these common concurrency problems that are hard to grasp from code or definitions alone.
Step 1/10
·Active fill★Answer cell
Transitionnone → ready - initialization
P1
ready
P2
ready
P3
ready
Ready Queue
P1P2P3
Waiting Queue
empty
🖥CPUidlet=0
Transitionready → running pid:P1 - allocated R1
P1
running
P2
ready
P3
ready
Ready Queue
P2P3
Waiting Queue
empty
🖥CPUP1t=1
P1
Transitionready → running pid:P2 - allocated R2
P1
running
P2
running
P3
ready
Ready Queue
P3
Waiting Queue
empty
🖥CPUP2t=2
P1
P2
Transitionready → waiting pid:P3 - R1 held by P1
P1
running
P2
running
P3
waiting
Ready Queue
empty
Waiting Queue
P3 (R1)
🖥CPUP1t=3
P1
P2
P1
Transitionrunning → waiting pid:P1 - R2 held by P2
P1
waiting
P2
running
P3
waiting
Ready Queue
empty
Waiting Queue
P3 (R1)P1 (R2)
🖥CPUP2t=4
P1
P2
P1
P2
Transitionrunning → waiting pid:P2 - R1 held by P1
Transitionvarious → final - summary of concurrency problems
P1
waiting (starved)
P2
waiting (deadlocked)
P3
running (livelocked)
Ready Queue
empty
Waiting Queue
P1 (R2)P2 (R1)
🖥CPUP3t=9
P1
P2
P1
P2
idle
P3
Key Takeaways
✓ Deadlock occurs when processes form a circular wait, each holding a resource the other needs.
This is hard to see from code alone because it requires visualizing resource dependencies and waiting chains.
✓ Starvation is a form of indefinite waiting caused by unfair resource allocation or scheduling bias.
Understanding starvation requires seeing how some processes never get resources despite availability.
✓ Livelock involves processes actively changing states and resources but making no forward progress.
Livelock is subtle because processes are not blocked but stuck in a loop of futile actions.
Practice
(1/5)
1. Trace the sequence of state transitions for a process that requests I/O while running and then completes the I/O operation. What is the correct order of states the process goes through?
easy
A. Running -> Waiting -> Ready -> Running
B. Running -> Ready -> Waiting -> Running
C. Running -> Waiting -> Running -> Ready
D. Running -> Ready -> Running -> Waiting
Solution
Step 1: Identify the event
The process requests I/O while Running, so it must wait for I/O completion.
Step 2: State transition on I/O request
Process moves from Running to Waiting state to wait for I/O.
Step 3: After I/O completes
Process moves from Waiting to Ready state, waiting for CPU scheduling.
Step 4: CPU scheduling
Process moves from Ready to Running when CPU is allocated.
Hint: I/O request moves process Running -> Waiting, then Waiting -> Ready after I/O completes [OK]
Common Mistakes:
Confusing Ready and Waiting states order
Assuming process goes directly from Waiting to Running
Skipping the Ready state after I/O completion
2. Consider a producer-consumer system using semaphores: when a producer produces an item, what is the correct sequence of semaphore operations to ensure proper synchronization?
easy
A. Wait on 'empty' semaphore, wait on mutex, add item, signal mutex, signal 'full' semaphore
B. Wait on mutex, wait on 'empty' semaphore, add item, signal 'full' semaphore, signal mutex
C. Wait on 'full' semaphore, wait on mutex, add item, signal mutex, signal 'empty' semaphore
D. Signal 'empty' semaphore, wait on mutex, add item, signal 'full' semaphore, wait on 'full' semaphore
Producer waits (P operation) on 'empty' to ensure space is available before producing.
Step 3: Acquire mutex before modifying buffer
Mutex wait ensures exclusive access to buffer.
Step 4: Add item, then release mutex
After adding, signal (V operation) mutex to release critical section.
Step 5: Signal 'full' to indicate new item
Signaling 'full' wakes consumers waiting for items.
Step 6: Why other options fail
Wait on 'full' semaphore, wait on mutex, add item, signal mutex, signal 'empty' semaphore waits on 'full' which is incorrect; Wait on mutex, wait on 'empty' semaphore, add item, signal 'full' semaphore, signal mutex waits on mutex before 'empty' which can cause deadlock; Signal 'empty' semaphore, wait on mutex, add item, signal 'full' semaphore, wait on 'full' semaphore signals before waiting, breaking synchronization.
Final Answer:
Option A -> Option A
Quick Check:
Wait empty -> wait mutex -> produce -> signal mutex -> signal full [OK]
Hint: Producer waits on empty, consumer waits on full
Common Mistakes:
Confusing 'full' and 'empty' semaphore roles
Incorrect order of mutex and semaphore waits
Signaling before waiting causing race
3. Which of the following statements about context switching is INCORRECT?
medium
A. Context switching involves saving the current process's CPU state into its PCB
B. The scheduler directly saves and restores CPU registers during a context switch
C. Context switches can be triggered by interrupts or system calls
D. Frequent context switches increase CPU overhead and reduce throughput
Solution
Step 1: Verify saving CPU state
Saving CPU state to PCB is true and essential for context switching.
Step 2: Scheduler role
The scheduler decides which process runs next but does not perform register saving/restoring; this is done by the OS kernel and hardware mechanisms.
Step 3: Triggers for context switch
Interrupts and system calls can trigger context switches, so this is correct.
Step 4: Overhead of frequent switches
Frequent context switches increase overhead and reduce throughput, which is true.
Final Answer:
Option B -> Option B
Quick Check:
Scheduler does not directly save/restore registers; it manages process selection.
4. Which of the following statements about the FIFO page replacement algorithm is INCORRECT?
medium
A. FIFO always evicts the least recently used page
B. FIFO can suffer from Belady's anomaly where increasing frames increases page faults
C. FIFO is simple to implement with a queue data structure
D. FIFO does not consider how frequently or recently a page was accessed
Solution
Step 1: Understand FIFO Eviction Policy
FIFO evicts the oldest loaded page, not the least recently used.
Step 2: Evaluate Each Option
FIFO can suffer from Belady's anomaly where increasing frames increases page faults is correct; Belady's anomaly can occur with FIFO. FIFO always evicts the least recently used page is incorrect; FIFO does not track recency of use. FIFO is simple to implement with a queue data structure is correct; FIFO uses a queue for eviction order. FIFO does not consider how frequently or recently a page was accessed is correct; FIFO ignores frequency and recency.
Final Answer:
Option A -> Option A
Quick Check:
FIFO evicts by arrival order, not usage recency.
Hint: FIFO evicts oldest loaded page, not least recently used [OK]
Common Mistakes:
Confusing FIFO with LRU eviction criteria
Assuming FIFO tracks page usage
Believing FIFO cannot have anomalies
5. Why is it generally inefficient to implement all OS services as system calls requiring mode switches?
medium
A. Because mode switches cause significant CPU overhead and latency
B. Because system calls cannot access hardware devices
C. Because user mode has unrestricted access to kernel data structures
D. Because system calls bypass the CPU privilege checks
Solution
Step 1: Understand mode switch cost
Switching from user to kernel mode involves saving/restoring CPU state and flushing pipelines, which is expensive.
Step 2: Why not all services as system calls
Excessive mode switches degrade performance, so only critical OS services use system calls.
Step 3: Why other options are incorrect
Because system calls cannot access hardware devices is false; system calls are the mechanism to access hardware safely. Because user mode has unrestricted access to kernel data structures is false; user mode is restricted from kernel data. Because system calls bypass the CPU privilege checks is false; system calls enforce privilege checks via mode switch.
Final Answer:
Option A -> Option A
Quick Check:
Mode switch overhead limits system call usage [OK]
Hint: Mode switches are costly, so minimize system calls
Common Mistakes:
Believing system calls cannot access hardware
Thinking user mode has full kernel access
Assuming system calls skip privilege checks
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.