Thread Livelocks in Python - Super Fast Python

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.

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:

How to Identify a Deadlock in Python

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...