Lock Splitting in Python

April 24, 2022 Python Threading

You can reduce lock contention using lock splitting.

In this tutorial you will discover how to use lock splitting in Python.

Let's get started.

Problem of Lock Contention

Lock contention is a problem that may occur when using mutual exclusion (mutex) locks.

Lock contention is typically described in the context of the internals of operating systems, but may also be a problem at a high-level such as application programming with concurrency primitives.

It describes a situation where a lock protects a critical section and multiple threads attempt to acquire the lock at the same time.

This is a problem because only one thread can acquire a lock, and all other threads must block, and wait for the lock to become available. This is an inefficient use of resources, as those threads could be executing and completing tasks in the application.

You can learn more about lock contention in this tutorial:

Lock Contention in Python

One approach to reducing contention is called lock splitting.

What is lock splitting and how can we implement this in Python?

What is Lock Splitting

Lock splitting is a technique for reducing lock contention.

It involves increasing the granularity of the usage of mutex locks in your application.

Lock granularity refers to the relationship between the lock and the state and resources it protects.

Coarse lock granularity means that one lock protects many state variables or resources, whereas fine lock granularity means that one lock protects few state variables or resources.

Coarse Lock Granularity: One lock protects many variables.
Fine Lock Granularity: One lock protects a few variables.

Lock granularity can be increased via lock splitting.

This can be achieved by replacing one lock that protects critical sections composed of many variables or many behaviors to multiple locks, into separate locks for each variable or each behavior.

... reduce the granularity at which locking occurs, potentially allowing greater scalability—but using more locks also increases the risk of deadlock.
-- Page 235, Java Concurrency in Practice, 2006.

It may be helpful to consider lock splitting in terms of code and in terms of application functionality.

For example, considered from a code perspective, perhaps there is an opportunity to split locks based on the number or type of variables. Alternatively, considered from an application functionality perspective, perhaps there are specific roles, responsibilities, or capabilities that can be split to use separate locks.

Split By Code: Split one lock into multiple locks based on the specific objects, variables, and functions you have in your code.
Split By Functionality: Split one lock into multiple locks based on the specific roles and responsibilities within the application.

It may be helpful to audit the usage of a lock in your application.

If the lock is protecting multiple variables, then perhaps it can be split into multiple locks, one protecting each variable.

If a lock guards more than one independent state variable, you may be able to improve scalability by splitting it into multiple locks that each guard different variables. This results in each lock being requested less often.
-- Page 235, Java Concurrency in Practice, 2006.

Importantly, it matters how the variables are used. Lock splitting for variables is most effective if different variables are used in different situations in the program. Threads would then contend for finer grained locks in those separate situations.

There is an increased risk of deadlock if additional locks are added and some locks must be acquired while other locks are held. This risk can be reduced through lock ordering.

Next, let's look at how we might implement lock splitting in Python.

How to Implement Lock Splitting

Lock splitting can be implemented by replacing one lock with multiple locks.

Recall that lock splitting is an approach to reduce lock contention.

Any changes to the program should only be adopted if lock contention has been reduced. Therefore it is important to both audit the usage of a lock within the program and even measure the amount of lock contention before and after the change.

There are many ways to implement lock splitting.

Two common approaches are to split by shared variables and to split by shared functionality.

Lock Splitting by Variables: One lock protecting multiple shared variables split into one lock per variable.
Lock Splitting by Functionality: One lock protecting multiple shared behaviors split into one lock per shared behavior.

Let's take a closer look at each approach.

Lock Splitting by Variables

Consider the case where one lock is used to protect multiple shared variables.

These variables may be used in many locations in the program and each usage is protected from race conditions by the single lock.

For example, we have a single shared lock.

...
# create shared lock
lock = threading.Lock()

We have multiple variables shared among threads of differing types.

...
# define shared variables
a = list()
b = 0
c = dict()

The variables are protected from race conditions by the lock each time they are read, written or updated to avoid race conditions.

Importantly, different variables are used at different points in the code.

For example, perhaps one variable is always used alone:

...
# acquire the lock
with lock:
	# update a variable
	a.append('some new data')

Perhaps other variables are always used together.

For example:

...
# acquire the lock
with lock:
	# update other variables
	b += 1
	c = 0

