Spinlock

From Wikipedia, the free 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. 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 (aka "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, both preventing other threads from running and requiring re-scheduling. The longer you hold the lock, the greater the risk that you will be interrupted by the O/S scheduler while holding it. If this happens, other threads will be left spinning on the lock, despite the fact that you are not making progress towards releasing it. This is especially true on a single-processor system, where each waiting thread of the same priority is likely to waste its full quantum spinning until the thread that holds the lock is finally re-scheduled.

Implementing spinlocks is difficult, because one must take account of 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 implemented from high level languages like C.^[1] 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 in use.

1 Example implementation
2 Significant optimisations
3 Alternatives
4 References
5 See also
6 External links

[edit] 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.

[edit] Significant optimisations

The above is a simple implementation which is easy to understand (if you know x86 assembler), and works on all x86 architecture CPUs. However a number of very effective performance optimisations 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 optimisation is effective on all CPU architectures that have a cache per CPU, because MESI is so ubiquitous.

To reduce power consumption, during the above loop the rep nop instruction is used which tells some x86 CPUs to relax and save power. (It is ignored on others). This instruction may also improve fairness of lock acquisition, though fairness is more of a problem with some other CPU architectures.

[edit] 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 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).^[2]

[edit] References

^ Silberschatz, Abraham; Galvin, Peter B. (1994). Operating System Concepts, Fourth Edition, Addison-Wesley, pp176-179. ISBN 0-201-59292-4.
^ Silberschatz, Abraham; Galvin, Peter B. (1994). Operating System Concepts, Fourth Edition, Addison-Wesley, p198. ISBN 0-201-59292-4.