Thread Livelocks in Python
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.
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.
# 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.
...
# loop until the task is completed
while True:
# ...
The task attempts to acquire the first lock.
...
# 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.
...
# 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.
...
# 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.
# 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.
...
# 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.
...
# 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.
...
# 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.
# 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.
...
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...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:
...
# 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:
...
# try the task ten times before giving up
for i in range(10):
# ...
else:
print('Task failed after 10 tries')
Takeaways
You now know how to identify a thread livelock in Python.
If you enjoyed this tutorial, you will love my book: Python Threading Jump-Start. It covers everything you need to master the topic with hands-on examples and clear explanations.