Threads suffer lock contention because the single lock is used to protect all variables.

The lock may be split into two locks, one to protect one shared variable and another to protect the other two shared variables.

This involves first defining two locks, for example:

...
# create shared locks
lock1 = threading.Lock()
lock2 = threading.Lock()

Then each lock must be adopted for its own subset of the shared variables.

For example:

...
# acquire the lock
with lock1:
	# update a variable
	a.append('some new data')

And:

...
# acquire the lock
with lock2:
	# update other variables
	b += 1
	c = 0

In this way, contention for a single lock is removed and replaced with contention for separate locks for separate subsets of the shared variables.

Lock Splitting by Functionality

Consider the situation where a lock is used to protect a shared resource that may be used in multiple behaviors within the application.

These behaviors may be used through the application, but each is protected by a single lock to avoid race conditions on the shared resource.

The shared resource may be data, an object, or access to something external like a file, database or socket.

For example, we may have read and write operations (functionality or behaviors) on the resource in separate functions, each protected by the same lock.

We have a single shared lock.

...
# create shared lock
lock = threading.Lock()

The read operation must be protected from race conditions with the shared lock.

For example:

# read operation on the resource
def read(resource, lock):
	# acquire the lock
	with lock:
		# read operation on the resource
		data = resource.read()

Similarly, write operations on the resource must be protected from race conditions with the shared lock.

For example:

# write operation on the resource
def write(resource, lock):
	# acquire the lock
	with lock:
		# write operation on the resource
		resource.write(data)

Threads suffer lock contention as any operation on the shared resource requires obtaining the same lock.

Lock splitting could be applied by using a separate lock for each operation on the resource, as long as the operations are appropriately mutually exclusive.

This requires first creating a separate lock for each operation.

For example:

...
# create shared locks
lock_read = threading.Lock()
lock_write = threading.Lock()

And then using a separate lock for each operation.

For example:

# read operation on the resource
def read(resource, lock):
	# acquire the read lock
	with lock_read:
		# read operation on the resource
		data = resource.read()

And:

For example:

# write operation on the resource
def write(resource, lock):
	# acquire the write lock
	with lock_write:
		# write operation on the resource
		resource.write(data)

Contention for a single lock has been removed and replaced with hopefully a lower level of contention for two separate locks organized by functionality or operations on a shared resource.

Now that we have some idea of how to implement lock splitting, let's look at some worked examples.

Example of Lock Contention

Before we explore lock splitting, we can develop a program with lock contention.

In this example, we will have a number of threads all performing the same task on shared data. The task involves iterating a number of times and randomly either writing data to the shared variable or reading data from the shared variable.

The shared data is a list and is protected by a single lock. The example is contrived as most operations on a Python list are atomic. We might pretend that the list represents a shared resource like a file or socket.

Nevertheless, it is a good example of lock contention as each thread must contend for the same lock that protects all operations on the shared data. It will provide a good example for lock splitting in the next section as the two operations on the data can be neatly partitioned.

First, we can define the task and two subtasks.

The first subtask will read from the shared data using the lock. Each thread will have a unique identifier to help see what is going on in our print messages. This identifier will be used in each subtask.

The read subtask will block for a random fraction of a second then report the thread identifier and the current state in the shared data.

The read_subtask() function below implements this, taking the shared data, shared lock and thread identifier as arguments.

# read subtask
def read_subtask(data, lock, identifier):
    # acquire the lock
    with lock:
        # block
        sleep(random())
        # report value
        print(f'.thread {identifier} read {data}')

The write subtask is similar to the read subtask, except it involves adding a value to the shared list. Namely, the thread identifier itself is appended to the list.

The write_subtask() below implements this, taking the shared data, shared lock and thread identifier as arguments.

# write subtask
def write_subtask(data, lock, identifier):
    # acquire the lock
    with lock:
        # block
        sleep(random())
        # add value
        data.append(identifier)
        # report value
        print(f'.thread {identifier} wrote to data')

Next, we can define the task function that will be executed in a new thread.

This function will iterate five times and each iteration it will randomly either execute the read task or the write task.

The task() function below implements this, taking the shared data, shared lock and thread identifier as arguments.

