一种验证并发程序中违反原子性错误是否被正确修复的方法

摘要

一种验证并发程序中违反原子性错误是否被正确修复的方法，利用原始程序执行错误时的执行日志，结合原子性错误的各种模式构造新的、适合于修复后程序的执行日志，并通过观察修复后的程序是否能够按照新的日志正确执行来判断原子性错误是否被修复。用户在并发程序出错后，使用同步化方法修复原子性错误，本发明方法能够帮助用户在重复执行修复程序若干次后自动判断bug是否被正确修复。本发明方法不要求用户知道Bug的准确位置，符合用户检验错误是否被修复的惯性方法。

主权项

一种验证并发程序中违反原子性错误是否被正确修复的方法，其特征是利用原始程序执行错误时的执行日志，结合原子性错误的各种模式构造新的、适合于修复后程序的执行日志，并通过观察修复后的程序是否能够按照新的日志正确执行来判断原子性错误是否被修复，包括以下步骤：1)利用原始程序的错误执行日志以及修复后的程序，构造与错误执行日志对应同时又包含修复信息的执行轨迹，所述修复指同步化，所述修复信息指如何使用同步化来修复的信息，一个执行轨迹是一个事件序列，表示为δ＝<e_i>，其中每个事件e_i包含下列属性：t_i：事件e_i所属的线程；m_i：事件e_i所存取的内存位置；l_i：当事件e_i执行时，其所拥有的锁；a_i：事件e_i的存取类型，包括读，写，获取锁，释放锁，等待，通知，创建线程和等待线程结束8种类型；2)利用所得执行轨迹，以及原子性错误的不同模式，构造适合于修复后程序的新执行轨迹：21)使用步骤1)所构造的执行轨迹，首先根据一个并发程序必须满足的约束，即Happens‑Before关系和锁约束构造一个有向无环图，该图中包含执行轨迹中的所有事件，事件用图的结点表示，且仅包含Happens‑Before关系和锁约束所要求的事件间顺序关系，顺序关系用图的有向边表示；22)根据原子性错误的各种模式，在步骤1)所构造的执行轨迹中搜索相应的事件序列；23)不断的向有向无环图中添加符合原子性错误模式的边，直到其不能满足Happens‑Before关系和锁约束，输出一个新构造的有向无环图，判断新构造的有向无环图是否覆盖所有满足原子性错误的模式的边，如不能覆盖，则构造新的有向无环图来覆盖他们，直到构造得到的所有有向无环图覆盖所有满足原子性错误模式的边；24)对于步骤23)中的每一个有向无环图，继续向其中加入有向无环图不包含但原始执行轨迹包含的边，直到不能满足Happens‑Before关系和锁约束，最终输出该图的一个拓扑排序，即一个新执行轨迹；3)按照构造的新执行轨迹，执行修复后的程序，观察程序是否正常执行来判断原子性错误是否被修复。