更新题目 getID：批量取号
题目 everpure-get-id · 修改（rev 10） · · 2026-10-26 00:29
body
@@ -57,5 +57,5 @@ | `get_block_id` 会失败吗？会少给吗？ | 先当作不会，写完再作为 follow-up 处理 | 失败要退避重试，而且不能让生产者线程死掉（Follow-up 第 1 条）。少给就按实际返回的长度算，代码不用改 | | 没发出去的 id 浪费了要不要紧？ | 【推断】要紧：进程退出时缓存里的 id 就作废了，分配器那边留下一段空洞。id 是有限资源（比如 32 位）或者要求连续时代价更大 | 完全不要紧的话，批量可以开得很大，只剩内存一个顾虑 | -| 用什么语言？ | 帖子都没说（2017 年的发帖人主用 Java，变体 C 是 C 签名）。本页用 Python：`get_block_id(count) -> list[int]`、`get_one_id() -> int`，语法见 [[p:me/python-concurrency]] | C/C++ 把锁和条件变量换成 `std::mutex`、`std::condition_variable`，结构一样 | +| 用什么语言？ | 帖子都没说（2017 年的发帖人主用 Java，变体 C 是 C 签名）。本页用 Python：`get_block_id(count) -> list[int]`、`get_one_id() -> int`，语法见 [[p:kb/python-concurrency]] | C/C++ 把锁和条件变量换成 `std::mutex`、`std::condition_variable`，结构一样 | ## 面经里怎么考的 @@ -114,5 +114,5 @@ ### 3. 多线程：不加锁会发重复的 id，加锁之后补货让所有人等 -第三版默认有多个线程同时调 `get_one_id`，所以先看第二版放进多线程会怎样。锁（lock）同一时刻最多一个线程拿着，从拿到到放开之间的代码叫临界区（critical section），两个线程的临界区不会同时跑（详见 [[p:me/python-concurrency]]）。 +第三版默认有多个线程同时调 `get_one_id`，所以先看第二版放进多线程会怎样。锁（lock）同一时刻最多一个线程拿着，从拿到到放开之间的代码叫临界区（critical section），两个线程的临界区不会同时跑（详见 [[p:kb/python-concurrency]]）。 `V2Single` 的共享状态是 `_cache` 和 `_pos`。`get_one_id` 分了几步：检查 `_pos` 有没有追上长度、读 `_cache[_pos]`、把 `_pos` 加一。两个线程的这几步可以交错。设线程 X 和线程 Y 同时调用，`_pos` 是 5，缓存里是 1000 到 1099： @@ -171,5 +171,5 @@ - **有界缓冲区（bounded buffer）**：容器有上限，生产者不能无休止地往里放。没有上限的话，需求低的时候生产者会一直取、缓冲区无限长，囤的 id 全是浪费。 - **低水位（low-water mark）**：一个阈值 L。缓冲区里剩的 id 数降到 L 或更少，就该去取下一批了。L = 0 就是「空了才取」。L 越大，取得越提前。它同时也定了缓冲区的上限：去取下一批的时候最多剩 L 个，所以到货后最多 L + B 个。 -- **条件变量（condition variable）**：让线程「睡下去等某个条件成立」的工具，和一把锁绑在一起用。`wait()` 在一步之内放锁并睡下，被叫醒后重新拿到锁才返回。`notify()` 叫醒一个等的线程，`notify_all()` 叫醒全部。等待为什么写 `while` 不写 `if`、为什么先改条件再通知，见 [[p:me/python-concurrency]]。 +- **条件变量（condition variable）**：让线程「睡下去等某个条件成立」的工具，和一把锁绑在一起用。`wait()` 在一步之内放锁并睡下，被叫醒后重新拿到锁才返回。`notify()` 叫醒一个等的线程，`notify_all()` 叫醒全部。等待为什么写 `while` 不写 `if`、为什么先改条件再通知，见 [[p:kb/python-concurrency]]。 设计是这样的。缓冲区 `_ids` 是一个双端队列。生产者线程循环做一件事：剩的 id 数大于 L 就睡，不大于 L 就在锁外调 `get_block_id` 取一批，回来后放进缓冲区、叫醒等着的调用者。`get_one_id` 拿锁，缓冲区空就等「缓冲区非空」，然后取一个，取完如果剩的不多于 L，就叫醒生产者。 @@ -312,5 +312,5 @@ - **生产者不睡**（第 4 节）：没有「缓冲区够就睡」这一条，需求低时缓冲区无限长。 - **一个条件变量、两边都用 `notify()`**（第 4 节的五步表）：调用者发的通知叫醒了另一个调用者，没叫醒生产者，最后所有人都睡着。 -- **条件变量先通知再改条件、或者 `wait()` 外面用 `if`**（[[p:me/python-concurrency]]）：被叫醒的线程看到旧条件又睡回去，没人再叫它。 +- **条件变量先通知再改条件、或者 `wait()` 外面用 `if`**（[[p:kb/python-concurrency]]）：被叫醒的线程看到旧条件又睡回去，没人再叫它。 - **生产者线程里的异常**（Follow-up 第 1 条）：`get_block_id` 抛一次异常线程就死了，之后所有调用者永远等。重试时不看关闭标志，分配器一直不可用时 `close()` 等不到生产者退出。 - **忘了预热**（第 4 节、第 5 节）：第一次调用等满 T，变体 B 里刚好压线。