Spinlock

From Free net encyclopedia

(Redirected from Spin lock)

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 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 the overhead of operating system process re-scheduling. For this reason, spinlocks are often used within operating system kernels. They are wasteful if the lock is held for a long period of time because they do not allow other threads to run while a thread is waiting for the lock to be released. They are always inefficient if used on systems with only one processor, as no other thread would be able to make progress while the waiting thread spun.

Implementing spinlocks is difficult, because they 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 Example implementation
2 Significant Optimisations
3 Alternatives
4 See also
5 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.
    dword   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.  Implies "lock" asm prefix,
                            #  preventing interleaved access from other CPU(s).
                            # This will always store 1 to the lock, leaving                                                                                
                            #  previous value in eax.
    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, it's 1 and the lock is already
                            #  locked.
                            
    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.

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 very 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.

[edit]