Lock convoy
Encyclopedia
In computer science
, a lock convoy is a performance problem that can occur when using locks
for concurrency control
in a multithreaded
application.
A lock convoy occurs when multiple threads
of equal priority contend repeatedly for the same lock. Unlike deadlock
and livelock situations, the threads in a lock convoy do progress; however, each time a thread attempts to acquire the lock and fails, it relinquishes the remainder of its scheduling quantum and forces a context switch. The overhead of repeated context switches and underutilization of scheduling quanta degrade overall performance.
Lock convoys often occur when concurrency control primitives such as critical section
s serialize access to a commonly used resource, such as a memory heap or a thread pool. They can sometimes be addressed by using non-locking alternatives such as lock-free algorithms or by altering the relative priorities of the contending threads.
operating systems provide a good example of how lock convoys can occur. In Windows, critical sections use a combination of a spinlock
and a kernel synchronization object called an "event" to ensure mutual exclusion
. For low-contention critical sections, the spinlock will provide mutual exclusion most of the time, falling back on the event only when a thread fails to acquire the spinlock within a certain amount of time. When contention is high, however, it is possible for many threads to fail to acquire the spinlock and enter a waiting state, all waiting on the same event.
When the event is signaled, all threads that are waiting on the event are woken, but only one will be allowed to acquire the critical section and continue execution; the remaining threads will each block again.
As of Windows 2003, a thread waiting on an event is boosted to 1 priority level more than the thread which "set" (ie: signaled) the event associated to the critical section (aka, the thread releasing the critical section, which notifies other waiters by signaling the event). On the other hand, the setting thread will also lose the boost it may have requested while calling the "Set Event" API, which takes such a boost as a parameter.
These two improvements help against a lock convoy, because now, each waiting thread should be able to run its full quantum, while the thread releasing the lock will probably have to wait more before being able to acquire the resource again.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, a lock convoy is a performance problem that can occur when using locks
Lock (computer science)
In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...
for concurrency control
Concurrency control
In information technology and computer science, especially in the fields of computer programming , operating systems , multiprocessors, and databases, concurrency control ensures that correct results for concurrent operations are generated, while getting those results as quickly as possible.Computer...
in a multithreaded
Thread (computer science)
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...
application.
A lock convoy occurs when multiple threads
Thread (computer science)
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...
of equal priority contend repeatedly for the same lock. Unlike deadlock
Deadlock
A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg"...
and livelock situations, the threads in a lock convoy do progress; however, each time a thread attempts to acquire the lock and fails, it relinquishes the remainder of its scheduling quantum and forces a context switch. The overhead of repeated context switches and underutilization of scheduling quanta degrade overall performance.
Lock convoys often occur when concurrency control primitives such as critical section
Critical section
In concurrent programming a critical section is a piece of code that accesses a shared resource that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task or process will have to wait a fixed time to...
s serialize access to a commonly used resource, such as a memory heap or a thread pool. They can sometimes be addressed by using non-locking alternatives such as lock-free algorithms or by altering the relative priorities of the contending threads.
Example
Critical sections as implemented in Microsoft WindowsMicrosoft Windows
Microsoft Windows is a series of operating systems produced by Microsoft.Microsoft introduced an operating environment named Windows on November 20, 1985 as an add-on to MS-DOS in response to the growing interest in graphical user interfaces . Microsoft Windows came to dominate the world's personal...
operating systems provide a good example of how lock convoys can occur. In Windows, critical sections use a combination of a spinlock
Spinlock
In software engineering, a spinlock is a lock where the thread simply waits in a loop repeatedly checking until the lock becomes available. Since the thread remains active but isn't performing a useful task, the use of such a lock is a kind of busy waiting...
and a kernel synchronization object called an "event" to ensure mutual exclusion
Mutual exclusion
Mutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...
. For low-contention critical sections, the spinlock will provide mutual exclusion most of the time, falling back on the event only when a thread fails to acquire the spinlock within a certain amount of time. When contention is high, however, it is possible for many threads to fail to acquire the spinlock and enter a waiting state, all waiting on the same event.
When the event is signaled, all threads that are waiting on the event are woken, but only one will be allowed to acquire the critical section and continue execution; the remaining threads will each block again.
As of Windows 2003, a thread waiting on an event is boosted to 1 priority level more than the thread which "set" (ie: signaled) the event associated to the critical section (aka, the thread releasing the critical section, which notifies other waiters by signaling the event). On the other hand, the setting thread will also lose the boost it may have requested while calling the "Set Event" API, which takes such a boost as a parameter.
These two improvements help against a lock convoy, because now, each waiting thread should be able to run its full quantum, while the thread releasing the lock will probably have to wait more before being able to acquire the resource again.