Futex 重排 PI¶

将任务从非 PI futex 重新排队到 PI futex 需要进行特殊处理，以确保底层 rt_mutex 在有等待者（waiters）时绝不会没有所有者（owner）；否则将破坏 PI 提升逻辑 [参见 RT-mutex 实现设计]。为简起见，本文档中将此动作统称为 “requeue_pi”。优先级继承（Priority inheritance）在全文中简称为 “PI”。

动机¶

如果没有 requeue_pi，glibc 对 pthread_cond_broadcast() 的实现必须诉诸于唤醒在 pthread_condvar 上等待的所有任务，并让它们以经典的惊群效应（thundering-herd）方式自行争抢哪个任务先运行。理想的实现是唤醒最高优先级的等待者，而将其余部分留给解锁与 condvar 关联的 mutex 时固有的自然唤醒。

考虑简化的 glibc 调用

/* caller must lock mutex */
pthread_cond_wait(cond, mutex)
{
        lock(cond->__data.__lock);
        unlock(mutex);
        do {
        unlock(cond->__data.__lock);
        futex_wait(cond->__data.__futex);
        lock(cond->__data.__lock);
        } while(...)
        unlock(cond->__data.__lock);
        lock(mutex);
}

pthread_cond_broadcast(cond)
{
        lock(cond->__data.__lock);
        unlock(cond->__data.__lock);
        futex_requeue(cond->data.__futex, cond->mutex);
}

一旦 pthread_cond_broadcast() 将任务重新排队，cond->mutex 就有了等待者。请注意，pthread_cond_wait() 仅在返回用户空间后才尝试锁住 mutex。这将导致底层的 rt_mutex 带有等待者却没有所有者，从而破坏前面提到的 PI 提升算法。

为了支持感知 PI 的 pthread_condvar，内核需要能够将任务重新排队到 PI futex。此支持意味着在成功的 futex_wait 系统调用后，调用者在返回用户空间时就已经持有了 PI futex。glibc 的实现将做如下修改

/* caller must lock mutex */
pthread_cond_wait_pi(cond, mutex)
{
        lock(cond->__data.__lock);
        unlock(mutex);
        do {
        unlock(cond->__data.__lock);
        futex_wait_requeue_pi(cond->__data.__futex);
        lock(cond->__data.__lock);
        } while(...)
        unlock(cond->__data.__lock);
        /* the kernel acquired the mutex for us */
}

pthread_cond_broadcast_pi(cond)
{
        lock(cond->__data.__lock);
        unlock(cond->__data.__lock);
        futex_requeue_pi(cond->data.__futex, cond->mutex);
}

实际的 glibc 实现可能会检测 PI 并在现有调用中进行必要的更改，而不是为 PI 情况创建新的调用。pthread_cond_timedwait() 和 pthread_cond_signal() 也需要进行类似的更改。

实现¶

为了确保 rt_mutex 在有等待者时拥有一个所有者，重新排队代码以及等待代码必须都能够在返回用户空间之前获取 rt_mutex。重新排队代码不能简单地唤醒等待者并任由其去获取 rt_mutex，因为这会在重新排队调用返回用户空间与等待者被唤醒并开始运行之间打开一个竞态窗口。在无竞争（uncontended）情况下尤其如此。

该解决方案涉及两个新的 rt_mutex 辅助例程：rt_mutex_start_proxy_lock() 和 rt_mutex_finish_proxy_lock()，它们允许重新排队代码代表等待者获取一个无竞争的 rt_mutex，并将等待者排队到一个有竞争的 rt_mutex 上。两个新的系统调用提供了用于 requeue_pi 的内核<->用户接口：FUTEX_WAIT_REQUEUE_PI 和 FUTEX_CMP_REQUEUE_PI。

FUTEX_WAIT_REQUEUE_PI 由等待者（pthread_cond_wait() 和 pthread_cond_timedwait()）调用，以在初始 futex 上阻塞并等待重新排队到一个感知 PI 的 futex。该实现是 futex_wait() 和 futex_lock_pi() 高速碰撞的产物，并带有用于检查其他唤醒场景的额外逻辑。

FUTEX_CMP_REQUEUE_PI 由唤醒者（pthread_cond_broadcast() 和 pthread_cond_signal()）调用，以重新排队并可能唤醒等待的任务。在内部，此系统调用仍由 futex_requeue 处理（通过传递 requeue_pi=1）。在重新排队之前，futex_requeue() 尝试代表顶层等待者获取重新排队的目标 PI futex。如果可以，该等待者将被唤醒。futex_requeue() 随后继续将剩余的 nr_wake+nr_requeue 个任务重新排队到 PI futex，并在每次重新排队之前调用 rt_mutex_start_proxy_lock()，以将该任务准备为底层 rt_mutex 上的等待者。在此阶段也有可能获取到锁，如果是这样，则唤醒下一个等待者以完成锁的获取。

FUTEX_CMP_REQUEUE_PI 接受 nr_wake 和 nr_requeue 作为参数，但真正重要的是它们的总和。futex_requeue() 将唤醒或重新排队最多 nr_wake + nr_requeue 个任务。它只会唤醒能够为其获取锁的那么多任务，在大多数情况下，这个数字应该是 0，因为良好的编程实践规定 pthread_cond_broadcast() 或 pthread_cond_signal() 的调用者在进行调用之前必须获取 mutex。FUTEX_CMP_REQUEUE_PI 要求 nr_wake=1。对于广播（broadcast），nr_requeue 应该是 INT_MAX；对于信号（signal），应该是 0。

Linux 内核

目录

本页

Futex 重排 PI¶

动机¶

实现¶