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

2. In which scenario is a Translation Lookaside Buffer (TLB) most beneficial for system performance?

easy

A. When the system uses a single-level page table with very few page faults

B. When virtual memory accesses exhibit high temporal locality of page references

C. When the system has a very small physical memory and no paging

D. When all memory accesses are sequential and predictable

Solution

1. Step 1: Understand TLB purpose

   The TLB caches recent virtual-to-physical address translations to speed up address translation.

2. Step 2: Analyze each option

   A: High temporal locality means repeated accesses to the same pages, so TLB hits are frequent, improving performance.
   B: Single-level page tables are fast, but TLB benefits more when page tables are large.
   C: Small physical memory with no paging reduces need for TLB since address translation is trivial.
   D: Sequential accesses may not reuse the same pages quickly, reducing TLB hit rate.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   TLB effectiveness depends on locality of reference, which is captured by when virtual memory accesses exhibit high temporal locality of page references.

Hint: TLB shines when recent translations are reused quickly [OK]

Common Mistakes:

• Assuming TLB is always beneficial regardless of access pattern
• Confusing physical memory size with TLB usefulness

3. Why might using semaphores alone without a mutex in a producer-consumer system lead to incorrect behavior?

medium

A. Semaphores increase memory usage exponentially without mutex

B. Semaphores cannot block threads, so busy-waiting occurs

C. Semaphores cause deadlocks if used without mutexes

D. Semaphores do not provide mutual exclusion, so concurrent buffer access can corrupt data

Solution

1. Step 1: Role of semaphores

   Semaphores can block threads and track resource counts but do not inherently provide mutual exclusion.

2. Step 2: Need for mutual exclusion

   Without a mutex, multiple producers or consumers can simultaneously modify the buffer, causing race conditions and data corruption.

3. Step 3: Why other options are incorrect

   Semaphores cannot block threads, so busy-waiting occurs is false because semaphores do block; Semaphores cause deadlocks if used without mutexes is incorrect as deadlocks depend on usage, not absence of mutex; Semaphores increase memory usage exponentially without mutex is false as semaphores do not cause exponential memory growth.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Semaphores synchronize counts but mutex needed for exclusive buffer access [OK]

Hint: Semaphores count resources; mutex protects critical section

Common Mistakes:

• Assuming semaphores alone prevent race conditions
• Confusing blocking behavior of semaphores
• Believing mutexes cause deadlocks by default

4. Suppose a multithreaded application crashes due to a segmentation fault. Which of the following scenarios best explains why debugging is more challenging compared to a multi-process application?

hard

A. Because threads share the same memory, a fault in one thread can corrupt shared data, making root cause analysis harder

B. Because each thread has its own memory space, faults are isolated and easier to debug

C. Because thread context switches are slower, the fault is harder to reproduce

D. Because processes share memory, faults propagate easily between them

Solution

1. Step 1: Understand memory sharing in threads

   Threads share the same address space, so a fault in one thread can corrupt shared data affecting others.

2. Step 2: Contrast with processes

   Processes have isolated memory, so faults are contained, making debugging easier.

3. Step 3: Evaluate options

   Because each thread has its own memory space, faults are isolated and easier to debug is false because threads share memory. Because thread context switches are slower, the fault is harder to reproduce is false; thread context switch speed does not affect fault reproducibility. Because processes share memory, faults propagate easily between them is false; processes do not share memory by default.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Shared memory in threads complicates debugging due to data corruption [OK]

Hint: Shared memory means shared bugs [OK]

Common Mistakes:

• Assuming threads have isolated memory like processes
• Confusing context switch speed with debugging difficulty
• Believing processes share memory by default

5. If the buffer size in a producer-consumer system is increased dynamically at runtime, which challenge arises that the classic semaphore-based solution does NOT handle well?

hard

A. Consumers must signal the 'empty' semaphore twice per consumed item

B. The 'empty' semaphore count must be adjusted atomically to reflect new buffer slots

C. Producers will never block because buffer is always large enough

D. Mutex locks become ineffective with dynamic buffer sizes

Solution

1. Step 1: Classic solution assumes fixed buffer size

   Semaphore 'empty' initialized once to buffer size; dynamic resizing breaks this assumption.

2. Step 2: Adjusting semaphore counts

   When buffer grows, 'empty' semaphore must be incremented atomically to reflect new slots; otherwise, producers may block unnecessarily.

3. Step 3: Why other options are incorrect

   Consumers must signal the 'empty' semaphore twice per consumed item is false; consumers do not signal 'empty' twice. Mutex locks become ineffective with dynamic buffer sizes is false; mutex still protects critical section regardless of size. Producers will never block because buffer is always large enough is false; producers can still block if buffer is full.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Dynamic buffer size requires careful semaphore count updates [OK]

Hint: Dynamic buffer size requires dynamic semaphore adjustment

Common Mistakes:

• Assuming fixed semaphore counts suffice for dynamic buffers
• Thinking mutex depends on buffer size
• Misunderstanding producer blocking conditions