3 ms·

A close look at a spinlock (2021)

87 points by signa11 3y ago

e1ghtSpace 3y ago
well you know
adrian_b 3y ago
While it gives examples of all alternatives, this blog post is not clear enough in explaining the differences between them. For releasing a lock, it is obvious enough that a single atomic store is sufficient. All CPUs provide store instructions that are atomic when certain restrictions on size and alignment are observed. So the only part that is tricky is acquiring the lock. A loop is needed to wait when the lock is owned by another thread, until the lock is released. So the question is what must be put in the wait loop. There are many variants, but they can be grouped in 3 classes, from the least efficient to the most efficient. The worst method for acquiring the lock is to use an atomic read-modify-write instruction in the wait loop, like in the first example from the blog posting. Historically, this is the earliest proposed method, with atomic test-and-set used first by Univac, then atomic swap proposed by Dijkstra, then atomic compare-and-swap used by IBM System/370. In modern computers with memories that are very slow in comparison with the CPUs and with complex cache hierarchies, the atomic read-modify-write instructions have a very high overhead and using any of them inside a wait loop is a big mistake. The second class of methods for acquiring the lock is improved over the first by moving the atomic read-modify-write instruction before the wait loop and using just a load-acquire instruction inside the loop. The best known method of this second class is the ticket lock, where, before waiting, a ticket is obtained with an atomic fetch-and-increment instruction, then the order number for the next owner of the lock is loaded in the loop, until it becomes equal to the ticket obtained previously. For this second class, there remains a reason for low efficiency, that all the threads that wait to acquire the lock load a value from the same address. Most of the time they load the value from their own cache, with minimum overhead, but every time when a thread releases the lock its new value will have to be broadcasted to the caches of all other threads, generating a great number of transfers. The third class of methods for acquiring a lock is like the second, except that it eliminates the contention for a single memory address that is loaded in the wait loop. To achieve this, the unique location that is known by all threads is no longer a location tested inside the loop, but it is used outside the loop to provide the address that should be tested inside the loop and which must be different for each waiting thread, so there will be no contention inside the wait loops as all loads will be from different addresses. This kind of queuing for acquiring a lock can be achieved e.g. when each thread that wants to acquire a lock uses an atomic exchange instruction to obtain the address from which it should load values to determine when the lock becomes released, while simultaneously storing the address where it will signal the release of the lock, providing it for the next thread which will want to acquire the lock. Normally the first 2 classes of lock acquiring methods are only of historical interest, there is no reason to ever use them, because they do not have any advantage in comparison with the third class of methods, which minimize the overhead of the wait loops by having inside the loops only a load-acquire instruction from addresses that are distinct for all threads.
- bonzini 3y ago
  The test-and-set lock has the "advantage" of being unfair. Being unfair could be seen as a problem, and indeed it is, especially when access to memory takes a time that depends on who performs the access. However, if the lock holder could be preempted, and you have no way to schedule it back, it will cause all waiters to delay even if one is runnable, and that will quickly send performance down a cliff. For that reason test-and-set spinlocks are sometimes used in userspace or in virtual machines.
- gpderetta 3y ago
  The first method has the advantage of being very simple and only takes one bit of space. Also if your spin lock is almost always uncontended there very little difference, while if it is contended probably a spin lock is not appropriate anyway. So I wouldn't consider trivial spinlocks just of historical interest.
  - adrian_b 3y ago
    In user-mode programs where simple mutual exclusion is needed, trivial spinlocks shall never be used, but only operating system functions like FUTEX_WAIT on Linux or WaitOnAddress on Windows. In privileged code or in sophisticated user-mode applications, e.g. where the OS scheduler is bypassed and the threads are pinned on cores, trivial spin locks shall never be used, but only deterministic, efficient and fair spin locks. So in my opinion there does not exist any use case when trivial spin locks can be recommended. The spin lock acquiring methods of the first class that I have mentioned, even if they require the least storage, i.e. of only one cache line, they are not even deterministic, i.e. they do not guarantee forward progress for the thread that attempts to acquire the lock. The second and the third class always guarantee forward progress. In the simplest case they ensure FIFO behavior for the lock, but they can be modified to implement a priority queue for the threads waiting to acquire the lock. A ticket lock requires only 2 cache lines instead of 1 cache line, while the third class of methods require one cache line per thread, besides one cache line known globally. This extra space is almost always negligible.
    - 3y ago
dang 3y ago
Discussed at the time: A Close Look at a Spinlock - https://news.ycombinator.com/item?id=29133386 https://news.ycombinator.com/item?id=29133386 - Nov 2021 (27 comments)
alecco 3y ago
Lower level details (x86): https://wiki.osdev.org/Spinlock https://wiki.osdev.org/Spinlock ARM implementation with LDAXR: https://github.com/ARM-software/arm-trusted-firmware/blob/master/lib/locks/exclusive/aarch64/spinlock.S https://github.com/ARM-software/arm-trusted-firmware/blob/ma...

