（计算机应用技术专业论文）嵌套事务内存研究.pdf

中文摘要 用户应用程序中的并发性正在逐渐增长，现代计算机包含了单核多线程和单 芯片多核的功能。如何有效地在多核处理器体系结构下开发出高性能、可移植的 并行程序，降低并行程序的开发难度，提高并行程序的设计开发效率成为并行计 算领域的一个关键性问题。传统的用户应用程序使用细粒度锁的互斥方式达到同 步，但是这种方式容易形成死锁和具有不可组合性、优先级反转和护航效应等问 题。非阻塞算法避免了这些限制，且保证线程的延迟或者失败不会阻碍系统整体 上向前执行，但同样难于实现和应用。事务内存技术基于数据库管理系统中成功 的并发处理经验，能够高效地完成内存级并发读写操作。 事务内存系统的核心是冲突检测。本文对国内外在事务内存方面所做的研究 与探索进行了总结与分析，研究了现有的软件和硬件事务内存系统的设计方法和 冲突检测机制，分析了各自的优缺点。在此基础上，本文首创了适用于所有事务 内存系统的冲突检测数学模型。 可组合性是现代软件工程的基础，嵌套事务内存正是事务内存可组合性的表 现。本文通过对传统并行程序设计方法进行分析，并结合事务内存的现有理论提 出了在内存访问层次的嵌套事务内存模型。该模型与硬件无关，定义了平面事务、 闭合事务和开放事务在各种操作下的语义，描述了事务所能见的内存状态、内存 访问冲突、提交与夭折动作。在该模型的基础上，本文深入研究和分析了开放事 务语义，并且提出了适用嵌套事务内存系统的优先级竞争管理算法，将此算法应 用于本系统后可以有效地提高单位时间内事务执行的数目。 在以上工作的基础上，本文使用c + + 编程语言实现了一个嵌套事务内存系统。 该系统具有良好的可扩展性、友好的编程接口，能从真正意义上简化并行程序设 计的开发过程，提高并行程序的开发效率。 关键词：事务内存嵌套事务内存平面事务闭合事务开放事务 a b s t r a c t c o n c u r r e n c yi nu s e ra p p l i c a t i o n s i so nt h er i s e m o d e mc o m p u t e r sc o n t a i n m u l t i p l et h r e a d sp e rc o r ea n dm u l t i p l ec o r e sp e rc h i p h o wt od e v e l o pe f f i c i e n ta n d p o r t a b l ep a r a l l e lp r o g r a m ，d e c r e a s et h ec o m p l e x i t yh a sb e e no n eo ft h ec r u c i a l p r o b l e m si np a r a l l e lc o m p u t i n gf i e l d t r a d i t i o n a lu s e ra p p l i c a t i o n su s ef i n e - g r a i n e d l o c kt os y n c h r o n i z el a r g em u l t i p r o g r a m m e ds y s t e m s u n f o r t u n a t e l y ，f i n e g r a i n e d l o c k i n gi sp r o n et od e a d l o c k , n o n - c o m p o s a b i l i t y ，p r i o r i t yi n v e r s i o na n dc o n v o y i n g n o n b l o c k i n ga l g o r i t h m sa v o i dt h e s el i m i t a t i o n sb ye n s u r i n gt h a tt h ed e l a yo rf a i l u r e o fat h r e a dn e v e rp r e v e n t st h es y s t e ma saw h o l ef r o mm a k i n gf o r w a r dp r o g r e s s b u ti t i ss t i l ld i f f i c u l tt od e s i g na n di m p l e m e n t b a s e do nt h es u c c e s s f u le x p e r i e n c e so f c o n c u r r e n to p e r a t i o n si nd a t a b a s em a n a g e m e n ts y s t e m , t r a n s a c t i o n a lm e m o r y ( t m ) p r o m i s e st od ot h ec o n c u r r e n tr e a d w r i t eo p e r a t i o n sw i t hh i 曲e f f i c i e n c y t h ek e yo ft r a n s a c t i o n a ls y s t e m si st h en e e df o rc o n f l i c tv a l i d a t i o n t h i st h e s i s a n a l y z e st h ec u r r e n tr e s e a r c hs t a t u sa b o u tt m ，i n c l u d i n gd e s i g np a t t e r no fs o f t w a r e a n dh a r d w a r et ma n dc o n f l i c td e t e c t i o nm e c h a n i s m f o u n d e do nt h er e s e a r c h ，w e i n t r o d u c eac o n f l i c tv a l i d a t i o nm o d e la p p l i c a b l et oa l lc a s e sa n da p p l yi ti nt h et m s y s t e m c o m p o s a b i l i t yi s t h eb a s i co fm o d e ms o f t w a r ee n g i n e e r n e s t e dt r a n s a c t i o n a l m e m o r y ( n t m ) r e p r e s e n t st h ec o m p o s a b i l i t yo ft m a f t e rar e s e a r c ho nt h em o d e m t h e o r yo ft m t h i st h e s i so f f e r sar e f e r e n c em o d e lf o rn e s t e dt r a n s a c t i o n sa tt h el e v e l o fm e m o r ya c c e s s e s t h em o d e ld o e sn o tr e l a t et oh a r d w a r e i td e f m e st h es e m a n t i c s f o rb o t hp l a i nn e s t i n g ，c l o s e da n do p e nn e s t i n g ，a n dd e s c r i b e st h em e m o r ys t a t e sa s s e e nb ye a c ht r a n s a c t i o n ，m e m o r ya c c e s sc o n f l i c t s ，c o m m i t sa n da b o r t sa c t i o n s g r o u n d e du p o nt h i sm o d e l ，t h et h e s i sd o e saf u r t h e rr e s e a r c ho no p e nn e s t i n ga n d o f f e r sap r i o r i t yc o n t e n t i o nm a n a g e m e n ta l g o r i t h m i tc a l le f f e c t i v e l yi m p r o v et h e e x e c u t i o nn u m b e ro ft r a n s a c t i o ni nu n i tt i m ea f t e ra p p l y i n gt ot h es y s t e m b a s e do nt h ew o r ka b o v e t h i st h e s i sr e a l i z e st h en t ms y s t e mu s i n gc + + i th a s g o o de x t e n s i b i l i t y a n df r i e n d l ya p i i tc a ns i m p l i f yt h ep r o c e s so fp a r a l l e l p r o g r a m m i n ga n di m p r o v et h ee f f i c i e n c yo fp a r a l l e lp r o g r a md e v e l o p m e n t k e yw o r d s ：t r a n s a c t i o n a lm e m o r y , n e s t e dt r a n s a c t i o n a lm e m o r y , p l a i n n e s t i n g ，c l o s e dn e s t i n g ，o p e nn e s t i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得基盗盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：何田百书 签字日期： 】。口7 年 6 月j 7 日 学位论文版权使用授权书 本学位论文作者完全了解苤壅盘堂有关保留、使用学位论文的规定。 特授权墨注盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：f 可闭伟 签字日期：2 t 7 呷年月i 日 翩签名：( h 傍盯 | 料聃明刨月j 7 日 第一章绪论 1 1 研究背景 第一章绪论 人类对计算能力及性能的要求永无止境。随着各行业计算量增大及计算复杂 度的增加，许多应用在计算能力及计算速度方面不断提出新的要求。1 9 6 5 年， g o r d o n m o o r e 提出摩尔定律“芯片上晶体管的数目大约每过两年就翻一番”。过 去几十年里，半导体工业的发展及其在处理器上的应用，使得处理器主频不断地 提高，因而推动了已有顺序式软件运行速度的稳步提升。虽然摩尔定律现在仍然 有效，但是由于能耗以及散热方面的原因，现在已经不能简单地通过提高时钟频 率来提升处理器的性能，取而代之的方法是在单个芯片上集成多个基于共享内存 的多核处理器( m u l t i c o r e ) 。然而随着i n t e l 、a m d 、m m 等巨头公司多核处理器 的发布上市，在体系结构上异于单核处理器的多核处理器仅对并发应用有益，几 乎绝大多数现存软件并不能从单核到多核的变化中获得速度提升或者性能提高。 现在以及将来，已有的桌面应用不可能比现在运行得更快。实际上，它们的运行 速度会稍慢，因为为了降低高密度多核处理器的电能消耗，新的芯片内核被简化 并运行在更低的时钟速度。多核处理器的出现将对软件至少是主流软件的开发带 来深远影响。计算机的能力无疑越来越强，但程序不再可能从硬件性能提升中免 费获益u j ，除非它们实现了并行。 虽然并行计算机已经有4 0 多年的历史，但是无需修改就能够充分利用多核 处理器的并行应用却非常少。这是因为与串行程序不同，并行程序需要对求解问 题进行分解，分解过程需要复杂的计算与分析，从而加大了并行程序设计的难度。 并发程序还要面临诸如安全性、公平性、同步分析等其它问题，而同时做上下文 相关性和同步分析已经被证明不可企及，因此并行程序设计的复杂性严重制约着 并行应用的普及与推广。并行程序设计只与少数人相关，不像顺序程序设计那样 广为人知，并受到大多数软件开发商的支持，这同时也制约了并行程序的发展。 随着多核处理器市场的不断繁荣，并行化成为了现代程序设计中的关键技 术，并行程序设计是获得更高性能的必需手段。 推进并行编程的发展，必须首先能够解决或者简化并行编程中的几个难点。 在并行程序设计中有以下几个难点制约了其向前发展： 第一，由于存在并发性和不确定性，并行程序设计比串行程序设计困难有着 第一章绪论 心理学上的原因。心理学研究表明，人把注意力分散开来处理多个任务的能力是 有限的。 第二，分析并行程序比顺序程序更加困难。在串行程序分析中只需要考虑上 下文，而在并行程序分析中还需要考虑同步。即使最细心的程序员，也会觉得分 析并发程序比顺序化代码更加难以把握。已经证明，即使只有两个线程，将上下 文和同步结合起来分析是一个不可判定问题。 第三，在程序设计模型、程序设计语言、程序设计工具等方面，并行程序设 计落后于顺序程序设计，并行程序设计只是少数的程序员懂得如何编写。现在， 能用多种方式实现并行，但每种方式仅仅适用于特定类型程序。大多数时候，没 有细致入微的设计与分析，极难提前知道哪种模型适合给定的待求解问题。如果 无法清楚地确定给出的问题能套用哪种模型，往往就必须将多个模型杂合起来灵 活运用。当前有两种并行程序设计模型( p a r a l l e lp r o g r a m m i n gm o d e l s ) ：数据并 行程序设计模型和任务并行程序设计模型。数据并行程序设计模型不通用，该模 型的各个线程间需要共享数据，因为作业变化多端和需要冲突检测，保证其正确 和高效的复杂性也大为增加；任务并行程序设计模型编程困难，因为并行任务间 存在性能平衡的问题，并行程序的性能由并行的各个任务的性能共同决定，目前 任务负载平衡是并行程序设计中一个难题【2 】【3 】，这需要充分考虑各并行处理器的 执行效率以及并行任务间的通信性能。并行系统无法有效做到这种性能上的平 衡，只能依靠程序设计人员通过并行程序的合理设计实现，而该设计过程十分复 杂。 传统并行程序设计中的状态共享是基于锁实现的，但是由于锁不具有可组合 性。不能保证由两部分以锁为基础且能正确运行的代码合并后得到的程序依然正 确。而现代软件工程开发的基础恰恰是将小程序库合并为更大程序的组装能力； 因此，无法做到不考察组件的具体实现，就能在它们基础上组装大软件，这是个 大问题。造成组装失败的祸首是死锁。 因为锁的一些先天性的缺陷以及在i n t e l 、a m d 、i b m 等跨国公司的大力推 动下，多核处理器体系结构已经日渐成熟和完善，更快、更好、更方便地设计和 开发并行程序的要求越来越迫切，通过对多核处理器内存模式的深入研究，建立 可共享但无显式锁的数据结构是可能的，即锁的替代物：事务内存。 事务内存将数据库中事务模式的核心思想移植到编程语言里来。数据库系统 能够有效地适应各种并行环境，其原因是数据库只能通过事务来访问：在数据库 系统中，通过将一系列操作抽象为事务，避免了程序员考虑复杂的同步问题。同 样在事务内存中，程序员将自己的程序编写为一个个具有确定原子性的块，每一 个原子块是一系列操作的抽象，作为一个事务块存在，该事务块的执行结果只有 第一章绪论 两种，一是全部提交，二是全部夭折，二者只能是其一。这样引进了事务的概念， 简化了多核处理器平台下的并行编程。 1 2 国内外研究现状 1 9 7 7 年，l o m e t 【4 】提出了在程序设计语言中引入类似数据库事务的抽象的想 法，他当时提出“原子动作”( a t o m i ca c t i o n s ) 即后来的事务概念，使用原子动 作来实现多进程的同步，由于当时的进程结构和管理机制并没有给程序员提供原 子动作的能力，l o m e t 在文中提到了一种简单的实现方式就是在多进程系统执行 操作时使得中断不可用，即，原子动作一直保持着对系统的控制直到它完成，在 这期间中断不允许。如果这样的话，实际上在动作执行期间，它就占用了所有的 系统资源，不利于执行的最大并行化，不利于提高并行化后的运行效率。 免锁( l o c k f r e e ) 算法是事务内存重要的基础，它们的研究几乎是同步进行 的。早在1 9 7 2 年，e a s t o n 5 就提出了在并行编程中对共享内存的访问和同步应该 避免使用互斥的方法以提高效率和性能，随后在1 9 7 7 年，l a m p o r t 6 】给出第一个 免锁算法，他实现了对同一个共享变量多读( m u l t i r e a d e r s ) 和单写( s i n g l e w r i t e r ) 。 l a m p o r tm - r - 作直接引起了更多人在免锁算法领域的研究阴【8 】【9 1 。这是因为免锁数 据结构比使用传统锁同步的数据结构有着更多的优点，尤其是在高度并行系统 中，免锁数据结构能够避免和传统使用锁同步技术相关的公共问题： 优先级反转( p r i o r i t yi n v e r s i o n ) ，当一个低优先级的线程占用了一个锁之 后，需要同一个锁的高优先级线程就只能等待。 护航效应( c o n v o y i n g ) ，当一个线程拥有一个锁而被切换出去时其他的 线程如果需要同一个锁的话都不能运行下去，其他线程都围着拥有锁的 线程团团转。 死锁( d e a d l o c k ) ，锁的拥有和依赖关系形成一个环。 在图1 1 优先级反转示意图中，系统中有3 个任务，分别为t a s k l 、t a s k 2 和 t a s k 3 。t a s k l 的优先级高于t a s k 2 ，而t a s k 2 的优先级高于t a s k 3 。恰在此时t a s k l 和t a s k 2 因某种原因被阻塞，这时候系统调度t a s k 3 执行。t a s k 3 执行一段时间后， t a s k l 被唤醒。由于采取的是p b p ( p r i o r i t yb a s e dp r e e m p t i v e ) 的调度策略，因此 t a s k l 抢占t a s k 3 的c p u ，从而t a s k l 获得执行。t a s k l 执行一段时间后要进入临 界区，但此时t a s k 3 占有此临界资源的信号量。因此t a s k l 被阻塞，处于等待状 态，等待t a s k 3 释放此信号量。经过这么一段时间后，t a s k 2 此时此刻处于就绪状 态。因此系统调度t a s k 2 执行。如果t a s k 3 在t a s k 2 的执行期间一直没有能够被调 度执行的话，那t a s k l 和t a s k 3 将一直等到t a s k 2 执行完后才能执行，t a s k l 更要 第一章绪论 等到t a s k 3 释放它所把持的信号量才能执行；而这段时间完全有可能超出t a s k l 的d e a d l i n e ，使得t a s k l 崩溃。当系统看到有高优先级的任务崩溃时候，系统认 为此时有重大事故发生，为了挽救系统，系统可能被自动复位。从上面的分析可 以看到，导致系统崩溃的原因是由于优先级高的任务t a s k l 要获取被低优先级任 务t a s k 3 占有的临界资源而被t a s k 3 阻塞，而具有中优先级的任务t a s k 2 抢占t a s k 3 的c p u ，从而导致t a s k 2 先于t a s k l 执行。这时候系统便出现了优先级反转的情况。 护航或者死锁效应同样也会导致系统的崩溃。 ! p r i o r i t yi n v e r s i o n ： 卜卜1 t 0t 1t 2t 3t 4t 5 t ：任务就绪1 | ：任务完成 图1 1 优先级反转 在l o m e t 之后的近二十年间，不断有人研究事务内存，但是进展缓慢，直到 1 9 9 3 年，h e r l i h y 和m o s s 1 0 1 给出了一个硬件事务内存系统。首先它要求c p u 体 系结构能够支持“免锁数据结构，这样共享数据就不需要互斥，如果一个进程 的操作被中断，也不会阻止其他的进程操作该对象。在高度并行系统中，“免锁” 数据结构避免和传统锁相关的问题，即优先级反转、护航效应、死锁等问题。硬 件事务内存，一种新的多处理器体系结构，它使用了免锁算法保持同步，效率也 同样达到了和使用传统互斥技术的程度，并且更加容易用。事务内存允许程序员 自定义读修改写( r e a d m o d i f y w r i t e ) 操作，通过对高速缓存一致性协议直接扩 展而实现，模拟结果显示事务内存和已知最好锁同步技术在性能方面不相上下。 这种硬件事务内存需要硬件上的特殊支持，并且不能把现有的主要软件直接应用 到这种处理器体系结构上，这使得它的推广也更加困难。 阻碍多核处理器被广泛应用的主要原因就是程序员极难在现有编程模型下 、，一 m 一 ，l 一 2 一 k s 一 第一章绪论 设计出高度并发的程序和数据结构。在现代多核处理器体系结构中，不可预测的 延时已经成为不断增长的严重问题，使用传统技术，如临界区域或者锁技术，来 实现并发对象的同步控制是不合适的，因为它们限制了并行性，增加了内存间的 竞争。高度并发编程的关键就是要减少多核处理器所使用锁的数目和临界区域的 数目和大小，即使用非阻塞算法实现。选择同步操作的灵活性可以极大地简化设 计高度并发程序的任务。如，m a s s a l i n 和p u 介绍了一种使用双字的非阻塞数据 结构【1 1 】；a n d e r s o n 使用了一种特殊的接合( s p l i c e ) 操作0 2 ，即将 f e t c h & c o m p l e m e n t 和f e t c h & i n c 联合；i s r a e l i 和r a p p o p o r t 介绍了一种使用三字 ( t h r e e w o r d ) c o m p a r e & s w a p 的堆数据结构【”】。然而，不幸的是，上面提到的 几种实现原语的方法在现有的c p u 体系结构中不可实现，因为它们不通用，所 以很可能在将来的c p u 体系结构中也不被支持。 1 9 9 5 年，s h a v i t 和t o u i t o u 给出了一个软件事务内存系统【l4 1 ，该文中提出了 软件事务内存正确性的基本要求是可线性化：即每一个并发操作历史等价于某种 合法的顺序操作历史，它在实时顺序上合并后操作历史是一致的。即首次提出了 事务内存正确性的条件，并给出了正确性的逻辑证明。 在现阶段，基于软件事务内存的算法一般情况下要比非阻塞( n o n - b l o c k i n g ) 算法和基于锁的细粒度( f r e e g r a i n e d ) 算法慢一些，但同时它们就像使用粗粒度 锁( c o a r s e g r a i n ) 一样简单：只要简单地在需要原子操作的代码加上括号说明即 可。事实上，软件事务内存系统允许将正确的顺序代码转化成高度并发的正确的 非阻塞的代码。 随后事务内存仍然处于不断研究中，后来有人提出并实现了d s t m ( d y n a m i c s o f t w a r et r a n s a c t i o n a lm e m o r y ) 1 5 】和s x m ( c 撑s o f t ：w a r et r a n s a c t i o n a lm e m o r y ) ， 推进了软件事务内存的发展，但是这几个系统有一个共同的特点：在内存回收方 面还是依靠编程语言所提供的垃圾回收功能。这样就会使系统存在一定的缺陷， 使得内存回收不能够由系统来控制，对系统而言存在一定的不确定性。 自从h e r l i h y 和m o s s 1 0 】首次提出“事务内存”来表示共享内存的事务访问后， 一些研究人员已经开发和实现了一些硬件和软件事务内存系统【1 6 】【1 7 】【18 1 ，这些系 统或者不支持嵌套事务内存或者仅仅简化嵌套事务成为单层次的事务，但是嵌套 事务在事务内存系统的可组合性中有着非常重要的地位，因此能够支持嵌套事务 的事务内存系统将是一个非常完善的系统。同时也因为嵌套事务在事务内存中占 有重要的地位： ( 一) 事务内存系统库包含原子操作，并且用户代码库或者其他代码库需 要在更大的原子操作内将这些各自的原子操作聚合到一起以形成功能更强大的 原子操作。这样，系统必须能够组合那些使用这些原子操作的代码。这也是事务 第一章绪论 内存系统必须提供的功能。 ( 二) 如果事务需要执行回滚操作的时候，单块巨大的原子操作增加了巨 大的工作量，闭合事务至少能够部分程度上解决了该问题。它允许工作量的部分 被重试，并且可能失败，而不必放弃事务已经完成的部分。同样它也可以被实现 用来运行程序能够对部分工作量夭折的相应控制，例如可以尝试用不同的工作方 式来完成工作。( 这个在分布式系统中非常有用：如果在资源无法满足或者系统 太忙而没有响应的时候，它能够重新定向到一个合适的资源上。) 相似地，由于代码库中的嵌套事务失败而遭受到的性能问题，因此对于不透 明的代码库的客户端来说，在这些性能瓶颈处需要以某种方式来编程。 总之，聚合子事务成为单块巨大的事务是为了能够对嵌套事务内存模型执行 的正确的响应和支持，子事务失败的性能和功能暗示信息可能对程序员来讲非常 重要，他们期望能够使用子事务编程和对事务的失败做出正确的响应。 ( 三) 单块巨大的事务限制了并发性。和锁相比，在共享对象上使用事务 操作在以下两种方式上提高了并发性。一是事务可以并发无冲突地处理如果它们 访问不同的数据，例如相同对象的不同数据域或者不同的对象。另一个是事务区 分读和写，并且并发读不会冲突。锁要求互斥访问即使在只有读的情况下。嵌套 事务的目的就是进一步提高并发性。 基于以上因素，本文研究了基于c + + 语言的支持嵌套事务的软件事务内存 s t m ，并且手动进行内存回收，对系统运行中释放的内存进行控制，减少内存分 配的次数从而提高了效率。 1 3 本文的主要研究工作和创新 并行程序设计是一个比较复杂的过程，传统的并行程序设计往往使用阻塞的 方式来实现，如使用旋转锁( s p i n l o c k ) 、信号量、临界区域等等，但是往往易于 形成死锁、优先级反转、护航效应，这样使得现有并行程序设计模型的推广更加 困难。简化并行程序设计的事务内存系统设计是一项艰难的工作，它的目标是研 究目前现有的并行程序设计方法，并且采用一种不同于现有并行程序设计方法的 新模型，使得可以大大简化并行程序设计和更好地利用现有的多核c p u 体系结 构从而提高性能。在此基础上做一些理论性的研究工作和探索性的实践工作，设 计并开发出嵌套事务内存系统。在阅读了大量论文之后，本文对目前国内外事务 内存理论和系统进行了深入细致的研究与分析，并对嵌套事务内存的理论和分类 进行了完善和细化，在该理论的基础上提出新的开放事务内存语义方案，并进行 了具体的实现，基于c + + 语言的嵌套事务内存。具体包括以下工作： 第一章绪论 对目前国内外软件事务内存、硬件事务内存和混合事务内存进行了研究与 分析，就现有的研究状况、进展和不同领域进行了综述。 深入研究了软件事务内存的实现机制和原理并进行了分析与评价。 - 有别于传统加锁从而实现阻塞同步的方法，本文采用了“非阻塞”方法实 现了底层同步。 _ 对现有嵌套事务内存的理论的研究和分析。 本论文设计和实现了嵌套事务内存系统，在关于嵌套事务内存的理论和应用 上有如下创新性研究成果： 首创了事务冲突检测数学模型。 _ 完善和定义了新的开放事务内存模型。 _ 设计和实现了基于c + 十语言的支持嵌套事务模型的事务内存系统。 - 在x 8 6 、p o w e r p c 、s p a r c 平台上设计和实现了比较并交换( c o m p a r ea n d s w a p ) 和测试并设置( t e s ta n ds e t ) 同步原语。 1 4 本文的内容和结构 本文通过研究国内外非阻塞算法和事务内存的理论和方法，提出了简化现有 并行程序设计方法的基于c + + 语言的事务内存模型和系统。在此模型的指导下提 出了一个支持三种嵌套事务( 平面事务、闭合事务、开放事务) 的嵌套事务内存 系统设计方案，并就该方案的具体实现技术进行了详细阐述。主要内容如下： 第二章介绍了事务内存( t m n s a c t i o n a lm e m o r y ) 概念和理论，就该理论 的概念、起源、意义以及事务内存系统中的常见问题做了系统的描述。 第三章主要针对嵌套事务内存模型的语义理论进行了阐述，并且定义了 嵌套事务内存模型的形式化语义，对三种嵌套事务内存模型的夭折和提交动作分 别进行了介绍和形式化语义描述，完善了开放事务的语义，并且进一步深入探讨 了开放事务语义。 第四章 介绍了嵌套事务内存系统的设计，对设计思想、方法、主要数据 结构进行了详细的阐述。针对不同层次的数据操作进行了不同的数据结构设计， 使之能够适应三种嵌套事务内存模型。并且对冲突检测数学模型和适用于嵌套事 务内存系统的优先级算法进行了论述。 第五章实现了嵌套事务内存系统，介绍了主要的编程接口和不同体系结 构平台的非阻塞( n o n b l o c k i n g ) 同步原语，根据各种平台特有的指令和功能， 分别介绍和实现了它们在x 8 6 、s p 根c 、p o w e r p c 等平台下的功能 第六章 全文工作总结及对未来工作的展望。 第二章事务内存 第二章事务内存 事务内存( t r a n s a c t i o n a lm e m o r y ) 是走出当前并行编程困境的重要途径。多 核处理器体系结构的快速发展以及它与事务内存系统的完美结合，推动了事务内 存系统的完善和前进。 2 1 事务内存与数据库事务 多核处理器体系结构的出现，是现有主流软件开发的转折点。开发出功能完 善的并行软件非常困难，而数据库在处理并行读写方面有着完美的经验：即事务 操作。事务内存概念最早起源于数据库的事务操作概念，但是它们又有许多不同 的地方。 一 2 1 1 数据库事务 数据库系统之所以能够有效地适应各种并行环境，其原因是数据库只能通过 事务进行访问，事务是现代数据库理论中的核心概念之一。如果一组处理步骤或 者全部发生或者一步也不执行，称这些处理步骤为一个事务。当所有的步骤像一 个操作一样被完整地执行，称该事务被提交。由于其中的一些代码执行失败，导 致没有步骤被提交，则事务必须回滚( 回到最初的系统状态) 。数据库的事务操 作具有以下四个特性： 原子性( a t o m i c i t y ) - 事务是数据库的逻辑工作单位，所有的操作要么都 做，要么都不做 一致性( c o n s i s t e n c y ) ：事务执行的结果必须是使数据库从一个一致状态变 成另一个一致状态 隔离性( i s o l a t i o n ) ：一个事务的执行不能被其他事务干扰，即并发执行的 各个事务之间不能互相干扰 持久性( d u r a b i l i t y ) ：一个事务一旦提交，对数据库中的数据的改变是永 久性的 在数据库系统中，通过将一系列操作抽象为事务，避免了程序员考虑复杂的 同步问题。现在的数据库产品在事务方面都支持的非常好，并且简单易用。例如 在j a v a 编程语言中，一般情况下，j 2 e e 应用服务器支持事务处理的接口主要有： 第二章事务内存 j a v a 事务编程接口( 胜) 、b e a n 管理持久性( b m p ) 、容器管理持久性( c m p ) 。 j a v a 事务编程接口是j 2 e e 事务服务的主要解决方案。本质上，它是描述事务接 口的j 2 e e 模型的一部分，如程序员可以直接使u s e r t r a n s a c t i o n 接口或者通过 j 2 e e 容器调用该接口以确保业务逻辑能够可靠地运行。j 2 e e 对这些的封装技术 极大地简化了数据库中事务操作，简化了事务编程。 2 1 2 事务内存 事务内存是一个内存操作的序列，它要么完全执行( 提交) ，要么不产生任 何影响( 夭折) 。事务内存同样也是将内存共享变量的访问封装为事务操作，使 得内存的访问更易操作和方便移植。事务内存引入了数据库事务的三大特性： 原子性：是指在事务内存系统中标记为事务的操作序列具有原子性，所 有标记为事务的操作要么在提交时( o nc o m m i t ) 所有内存操作全部生效， 要么夭折时( o na b o r t ) 所有操作都不执行 一致性：不同事务间的数据必须保持一致 隔离性：直到事务完成后，内存存储操作才可见；不会对其他事务有并 发冲突访问 在事务内存语言构造方面，一般采用如下的形式： l o c k ( l ) ；x + + ；u n l o c k ( l ) ；一 a t o m i c x + + ；) h p c s ( h i g h p e r f o r m a n c ec o m p u t i n gs y s t e m s ) 语言( 如f o r t r e s s ，x10 等) 都提供a t o m i c 来替代锁，现在的研究逐步扩展到通用的编程语言如j a v a 、c 撑等。 在编程语言层次上，需要扩展现有的编程语言以适应事务内存，同样也需要优化 和改进现有的编译器，使之更好地生成和优化事务内存的代码，从而提高性能。 现代软件工程提倡模块化的软件系统，它具有易用、易扩展、易维护等优点。 事务内存同样具有模块化的功能，它如同粗粒度锁一样易用，同时还具有细粒度 锁一样的性能，它是安全且可扩展的软件模块。 例如，在银行业务系统中，每一个帐户都与一个帐户名相关，对账户的操作 必须是线程安全的，而一般的串行程序编程模型已经无法满足这种要求，必须使 用并行编程的方法。传统并行编程对此的解决方法是使用锁来保证线程安全，如 对账户进行存款业务操作的主要功能代码如下所示： v o i dd e p o s i t ( s t r i n gn a m e ，i n ta m o u n t ) s y n c h r o n i z e d ( a c c o u n t s ) i n tb a l a n c e = a c c o u n t s g e t ( n a m e ) ；g e tt h ec u r r e n tb a l a n c e b a l a n c e + = - a m o u n t ； i n c r e m e n ti t a c c o u n t s p u t ( n a m e ，b a l a n c e ) ； s e tt h en e wb a l a n c e 第二章事务内存 但是锁却不可扩展，并且使用锁的时候必须要求程序员能够非常熟悉代码， 否则容易形成死锁。使用锁不具备模块化的编程思想，不利于移植，并且由于锁 的不可组合性，这些都给并行编程带来了非常大的困难。如果使用事务内存的编 程方式，不仅可以保证线程安全，并且易扩展和高性能。同样的银行账户存款程 序使用事务内存编程后示例如下： v o i dd e p o s i t ( s t r i n gn a m e ，i n ta m o u n t ) a t o m i c i n tb a l a n c e = a c c o u n t s g e t ( n a m e ) ；h g e tt h ec u r r e n tb a l a n c e b a l a n c e + = a m o u n t ； i n c r e m e n ti t a c c o u n t s p u t ( n a m e ，b a l a n c e ) ； n s e tt h en e wb a l a n c e ) 事务内存具有易用性和高性能等特点，是解决多核处理器体系结构下并行编 程困境的重要途径。 2 1 3 事务内存与数据库事务的差异 事务内存的最初概念来源于数据库的事务操作，它们在许多方面都有着相似 性，但又由于面向的对象不同，从而造成了它们在以下三个方面的不同： ( 一) 数据库中的数据存储在磁盘上，事务内存中的数据存储在主存中。 假定一次磁盘存取时间是5 m s ，一次主存存取时间是5 0 n s ，c p u 的计算速度为 1 0 g p i s ，则在一次磁盘存取时间内c p u 可执行5 千万条指令，而在一次主存存 取时间内c p u 只可执行5 0 0 条指令，由此可见这两者之间有着显著的速度差别。 ( 二)数据库中的数据需要持久存储，而事务内存中的数据不需要持久存 储。数据库存储的数据巨大，并且由于数据库的性质决定了需要在磁盘上长久保 存这些数据；而事务内存主要是负责共享内存中数据的同步，他存在于多线程或 者多程序的运行期间，在系统运行结束后或者事务处理完后，数据已经在磁盘中 做好保存后，内存中的这些数据即可扔掉，因而事务内存中的数据不需要持久保 存。 ( 三)数据库系统是一个封闭的世界，所有对磁盘数据的访问都必须通过 数据库系统来进行，数据库直接面向的对象是内存，通过数据库系统将数据提交 到内存后，以后的工作则受主存和c p u 的管束。但是对内存数据的访问不太可 能只是来自于事务内存系统，事务内存系统必须和现有的程序设计语言、程序库、 操作系统等共存，且由于事务内存系统自身的性质，直接和c p u 做数据交换。 数据库事务系统已经非常成熟，而事务内存只是刚刚起步，还有很多方面需 要研究，如在性能方面，需要编译器优化、适当的组合硬件和软件事务内存组件、 更优秀的策略处理竞争问题：在事务内存语义方面，事务操作的强原子性语义等； 第二章事务内存 在性能和调试分析工具方面，还需要做出好的诊断工具，来配合事务内存程序的 编写；在系统集成方面，可以考虑事务系统和分布式事务。 事务内存正确性的条件是可线性化( 1 i n e a r i z a b i l i t y ) ，可线性化【l9 】是并发访 问共享对象的充分条件。可线性化可以看作是可串行化的特殊情形，但是它们之 间也有着区别。可线性化是一个方法作用于一个对象，其特性包括局部性和非阻 塞性，适用于单个共享内存对象的共享。可串行化是一个方法作用于多个对象， 不具备局部性和非阻塞性，适用于数据库的共享。可线性化和可串行化一样，也 未涵盖非事务存取。 2 2 事务内存系统分类 事务内存一般情况下均指软件事务内存，本文中除非特殊说明，否则本文提 到的事务内存均指软件事务内存。但是如果按照事务内存的实现方式可以分为： 硬件事务内存( h a r d w a r et r a n s a c t i o n a lm e m o r y ) 、软件事务内存( s o f t w a r e t r a n s a c t i o n a lm e m o r y ) 、混合事务内存( h y b 稍t r a n s a c t i o n a lm e m o r y ) 。 硬件事务内存系统可以很大程度上获得由于硬件加速所带来性能上的提高， 如数据读、写的零延时。现有的事务内存系统在性能上还比不上基于锁的细粒度 模式的并行编程，但是硬件事务内存系统将显著地改进事务内存系统的性能。 h e r l i h y 和m o s s 1 0 】给出了一个硬件事务内存系统，在该硬件模式中，数据结构操 作被封装成为事务，更新那些能够集体地描述该操作的一组内存，特殊的事务高 速缓存保留着事务读取的内存位置的需要更新的数据。高速缓存一致性机制被扩 展，只要事务性高速缓存的数据不是无效的，事务就能够继续。一旦数据更新完 成，提交指令释放它们，使得对其他处理器单元可见。高速缓存一致性协议在硬 件事务内存中占据着重要的位置，是实现硬件事务内存系统的核心部分。 在硬件事务内存系统，高速缓存一致性( c a c h ec o h e r e n c e ) 2 0 1 主要有m e s i 一致性协议和仅使用读写位的一致性协议。 m e s i 一致性协议主要是指高速缓冲中的每一行或者处理单元只能是下面四 种状态之一： 更改的( 独占的) ：只在一个高速缓存中，并且处于更改态。 独占的( 未更改的) ：只在一个高速缓存中，并且处于未更改态。 共享的( 未更改的) ：一个或者多个高速缓存中。 无效的 m e s i 一致性协议共有四种状态，这种高速缓存一致性协议在一些商业系统 中得到应用，但是由于其四种状态转换复杂，并且状态过多，不易在硬件事务内 第二章事务内存 存系统中应用。 由于在并发的时候可能存在的冲突主要有读写、写读、写写操作冲突，针 对这些特点使用读写位的一致性协议，只需要在高速缓存中增加一个读位( b i t ) 和一个写位，这样就可以较好地控制这三种冲突。 在图2 1 中，显示了读写位一致性协议在高速缓存中的数据结构： 读位：表示事