软件事务存储系统设计选择

1、软件事务存储系统设计选择摘要：多核微处理器的发展为线程级并行编程带来了新的机遇和挑战。面对传统锁机制应用对并行开发带来的诸多困难，借鉴数据库中事务的概念提出事务存储技术。软件事务存储系统的性能受设计上各方面因素的影响，比如基于字或基于对象、基于锁或无阻塞、直写或回写、早检测或晚检测。对此进行了论述。关键词：软件事务存储；设计选择；数据组织方式；更新控制方式0引言多核微处理器的发展为线程级并行编程带来新的机遇和挑战。新的摩尔定律指出，在基本不变的主频下，单个芯片上的处理器核的数目每一代(约两年)增加一倍。当前，程序性能的提高只能依靠并行，并行算法和并行编程是今后几十年计算机科学和软件界必须突破的

2、科学问题和关键技术。并行程序设计将越来越大众化，对提高并行程序设计的产出率(Productivity)的要求越来越高，提供易用高效的并行编程手段显得尤为关键。传统的用于线程间同步的锁机制编程困难，可扩展性差，并不适于未经专业培训的一般程序员使用：粗粒度锁由于一次性地对本地大量数据进行保护，即使两个线程之间理论上并不存在干扰，也可能因粗粒度锁而产生冲突，因此粗粒度锁不适于拓展，性能较低；细粒度锁虽然性能高，但在实现上很难保证其准确性及避免死锁。同时，锁技术容易致使线程脆弱，即线程更加容易失败或延迟。比如，持有锁的线程会阻塞其它线程。研究人员为解决以上问题，借鉴数据库中的事务概念提出事务存储(Tr

3、ansactionalMemory，TM)技术，希望获得一种像粗粒度一样容易使用、性能接近细粒度锁的同步手段。事务存储技术在事务存储技术中，线程事务采用原子执行单元来替代锁。各线程事务以原子的方式执行，把维持事务特性的工作交给编译器、运行时库或硬件完成，进一步的性能调优可以在系统层完成。比如，如下计算直方图的代码块：atomichistarrayij+；程序员可将其看作是一个临界区，TM实现来决定如何将该临界区与其它线程隔离运行。根据事务存储系统实现方法的不同，目前的事务存储系统的研究主要有3个方向：基于硬件实现的硬件事务存储系统(HTM，HardwareTransactionMemory),

4、女口Stanford大学的TCC;基于运行时库实现的软件事务存储系统(STM,SoftwareTransactionMemory)，如Rochester大学的RSTM；结合软硬件实现的混合事务存储系统(HybridTransactionMemory)，女口Rajwar等提出的VTM。HTM系统主要由硬件实现，速度最快，并行粒度是cache行或内存字；STM以计算机语言实现，并行力度是对象或内存字，速度较慢，但比较灵活；HyTM由适当的软件或硬件实现，性能介于HTM与STM之间。本文主要研究软件事务存储技术。事务存储实现方式为了实现事务的特性，一般来说，软件事务存储的实现必须具备三大功能。冲突检

5、测。事务在执行过程中，要根据具体的情况适时地检测冲突，只有在无冲突发生的情况下，事务才能提交。一致性校验。事务在执行过程中始终要保持共享对象的一致性状态。在共享对象不一致的状态下，计算可能会产生无法控制的结果，如死循环或除零错。所以，即使执行过程中没有检测到冲突，事务还是可能进行一致性校验。冲突消解。当冲突发生后，需要采取一定的措施来消解冲突。当前的各种STM通过不同手段来实现上述三大功能。早检测与晚检测对于冲突的检测，可以分为早检测(earlydetect)和晚检测(lazydetect)。早检测即每当事务读或写时，都会去检测是否有冲突事务存在，以此来保持共享对象的一致性。因此，早检测策略需

6、要事务的读集(readse)及写集(writeset)对所有的事务都是可见的，我们将这种设计称之为可见读(visibleread)设计。Harris于2003年提出不可见读，与之相应的是晚检测策略，只有在事务提交时才依靠对读集的检测来确定是否存在冲突事务。一般来说，早检测能比晚检测更加及时地发现冲突，从而避免冲突事务执行不必要的操作，且检测手段的实现相对简单，但早检测的执行开销明显大于晚检测。基于锁与无阻塞鉴于前面提到的锁机制的各种缺陷，早期的STM研究将无阻塞(nonblocking)作为实现目标。无阻塞算法能够保证进程不会因不活跃的线程而阻塞，从而避免优先级倒置或线程死锁。其中，Herli

