基于多核PC 的事务内存冲突管理算法的改进

张婷，李文敬

（1.广西民族大学相思湖学院，南宁530008；2.南宁师范大学，南宁530001）

0 引言

软件事务内存的竞争管理策略在事务发生冲突时决定是否放弃其中一个事务，Scherer 等人对此进行了专门的分析，但是目前并没有一个能够适用于不同环境的竞争管理策略算法。现有竞争管理策略有：Aggressive 激进算法、Polite 礼让算法、Randomized 随机算法、Karma 报应算法、Timestamp 时间戳算法等，本文将对竞争管理算法进行理论分析，并结合Repeat-Hash冲突检测算法及冲突规避算法进行实验，将不同的竞争管理算法的评测结果进行对比，选择出最优的算法，验证该算法可以在一定程度上提高性能。通过三者的结合所构成的完整冲突管理算法，降低了系统运行时冲突发生的概率，并且缩短运行时间。

1 竞争管理

并发的事务之间发生冲突，在何种条件下，决定哪个事务被中止，是竞争管理来决定的问题。竞争管理发生在冲突检测之后，事务申请提交之前，保证每个事务都能在有限时间内完成。文献[1,2]介绍了一些新颖的竞争管理策略,并评估了它们在各种各样的基准下的表现,在一个给定的数据结构下，竞争管理所要做的总结为一个问题：当检测出两个事务同时访问同一个内存单元发生冲突时，我们该怎么做？这些请求交由竞争管理器来解决，竞争管理器的作用是：①判断事务是否在这个时间可以开始或重新执行。②判断事务是否要中止与之竞争的敌对事务。

假设两种极端的情况，第一种是当一个事务发现与别的事务发生冲突时，总是让自己中止，让敌对事务继续执行，这样的礼貌行为将导致死锁或优先级反转的问题。第二种情况是事务总是中止敌对事务，让自己继续执行，这样的激进策略有可能导致活锁。因此，设计竞争管理方案时，要尽量介于两种极端情况之间。

目前学术界研究出了一些竞争管理算法，但是竞争管理的设计空间还非常大，仍需继续研究与改进。下面，给出几种常见的竞争管理算法的分析。

Aggressive 侵略算法是当发生冲突时，总是选择中止与之竞争的事务，让自己获得资源，这使得它非常容易导致活锁问题，目前，学术界将该策略形成一个有用的基准来跟其他策略进行实验比较。

与之相反的，是Polite 礼貌算法，为了防止某个事务无休止的礼貌等待，该算法增加了等待期限。当检测到冲突时，该事务先礼貌地等待一段时间，为2n 的单位时间，当重试的次数n 达到了最大的重试次数8，那么礼貌算法将会毫无条件地中止其竞争的事务。

究竟选择两个事务中的哪一个继续运行，是算法的关键问题。Timestamp 时间戳算法以事务的开始时间作为判断事务是否被中止的标准，当事务之间发生冲突时，较早开始的事务得以继续执行，较晚的事务则被中止掉。这样可以避免之前做了大量计算工作的事务被中止掉，造成计算资源浪费。但是如果较晚开始的事务一直被中止，不能得以执行，将造成死锁、优先级反转等问题。

为了让优先级低的事务也能够在有限时间内提交，Karma 工作量算法则给了优先级低的事务增加优先级的机会。Karma 算法总是企图根据一个事务迄今为止所做的工作量，来决定是否中止该事务。当一个事务遇到冲突，竞争管理器将会比较该事务与敌对事务之间的优先级，如果该事务的优先级较高，则对方就要流产。反之，该线程就要等待一段固定的时间，等待敌对事务完成。该算法为了解决短事务因优先级低不断被中止的问题，将成功提交的事务优先级置为0，被中止的事务继续保留原来的优先级，这使得短事务在不断重试，优先级累加之后，能达到超过长事务的优先级，从而可以顺利提交。但是，有可能会出现敌对事务执行时间太久，阻塞其他的竞争线程，影响整体提交的效率。