# task executed in a new thread
def task(data, lock, identifier):
    # perform task
    for i in range(5):
        # read or write
        if random() < 0.5:
            read_subtask(data, lock, identifier)
        else:
            write_subtask(data, lock, identifier)

Next, in the main thread, we can create the shared data and the shared lock instances.

...
# create shared data
data = list()
# create shared lock
lock = Lock()

We can then create the threads and configure them to execute our task() function with the required arguments. This can be achieved in a list comprehension.

...
# create worker threads
threads = [Thread(target=task, args=(data, lock, i)) for i in range(10)]

The main thread can then start the threads, then block and wait for the new threads to terminate.

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

# SuperFastPython.com
# example of lock contention
from random import random
from time import sleep
from threading import Thread
from threading import Lock

# read subtask
def read_subtask(data, lock, identifier):
    # acquire the lock
    with lock:
        # block
        sleep(random())
        # report value
        print(f'.thread {identifier} read {data}')

# write subtask
def write_subtask(data, lock, identifier):
    # acquire the lock
    with lock:
        # block
        sleep(random())
        # add value
        data.append(identifier)
        # report value
        print(f'.thread {identifier} wrote to data')

# task executed in a new thread
def task(data, lock, identifier):
    # perform task
    for i in range(5):
        # read or write
        if random() < 0.5:
            read_subtask(data, lock, identifier)
        else:
            write_subtask(data, lock, identifier)

# create shared data
data = list()
# create shared lock
lock = Lock()
# create worker threads
threads = [Thread(target=task, args=(data, lock, i)) for i in range(10)]
# 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 data and shared lock.

The ten new threads are then created and started, and the main thread blocks until they are complete.

Each thread then executes the task() function and randomly executes the read or the write subtask.

There is high contention for the lock as all ten threads require the lock in order to perform either subtask. This makes each thread's task execution slow, and the overall execution of the program slow as the threads spend most of their time waiting for access to the lock.

A sample output from the program is listed below.

Note, your results will differ given the use of random numbers. Try running the example a few times.

.thread 0 wrote to data
.thread 1 wrote to data
.thread 1 read [0, 1]
.thread 3 read [0, 1]
.thread 4 wrote to data
.thread 5 wrote to data
.thread 5 wrote to data
.thread 5 read [0, 1, 4, 5, 5]
.thread 5 wrote to data
.thread 9 wrote to data
.thread 9 wrote to data
.thread 9 wrote to data
.thread 9 wrote to data
.thread 3 read [0, 1, 4, 5, 5, 5, 9, 9, 9, 9]
.thread 3 wrote to data
.thread 3 wrote to data
.thread 3 read [0, 1, 4, 5, 5, 5, 9, 9, 9, 9, 3, 3]
.thread 8 wrote to data
.thread 5 read [0, 1, 4, 5, 5, 5, 9, 9, 9, 9, 3, 3, 8]
.thread 0 read [0, 1, 4, 5, 5, 5, 9, 9, 9, 9, 3, 3, 8]
.thread 0 read [0, 1, 4, 5, 5, 5, 9, 9, 9, 9, 3, 3, 8]
.thread 1 wrote to data
.thread 9 read [0, 1, 4, 5, 5, 5, 9, 9, 9, 9, 3, 3, 8, 1]
.thread 4 wrote to data
.thread 4 wrote to data
.thread 4 wrote to data
.thread 8 read [0, 1, 4, 5, 5, 5, 9, 9, 9, 9, 3, 3, 8, 1, 4, 4, 4]
.thread 8 read [0, 1, 4, 5, 5, 5, 9, 9, 9, 9, 3, 3, 8, 1, 4, 4, 4]
.thread 8 read [0, 1, 4, 5, 5, 5, 9, 9, 9, 9, 3, 3, 8, 1, 4, 4, 4]
.thread 8 wrote to data
.thread 6 wrote to data
.thread 6 read [0, 1, 4, 5, 5, 5, 9, 9, 9, 9, 3, 3, 8, 1, 4, 4, 4, 8, 6]
.thread 6 read [0, 1, 4, 5, 5, 5, 9, 9, 9, 9, 3, 3, 8, 1, 4, 4, 4, 8, 6]
.thread 2 read [0, 1, 4, 5, 5, 5, 9, 9, 9, 9, 3, 3, 8, 1, 4, 4, 4, 8, 6]
.thread 2 wrote to data
.thread 2 read [0, 1, 4, 5, 5, 5, 9, 9, 9, 9, 3, 3, 8, 1, 4, 4, 4, 8, 6, 2]
.thread 2 read [0, 1, 4, 5, 5, 5, 9, 9, 9, 9, 3, 3, 8, 1, 4, 4, 4, 8, 6, 2]
.thread 2 read [0, 1, 4, 5, 5, 5, 9, 9, 9, 9, 3, 3, 8, 1, 4, 4, 4, 8, 6, 2]
.thread 6 read [0, 1, 4, 5, 5, 5, 9, 9, 9, 9, 3, 3, 8, 1, 4, 4, 4, 8, 6, 2]
.thread 6 wrote to data
.thread 1 wrote to data
.thread 7 read [0, 1, 4, 5, 5, 5, 9, 9, 9, 9, 3, 3, 8, 1, 4, 4, 4, 8, 6, 2, 6, 1]
.thread 7 wrote to data
.thread 0 read [0, 1, 4, 5, 5, 5, 9, 9, 9, 9, 3, 3, 8, 1, 4, 4, 4, 8, 6, 2, 6, 1, 7]
.thread 0 read [0, 1, 4, 5, 5, 5, 9, 9, 9, 9, 3, 3, 8, 1, 4, 4, 4, 8, 6, 2, 6, 1, 7]
.thread 4 read [0, 1, 4, 5, 5, 5, 9, 9, 9, 9, 3, 3, 8, 1, 4, 4, 4, 8, 6, 2, 6, 1, 7]
.thread 7 wrote to data
.thread 1 read [0, 1, 4, 5, 5, 5, 9, 9, 9, 9, 3, 3, 8, 1, 4, 4, 4, 8, 6, 2, 6, 1, 7, 7]
.thread 7 wrote to data
.thread 7 wrote to data