7、hy等人提出的无干扰同步算法(obstructionfreesynchronization)是比较典型的无阻塞算法。然而，无阻塞算法无论在其结构还是运行时的CAS(compareandswap操作都比较复杂，相应的无阻塞的STM性能远远低于良好实现的锁机制。为应对这种情况，基于锁的(lockbased)STM应运而生。基于锁的STM采用互斥版本锁(versionedmutualexclusior)技术，如图1。该技术支持普通的互斥语义且提供对版本号(versionnumber)的访问，通过版本号来统计加锁和解锁的次数。当事务第一次读取某对象时，记录其版本号。事务提交之前必须保证该版本号未改变，

8、即不存在其它事务对该对象进行修改。互斥版本锁技术比较灵活，可以支持大多数的STM实现，既可以在事务执行过程中对其访问的共享对象加锁，比如BartokSTM，也可以只在提交时加锁。基于字与基于对象软件事务存储系统根据其数据组织方式可分为基于对象(objectbased)即面向对象的实现和基于字(wordbasec)即面向内存单元的实现。面向对象的实现由Herlihy提出。事务通过共享对象的封装容器(Locator)来访问对象，如图2,共享对象在封装容器中被分为两个部分：新版本(NewVersion)和旧版本(OldVersions)，事务访问共享对象时根据操作类型判断获得哪个版本,并在提交或放弃

9、时更新两个版本对象中的内容。典型的基于字的STM实现有DSTM,OSTM,ASTM等。基于字的STM直接对内存中的数据进行访问,且使用独立的结构来维持其自身元数据(metadata，女口BartokSTM通过将字地址映射至事务字(TMW，transactinalmetadata中来管理数据。直写与回写现有的STM系统基本分为两种控制更新方式：直写(writethrough)和回写(writeback)。直写方式允许事务直接将修改内容写到内存之中，并将更新信息保存至撤销日志(undolog)当中。当事务遇到冲突而被迫放弃时，依据撤销日志将内存内容恢复至更新之前。采用回写方式的STM系统的每个事务

10、各自维持一个缓存，事务将要更新的内容写入到缓存之中，事务提交时，再将缓存内容写入内存。结语相对于锁机制，一方面TM技术为程序员提供了更高层次的抽象，使程序员不再纠结于同步机制的算法细节；另一方面，TM技术在程序的拓展性与实现之间提供了一个较好的权重。虽然一个良好设计的锁也具有良好的拓展性，但设计起来具有相当的技术难度。另外，TM技术能够很好地避免死锁。虽然可能会出现导致活锁的现象，即相冲突的进程不断地抢占或放弃共享资源，致使每个进程都无法向前，但这种情况明显比死锁要好解决得多。如何在保证性能的情况下很好地避免活锁，是TM技术目前的一个研究重点。参考文献：LANCEHAMMOND，BRIAND，

11、CARLSTROM，etal.Programmingwithtransactionalcoherenceandconsistency（tcc）C.InProceedingsofthe1thinternationalconferenceonArchitecturalsupportforprogramminglanguageandoperatingsystem，sASPLOSXI，pages113，NewYork，NY，USA，2004.ACM.ROCHER.RstmrochestersoftwaretransactionalmemoryEB/OL.http：RAVIRAJWAR，MAURICEH

12、ERLIHY，KONRADLAI.VirtualizingtransactionalmemoryC.InProceedingsofthe32ndannualinternaltionalsymposiumonComputerArchitecture，ISCA5，pages494505，Washington，DC，USA，2005.IEEEComputerSociety.MHERLIHYV，LUCHANGCO，MMOIR.SoftwaretransactionalmemoryfordynamicsizeddatastructuresC.PODC03：ProceedingsoftheTwentysecondAnnualSymposiumonPrinciplesofDistributedComputing.ACM，NewYork，NY，USA，2003.MHERLIHY，VLUCHANGCO，MMOIR.Obstructionfreesynchronization：doubleendedqueuesasanexampleC.Proc.23rdIEEEIntlConf.DistributedComputingSystems（ICDCS03），IEEECSPress，2003.（PLDI06），ACMPress，2006.KFRASER.Practicallockfreedom，docto