Spinlock
Encyclopedia
In software engineering
, a spinlock is a lock
where the thread
simply waits in a loop ("spins") 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
. Once acquired, spinlocks will usually be held until they are explicitly released, although in some implementations they may be automatically released if the thread being waited on (that which holds the lock) blocks, or "goes to sleep".
Spinlocks are efficient if thread
s are only likely to be blocked for a short period of time, as they avoid overhead from operating system
process re-scheduling
or context switch
ing. For this reason, spinlocks are often used inside operating system kernels. However, spinlocks become wasteful if held for longer durations, preventing other threads from running and requiring re-scheduling. The longer a lock is held by a thread, the greater the risk that it will be interrupted by the OS scheduler while holding the lock. If this happens, other threads will be left "spinning" (repeatedly trying to acquire the lock), while the thread holding the lock is not making progress towards releasing it. The result is an indefinite postponement until the thread holding the lock can finish and release it. This is especially true on a single-processor system, where each waiting thread of the same priority is likely to waste its quantum (allocated time where a thread can run) spinning until the thread that holds the lock is finally finished.
Implementing spin locks correctly is difficult because one must take into account the possibility of simultaneous access to the lock to prevent race condition
s. Generally this is only possible with special assembly language
instructions, such as atomic test-and-set
operations, and cannot be easily implemented in high-level programming language
s or those languages which don't support truly atomic operations. On architectures without such operations, or if high-level language implementation is required, a non-atomic locking algorithm may be used, e.g. Peterson's algorithm
. But note that such an implementation may require more memory than a spinlock, be slower to allow progress after unlocking, and may not be implementable in a high-level language if out-of-order execution
is allowed.
Intel syntax
lock: ; The lock variable. 1 = locked, 0 = unlocked.
dd 0
spin_lock:
mov eax, 1 ; Set the EAX register to 1.
xchg eax, [lock] ; Atomically swap the EAX register with
; the lock variable.
; This will always store 1 to the lock, leaving
; previous value in the EAX register.
test eax, eax ; Test EAX with itself. Among other things, this will
; set the processor's Zero Flag if EAX is 0.
; If EAX is 0, then the lock was unlocked and
; we just locked it.
; Otherwise, EAX is 1 and we didn't acquire the lock.
jnz spin_lock ; Jump back to the XCHG instruction if the Zero Flag is
; not set; the lock was previously locked, and so
; we need to spin until it becomes unlocked.
ret ; The lock has been acquired, return to the calling
; function.
spin_unlock:
mov eax, 0 ; Set the EAX register to 0.
xchg eax, [lock] ; Atomically swap the EAX register with
; the lock variable.
ret ; The lock has been released.
On later implementations of the x86 architecture, spin_unlock can safely use an unlocked MOV instead of the locked XCHG, which is much faster. This is due to subtle memory ordering
rules which support this, even though MOV isn't a full memory barrier
. However some processors (some Cyrix
processors, some revisions of the Intel Pentium Pro
(due to bugs), and earlier Pentium and i486 SMP
systems) will do the wrong thing and data protected by the lock could be corrupted. On most non-x86 architectures, explicit memory barrier instructions or atomic instructions (like in the example) must be used, or there may be special "unlock" instructions (as on IA-64) which provide the needed memory ordering.
To reduce inter-CPU bus traffic, when the lock is not acquired, the code should loop reading without trying to write anything, until it reads a changed value. Because of MESI caching protocols, this causes the cache line for the lock to become "Shared"; then there is remarkably no bus traffic while a CPU is waiting for the lock. This optimization is effective on all CPU architectures that have a cache per CPU, because MESI is so widespread.
Most operating systems (including Solaris, Mac OS X
and FreeBSD
) use a hybrid approach called "adaptive mutex
". The idea is to use a spinlock when trying to access a resource locked by a currently-running thread, but to sleep if the thread is not currently running. (The latter is always the case on single-processor systems.)
which arms it upon firing. Implemented on gun-launched ammunition, the rotation imparted on the projectile causes the lock to disengage from a "safe" condition to an "armed" one.
Software engineering
Software Engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software...
, a spinlock is a lock
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:...
where the thread
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...
simply waits in a loop ("spins") 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
Busy waiting
In software engineering, busy-waiting or spinning is a technique in which a process repeatedly checks to see if a condition is true, such as whether keyboard input is available, or if a lock is available. Spinning can also be used to generate an arbitrary time delay, a technique that was necessary...
. Once acquired, spinlocks will usually be held until they are explicitly released, although in some implementations they may be automatically released if the thread being waited on (that which holds the lock) blocks, or "goes to sleep".
Spinlocks are efficient if thread
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...
s are only likely to be blocked for a short period of time, as they avoid overhead from operating system
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
process re-scheduling
Scheduling (computing)
In computer science, a scheduling is the method by which threads, processes or data flows are given access to system resources . This is usually done to load balance a system effectively or achieve a target quality of service...
or context switch
Context switch
A context switch is the computing process of storing and restoring the state of a CPU so that execution can be resumed from the same point at a later time. This enables multiple processes to share a single CPU. The context switch is an essential feature of a multitasking operating system...
ing. For this reason, spinlocks are often used inside operating system kernels. However, spinlocks become wasteful if held for longer durations, preventing other threads from running and requiring re-scheduling. The longer a lock is held by a thread, the greater the risk that it will be interrupted by the OS scheduler while holding the lock. If this happens, other threads will be left "spinning" (repeatedly trying to acquire the lock), while the thread holding the lock is not making progress towards releasing it. The result is an indefinite postponement until the thread holding the lock can finish and release it. This is especially true on a single-processor system, where each waiting thread of the same priority is likely to waste its quantum (allocated time where a thread can run) spinning until the thread that holds the lock is finally finished.
Implementing spin locks correctly is difficult because one must take into account the possibility of simultaneous access to the lock to prevent race condition
Race condition
A race condition or race hazard is a flaw in an electronic system or process whereby the output or result of the process is unexpectedly and critically dependent on the sequence or timing of other events...
s. Generally this is only possible with special assembly language
Assembly language
An assembly language is a low-level programming language for computers, microprocessors, microcontrollers, and other programmable devices. It implements a symbolic representation of the machine codes and other constants needed to program a given CPU architecture...
instructions, such as atomic test-and-set
Test-and-set
In computer science, the test-and-set instruction is an instruction used to write to a memory location and return its old value as a single atomic operation. If multiple processes may access the same memory, and if a process is currently performing a test-and-set, no other process may begin...
operations, and cannot be easily implemented in high-level programming language
High-level programming language
A high-level programming language is a programming language with strong abstraction from the details of the computer. In comparison to low-level programming languages, it may use natural language elements, be easier to use, or be from the specification of the program, making the process of...
s or those languages which don't support truly atomic operations. On architectures without such operations, or if high-level language implementation is required, a non-atomic locking algorithm may be used, e.g. Peterson's algorithm
Peterson's algorithm
Peterson's algorithm is a concurrent programming algorithm for mutual exclusion that allows two processes to share a single-use resource without conflict, using only shared memory for communication. It was formulated by Gary L. Peterson in 1981...
. But note that such an implementation may require more memory than a spinlock, be slower to allow progress after unlocking, and may not be implementable in a high-level language if out-of-order execution
Out-of-order execution
In computer engineering, out-of-order execution is a paradigm used in most high-performance microprocessors to make use of instruction cycles that would otherwise be wasted by a certain type of costly delay...
is allowed.
Example implementation
The following example uses x86 assembly language to implement a spinlock. It will work on any Intel 80386 compatible processor.Intel syntax
lock: ; The lock variable. 1 = locked, 0 = unlocked.
dd 0
spin_lock:
mov eax, 1 ; Set the EAX register to 1.
xchg eax, [lock] ; Atomically swap the EAX register with
; the lock variable.
; This will always store 1 to the lock, leaving
; previous value in the EAX register.
test eax, eax ; Test EAX with itself. Among other things, this will
; set the processor's Zero Flag if EAX is 0.
; If EAX is 0, then the lock was unlocked and
; we just locked it.
; Otherwise, EAX is 1 and we didn't acquire the lock.
jnz spin_lock ; Jump back to the XCHG instruction if the Zero Flag is
; not set; the lock was previously locked, and so
; we need to spin until it becomes unlocked.
ret ; The lock has been acquired, return to the calling
; function.
spin_unlock:
mov eax, 0 ; Set the EAX register to 0.
xchg eax, [lock] ; Atomically swap the EAX register with
; the lock variable.
ret ; The lock has been released.
Significant optimizations
The above is a simple implementation which is easy to understand (for a programmer who understands x86 assembly language) and works on all x86 architecture CPUs. However a number of performance optimizations are possible:On later implementations of the x86 architecture, spin_unlock can safely use an unlocked MOV instead of the locked XCHG, which is much faster. This is due to subtle memory ordering
Memory ordering
Memory ordering is a group of properties of the modern microprocessors, characterising their possibilities in memory operations reordering. It is a type of out-of-order execution. Memory reordering can be used to fully utilize different cache and memory banks.On most modern uniprocessors memory...
rules which support this, even though MOV isn't a full memory barrier
Memory barrier
Memory barrier, also known as membar or memory fence or fence instruction, is a type of barrier and a class of instruction which causes a central processing unit or compiler to enforce an ordering constraint on memory operations issued before and after the barrier instruction.CPUs employ...
. However some processors (some Cyrix
Cyrix
Cyrix Corporation was a microprocessor developer that was founded in 1988 in Richardson, Texas as a specialist supplier of high-performance math coprocessors for 286 and 386 microprocessors. The company was founded by former Texas Instruments staff members and had a long but troubled relationship...
processors, some revisions of the Intel Pentium Pro
Pentium Pro
The Pentium Pro is a sixth-generation x86 microprocessor developed and manufactured by Intel introduced in November 1, 1995 . It introduced the P6 microarchitecture and was originally intended to replace the original Pentium in a full range of applications...
(due to bugs), and earlier Pentium and i486 SMP
Symmetric multiprocessing
In computing, symmetric multiprocessing involves a multiprocessor computer hardware architecture where two or more identical processors are connected to a single shared main memory and are controlled by a single OS instance. Most common multiprocessor systems today use an SMP architecture...
systems) will do the wrong thing and data protected by the lock could be corrupted. On most non-x86 architectures, explicit memory barrier instructions or atomic instructions (like in the example) must be used, or there may be special "unlock" instructions (as on IA-64) which provide the needed memory ordering.
To reduce inter-CPU bus traffic, when the lock is not acquired, the code should loop reading without trying to write anything, until it reads a changed value. Because of MESI caching protocols, this causes the cache line for the lock to become "Shared"; then there is remarkably no bus traffic while a CPU is waiting for the lock. This optimization is effective on all CPU architectures that have a cache per CPU, because MESI is so widespread.
Alternatives
The primary disadvantage of a spinlock is that it wastes time while waiting to acquire the lock that might be productively spent elsewhere. There are two alternatives that avoid this:- Do not acquire the lock. In many situations it is possible to design data structures that do not require lockingNon-blocking synchronizationIn computer science, a non-blocking algorithm ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion...
, e.g. by using per thread data, or by using per-cpu data and disabling interrupts. - Switch to a different thread while waiting (sometimes called sleeplocks). This typically involves attaching the current thread to a queue of threads waiting for the lock, followed by switching to another thread that is ready to do some useful work. This scheme also has the advantage that it guarantees that resource starvationResource starvationIn computer science, starvation is a multitasking-related problem, where a process is perpetually denied necessary resources. Without those resources, the program can never finish its task....
does not occur as long as all threads eventually relinquish locks they acquire and scheduling decisions can be made about which thread should progress first.
Most operating systems (including Solaris, Mac OS X
Mac OS X
Mac OS X is a series of Unix-based operating systems and graphical user interfaces developed, marketed, and sold by Apple Inc. Since 2002, has been included with all new Macintosh computer systems...
and FreeBSD
FreeBSD
FreeBSD is a free Unix-like operating system descended from AT&T UNIX via BSD UNIX. Although for legal reasons FreeBSD cannot be called “UNIX”, as the direct descendant of BSD UNIX , FreeBSD’s internals and system APIs are UNIX-compliant...
) use a hybrid approach called "adaptive mutex
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...
". The idea is to use a spinlock when trying to access a resource locked by a currently-running thread, but to sleep if the thread is not currently running. (The latter is always the case on single-processor systems.)
Other Meanings
In a military context, the term "spin lock" can be used to refer to a mechanism within a munition's fuzeFuze
Fuze Beverage, commercially referred to as just Fuze , is a manufacturer of teas and non-carbonated fruit drinks enriched with vitamins. Currently the brand consists of five vitamin-infused lines: Slenderize, Refresh, Tea, Defensify, and Vitalize...
which arms it upon firing. Implemented on gun-launched ammunition, the rotation imparted on the projectile causes the lock to disengage from a "safe" condition to an "armed" one.
See also
- synchronizationSynchronization (computer science)In computer science, synchronization refers to one of two distinct but related concepts: synchronization of processes, and synchronization of data. Process synchronization refers to the idea that multiple processes are to join up or handshake at a certain point, so as to reach an agreement or...
- Busy spin
- deadlockDeadlockA 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"...
- seqlockSeqlockA seqlock is a special locking mechanism used in Linux for supporting fast writes of shared variables between two parallel operating system routines. The semantics stabilized as of version 2.5.59, and they are present in the 2.6.x stable kernel series...
- ticket lockTicket lockIn computer science, a ticket lock is a locking algorithm that is a type of spinlock which uses "tickets" to control which thread of execution is allowed to enter a critical section.-Overview:...
External links
- pthread_spin_lock documentation from The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition
- Spinlock Implementations and Latency
- Article "User-Level Spin Locks - Threads, Processes & IPC" by Gert Boddaert
- Paper "The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors" by Thomas AndersonThomas AndersonThomas Anderson may refer to:*Thomas David Anderson , Scottish astronomer*Thomas H. Anderson, Jr. , American diplomat*Thomas H. Anderson , United States federal judge*Thomas J...
- Paper "Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors" by John M. Mellor-Crummey and Michael L. ScottMichael L. ScottMichael Lee Scott is a professor of computer science at the University of Rochester in Rochester, New York.-Education and teaching:...
. This paper received the 2006 Dijkstra Prize in Distributed Computing. - Spin-Wait Lock by Jeffrey RichterJeffrey RichterJeffrey Richter is a co-founder of Wintellect. He has written a number of books on programming for Windows and .NET.-Bibliography:* CLR via C#, Third Edition...
- Austria C++ SpinLock Class Reference
- Interlocked Variable Access(Windows)