Next, let's explore how we might reduce lock contention by using lock splitting.

Example of Lock Splitting

Lock splitting can be implemented by replacing one lock with two or more locks.

In this example, we have two clear responsibilities in the task executed by new threads, the read subtask and the write subtask, putting aside the contrived necessity to lock on a list for read and write operations.

The example in the previous section suffered high lock contention as all ten threads competed for the same lock for each thread's five subtasks.

We can split the single lock into two locks, one for read operations and one for write operations. This will reduce contention for all subtasks to lock contention on only read or write operations to the shared data.

This can be achieved by creating a read lock and a write lock in the main thread, sharing them with the task() function and then having the task function choose to use the appropriate lock for each subtask.

First, we can update the task() function to take two locks as arguments.

# task executed in a new thread
def task(data, read_lock, write_lock, identifier):
	# ...

We can then use a separate lock for each subtask.

For example:

...
# read or write
if random() < 0.5:
    read_subtask(data, read_lock, identifier)
else:
    write_subtask(data, write_lock, identifier)

The updated task() function with this change is listed below.

# task executed in a new thread
def task(data, read_lock, write_lock, identifier):
    # perform task
    for i in range(5):
        # read or write
        if random() < 0.5:
            read_subtask(data, read_lock, identifier)
        else:
            write_subtask(data, write_lock, identifier)

In the main thread, we can then create two locks, one for each subtask.

...
# create shared locks
read_lock = Lock()
write_lock = Lock()

These locks can then be passed to each thread when configured to execute the task() function.

...
# create worker threads
threads = [Thread(target=task, args=(data, read_lock, write_lock, i)) for i in range(10)]

Tying this together, the complete example is listed below.

# SuperFastPython.com
# example of reducing lock contention with lock splitting
from random import random
from time import sleep
from threading import Thread
from threading import Lock

# read subtask
def read_subtask(data, lock, identifier):
    # acquire the lock
    with lock:
        # block
        sleep(random())
        # report value
        print(f'.thread {identifier} read {data}')

# write subtask
def write_subtask(data, lock, identifier):
    # acquire the lock
    with lock:
        # block
        sleep(random())
        # add value
        data.append(identifier)
        # report value
        print(f'.thread {identifier} wrote to data')

