编程问题智能生成器

问题标题

并发读写锁管理器：支持升级、死锁检测、超时与公平策略

问题描述

实现一个多资源的并发读写锁管理器（Lock Manager），支持以下能力：

• 基本读写锁（S 共享、X 独占）与同一资源上的 S→X 升级、X→S 降级（本题只要求升级）。
• 公平策略：写者优先（当等待队列中存在写者或升级请求在队首时，后续到达的读者不再被立即授予）。
• 死锁检测：基于等待图（Wait-For Graph）周期检测，发现后按策略选择牺牲者并中止其事务。
• 超时：等待超过指定超时的锁请求导致事务整体回滚（释放已持有的全部锁）。
• 多资源：事务可对多个资源加锁；需正确处理跨资源的等待与死锁。

你需要编写一个程序，按输入脚本驱动该锁管理器的行为，输出每一步的可观测事件（如授予、排队、阻塞、超时、死锁与中止等）。该题旨在考察并发控制的高级概念与工程实现，包括数据结构设计、调度公平性、升级语义、死锁检测与恢复策略。

注：为便于判题与复现，本题使用“事件驱动 + 逻辑时钟”的模拟方式；你可以用多线程/协程实现内部并发控制，也可以用单线程事件驱动模拟，但必须满足技术要求的语义与输出。

技术要求

• 锁模型与兼容性
  • 模式：S（共享）、X（独占）。兼容性：S 与 S 兼容；X 与任意不兼容。
  • 升级：若事务 T 已持有资源 R 的 S，T 可发起对 R 的 X 的升级请求。升级请求被视为写者请求，插入队列头（高优先级），但需等待其他持有者释放。
  • 重入：禁止同一事务对同一资源重复获取相同模式（再次请求视作无效，应报错或忽略；推荐忽略并不输出事件）。
• 公平性
  • 写者优先：当某资源的等待队列队首为写者或升级请求时，后续到达的读者请求一律进入队列等待（不即时授予）。
  • 授予策略：在释放或中止后，按队列顺序尝试授予；若队首为写者/升级且可授予则授予；若队首为读者，则可批量授予一段连续的读者请求，直到队列遇到写者/升级为止。
• 死锁检测
  • 等待图构建：对每个因冲突而阻塞的请求 A→B 建边（A 等待持有冲突锁的事务 B）；升级请求对“其他持有该资源 S 的事务”建边。
  • 检测时机：在每次状态变化（LOCK/UNLOCK/TICK/ABORT/COMMIT）后进行；一旦发现环路，立刻选择牺牲者并中止（释放其所有锁，清除其队列项），然后继续尝试授予。
  • 牺牲者选择：优先级低者优先被中止；若优先级相同，锁持有数多者先中止；如仍相同，事务 ID 字典序更大者中止。
• 超时
  • 请求可指定超时时间（毫秒）。若从进入阻塞状态起等待时间超过超时，直接中止整个事务（释放其全部锁）。无限超时可用 TIMEOUT INF 表示或省略 TIMEOUT。
• 事务语义
  • BEGIN/COMMIT/ABORT：BEGIN 创建事务（可指定优先级，默认 0）；COMMIT 释放其全部锁并结束；ABORT 可由客户端发起，或由死锁/超时触发。
• 时间推进
  • 通过 TICK ms 推进逻辑时钟，驱动超时判断与随后的授予。
• 输出要求
  • 输出必须严格按照“输入事件发生后导致的可观测状态变化”的顺序打印，详见“输入输出示例”。
• 复杂度建议
  • 资源表与事务表：哈希表 O(1) 期望时间访问。
  • 每资源等待队列：双端队列。
  • 死锁检测：对当前等待图做一次 DFS/Tarjan/Kahn，O(V+E)，在规模上限内可接受。
• 可用语言
  • Python、Java、Go、Rust、C++ 等。并发实现可用线程/协程/异步事件均可，但行为需与规范一致。

输入输出示例

输入格式（逐行命令）：

• BEGIN [PRIORITY

  ]

• LOCK [TIMEOUT |TIMEOUT INF] [UPGRADE]
• UNLOCK
• COMMIT
• ABORT
• TICK
• END

输出事件（逐行）：

• GRANTED
• QUEUED [UPGRADE] // 因公平策略进入队列但非直接冲突
• BLOCKED BY <tx1,tx2,...> // 直接冲突的阻塞者，按事务 ID 升序
• RELEASED
• TIMEOUT
• DEADLOCK --...- CHOOSE
• ABORT REASON <DEADLOCK|TIMEOUT|CLIENT>
• COMMIT
• TICK // 打印推进后的当前时间

说明：

