面向NPC任务的SEND/WAIT信号机制下的数据竞争检测需求

静态检测算法（基于任务执行图） #

适合在任务部署前分析执行图，无需运行游戏，逻辑简单直接。

核心建模思路 #

把任务执行图中的原子任务、同步操作（SEND/WAIT、ENTER/EXIT）、共享资源抽象为状态和约束：

• 信号量初始值全为0，WAIT(X,0)+SEND(X,1)等价于获取锁，SEND(X,0)等价于释放锁；ENTER/EXIT临界区本身就是互斥锁操作。
• 轮询执行意味着任意两个未被同步约束的原子任务可以交替执行。

数据竞争检测步骤 #

1. 标记共享资源访问点：遍历所有原子任务，标记出所有访问共享资源的节点。
2. 构建同步约束集：
   • 对临界区：同一临界区的ENTER/EXIT包裹的所有原子任务，属于互斥执行集合（任意两个任务不能同时执行该集合内的操作）。
   • 对SEND/WAIT：如果任务A执行SEND(X,1)，所有需要WAIT(X,0)才能继续的任务B，建立A→B的顺序约束（A的相关操作必须在B之前执行）。
3. 检测无约束访问对：对每一对共享资源访问点，检查是否存在两条执行路径，使得两个访问可以在**没有同步约束（不属于同一互斥集合、没有顺序约束）**的情况下被轮询执行。如果存在，则判定为数据竞争。

死锁检测步骤 #

1. 构建资源-任务映射：
   • 临界区：记录当前持有临界区的任务（执行ENTER后未EXIT）。
   • 信号量：记录当前持有信号量的任务（执行SEND(X,1)后未执行SEND(X,0)）。
2. 构建等待图：节点为NPC任务，若任务A等待的资源（WAIT(X,0)阻塞、等待ENTER临界区）被任务B持有，则添加边A→B。
3. 检测循环等待：遍历等待图，若存在环，则判定为死锁。

动态检测算法（运行时插桩） #

适合游戏运行时实时检测，适配轮询执行的原子任务逻辑，无需复杂预分析。

数据竞争检测（适配SEND/WAIT的简化Lockset） #

解决原Eraser/Lockset失效的核心是把SEND/WAIT显式映射为锁操作：

1. 状态跟踪：
   • 为每个信号量X维护持有者（初始为null）：任务执行WAIT(X,0)成功后，标记自身为X的持有者；执行SEND(X,0)后，清空持有者。
   • 为每个临界区维护当前持有任务。
   • 为每个共享资源维护锁集合：记录所有保护过该资源的临界区、信号量。
2. 竞争判定：
   • 当任务访问共享资源时，收集当前任务持有的所有锁（已进入的临界区、已获取的信号量），更新该资源的锁集合。
   • 若两次访问该资源的锁集合交集为空，且两次访问来自不同任务，则判定为数据竞争。
   • （无需区分读写，所有访问均视为冲突）

死锁检测（运行时等待图） #

1. 状态跟踪：
   • 为每个任务维护持有资源列表（当前持有的临界区、信号量）和等待资源列表（阻塞中的WAIT目标、等待的临界区）。
2. 等待图维护：
   • 任务进入阻塞状态时，找到持有该资源的任务，添加边当前任务→持有任务。
   • 任务释放资源时，移除所有指向该任务的等待边。
3. 环检测：每次等待图更新后，检查是否存在环，存在则触发死锁告警。

简易优化点 #

• 静态分析时，可仅关注用户指定的共享资源，无需自动推断，减少计算量。
• 动态检测时，因原子任务是轮询执行，可在每个原子任务执行前后做状态同步，无需细粒度插桩。

内容的提问来源于stack exchange，提问作者ListigerLurch