87 points by signa11 3y ago

well you know

While it gives examples of all alternatives, this blog post is not clear enough in explaining the differences between them. For releasing a lock, it is obvious enough that a single atomic store is sufficient. All CPUs provide store instructions that are atomic when certain restrictions on size and alignment are observed. So the only part that is tricky is acquiring the lock. A loop is needed to wait when the lock is owned by another thread, until the lock is released. So the question is what must be put in the wait loop. There are many variants, but they can be grouped in 3 classes, from the least efficient to the most efficient. The worst method for acquiring the lock is to use an atomic read-modify-write instruction in the wait loop, like in the first example from the blog posting. Historically, this is the earliest proposed method, with atomic test-and-set used first by Univac, then atomic swap proposed by Dijkstra, then atomic compare-and-swap used by IBM System/370. In modern computers with memories that are very slow in comparison with the CPUs and with complex cache hierarchies, the atomic read-modify-write instructions have a very high overhead and using any of them inside a wait loop is a big mistake. The second class of methods for acquiring the lock is improved over the first by moving the atomic read-modify-write instruction before the wait loop and using just a load-acquire instruction inside the loop. The best known method of this second class is the ticket lock, where, before waiting, a ticket is obtained with an atomic fetch-and-increment instruction, then the order number for the next owner of the lock is loaded in the loop, until it becomes equal to the ticket obtained previously. For this second class, there remains a reason for low efficiency, that all the threads that wait to acquire the lock load a value from the same address. Most of the time they load the value from their own cache, with minimum overhead, but every time when a thread releases the lock its new value will have to be broadcasted to the caches of all other threads, generating a great number of transfers. The third class of methods for acquiring a lock is like the second, except that it eliminates the contention for a single memory address that is loaded in the wait loop. To achieve this, the unique location that is known by all threads is no longer a location tested inside the loop, but it is used outside the loop to provide the address that should be tested inside the loop and which must be different for each waiting thread, so there will be no contention inside the wait loops as all loads will be from different addresses. This kind of queuing for acquiring a lock can be achieved e.g. when each thread that wants to acquire a lock uses an atomic exchange instruction to obtain the address from which it should load values to determine when the lock becomes released, while simultaneously storing the address where it will signal the release of the lock, providing it for the next thread which will want to acquire the lock. Normally the first 2 classes of lock acquiring methods are only of historical interest, there is no reason to ever use them, because they do not have any advantage in comparison with the third class of methods, which minimize the overhead of the wait loops by having inside the loops only a load-acquire instruction from addresses that are distinct for all threads.

bonzini 3y ago
The test-and-set lock has the "advantage" of being unfair. Being unfair could be seen as a problem, and indeed it is, especially when access to memory takes a time that depends on who performs the access. However, if the lock holder could be preempted, and you have no way to schedule it back, it will cause all waiters to delay even if one is runnable, and that will quickly send performance down a cliff. For that reason test-and-set spinlocks are sometimes used in userspace or in virtual machines.
gpderetta 3y ago
The first method has the advantage of being very simple and only takes one bit of space. Also if your spin lock is almost always uncontended there very little difference, while if it is contended probably a spin lock is not appropriate anyway. So I wouldn't consider trivial spinlocks just of historical interest.
- adrian_b 3y ago
  In user-mode programs where simple mutual exclusion is needed, trivial spinlocks shall never be used, but only operating system functions like FUTEX_WAIT on Linux or WaitOnAddress on Windows. In privileged code or in sophisticated user-mode applications, e.g. where the OS scheduler is bypassed and the threads are pinned on cores, trivial spin locks shall never be used, but only deterministic, efficient and fair spin locks. So in my opinion there does not exist any use case when trivial spin locks can be recommended. The spin lock acquiring methods of the first class that I have mentioned, even if they require the least storage, i.e. of only one cache line, they are not even deterministic, i.e. they do not guarantee forward progress for the thread that attempts to acquire the lock. The second and the third class always guarantee forward progress. In the simplest case they ensure FIFO behavior for the lock, but they can be modified to implement a priority queue for the threads waiting to acquire the lock. A ticket lock requires only 2 cache lines instead of 1 cache line, while the third class of methods require one cache line per thread, besides one cache line known globally. This extra space is almost always negligible.
  - 3y ago

dang 3y ago

Discussed at the time: A Close Look at a Spinlock - https://news.ycombinator.com/item?id=29133386 https://news.ycombinator.com/item?id=29133386 - Nov 2021 (27 comments)

alecco 3y ago

Lower level details (x86): https://wiki.osdev.org/Spinlock https://wiki.osdev.org/Spinlock ARM implementation with LDAXR: https://github.com/ARM-software/arm-trusted-firmware/blob/master/lib/locks/exclusive/aarch64/spinlock.S https://github.com/ARM-software/arm-trusted-firmware/blob/ma...