• 对同一命令，先输出本命令直接产生的事件（如 GRANTED/QUEUED/BLOCKED），再在需要时进行死锁检测与后续事件（DEADLOCK/ABORT/GRANTED...）。
• TICK 后需输出当前逻辑时间（累计）。

示例（简要）： 输入 BEGIN T1 LOCK T1 A S BEGIN T2 LOCK T2 A S BEGIN T3 LOCK T3 A X BEGIN T4 LOCK T4 A S UNLOCK T1 A UNLOCK T2 A TICK 0 UNLOCK T3 A TICK 0 END

输出 GRANTED T1 A S GRANTED T2 A S BLOCKED T3 A X BY T1,T2 QUEUED T4 A S RELEASED T1 A RELEASED T2 A GRANTED T3 A X TICK 0 RELEASED T3 A GRANTED T4 A S TICK 0

测试用例

用例 1：基础共享/独占与写者优先 输入 BEGIN T1 LOCK T1 A S BEGIN T2 LOCK T2 A S BEGIN T3 LOCK T3 A X BEGIN T4 LOCK T4 A S UNLOCK T1 A UNLOCK T2 A TICK 0 UNLOCK T3 A TICK 0 END

期望输出 GRANTED T1 A S GRANTED T2 A S BLOCKED T3 A X BY T1,T2 QUEUED T4 A S RELEASED T1 A RELEASED T2 A GRANTED T3 A X TICK 0 RELEASED T3 A GRANTED T4 A S TICK 0

用例 2：升级导致的死锁 输入 BEGIN T1 LOCK T1 A S BEGIN T2 LOCK T2 A S LOCK T1 A X UPGRADE LOCK T2 A X UPGRADE TICK 0 END

期望输出 GRANTED T1 A S GRANTED T2 A S BLOCKED T1 A X BY T2 BLOCKED T2 A X BY T1 DEADLOCK T1-T2-T1 CHOOSE T2 ABORT T2 REASON DEADLOCK GRANTED T1 A X TICK 0

用例 3：经典 ABBA 死锁 输入 BEGIN T1 BEGIN T2 LOCK T1 A X LOCK T2 B X LOCK T1 B X LOCK T2 A X TICK 0 END

期望输出 GRANTED T1 A X GRANTED T2 B X BLOCKED T1 B X BY T2 BLOCKED T2 A X BY T1 DEADLOCK T1-T2-T1 CHOOSE T2 ABORT T2 REASON DEADLOCK GRANTED T1 B X TICK 0

用例 4：超时回滚 输入 BEGIN T1 LOCK T1 A X BEGIN T2 LOCK T2 A X TIMEOUT 100 TICK 100 END

期望输出 GRANTED T1 A X BLOCKED T2 A X BY T1 TIMEOUT T2 A X ABORT T2 REASON TIMEOUT TICK 100

用例 5：队首写者存在时的新读者排队、公平授予 输入 BEGIN T1 LOCK T1 A S BEGIN T2 LOCK T2 A S BEGIN T3 LOCK T3 A X BEGIN T4 LOCK T4 A S BEGIN T5 LOCK T5 A S UNLOCK T1 A UNLOCK T2 A TICK 0 UNLOCK T3 A TICK 0 END

期望输出 GRANTED T1 A S GRANTED T2 A S BLOCKED T3 A X BY T1,T2 QUEUED T4 A S QUEUED T5 A S RELEASED T1 A RELEASED T2 A GRANTED T3 A X TICK 0 RELEASED T3 A GRANTED T4 A S GRANTED T5 A S TICK 0

边界建议再自测：

• 同一事务对同一资源重复 LOCK S 或 LOCK X（应忽略或报错，不影响状态）。
• 升级请求到达时，资源等待队列已有写者。
• 多个循环同时存在的死锁检测（应一次至少打破一个环，建议循环处理直到无环）。

评分标准

• 正确性（50%）
  • 锁兼容性与授予规则正确（含批量授予读者）。
  • 写者优先策略严格执行。
  • 升级语义与队列位置处理正确。
  • 死锁检测与牺牲者选择符合规范。
  • 超时触发的事务回滚逻辑正确。
• 完整性与鲁棒性（20%)
  • 支持多资源与多事务同时操作。
  • 边界处理（重复请求、无效解锁、已结束事务操作等）健壮。
  • 输出顺序与格式严格符合要求。
• 性能（15%）
  • 数据结构设计合理；在大规模事件下仍可在限定时间内完成（如 10^5 条命令）。
  • 死锁检测开销控制（按需触发或增量维护）。
• 工程实现（10%）
  • 代码结构清晰、模块化（事务表、资源表、等待图等）。
  • 并发安全（若使用多线程）或事件驱动逻辑一致性（若单线程）。
• 额外加分（5%）
  • 支持 X→S 降级命令，或提供可切换的公平策略（严格 FIFO 与写者优先）。

