You can reduce lock contention by reducing the frequency and duration that a lock is used and held.
In this tutorial you will discover how to identify and reduce lock contention in Python.
Let’s get started.
Table of Contents
Problem With Lock Contention
A mutual exclusion lock or mutex lock is a synchronization primitive intended to prevent a race condition.
A mutex lock can be used to ensure that only one thread at a time executes a critical section of code at a time, while all other threads trying to execute the same code must wait until the currently executing thread is finished with the critical section and releases the lock.
Python provides a mutual exclusion lock via the threading.Lock class.
An instance of the lock can be created and then acquired by threads before accessing a critical section, and released after the critical section.
# create a lock
lock = Lock()
# acquire the lock
# critical section
# release the lock
Only one thread can have the lock at any time. If a thread does not release an acquired lock, it cannot be acquired again.
The thread attempting to acquire the lock will block until the lock is acquired, such as if another thread currently holds the lock then releases it.
We can also use the lock via the context manager. This will allow the critical section to be a block within the usage of the lock and for the lock to be released automatically once the block has completed.
# create a lock
lock = Lock()
# acquire the lock
You can learn more about mutex locks in the tutorial:
A problem with locks is that multiple threads may attempt to acquire the lock at the same time.
This is called lock contention.
What is lock contention and how can we fix it in our programs?
What is 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.
Contention on a lock occurs when multiple threads try to acquire the lock at the same time. High contention means there are many such threads; low contention means there are few.— Page 154, The Art of Multiprocessor Programming, 2020.
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.
If, however, the lock is in sufficiently high demand, threads will block waiting for it; in the extreme case, processors will sit idle even though there is plenty of work to do.— Page 232, Java Concurrency in Practice, 2006.
Lock contention is a specific type of contention problem, related to the broader problem of resource contention where multiple threads may compete for access for any given resource accessible to the program.
It may be helpful to think of lock contention in terms of severity.
- High Lock Contention: Many threads competing for the same lock.
- Low Lock Contention: Few threads competing for the same lock.
If we are subjected to the problem of lock contention in our concurrent application, we would prefer low lock contention over high lock contention.
There are two aspects of using a lock which may influence whether we suffer lock contention.
- How often the lock is used.
- How long the lock is held.
For example, the more often a lock is used in a multithreaded application, the more likely there will be contention for the lock among threads.
Additionally, the longer a lock is held within the application, the more likely that there will be contention for the lock among the threads.
Two factors influence the likelihood of contention for a lock: how often that lock is requested and how long it is held once acquired.— Page 232, Java Concurrency in Practice, 2006.
This provides some insight in how we might reduce contention for locks in our programs.
Next, let’s look at approaches we can use to reduce lock contention.
How to Reduce Lock Contention
There are two main techniques we can use to address and reduce lock contention in our programs.
- Reduce lock frequency.
- Reduce lock duration.
We may be able to reduce the frequency and duration of the locks directly.
Alternatively, we might consider a framework under which the locks are used in the program.
- Reduce lock scope.
- Increase lock granularity.
If we must suffer some contention for locks in our application, there are two approaches we may use to reduce their effects.
- Block before acquiring the lock.
- Back-off while waiting for the lock.
Let’s take a closer look at each approach in turn.
Reduce Lock Frequency
The more often a lock is used within the program, the more likely lock contention will occur.
As such, we can reduce the likelihood of lock contention by limiting the use of a lock as much as possible within the program.
The other way to reduce the fraction of time that a lock is held (and therefore the likelihood that it will be contended) is to have threads ask for it less often.— Page 233, Java Concurrency in Practice, 2006.
This may involve an audit of the usage of the lock to confirm that it is indeed protecting the same or related critical sections in the program.
One approach to reducing lock frequency is by increasing the lock granularity.
Increase Lock Granularity
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 contention may be reduced by increasing the granularity of the lock.
Two approaches to increasing lock granularity are lock splitting and lock stripping.
- Lock Splitting: Split a critical section of multiple variables protected by one lock into multiple critical sections per variable each protected by their own lock.
- Lock Striping: Split a data structure protected by one lock into multiple partitions or stripes each protected by their own lock.
Lock splitting can be achieved by splitting up a critical section into multiple critical sections, perhaps one per variable. Then adding a new lock for each new critical section.
This can be accomplished by lock splitting and lock striping, which involve using separate locks to guard multiple independent state variables previously guarded by a single lock.— Page 233, Java Concurrency in Practice, 2006.
For example, perhaps a lock protected four variables. Lock granularity could be increased by separating the four variables into four critical sections, then adding three additional locks so that each variable was protected by its own lock.
This may allow the frequency of any given lock to be reduced throughout the application.
Alternately, splitting a lock into multiple locks may result in multiple locks with equally high lock contention.
Splitting a heavily contended lock into two is likely to result in two heavily contended locks.— Page 233, Java Concurrency in Practice, 2006.
If a variable being protected is a data structure like a list, set, or dictionary, then it may be possible to split up the data structure into sub-structures. Each sub-structure may then be protected by its own lock, reducing contention. This is called lock striping.
Lock splitting can sometimes be extended to partition locking on a variable-sized set of independent objects, in which case it is called lock striping.— Page 233, Java Concurrency in Practice, 2006.
Another approach might be to split up the responsibilities on the objects that are being protected.
For example, if a resource is being protected, then perhaps the responsibilities of reading from the resource can be separated from the responsibility of writing to the resource, each protected by their own lock.
This highlights that scope may refer to the set of variables being protected or the set of responsibilities being protected by a lock.
- Scope of Variables: Increase lock granularity by decreasing the number of variables protected by a lock.
- Scope of Responsibilities: Increase lock granularity by decreasing the number of responsibilities protected by a lock.
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.
Reduce Lock Duration
The longer a lock is held within the program, the more likely that lock contention will occur.
As such, we can reduce lock contention by holding a lock for as short a time as possible in the program.
An effective way to reduce the likelihood of contention is to hold locks as briefly as possible.— Page 233, Java Concurrency in Practice, 2006.
This may involve an audit of the usage of the lock to confirm that it is indeed protecting the minimum amount of code that requires protection from race conditions.
One approach to reducing lock duration is by decreasing the lock scope.
Reduce Lock Scope
Lock scope refers to the amount of code protected by a lock.
A large scope refers to a lot of code protected by a lock, whereas a small scope refers to less code or instructions protected by a lock.
- Large Lock Scope: Many instructions protected by the lock.
- Small Lock Scope: Fewer instructions protected by the lock.
A smaller scope is preferred as fewer instructions executed while the lock is being held likely means a smaller duration of time that the lock will be held.
We might consider scope along two dimensions, the lines of code and the time taken to execute each line of code.
- Reduce total lines of code protected by the lock.
- Reduce lines of code that take the longest to execute protected by the lock.
Often code can be re-organized such that a critical section protected by the lock consists of only the state that requires protection, with nothing extraneous.
This can help to reduce the overall number of lines of code protected by a lock.
Perhaps more importantly is the time taken to execute the lines of code protected by a lock. The most time consuming lines of code are blocking function calls.
This can be done by moving code that doesn’t require the lock out of synchronized blocks, especially for expensive operations and potentially blocking operations such as I/O.— Page 233, Java Concurrency in Practice, 2006.
Perhaps we can audit the code and move out function calls that are particularly slow, requiring that the lock be held for an extended period of time. This might include blocking calls that access external resources.
Block Before Acquiring Lock
Sometimes some lock contention must be suffered, even after our best efforts to reduce the duration and frequency of the usage of the lock.
One aspect of lock contention is when many threads attempt to acquire a lock at exactly the same time.
This puts a burden on the lock itself, and perhaps the underlying mechanics in the C-code or the operating system in terminating what thread can acquire the lock and what threads must block wait and in what order.
We may reduce this direct contention by reducing the number of threads that simultaneously attempt to acquire the lock.
This can be achieved by introducing a small sleep prior to acquiring the lock.
The interval may be small, much less than a second, such as a random number of a few milliseconds, a few tens of milliseconds or a few hundreds of milliseconds, depending on the application.
Sleep is a system call that blocks the current thread of execution.
This can be achieved via the time.sleep() function and specifying the time interval in seconds to block before acquiring the lock, such as 1 for one second or 0.100 for 100 milliseconds.
A random interval in the desired range can be used to reduce the simultaneous attempt at acquiring the lock. This can be achieved via the random.random() function.
# block for a random amount between 0 and 1 seconds
# acquire the lock
You can learn more about sleeping threads in this tutorial:
Back-Off While Waiting for Lock
Lock contention may be a part of a concurrent program.
One approach to reducing contention for a lock is to add a back-off.
Whenever a thread sees the lock has become free but fails to acquire it, it backs off before retrying.— Page 154, The Art of Multiprocessor Programming, 2020.
If a thread attempts to acquire a lock, rather than block until the lock becomes available, the thread may try to acquire the lock again after some interval of time, called a back-off interval.
- Back-Off Interval: The time waited before a thread makes another attempt to acquire a lock that is currently unavailable.
As the number of attempts to acquire the lock are tried and fail, the back-off interval can be increased as a function of the number of failed attempts to acquire the lock.
- Linear Back-Off: Back-off interval increases as a linear function of the number of attempts to acquire the lock.
- Exponential Back-Off: Back-off interval increases as an exponential function (e.g. doubles) of the number of attempts to acquire the lock.
An exponential back-off function that doubles for each failed attempt to acquire a lock is a popular approach used in concurrency programming, and in other domains for the broader problem of resource contention.
A good rule of thumb is that the larger the number of unsuccessful tries, the higher the likely contention, so the longer the thread should back off. To incorporate this rule, each time a thread tries and fails to get the lock, it doubles the expected back-off time, up to a fixed maximum.— Page 154, The Art of Multiprocessor Programming, 2020.
The back-off interval may be seeded with a random initial interval to avoid multiple threads attempting to acquire the lock at the same time, in lock-step.
To ensure that competing threads do not fall into lockstep, each backing off and then trying again to acquire the lock at the same time, the thread backs off for a random duration.— Page 154, The Art of Multiprocessor Programming, 2020.
You now know how to identify and fix reduce contention in Python.
Do you have any questions?
Ask your questions in the comments below and I will do my best to answer.