Page 51 - 《软件学报》2021年第6期

郝宗寅 等:Petri 网的反向展开及其在程序数据竞争检测的应用 1625

Table 4 Results of directed unfolding and reverse unfolding in randomtree (Continued)
表 4 directed unfolding 与反向展开在 randomtree 上的实验结果(续)
Unf-hmax RUnf-blcok+dfs
测试用例 |T|
|E| 时间(ms) |E| 时间(ms)
randomtree600 5 739 33 183 32 4
randomtree625 5 835 27 137 24 3
randomtree650 6 238 36 83 31 5
randomtree675 6 423 34 77 31 4
randomtree700 6 529 28 57 26 4
randomtree725 7 026 55 142 51 9
randomtree750 7 133 46 112 38 26
randomtree775 7 415 54 131 49 12
randomtree800 7 673 21 59 20 4
randomtree825 7 689 32 78 29 4
randomtree850 8 030 16 41 15 3
randomtree875 8 224 27 90 25 7
randomtree900 8 402 30 71 28 19
randomtree925 8 762 54 161 47 18
randomtree950 9 135 66 229 59 12
randomtree975 9 491 56 228 52 12
randomtree1000 9 462 49 152 43 8

结果表明:在 randomtree 上,基于 block+深度优先策略的反向展开效果最佳,在全部 37 组用例上,|E|的规模
均最优.值得注意的是:在正向展开,hmax 策略相比无启发式策略有明显的效率提升.这在一定程度上说明了,启
发式技术可以弥补算法在性质上的不足.
(2) threadlock
用例集 threadlock 按照如下规则模拟了一类线程-锁模型:假设有 x 个线程 y 把锁,x 个线程依次申请锁 1,
锁 2,...,锁 y,接着依次释放锁 y,锁 y−1,...,锁 1.目标标识由每个线程的终止库所组成.规定算法的最大扩展次数为
10 000 次,最大运行时间为 70 秒.实验结果如表 5 与图 10(b)所示.

Table 5 Results of directed unfolding and reverse unfolding in threadlock
表 5 directed unfolding 与反向展开在 threadlock 上的实验结果
Unf-dfs RUnf-blcok+dfs
测试用例 |T|
|E| 时间(ms) |Ext| |E| 事件(ms) |RExt|
threadlock2_1 6 8 20 1 8 10 5
threadlock3_1 10 12 7 3 12 8 11
threadlock3_2 16 18 27 3 21 14 23
threadlock4_1 14 16 19 6 16 10 19
threadlock4_2 22 24 7 6 28 8 41
threadlock4_3 30 32 8 6 40 7 60
threadlock5_1 18 20 9 10 20 2 29
threadlock5_2 28 30 5 10 35 5 62
threadlock5_3 38 40 8 10 50 7 91
threadlock6_1 22 24 5 15 24 3 43
threadlock6_2 34 36 20 15 42 5 84
threadlock6_3 46 48 23 15 60 25 129
threadlock8_4 78 80 29 28 104 39 291
threadlock10_5 118 120 34 45 160 87 554
threadlock12_6 166 168 87 66 228 105 943
threadlock14_7 222 224 85 91 308 223 1 474
threadlock16_8 286 288 72 120 400 161 2 186
threadlock18_9 358 360 70 153 504 399 3 088
threadlock20_10 438 440 131 190 620 497 4 211
threadlock50_25 2 598 2600 3 746 1 225 3 800 49 214 63 785

结果表明:基于深度优先策略的正向展开在 threadlock 上效果最佳,其|E|的规模在 20 组用例中有 15 次最优,
有 5 次同基于 block+深度优先策略的反向展开持平;且随着用例规模的增大,正向展开的运行时间明显优于反
向展开.然而 threadlock 中,Petri 网的正向分支与反向分支数量相差不大,理论上正向展开与反向展开的效率也
应该相近,这与实验结果相违背.分析可知:随着用例规模的增大,RExt 中的冗余扩展数量迅速增加,导致反向展