40

我正在使用自旋锁来保护一个非常小的关键部分。争用很少发生，因此自旋锁比常规互斥锁更合适。

我当前的代码如下，并假设 x86 和 GCC：

volatile int exclusion = 0;

void lock() {
    while (__sync_lock_test_and_set(&exclusion, 1)) {
        // Do nothing. This GCC builtin instruction
        // ensures memory barrier.
    }
}

void unlock() {
    __sync_synchronize(); // Memory barrier.
    exclusion = 0;
}

所以我想知道：

  • 这段代码正确吗？它是否正确地确保了互斥？
  • 它适用于所有 x86 操作系统吗？
  • 它也适用于 x86_64 吗？在所有操作系统上？
  • 是最优的吗？
    • 我见过使用比较和交换的自旋锁实现，但我不确定哪个更好。
    • 根据 GCC atomic builtins 文档（http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html），还有__sync_lock_release. 我不是记忆障碍方面的专家，所以我不确定我是否可以使用它而不是__sync_synchronize.
    • 我正在针对没有争用的情况进行优化。

我根本不在乎争吵。可能有 1 个，也可能有 2 个其他线程试图每隔几天锁定一次自旋锁。

4

11 回答 11

22

在我看来很好。顺便说一句，这是即使在有争议的情况下也更有效的教科书实现。

void lock(volatile int *exclusion)
{
    while (__sync_lock_test_and_set(exclusion, 1))
        while (*exclusion)
            ;
}
于 2009-09-05T14:50:23.653 回答
18

所以我想知道：

* Is it correct?

在提到的上下文中，我会说是的。

* Is it optimal?

这是一个加载的问题。通过重新发明轮子，您也在重新发明许多其他实现已经解决的问题

  • 我希望在您没有尝试访问锁定字的情况下出现故障循环。

  • 在解锁中使用完整屏障只需要具有释放语义（这就是您使用 __sync_lock_release 的原因，这样您就可以在 itanium 上获得 st1.rel 而不是 mf，或者在 powerpc 上获得 lwsync，...）。如果您真的只关心 x86 或 x86_64，那么这里使用的屏障类型与否并不重要（但如果您在哪里跳转到英特尔的安腾以获得 HP-IPF 端口，那么您不会想要这个）。

  • 您没有通常在废物循环之前放置的 pause() 指令。

  • 当有争执时，你想要一些东西，semop，甚至绝望地睡个懒觉。如果你真的需要这给你带来的性能，那么 futex 建议可能是一个不错的选择。如果您需要性能，这对您来说已经足够糟糕以维护此代码，您需要进行大量研究。

请注意，有一条评论说不需要释放屏障。即使在 x86 上也不是这样，因为释放屏障也可以作为编译器的指令，不要在“屏障”周围打乱其他内存访问。非常类似于使用asm ("" ::: "memory" ) 得到的结果。

* on compare and swap

在 x86 上，sync_lock_test_and_set 将映射到具有隐含锁定前缀的 xchg 指令。绝对是最紧凑的生成代码（尤其是如果您使用字节作为“锁定字”而不是 int），但与使用 LOCK CMPXCHG 时一样正确。比较和交换的使用可用于更高级的算法（例如将指向第一个“服务员”的元数据的非零指针放入失败时的锁定字中）。

于 2009-10-13T17:29:50.623 回答
4

针对您的问题：

  1. 在我看来没问题
  2. 假设操作系统支持 GCC（并且 GCC 已经实现了功能）；这应该适用于所有 x86 操作系统。GCC 文档建议，如果给定平台不支持它们，则会产生警告。
  3. 这里没有具体的 x86-64，所以我不明白为什么不这样做。这可以扩展到涵盖GCC 支持的任何架构，但是在非 x86 架构上可能有更优化的方法来实现这一点。
  4. __sync_lock_release()在这种情况下使用可能会稍微好一些unlock()；因为这将减少锁并在单个操作中添加内存屏障。但是，假设您的断言很少会发生争用；对我来说看起来不错。
