自旋锁是免费的吗?
Is a spinlock lock free?
我对这两个概念有点混淆。
wiki上无锁的定义:
A non-blocking algorithm is lock-free if there is guaranteed
system-wide progress
非阻塞的定义:
an algorithm is called non-blocking if failure or suspension of any
thread cannot cause failure or suspension of another thread
我认为自旋锁是无锁的,或者至少是非阻塞的。但现在我不确定。因为根据定义,"spinlock is not lock-free"
对我也有意义。就像,如果持有自旋锁的线程被挂起,那么它会导致其他在外面旋转的线程挂起。所以,根据定义,spinlock
甚至都不是非阻塞的,更不用说无锁了。
我现在很困惑。谁能解释清楚?
任何可以称为锁的东西(在当前线程解锁之前从关键部分排除其他线程)根据定义不是无锁的。是的,自旋锁是一种锁。
如果一个线程在持有锁时休眠,则没有其他线程可以获取它并继续前进,而自旋锁无法阻止这种情况。 OS 可以随时取消调度线程,即使它处于临界区的中间。
请注意 "lock-free" 与 "wait-free" 不同,因此无锁算法仍然可以包含 cmpxchg 重试循环之类的东西,但只要每次都有一个线程成功,它是无锁的。
无等待算法甚至不能做到这一点,最多只能等待竞争原子操作的高速缓存未命中/硬件仲裁。维基百科的 non-blocking algorithm article 更详细地定义了无等待和无锁。
我认为您混淆了 "blocking" 的两个定义。
我想你是在谈论一个 spin_trylock
函数,它 尝试 获取自旋锁 ,并且 returns 如果失败而不是旋转,则会出现错误。所以这在非阻塞的意义上是非阻塞的I/O:失败并出现错误而不是等待资源可用。
这并不意味着系统中的任何线程都在受自旋锁保护的事物上取得进展。它只是意味着您的线程可以在再次尝试之前去做其他事情,而不是需要使用单独的线程在等待获取锁的同时做一些事情。
在无限循环中旋转算作阻塞/未取得进展。对于这个定义,纯自旋锁和(在 OS 帮助下)休眠直到另一个线程解锁的自旋锁之间没有区别。
无锁的定义不涉及浪费 CPU 时间/权力来为独立工作腾出空间。
有点相关:获取无竞争的自旋锁不需要系统调用,这意味着它是一个 "light-weight" 锁。一些锁实现总是使用(相对较慢的)系统调用,即使在无竞争的情况下也是如此。请参阅 Jeff Preshing's Always Use a Lightweight Mutex 文章。另请阅读 Jeff 的其他帖子以了解有关无锁编程的更多信息,因为它们非常出色。事实上,[无锁] 标签 wiki 链接到它们非常好。
我对这两个概念有点混淆。
wiki上无锁的定义:
A non-blocking algorithm is lock-free if there is guaranteed system-wide progress
非阻塞的定义:
an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread
我认为自旋锁是无锁的,或者至少是非阻塞的。但现在我不确定。因为根据定义,"spinlock is not lock-free"
对我也有意义。就像,如果持有自旋锁的线程被挂起,那么它会导致其他在外面旋转的线程挂起。所以,根据定义,spinlock
甚至都不是非阻塞的,更不用说无锁了。
我现在很困惑。谁能解释清楚?
任何可以称为锁的东西(在当前线程解锁之前从关键部分排除其他线程)根据定义不是无锁的。是的,自旋锁是一种锁。
如果一个线程在持有锁时休眠,则没有其他线程可以获取它并继续前进,而自旋锁无法阻止这种情况。 OS 可以随时取消调度线程,即使它处于临界区的中间。
请注意 "lock-free" 与 "wait-free" 不同,因此无锁算法仍然可以包含 cmpxchg 重试循环之类的东西,但只要每次都有一个线程成功,它是无锁的。
无等待算法甚至不能做到这一点,最多只能等待竞争原子操作的高速缓存未命中/硬件仲裁。维基百科的 non-blocking algorithm article 更详细地定义了无等待和无锁。
我认为您混淆了 "blocking" 的两个定义。
我想你是在谈论一个 spin_trylock
函数,它 尝试 获取自旋锁 ,并且 returns 如果失败而不是旋转,则会出现错误。所以这在非阻塞的意义上是非阻塞的I/O:失败并出现错误而不是等待资源可用。
这并不意味着系统中的任何线程都在受自旋锁保护的事物上取得进展。它只是意味着您的线程可以在再次尝试之前去做其他事情,而不是需要使用单独的线程在等待获取锁的同时做一些事情。
在无限循环中旋转算作阻塞/未取得进展。对于这个定义,纯自旋锁和(在 OS 帮助下)休眠直到另一个线程解锁的自旋锁之间没有区别。
无锁的定义不涉及浪费 CPU 时间/权力来为独立工作腾出空间。
有点相关:获取无竞争的自旋锁不需要系统调用,这意味着它是一个 "light-weight" 锁。一些锁实现总是使用(相对较慢的)系统调用,即使在无竞争的情况下也是如此。请参阅 Jeff Preshing's Always Use a Lightweight Mutex 文章。另请阅读 Jeff 的其他帖子以了解有关无锁编程的更多信息,因为它们非常出色。事实上,[无锁] 标签 wiki 链接到它们非常好。