Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 66 ยท Synchronization

Priority Inversion, Starvation, Aging and Livelock

Understand three ways threads fail to make progress without a deadlock: priority inversion, starvation fixed by aging, and livelock. Simulate each in Python.

Locks solve the race condition, but they bring a second family of problems: threads that are correct and safe, yet do not make progress when they should. A deadlock is the most famous, and it gets its own chapter. This lesson covers three others that are just as real: priority inversion, starvation and livelock.

Problem Is anyone running? Are threads blocked? Typical cause
Deadlock No one involved runs Yes, forever Circular wait for resources
Starvation Others run One (or a few) waits too long Unfair scheduling or locking
Livelock Yes, busily No, but no useful work Everyone keeps reacting to everyone
Priority inversion Yes A high-priority task waits on a low one Lock held by a low-priority thread

Priority inversion

Imagine three tasks with priorities High, Medium and Low. Low takes a mutex. High wakes up and also needs it, so High blocks and waits for Low. So far, that is normal. But now Medium wakes up. It does not need the lock, and it has higher priority than Low, so the scheduler runs Medium and Low cannot run to release the lock. High is stuck behind a medium-priority task that it should outrank: the priorities are inverted.

gantt
    title Priority inversion (no inheritance)
    dateFormat X
    axisFormat %s
    section Low
    holds the lock :a1, 0, 3
    finishes the lock late :a2, 11, 13
    section Medium
    runs for a long time :m1, 3, 11
    section High
    blocked on the lock :crit, h1, 2, 13
    runs :h2, 13, 15

High arrives at time 2 and needs the lock; Medium (arrival 3) keeps Low off the CPU until time 11.

The famous real case is the 1997 Mars Pathfinder probe, which kept resetting itself because a high-priority bus-management task waited on a mutex held by a low-priority task that was starved by medium-priority work. Engineers fixed it from Earth by enabling priority inheritance in the real-time operating system.

The cure: priority inheritance

While a low-priority thread holds a lock that a higher-priority thread wants, it temporarily inherits the higher priority. Medium can no longer preempt it. As soon as the lock is released, the priority drops back. (A related method, the priority ceiling protocol, gives each lock a ceiling equal to the highest priority of any thread that uses it.)

Let us simulate it tick by tick. A task's work is a list of segments: cpu (no lock) or lock (holding the shared mutex). The scheduler always runs the highest effective priority runnable task.

Python Priority inversion and inheritance

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Without inheritance, the timeline shows Medium (M) running its whole burst while H waits, and High finishes at tick 15. With inheritance, Low runs right after High blocks, releases the mutex quickly, and High finishes at tick 7, well before Medium.

Starvation and aging

Starvation (indefinite blocking) means a thread is ready to run but never gets the CPU or the lock. It happens when a policy always favours someone else: a priority scheduler where high-priority jobs keep arriving, a readers-preference lock with a constant flow of readers, or a "shortest job first" queue that always has a shorter job.

The standard cure is aging: the longer a thread waits, the more its priority grows. Eventually any waiting thread outranks the newcomers.

Python A low-priority job under a stream of high-priority ones

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Without aging the low job is still waiting when we stop watching. With aging it always runs eventually, and the knob (how fast priority grows) trades fairness against respecting priorities. Do not confuse starvation with deadlock: in starvation the system as a whole still makes progress, only one participant does not.

Livelock

In a livelock, threads are not blocked: they are running, changing state, and reacting to each other, but no progress is made. The textbook picture is two people meeting in a corridor: both step to the left to let the other pass, then both step right, and so on forever.

In code it appears when threads try to avoid deadlock by backing off in lockstep: each thread takes lock A, tries lock B, fails, releases A, and tries again, at the same pace as the other thread.

Python Polite threads, no progress

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Identical behaviour forever never makes progress, but even a small random backoff breaks the symmetry. This is exactly why Ethernet and Wi-Fi use randomized exponential backoff after a collision, and why retry loops in distributed systems add jitter.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What defines priority inversion?

    The medium-priority thread indirectly blocks the high-priority one because it prevents the lock holder from running.
  2. 2. How does priority inheritance solve it?

    Boosted, the holder can no longer be preempted by medium threads, finishes its critical section and releases the lock.
  3. 3. What is aging?

    Aging guarantees that a thread that waits long enough eventually outranks any newcomer.
  4. 4. Which statement describes livelock?

    Unlike deadlock the threads are active, but their reactions to each other prevent progress. Random backoff breaks the symmetry.
  5. 5. What distinguishes starvation from deadlock?

    In a deadlock no involved process can proceed. In starvation others proceed while one is passed over.

Summary

  • Priority inversion: a high-priority task waits on a lock held by a low-priority task that medium tasks keep from running. Priority inheritance (or ceilings) fixes it; Mars Pathfinder is the famous case.
  • Starvation is indefinite waiting caused by an unfair policy; aging raises priority with waiting time.
  • Livelock is busy but fruitless: symmetric polite retries. Randomized backoff breaks the pattern.
  • Deadlock, starvation and livelock are different failures; diagnose by asking who is running and who is blocked.

Next: Deadlock: The Four Conditions