于 2009-09-05T14:02:21.263 回答
4

我想知道以下 CAS 实现是否是 x86_64 上的正确实现。在我的 i7 X920 笔记本电脑（fedora 13 x86_64，gcc 4.4.5）上，它几乎快了两倍。

inline void lock(volatile int *locked) {
    while (__sync_val_compare_and_swap(locked, 0, 1));
    asm volatile("lfence" ::: "memory");
}
inline void unlock(volatile int *locked) {
    *locked=0;
    asm volatile("sfence" ::: "memory");
}
于 2010-11-24T20:55:20.027 回答
3

如果您使用的是最新版本的 Linux，则可以使用futex—— “快速用户空间互斥锁”：

一个正确编程的基于 futex 的锁不会使用系统调用，除非锁被争用

在无争议的情况下，您尝试使用自旋锁进行优化，futex 的行为就像自旋锁一样，不需要内核系统调用。如果锁被争用，则等待发生在内核中，而不是忙等待。

于 2009-09-05T16:29:20.530 回答
2

我无法评论正确性，但在我阅读问题正文之前，您的问题的标题就提出了一个危险信号。同步原语非常难以确保正确性......如果可能的话，最好使用设计/维护良好的库，也许是pthreads或boost::thread。

于 2009-09-05T14:22:35.437 回答
1

有一些错误的假设。

首先，SpinLock 只有在资源被锁定在另一个 CPU 上时才有意义。如果资源被锁定在同一个 CPU 上（在单处理器系统上总是如此），您需要放松调度程序以解锁资源。您当前的代码将在单处理器系统上运行，因为调度程序会自动切换任务，但这会浪费资源。

在多处理器系统上，可能会发生同样的事情，但任务可能会从一个 CPU 迁移到另一个 CPU。简而言之，如果您保证您的任务将在不同的 CPU 上运行，则使用自旋锁是正确的。

其次，在解锁时锁定互斥锁的速度很快（与自旋锁一样快）。仅当互斥锁已被锁定时，互斥锁锁定（和解锁）才会很慢（非常慢）。

所以，在你的情况下，我建议使用互斥锁。

于 2014-07-25T09:37:50.587 回答
1

为了使您的自旋锁实现更有效，您可以在锁获取失败时让步给调度程序。

void lock() {
    while (__sync_lock_test_and_set(&exclusion, 1)) yield(-1) ;
}
于 2021-11-13T16:34:38.180 回答
0

建议的一项改进是使用TATAS (test-and-test-and-set)。使用 CAS 操作对于处理器来说被认为是相当昂贵的，所以如果可能的话最好避免它们。另一件事，确保您不会遭受优先级倒置（如果具有高优先级的线程试图获取锁而低优先级的线程试图释放锁怎么办？例如，在 Windows 上，这个问题最终将通过以下方式解决调度程序使用优先级提升，但您可以明确放弃线程的时间片，以防您在最近 20 次尝试中未能成功获取锁定（例如..）

于 2009-09-05T14:45:16.813 回答
0

您的解锁过程不需要内存屏障；只要在 x86 上对齐双字，排除的分配就是原子的。

于 2009-09-05T15:15:31.833 回答
0

在 x86 (32/64) 的特定情况下，我认为解锁代码中根本不需要内存栅栏。x86 不进行任何重新排序，除了首先将存储放入存储缓冲区中，因此它们变得可见可能会延迟其他线程。如果线程尚未刷新到内存，则执行存储然后从同一变量读取的线程将从其存储缓冲区中读取。因此，您需要的只是一个asm防止编译器重新排序的语句。从其他线程的角度来看，您可能会冒一个线程持有锁的时间比必要时间稍长的风险，但是如果您不关心争用，那应该没关系。事实上，pthread_spin_unlock在我的系统（linux x86_64）上是这样实现的。

我的系统也实现了pthread_spin_lock使用lock decl lockvar; jne spinloop;而不是使用xchg（这是__sync_lock_test_and_set使用），但我不知道是否真的存在性能差异。

于 2013-03-03T18:52:36.750 回答