因此，Polka 算法增加了等待时间的上限，Polka 算法是Polite 算法与Karma 算法的结合，将两种算法的名称结合在一起取名，因此称为“Polka”。该算法结合了Polite 与Karma 的优点，各取所长。它保留了Polite算法的一定长度的回退时间，以及Karma 的优先级累加的机制。因此，该算法的设计思想为：被中止的事务T 回退进行重试的时间m 等于该事务与其敌对事务的优先级之差p，若重试的时间超过m，则竞争管理器让事务T 继续执行，中止竞争的事务。该算法在很多的实验中，获得了很高的性能。

为了改进松散的解决冲突的规则，Kindergarten 队列算法倾向于让事务有秩序的申请提交。对于每一个事务,竞争管理器维护一个列表（起初是空的），该列表存储着事务T 之前中止掉的敌对事务。当冲突发生时，竞争管理器核对该列表，如果目前的敌对事务在列表中能找到，则中止该敌对事务。若未找到，则将新的敌对事务添加进列表中，事务T 则要回退一小段时间长度。在回退的时间间隔里同时将敌对事务的哈希地址存储至列表。若在固定的等待时间内，事务T 仍然在等待相同的敌对事务申请提交，则竞争管理器就将事务T 中止。当事务T 重新被一个线程执行，并出现相同的敌对事务时，则可以在列表中找到敌对事务，并且中止敌对事务，保证了事务T 可以顺利提交。

常用的竞争管理算法还有Greedy、Eruption、Randomize、Published Timestamp 等，根据不同竞争管理算法对于竞争事务的处理方式，我们做出如表1 所示的分类对比。

表1 竞争管理策略分类

文献[1,2]研究表明，并没有一种竞争管理算法适用于所有的应用，不同的算法在不同的系统及程序中，有不同的性能表现。

2 竞争管理算法的设计

2.1 Polite和Timestamp算法简介

为了防止某个事务无休止地等待敌对事务执行完成，Polite 礼貌算法增加了等待时间的上限。当检测到冲突时，该事务先礼貌地等待一段时间，为2n 的单位时间，当重试的次数n 达到了最大的重试次数8，那么Polite 算法将会毫无条件的中止执行耗时太久的竞争的事务。但是Polite 算法的缺点是并没有明确让哪种事务等待，有可能出现工作量大的事务等待工作量小的事务，最后工作量大的事务被判回滚，浪费了大量计算资源，出现优先级反转问题。

因此，究竟选择两个事务中的哪一个继续运行，而不导致计算资源浪费，是算法的关键问题。Timestamp时间戳算法以事务的开始时间作为判断事务是否被中止的标准，当事务之间发生冲突时，较早开始的事务得以继续执行，较晚的事务则被中止掉。这样可以避免之前做了大量计算工作的事务被中止掉，造成计算资源浪费。但是Timestamp 的缺点是：如果较晚开始的事务一直被中止，不能得以执行，将造成死锁、优先级反转等问题。

两种算法各有优缺点，Polite 算法没有优先级的比较，但是限制了等待的时间长度；Timestamp 算法对优先级进行比较，比较后直接判执行和回滚，没有对优先级进行时间的维护。因此，我们尝试将两种算法结合，各取所长，构建竞争管理算法“Polti”。

2.2 竞争管理算法Polti的设计

目前已经实现了重复探测的Hash 冲突检测，以及引入高低频区分的记录表冲突规避机制，最后需要设计竞争管理算法来实现对冲突事务的管理。本文所设计的完整冲突管理算法包括冲突规避、冲突检测以及冲突时调用的竞争管理方案。

竞争管理是对于每一个线程都有作用的，当检测出事务T1 与事务T2 产生冲突，事务T1 将会请求竞争管理器做出裁决，有三种可能的裁决方式：a、事务T1中止T2；b、事务T1 中止自己；c、事务T1 等待一段时间。

