最小停车场与 1 字节 mutex

主线位置：主线 1「一次有竞争的 lock / unlock」与横线「桶锁里能做什么」的缩小版。真实实现见 park 与四种 unpark 和 RawMutex 的一字节状态机。代码在 exp-parking_lot/hands-on/src/lot.rs、src/mini_mutex.rs。

sequenceDiagram
  participant B as 加锁方 B
  participant K as 桶（std Mutex + FIFO）
  participant A as 解锁方 A
  B->>B: 状态置 PARKED（11）
  B->>K: 锁桶
  B->>B: validate：状态仍是 11？
  B->>K: 入队，放桶锁，睡在自己的 parker 上
  A->>A: unlock 快路径 CAS 失败（有 PARKED）
  A->>K: 锁桶，摘下 B，看还有没有同 key 的
  A->>A: 回调（仍在桶锁里）：写 10 或 00
  A->>K: 放桶锁
  A->>B: 叫醒 B，B 回去重抢

停车场：一张固定的表

struct Waiter {
  key: usize,
  parker: Arc<Parker>, // Mutex<bool> + Condvar，每线程一个，放在 thread_local
}

type Bucket = Mutex<VecDeque<Waiter>>;

const BUCKET_BITS: u32 = 6;
static TABLE: [Bucket; 1 << BUCKET_BITS] = [const { Mutex::new(VecDeque::new()) }; 1 << BUCKET_BITS];

fn bucket(key: usize) -> &'static Bucket {
  // Fibonacci hashing, same constant as parking_lot_core.
  let h = (key as u64).wrapping_mul(0x9E37_79B9_7F4A_7C15) >> (64 - BUCKET_BITS);
  &TABLE[h as usize]
}

和 parking_lot_core 比省掉了三样（停车场哈希表）：表不扩容（64 个桶写死）、桶锁直接用 std Mutex 而不是自己管队列的 WordLock（WordLock）、parker 用 std 的 Mutex<bool> + Condvar。哈希函数照抄：乘斐波那契常数取高 6 位。

park：在桶锁里验证

pub fn park(key: usize, validate: impl FnOnce() -> bool) -> bool {
  let parker = PARKER.with(Arc::clone);
  *parker.woken.lock().unwrap() = false;
  {
    let mut q = bucket(key).lock().unwrap();
    if !validate() {
      return false;
    }
    q.push_back(Waiter { key, parker: parker.clone() });
  }
  let mut woken = parker.woken.lock().unwrap();
  while !*woken {
    woken = parker.cv.wait(woken).unwrap();
  }
  true
}

validate 和「入队」在同一段桶锁里。解锁方要改状态、找人，也必须拿同一把桶锁。于是「检查条件」和「登记自己」对解锁方来说是一个不可分的动作：解锁方要么在 B 验证之前改完状态（B 的验证失败，不睡），要么在 B 入队之后才来（找得到 B）。这就是 parking_lot_core 整个协议的核心，rayon 的 sleep 模块用「先拿 is_blocked 锁再登记」做的是同一件事（rayon 卷：睡眠与唤醒的握手）。

unpark_one：回调在桶锁里

pub fn unpark_one(key: usize, callback: impl FnOnce(bool, bool)) -> bool {
  let waiter = {
    let mut q = bucket(key).lock().unwrap();
    let w = q.iter().position(|w| w.key == key).and_then(|i| q.remove(i));
    let have_more = q.iter().any(|w| w.key == key);
    callback(w.is_some(), have_more);
    w
  };
  match waiter {
    Some(w) => {
      *w.parker.woken.lock().unwrap() = true;
      w.parker.cv.notify_one();
      true
    }
    None => false,
  }
}

同一个桶里混着不同 key 的线程，按 key 线性查找（真实实现也是如此，桶多所以链短）。真正叫醒放在桶锁外，减少桶锁的持有时间。parking_lot_core 在桶锁里还要先 unpark_lock，因为它的 ThreadData 在对方线程的 TLS 里，对方一旦醒来退出就没了（ThreadParker）；这里 parker 是 Arc，Waiter 里持有一份引用，对方退出也不会释放，所以省掉了这一步。

1 字节 mutex

状态和 parking_lot 一样两位，LOCKED = 0b01、PARKED = 0b10。快路径各一次 CAS，慢路径照抄 lock_slow 的四段（抢、没人排队才转、置 PARKED、停车），自旋直接借用 parking_lot_core 公开的 SpinWait：

