Priority Inversion

 

Priority Inversion: Why Spin Locks Can Break Correctness

1. What Is Priority Inversion?

Priority inversion occurs when a high-priority thread is forced to wait for a lower-priority thread, while one or more medium-priority threads run instead.

👉 In effect, the system behaves opposite to what priorities intend.

• High priority → should run first ❌

• Low priority → indirectly controls the CPU ✅

This is not just a performance issue — it can be a correctness problem.

---

2. Why Spin Locks Make It Worse

Spin locks rely on busy waiting:

• A thread repeatedly checks whether a lock is available

• It does not block or sleep

• It keeps the CPU busy

If scheduling priorities are involved, this behavior can cause serious problems.

---

3. Two-Thread Priority Inversion Example

Scenario

Thread	Priority
T2	High
T1	Low

Assume:

• The scheduler always runs T2 if it is runnable

• T1 only runs when T2 is blocked

---

Step-by-Step Execution

1. T2 is blocked (e.g., waiting for I/O)

2. T1 runs, acquires a spin lock, and enters a critical section

3. T2 becomes unblocked

4. Scheduler immediately switches to T2 (higher priority)

5. T2 tries to acquire the spin lock

6. Lock is held by T1, so T2 starts spinning

---

What Goes Wrong?

• T2 is spinning → always runnable

• Scheduler keeps choosing T2 (highest priority)

• T1 never gets CPU time

• Lock is never released

👉 System hangs forever

---

Diagram

CPU
 |
 |-- T1 (low) acquires lock
 |-- T2 (high) wakes up
 |-- T2 spins forever
 |
T1 never runs → lock never released

---

4. Three-Thread Priority Inversion (Classic Case)

Threads and Priorities

Thread	Priority
T3	High
T2	Medium
T1	Low

---

Step-by-Step Execution

1. T1 (low) acquires a lock

2. T3 (high) becomes runnable and preempts T1

3. T3 tries to acquire the lock → blocked waiting for T1

4. T2 (medium) becomes runnable

5. Scheduler runs T2 (higher priority than T1)

6. T1 never runs, so the lock is never released

7. T3 waits indefinitely

---

Why This Is Called “Inversion”

Expected order:   T3 > T2 > T1
Actual control:   T2 > T1 > T3

The lowest-priority thread indirectly blocks the highest-priority thread.

---

5. Why This Is a Correctness Problem

Priority inversion can cause:

• Deadlock-like behavior

• Missed real-time deadlines

• System hangs

• Unpredictable scheduling

This is why priority inversion has caused real-world system failures (including space missions 🚀).

---

6. Why Avoiding Spin Locks Helps

Spin locks:

• Keep high-priority threads runnable

• Prevent low-priority lock holders from running

• Make inversion worse

Blocking locks:

• Put waiting threads to sleep

• Allow lock holders to run and release the lock

---

7. Solutions to Priority Inversion

1. Avoid Spin Locks

• Especially in user-level code

• Especially on single-CPU systems

---

2. Priority Inheritance (Most Important)

When:

• High-priority thread waits for a lock held by a low-priority thread

Then:

• Temporarily raise the priority of the lock holder

👉 Low-priority thread runs faster, releases lock, system recovers

---

3. Priority Ceiling (Advanced)

• Locks have a predefined priority ceiling

• Threads acquire elevated priority when holding locks

---

4. Equal Priorities

• Simplest solution

• Not practical for real-time systems

---

8. Key Takeaways 

• Priority inversion occurs when low-priority threads block high-priority ones

• Spin locks can cause infinite spinning under priority scheduling

• Medium-priority threads can worsen the problem

• Priority inversion affects correctness, not just performance

• Priority inheritance is the standard solution