eventual fairness

主线位置：主线 1 里 A 解锁的那一刻。unpark_one 摘下 B 之后、调 callback 之前，算一次 be_fair = bucket.fair_timeout.should_timeout()；RawMutex::unlock_slow 的回调看到 be_fair 就保持上锁、返回 TOKEN_HANDOFF，把锁直接交给 B。

flowchart TB
  u["unpark_one / unpark_requeue / unpark_filter 叫醒了线程"] --> st{"now 超过这个桶的 timeout？"}
  st -->|"否"| nf["be_fair = false：普通解锁，锁放开，被叫醒者回去重抢"]
  st -->|"是"| f["be_fair = true；timeout = now + (xorshift % 1_000_000) ns"]
  f --> h["RawMutex / RawRwLock：保持上锁，TOKEN_HANDOFF"]
  none["没有停车的线程"] --> skip["根本不计算"]

问题：插队让吞吐变高，也让人饿死

一次有竞争的加锁 里，普通解锁把锁放开、叫醒一个等待者，等待者要等 OS 把它调度起来（本机 1–2 µs）才能回来抢；这期间刚解锁的线程自己就能重新加锁。如果它在一个循环里「加锁、干一会儿、解锁、马上再加锁」，等待者几乎永远抢不到。Mutex 的文档把这件事说得很清楚（src/mutex.rs:21-33）：

A typical unfair lock can often end up in a situation where a single thread quickly acquires and releases the same mutex in succession, which can starve other threads waiting to acquire the mutex. While this improves throughput because it doesn't force a context switch when a thread tries to re-acquire a mutex it has just released, this can starve other threads.This mutex uses eventual fairness to ensure that the lock will be fair on average without sacrificing throughput. This is done by forcing a fair unlock on average every 0.5ms, which will force the lock to go to the next thread waiting for the mutex.Additionally, any critical section longer than 1ms will always use a fair unlock, which has a negligible impact on throughput considering the length of the critical section.

文档里的「eventual fairness」链接指向 WebKit 的一个 changeset，出处只交代到这里。

FairTimeout

parking_lot.rs:114-149：

struct FairTimeout {
    // Next time at which point be_fair should be set
    timeout: TimeoutInstant,

    // the PRNG state for calculating the next timeout
    seed: u32,
}

impl FairTimeout {
    // ...
    // Determine whether we should force a fair unlock, and update the timeout
    #[inline]
    fn should_timeout(&mut self) -> bool {
        let now = TimeoutInstant::now();
        if now > self.timeout {
            // Time between 0 and 1ms.
            let nanos = self.gen_u32() % 1_000_000;
            self.timeout = now + Duration::new(0, nanos);
            true
        } else {
            false
        }
    }

    // Pseudorandom number generator from the "Xorshift RNGs" paper ...
    fn gen_u32(&mut self) -> u32 {
        self.seed ^= self.seed << 13;
        self.seed ^= self.seed >> 17;
        self.seed ^= self.seed << 5;
        self.seed
    }
}

• 到期就返回 true，同时把下一次到期定在 now + (随机数 % 1 000 000) ns，即 0 到 1 ms 之间均匀分布，平均 0.5 ms。随机数是 32 位 xorshift，种子在建表时设为桶下标加一（「We must ensure the seed is not zero」，第 77–78 行）。随机间隔避免了多个桶、多把锁在同一时刻集体进入公平模式（推测，注释没有说明为什么要随机）。
• 建表时每个桶的 timeout 设为建表那一刻（第 74 行），所以一个桶第一次被问到时总是到期的：新表上第一次有线程被叫醒的解锁，一定是公平解锁。
• wasm32-unknown-unknown 上 TimeoutInstant 是一个永远相等的空类型（第 18–41 行），now > timeout 永不成立，eventual fairness 实际上关闭。

每个桶一个，不是每把锁一个

fair_timeout 是 Bucket 的字段（parking_lot.rs:89-100）。哈希到同一个桶的所有 key 共用这一个计时器。而 UnparkResult::be_fair 的文档写的是（第 507–510 行）：

This is set to true on average once every 0.5ms for any given key.

以代码为准：「平均每 0.5 ms 一次」是对一个桶而言的。同一个桶里如果有两把都在被频繁交接的锁，一把锁的解锁消耗掉了一次到期，另一把锁就要等下一次（推测的后果：两把锁平均各自每 1 ms 左右才轮到一次公平交接；本卷没有构造同桶的两把锁去实测）。桶数至少是线程数的 3 倍，两把繁忙的锁恰好落在同一个桶的概率不大，但不是零。

什么时候算、谁来用

should_timeout 只在三处被调用，而且都在「确实叫醒了线程」之后：

