`FUTEX_REQUEUE`的错误是什么？

Question

我在操作系统类中按需要分配Linux FUTEX(2)手册页，作为对学生在设计同步原语时不要自满的警告。

futex()系统调用是Linux提供的允许用户级线程同步原语在必要时休眠和唤醒的API。手册页描述了可以使用futex()系统调用调用的5种不同操作。这两个基本操作是FUTEX_WAIT (当线程试图获取同步对象而有人已经持有它时，线程使用它来使自己休眠)和FUTEX_WAKE (线程用于在释放同步对象时唤醒任何等待的线程)。

接下来的三个操作是乐趣的开始。手册页描述如下：

FUTEX_FD (present up to and including Linux 2.6.25)
       [...]
       Because it was inherently racy, FUTEX_FD has been removed
       from Linux 2.6.26 onward.

论文乌尔里希·德雷珀( Ulrich Dreper，2004 )著的“富特克斯是棘手的”描述了这种竞争状况(这是一种潜在的漏掉的唤醒)。但还有更多：

FUTEX_REQUEUE (since Linux 2.5.70)
       This operation was introduced in order to avoid a
       "thundering herd" effect when FUTEX_WAKE is used and all
       processes woken up need to acquire another futex. [...]

FUTEX_CMP_REQUEUE (since Linux 2.6.7)
       There was a race in the intended use of FUTEX_REQUEUE, so
       FUTEX_CMP_REQUEUE was introduced. [...]

FUTEX_REQUEUE的比赛是什么？Ulrich的文章甚至没有提到它(本文描述了一个使用FUTEX_CMP_REQUEUE实现的函数FUTEX_CMP_REQUEUE，但没有描述FUTEX_REQUEUE操作)。

Answer 1

看起来，种族状况是由于在glibc中实现互斥，以及它们与futexes之间的差异。似乎需要FUTEX_CMP_REQUEUE来支持更复杂的glibc互斥体：

它们要复杂得多，因为它们支持更多的特性，如死锁测试和递归锁定。因此，他们有一个内部锁保护额外的状态。这个额外的锁意味着由于可能的竞争，它们不能使用FUTEX_REQUEUE多路复用函数。

来源：单张/

Answer 2

旧的requeue操作有两个地址addr1和addr2，首先它在addr1上卸载服务生，然后将它们停在addr2上。

新的requeue操作在验证*addr1 == user_provided_val之后执行所有这些操作。

要了解可能的争用条件，请考虑以下两个线程：

wait(cv, mutex);
  lock(&cv.lock);
  cv.mutex_ref = &mutex;
  unlock(&mutex);
  let futexval = ++cv.futex;
  unlock(&cv.lock);
  FUTEX_WAIT(&cv.futex, futexval);   // --- (1)

lock(&mutex);
broadcast(cv);
  lock(&cv.lock);
  let futexval = cv.futex;
  unlock(&cv.lock);
  FUTEX_CMP_REQUEUE(&cv.futex,   // --- (2)
    1 /*wake*/,
    ALL /*queue*/,
    &cv.mutex_ref.lock,
    futexval);

syscall (1)和(2)都是在没有锁的情况下执行的，但它们必须与mutex锁的顺序相同，这样用户就不会出现丢失信号的情况。

因此，为了检测在实际的wait之后重新排序的wake操作，在(2)处将锁中获得的futexval传递给内核。

类似地，我们在(1)处将futexval传递给FUTEX_WAIT调用。这个设计在futex 手册页中得到了明确的说明。

当执行请求阻塞线程的futex操作时，只有当调用线程提供的值(作为futex()调用的参数之一)作为futex字的期望值时，内核才会阻塞。加载futex单词的值，将该值与期望值进行比较，以及实际的阻塞将发生在原子上，并将与其他线程在同一个futex字上执行的并发操作完全排序。因此，使用futex字将用户空间中的同步与内核阻塞的实现连接起来。类似于可能改变共享内存的原子比较和交换操作，通过futex阻塞是一种原子比较和块操作。

IMHO，调用(2)外部锁的原因主要是性能。按着锁时打电话给wake会导致服务员醒来而无法获得锁的情况下“赶快等”的情况。

还值得一提的是，上面的答案是基于p线程实现的历史版本。最新版本的pthread_cond已经删除了REQUEUE的用法。(有关详细信息，请查看此补丁 )。