选择哪个事务中止或等待，都需要慎重考虑，因为有可能将工作量较大的事务中止，导致其之前的所有读写操作全部撤销，浪费大量计算资源。事务等待的时间长度也需要仔细权衡，因为有可能事务占有某数据的时间太长不释放，而导致其他的事务不能及时获取数据的所有权。

为了更好地对冲突的事务进行竞争管理，避免死锁或活锁的发生，本文尝试将“Polite”和“Timestamp”相结合，形成一种简称为“Polti”的竞争管理算法，算法简单，实现容易，性能消耗低。算法的基本思想是冲突的事务T1 和T2 之间，较晚开始的事务T1 要等待一段时间，先进行2^n 个单位时间（毫秒）的等待，其中n 为重试次数，每重试一次就进行一次冲突检测，检测写入的地址是否有其他线程在使用，如果没有则说明无冲突，事务T1 得以继续执行。如果仍检测出有线程使用则说明出现冲突，继续进行2^（n+1）个单位时间的等待，n=n+1，当重试次数n 累加到8 时，事务T1 不再等待，而是直接中止与之竞争的事务T,让其回滚，让自己占有地址的使用权。首先，我们对Polti 算法进行理论分析：

事务T1 和T2 发生冲突后，竞争管理算法首先比较两者的优先级p1 和p2。

（1）当p12^7,则T1 不再等T2 申请提交，而是让自己继续执行。

（2）当p1>p2 时，事务T1 能最终不被中止，得以申请提交的条件为它让T2 等待的时间m 小于2^7 个单位时间，也就是说T1 要在m 个单位时间之内执行完：

m ≤2^n.(n=n+1,n<8) （1）

从上述式子可以看出，较早开始的事务理论上来说应该可以先申请提交，但是实际上却不能按时申请提交，说明这个事务执行所占用的时间太多，计算量太大。因此Polti 算法设计为：执行耗时久的事务将被延后执行，耗时短的事务优先执行，从而提高算法的效率。

如图1 所示，事务T1 开始的时间比与之竞争的事务T2 早，优先级p1 大于p2，因此先让T1 先执行，T2等待m 个单位时间，但是有可能出现T1 的计算量较大，执行耗时很多，则T2 不能无休止等待，当等待时间大于2^7 个单位时间时，T2 中止T1，让自己继续执行，执行完成后申请提交。

接下来，我们对算法的执行时间进行分析。在没有等待时间的情况下，m 个事务最多在运行了m·tmax的时间之后，方可申请提交。tmax 为事务执行的最长时间，在没有引入等待时间上限的情况下，tmax 的长度不受限制，有可能某些竞争事务执行了大量的时间，而影响了整体的提交效率。Polti 算法让优先级低的事务等待一个常数时间，达到等待时间上限后，执行耗时久的竞争事务将被判中止，tmax 也相应缩短，总体的提交效率提升。

图1 Polti算法维护事务优先级的流程

2.3 冲突管理算法的构建

接下来，我们将融合重复探测Hash 冲突检测算法和高低频区分的冲突规避算法的优势，结合Polti 竞争管理算法的优点，构建基于多核处理器的事务内存冲突管理算法Full-Polti。

Full-Polti 算法描述如下：

Begin：

输入：定义最大线程数，随机生成N 个随机数，维护高低频记录表，记录历史冲突的地址值与冲突次数n。

输出：输出的参数，第一列是线程id，第二列是hash 地址，第三列是发生冲突的次数，并输出运行时间（毫秒）。

Step1：使用OMP_NUM_THREADS 定义执行中最大的线程数。

Step2：每一个线程都取一个随机数作为关键字，首先在高低频记录表中进行寻址，预测该关键字出现冲突的可能性，如果可能性不大，则可以开始执行质数取余的哈希运算。