所以没有线程在停车时，这个机制根本不触发：解锁走快路径，连桶都不碰。它只管「有人睡着在等、而锁一直被别人抢走」这一种情况。

消费方看 be_fair：

• RawMutex::unlock_slow（raw_mutex.rs:299）：unparked_threads != 0 && (force_fair || be_fair) 时保持 LOCKED_BIT、返回 TOKEN_HANDOFF。
• RawRwLock 的两处解锁回调（raw_rwlock.rs:654、804）：同样改走交接。
• Condvar 的 notify_* 不看它：requeue 本来就不交锁。

再看文档里那句「临界区超过 1 ms 的总会走公平解锁」：计时器最多 1 ms 后到期，只要两次解锁之间隔了 1 ms 以上，下一次叫醒线程时 now > timeout 必然成立。所以这句话由代码直接保证，前提是有线程在停车（没人等时没有「公平」可言）。

实验：最长连续独占

E3 在 公平解锁、bump 与 FairMutex 里做了全套（多种线程数、unlock_fair、FairMutex、std）。这里只取最能说明这个机制的一组，在不开 deadlock_detection 的 crate 里重跑。

断言：2 个线程循环「加锁、持锁 h、解锁、立刻重新加锁」，一个线程最长连续拿到锁的次数约为 1 ms / h；没有这个机制的 0.13.0 没有上限。

方法（exp-parking_lot/fairness-nodd，程序与规划阶段的 survey 同源，去掉了 deadlock_detection）：锁里有一个 Vec<u8>，每次拿到锁就推入自己的线程号，持锁期间忙等 h，解锁后不做任何事直接再加锁，总次数达到上限后停止。统计「解锁后自己又拿到」的比例、最长连续次数和两个线程的份额。对照组是规划阶段的 survey-013（parking_lot 0.13.0，本来就不开这个 feature）。

结果：2026-11-01 22:59，开始时负载 1 分钟 1.88、5 分钟 2.94，M2 Max（8P + 4E，macOS 不能绑核），不开 deadlock_detection：

同一天 22:23 还跑过一组，当时 1 分钟负载已被前面的实验抬到 5.2，只作参考，结果一致：10 µs 时 0.12.5 三轮最长连续都是 95，0.13.0 是 17 894、11 103、22 368；100 µs 时 0.12.5 是 10、10、10。

• 0.12.5 把连续独占限制在 1 ms 左右：h = 10 µs 时最长 95 次，95 × 10 µs ≈ 0.95 ms，正好对上计时器 0–1 ms 的上限；h = 100 µs 时最长 10–15 次，即 1.0–1.5 ms。偶尔超出 1 ms（135 次、15 次），推测是计时器到期的那次解锁时对方恰好不在停车（被叫醒后正在回来的路上），交接要等到下一次「有人在停车」的解锁，代码里 should_timeout 只在叫醒了线程时才算。
• 两个线程的份额都是 50 / 50，平均连续次数约 46：平均每 0.46 ms 换一次手，和「平均 0.5 ms」一致。
• 0.13.0 没有上限：自取比例 100.0%，最长连续 1.9 万到 3 万次（0.19–0.30 秒），份额偏到 63 / 37。这是「去掉这个机制」的天然对照。
• 反向验证：h = 1 ms 时，每次解锁距离上一次计时器重置都已超过 1 ms，按上面「临界区超过 1 ms 一定公平」的推导，每次都应交接：实测三轮自取比例 0.0%、最长连续 1，严格交替。

演进

• 9322f98「Add support for eventual fairness and fair mutex unlocking」（2016-08-25）：FairTimeout、be_fair、unlock_fair 一起加入。
• 0.13 起不同：#533 中的 8cfdedb「Remove eventual fairness」去掉了这个机制和 UnparkResult::be_fair 字段，unlock_fair / FairMutex 保留。依赖它防饿死的程序升级后要改用显式的公平解锁，见 07 0.13 的变化。

小结

• FairTimeout 在 Bucket 里，每个桶一个；到期就返回 true，下一次定在 0–1 ms 之后（平均 0.5 ms）。文档说「对任意给定的 key」，代码是对整个桶。
• 只在叫醒了线程时计算；没人停车时不触发。
• RawMutex 和 RawRwLock 看到 be_fair 就保持上锁、TOKEN_HANDOFF 交接；临界区超过 1 ms 时一定走公平解锁。
• 实测（2 线程、持锁后立刻重新加锁）：0.12.5 最长连续独占约 1 ms（10 µs 临界区 95 次），持锁 1 ms 时严格交替；0.13.0 一个线程可以连续拿 0.2–0.3 秒。
• 0.13 去掉了这个机制。