AnwarWelcome to Part 2 of our multithreading series!
In this part, we’ll dive deeper to understand starvation as it is essential for engineers, because it ensures fairness and system performance. By recognizing starvation risks, engineers can design systems that prioritize fairness, prevent resource monopolization, and ensure all threads get the necessary CPU time and resources to function optimally.
The Never-Ending Wait in Game Lobbies
Imagine you’re playing an online multiplayer game, and you’re trying to join a lobby for a popular game mode, like a team battle. You’ve been waiting in the lobby for a while, but every time a match starts, a new batch of players with faster internet or higher skill ranking gets prioritized and added to the game before you. You see matches starting over and over, but you never seem to get in!
You are technically in the queue, but because other players with faster response times or higher ranks keep getting into games first, you are left in the lobby indefinitely. Despite having a perfectly functional system, you’re denied the chance to play because of how the matchmaking algorithm unfairly prioritizes others.
1. Starvation
Starvation is a situation in which a process is continuously denied access to the resources it needs to proceed, even though those resources are available. The process remains in a waiting state because higher-priority processes or other resource allocation policies prevent it from acquiring the necessary resources. Unlike deadlock, the resources are not entirely unavailable, but the process is unable to access them due to unfair scheduling.
2. Causes
Priority Inversion: When a higher-priority process is waiting for a resource held by a lower-priority process, the lower-priority process may be starved of CPU time if other higher-priority processes keep arriving.
Resource Allocation Policies: Some scheduling algorithms may favor certain processes (usually those with higher priorities), leading to a situation where lower-priority processes are rarely allocated resources.
Poorly Designed Algorithms: If the resource allocation algorithm is not balanced or fair, it may lead to certain processes being continuously overlooked.
High Resource Demand: If a few processes demand an excessive amount of resources, they can starve other processes by monopolizing those resources.
Long Wait Times: Processes that are frequently preempted or that find themselves in competition for limited resources may experience starvation.
3. Preventing Starvation
- Using ReentrantLock with Fairness
Java’s ReentrantLock provides an option to enforce fairness. By using the ReentrantLock constructor with the true argument, we can ensure that threads acquire the lock in a first-come, first-served (FCFS) manner, preventing starvation.
private final Lock lock = new ReentrantLock(true); // Fair lock
- Using Semaphore for Fair Resource Sharing
A Semaphore is used to control access to a limited number of resources. By using a semaphore with fairness enabled, we can ensure that threads acquire permits in a fair order, avoiding starvation.
private final Semaphore sp = new Semaphore(1, true); // Fair semaphore
The Semaphore(1, true) is a semaphore with only one permit and fairness enabled.
- Avoiding Starvation in Producer-Consumer Problem (Using BlockingQueue)
In traditional producer-consumer problems, starvation may occur if the producer overwhelms the consumer or if consumers are denied access to the shared resource. BlockingQueue prevents this because it automatically handles synchronization between producers and consumers. Both the producer and consumer are blocked when the queue is full or empty, respectively. This ensures a fair balance between the two and prevents one from overwhelming the other, thus avoiding starvation.
- Using Java’s ForkJoinPool for Fair Task Scheduling
In scenarios where multiple tasks are forked and joined, ForkJoinPool in Java provides a way to balance the work fairly among threads. It ensures work-stealing, preventing starvation of less active threads. Java’s ForkJoinPool efficiently handles task splitting and balancing, ensuring that no thread starves for work. This is achieved using a work-stealing algorithm, where idle threads
stealtasks from busy threads to keep everything moving smoothly
4. How Operating System prevents Starvation
Operating systems (OS) use various techniques to avoid starvation—a situation where certain processes or threads are denied necessary resources (such as CPU time, memory, or I/O access) for prolonged periods because higher-priority tasks dominate. Here are some of the common ways an OS prevents starvation:
| No. | Method | Description | Prevents Starvation By |
|---|---|---|---|
| 1 | Aging | Gradually increases priority of waiting processes. | Prevents long waits by adjusting priority based on wait time. |
| 2 | Round-Robin Scheduling | Allocates CPU time in a fixed cyclic order. | Ensures all processes get CPU time, avoiding starvation. |
| 3 | Completely Fair Scheduler | Allocates CPU based on fairness, independent of priority. | Ensures fair distribution of CPU time. |
| 4 | Priority Boosting | Temporarily raises the priority of starved processes holding important resources. | Prevents priority inversion and ensures high-priority tasks get needed resources. |
| 5 | Multilevel Feedback Queues | Dynamically adjusts process priorities based on behavior. | Promotes long-waiting processes to higher-priority queues. |
| 6 | Semaphores with Fairness | Ensures fair access to resources through FIFO queues. | Prevents low-priority tasks from being perpetually blocked by higher-priority tasks. |
| 7 | Fair Resource Allocation | Distributes system resources like CPU and memory based on process demand and need. | Prevents resource-hogging processes from starving others. |
| 8 | Fair I/O Scheduling | Prioritizes I/O requests to ensure timely completion for all processes. | Prevents disk I/O starvation for processes making low-priority requests. |
By implementing these strategies, operating systems can ensure that no process or thread is indefinitely starved for resources, promoting a more fair and efficient use of system resources.
Key Takeaways for Software Engineers
- Starvation is a progress issue where a process keeps being denied access to a resource, but doesn’t necessarily involve other processes blocking it in a deadlock cycle. It is often caused by unfair scheduling or resource allocation.
- Starvation happens even though the resource it needs is available, but it never gets the chance to acquire it.
- Starvation also happens even when there is no deadlock on the system.
- Starvation can be a side effect of deadlock prevention (e.g., prioritizing certain processes to avoid deadlock), so it’s crucial to balance fairness with deadlock avoidance strategies.
Reference
A huge thanks to the online documentation, community and all the resources available that made this write-up possible.
