Bird
Raised Fist0
Interview Prepoperating-systemsmediumAmazonGoogleMicrosoftTCSInfosys

Starvation vs Deadlock vs Livelock - Differences & Examples

Choose your preparation mode3 modes available
▶
Steps
setup

Initialize Processes and Resources

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.
📊
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
Transition none → ready - initialization
P1
ready
P2
ready
P3
ready
Ready Queue
P1P2P3
Waiting Queue
empty
🖥CPUidlet=0
Transition ready → running pid:P1 - allocated R1
P1
running
P2
ready
P3
ready
Ready Queue
P2P3
Waiting Queue
empty
🖥CPUP1t=1
P1
Transition ready → running pid:P2 - allocated R2
P1
running
P2
running
P3
ready
Ready Queue
P3
Waiting Queue
empty
🖥CPUP2t=2
P1
P2
Transition ready → 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
Transition running → 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
Transition running → waiting pid:P2 - R1 held by P1
P1
waiting
P2
waiting
P3
waiting
Ready Queue
empty
Waiting Queue
P3 (R1)P1 (R2)P2 (R1)
🖥CPUidlet=5
P1
P2
P1
P2
idle
Transition waiting → running pid:P3 - attempting livelock resource cycling
P1
waiting
P2
waiting
P3
running
Ready Queue
empty
Waiting Queue
P1 (R2)P2 (R1)
🖥CPUP3t=6
P1
P2
P1
P2
idle
P3
Transition waiting → waiting pid:P1 - starvation due to deadlock
P1
waiting
P2
waiting
P3
running
Ready Queue
empty
Waiting Queue
P1 (R2)P2 (R1)
🖥CPUP3t=7
P1
P2
P1
P2
idle
P3
Transition waiting → waiting pid:system - deadlock detection
P1
waiting
P2
waiting
P3
running
Ready Queue
empty
Waiting Queue
P1 (R2)P2 (R1)
🖥CPUP3t=8
P1
P2
P1
P2
idle
P3
Transition various → 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

  1. Step 1: Identify the event

    The process requests I/O while Running, so it must wait for I/O completion.
  2. Step 2: State transition on I/O request

    Process moves from Running to Waiting state to wait for I/O.
  3. Step 3: After I/O completes

    Process moves from Waiting to Ready state, waiting for CPU scheduling.
  4. Step 4: CPU scheduling

    Process moves from Ready to Running when CPU is allocated.
  5. Final Answer:

    Option A -> Option A
  6. Quick Check:

    Running -> Waiting (I/O request), Waiting -> Ready (I/O done), Ready -> Running (CPU assigned) [OK]
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

Solution

  1. Step 1: Understand semaphore roles

    'empty' counts available buffer slots; 'full' counts filled slots; mutex protects buffer access.
  2. Step 2: Producer must wait for empty slot

    Producer waits (P operation) on 'empty' to ensure space is available before producing.
  3. Step 3: Acquire mutex before modifying buffer

    Mutex wait ensures exclusive access to buffer.
  4. Step 4: Add item, then release mutex

    After adding, signal (V operation) mutex to release critical section.
  5. Step 5: Signal 'full' to indicate new item

    Signaling 'full' wakes consumers waiting for items.
  6. 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.
  7. Final Answer:

    Option A -> Option A
  8. 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

  1. Step 1: Verify saving CPU state

    Saving CPU state to PCB is true and essential for context switching.
  2. 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.
  3. Step 3: Triggers for context switch

    Interrupts and system calls can trigger context switches, so this is correct.
  4. Step 4: Overhead of frequent switches

    Frequent context switches increase overhead and reduce throughput, which is true.
  5. Final Answer:

    Option B -> Option B
  6. Quick Check:

    Scheduler does not directly save/restore registers; it manages process selection.
Hint: Scheduler selects process, kernel saves/restores registers [OK]
Common Mistakes:
  • Assuming scheduler handles register saving
  • Confusing triggers of context switch
  • Underestimating overhead of frequent switches
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

  1. Step 1: Understand FIFO Eviction Policy

    FIFO evicts the oldest loaded page, not the least recently used.
  2. 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.
  3. Final Answer:

    Option A -> Option A
  4. 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

  1. Step 1: Understand mode switch cost

    Switching from user to kernel mode involves saving/restoring CPU state and flushing pipelines, which is expensive.
  2. Step 2: Why not all services as system calls

    Excessive mode switches degrade performance, so only critical OS services use system calls.
  3. 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.
  4. Final Answer:

    Option A -> Option A
  5. 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 unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard