Preventing Starvation

Core Concept
Preventing starvation requires bounded waiting: the time any thread waits must be provably finite. This needs cooperation between your code, the scheduler, and your synchronization primitives.
Strong vs Weak Semaphores
Weak semaphore: When you signal, some waiting thread wakes up. No guarantee which one. A thread could theoretically wait forever.
Strong semaphore: Uses FIFO queue. When you signal, the thread that waited longest wakes up. Once you join the queue, a bounded number of threads can go ahead of you.
Most modern systems provide strong semaphores (FIFO). But do not assume - check your platform documentation.
The Turnstile Pattern
Morris solved starvation using two turnstiles creating a waiting room. The key insight: batch threads into groups. Current batch finishes before new arrivals can proceed.
Phase 1: New threads enter waiting room, first turnstile open.
Phase 2: First turnstile closes, second opens. Waiting threads proceed to critical section.
New arrivals must wait for next cycle. Nobody can cut in line indefinitely.
Practical Prevention Strategies
Fair locks: Use locks with FIFO acquisition order (ReentrantLock(true) in Java).
Priority aging: Gradually increase priority of waiting threads. Eventually even low-priority threads become high-priority.
Turnstile for readers-writers: When a writer arrives, close a turnstile. Existing readers finish, writer proceeds, then readers continue.
Design Principle: Use FIFO-ordered primitives when fairness matters. Accept that fairness often costs throughput - batching and priority can help balance both.

💡 Key Takeaways

✓Bounded waiting: maximum wait time must be provably finite

✓Strong semaphores (FIFO) guarantee fairness - weak semaphores allow starvation

✓Turnstile pattern: batch threads, close entry, process batch, reopen - prevents cutting in line

✓Fair locks: FIFO acquisition order ensures first-come-first-served

✓Priority aging: gradually increase waiting thread priority until it runs

📌 Examples

1Java ReentrantLock(true): fair mode uses FIFO queue, prevents thread starvation

2No-starve readers-writers: turnstile blocks new readers when writer is waiting

3Linux CFS scheduler: uses aging to ensure low-priority processes eventually run

← Back to Livelock & Starvation Overview