# task executed in a new thread
def task(data, read_lock, write_lock, identifier):
    # perform task
    for i in range(5):
        # read or write
        if random() < 0.5:
            read_subtask(data, read_lock, identifier)
        else:
            write_subtask(data, write_lock, identifier)

# create shared data
data = list()
# create shared locks
read_lock = Lock()
write_lock = Lock()
# create worker threads
threads = [Thread(target=task, args=(data, read_lock, write_lock, i)) for i in range(10)]
# 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 data and the two shared locks.

The ten threads are then created, configured and started, then the main thread blocks until the new threads terminate.

Each thread then executes its task look five times and randomly performs a read or write operation.

The task will use a separate lock for read operations from write operations. This means that only a subset of threads will contend for a lock based on the specific subtask being performed, rather than a single lock used to protect the shared data.

A sample output from the program is listed below.

Note, your results will differ given the use of random numbers. Try running the example a few times.

This highlights an example of how to apply lock splitting to reduce lock contention.

.thread 1 read []
.thread 2 read []
.thread 0 wrote to data
.thread 5 read [0]
.thread 3 wrote to data
.thread 5 read [0, 3]
.thread 7 read [0, 3]
.thread 4 wrote to data
.thread 8 read [0, 3, 4]
.thread 9 wrote to data
.thread 8 read [0, 3, 4, 9]
.thread 0 wrote to data
.thread 2 read [0, 3, 4, 9, 0]
.thread 6 read [0, 3, 4, 9, 0]
.thread 6 read [0, 3, 4, 9, 0]
.thread 5 wrote to data
.thread 6 read [0, 3, 4, 9, 0, 5]
.thread 5 wrote to data
.thread 5 wrote to data
.thread 1 read [0, 3, 4, 9, 0, 5, 5, 5]
.thread 9 read [0, 3, 4, 9, 0, 5, 5, 5]
.thread 0 wrote to data
.thread 9 read [0, 3, 4, 9, 0, 5, 5, 5, 0]
.thread 9 read [0, 3, 4, 9, 0, 5, 5, 5, 0]
.thread 0 wrote to data
.thread 7 wrote to data
.thread 6 wrote to data
.thread 9 read [0, 3, 4, 9, 0, 5, 5, 5, 0, 0, 7, 6]
.thread 4 read [0, 3, 4, 9, 0, 5, 5, 5, 0, 0, 7, 6]
.thread 8 wrote to data
.thread 3 read [0, 3, 4, 9, 0, 5, 5, 5, 0, 0, 7, 6, 8]
.thread 3 read [0, 3, 4, 9, 0, 5, 5, 5, 0, 0, 7, 6, 8]
.thread 1 wrote to data
.thread 1 wrote to data
.thread 7 read [0, 3, 4, 9, 0, 5, 5, 5, 0, 0, 7, 6, 8, 1, 1]
.thread 6 read [0, 3, 4, 9, 0, 5, 5, 5, 0, 0, 7, 6, 8, 1, 1]
.thread 4 wrote to data
.thread 3 wrote to data
.thread 2 wrote to data
.thread 1 wrote to data
.thread 8 read [0, 3, 4, 9, 0, 5, 5, 5, 0, 0, 7, 6, 8, 1, 1, 4, 3, 2, 1]
.thread 7 wrote to data
.thread 8 read [0, 3, 4, 9, 0, 5, 5, 5, 0, 0, 7, 6, 8, 1, 1, 4, 3, 2, 1, 7]
.thread 4 read [0, 3, 4, 9, 0, 5, 5, 5, 0, 0, 7, 6, 8, 1, 1, 4, 3, 2, 1, 7]
.thread 2 read [0, 3, 4, 9, 0, 5, 5, 5, 0, 0, 7, 6, 8, 1, 1, 4, 3, 2, 1, 7]
.thread 7 wrote to data
.thread 0 read [0, 3, 4, 9, 0, 5, 5, 5, 0, 0, 7, 6, 8, 1, 1, 4, 3, 2, 1, 7, 7]
.thread 4 read [0, 3, 4, 9, 0, 5, 5, 5, 0, 0, 7, 6, 8, 1, 1, 4, 3, 2, 1, 7, 7]
.thread 3 wrote to data
.thread 2 wrote to data

Takeaways

You now know how to reduce lock contention with lock splitting.

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.