Page namespace (page_namespace) | 0 |
Page title without namespace (page_title) | 'Spinlock' |
Full page title (page_prefixedtitle) | 'Spinlock' |
Last ten users to contribute to the page (page_recent_contributors) | [
0 => 'Ale2006',
1 => 'Addbot',
2 => 'Boleyn',
3 => 'Zakblade2000',
4 => '54.240.196.185',
5 => 'Infinitywater',
6 => 'Rubinbot',
7 => 'Mcaramel',
8 => 'Jfmantis',
9 => 'Gpvos'
] |
Old page wikitext, before the edit (old_wikitext) | '{{ref improve|date=October 2012}}
In [[software engineering]], a '''spinlock''' is a [[lock (computer science)|lock]] which causes a [[thread (computer science)|thread]] trying to acquire it to simply wait in a loop ("spin") while repeatedly checking if the lock is available. Since the thread remains active but is not 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".
Because they avoid overhead from [[operating system]] [[Scheduling (computing)|process re-scheduling]] or [[context switch]]ing, spinlocks are efficient if [[thread (computer science)|thread]]s are only likely to be blocked for a short period. For this reason, spinlocks are often used inside [[operating system kernel]]s. However, spinlocks become wasteful if held for longer durations, as they may prevent other threads from running and require re-scheduling. The longer a lock is held by a thread, the greater the risk is that the thread 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, which could cause [[race condition]]s. Generally this is only possible with special [[assembly language]] instructions, such as [[atomic operation|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.<ref>{{cite book | last=Silberschatz| first=Abraham | coauthors=Galvin, Peter B. | title=Operating System Concepts | edition=Fourth Edition | year=1994 | publisher=Addison-Wesley | pages=176–179 | isbn=0-201-59292-4 }}</ref> 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.
==Example implementation==
The following example uses x86 assembly language to implement a spinlock. It will work on any [[Intel]] [[80386]] compatible processor.
<syntaxhighlight lang="asm">
; Intel syntax
locked: ; The lock variable. 1 = locked, 0 = unlocked.
dd 0
spin_lock:
mov eax, 1 ; Set the EAX register to 1.
xchg eax, [locked] ; 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 MOV 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, [locked] ; Atomically swap the EAX register with
; the lock variable.
ret ; The lock has been released.
</syntaxhighlight>
==Significant optimizations==
The simple implementation above works on all CPUs using the x86 architecture. 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 slower locked XCHG. This is due to subtle [[memory ordering]] rules which support this, even though MOV is not a full [[memory barrier]]. However, some processors (some [[Cyrix]] processors, some revisions of the [[Intel]] [[Pentium Pro]] (due to bugs), and earlier [[Pentium (brand)|Pentium]] and [[i486]] [[Symmetric multiprocessing|SMP]] systems) will do the wrong thing and data protected by the lock could be corrupted. On most non-x86 architectures, explicit memory barrier or atomic instructions (as in the example) must be used. On some systems, such as [[IA-64]], there are special "unlock" instructions which provide the needed memory ordering.
To reduce inter-CPU [[Bus (computing)|bus traffic]], code trying to acquire a lock 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 waits 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, while waiting to acquire a lock, it wastes time that might be productively spent elsewhere. There are two ways to avoid this:
# Do not acquire the lock. In many situations it is possible to design data structures that [[Non-blocking synchronization|do not require locking]], e.g. by using per-thread or per-CPU data and disabling interrupts.
# [[Context switch|Switch]] to a different thread while waiting. 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 starvation]] 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. Spinlocks that never entail switching, usable by [[real-time operating system]], are sometimes called ''raw spinlocks''.<ref>{{cite web |url=http://lwn.net/Articles/365863/ |title=Spinlock naming resolved |author=Jonathan Corbet |date=9 December 2009 |publisher=[[LWN.net]] |accessdate=14 May 2013}}</ref>
Most operating systems (including [[Solaris (operating system)|Solaris]], [[Mac OS X]] and [[FreeBSD]]) use a hybrid approach called "adaptive [[Mutual exclusion|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.)<ref>{{cite book | last=Silberschatz| first=Abraham | coauthors=Galvin, Peter B. | title=Operating System Concepts | edition=Fourth Edition | year=1994 | publisher=Addison-Wesley | pages=198 | isbn=0-201-59292-4}}</ref>
==Other meanings==
In a military context, the term "spin lock" can be used to refer to a mechanism within a munition's [[fuze]] 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==
*[[Synchronization (computer science)|Synchronization]]
*[[Busy spin]]
*[[Deadlock]]
*[[Seqlock]]
*[[Ticket lock]]
==References==
<references/>
==External links==
*[http://www.opengroup.org/onlinepubs/009695399/functions/pthread_spin_lock.html pthread_spin_lock documentation] from The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition
*[http://concurrencykit.org/cgit/cgit.cgi/ck/tree/include/ck_spinlock.h Variety of spinlock Implementations] from Concurrency Kit
*Article "[http://codeproject.com/threads/spinlocks.asp User-Level Spin Locks - Threads, Processes & IPC]" by [[Gert Boddaert]]
*Paper "[http://www.cs.washington.edu/homes/tom/pubs/spinlock.html The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors]" by [[Thomas Anderson]]
*Paper "[http://portal.acm.org/citation.cfm?id=103727.103729 Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors]" by [[John M. Mellor-Crummey]] and [[Michael L. Scott]]. This paper received the [http://www.podc.org/dijkstra/2006.html 2006 Dijkstra Prize in Distributed Computing].
*[http://msdn.microsoft.com/en-us/magazine/cc163726.aspx Spin-Wait Lock] by [[Jeffrey Richter]]
*[http://austria.sourceforge.net/dox/html/classSpinLock.html Austria C++ SpinLock Class Reference]
*[http://msdn2.microsoft.com/en-us/library/ms684122(VS.85).aspx Interlocked Variable Access(Windows)]
[[Category:Concurrency control algorithms]]
[[Category:Programming constructs]]' |
New page wikitext, after the edit (new_wikitext) | '{{ref improve|date=October 2012}}
In [[software engineering]], a '''spinlock''' is a [[lock (computer science)|lock]] which causes a [[thread (computer science)|thread]] trying to acquire it to simply wait in a loop ("spin") while repeatedly checking if the lock is available. Since the thread remains active but is not 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".
Because they avoid overhead from [[operating system]] [[Scheduling (computing)|process re-scheduling]] or [[context switch]]ing, spinlocks are efficient if [[thread (computer science)|thread]]s are only likely to be blocked for a short period. For this reason, spinlocks are often used inside [[operating system kernel]]s. However, spinlocks become wasteful if held for longer durations, as they may prevent other threads from running and require re-scheduling. The longer a lock is held by a thread, the greater the risk is that the thread 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, which could cause [[race condition]]s. Generally this is only possible with special [[assembly language]] instructions, such as [[atomic operation|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.<ref>{{cite book | last=Silberschatz| first=Abraham | coauthors=Galvin, Peter B. | title=Operating System Concepts | edition=Fourth Edition | year=1994 | publisher=Addison-Wesley | pages=176–179 | isbn=0-201-59292-4 }}</ref> 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.
==Example implementation==
The following example uses x86 assembly language to implement a spinlock. It will work on any [[Intel]] [[80386]] compatible processor.
<syntaxhighlight lang="asm">
; Intel syntax
locked: ; The lock variable. 1 = locked, 0 = unlocked.
dd 0
spin_lock:
mov eax, 1 ; Set the EAX register to 1.
xchg eax, [locked] ; 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 MOV 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, [locked] ; Atomically swap the EAX register with
; the lock variable.
ret ; The lock has been released.
</syntaxhighlight>
==Significant optimizations==
The simple implementation above works on all CPUs using the x86 architecture. 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 slower locked XCHG. This is due to subtle [[memory ordering]] rules which support this, even though MOV is not a full [[memory barrier]]. However, some processors (some [[Cyrix]] processors, some revisions of the [[Intel]] [[Pentium Pro]] (due to bugs), and earlier [[Pentium (brand)|Pentium]] and [[i486]] [[Symmetric multiprocessing|SMP]] systems) will do the wrong thing and data protected by the lock could be corrupted. On most non-x86 architectures, explicit memory barrier or atomic instructions (as in the example) must be used. On some systems, such as [[IA-64]], there are special "unlock" instructions which provide the needed memory ordering.
To reduce inter-CPU [[Bus (computing)|bus traffic]], code trying to acquire a lock 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 waits 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, while waiting to acquire a lock, it wastes time that might be productively spent elsewhere. There are two ways to avoid this:
# Do not acquire the lock. In many situations it is possible to design data structures that [[Non-blocking synchronization|do not require locking]], e.g. by using per-thread or per-CPU data and disabling interrupts.
# [[Context switch|Switch]] to a different thread while waiting. 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 starvation]] 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. Spinlocks that never entail switching, usable by [[real-time operating system]], are sometimes called ''raw spinlocks''.<ref>{{cite web |url=http://lwn.net/Articles/365863/ |title=Spinlock naming resolved |author=Jonathan Corbet |date=9 December 2009 |publisher=[[LWN.net]] |accessdate=14 May 2013}}</ref>
Most operating systems (including [[Solaris (operating system)|Solaris]], [[Mac OS X]] and [[FreeBSD]]) use a hybrid approach called "adaptive [[Mutual exclusion|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.)<ref>{{cite book | last=Silberschatz| first=Abraham | coauthors=Galvin, Peter B. | title=Operating System Concepts | edition=Fourth Edition | year=1994 | publisher=Addison-Wesley | pages=198 | isbn=0-201-59292-4}}</ref>
==See also==
*[[Synchronization (computer science)|Synchronization]]
*[[Busy spin]]
*[[Deadlock]]
*[[Seqlock]]
*[[Ticket lock]]
==References==
<references/>
==External links==
*[http://www.opengroup.org/onlinepubs/009695399/functions/pthread_spin_lock.html pthread_spin_lock documentation] from The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition
*[http://concurrencykit.org/cgit/cgit.cgi/ck/tree/include/ck_spinlock.h Variety of spinlock Implementations] from Concurrency Kit
*Article "[http://codeproject.com/threads/spinlocks.asp User-Level Spin Locks - Threads, Processes & IPC]" by [[Gert Boddaert]]
*Paper "[http://www.cs.washington.edu/homes/tom/pubs/spinlock.html The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors]" by [[Thomas Anderson]]
*Paper "[http://portal.acm.org/citation.cfm?id=103727.103729 Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors]" by [[John M. Mellor-Crummey]] and [[Michael L. Scott]]. This paper received the [http://www.podc.org/dijkstra/2006.html 2006 Dijkstra Prize in Distributed Computing].
*[http://msdn.microsoft.com/en-us/magazine/cc163726.aspx Spin-Wait Lock] by [[Jeffrey Richter]]
*[http://austria.sourceforge.net/dox/html/classSpinLock.html Austria C++ SpinLock Class Reference]
*[http://msdn2.microsoft.com/en-us/library/ms684122(VS.85).aspx Interlocked Variable Access(Windows)]
[[Category:Concurrency control algorithms]]
[[Category:Programming constructs]]' |