Step3：在冲突检测阶段，用重复探测Hash 冲突检测算法检测出两个事务发生读写地址冲突后，交由竞争管理进行裁决。

Step4：首先竞争管理器先让开始执行时间较早的事务继续执行，开始时间较晚的事务等待2^n 个单位时间，n 为重试次数，n=n+1。

Step5：若n<8，等待的事务检测到与竞争事务无冲突，则可以继续执行。

Step6：若n=8,则等待的事务不再等待竞争事务的申请提交，而是直接中止掉竞争事务，让自己继续执行。

接下来，我们对算法的时间复杂度进行分析。对于P 个线程同时执行N 个事务，将质数取余的运算结果映射到哈希地址上，哈希表中的地址空间数量为C，其中C>N,一个事务执行任务所需的时间为Tr，一个事务等待的时间为Tw，经推导，得到Polti 算法的时间复杂度为：

为了简化模型，我们假设事务等待和执行的时间比为1：1，上述式子可以写成：

经计算，该式子是一个收敛的数组，x 的值越大，计算出的值越小，说明该算法能够在一定的有限时间能将任务执行完成。

Polti 算法的设计可以避免事务之间无休止的相互等待，也避免了将开始较早的事务撤销而导致的计算资源浪费。相比直接中止的激进算法，该算法给事务一定的等待和重试的时间，避免长事务的长时间执行，保证了事务的提交时间。

3 算法实现

本文在程序并行域部分使用OpenMP 编译指导语句，将串行程序并行化，OpenMP 应用编程接口API 是在共享存储体系结构上的一个编程模型：其中包含编译制导（Compiler Directive），运行库例程（Runtime Library）以及环境变量（Environment Variables）。OpenMP使用Fork-Join 作为基于线程的并行执行模型。Fork-Join 将主程序中不能并行执行的部分由主线程执行，能够并行执行的部分交由若干个线程同时执行，最后将执行结果进行合并。Fork-Join 结构将其所包含的代码划分给线程组的各个线程来执行，也可以通过编译指导语句，设置并行sections，不同的任务给不同的线程执行，或者设置single，只由一个线程来执行代码段。本实验的并行程序流程如图2 所示。

图2 多线程并行程序流程

多线程并行程序流程为：随机生成N 个随机数，由n 个线程执行质数取余的操作，将冲突检测出的冲突地址和次数记录到记录表中，作为冲突规避的依据。冲突的线程进入到竞争管理阶段，根据竞争管理算法，让其中一个事务继续运行，其他事务中止或等待。继续运行的线程完成计算后，将数据申请提交。被中止的线程则要回滚，放弃之前所做的所有计算，重新开始执行，当N 个随机数都计算完成后，由JION 把所有的数据收集完整，统一输出。

本实验使用的OpenMP 指导语句实现多线程的并行同步与归并。使用“omp_num_treads”语句设置环境变量，定义执行中最大的线程数。在多线程同时执行的可并行程序部分，加入“#pragma omp parallel for”语句，将可并行执行的语句自动并行化，紧随它的循环语句由线程组并行执行。在线程同步的设置上，使用“#pragma omp critical（name）”语句使得并行域中的代码块每次只能执行多个线程中的一个，其他线程则被阻塞，该语句用于竞争管理部分的线程等待。使用barrier 制导语句用来同步一个线程组中所有的线程，本实验的barrier 为隐藏的栅障，等并行区域中所有线程都执行完成后，再继续执行主线程。最后，将执行结果进行归并，使用“reduction（operator：list）”子句在结构尾部对线程中的变量进行归并，保证最后输出的结果是正确的。

4 实验结果与分析

4.1 实验结果

本实验的硬件平台为：英特尔22 纳米酷睿i5-3450 4 核处理器，CPU 主频3.7GHz，内存为8G。软件平台为：Microsoft Windows 7 操作系统，Microsoft Visual Studio 2010（OpenMP），使用C++语言编写程序。

