Chapter 13: Starvation

In this chapter, we will discuss the concept of starvation and its potential causes in concurrent programming. We will cover a number of variations of the readers-writers problems, which are prime examples of starvation, and we will simulate them in example Python code. This chapter will also cover the relationship between deadlock and starvation, as well as some potential solutions for starvation.

The following topics will be covered in this chapter:

• Understanding starvation
• Approaching the readers-writers problem
• Solutions to starvation

By the end of the chapter, you will have a deep understanding of starvation, what causes it, and what practical solutions can be implemented to address the problem.

Technical requirements

The code files for this chapter can be accessed through this link: https://github.com/PacktPublishing/Advanced-Python-Programming-Second-Edition/tree/main/Chapter13.

Understanding starvation

Starvation is a problem in concurrent systems, in which a process (or a thread) cannot gain access to the necessary resources in order to proceed with its execution and, therefore, cannot make any progress. In this section, we will look into the characteristics of a starvation situation, analyze its most common causes, and finally, consider a sample program that exemplifies starvation.

What is starvation?

It is quite common for a concurrent program to implement some sort of ordering between the different processes in its execution. For example, consider a program that has three separate processes, as follows:

• One is responsible for handling extremely pressing instructions that need to be run as soon as the necessary resources become available.
• Another process is responsible for other important executions, which are not as essential as the tasks in the first process.
• The last one handles miscellaneous, very infrequent tasks.

Furthermore...

Approaching the readers-writers problem

The readers-writers problem is one of the classic use cases in concurrent programming, illustrating problems that might occur in a concurrent program. Throughout the analysis of the different variations of the readers-writers problem, we will reveal more about starvation, as well as its common causes. We will also simulate the problem in Python so that a deeper understanding of the problem can be gained.

Problem statement

In a readers-writers problem, first and foremost, we have a shared resource, which, in most cases, is a text file. Different threads interact with that text file; each is either a reader or a writer. A reader is a thread that simply accesses the shared resource (the text file) and reads in the data included in that file, while a writer is a thread that accesses, and possibly mutates, the contents of the text file.

We know that writers and readers cannot access the shared resources simultaneously since if a thread is...

Solutions to starvation

Through an analysis of different approaches to the readers-writers problem, you have seen the key to solving starvation – since some threads will be starved if they are not given a high priority in accessing the shared resources, implementing fairness in the execution of all of the threads will prevent starvation from occurring. Fairness, in this case, does not require a program to forgo any order or priority that it has imposed on the different threads; but to implement fairness, a program needs to ensure that all threads are given sufficient opportunities to execute their instructions.

Keeping this idea in mind, we can potentially address the problem of starvation by implementing one (or a combination) of the following approaches:

• Increasing the priority of low-priority threads: As we did with the writer threads in the second approach and the reader threads in the third approach to the readers-writers problem, prioritizing the threads that...

Summary

In this chapter, we have covered starvation and the specific situations in which it could occur by analyzing different instances of the readers-writers problem. We have gained insight into how starvation can be solved with different scheduling algorithms – by making sure that the priority is distributed appropriately among different processes and threads, starvation can be eliminated. These discussions will serve as a guide to solutions to real-life instances of starvation.

In the next chapter, we will discuss the last of the three common problems of concurrent programming – race conditions. We will cover the basic foundation and causes of race conditions, relevant concepts, and the connection of race conditions to other concurrency-related problems.

Questions

1. What is starvation and why is it undesirable in a concurrent program?
2. What are the underlying causes of starvation? What are the common high-level causes of starvation that can manifest from the underlying causes?
3. What is the connection between deadlock and starvation?
4. What is the readers-writers problem?
5. What is the first approach to the readers-writers problem? Why does starvation arise in that situation?
6. What is the second approach to the readers-writers problem? Why does starvation arise in that situation?
7. What is the third approach to the readers-writers problem? Why does it successfully address starvation?
8. What are some common solutions to starvation?

Further reading

• Parallel Programming with Python, Jan Palach, Packt Publishing Ltd, 2014
• Python Parallel Programming Cookbook, Giancarlo Zaccone, Packt Publishing Ltd, 2015
• Starvation and Fairness, Jakob Jenkov (tutorials.jenkov.com/java-concurrency/starvation-and-fairness)
• Faster Fair Solution for the Reader-Writer Problem, V. Popov and O. Mazonka