使用 fetch-and-add 作为锁

Question

我正在尝试了解如何将 fetch-and-add 用作锁。这是这本书（OS 的：3 篇简单的文章）所说的：

The basic operation is pretty simple: when a thread wishes to acquire a lock, it first does an atomic fetch-and-add on the ticket value; that value is now considered this thread’s “turn” (myturn). The globally shared lock->turn is then used to determine which thread’s turn it is; when (myturn == turn) for a given thread, it is that thread’s turn to enter the critical section.

我不明白的是线程在进入线程之前如何检查是否被另一个进程持有锁。我只能读到价值会增加，没有提到支票！

另一部分说：

Unlock is accomplished simply by incrementing the turn such that the next waiting thread (if there is one) can now enter the critical section.

我无法以不执行检查的方式来解释，这不可能是真的，因为它包含了锁定秘密部分的全部目的。我在这里错过了什么？谢谢

Answer 1

What I do not understand is how the thread checks if the lock held by another process before entering the cretical seection.

为此您需要一个 "atomic fetch"，可能类似于“while( atomic_fetch(currently_serving) != my_ticket) { /* wait */ }”。

如果您有 "atomic fetch and add"，那么您可以通过执行 "atomic fetch and add the value zero" 来实现 "atomic fetch"，也许类似于“while( atomic_fetch_and_add(currently_serving, 0) != my_ticket) { /* wait */ }”。

供参考；完整的序列可能是这样的：

    my_ticket = atomic_fetch_and_add(ticket_counter, 1);

    while( atomic_fetch_and_add(currently_serving, 0) != my_ticket) {
        /* wait */
    }

    /* Critical section (lock successfully acquired). */

    atomic_fetch_and_add(currently_serving, 1);   /* Release the lock */

当然，您可以使用更好的原子提取（例如，对于某些 CPU，任何正常对齐的加载都是原子的）。

使用 fetch-and-add 作为锁

Using fetch-and-add as lock

x86

multithreading

operating-system

locking

mutual-exclusion