票务自旋锁互斥体的内存顺序

Question

票务自旋锁互斥体的内存顺序

3

假设我有以下的票据取锁互斥量实现（使用GCC原子内建函数的C语言）。据我所知，在解锁函数中使用“release”内存顺序是正确的。然而，对于锁定函数，我不确定。因为这是一个票据取锁互斥量，有一个字段表示下一个要分配的票号，还有一个字段表示当前持有锁的票号。我在票号递增时使用了acquire-release，而在自旋加载时使用了acquire。这样做是否过于强大，如果是，为什么？

另外，这两个字段（票号和服务中）是否应该分开，以便它们位于不同的缓存行上，或者这并不重要？我主要关注arm64和amd64。

typedef struct {
        u64 ticket;
        u64 serving;
} ticket_mutex;

void
ticket_mutex_lock(ticket_mutex *m)
{
        u64 my_ticket = __atomic_fetch_add(&m->ticket, 1, __ATOMIC_ACQ_REL);
        while (my_ticket != __atomic_load_n(&m->serving, __ATOMIC_ACQUIRE));
}

void
ticket_mutex_unlock(ticket_mutex *m)
{
        (void) __atomic_fetch_add(&m->serving, 1, __ATOMIC_RELEASE);
}

更新：根据被接受答案的建议，我已经调整了实现方式如下。这个互斥锁适用于低并发情况。

typedef struct {
        u32 ticket;
        u32 serving;
} ticket_mutex;

void
ticket_mutex_lock(ticket_mutex *m)
{
        u32 my_ticket = __atomic_fetch_add(&m->ticket, 1, __ATOMIC_RELAXED);
        while (my_ticket != __atomic_load_n(&m->serving, __ATOMIC_ACQUIRE)) {
                #ifdef __x86_64__
                __asm __volatile ("pause");
                #endif
        }
}

void
ticket_mutex_unlock(ticket_mutex *m)
{
        u32 my_ticket = __atomic_load_n(&m->serving, __ATOMIC_RELAXED);
        (void) __atomic_store_n(&m->serving, my_ticket+1, __ATOMIC_RELEASE);
}

- Harris M Snyder

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter Cordes · Accepted Answer

m->ticket的增量只需要是RELAXED。你只需要让每个线程获得一个不同的票号；与同一线程中的其他操作相比，它可以早或晚发生。

load(&m->serving, acquire)是用于排序关键部分的操作，防止这些部分在我们与先前持有锁的unlock函数中的RELEASE操作同步之前开始。因此，m->serving的加载至少需要是acquire。

即使m->ticket++直到获取m->serving的acquire负载后才完成，也没问题。 while条件仍然确定是否（非规范地）进入关键部分执行。规范执行进入关键部分是好的，因为它可能意味着准备更快地提交，减少了保持锁定的时间。

对RMW操作进行额外排序不会使其在本地或线程间可见性方面更快，并且会减慢获取锁的线程。

一个高速缓存行还是两个

为了提高性能，我认为在高争用情况下，将成员保留在单独的高速缓存行中有优势。

需要独占高速缓存行以获取票号的线程不会与解锁.serving的线程竞争，因此这些线程间的延迟可以并行发生。

在自旋等待while(load(serving))循环中有多个核心时，它们可以在本地L1d缓存中命中，直到某些内容使共享行的副本无效，从而不会创建任何额外的流量。但是，除非使用类似于x86 _mm_pause()的东西，否则会浪费大量功率，同时还会浪费可与同一物理上的另一个逻辑核共享的执行资源。 x86 pause也避免了离开自旋循环时的分支错误预测。相关：

指数退避是一种常见的建议，可以在检查之间暂停一些次数，但是在这里我们可以更好地解决：在检查之间使用一些 pause 指令，这些指令的数量与 my_ticket - m->serving 成比例，因此当您的票即将到来时，您会更频繁地进行检查。

在竞争非常激烈的情况下，如果您将等待很长时间，例如 Linux 的 futex，则回退到操作系统辅助的睡眠/唤醒是适当的。或者，由于我们可以看到队列头有多近，如果您的等待间隔将超过 3 或 8 个票号或其他数字，则使用 yield、nanosleep 或 futex。（根据服务一个票所需的时间可以进行调整。）

（使用 futex，您可能需要在解锁时读取 m->ticket，以确定是否存在正在等待通知的线程，就像 C++20 的 atomic<>.wait() 和 atomic.notify_all()。不幸的是，我不知道有什么好方法可以找出要通知哪个线程，而不是叫醒它们所有人以检查是否是幸运的赢家。

在平均竞争较低的情况下，应将两者都保留在同一缓存行中。对 .ticket 的访问总是紧随其后 .serving 的载入。在未锁定且无竞争的情况下，这意味着只有一个缓存行在跳动或必须保持热状态以供相同的内核获取/释放锁。

如果锁已经被持有，则想要解锁的线程需要独占缓存行来进行 RMW 或存储。当另一个内核对包含 .serving 的行进行 RMW 或仅进行纯负载时，它会失去这个操作。

不会有太多情况出现多个等待者都在旋转同一把锁，并且新线程获取票号会延迟解锁及其对等待该锁的线程的可见性。

这是我的直觉；它可能很难进行微基准测试，除非缓存未命中原子 RMW 阻止后续加载甚至开始请求后续行，在这种情况下，您可以在获取锁时产生两个缓存未命中延迟。

如何避免在解锁时进行原子 RMW 操作？

持有锁的线程知道它拥有独占权，没有其他线程会同时修改 m->serving。如果锁所有者记住自己的票号，则可以将解锁优化为仅存储操作。

void ticket_mutex_unlock(ticket_mutex *m, uint32_t ticket_num)
{
        (void) __atomic_store_n(&m->serving, ticket_num+1, __ATOMIC_RELEASE);
}

或者在不进行API更改的情况下（即从u32 ticket_mutex_lock()返回整数），

void ticket_mutex_unlock(ticket_mutex *m)
{
        uint32_t ticket = __atomic_load_n(&m->serving, __ATOMIC_RELAXED);  // we already own the lock
        // and no other thread can be writing concurrently, so a non-atomic increment is safe
        (void) __atomic_store_n(&m->serving, ticket+1, __ATOMIC_RELEASE);
}

这在需要LL/SC重试循环进行原子RMW操作的ISA上具有良好的效率优势，因为另一个核读取值可能会导致虚假失败。而在x86上，唯一可能的原子RMW是完整的屏障，甚至比C的seq_cst语义更强。

顺便说一下，锁字段可以使用uint32_t。你不会有2^32个线程等待锁。因此，我使用了uint32_t而不是u64。循环计数是明确定义的。即使在跨越该包装边界的情况下，如1 - 0xffffffffUL仍然能够正常工作，因此您仍然可以计算离服务有多近，以进行睡眠决策。

对于x86-64来说不是很重要，只能节省一点代码大小，在AArch64上可能根本不起作用。但在一些32位ISA上将会有很大帮助。