Last Updated on September 12, 2022
You can get a livelock if a thread cannot make progress because of another thread, but is not blocked as with a deadlock.
In this tutorial you will discover how to identify a thread livelock in Python.
Let’s get started.
What is a Livelock
A livelock is a concurrency failure case where a thread is not blocked but is unable to make progress because of the actions of another thread.
A livelock typically involves two or more threads that share concurrency primitives such as mutual exclusion (mutex) locks.
The threads may both attempt to acquire a lock or series of locks at the same time, detect that they are competing for the same resource, and then back-off. This process is repeated and neither thread is able to make progress and are “locked”.
Livelock: A situation in which threads are doing some computation but are unable to proceed past the current computation phase due to the actions of some other thread. This is typically caused by resource starvation where there’s constant change, with no thread progressing.
— Page 269, The Art of Concurrency, 2009.
Next, let’s learn more about a livelock by contrasting it with a deadlock.
Run loops using all CPUs, download your FREE book to learn how.
Livelock vs Deadlock
A livelock can be contrasted with a deadlock.
Both a livelock and a deadlock have a lock in common, for example:
- Both are examples of a concurrency failure mode.
- Both prevent threads from progressing.
- Both are challenging to identify from code alone, e.g. may require running code.
The main difference between a livelock and a deadlock is the state of the thread or threads while they are unable to make progress.
In a livelock the threads execute and are not blocked, whereas in a deadlock the threads are blocked, e.g. waiting on a concurrency primitive such as a lock, and are unable to to execute code.
- Livelock: Threads cannot make progress but can continue to execute code.
- Deadlock: Threads cannot make progress and are blocked, e.g. waiting.
You can learn more about thread deadlocks in this tutorial:
Next, let’s look at a worked example of a thread livelock.
Example of a Livelock
We can make the idea of a livelock clear with a worked example.
In this example we will define a task function to be executed by worker threads. The function will involve acquiring one lock, then attempting to acquire the second lock. If the second lock is already locked, it will back-off, release the first lock and wait a fraction of a second before trying again.
If the function is executed by two threads at the same time and the threads acquire the locks in a different order then it will lead to a live lock.
For example:
- Thread 1: Acquires Lock1, checks Lock2 and backs off if it is not free.
- Thread 2: Acquires Lock2, checks Lock1 and backs off if it is not free.
First, let’s define a function that attempts to acquire locks in an order and backs off if the second lock is not available.
The function will take a unique number to identify the thread, and the two locks to acquire as arguments.
1 2 3 |
# task for worker threads def task(number, lock1, lock2): # ... |
The task will continue to attempt to acquire both locks forever. This can be achieved with a while-loop.
1 2 3 4 |
... # loop until the task is completed while True: # ... |
The task attempts to acquire the first lock.
1 2 3 4 |
... # acquire the first lock with lock1: # ... |
We need to contrive the situation by ensuring the lock is held while the other thread attempts to acquire it. Therefore we will force the task to block for a moment while holding the lock.
1 2 3 |
... # wait a moment sleep(0.1) |
Next, the task checks if the second lock is available, and if not it gives up. Otherwise, if the lock is available, it attempts to acquire it and if so completes the task and breaks out of the outer while loop.
1 2 3 4 5 6 7 8 9 |
... # check if the second lock is available if lock2.locked(): print(f'Task {number} cannot get the second lock, giving up...') else: # acquire lock2 with lock2: print(f'Task {number} made it, all done.') break |
Tying this together, the complete task() function is listed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
# task for worker threads def task(number, lock1, lock2): # loop until the task is completed while True: # acquire the first lock with lock1: # wait a moment sleep(0.1) # check if the second lock is available if lock2.locked(): print(f'Task {number} cannot get the second lock, giving up...') else: # acquire lock2 with lock2: print(f'Task {number} made it, all done.') break |
Finally, in the main thread, we can first create both mutex locks.
1 2 3 4 |
... # create locks lock1 = Lock() lock2 = Lock() |
We can then create and configure two threads, both executing the same task at the same time. Importantly, we will switch the order of the locks provided as arguments to each thread to force the live-lock situation.
1 2 3 4 |
... # create threads thread1 = Thread(target=task, args=(0, lock1, lock2)) thread2 = Thread(target=task, args=(1, lock2, lock1)) |
We can then start both worker threads and wait for the tasks to finish.
1 2 3 4 5 6 7 |
... # start threads thread1.start() thread2.start() # wait for threads to finish thread1.join() thread2.join() |
Tying this together, the complete example of a livelock 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 29 30 31 32 33 34 35 |
# SuperFastPython.com # example of a livelock from time import sleep from threading import Thread from threading import Lock # task for worker threads def task(number, lock1, lock2): # loop until the task is completed while True: # acquire the first lock with lock1: # wait a moment sleep(0.1) # check if the second lock is available if lock2.locked(): print(f'Task {number} cannot get the second lock, giving up...') else: # acquire lock2 with lock2: print(f'Task {number} made it, all done.') break # create locks lock1 = Lock() lock2 = Lock() # create threads thread1 = Thread(target=task, args=(0, lock1, lock2)) thread2 = Thread(target=task, args=(1, lock2, lock1)) # start threads thread1.start() thread2.start() # wait for threads to finish thread1.join() thread2.join() |
Running the example first creates the locks.
The two worker threads are then configured and started and the main thread blocks while waiting for the tasks to complete.
The first thread acquires lock1 and blocks for a moment. The second thread acquires lock2 and blocks for a moment.
The first thread then checks if lock2 is available. It isn’t so it gives up and repeats the loop. At the same time, the second thread checks if lock1 is available. It isn’t so it also gives up and repeats the loop.
This process of both threads getting one lock and attempting to get the next lock and giving up is then repeated forever.
Note, you will have to manually kill the process (e.g. Control-C) in order to stop it.
1 2 3 4 5 6 7 8 9 10 11 |
... Task 0 cannot get the second lock, giving up... Task 1 cannot get the second lock, giving up... Task 0 cannot get the second lock, giving up... Task 1 cannot get the second lock, giving up... Task 0 cannot get the second lock, giving up... Task 1 cannot get the second lock, giving up... Task 0 cannot get the second lock, giving up... Task 1 cannot get the second lock, giving up... Task 0 cannot get the second lock, giving up... Task 1 cannot get the second lock, giving up... |
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
Tips On Avoiding a Livelock
This section provides some tips to help avoiding livelocks in your multithreaded Python applications.
Two tips for avoiding livelocks include:
- Always acquire sequences of locks in the same order.
- Give-up on repeated tasks after a fixed number of tries.
Let’s take a closer look at each.
Tip 1: Force Consistent Lock Ordering
This specific livelock in the previous section could be avoided if both threads acquired the locks in the same order.
This is a best practice when threads must acquire multiple locks in order to perform a task and is called “lock ordering“.
For example, both functions may be given the same locks in the same order as arguments:
1 2 3 4 |
... # create threads thread1 = Thread(target=task, args=(0, lock1, lock2)) thread2 = Thread(target=task, args=(1, lock1, lock2)) |
Tip 2: Use a Fixed Number of Tries
The lock could be broken if the task used a counter and gave up after a fixed number of tries, rather than looping forever.
For example:
1 2 3 4 5 6 |
... # try the task ten times before giving up for i in range(10): # ... else: print('Task failed after 10 tries') |
Overwhelmed by the python concurrency APIs?
Find relief, download my FREE Python Concurrency Mind Maps
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 a thread livelock in Python.
Do you have any questions?
Ask your questions in the comments below and I will do my best to answer.
Do you have any questions?