解决思路

• 核心数据结构
  • 事务表 TxTable：记录状态（活跃/中止/提交）、优先级、持有的锁集合、等待中的请求与其开始等待时间。
  • 资源表 ResTable：每个资源维护
    • 当前持有者列表（S 可多，X 最多 1）
    • 等待队列（元素包含：txId、mode、是否升级、入队时间、超时设置）
  • 等待图 WFG：邻接表，边 A→B 表示 A 被 B 阻塞（来自直接冲突或升级等待）。
• 授予与队列规则
  • 尝试授予时：
    • 若队首是写者/升级，且兼容当前持有者则授予；否则停止。
    • 若队首是读者，批量处理连续读者，直到遇到写者/升级或与持有者冲突。
  • 新读者到达时：若等待队列为空且当前持有者无冲突且队首不是写者/升级，则立即授予；否则入队输出 QUEUED。
  • 升级：若已持有 S，生成升级请求，插入队首并标记 UPGRADE；其阻塞集为“除了自己之外的全部当前持有 S 的事务”。
• 死锁检测
  • 在状态变化后重建或增量更新等待图。
  • 运行环检测（DFS/Tarjan/Kahn 任一）。若存在环，依据策略选择牺牲者，输出 DEADLOCK 和 ABORT，释放其全部锁并清理其等待项，然后再次尝试授予。
• 超时处理
  • TICK 推进逻辑时钟；遍历等待请求，若 now - waitStart > timeout，则输出 TIMEOUT 并 ABORT 整个事务；释放后重新尝试授予。
• 事件顺序与输出
  • 每条输入命令处理时：
    1. 执行直接动作并输出（GRANTED/QUEUED/BLOCKED/RELEASED 等）。
    2. 进行死锁检测与可能的中止、授予，依次输出。
    3. 若为 TICK，推进时间并输出 TICK now，再处理可能的超时与后续授予。
• 实现建议
  • 使用哈希表存 Tx 与 Res 的快速定位；等待队列用双端队列。
  • BLOCKED 的阻塞者集合按事务 ID 排序输出，确保确定性。
  • 牺牲者选择严格按优先级→持锁数→事务 ID 字典序进行。
  • 注意升级请求与普通写者的相对优先级（升级在队首）。

该问题覆盖了并发控制核心要点：锁兼容性、队列公平性、升级/降级语义、等待图与死锁检测、超时与恢复策略。实现中可使用多线程或事件驱动，但需保证语义正确与输出可复现。

问题标题

可删除的前缀字典与限量自动补全

问题描述

实现一个支持动态更新的前缀字典，维护一组仅包含小写字母的单词（不含重复）。需要支持三类操作：

• 添加单词
• 删除单词
• 基于给定前缀查询最多 K 个按字典序排列的候选词（自动补全）

查询时，如果以该前缀开头的单词数不足 K 个，则返回能找到的全部；如果一个也没有，输出一个连字符“-”。

本题旨在考察对字符串数据结构（如 Trie/前缀树，或基于有序集合的范围查询）的设计与实现能力，以及在高并发操作下的时间与空间效率权衡。

技术要求

• 输入包含多条指令，需在线处理（每条指令立刻生效）。
• 字典语义为集合：相同单词多次添加等价于一次；删除不存在的单词应安全忽略。
• 词汇仅由小写字母 a-z 构成，长度在 1 到 30 之间。
• 查询返回按字典序升序的至多 K 个候选词，同一行以空格分隔；若无候选则输出“-”。
• 性能目标（建议，不作硬性判定）：
  • ADD/DEL 平均时间 O(L)，L 为单词长度
  • QUERY 平均时间 O(P + R)，P 为前缀长度，R 与输出规模成正比（可视为 K 乘以平均单词长度的常数倍）
• 允许语言：任意主流编程语言（Python/Java/JavaScript/C++/Go 等）。
• 可使用的核心数据结构建议：
  • 首选：Trie（前缀树），孩子指针为固定 26 分支或映射。节点需保存：
    • 子链接
    • 是否为单词结尾
    • 通过该节点的单词计数（用于删除时回收/剪枝）
  • 备选：若语言原生提供有序集合（如 C++ std::set / std::map，Java TreeSet/TreeMap），可用“前缀范围”迭代实现 QUERY（lower_bound(prefix) 遍历至 prefix 的上界）。
• 禁止在每次 QUERY 时对全集合再排序（会超时）。

输入输出示例

输入格式：

• 第一行：整数 Q（操作数）
• 接下来 Q 行每行一条指令，指令有三类：
  • ADD word
  • DEL word
  • QUERY prefix K

输出格式：

• 对于每条 QUERY 指令，输出一行结果：空格分隔的单词列表，或单独一个字符“-”。

