4 ms·

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 d

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.
- mips_r4300i 3y ago
  Really good information. I have only used naive spinlocks on hacky ducttape for embedded RTOSes. And most of the time those will provide better mutex or semaphore functions you should be using instead of the spinwait. Interesting that the example uses ARM but the moral of the story is "you shouldn't need to do this, and if you do, you have bigger problems"
- kccqzy 3y ago
  IMO the only use case for trivial spin locks is to be used by the implementation of a more sophisticated mutex implementation. It helps to implement a mutex that starts with a spin lock, spins a short while during lock acquisition, and then falls back to FUTEX_WAIT.
  - jeffbee 3y ago
    Sure, because putting futex into the critical path of uncontended locks would be an efficiency disaster. All the major libraries and runtimes spin for a bit before resorting to futex.
    - adrian_b 3y ago
      I do not believe that spinning a bit before invoking the operating system is an efficient method. Checking at least once if the lock is free is absolutely necessary before invoking the operating system. Optionally, it is good to wait a short time (e.g. with an empty loop) and then check again if the lock is free, before invoking the operating system to wait. On the other hand, to execute repeatedly in a loop atomic read-memory-write instructions on the address contended with other threads wastes energy and it wastes time for the other threads, due to the generated cache traffic. Even if spinning on the lock gives a higher chance for your thread to be the first that will get the lock, this makes the performance worse for the whole system. If you must be certain that no other thread gets the lock before, at least a ticket lock should be used, if not a better queued lock.
      - jeffbee 3y ago
        If you define spinning to mean the most naive and bad way to repeatedly check a condition, then yes that would be bad, tautologically. Some libraries have used the x86 PAUSE instruction or its equivalent. Recent x86 offers UMWAIT which is also applicable. These are both good and efficient ways to briefly wait.
- gpderetta 3y ago
  I have used one bit spinlocks to protect the wait queue of a more sophisticated waiting primitive for an user-space[1] application. Adding to the queue and signalling all could be done lock-free, but lock-free removal of a waiter before a signal (which I needed to support) is quite complicated, and borrowing a bit from the wait list head field to encode a list-deleter spinlock was the best solution. [1] one-thread per core, pinned, isolcpu, NO_HZ, etc. The usual.
- bonzini 3y ago
  There are plans to support userspace spinlocks in Linux by letting a userspace program borrow from the next scheduling quantum: https://lwn.net/Articles/948870/ https://lwn.net/Articles/948870/
- Veserv 3y ago
  The second and third class, as described, do not support release/“stop wait” before acquisition. Once you start waiting you must continue waiting until you acquire the lock and then release otherwise it stalls forever. I imagine it might be solvable if each acquire, B, also atomically encodes its acquire criteria to the previous acquire, A, so that if A does a early release it can forward its acquire criteria to B.

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.

mips_r4300i 3y ago
Really good information. I have only used naive spinlocks on hacky ducttape for embedded RTOSes. And most of the time those will provide better mutex or semaphore functions you should be using instead of the spinwait. Interesting that the example uses ARM but the moral of the story is "you shouldn't need to do this, and if you do, you have bigger problems"
kccqzy 3y ago
IMO the only use case for trivial spin locks is to be used by the implementation of a more sophisticated mutex implementation. It helps to implement a mutex that starts with a spin lock, spins a short while during lock acquisition, and then falls back to FUTEX_WAIT.
- jeffbee 3y ago
  Sure, because putting futex into the critical path of uncontended locks would be an efficiency disaster. All the major libraries and runtimes spin for a bit before resorting to futex.
  - adrian_b 3y ago
    I do not believe that spinning a bit before invoking the operating system is an efficient method. Checking at least once if the lock is free is absolutely necessary before invoking the operating system. Optionally, it is good to wait a short time (e.g. with an empty loop) and then check again if the lock is free, before invoking the operating system to wait. On the other hand, to execute repeatedly in a loop atomic read-memory-write instructions on the address contended with other threads wastes energy and it wastes time for the other threads, due to the generated cache traffic. Even if spinning on the lock gives a higher chance for your thread to be the first that will get the lock, this makes the performance worse for the whole system. If you must be certain that no other thread gets the lock before, at least a ticket lock should be used, if not a better queued lock.
    - jeffbee 3y ago
      If you define spinning to mean the most naive and bad way to repeatedly check a condition, then yes that would be bad, tautologically. Some libraries have used the x86 PAUSE instruction or its equivalent. Recent x86 offers UMWAIT which is also applicable. These are both good and efficient ways to briefly wait.
gpderetta 3y ago
I have used one bit spinlocks to protect the wait queue of a more sophisticated waiting primitive for an user-space[1] application. Adding to the queue and signalling all could be done lock-free, but lock-free removal of a waiter before a signal (which I needed to support) is quite complicated, and borrowing a bit from the wait list head field to encode a list-deleter spinlock was the best solution. [1] one-thread per core, pinned, isolcpu, NO_HZ, etc. The usual.
bonzini 3y ago
There are plans to support userspace spinlocks in Linux by letting a userspace program borrow from the next scheduling quantum: https://lwn.net/Articles/948870/ https://lwn.net/Articles/948870/
Veserv 3y ago
The second and third class, as described, do not support release/“stop wait” before acquisition. Once you start waiting you must continue waiting until you acquire the lock and then release otherwise it stalls forever. I imagine it might be solvable if each acquire, B, also atomically encodes its acquire criteria to the previous acquire, A, so that if A does a early release it can forward its acquire criteria to B.