Last Updated on September 12, 2022
You can starve a thread of execution, which is a concurrency failure mode called thread starvation.
In this tutorial you will discover thread starvation and how to fix it in Python.
Let’s get started.
What is Thread Starvation
Thread starvation is a concurrency failure mode.
Generally, starvation refers to the case where one thread gets preferential access to a resource over other threads, making access to the resource uneven or unfair.
Starvation: A condition of execution in which a thread is not allowed to proceed with assigned computations. This term applies to threads that are blocked from being scheduled into a processor by the operating system due to execution of higher priority threads.
— Page 272, The Art of Concurrency, 2009.
It often refers to the scheduling of threads, such as a bug in an operating system or thread-scheduler.
… starvation is the responsibility of the scheduler. Whenever multiple threads are ready to run, the scheduler decides which one or, on a parallel processor, which set of threads gets to run. If a thread is never scheduled, then it will starve, no matter what we do with semaphores.
— Page 81, The Little Book of Semaphores, 2009.
It may also occur within concurrent application programming.
In concurrent programming, thread starvation refers to the situation where one thread monopolizes a resource protected by a concurrency primitive and prevents one or more other threads from accessing the resource fairly.
Now that we know what thread starvation is, let’s consider some common examples.
Run loops using all CPUs, download your FREE book to learn how.
Examples of Thread Starvation
Thread Starvation can happen for many reasons, although it is common when a concurrency primitive is acquired too far from the critical section.
Here, “too far” refers to the number of lines of code or instructions executed prior to the point in the code where the resource or critical section requires protection from the concurrency programming.
This leads to the heuristic:
– Acquire concurrency primitives as close as possible (in code) to the resource or critical section they protect.
Thread starvation can occur with most concurrency primitives that must be acquired, such as:
- Mutual exclusion (mutex) locks.
- Semaphores.
- Conditions
For example, there might be a critical section of code protected by a mutual exclusion (mutex) lock. This critical section may need to be executed many times by a given thread, and by multiple threads. Thread starvation may occur if one thread continues to acquire the mutex lock and execute the critical section, starving out or preventing all other threads from acquiring the lock and executing the critical section.
Another example might be a resource with limited access protected by a semaphore. Multiple threads may need to acquire a position on the semaphore repeatedly as part of their task. Thread starvation may occur if the number of positions on the semaphore are limited and the same thread or threads continue to acquire those positions, starving out or preventing other threads from acquiring a position on the semaphore.
Next, let’s compare thread starvation to other concurrency failure modes.
Thread Starvation vs Deadlock and Livelock.
Thread starvation is a concurrency failure mode, like a deadlock and like a livelock.
A deadlock is a situation where threads are unable to make progress and cannot execute. This can happen for many reasons, although typically involves one thread waiting to acquire a lock held by another thread and the other thread unable to release the lock.
You can learn more about deadlocks in this tutorial:
A livelock is a situation where threads are unable to make progress in the application, but continue to execute. This can happen for many reasons, although typically involves two threads repeatedly competing for a shared resource and preventing each other, such as in a spinlock.
You can learn more about livelocks in this tutorial:
Thread starvation is similar to a deadlock and a livelock in that one or more threads are unable to make progress, but other threads in the system are able to make progress and the starved thread may or may not be a temporary condition.
In thread starvation, typically the thread starved of execution will make progress once the greedy thread or threads that cause the starvation move on or terminate. Alternately, the starved thread may make progress, but it may be less or slower than other threads accessing the same resource.
In this way, thread starvation is more related to the fairness of access to a resource, although the program may still progress. Whereas, a deadlock and a livelock are typically both fatal to the application.
Next, let’s consider how we might fix thread starvation.
Free Python Threading Course
Download your FREE threading PDF cheat sheet and get BONUS access to my free 7-day crash course on the threading API.
Discover how to use the Python threading module including how to create and start new threads and how to use a mutex locks and semaphores
How To Fix Thread Starvation
A common example of thread starvation is a critical section executed in a loop, protected by a concurrency primitive.
The critical section often involves some blocking call, such as writing to a file or reading from a socket.
For example:
|
1 2 3 4 5 6 |
... # acquire lock with lock: for i in range(...): # execute critical section # ... |
As such, each iteration is slow because of the blocking call and the lock is held for a long time by a thread.
This starves other threads blocked attempting to acquire the same lock.
Let’s consider some fixes for the above thread starvation case.
Fix 1: Move the Concurrency Primitive Closer
The first fix to consider is to move the concurrency primitive closer to the critical section.
We might require that the thread acquire the lock each iteration within the loop.
This might be computationally less efficient because acquiring a lock can be expensive, but may reduce the starvation of other threads. This is because each loop the lock is acquired, then released, potentially allowing other threads to acquire it.
For example:
|
1 2 3 4 5 6 |
... for i in range(...): # acquire lock with lock: # execute critical section # ... |
This may or may not improve the fairness of the access to the shared resource.
Fix 2: Don’t Use Context Manager
In the above example, we use the context manager to acquire the concurrency primitive, then to automatically release it. This is a helpful and safe way for acquiring and releasing concurrency primitives.
An alternate approach might be to explicitly acquire and release the resource, in case the context manager is causing some additional code optimizing efficiency within the Python virtual machine resulting in less fair access to the critical section.
There is some anecdotal evidence that it may help in some situations or on some platforms.
This can be achieved by manually calling the acquire() function at the beginning of the critical section, then manually calling release() at the end of the critical section.
For example:
|
1 2 3 4 5 6 7 8 |
... for i in range(...): # acquire lock lock.acquire() # execute critical section # ... # release the lock lock.release() |
Fix 3: Use a Binary Semaphore
Sometimes simple loops like the above may be optimized by the Python interpreter, or the thread scheduler in the operating system.
As such, the fairness of access to the critical section or shared resource may be modified in a way that is out of our control.
As such, we may need to try other tactics.
For example, instead of using a mutex lock, we may use a binary semaphore. Threads will queue up waiting to access the semaphore.
This may or may not improve the fairness of access to the critical section.
For example:
|
1 2 3 |
... # use a binary semaphore as a mutex lock = Semaphore(1) |
Fix 4: Add a Blocking Call
Another tactic may be to introduce a blocking call prior to acquiring the lock.
This will likely trigger a context switch in the operating system and cause the thread scheduler to preferentially choose another non-blocked thread to execute. The result is likely less starvation and more fair access to the critical section.
We could add a blocking call like a sleep so that each thread may block for one millisecond (one one-thousandth of a second) prior to acquiring the lock.
For example:
|
1 2 3 4 5 6 7 8 |
... for i in range(...): # give another thread a chance to acquire the lock sleep(0.001) # 1 ms # acquire lock with lock: # execute critical section # ... |
Now that we have reviewed some fixes for thread starvation, let’s look at some worked examples.
Overwhelmed by the python concurrency APIs?
Find relief, download my FREE Python Concurrency Mind Maps
Example of Thread Starvation
We can explore an example of thread starvation, common in concurrency programming.
In this example we will have a task that executes a loop and each iteration in the loop is a critical section that contains a blocking call. A mutex lock is used to protect the critical section, by protecting the entire task. Two threads execute the task, where one thread always starves out the other thread.
First, we can define the task function.
The function takes the shared mutex lock and a unique identifier for the thread, which we can use in our print messages.
|
1 2 3 4 |
... # task def task(lock, identifier): # ... |
First, we acquire the lock using the context manager.
|
1 2 3 4 |
... # acquire lock with lock: # ... |
Next, we loop five times.
|
1 2 3 4 |
... # execute task for i in range(5): # ... |
The critical section involves printing a message that includes the thread identifier and then blocking, in this case sleeping for one second.
|
1 2 3 4 |
... # simulate effort print(f'Thread {identifier} working') sleep(1) |
Tying this together, the complete task() function is listed below.
|
1 2 3 4 5 6 7 8 9 |
# task def task(lock, identifier): # acquire lock with lock: # execute task for i in range(5): # simulate effort print(f'Thread {identifier} working') sleep(1) |
In the main thread, we can first create the shared mutex lock.
|
1 2 3 |
... # create shared lock lock = Lock() |
Next, we can create two threads to execute the task() function and pass the shared lock and a unique integer identifier 0 or 1.
This can be achieved in a list comprehension.
|
1 2 3 |
... # create worker threads threads = [Thread(target=task, args=(lock,i)) for i in range(2)] |
The main thread can then start both threads, then block until both threads terminate.
|
1 2 3 4 5 6 7 |
... # start threads for thread in threads: thread.start() # wait for threads to terminate for thread in threads: thread.join() |
Tying this together, the complete example is listed below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
# SuperFastPython.com # example of thread starvation from time import sleep from threading import Thread from threading import Lock # task def task(lock, identifier): # acquire lock with lock: # execute task for i in range(5): # simulate effort print(f'Thread {identifier} working') sleep(1) # create shared lock lock = Lock() # create worker threads threads = [Thread(target=task, args=(lock,i)) for i in range(2)] # start threads for thread in threads: thread.start() # wait for threads to terminate for thread in threads: thread.join() |
Running the example first creates the shared lock.
Both threads are created and configured. The main thread starts both new threads, then blocks until they terminate.
One thread acquires the lock, then proceeds with the task. The second thread is blocked until the first thread completely finishes the task and releases the lock.
A sample of results is listed below. In this case Thread 0 acquires the lock first, starving Thread 1. Thread 0 finishes, allowing Thread 1 to acquire the lock and perform the task.
This is a common example of thread starvation in concurrency programming caused by the use of a lock that is too liberal.
|
1 2 3 4 5 6 7 8 9 10 |
Thread 0 working Thread 0 working Thread 0 working Thread 0 working Thread 0 working Thread 1 working Thread 1 working Thread 1 working Thread 1 working Thread 1 working |
Next, let’s look at how we might start to improve this code to reduce thread starvation.
Thread Starvation Fix: Move the Lock
We may be able to reduce thread starvation by moving the usage of the lock closer to the critical section.
That is, rather than locking the entire task, we can lock each iteration of the looped task.
Each iteration of the loop, a thread will acquire the lock, perform the task, then release the lock. This may allow another thread to acquire the lock and perform the task, making access to the critical section more fair and reducing starvation.
We can update the example in the previous section to demonstrate this fix.
This can be achieved by moving the mutex from the top of the task function to within the loop of the iterated critical section.
The task() function with this change is listed below.
|
1 2 3 4 5 6 7 8 9 |
# task def task(lock, identifier): # execute task for i in range(5): # acquire lock with lock: # simulate effort print(f'Thread {identifier} working') sleep(1) |
Tying this together, the complete example is listed below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
# SuperFastPython.com # example of a fix for thread starvation by moving the lock from time import sleep from threading import Thread from threading import Lock # task def task(lock, identifier): # execute task for i in range(5): # acquire lock with lock: # simulate effort print(f'Thread {identifier} working') sleep(1) # create shared lock lock = Lock() # create worker threads threads = [Thread(target=task, args=(lock,i)) for i in range(2)] # start threads for thread in threads: thread.start() # wait for threads to terminate for thread in threads: thread.join() |
Running the example creates the shared lock, then creates and starts the new threads.
Each iteration, a thread will acquire the lock, execute the critical section of the task, then release the lock.
The hope is that the repeated acquiring and releasing of the lock will give each thread a fair and equal chance of acquiring the lock.
In this example, we can see that this was not the case.
One thread acquired the lock and then repeatedly acquired the lock each iteration, starving out the other thread.
Importantly, this result is repeatable, showing a similar outcome each time the program is run.
The result suggests that the Python interpreter may have optimized the bytecode of the program which has allowed one thread to be favored over another when executing the example, or the operating system that schedules the threads chooses to favor one thread over another.
This highlights that even though a fix for thread starvation looks plausible from a design perspective, we cannot know whether it is effective until the code is run.
|
1 2 3 4 5 6 7 8 9 10 |
Thread 0 working Thread 0 working Thread 0 working Thread 0 working Thread 0 working Thread 1 working Thread 1 working Thread 1 working Thread 1 working Thread 1 working |
Next, let’s explore further changes we can make to reduce thread starvation.
Thread Starvation Fix: Manually Acquire and Release
There are some anecdotes that more thread starvation can be seen when using the context manager interface for concurrency primitives.
Another fix to reducing thread starvation might be to manually acquire and release the concurrency primitive, like the lock or semaphore.
This involves manually calling acquire() on the mutex at the beginning of the critical section, then manually calling release() at the end of the critical section. If the critical section can raise an error or exception, then a try-finally pattern may be used with the try block holding the critical section and the call to release() in the finally block.
For more about the try-finally pattern and context managers for concurrent primitives, see the tutorial:
We can update the above example to achieve this.
For example:
|
1 2 3 4 5 6 7 8 |
... # acquire lock lock.acquire() # simulate effort print(f'Thread {identifier} working') sleep(1) # release lock lock.release() |
The updated task() function with this change is listed below.
|
1 2 3 4 5 6 7 8 9 10 11 |
# task def task(lock, identifier): # execute task for i in range(5): # acquire lock lock.acquire() # simulate effort print(f'Thread {identifier} working') sleep(1) # release lock lock.release() |
Tying this together, the complete example is listed below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
# SuperFastPython.com # example of a fix for thread starvation by moving the lock from time import sleep from threading import Thread from threading import Lock # task def task(lock, identifier): # execute task for i in range(5): # acquire lock lock.acquire() # simulate effort print(f'Thread {identifier} working') sleep(1) # release lock lock.release() # create shared lock lock = Lock() # create worker threads threads = [Thread(target=task, args=(lock,i)) for i in range(2)] # start threads for thread in threads: thread.start() # wait for threads to terminate for thread in threads: thread.join() |
Running the example creates the shared lock, then creates and starts the new threads.
Each iteration of the task, each thread will attempt to manually acquire the mutex lock. One thread will acquire it, execute the critical section, then release the lock.
The hope is that the explicit function calls will give each thread an even and fair chance of acquiring the lock each iteration, reducing thread starvation.
In this case, we can see some reduction in thread starvation, but we do not see a fair interleaving of threads accessing the critical section.
|
1 2 3 4 5 6 7 8 9 10 |
Thread 0 working Thread 1 working Thread 1 working Thread 1 working Thread 1 working Thread 1 working Thread 0 working Thread 0 working Thread 0 working Thread 0 working |
This type of result is not seen every time the code is executed. Sometimes one thread is completely starved of access to the critical section.
For example:
|
1 2 3 4 5 6 7 8 9 10 |
Thread 0 working Thread 0 working Thread 0 working Thread 0 working Thread 0 working Thread 1 working Thread 1 working Thread 1 working Thread 1 working Thread 1 working |
These results may lend some credence to the anecdotes that manual calls to acquire() and release() reduce starvation, although perhaps further systematic testing is required.
Next, let’s consider changing the concurrent primitive.
Thread Starvation Fix: Change Concurrency Primitive
Changing the concurrency primitive may help with thread starvation.
For example, a binary semaphore could be used in place of a mutex lock.
When using a semaphore, threads may queue up in FIFO order waiting to acquire the semaphore. Releasing the semaphore may notify these threads, allowing them to acquire the semaphore on the next iteration and reduce the thread starvation.
This can be achieved by replacing the threading.Lock with a threading.Semaphore configured with an initial count of 1.
For example:
|
1 2 3 |
... # create shared lock lock = Semaphore(1) |
The semaphore may then be used just like a mutex lock in the task, acquired and released each iteration via the context manager or manually via calls to acquire() and release().
The example from the previous section can be updated to use a binary semaphore instead of a mutex.
The complete example is listed below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
# SuperFastPython.com # example of a fix for thread starvation by using a semaphore from time import sleep from threading import Thread from threading import Semaphore # task def task(lock, identifier): # execute task for i in range(5): # acquire lock with lock: # simulate effort print(f'Thread {identifier} working') sleep(1) # create shared lock lock = Semaphore(1) # create worker threads threads = [Thread(target=task, args=(lock,i)) for i in range(2)] # start threads for thread in threads: thread.start() # wait for threads to terminate for thread in threads: thread.join() |
Running the example creates the shared binary semaphore, then creates and starts the two new threads.
The semaphore is acquired each iteration, the critical section executed, and the semaphore is released.
The hope is that each time the semaphore is released it will notify the waiting thread which will acquire it and have a turn at executing the critical section, causing the first thread to block. This would give each thread a fair and even chance at executing the critical section and reduce thread starvation.
In this case, we can see that using a binary semaphore instead of a mutex did not reduce thread starvation.
|
1 2 3 4 5 6 7 8 9 10 |
Thread 0 working Thread 0 working Thread 0 working Thread 0 working Thread 0 working Thread 1 working Thread 1 working Thread 1 working Thread 1 working Thread 1 working |
Perhaps this approach would be more successful in your application, your platform, or your version of the Python interpreter.
If so, let me know in the comments below.
Alternatively, perhaps alternate concurrency primitives can be used, such as a threading.Event or a threading.Condition.
Next, let’s look at reducing starvation by adding a blocking call.
Thread Starvation Fix: Add Blocking Call
A common fix for thread starvation is to add a blocking call right before acquiring the concurrency primitive.
For example a call to time.sleep() can be made right before acquiring a mutex lock.
The sleep interval may be for a tiny fraction of a second, such as 1 millisecond (one one-thousandth of a second). This will be enough to suggest a context switch to the underlying operating system.
For example:
|
1 2 3 |
... # give another thread a chance to acquire the lock sleep(0.001) # 1 ms |
Some operating systems may permit you to sleep for zero seconds, and possibly trigger a context switch.
For example:
|
1 2 3 |
... # give another thread a chance to acquire the lock sleep(0) |
This may or may not be supported on your operating system, or may be optimized away by modern versions of the Python interpreter or underlying C-code.
I would recommend using a fraction of a second instead of zero as an argument to time.sleep().
The expected result is that the operating system will give a fair and even split of access to the critical section to the competing threads, at least on average. The operating system still must schedule the threads, and it is possible for access to not be perfectly even, especially if the number of threads is three or more.
We can update the above example to test this fix.
The call to sleep would be added at the beginning of each iteration of the task loop right before the lock is acquired.
For example:
|
1 2 3 4 5 6 7 8 |
... # give another thread a chance to acquire the lock sleep(0.001) # 1 ms # acquire lock with lock: # simulate effort print(f'Thread {identifier} working') sleep(1) |
The updated task() function with this change is listed below.
|
1 2 3 4 5 6 7 8 9 10 11 |
# task def task(lock, identifier): # execute task for i in range(5): # give another thread a chance to acquire the lock sleep(0.001) # 1 ms # acquire lock with lock: # simulate effort print(f'Thread {identifier} working') sleep(1) |
Tying this together, the complete example is listed below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
# SuperFastPython.com # example of a fix for thread starvation by adding a sleep from time import sleep from threading import Thread from threading import Lock # task def task(lock, identifier): # execute task for i in range(5): # give another thread a chance to acquire the lock sleep(0.001) # 1 ms # acquire lock with lock: # simulate effort print(f'Thread {identifier} working') sleep(1) # create shared lock lock = Lock() # create worker threads threads = [Thread(target=task, args=(lock,i)) for i in range(2)] # start threads for thread in threads: thread.start() # wait for threads to terminate for thread in threads: thread.join() |
Running the example creates the shared lock, then creates and starts the two new threads.
Each thread blocks for a tiny fraction of a second each iteration, then attempts to acquire the lock.
One thread will acquire the lock, execute the critical section, then release the lock. Before this thread can acquire the lock again on the next iteration, it must block. This very likely will give the chance for another thread to run (e.g. be scheduled by the operating system) and acquire the lock instead.
In this case, we can see that adding a block for one millisecond had the desired effect of completely removing thread starvation and allowing fair and equal access to the critical section.
|
1 2 3 4 5 6 7 8 9 10 |
Thread 0 working Thread 1 working Thread 0 working Thread 1 working Thread 0 working Thread 1 working Thread 0 working Thread 1 working Thread 0 working Thread 1 working |
Further Reading
This section provides additional resources that you may find helpful.
Python Threading Books
- Python Threading Jump-Start, Jason Brownlee (my book!)
- Threading API Interview Questions
- Threading Module API Cheat Sheet
I also recommend specific chapters in the following books:
- Python Cookbook, David Beazley and Brian Jones, 2013.
- See: Chapter 12: Concurrency
- Effective Python, Brett Slatkin, 2019.
- See: Chapter 7: Concurrency and Parallelism
- Python in a Nutshell, Alex Martelli, et al., 2017.
- See: Chapter: 14: Threads and Processes
Guides
- Python Threading: The Complete Guide
- Python ThreadPoolExecutor: The Complete Guide
- Python ThreadPool: The Complete Guide
APIs
References
Takeaways
You now know how to identify and fix thread starvation in Python.
Do you have any questions?
Ask your questions in the comments below and I will do my best to answer.
Photo by vikram sundaramoorthy on Unsplash
Do you have any questions?