本站原创
摘 要：事务存储是一种并行编程同步方式，与基于锁的同步方式相比具有易于使用、可扩展等优点。对软件事务存储系统竞争管理策略中的序列化调节机制进行了改进，使竞争管理策略在序列化调节的支持下，更加有效地对冲突进行消解。经测试表明，与传统的竞争管理策略相比，带有序列化调节机制的竞争管理策略在高冲突率状况下的性能有明显改善。
关键词：竞争管理策略；事务存储；序列化调节机制；编程同步方式；并行处理
16727800（2013）003001203
0 引言
随着多核处理器的普及，充分利用计算机的并行处理能力已成为了提高软件性能的重要手段。然而，开发有效的并行程序对开发人员来说并不是一项轻松的工作，目前基于锁的线程同步机制的熟练使用需要较长时间的培训，使用不当很容易增加软件中的错误，而且这些错误难以发现和调试。更重要的是锁不具备可组合性，这些都对并行程序的扩展性和复用性带来了不利影响。事务存储（transactional memory，TM）作为一种新的同步手段，已经受到了越来越多的关注。它借鉴了数据库中事务的概念，把多线程之间复杂的并发操作抽象成大量事务的并行执行。TM的事务具有与数据库事务类似的初始化、执行、回滚等操作，当发生共享资源的访问冲突时，由事务存储系统负责决定让哪个冲突事务执行，哪个事务放弃或等待，这样就避免了通过临界区控制资源互斥访问的繁琐方式，减轻了开发者的工作量。当然，事务存储模型是遵循特定的一致性规范，以保证人们可以借助其提供的扩展接口编写满足正确性要求的程序。
事务存储系统有3个主要功能：冲突检测、版本控制和冲突消解。在具体实现上可以分为支持事务指令集的硬件事务存储（Hardware Transactional Memory，HTM）、基于运行时库实现的软件事务存储（Software Transactional Memory，STM）和混合型事务存储（Hybrid Transactional Memory）。软件事务存储系统虽在性能上不及硬件事务存储系统，但具有设计灵活、扩展性好、不需要特定硬件支持等优点。TM在实现上一般会把冲突消解的任务交由竞争管理器（contention manager，CM）来完成，由CM决定冲突中的事务是否放弃，CM对系统的吞吐量和竞争比（contention ratio）具有直接影响。
现有的竞争管理策略普遍存在依赖负载类型的问题，往往一种策略在某种应用下表现极好，而在另一种应用下的性能又很差，甚至不如串行执行下的性能。这主要是因为当冲突率过高时，系统中有大量事务中途放弃，造成CPU资源的浪费，降低了系统整体吞吐量。本文的第2节主要改进了基于序列化调节（Serialization Adjustment，SA）的冲突管理策略，当系统的冲突率过高时，通过对易造成冲突事务的序列化，降低了冲突率，有效提高了吞吐量；第3节实现了序列化后的演进保证；第4节对实验结果进行了评估。
在基于非阻塞的软件事务系统已在定义上避免了死锁的产生，但是却无法排除发生饥饿和活锁的可能性，因此竞争管理的一个重要任务就是避免活锁。大量实验表明，竞争管理器在负载有较高竞争强度的情况下，性能都不理想。一方面是因为竞争管理功能代码被频繁调用，占用了大量的执行时间；另一方面是因为高冲突率导致大量事务被迫放弃，这也最容易发生饥饿和活锁的情况发生。
（1）依据其竞争强度的定义，CI数值的变化仅仅受事务提交与否的影响，没有考虑事务本身占用或申请的共享资源数量与冲突率也存在正比关系。这样所导致的不利结果是保持和申请共享资源数量都不高的事务的CI会较快达到阈值，优先得到调度执行，而需要资源较多的大型事务的竞争强度相对会增长较慢，不利于其及时调度执行。
（2）事务在序列化后，其能否成功提交依然难以保证。ATS机制通过序列化调
针对上述问题，本文对竞争强度的概念做了改进，提出了扩展的竞争强度（Extended Contention Intensity，ECI）用于描述事务面临冲突的程度。ECI定义如下：ECIn=α*ECIn-1+（1-α）*CC+β*R 其中，ECIn-1表示上次计算ECI得到的值（初始为0）；CC表示当前冲突的判定结果，如果事务放弃，CC为1，反之如果事务提交，CC为0；α和β是权重因子，α用于控制ECI的增长幅度更偏向历史记录还是当前冲突状况，而β用于控制事务保持的共享对象数量在ECI中所占的比例；R表示事务每次执行所申请到的共享资源数量的均值。每个事务都会在提交或放弃时计算自己的ECI，以保证在竞争强度超过一定阈值时，及时得到序列化调度。
在图1中有3个重要时间点，在TimeLine1时刻，系统存在大量事务多次放弃，难以成功提交，如果不采取任何措施，ECI较高的事务（用实线深色的正方形表示）之间很可能会进一步产生冲突。这时冲突中的一方无论是放弃或是等待，都难以保证对方的顺利提交，更不用说防止饥饿和活锁的产生。在TimeLine2时刻，CM实例在调度器的帮助下进行了序列化处理，有效避免了系统性能的降低。在多个竞争管理器同时访问调度器的情况下，可以采用临界区对访问进行同步，但是由于调度器本身就是以阻塞的方式工作，此处引入临界区并不会影响其它事务的并行。在TimeLine3时刻，系统完成了高竞争强度事务的序列化任务，线程可以调用更多的事务执行，同时队列中的事务串行执行，节省了CPU的计算能力。本文的第3节会介绍CM如何为序列化后事务提供演进保证，使系统至少具有不低于采用粗粒度的全局锁机制时的性能。
检测如有两个事务TA和TB，TA是经序列化处理后的事务，TB是正常执行的事务，为保证事务TA可以不受到TB的干扰，需要应对两种情况：①TA发现了与TB的冲突，即TA是冲突主动方；②TB发现了与TA的冲突，即TB是冲突的主动方。对于第一种情况，只需要将TA切换为Aggressive策略即可保证TA的继续执行；对于第二种情况，需要在共享对象版本信息或是TA的事务描述符（Transaction Descriptor）结构中加入特定的标记位，这样，TB可以从共享对象的版本记录或是TA的事务描述符中找到信息，主动放弃自身。
图2描述了整个事务存储系统在序列化调节机制下的工作情况。从图中可以看出，序列化调度器将整个系统分成了两块区域。区域1中的事务ECI超过了阈值，在调度器和事务队列的控制下串行执行，而通过系统提供演进保证，这些事务在序列化后都可以成功提交。区域2中事务的ECI较低，说明其产生共享资源访问冲突的概率也较低，可以应用CM策略有效提高事务的并发度。由于区域1的序列化调节作用，系统在高冲突率的环境下可以保持不低于采用粗粒度的全局锁机制时的性能。
测试环境使用Intel Xeon 3.0 GHz CPU，内存2GB，操作系统为Linux。测试程序创建并启动一组线程，分别选用红黑树（Red Black Tree）和链表（Linked List）这两种基准数据进行10 000次随机查找、插入和删除3种操作。选取原始的Greedy策略和经过序列化调整改进的GreedySA策略分别执行10次，取平均值作为实验结果进行比较。图3和图4分别是在红黑树和链表下的测试结果。
图3中，在线程数量较少的情况下，事务并发度不高，访问共享资源时发生冲突的概率很低，序列化调节的开销在一定程度上降低了系统的吞吐量。然而随着线程数的增加，未经调节的Greedy策略性能出现了明显下降，这主要是由于随着并发度的提高，冲突率也会显著升高，大量事务因资源竞争而放弃。对于改进的GreedySA策略来说，在线程数增加时，竞争强度较高的事务会串行执行，在保留一定程度并发性的基础上避免了一些事务无谓的频繁放弃，有效抑制了系统性能的降低。在图4中，由于链表的结构特性，并发度的提高对性能的改善作用十分有限，然而通过观察可以发现，在序列化调节支持下的竞争管理策略和现有的竞争管理策略相比，在冲突率高的情况下的表现更加稳定。
4 结语
在事务存储系统中，竞争管理策略的重要任务是预防饥饿和活锁并最大程度地降低放弃事务的数量。竞争管理策略与集中管理方式相比，由于其分布式的特征，可以有效降低事务间的耦合度，减少同步操作的数量和开销。在序列化调节机制下，竞争管理器与调度器在功能上相互配合，最大程度地发挥彼此的优势。竞争管理器不仅负责探索事务的并发度，而且可以保护事务在序列化后顺利提交。调度器把频繁放弃和发生冲突的事务收集起来串行执行，为竞争管理器减轻了冲突处理的压力。实验数据表明，带有序列化调节机制的冲突管理策略具有更好的表现，特别是在并发度高的情况下有效配置了事务的执行方式，避免了系统性能的退化。
参考文献：
＼[1＼] SUTTER H AND LARUS J. Software and the concurrency revolution＼[J＼]. Queue，2005 （7）.
＼[2＼] GAREY M R， GRAHAMS R L. Bounds for multiprocessor scheduling with resource constraints＼[J＼]. SIAM Journal on Computing，1975（4）.＼[3＼] 彭林， 谢伦国， 张小强.事务存储系统＼[J＼].计算机研究与发展，2009（8）.
＼[4＼] HERLIHY M， LUCHANGCO V， MOIR M， et al. Software transactional memory for dynamicsized data structures＼[C＼]. In Proc of the 21st Annual Symp on Principles of Distributed Computing（PODC），2003.
＼[5＼] GUERRAOUI R， HERLIHY M， AND POCHON B. Toward atheory of transactional contention managers＼[C＼]. In Proceedings of the twentyfourth annual ACM symposium on Principles of Distributed Computing，2005.
＼[6＼] GUERRAOUI R， HERLIHY M， AND POCHON B. Polymorphic contention management＼[C＼]. In Proceedings of the 19th International Symposium on Distributed Computing，2005.
＼[7＼] SCHERERⅢ WILLIAM N， AND SCOTT MICHAEL L. Advanced contention management in dynamic software transactional memory＼[C＼]. In Proceedings of the 24th annual ACM symposium on Principles of Distributed Computing （PODC），2005.
＼[8＼] SHRIRAMAN A， SPEAR MF， HOSSAIN H， MARATHE V J， et al. An integrated hardwaresoftware approach to flexible transactional memory＼[C＼]. In Proceedings of the 34th annual international symposium on Computer architecture，2007.
＼[9＼] YOO R M， LEE H S. Adaptive transaction scheduling for transactional memory systems＼[C＼]. In Proceedings of the 20th annual symposium on Paralleli in algorithms and architectures，2008.
＼[10＼] SPEAR M F， MARATHE V J， SCHERERⅢ
（责任编辑：孙 娟）
关键词：竞争管理策略；事务存储；序列化调节机制；编程同步方式；并行处理
16727800（2013）003001203
0 引言
随着多核处理器的普及，充分利用计算机的并行处理能力已成为了提高软件性能的重要手段。然而，开发有效的并行程序对开发人员来说并不是一项轻松的工作，目前基于锁的线程同步机制的熟练使用需要较长时间的培训，使用不当很容易增加软件中的错误，而且这些错误难以发现和调试。更重要的是锁不具备可组合性，这些都对并行程序的扩展性和复用性带来了不利影响。事务存储（transactional memory，TM）作为一种新的同步手段，已经受到了越来越多的关注。它借鉴了数据库中事务的概念，把多线程之间复杂的并发操作抽象成大量事务的并行执行。TM的事务具有与数据库事务类似的初始化、执行、回滚等操作，当发生共享资源的访问冲突时，由事务存储系统负责决定让哪个冲突事务执行，哪个事务放弃或等待，这样就避免了通过临界区控制资源互斥访问的繁琐方式，减轻了开发者的工作量。当然，事务存储模型是遵循特定的一致性规范，以保证人们可以借助其提供的扩展接口编写满足正确性要求的程序。
事务存储系统有3个主要功能：冲突检测、版本控制和冲突消解。在具体实现上可以分为支持事务指令集的硬件事务存储（Hardware Transactional Memory，HTM）、基于运行时库实现的软件事务存储（Software Transactional Memory，STM）和混合型事务存储（Hybrid Transactional Memory）。软件事务存储系统虽在性能上不及硬件事务存储系统，但具有设计灵活、扩展性好、不需要特定硬件支持等优点。TM在实现上一般会把冲突消解的任务交由竞争管理器（contention manager，CM）来完成，由CM决定冲突中的事务是否放弃，CM对系统的吞吐量和竞争比（contention ratio）具有直接影响。
现有的竞争管理策略普遍存在依赖负载类型的问题，往往一种策略在某种应用下表现极好，而在另一种应用下的性能又很差，甚至不如串行执行下的性能。这主要是因为当冲突率过高时，系统中有大量事务中途放弃，造成CPU资源的浪费，降低了系统整体吞吐量。本文的第2节主要改进了基于序列化调节（Serialization Adjustment，SA）的冲突管理策略，当系统的冲突率过高时，通过对易造成冲突事务的序列化，降低了冲突率，有效提高了吞吐量；第3节实现了序列化后的演进保证；第4节对实验结果进行了评估。
1 竞争管理
目前，研究人员已从不同的思考角度提出了很多种不同的竞争管理策略，表1根据复杂度的不同，对其中几种典型的CM策略进行了分类。然而正如上文所说，这些CM策略普遍都存在对系统配置和应用环境敏感的情况。例如使用Timid策略在相同的配置下测试红黑树（Red Black Tree）的性能仅有其执行哈希表（Hash Table）性能的三分之一；在测试红黑树时，使用Karma策略采取早期冲突检测的性能只有采取惰性检测时性能的十分之一。在基于非阻塞的软件事务系统已在定义上避免了死锁的产生，但是却无法排除发生饥饿和活锁的可能性，因此竞争管理的一个重要任务就是避免活锁。大量实验表明，竞争管理器在负载有较高竞争强度的情况下，性能都不理想。一方面是因为竞争管理功能代码被频繁调用，占用了大量的执行时间；另一方面是因为高冲突率导致大量事务被迫放弃，这也最容易发生饥饿和活锁的情况发生。
1.1 竞争强度检测
文献＼[9＼]首次提出动态事务调度（Adaptive Transaction Schedule，ATS）的思想，引入了竞争强度（Contention Intensity，CI）的概念来衡量系统中事务的冲突率。如果事务的CI过高则说明存在大量事务因冲突而不能成功提交，系统会通过将具有高冲突事务串行调度来降低系统中的冲突率。测试数据表明，这一措施有效提高了事务存储系统的性能，但是通过分析可以发现原有的序列化调度存在一些不足之处：（1）依据其竞争强度的定义，CI数值的变化仅仅受事务提交与否的影响，没有考虑事务本身占用或申请的共享资源数量与冲突率也存在正比关系。这样所导致的不利结果是保持和申请共享资源数量都不高的事务的CI会较快达到阈值，优先得到调度执行，而需要资源较多的大型事务的竞争强度相对会增长较慢，不利于其及时调度执行。
（2）事务在序列化后，其能否成功提交依然难以保证。ATS机制通过序列化调
源于：论文网站大全www.udooo.com
度在一定程度上降低了冲突事务再次相遇的可能性，但序列化后的事务依然会发生冲突。特别在事务的资源需求差异很大的情况下，系统收敛较慢，发生冲突的概率依然很大。针对上述问题，本文对竞争强度的概念做了改进，提出了扩展的竞争强度（Extended Contention Intensity，ECI）用于描述事务面临冲突的程度。ECI定义如下：ECIn=α*ECIn-1+（1-α）*CC+β*R 其中，ECIn-1表示上次计算ECI得到的值（初始为0）；CC表示当前冲突的判定结果，如果事务放弃，CC为1，反之如果事务提交，CC为0；α和β是权重因子，α用于控制ECI的增长幅度更偏向历史记录还是当前冲突状况，而β用于控制事务保持的共享对象数量在ECI中所占的比例；R表示事务每次执行所申请到的共享资源数量的均值。每个事务都会在提交或放弃时计算自己的ECI，以保证在竞争强度超过一定阈值时，及时得到序列化调度。
1.2 高冲突率下的序列化控制
在事务存储系统中，每个事务都会分配一个竞争管理器实例，由竞争管理器执行现有的竞争管理策略处理冲突并负责检测和维护事务当前的ECI数据。系统在高冲突率情况下的序列化控制过程如图1所示。当有事务检测到ECI超出限定时，其CM实例就会通知调度器（Scheduler）将该事务加入到事务队列中，序列化后的事务串行执行，既避免了彼此之间再次冲突的可能，又方便后续事务（如图1中的虚线方块所示）更快地投入执行，最大限度地发挥系统的并行处理能力。在图1中有3个重要时间点，在TimeLine1时刻，系统存在大量事务多次放弃，难以成功提交，如果不采取任何措施，ECI较高的事务（用实线深色的正方形表示）之间很可能会进一步产生冲突。这时冲突中的一方无论是放弃或是等待，都难以保证对方的顺利提交，更不用说防止饥饿和活锁的产生。在TimeLine2时刻，CM实例在调度器的帮助下进行了序列化处理，有效避免了系统性能的降低。在多个竞争管理器同时访问调度器的情况下，可以采用临界区对访问进行同步，但是由于调度器本身就是以阻塞的方式工作，此处引入临界区并不会影响其它事务的并行。在TimeLine3时刻，系统完成了高竞争强度事务的序列化任务，线程可以调用更多的事务执行，同时队列中的事务串行执行，节省了CPU的计算能力。本文的第3节会介绍CM如何为序列化后事务提供演进保证，使系统至少具有不低于采用粗粒度的全局锁机制时的性能。
2 事务序列化后的演进保证
虽然事务在经过序列化后，与其它事务发生冲突的概率大大降低，但冲突的可能性依然存在，如果序列化后的事务在冲突中决定放弃自身就不得不重新序列化，反而浪源于：大学论文格式范文www.udooo.com
费了之前进行序列化操作的额外开销。针对这一情况，本文加强了事务在序列化后的演进保证（progress guarantee），即通过CM的支持，保证序列化事务在发生冲突时不会放弃直到成功提交。检测如有两个事务TA和TB，TA是经序列化处理后的事务，TB是正常执行的事务，为保证事务TA可以不受到TB的干扰，需要应对两种情况：①TA发现了与TB的冲突，即TA是冲突主动方；②TB发现了与TA的冲突，即TB是冲突的主动方。对于第一种情况，只需要将TA切换为Aggressive策略即可保证TA的继续执行；对于第二种情况，需要在共享对象版本信息或是TA的事务描述符（Transaction Descriptor）结构中加入特定的标记位，这样，TB可以从共享对象的版本记录或是TA的事务描述符中找到信息，主动放弃自身。
图2描述了整个事务存储系统在序列化调节机制下的工作情况。从图中可以看出，序列化调度器将整个系统分成了两块区域。区域1中的事务ECI超过了阈值，在调度器和事务队列的控制下串行执行，而通过系统提供演进保证，这些事务在序列化后都可以成功提交。区域2中事务的ECI较低，说明其产生共享资源访问冲突的概率也较低，可以应用CM策略有效提高事务的并发度。由于区域1的序列化调节作用，系统在高冲突率的环境下可以保持不低于采用粗粒度的全局锁机制时的性能。
3 实验结果
RSTM是一个开源的软件事务研究平台，提供了可配置的竞争管理策略。本文对RSTM现有的CM策略引入了序列化调节机制：增加了事务队列Transaction Queue；ECI信息和序列事务标记都保存在相应事务的Transaction Descriptor结构中；借助pthread库提供的条件变量，事务可以通过一个全局锁互斥访问Scheduler。测试环境使用Intel Xeon 3.0 GHz CPU，内存2GB，操作系统为Linux。测试程序创建并启动一组线程，分别选用红黑树（Red Black Tree）和链表（Linked List）这两种基准数据进行10 000次随机查找、插入和删除3种操作。选取原始的Greedy策略和经过序列化调整改进的GreedySA策略分别执行10次，取平均值作为实验结果进行比较。图3和图4分别是在红黑树和链表下的测试结果。
图3中，在线程数量较少的情况下，事务并发度不高，访问共享资源时发生冲突的概率很低，序列化调节的开销在一定程度上降低了系统的吞吐量。然而随着线程数的增加，未经调节的Greedy策略性能出现了明显下降，这主要是由于随着并发度的提高，冲突率也会显著升高，大量事务因资源竞争而放弃。对于改进的GreedySA策略来说，在线程数增加时，竞争强度较高的事务会串行执行，在保留一定程度并发性的基础上避免了一些事务无谓的频繁放弃，有效抑制了系统性能的降低。在图4中，由于链表的结构特性，并发度的提高对性能的改善作用十分有限，然而通过观察可以发现，在序列化调节支持下的竞争管理策略和现有的竞争管理策略相比，在冲突率高的情况下的表现更加稳定。
4 结语
在事务存储系统中，竞争管理策略的重要任务是预防饥饿和活锁并最大程度地降低放弃事务的数量。竞争管理策略与集中管理方式相比，由于其分布式的特征，可以有效降低事务间的耦合度，减少同步操作的数量和开销。在序列化调节机制下，竞争管理器与调度器在功能上相互配合，最大程度地发挥彼此的优势。竞争管理器不仅负责探索事务的并发度，而且可以保护事务在序列化后顺利提交。调度器把频繁放弃和发生冲突的事务收集起来串行执行，为竞争管理器减轻了冲突处理的压力。实验数据表明，带有序列化调节机制的冲突管理策略具有更好的表现，特别是在并发度高的情况下有效配置了事务的执行方式，避免了系统性能的退化。
参考文献：
＼[1＼] SUTTER H AND LARUS J. Software and the concurrency revolution＼[J＼]. Queue，2005 （7）.
＼[2＼] GAREY M R， GRAHAMS R L. Bounds for multiprocessor scheduling with resource constraints＼[J＼]. SIAM Journal on Computing，1975（4）.＼[3＼] 彭林， 谢伦国， 张小强.事务存储系统＼[J＼].计算机研究与发展，2009（8）.
＼[4＼] HERLIHY M， LUCHANGCO V， MOIR M， et al. Software transactional memory for dynamicsized data structures＼[C＼]. In Proc of the 21st Annual Symp on Principles of Distributed Computing（PODC），2003.
＼[5＼] GUERRAOUI R， HERLIHY M， AND POCHON B. Toward atheory of transactional contention managers＼[C＼]. In Proceedings of the twentyfourth annual ACM symposium on Principles of Distributed Computing，2005.
＼[6＼] GUERRAOUI R， HERLIHY M， AND POCHON B. Polymorphic contention management＼[C＼]. In Proceedings of the 19th International Symposium on Distributed Computing，2005.
＼[7＼] SCHERERⅢ WILLIAM N， AND SCOTT MICHAEL L. Advanced contention management in dynamic software transactional memory＼[C＼]. In Proceedings of the 24th annual ACM symposium on Principles of Distributed Computing （PODC），2005.
＼[8＼] SHRIRAMAN A， SPEAR MF， HOSSAIN H， MARATHE V J， et al. An integrated hardwaresoftware approach to flexible transactional memory＼[C＼]. In Proceedings of the 34th annual international symposium on Computer architecture，2007.
＼[9＼] YOO R M， LEE H S. Adaptive transaction scheduling for transactional memory systems＼[C＼]. In Proceedings of the 20th annual symposium on Paralleli in algorithms and architectures，2008.
＼[10＼] SPEAR M F， MARATHE V J， SCHERERⅢ
源于：毕业设计论文总结www.udooo.com
W N， et al. Conflict detection and validation strategies for software transactional memory＼[J＼]. Distributed Computing，2006（4）.（责任编辑：孙 娟）