// 4. sleep only if the state is still exactly LOCKED|PARKED
let addr = self as *const _ as usize;
lot::park(addr, || self.state.load(Ordering::Relaxed) == LOCKED | PARKED);

#[cold]
fn unlock_slow(&self) {
  let addr = self as *const _ as usize;
  lot::unpark_one(addr, |_unparked, have_more| {
    let next = if have_more { PARKED } else { 0 };
    self.state.store(next, Ordering::Release);
  });
}

不变量也照抄：锁被持有时，PARKED 只在桶锁里清。回调在桶锁里，所以「清 PARKED」和「有人正在验证、准备入队」不会交错。没有公平交接（总是写 10 / 00 让被叫醒者重抢），没有超时。外壳直接用 lock_api：pub type MiniMutex<T> = lock_api::Mutex<RawMiniMutex, T>;，GuardMarker = GuardSend（解锁只是原子操作，哪个线程做都一样）。

测试与计时

tests/hands_on.rs 里两项（各在看门狗下，连续跑 3 遍都通过）：

• mini_mutex_counts_exactly：2、8、32 个线程各加锁加一 10 万次，计数精确，临界区重叠计数（进门 fetch_add、返回值不为 0 记一次）为 0。
• mini_mutex_parks_and_wakes：主线程持锁 50 ms，8 个线程在这段时间里转完 SpinWait 后停车；放锁后全部被逐个叫醒，计数为 8。

和 parking_lot 0.12.5、std 并排计时（src/bin/bench.rs，E2 的形状：T 个线程共享一把 Mutex<u64>，加锁、加一、解锁，锁外可选忙等；不做延迟采样；ns/op = 墙钟 / 总次数）。23:07 开始时 1 / 5 分钟负载 2.08 / 2.98，结束时 3.91 / 3.35；每格 3 轮中位数，括号是范围：

一百来行的版本和 parking_lot 在每一行都是同一个量级，相对 std 的胜负形状也一样（锁外不做事时 std 快，锁外有工作时 parking_lot 一族快约 1.8 倍）。这说明在这类负载下，parking_lot 的速度主要来自「快路径一次 CAS + 插队 + 有人排队就不转」这套状态机，而不是 WordLock、扩容哈希表这些细节；后者解决的是线程很多、锁很多时的可扩展性和内存占用，这组实验没有测到。parking_lot 一列与 和 std Mutex 比 的 E2 数字略有出入（那边带延迟采样、是另一个程序），以那一页为准。

反向验证：把 validate 移到桶锁外

feature validate_outside 只改 park 里的顺序：先 validate()，通过后再锁桶、入队。widen 在两步之间再加一次 yield_now()。lost_wakeup 程序：4 个线程各加锁加一 20 万次，跑 10 轮，每轮 5 秒看门狗：

不需要加宽窗口就 10/10 卡死。丢唤醒的交错：

sequenceDiagram
  participant B as 加锁方 B
  participant A as 解锁方 A
  participant K as 桶
  B->>B: 状态 11，validate 通过（没拿桶锁）
  A->>K: unlock_slow：锁桶，队列里没有 B
  A->>A: 回调：没人等，写 00
  B->>K: 锁桶，入队，睡
  Note over B: 状态是 00 或 01，没有 PARKED：以后的解锁都走快路径，没人会来叫 B

之后别的线程如果又置 PARKED 并停车，下一次慢路径解锁会按 FIFO 先叫醒 B，B 偶尔能被「顺带救活」；但到了最后几个线程，没人再停车，B 就永远睡下去。所以压测里看到的是「跑完一部分线程后卡住」。

省掉了什么

小结

• 停车场的核心只有一句：validate 和入队在同一段桶锁里，解锁方的回调也在这把锁里。
• 一百来行的 mini 版（固定 64 桶、std Mutex 作桶锁、Arc parker）加一个两位状态的 mutex，32 线程计数精确，吞吐与 parking_lot 同量级。
• 把 validate 挪到桶锁外，10 轮压测 10 轮卡死；交错是「验证通过 → 解锁方清掉 PARKED → 入队睡下」。
• parking_lot 的速度主要来自状态机本身；表扩容、WordLock 解决的是规模问题。