Starvation vs Deadlock vs Livelock - Differences & Examples

▶

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.

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.

Line:

if detect_cycle(waiting_queue):
    deadlock = True

💡 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.

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. In which scenario is First-Come, First-Served (FCFS) scheduling most appropriate to use?

easy

A. When all processes have similar CPU burst times and arrival times

B. When minimizing average waiting time is the highest priority

C. When process arrival times are unpredictable and preemption is required

D. When simplicity and fairness in process order are more important than responsiveness

Solution

1. Step 1: Understand FCFS characteristics

   FCFS schedules processes in the order they arrive without preemption, making it simple and fair in terms of arrival order.

2. Step 2: Analyze each option

   A is incorrect because FCFS does not optimize for similar burst times; it just queues by arrival.
   B is incorrect because FCFS can cause long waiting times if a long process arrives first.
   C is incorrect because FCFS is non-preemptive and does not handle unpredictable arrivals well.
   D is correct because FCFS's main advantage is simplicity and fairness in order, not responsiveness or waiting time optimization.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   FCFS is chosen for simplicity and fairness, not for minimizing waiting time or handling preemption.

Hint: FCFS = simple, fair order, not optimized for waiting time

Common Mistakes:

• Assuming FCFS minimizes average waiting time
• Confusing FCFS with preemptive scheduling
• Believing FCFS handles unpredictable arrivals efficiently

2. In which scenario is the Process Control Block (PCB) primarily used during the process state transitions in the five-state model?

easy

A. When a process moves from New to Ready state to store initial process information

B. When a process is terminated to delete all its data from memory

C. When a process is in the Ready state to execute instructions directly

D. When a process moves from Running to Waiting state to save CPU registers and state

Solution

1. Step 1: Understand the role of PCB during state transitions

   The PCB stores the process state, CPU registers, and scheduling information during context switches.

2. Step 2: Analyze each option

   A: PCB is created at process creation but its primary use is during context switches, not just at New to Ready.
   B: PCB is involved in termination but mainly to release resources; it is not primarily used to delete data.
   C: Processes in Ready state do not execute instructions directly; they wait for CPU allocation.
   D: Correct. When a process moves from Running to Waiting, the PCB saves CPU registers and state for resumption.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   PCB is essential for saving CPU state during Running to Waiting transitions [OK]

Hint: PCB saves CPU state during Running to Waiting transitions [OK]

Common Mistakes:

• Thinking PCB is only used at process creation
• Assuming Ready state processes execute instructions
• Believing PCB is deleted immediately at termination

3. Which of the following statements about thrashing and the working set model is INCORRECT?

medium

A. Thrashing occurs when the sum of all processes' working sets exceeds total available frames

B. The working set model dynamically adjusts the number of frames allocated to each process based on recent page usage

C. Increasing the total number of processes always reduces thrashing by distributing memory pressure

D. Load control can be used alongside the working set model to prevent thrashing by limiting the number of active processes

Solution

1. Step 1: Analyze each statement

   A is correct: thrashing happens when total working sets exceed memory.
   B is correct: working set model adjusts frames dynamically.
   C is incorrect: increasing processes usually increases memory pressure, worsening thrashing.
   D is correct: load control limits active processes to prevent thrashing.

2. Final Answer:

   Option C -> Option C

3. Quick Check:

   More processes usually increase thrashing risk, not reduce it.

Hint: More processes -> more memory pressure -> more thrashing

Common Mistakes:

• Believing more processes reduce thrashing
• Confusing load control with working set adjustments
• Ignoring total memory constraints

4. Which of the following statements about the trade-offs of increasing TLB size is TRUE?

medium

A. A bigger TLB eliminates the need for page tables

B. Increasing TLB size always reduces effective access time without any downside

C. TLB size does not affect power consumption or chip area significantly

D. A larger TLB may increase lookup time, potentially offsetting hit rate benefits

Solution

1. Step 1: Understand TLB size impact

   Larger TLB can cache more translations, increasing hit rate.

2. Step 2: Consider trade-offs

   However, larger TLBs have longer lookup times and consume more power and chip area.

3. Step 3: Analyze options

   A: Correct, bigger TLBs have diminishing returns and increased latency.
   B: Incorrect, increasing size does not always reduce access time without downsides.
   C: Incorrect, larger TLBs increase power and area.
   D: Incorrect, page tables remain necessary for full address translation.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Trade-offs include lookup latency and hardware cost, not just hit rate.

Hint: Bigger TLB -> better hit rate but slower lookup and more power [OK]

Common Mistakes:

• Assuming bigger TLB is always better
• Ignoring hardware cost and latency

5. If a system call is invoked from an interrupt handler already running in kernel mode, what is the expected behavior regarding mode switching and privilege checks?

hard

A. The system call is deferred until the interrupt handler finishes and user mode resumes.

B. The CPU switches to user mode before executing the system call to prevent privilege escalation.

C. The system call executes immediately without a mode switch since already in kernel mode.

D. The system call triggers a nested mode switch to a higher privilege level.

Solution

1. Step 1: Understand current mode

   Interrupt handlers run in kernel mode with full privileges.

2. Step 2: System call invoked in kernel mode

   Since already in kernel mode, no mode switch is needed; system call executes directly.

3. Step 3: Why other options are incorrect

   The CPU switches to user mode before executing the system call to prevent privilege escalation. is incorrect; switching to user mode would reduce privileges improperly. The system call is deferred until the interrupt handler finishes and user mode resumes. is wrong; system calls are not deferred. The system call triggers a nested mode switch to a higher privilege level. is false; kernel mode is the highest privilege level, no nested switch occurs.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   System call in kernel mode -> no mode switch -> immediate execution [OK]

Hint: No mode switch if already in kernel mode

Common Mistakes:

• Assuming mode switch always occurs on system call
• Thinking system calls are deferred inside kernel
• Believing nested privilege levels exist beyond kernel mode