Spinlock

Physically, the spinlock is a variable in memory and is implemented on atomic operations that must be present in the processor instruction set. Every processor that wants to access a shared resource atomically writes a conditional “ busy ” value to this variable, using an analogue of the swap operation (in the x86 architecture - xchg). If the previous value of the variable (returned by the command) was “ free ”, then this processor is considered to have access to the resource, otherwise the processor returns to the swap operation and runs in a loop, waiting for the spinlock to be released. After working with a shared resource, the processor-owner of the spinlock must write the conditional value “ free ” into it.

An example of a spinlock implementation in x86 assembler:

  mov eax , spinlock_address
 mov ebx , SPINLOCK_BUSY

 wait_cycle:
 xchg [ eax ], ebx ;  xchg is the only instruction that is atomic without the lock prefix
 cmp ebx , SPINLOCK_FREE
 jnz wait_cycle

 ;  <critical section is captured by this thread, here we are working with a shared resource>

 mov eax , spinlock_address
 mov ebx , SPINLOCK_FREE
 xchg [ eax ], ebx ;  used xchg for atomic change
 ;  The last 3 instructions should be replaced by mov [spinlock_address], SPINLOCK_FREE -
 ;  this will increase the speed due to the absence of unnecessary blocking of the tire, and the mov will run atomically
 ;  (but only if the address of the spinlock_address is aligned on the double word boundary)

A more intelligent implementation will use a regular, rather than an atomic operation, for polling in a loop, and an atomic operation - only for capture attempts. The fact is that the implementation of atomic memory operations takes place by hardware blocking of the system bus by the processor for the duration of the atomic operation (which includes reading, modification and writing). During the execution of these three operations, it is impossible to perform any other operations on the bus, which reduces the performance of other processors in the system (if they share a common bus ), even if they have nothing to do with this spinlock.

Also used so-called. queued spinlocks - "spinlock with a queue." In them, instead of assigning 0 or 1 to an atomic variable, an atomic addition of the structure to the head of the list is used, while the head of the list is an atomic variable of the “pointer” type.

Useful properties of queued spinlocks:

• guarantee of the order of provision in the order of request, the guarantee of "starvation"
• in the polling cycle, each processor polls its local variable
• exactly 1 atomic operation during capture and exactly 1 at release

Spinlock is used to synchronize small sections of code when the use of more complex mechanisms is unjustified or impossible. The implementation of synchronization primitives and the thread manager necessarily requires locks that protect lists of streams that are ready for execution, and lists of streams waiting on objects. Such a lock can only be a spinlock because of its very low level. Thus, the spinlock is the lowest synchronization primitive on which the implementation of all the others is based.

There is a widespread belief that user applications running multi-tasking OSs do not allow the use of spin locks, since waiting for a spinlock to be released leads to active waiting in a cycle, wasting computer processor resources, and for synchronizing user programs, high-level primitives should be used, which assume a passive wait - if this thread cannot continue execution, then it gives control to the OS, and does not spin in the sleep loop, sleep Lok (which can be potentially infinite). In fact, this statement is 100% valid only for single-processor systems. In many cases, the use of spinlock in SMP configurations leads to an increase in efficiency if polling and capture of the spinlock are faster than invoking the capture of a mutex in the core.

The main criterion here is contention - the "hardness" of competition for the resource. A lightly loaded resource that is not a popular place of performance behaves differently than it is heavily loaded, captured and released very often.

In addition, in the same Windows, there are types of mutexes (for example, the well-known CRITICAL_SECTION, or FAST_MUTEX in the kernel), which first work as a spinlock, using a polled value in memory, and only after a large number of polls, go to the kernel to block waiting Such objects combine the best qualities of spin locks (minimum capture price) and mutexes (no waste of processor resources for polling).

Cases when the use of spinlock in space gives a tangible effect:

• Inside the section of the protected code there are several related variables, the modification time of which can be hundreds or even thousands of times less than the context switch by the processor, which is a particularly expensive operation, especially on modern systems.
• Blocking not of code sections, but of data (with each data structure that should atomically change as a whole, the spinlock is connected, protecting it)
• Code optimization when it is necessary to reduce the load arising due to too frequent context switching

Cases where the use of spinlock is not justified and is a waste of processor resources:

• Long blocking operations inside the protected area of ​​the code (disk and network I / O can take a very long time by processor standards)
• Single-processor configurations - the processor spends the rest of the time quantum in the idle cycle.

On modern processors, the wait cycle can be performed very quickly due to the peculiarities of the pipeline architecture, which, in addition to winding idle cycles, can lead to more intensive heating than during normal operation.

In the Pentium 4 and subsequent Intel processor models, a special assembler command was introduced to insert into the pause loop ( opcode 0xf3 0x90, similar to the rep nop command for compatibility with older processors), the purpose of which is to instruct the processor that this cycle is a wait cycle and allows the processor to support multiple threads on one core go to the next thread.

Windows versions of Windows 7 are optimized to work as a “guest” in a virtual machine, and instead of pause, when the OS is running as a guest, they use the special call “notify the hypervisor that we are in a wait cycle”.

• Spin blocks are used to provide exclusive access to the flow of the protected data structure. In this case, no distinction is made either between the flows themselves or between the operations performed. However, often in real-world applications, streams can be divided into “Reading” and “Writing”. For this asymmetric case, it is more advisable to use RWLock . The structure can be simultaneously used by an unlimited number of streams in the “read only” mode, at the same time giving protection to the integrity of data upon the arrival of a “writing” stream.
• There are also non-blocking algorithms based on atomic collision detection. They are optimized for the optimistic case in which the entire collision check is reduced to one atomic assembler operation ( Compare And Swap , on the x86 architecture, the cmpxchg command)

Spinlock with automatic escalation before capturing a full-fledged mutex after the expiration of a certain number of cycle turns is used, for example, in critical sections of Windows for optimization, which consists in the absence of references to a mutex in the absence of competition for a resource.

• M. Russinovich , D. Solomon. 1 // Microsoft Windows internal device. - 6th ed .. - St. Petersburg. : Peter, 2013. - p. 218-222. - 800 s. - ("Master Class"). - ISBN 978-5-459-01730-4 .
• Walter They. Using Microsoft Windows Driver Model. - 2nd ed .. - SPb. : Peter, 2007. - p. 173-178. - 764 s. - ISBN 978-5-91180-057-4 .

• DISPATCH LEVEL
• DPC
• IRQL