更新题目 Fire Event：多线程回调
题目 everpure-fire-event · 修改（rev 32） · · 2026-10-25 19:43
body
@@ -18,5 +18,5 @@ - 可重置用一个 fire 次数计数器（generation），等的是开始等之后的第一次 fire。 - 无锁用 CAS，把标志和链表合成一个原子的头指针。 - - 可选知识：C++ 里锁外读写的标志要 `std::atomic`，`volatile` 不够。 + - 可选知识：C++ 里锁外读写的标志要 `std::atomic`，`volatile` 不够（Follow-up 第七条有名词解释）。 - 推断的追问（取消登记、fire 传数据、wait 超时、回调里再调 register 或 fire、asyncio）见 Follow-up 第八条。 @@ -107,9 +107,21 @@ 先说几个后面要反复用到的概念。Python 里这些东西怎么写、拿不到会怎样，[[p:me/python-concurrency]] 有完整说明，这里只讲这道题用到的部分。 -- **共享状态**：`_fired` 标志和 `_queue` 队列，`register` 和 `fire` 都会读写它们。 -- **竞态条件（race condition）**：两个线程同时读写同一份数据，而且至少有一个在写，最后的结果取决于两个线程的执行顺序恰好怎么交错。代码在你机器上跑一万次都对，也可能有竞态，只是坏的那种交错比较少见。 -- **锁（lock，也叫 mutex，互斥锁）**：一个对象，只有两个操作。acquire（Java 里叫 `lock()`）是「拿锁」：这时没人拿着，调用者就立刻拿到、继续往下跑。别的线程正拿着，调用者就停在这一行等，直到那个线程放锁。release（`unlock()`）是「放锁」：放掉以后，正在等的线程里有一个会拿到并继续。所以同一时刻最多一个线程处在「拿着锁」的状态。从拿到放之间执行的那段代码叫临界区（critical section），两个线程的临界区不会同时跑。Python 里 `with self._lock:` 就是进块时 acquire、出块时 release。**锁只能约束「同样去拿这把锁」的线程**：一个线程不拿锁就直接读写变量，锁拦不住它，它那几行可以和别人的临界区同时跑。2017 年原帖发帖人说自己当场就卡在这里，以为锁会锁住整个对象，其实不会。 - -这道题里所有的 bug 都是同一个形状。`register` 要先「检查 `_fired`」，再根据结果决定「入队」还是「当场执行」，这是两步。如果 `fire()` 恰好在这两步之间把标志改成了 True、并且把队列清完了，`register` 接下来还是会把回调放进队列，而这个队列再也没有人来清。结果就是**回调丢失**：它永远不会被执行，程序也不会报错。这种「先检查、再根据检查结果行动」的竞态，英文叫 check-then-act。 +这道题的共享状态（shared state）是 `_fired` 标志和 `_queue` 队列：`register` 和 `fire` 都会读写它们。 + +> [!term] 竞态条件（race condition） +> 两个线程同时读写同一份数据，而且至少有一个在写，最后的结果取决于两个线程的执行顺序恰好怎么交错。代码在你机器上跑一万次都对，也可能有竞态，只是坏的那种交错比较少见。 + +> [!term] 锁（lock，也叫互斥锁 mutex） +> 一个对象，只有两个操作。`acquire()` 是「拿锁」：这时没人拿着，调用者就立刻拿到、继续往下跑。别的线程正拿着，调用者就停在这一行等，直到那个线程放锁。`release()` 是「放锁」：放掉以后，正在等的线程里有一个会拿到并继续。所以同一时刻最多一个线程拿着锁。Python 里 `with self._lock:` 就是进块时 `acquire()`、出块时 `release()`。 + +> [!term] 临界区（critical section） +> 从拿到锁到放锁之间执行的那段代码。两个线程拿的如果是同一把锁，它们的临界区不会同时跑。 + +要特别注意，锁只能约束「同样去拿这把锁」的线程：一个线程不拿锁就直接读写变量，锁拦不住它，它那几行可以和别人的临界区同时跑。2017 年原帖发帖人说自己当场就卡在这里，以为锁会锁住整个对象，其实不会。 + +这道题里所有的 bug 都是同一个形状。`register` 要先「检查 `_fired`」，再根据结果决定「入队」还是「当场执行」，这是两步。如果 `fire()` 恰好在这两步之间把标志改成了 True、并且把队列清完了，`register` 接下来还是会把回调放进队列，而这个队列再也没有人来清。结果就是**回调丢失**：它永远不会被执行，程序也不会报错。这种竞态有一个专门的名字： + +> [!term] 先检查后执行（check-then-act） +> 一种竞态：先读一个状态（检查），再根据读到的结果做事（执行），而这两步没有在同一次持锁里完成。别的线程可以插在两步之间把状态改掉，于是执行时依据的是一个已经过期的检查结果。修法是让检查和执行在同一次持锁里完成。 举一个具体的例子。把第 1 节的单线程版本原样拿到两个线程里用，不加任何锁。下面把调 `register(cb)` 的线程叫作线程 R，调 `fire()` 的线程叫作线程 F。假设队列一开始是空的，两个线程的执行顺序恰好是这样： @@ -207,6 +219,9 @@ 1. **回调可能很慢**。如果拿着锁执行一个要跑一秒的回调，这一秒里所有想 `register` 的线程都得排队干等。 -2. **回调里可能又调 `register`**。这时同一个线程会再去拿它自己已经拿着的锁。Python 的 `threading.Lock` 是不可重入的（non-reentrant），同一个线程第二次拿会永远等下去，也就是死锁（deadlock）。换成可重入锁（reentrant lock，Python 的 `threading.RLock`、Java 的 `ReentrantLock`）能避开死锁，但理由 1 和理由 3 还在。 +2. **回调里可能又调 `register`**。这时同一个线程会再去拿它自己已经拿着的锁。Python 的 `threading.Lock` 是不可重入的（non-reentrant），同一个线程第二次拿会永远等下去，也就是死锁（deadlock）。换成可重入锁（reentrant lock，Python 的 `threading.RLock`）能避开死锁，但理由 1 和理由 3 还在。 3. **回调可能抛异常**。如果在锁里抛出，又没有用 `finally` 放锁，这把锁就永远不会被释放，之后所有线程都卡死。 + +> [!term] 死锁（deadlock） +> 几个线程互相等对方手里的东西，谁都等不到，全部永远停住。最简单的一种就是理由 2 说的：一个线程拿着一把不可重入的锁，又去拿同一把锁，等的是它自己。另一种常见的是线程 A 拿着锁 1 等锁 2，线程 B 拿着锁 2 等锁 1。 背后的通用原则是：**拿着锁的时候，不要去调用你控制不了的外部代码**。 @@ -228,4 +243,7 @@ 在 `fire()` 只调一次的前提下，这个版本是对的，原帖发帖人也是这么答的（题目一节的表里，「`fire()` 会被调用几次」通常的答案就是一次）。乍一看「不拿锁就读写共享队列」很危险，但这时队列其实已经不是共享的了。标志在锁里改成 True 以后，再来的 `register` 都会看到 True，不会再碰队列。而在那之前看到 False 的 `register`，都已经在 `fire` 拿锁之前完成了入队。所以 `fire` 放锁以后，只剩 `fire` 线程自己会访问这个队列，自然不用加锁。在 Python 里，`fire` 不拿锁读队列，也一定能读到别的线程之前放进去的完整内容，因为 GIL 保证一个线程写完，别的线程马上就能看到（见 [[p:me/python-concurrency]] 的 GIL 一节）。 + +> [!term] 全局解释器锁（GIL，global interpreter lock） +> 标准的 Python 解释器 CPython 里的一把锁：同一时刻只有一个线程能执行 Python 字节码。所以一条赋值不会写到一半被别的线程打断，写完别的线程马上就能看到。它管不了两条语句之间的交错，多线程代码照样要自己加锁。它也让纯 Python 计算没法靠多线程同时用上多个 CPU 核。 > [!optional] Java 和 C++ 里，`fire` 不拿锁读队列也能读到完整的内容，靠的是它之前拿过一次锁。下面线程 R 调 `register(cb)`，线程 F 调版本三的 `fire()`： @@ -293,5 +311,5 @@ > [!say] Swapping the two lines fixes it. Once the flag is set, acquiring the lock acts as a barrier: it waits for any register that already saw false to finish appending, and every later register will see true. -> [!optional] 在 Java 和 C++ 里，版本五还有一个前提：`_fired` 是在锁外写的，而 `register` 在锁里读它，这在 C++ 里是数据竞争（data race），按标准是未定义行为，所以 `_fired` 必须声明成 `std::atomic<bool>`。Java 里普通的 `boolean` 也能工作，因为 `fire` 的放锁和后来 `register` 的拿锁之间建立了先后关系，但面试里说「声明成 `volatile` 或 `AtomicBoolean` 更稳妥」更好。这部分原理见 Follow-up 第七条。 +> [!optional] 在 Java 和 C++ 里，版本五还有一个前提：`_fired` 是在锁外写的，而 `register` 在锁里读它，这在 C++ 里是数据竞争（data race），按标准是未定义行为，所以 `_fired` 必须声明成 `std::atomic<bool>`。Java 里普通的 `boolean` 也能工作，因为 `fire` 的放锁和后来 `register` 的拿锁之间建立了先后关系，但面试里说「声明成 `volatile` 或 `AtomicBoolean` 更稳妥」更好。`volatile` 是什么、这部分原理，见 Follow-up 第七条。 ### 7. 版本六：一直拿着锁清队列，最后才改标志 @@ -334,10 +352,16 @@ 所以两个变体的差别在考点：回调版考锁和 check-then-act，Trigger 版考条件变量，也就是下面讲的丢失唤醒、`while` 包住 `wait()`、先改条件再通知。 -Trigger 要求 `wait()` 阻塞到 fire 为止。要「停下来等一个条件成立」，最笨的办法是忙等（busy wait），也就是写一个 `while not flag: pass` 一直空转查标志，白白占满一个 CPU 核。正确的工具是条件变量（condition variable）。 - -条件变量总是和一把锁绑在一起用，提供两个操作： - -- `wait()`：必须在已经拿着锁的时候调用。它会**在一步之内**放锁并让线程睡下。被叫醒以后，要重新拿到锁才返回。「放锁」和「睡下」必须是一步，否则会出现：线程刚放锁、还没睡着，别人就把条件改了并发了通知，这个通知没人收到，线程随后睡下去就再也醒不过来。这种 bug 叫丢失唤醒（lost wakeup）。 -- `notify_all()`：叫醒所有在这个条件变量上等的线程。Python 要求调用时拿着锁，不拿会直接报错。C++ 允许不拿锁调用。 +Trigger 要求 `wait()` 阻塞到 fire 为止。要「停下来等一个条件成立」，最笨的办法是忙等（busy wait），也就是写一个 `while not flag: pass` 一直空转查标志，白白占满一个 CPU 核。正确的工具是条件变量。 + +> [!term] 条件变量（condition variable） +> 一个和锁绑在一起用的等待工具。线程在它上面 `wait()`，放锁并睡下。别的线程改完条件以后 `notify_all()`，把等着的线程叫醒。它只负责「睡」和「叫醒」，条件成没成立要另用一个变量记下来，比如这里的 `_fired`。 + +它提供两个操作： + +- `wait()`：必须在已经拿着锁的时候调用。它会**在一步之内**放锁并让线程睡下。被叫醒以后，要重新拿到锁才返回。「放锁」和「睡下」必须是一步，否则会出现：线程刚放锁、还没睡着，别人就把条件改了并发了通知，这个通知没人收到，线程随后睡下去就再也醒不过来。这种 bug 叫丢失唤醒，见下面的名词解释。 +- `notify_all()`：叫醒所有在这个条件变量上等的线程。Python 要求调用时拿着锁，不拿会直接报错。 + +> [!term] 丢失唤醒（lost wakeup） +> 通知发出的时候，要等的线程还没开始等，这次通知就落空了。那个线程随后开始等，可再也没有人通知它，于是永远睡下去。条件变量本身不记得通知过，所以等的一方必须先在锁里查条件，条件不成立才睡。 ```python @@ -358,5 +382,8 @@ ``` -`wait()` 外面要用 `while` 而不是 `if`，有两个原因。第一，虚假唤醒（spurious wakeup）：POSIX、Java、C++ 的规范都明确允许 `wait()` 在没人通知的情况下返回，所以醒来不代表条件成立。第二，从被叫醒到重新拿到锁之间有一段空档，别的线程可能在这段时间里又把条件改回去了（在可以重置的版本里就会发生，见 Follow-up 第五条）。所以醒来后一律重新检查。 +> [!term] 虚假唤醒（spurious wakeup） +> 等待的线程在没有任何人通知的情况下，从 `wait()` 里返回了。POSIX 线程库和 C++ 标准都明确允许这种情况，所以从 `wait()` 返回只说明「该醒来再看一眼了」，不说明条件已经成立。 + +`wait()` 外面要用 `while` 而不是 `if`，有两个原因。第一，可能是虚假唤醒，醒来不代表条件成立。第二，从被叫醒到重新拿到锁之间有一段空档，别的线程可能在这段时间里又把条件改回去了（在可以重置的版本里就会发生，见 Follow-up 第五条）。所以醒来后一律重新检查。 #### Trigger 的错误写法：先通知、后改标志 @@ -670,5 +697,8 @@ #### 做法二：所有回调交给同一个工作线程 -线程池（thread pool）是一组事先建好的工作线程（worker thread）：你把任务提交给它，它从内部的队列里按提交顺序取出任务来执行。Python 标准库里的线程池是 `concurrent.futures.ThreadPoolExecutor`，语法见 [[p:me/python-concurrency]]。`max_workers=1` 的线程池只有一个工作线程，提交上去的任务一个执行完才轮到下一个，执行顺序就是提交顺序。 +> [!term] 线程池（thread pool） +> 一组事先建好、反复使用的工作线程（worker thread）。你把任务提交给它，它从内部的队列里按提交顺序取出任务，交给空闲的工作线程执行。Python 标准库里是 `concurrent.futures.ThreadPoolExecutor`，语法见 [[p:me/python-concurrency]]。 + +`max_workers=1` 的线程池只有一个工作线程，提交上去的任务一个执行完才轮到下一个，执行顺序就是提交顺序。 ```python @@ -880,5 +910,10 @@ 「不用锁」的意思是 `register` 和 `fire` 都不拿任何锁，没有线程会因为等锁而停下来。难点在于，前面所有正确的版本都靠锁把「检查标志」和「入队」绑成一步。不拿锁，就得换一个能把「检查」和「修改」一步做完的工具。 -这个工具是比较并交换（compare-and-swap，简称 CAS），一条 CPU 原子指令。它做的事是：这个变量如果还等于我预期的旧值，就改成新值，返回成功，否则什么都不改，返回失败。「原子」指检查和修改一步做完，中间不会被别的线程插进来。和它配套的还有原子交换（exchange）：把变量改成新值，同时拿回旧值，也是一步做完。 +这个工具叫 CAS。 + +> [!term] 比较并交换（compare-and-swap，CAS） +> 一条 CPU 原子指令：一个变量如果还等于我预期的旧值，就把它改成新值，返回成功，否则什么都不改，返回失败。「原子」指检查和修改一步做完，中间不会被别的线程插进来。 + +和它配套的还有原子交换（exchange）：把变量改成新值，同时拿回旧值，也是一步做完。 CAS 一次只能管一个变量，这道题却有两份共享数据：标志和队列。所以第一步是把它们合成一个变量 `head`，它有三种取值： @@ -1039,9 +1074,11 @@ 这一条同样是 C/C++ 和 Java 里才有的问题，用 Python 写时基本碰不到（下一段讲为什么）。放在这里，是因为面试官如果按 C++ 的习惯问「这个标志要不要声明成 `volatile`」，你要答得上来。Glassdoor 2025-12 一篇资深岗面经的总监轮就问过 C++ 多线程概念。 -先说 Python。标准解释器 CPython 有一把全局解释器锁（GIL），同一时刻只有一个线程在执行 Python 字节码，所以一条赋值不会只写一半，写完别的线程马上就能看到，Python 版本用普通的 `bool` 没有可见性问题。但 GIL 只保证单条操作不被打断，管不了两条语句之间的交错，所以版本四在 Python 里照样丢回调。另外这只是 CPython 实现的性质，Python 语言规范里没有这条保证。 +先说 Python。有 GIL（第 4 节的名词解释），同一时刻只有一个线程在执行 Python 字节码，所以一条赋值不会只写一半，写完别的线程马上就能看到，Python 版本用普通的 `bool` 没有可见性问题。但 GIL 只保证单条操作不被打断，管不了两条语句之间的交错，所以版本四在 Python 里照样丢回调。另外这只是 CPython 实现的性质，Python 语言规范里没有这条保证。 > [!optional] 前面一直默认「一个线程写了变量，另一个线程马上就能看到」，在 C++ 和 Java 里这并不成立。编译器为了优化，可能把变量缓存在寄存器里，或者调换前后两条读写的顺序。CPU 也会乱序执行，而且每个核有自己的缓存。所以一个线程写了 `fired = true`，另一个线程可能过一阵才看到，甚至先看到后面的写、再看到前面的写。 > -> C++ 标准规定：两个线程同时访问同一个普通变量、至少一个在写、又没有任何同步，这叫数据竞争（data race），整个程序的行为是未定义的（undefined behavior），编译器怎么优化都不算错。 +> > [!term] 数据竞争（data race） +> > +> > 两个线程同时访问同一个普通变量，至少一个在写，中间又没有任何同步。C++ 标准规定，出现数据竞争的程序行为是未定义的（undefined behavior），编译器怎么优化都不算错。 > > 解决办法是让两个线程之间建立「先行发生」关系（happens-before）。最常用的两种： @@ -1050,5 +1087,9 @@ > - **原子变量**（`std::atomic`）：对它的读写本身不会被撕裂，而且按指定的内存顺序（memory order）建立可见性。比如 release 写配 acquire 读：读到这个值的线程，一定也能看到写入者在写它之前做的其他写。 > -> `volatile` 在 C/C++ 里只做一件事：告诉编译器每次都真的去内存里读写这个变量，不要优化掉。它本来是为内存映射的硬件寄存器设计的。它**不保证原子性**（比如 `x++` 仍然是读、加、写三步，会被打断），**也不保证和其他变量之间的顺序**（编译器和 CPU 仍然可以把别的读写挪到它前后）。所以用 `volatile` 做线程间的标志是错的，应该用 `std::atomic<bool>`。 +> > [!term] volatile 关键字 +> > +> > C、C++ 和 Java 里都有的一个变量修饰词，写在变量声明前面，比如 `volatile bool fired;`。在 C/C++ 里，它告诉编译器：这个变量的每一次读写都必须真的去内存里做，不能缓存在寄存器里，也不能被优化掉。它本来是为硬件寄存器设计的：那种变量的值会被硬件改掉，编译器看不出来。Java 里同名的关键字含义更强，见下面最后一段。 +> +> `volatile` 只管「每次都真的读写内存」，别的都不管。它**不保证原子性**（比如 `x++` 仍然是读、加、写三步，会被打断），**也不保证和其他变量之间的顺序**（编译器和 CPU 仍然可以把别的读写挪到它前后）。所以用 `volatile` 做线程间的标志是错的，应该用 `std::atomic<bool>`。 > > 注意 Java 的 `volatile` 不一样：Java 的 `volatile` 变量读写自带可见性和顺序保证，相当于 C++ 里顺序一致的原子变量（但 `volatile int` 的 `x++` 同样不是原子的）。面试时说清楚是哪个语言的 `volatile`。