Spinlock

Spinlock

In software engineering, a spinlock is a lock where the thread simply waits in a loop ("spins") repeatedly checking until the lock becomes available. As 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 blocks, or "goes to sleep".

Spinlocks are efficient if threads are only likely to be blocked for a short period of time, as they avoid overhead from operating system process re-scheduling or context switching. For this reason, spinlocks are often used inside operating system kernels. However, spinlocks become wasteful if held for longer durations, both 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 O/S 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 a semi-deadlock 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 each 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 conditions. 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 languages or those languages which don't support truly atomic operations. [cite book | last=Silberschatz| first=Abraham | coauthors=Galvin, Peter B. | title=Operating System Concepts | edition=Fourth Edition | year=1994 | publisher=Addison-Wesley | pages=pp176-179 | id=ISBN 0-201-59292-4 ] 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.

lock: # The lock variable. 1 = locked, 0 = unlocked. dd 0 spin_lock: mov eax, 1 # Set the EAX register to 1. loop: 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 loop # Jump back to the XCHG instruction if the Zero Flag is # not set, the lock was locked, and we need to spin. 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.

ignificant optimizations

The above is a simple implementation which is easy to understand (for a programmer who understands x86 assembler) 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 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 IA64) which provide the necessary 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 ubiquitous.

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 locking, 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, then switching to another one. This scheme also has the advantages 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.

Some operating systems use a hybrid approach called "adaptive mutex" where a spinlock is used initially, but the thread suspends itself if it does not progress quickly. Solaris will use a spinlock when trying to access a resource locked by a currently-running thread, but will sleep if the thread is not currently running (which always happens on single-processor systems). [cite book | last=Silberschatz| first=Abraham | coauthors=Galvin, Peter B. | title=Operating System Concepts | edition=Fourth Edition | year=1994 | publisher=Addison-Wesley | pages=p198 | id=ISBN 0-201-59292-4]

ee also

*synchronization
*deadlock
*seqlock

References

External links

* [http://www.opengroup.org/onlinepubs/009695399/functions/pthread_spin_lock.html Description] from The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition
*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)]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Spinlock — En programmation informatique, le spinlock ou verrou tournant est un mécanisme simple de synchronisation basé sur l attente active. Algorithme TestAndSet(*s, v) { s< v return prev(s) } //Instruction Atomique (ie non interruptible) init(s) {… …   Wikipédia en Français

  • Spinlock — Ein Spinlock (Spin Lock) ist ein Mechanismus zur Prozesssynchronisation. Es ist eine Sperre (Lock) zum Schutz einer gemeinsam genutzten Ressource durch konkurrierende Prozesse bzw. Threads (siehe Kritischer Abschnitt). Die Sperre wird umgesetzt… …   Deutsch Wikipedia

  • Spinlock — Для улучшения этой статьи желательно?: Викифицировать статью. Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное …   Википедия

  • Spinlock — En ingeniería de software, un spinlock es cuando un hilo (o thread) simplemente espera en un bucle ( spins ) repetidamente hasta que se cumple una condición, como por ejemplo la llegada de un paquete por la red o un semáforo que se haga… …   Wikipedia Español

  • Spinlock — En ingeniería de software, un spinlock es cuando un hilo (o thread) simplemente espera en un bucle ( spins ) repetidamente hasta que se cumple una condición, como por ejemplo la llegada de un paquete por la red o un semáforo que se haga… …   Enciclopedia Universal

  • 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 waiting for keyboard input or waiting for a lock to become available. It can also be used to delay… …   Wikipedia

  • Gegenseitiger Ausschluss — Der Begriff Wechselseitiger Ausschluss bzw. Mutex (Abk. für engl. mutual exclusion, auf deutsch etwa wechselseitiger Ausschluss) bezeichnet eine Gruppe von Verfahren, mit denen das Problem des kritischen Abschnitts gelöst wird. Mutex Verfahren… …   Deutsch Wikipedia

  • Wechselseitiger Ausschluss — Der Begriff Wechselseitiger Ausschluss bzw. Mutex (Abk. für engl. mutual exclusion, auf deutsch etwa wechselseitiger Ausschluss) bezeichnet eine Gruppe von Verfahren, mit denen das Problem des kritischen Abschnitts gelöst wird. Mutex Verfahren… …   Deutsch Wikipedia

  • Lock convoy — 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 …   Wikipedia

  • Test-and-set — In computer science, the test and set instruction is an instruction used to both test and (conditionally) write to a memory location as part of a single atomic (i.e. non interruptible) operation. This means setting a value, but first performing… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”