示例输入： 10 ADD apple ADD app ADD application ADD apt QUERY ap 3 DEL app QUERY ap 3 ADD apron QUERY ap 5 QUERY b 3

示例输出： app apple application apple application apt apple application apron apt

说明：

• 第一次查询返回以“ap”开头的前三个词，按字典序为 app, apple, application
• 删除 app 后，再查前三个为 apple, application, apt
• 添加 apron 后，再查最多 5 个为 apple, application, apron, apt（共 4 个）
• 查询以 b 开头时不存在，输出“-”

测试用例

测试用例1：基本操作与重复插入/删除 输入： 14 ADD cat ADD car ADD cart ADD car QUERY ca 5 DEL car QUERY ca 5 DEL car DEL dog QUERY c 2 ADD dog QUERY d 3 DEL dog QUERY d 1

输出： car cart cat cart cat cart cat dog

测试用例2：边界与前缀等于单词 输入： 12 ADD a ADD ab ADD abc ADD abcd QUERY a 10 QUERY ab 2 DEL ab QUERY ab 3 DEL a QUERY a 2 DEL abc QUERY ab 5

输出： a ab abc abcd ab abc abc abcd abc abcd abcd

测试用例3：无结果与K为1 输入： 8 ADD hello ADD help QUERY hi 3 QUERY h 1 DEL hello QUERY h 1 DEL help QUERY h 1

输出：

hello help

测试用例4：大K与顺序校验 输入： 9 ADD beta ADD bet ADD better ADD between ADD be QUERY be 10 DEL bet QUERY be 10 QUERY bet 10

输出： be bet beta better between be beta better between beta better between

评分标准

• 正确性（70分）
  • 集合语义正确处理重复 ADD/DEL（10分）
  • QUERY 仅返回当前存在的单词，字典序正确（20分）
  • 空结果输出“-”（5分）
  • 删除后数据结构一致性（防止“幽灵词”）（15分）
  • 前缀即完整单词与其扩展词同时存在时的正确性（10分）
  • 边界情况处理（空前缀不允许、K≥1、词长范围）（10分）
• 性能与实现（20分）
  • 操作复杂度与内存控制合理，避免全量排序/线性扫描全集（10分）
  • 查询时基于前缀节点的受限 DFS/迭代，能提前剪枝（10分）
• 代码质量（10分）
  • 结构清晰、适当封装、命名规范、注释说明关键逻辑（10分）

解决思路

• 数据结构选择
  • Trie（推荐）
    • 每个节点包含：
      • children[26] 或 Map<Character, Node>
      • isWord 布尔标记
      • passCount（通过该节点的单词数量，用于删除时回收和查询时快速判断是否有必要继续）
    • 插入（ADD）
      • 沿路径创建缺失节点，passCount++，尾节点标记 isWord=true
      • 若单词已存在（尾节点 isWord 已为 true），则不重复计数
    • 删除（DEL）
      • 若单词不存在直接返回
      • 沿路径 passCount--，当子节点 passCount 归零时可释放该子树（优化内存，非必须）
      • 尾节点 isWord=false
    • 查询（QUERY）
      • 先走到前缀节点，若不存在直接输出“-”
      • 从该节点起按字母 a→z 做受限 DFS/迭代，遇到 isWord 则收集，直到收集到 K 个或子树耗尽
      • 用 StringBuilder/数组维护当前路径，避免重复字符串拼接带来的高开销
  • 有序集合（备选，依赖语言特性）
    • 将所有单词保存在 TreeSet/ordered set
    • 对 prefix，计算下界 lower_bound(prefix) 与上界 bound= prefixWithNext(prefix)（如将最后一位+1或 prefix + '{'）
    • 从下界起迭代最多 K 个、且严格小于上界的元素
    • 插入/删除 O(log N)，查询 O(log N + K)
• 关键边界与注意点
  • 同一单词重复 ADD 不应改变结构（可通过尾节点 isWord 判断）
  • 删除不存在的词不应抛出异常，不改变结构
  • 查询时要确保严格以 prefix 开头；使用 Trie 时自然满足；使用有序集合时需检查上界
  • K 可能大于可用词数，确保不越界且按实际数量返回
  • 字典序需与字符集一致（仅 a-z，'a' < ... < 'z'）
• 复杂度分析（Trie 方案）
  • ADD/DEL：O(L)
  • QUERY：O(P + min(K, M) * avgWordLenInSubtree)，通常可视为 O(P + 输出规模)
  • 空间：O(Σ L)，Σ为当前字典中单词的总长度，常数与分支度有关（26）

提示：若使用 Python，建议用数组表示 26 个孩子并用整数索引映射字符；DFS 时避免深层递归（可改用显式栈）以防极端情况下的递归深度问题。