为了制造更多的冲突，以检验竞争管理算法的性能，我们将质数表的个数从699 个减少到25 个。编程实现事务内存冲突管理算法，在重复探测Hash 冲突检测算法中分别加入竞争管理算法Polite、Timestamp 和Polti，并使用高低频区分的冲突规避功能，形成一套“完整polite 冲突管理算法”“完整Timestamp 冲突管理算法”和“完整Polti 冲突管理算法”，分别简称为“Full-Polite”、“Full-Timestamp”和“Full-Polti”，当线程数为16 时，实验结果如图3 所示。

图3 Full-Polite、Full-Timestamp、Full-Polti 算法运行时间对比

实验结果显示，Full-Polti 冲突管理算法的用时要少于其余两种算法，因为Full-Polti 定义了优先级低的事务所需等待时间的上限，因此能让等待的事务中止掉耗时多的竞争事务，不至于耗费太多等待时间。

本文经实验验证了Full-Polti 算法的优势，接下来，分析冲突管理算法给事务内存系统所带来的性能提升。为了更直观的进行实验对比，我们分别编程实现了以下三种算法：

（1）“完整Polti 冲突管理算法”——即Full-Polti。

（2）“无预测Polti 冲突管理算法”——不使用冲突规避机制的Polti 冲突管理算法。

（3）“无预测无管理算法”——既无冲突规避又无竞争管理的算法。

在相同的初始参数下，当线程数为16 时，对三种算法进行测试。测试结果如图4、图5 所示

图4 三种算法运行时间对比结果

图5 三种算法冲突次数对比结果

4.2 结果分析

从以上实验结果可以看出，完整的Polti 冲突管理算法“Full-Polti”的表现最为优越，在相同的初始参数下，完整算法的运行时间最短，冲突次数最少。因为完整算法使用了冲突预测避免了不必要的冲突发生，使用Polti 竞争管理算法对冲突的事务进行合理管理，保证事务在有限的时间内得以申请提交，使运行效率得到提高，最终输出的冲突次数也比无预测无管理的算法减少了将近二分之一。

性能评测结果显示，融合冲突检测算法和冲突规避算法的优势，结合Polite 和Timestamp 两种策略的优点，所构建的基于多核处理器的事务内存冲突管理算法，整体性能基本上可以满足多核PC 系统的需要，另外，使用冲突规避机制可以在一定程度上提高系统性能,总体来说，设计合理的冲突管理算法对事务内存系统的性能和效率有着重要影响，可以显著提高事务内存系统的执行性能。

最后，我们对算法的时间复杂度进行理论上和实验结果的一致性分析。首先我们计算算法理论上的时间复杂度，将N=2500，C=5000，P=4，x=1,2,3,…,8，代入公式（3）中计算，计算得到理论上的时间复杂度为2502.0016，乘上单位时间，我们在实验中定义RUN_TIME 为17 个单位时间，因此理论上该算法的运行时间为42534.03ms，根据实验结果，Full-Polti 的平均运行时间为43012ms，与理论上的计算值相近，因为还有其他时间损耗，实际运行时间比理论值稍大。综上，实验结果与理论分析的结论是一致的。

5 结语

竞争管理是事务申请提交前的一个操作，是对冲突检测的结果进行的，多个事务发生冲突后，应该如何管理冲突事务，选择哪个继续执行，哪个要回滚。本文首先将目前的几种竞争管理算法进行研究并归纳分析。在实验中，尝试将Polite 和Timestamp 两种算法结合，构建Polti 竞争管理算法，将重复探测Hash 冲突检测算法与之进行结合，并使用高低频区分冲突规避算法进行冲突预测。实验结果表明，完整的“三合一”Full-Polti 冲突管理算法融合了冲突检测算法和冲突规避算法的优势，结合了Polite 和Timestamp 两种策略的优点，在性能上较为优越，在数据规模大的情况下，更能体现出优势。