（计算机软件与理论专业论文）基于事务内存的openmp扩展研究与实现.pdf

摘要 摘要 基于共享存储的多线程并行编程模型是高性能并行计算中重要的编程模型 之一。p t i l r e a d 和o p e n m p 是两种进行共享存储并行编程的典型方法，其中 o p e n m p 因能提供描述并行区域的编译制导语句以隐藏有关并行线程创建、管理 等细节，并提供增量式并行开发方式而日渐受到编程人员的欢迎。但无论是 p t h r e a d 还是o p e 心佃，并行多线程程序的正确性都必须由程序员来保证，而且 由于底层实现中采用的是并发互斥锁机制，往往会出现死锁、护航、优先权倒置 等问题，在某种程度上制约了它们的应用推广。 事务内存技术是近十年针对共享存储计算机体系结构编程的一个研究热点， 它的目标就是要克服传统并发锁机制所隐含的死锁、护航、优先权倒置、锁粒度 选择困难等缺陷，简化用户的多线程并行编程。本文通过对无锁的软件事务内存 机制的研究，将o p e n m p 和事务内存的优点有机结合，对o p e 洲p 模型进行了 有益的扩展。该扩展工作在保障程序并行性的同时，又能有效确保程序执行的正 确性。本文主要内容和工作如下： 第一，事务内存技术及其冲突机制的研究。本文在分析各种事务内存技术的 基础上，对一个基于j a v a 的软件事务内存模型进行扩展，实现了懒惰方式的冲 突检测机制和多种冲突解决方案。本文通过多个不同角度的测试分析，为事务内 存技术的进一步研究提供了更多的实验依据。 第二，基于j a v a 和事务内存技术的o p e i 蝴扩展研究与实现。j a v a 是一种 可移植和面向对象的高级语言，在语言级别上对多线程提供了很好的支持，而现 有o p e n m p 模型仅支持c c + + 和f o r t r a i l 等高级语言。本文结合j a v a 和o p e n m p 的各自特点，实现了一种称为j o m p t m 的并行编程模型。该模型定义了o p e n m p 风格的事务内存原语，封装了事务内存的实现细节，使用户既可以得到o p e 洲p 编程的简单性，又可得到由事务内存技术带来的程序正确性的保障。 第三，并行程序远程开发环境的设计与实现。针对并行程序开发的实际需求， 本文设计并实现了基于w e bs e r v i c e s 的远程高性能计算机开发与服务系统。该系 统提供了远程并行计算资源的有效共享与管理支持，使用户可以方便地使用并行 程序的本地编写、远程提交、运行与调试等功能。 关键词：共享存储并行编程，j a v a ，o p e 川p ，事务内存，w e b 服务 a b s t r a c t a b s t r a c t m u l t i n 鹏a d i n gp a r a l l e lp r 0 掣删n gm o d e lb a s e do ns h a r e dm 锄。巧 a r c h i t e c t u r ei so n eo ft h em o s ti m p o r t a n tp r o 伊姗i i 玛m o d e lf o rh i 曲p e r f 0 衄a 1 1 c e p 锄1 1 e lc o m p u t 岵p t h r e a da i l do p e 洲pa r e t y p i c a lm e t h o d so fs 慨dm e m o r ) r p a m l l e lp r 0 伊猢i n g o p e n m pi sm o r ep o p u l a rf o ri t sp r o v i d i n gd i r e c t i v e sf o r p 砌e lr e g i o n sw h i c hh i d et l l ed e t a i l sa b o u tp a r a l l e lt h r e a d sc r e a t i o n ，m 锄a g e m e n t ， e t c ，a 1 1 df o rp r 0 v i d i n gi n c r e m e n t a lp a r a l l e ld e v e l o p i n ga p p r o a c h h o w e v e r ，e i t h e ri n p t h 托a d0 ri no p e n m p ，t 1 1 ec o r r e c t n e s so ft h e p a r a l l e lp r o g r 锄1 m i n gs h o u l db e 创m 锄e e db yt h ep r o 笋a m m e r ，锄ds o m e t i m e sd e a d l o c k ，c o n v o ya i l dp r i o r i t ) ， i n v e r t i o nc a j m o tb ea v o i d e dw h e n 删i t i o n a lm u t u a l l ye x c l u s i v el o c km e c l 姗i s mi s e x p l o i t e d i nt h eb a s ei m p l e m e n t a t i o n ，r e s t r i c t i n gt h e i rp o p u l a r i t yi nac e r t a i l le x t e n t t r a l l s a c t i o n a lm e m o 巧t e c l l l l o l o g ) ，i sah o tt o p i ca r o l u l dp r o g r a m m i n go ns h a r e d m e i n o 巧c o m p u t e r a r c h i t e c t u r ei nr e c e n td e c a d e ，w h i c ha i m sa t s i m p l i f i n g m u l 6 t l l r e a d i n gp a r a l l e lp r o g r 舢i n g 锄do v e r c o m i n gt h e 如o v ed e f e c t so ft r a d i t i o i l a l l o c k s 鹤w e na st h ed i l e m m ao fc h o o s i n gl o c ks i z e ，e t c b a s e do nt h er e s e a r c ho f s o f h 硼t r a l l s a c t i o n a lm e m o 巧w i t h o u tl o c k s ，t h j sp a p e rc o m b i n e st h em e r i t so f q 瑚1 m pa n dt m s a c t i o n a lm e m o r yt 0e x t e n do p e 州pm o d e l u r l d e rt h i se x t e n t i o n ， b o t hp a r a l l e l i s ma n dc o r r e c t n e s so fm eu s e rp r 0 黟锄a r e 昏瑚跚l t e e d t h ec o n t e m s 舡l d w o f i c so ft h ep 印e ra r ea sf o l l o 、v s ： f i r s t l y ，t 1 1 er e s e a r c ho f 咖a c t i o n a lm e m o d ，t e c l l i l o l o g y 锄di t sc o n t e m i o n m a i i a g e ri sd o n e b ya 1 1 a l y z i n gc u l l r e n t 仃a n s a c t i o n a lm 锄。巧t e c h n o l o g i e s ，t h i sp 印e r e x t e 】耐saj a v ai m p l e m e n t e ds o f 时a r e 仃a l f l s a c t i o n a lm e m o r ys y s t e mb ya d d i n gal a z y c o n 锄t i o nd e t e c t i o nm e c h a n i s ma n de x t e n d i i 培i t sc o n t e n t i o nm a n a g e r t h i sp 印e r a l s 0 p r e s e n t sm a n yt e s tr e s u l t sf b md i f f e r e n ta n g l e so fv i e w ，p r o v i d i i 唱m o r c e x p e r 姗e n t a lb a s i sf o r 缸n h e rs t u d yi nt r a n s a c t i o n a lm e m o r ) r s e c o n d l y ，t l l er e s e a r c ha n di m p l e m e 曲l t i o no n 觚e x t e n d e do p e i m pm o d e li s f i n i s h e db 2 u s e do nj a v aa 1 1 dt r 觚s a c t i o n a lm e m o 巧j a v ai sap o n a b l ea 1 1 d o b i e c t - o r i e n t e dh i g hl e v e ll a n g u a g e ，p r o v i d e i n gag o o dm u l t i t l l r e a d e ds u p p o r ti n 1 e l 锄毋翰g el e v e l ，a n dm e a n w h i l e ，o p e n m pm o d e lc u 玎e n yo n l ys u p p o r t sc c + + a i l d f o n r 孤e t c h i 曲l e v e l l a n g u a g e s s o ，t i l i sp 印e rc o m b i n e st 1 1 em 翻t so fj a v aa i l d o p e m 订pt 0i m p l e m e n tan e wp a r a l l e lp r o g r a m m i n gm o d e l ，i l a m e dj o i l l pt m b y d e f i i i i n gs o m et r a l l s a c t i o n a lm e m o 巧砸m i t i v e si no p e n m ps t y l ea n de n c 印s u l a t i n g m e 蛔p l e m e n t a t i o nd e t a i l s ，j o m p j mc a i ln o to n l yg i v eu s e r sas i m p l eo p e n m p l i k e p r 0 踟m i n ge x p e r i e n c eb u ta l s ot l l e c o r r e c 恤e s sg u a r 锄t e eb yu s i n gt r a l l s a c t i o n a l m e 如i o r yt e c h n o l o g y t m r d l y ， ar e m o t es e r v i c e锄dd e v e l o p m e n te 1 1 v i r 0 姗e mf o r p a r a l l e i p r a 踟m i n g i sd e s i g n e da n di m p l e m e n t e du n d e rt h ec u r r e ms i t u a t i o na n dt h er e a l n e e do fh i 曲p e r f 0 m a n c ec o m p u t i n g w i t l lt h o s ee 仃e c t i v es u p p o r t sf o rs h a r i n ga n d m a i 磁g e m e n to fr e m o t ep a r a l l e lc o m p u t i n gr c s o u r c e sp r o v i d e db ym es y s t e m ，u s e 瑙 c a ne 嬲i l yw r i t ep a r a l l e lp r o g r a m sl o c a l l y ，a i l dt l l e ns u b i i l i tm e mt 0t l l er e m o t et 0 姗， d e b u 眵e t c a b s t r a c t k e yw o r d s ：s h a r e dm e m o 巧p 删l e lp r o g r 锄m i l l g ，j a v a ，o p e n m p ，t m s a c t i o 砌 m e m o 巧，w e bs e i c e s v 中国科学技术大学计算机科学与技术系 2 0 0 8 年5 月 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：盍4 互嵫 第l 章绪论 1 2 共享存储编程的研究现状 传统的共享变量编程是基于库的，比如a n s jx 3 h 5 ( a n s i1 9 9 3 ) 、p t h r e a d s ( p t h r e a d sp r o 鲈锄m i n gp a g e ) ，开发效率低、难以维护、可移植性差。对称多处理 器体系结构的发展和实践直接导致了1 9 9 7 年o p e n m p 标准( o p e l l m p1 9 9 7 ) 的出 现。o p e n m p ( o p e 州ph o m ep a g e ) 是共享内存环境上，多线程并行程序设计的标 准，它基于现有的串行语言，采用制导扩展的形式，提供功能强大的一组编译制 导和库函数，提供c f o r c r a n 的接口。o p e n m p 具有简单易学、可移植、可扩放 等优点，但o p e i m p 程序的正确性则必须完全由用户来保证，这就对用户的编程 水平提出了很高的要求，同时，它采用锁机制还可能带来死锁、护航、优先权倒 置等问题，这也在很大程度上限制了它的应用推广。 由于o p e n m p 不提供对j a v a 语言的支持，无法利用j a v a 在多线程( l e a1 9 9 9 ， e c k d2 0 0 6 ) 、可移植以及软件工程上的诸多优点，b u l l 于2 0 0 0 年实现了一个基 于j a y a 的o p e 心厦p 模型- j o m p 模型( b u l l2 0 0 0 ) 。j 0 m p 提供了多个类似于c c 抖 和f o r t r 锄中的o p e n m p 原语，用户通过调用这些原语来编写基于j a 豫的o p e n m p 程序，但该模型还有许多不完善之处，如不支持线程嵌套、不能动态调整线程数， 以及部分o p e n m p 制导语句未实现( 如a t o m i c 、f l u s h 、t h r e a d p r i v a t e ) 等。 事务内存( t r a u l s a c t i o n a lm e m o 巧，简称t m ) 的概念是h e r l i h y ( h e r l i h y1 9 9 3 ) 等人在1 9 9 3 年提出的，用以解决由传统锁机制带来的各种问题。事务内存通过 将并行执行的线程事务化、用事务操作代替互斥锁的方式来克服锁的各种缺陷。 在事务内存模型中，事务是一段连续的指令流，它是并行调试和处理的基本单位， 事务中所有针对共享数据的更新都将作为一个整体被原子地更新到共享内存中。 该模型既能降低编程的复杂性，又能保证程序的正确性，从而最大程度地挖掘程 序的并行性，提高程序的运行效率。近十年来，针对事务内存的研究比较多，但 至今仍没有个标准的、类似于o p e r 似p 的并行编程模型可供使用。 1 3 本文的工作和章节安排 本文在讨论软件事务内存技术的基础上，对基于j a v a 的o p e n m p 模型( b u l l 2 0 0 0 。j o n l p 模型) 进行扩展，在保留o p e n m p 简单、可移植、可扩放等优点的同 时，增加无锁的软件事务内存机制，以克服0 p e r m p 技术中的固有缺陷。另外， 本文还设计了一个远程高性能并行开发系统，以方便并行程序的本地开发和远程 运行。 以下是对本文工作内容及文章结构的简要介绍。 2 第l 章绪论 1 3 2 本文的组织 本文共分为6 章，具体组织如下： 第l 章，简单介绍了共享存储编程的研究背景、发展趋势，以及当前普通接 受的o p e r m p 并行编程模型和仍处于研究阶段的事务内存技术，并通过o p e r l m p 优、缺点的说明，提出将事务内存技术和o p e 蝴p 模型相结合的j o m p t m 并行 编程模型。最后，为本文的工作内容、成果和文章结构做概括性的描述。 第2 章，概述共享存储的体系结构、早期主要的并行编程语言( 或接口) ，详 细介绍o p e i 蝴p 并行编程模型技术，并通过比较o p e i l m p 和事务内存技术，指 出将两者相结合的必要性。 第3 章，详细介绍事务内存技术和冲突处理机制。本章主要集中讨论由软件 的方式实现的事务内存技术，即软件事务内存技术的相关知识和研究现状。本章 最后还给出一个实现了懒惰冲突检测机制的事务内存系统，称为l a s t c h e c k 系统， 通过针对该系统的不用角度的性能分析，为事务内存技术的进一步研究提供了实 验依据。 第4 章，介绍一种将j a v a 多线程技术和o p e n m p 并行编程接口相结合的软 件事务内存编程模型，即j o m pt m 模型。文中首先对j a v a 语言和j o i n p 库做了 简要介绍，然后对j o m pt m 的实现、性能以及进一步改进做了详细地描述。 第5 章，给出基于w e bs e r v i c e s 技术的远程并行程序开发系统的设计、实现 和相关的性能分析。该系统实现的功能较多，包括本地程序开发、远程运行以及 文件传输等多个模块，本文主要针对与j o m pt m 相关的程序开发、运行细节做 了较为详细地阐述，而其它功能则在性能分析中做简单的介绍。 第6 章，总结本文的工作和j o m pt m 下一步研究的方向。 1 4小结 本章首先简要介绍了共享存储编程的研究背景、研究现状和o p e r l m p 共享存 储编程模型的优、缺点，提出了结合j a v a 和o p e n m p 的特点且能克服o p e n m p 固有缺陷的事务内存机制；接下来，阐述了本文所完成的主要工作；最后给出了 全文的章节安排。 4 第2 章共享存储的并行编程 第2 章共享存储的并行编程 2 1共享存储计算机体系结构 根据并行存储器的体系结构，共享存储系统可分为纯共享存储环境和虚拟共 享存储环境( 陈国良，2 0 0 2 a 、2 0 0 2 b ) 。 2 1 1 纯共享存储环境 纯共享存储环境的主要特点是： 系统中存在一个集中的、公共的共享存储器； 系统中集中的存储器对程序员而言是全局统一编址的； 不提供对非一致存储访问应用程序的支持。 早期的共享存储并行程序主要使用信号灯、条件临界区和管程等进行任务 ( 进程、线程) 间的通信。近代的编程标准有a n s ix 3 h 5 ( a n s il9 9 3 ) 、p t h r e a d s 口t l l 陀a d sp r o g r a l 砌i n gp a g e ) 和0 p e i l m p ( o p e n m ph o m ep a g e ) 等。 与纯共享存储环境相对应的并行计算机结构模型是对称多处理机( s m p ： s y 玎m l e t r i c a lm u l t i p r o c e s s i n g ) 结构。s m p 系统通常使用商品微处理器( 具有片上 或外置高速缓存) ，它们经由高速总线( 或交叉开关) 连向共享存储器。此类系 统主要应用于商务，例如数据库、在线事务处理系统和数据仓库等。一方面，由 于系统是对称的，每个处理器可等同地访问共享存储器、i ，o 设备和操作系统服 务，因此可以开拓较高的并行度；而另一方面，由于存储是共享的，此类系统中 的处理器也往往受到限制而不能太多( 一般少于6 4 个) ，同时总线和交叉形状 互连一旦做成也难于扩展。s m p 系统的结构见图2 1 ( a ) 。 与s m p 结构相对应的访存模型是均匀存储访问( u m a ：u n i f o n nm e m o 巧 a c c e 黟) 模型。 2 1 2 虚拟共享存储环境 虚拟共享存储环境的主要特点是： 系统中分布的局部存储器组成了系统的全局共享虚拟存储器； 系统中的虚拟共享存储器对程序员而言是全局可寻址的，即由操作系统负责 将这些物理上分布的局部存储器向用户呈现为共享的存储视图，所共享的数据空 间是连续的，且可以用通常的读、写操作访问它。近代的编程标准有l i n d a 和 j 蠲i a ( h uw1 9 9 9 ) 等。 s 第2 章共享存储的并行编程 与虚拟共享存储环境相对应的并行计算机结构模型是分布式共享存储( d s m ： d i s t r i b u t e ds h a f e dm e m o g ) 多处理机结构。d s m 系统中用高速缓存目录d i r 来 支持分布高速缓存的一致性。d s m 和s m p 的差别是：d s m 在物理上有分布在 各节点的本地存储器，从而形成了一个共享的存储器。对用户而言，系统硬件和 软件提供了一个单地址的编程空间。d s m 系统的结构见图2 1 ( b ) 。 与d s m 结构相对应的访存模型是非均匀存储访问烈u m a ：n o n 岫j f o 姗 m e m o 巧a c c e s s ) 模型。 s m ：共享存储器蹦：本地存储器 髓：存储器总线d i r ：高速缓存目录 n i c ：网络接口电路p c ：微处理器和c a c h e f 总线或交叉开关 ( a ) s m p m 扛圈l 忙圃 ：q 半叫； im k 圈i i 旧 ：叶半叫i 定制网络 ( b ) d s m 图2 1 共享存储并行计算机结构模型 2 2 共享存储并行编程模型 2 2 1早期共享存储并行编程模型 早期的共享存储并行编程模型主要有a n s ix 3 h 5 和p o s 两种，前者只支 持循环级并行性，粒度太细，后者适合任务并行，而不适合数据并行。 2 2 1 1a n s ix 3 h 5 共享存储模型 x 3 h 5 共享存储模型是1 9 9 3 年建立的a n s i 标准( a n s i1 9 9 3 ) ，它定义了一 个概念标准编程模型，已与c 、f o n r a i l 7 7 和f o 舰1 9 0 等语言相结合。 x 3 h 5 的并行区域是包含在p 搬l l e l 和e n dp a r a l l e l 之间的部分，程序首先由 单个线程( 称为主线程) 串行执行，当遇到p a r a l l e l 语句时开始进入并行阶段、生 成多个子线程，主线程和子线程一起执行各自的任务；当遇到e n dp a m l l e l 时， 返回到串行模式，只有主线程继续运行。 在x 3 h 5 中，各线程可以拥有自己的私有变量，通过隐路障、栅栏、显路障 等方法保证存储器的一致性。而且，x 3 h 5 模型引入了四种形式的同步变量，即 闩锁皿a t c h ，在临界区内使用，用于减少竞争和增加并行度) 、锁( 用于实现互斥 6 第2 章共享存储的并行编程 访问韵原子性) 、事件( 用于实现“生产者 和“消费者 的同步) 和顺序( o r d i n a l ， 用于按照线程的瑚 1 l 【进行线程同步) ，每种类型的变量都伴有初始化操作和释放 操作，任何变量在使用前均须被初始化，并通过赋值为非初始化状态而被释放。 2 2 1 2p o s 线程模型 p o s ( p o m b l eo p e r a t i o ns y s t e mi n t e r & e ) n r e a d s ，简称p t h r e a d s 洲i c h o l s 1 9 9 6 ) ，其功能和界面与s o l a r i s 线程类似，由i e e e 标准委员会1 9 9 5 年建立。 h i l 玎鼢d s 被定义为一组c 语言的编程类型和过程调用，通过包含p t l l r e a d h 头文件 和一个线程库来使用。 p o s i x 的特点是： - 线程共享相同的内存空间。 - 与标准f o r k o 相比，线程带来的开销很小。内核无需单独复制进程的内 存空间或文件描述符等，节省了大量的c p u 时间。 一 和进程一样，线程将利用多c p u ，如果软件是针对多处理器系统设计的 计算密集型应用。 - 支持内存共享无需使用繁琐的i p c 和其它复杂的通信机制。 - p o s i x 线程标准不记录任何“家族 信息，无父无子。 2 2 2 o p e n m p 编程模型 2 2 z 1 o p e n m p 概述 o p e i l m p ( o p e 州ph o m ep a g e ) 起源于a n s ix 3 h 5 ，是共享存储体系结构( 主要 针对s m p 结构) 上的应用编程模型，具有简单、移植性好和可扩放等优点，目前 已经广泛应用于u n i x 、w i n d o w sn t 等多种平台上。严格地说，o p e i l m p 不是 一门新的语言，不能自动进行并行化，它是对基本语言( c 、c 抖、f o r t r a l l 7 7 、 f o i t r 锄9 0 等) 的扩展。 2 2 五2 o p e n m p 并行编程模型 o p e 州p 规范了一系列的编译制导、运行库和环境变量，并将它们提供给用 户，用于与编译器和运行时系统进行交互。o p e r l m p 的体系结构见图2 2 。 7 第2 章共享存储的并行编程 应用用户 个 编谇l j 导! 环嵌量 爪 运行库例程 l 个 山 ，o s 线程 图2 2o p e n m 体系结构 o p e n m p 是基于编译制导的，其规范中定义的制导指令、运行库和环境变量， 用于同编译器和运行时系统进行交互，使得用户能够控制并行程序的行为，按照 标准将已有的串行程序逐步并行化。制导指令是对程序设计语言的扩展，迸一步 提供了对并行区域、工作共享、同步构造的支持，并且支持数据的共享和私有化。 运行库和环境变量，使用户可以调整并行程序的执行环境。 o p e i 州p 使用f o r k j o i n 并行执行模型。所有的o p e n m p 程序都开始于一 个单独串行执行的主线程，直到遇见第一个并行域才开始多线程执行。这个过程 如图2 3 所示，分为两个阶段： f o r k ：主线程创建一队并行的线程，然后，并行域中的代码在不同的 线程队中并行执行； j o i n ：当所有线程在并行域中执行完之后，它们或被同步或被中断，最 后只有主线程继续执行。 ， f j f j oo0 o riri knk n l 叠唇； 击* ；4 击 图2 3o p e m 汀程序运行过程 2 2 2 3 o p e n m p 的优缺点 o p e r l m p 通过制导、运行库例程和环境变量，使程序具有较高的可移植性， 而且通过对程序添加制导，使用户可以逐步对串行程序进行增量并行化，可扩放 性较强。但o p e 洲p 完全依赖用户保证制导的正确性，即使用户给出的制导是错 8 第2 章共享存储的并行编程 误的。而且o p e n m p 中线程同步的方法本质上还是采用互斥锁机制，为保证程序 并行执行的正确性，用户仍需要考虑诸如线程同步等许多细节，因此无法避免锁 机制的固有缺陷。这些缺陷主要包括： 死锁 指多个线程互相等待被其它线程占有的资源，彼此间形成一个等待环，因而 都无法继续运行下去。 护航 指当拥有某个锁的线程被切换出去后，导致需要该锁的其它线程必须等待。 优先权倒置 指当优先权低的线程拥有某个锁时，高优先权的线程若想使用该锁，则它必 须先等待。 粒度选择困难 粗粒度的锁，虽然易于编程和使用，但是并行效率低，因为它加剧了对锁的 竞争，使得无关的操作顺序执行；细粒度的锁，虽然并行效率较高，但往往因需 要考虑更多实现细节而难以编程。 针对传统多线程编程中存在的这些问题，“事务内存 的概念被提了出来。 2 2 3 事务内存 靠事务 的概念来源于数据库，由t o mk n i g h t 将此概念引入并行计算领域 ( 1 ；乙= l i ；曲t1 9 8 6 ) 。事务内存( 1 m ，n a i l s a c t i o n a lm e m o r y ) 是指用于访问或修改共享对 象的有限指令序列( m a r a t h e2 0 0 4 a ) 。在实现事务机制的程序中，访闾共享存储的 代码被分成多个事务，它们的执行是原子的，即不同事务的操作互不交迭( h e r l i h y 2 0 0 6 ) 。根据实现媒介的不同，1 m 又可分为硬件1 m ( h t m ，h a r d w a r et r a i l s a c t i o l l a l m e m o r y ) 和软件1 m ( s t m ，s o f 时a r e t r a i l s a c t i o n a lm e m o 巧) ，本文主要研究后者。 事务内存相对于由锁机制实现的共享存储编程模型有以下优点： 死锁避免 多个线程竞争同一资源的现象在事务内存中被称为冲突，当冲突发生时，事 务内存可以通过多种冲突解决方案来避免死锁的发生。 护航处理 在事务内存中，若占有共享资源的事务被切换出去，其它线程可以将其撤消， 而不用一直等待。 优先权保证 9 第2 章共享存储的并行编程 通过采用基于优先权的冲突解决方案，事务内存可以有效保证高优先权的事 务及时获得共享资源的访问权。 粒度选择容易 事务内存既像粗粒度锁一样易于使用，其性能又与细粒度锁相当。同时， 它还具有较好的代码复用性，而且比锁更易于从出错状态中恢复。 但是，目前还没有针对事务内存技术的统一并行编程模型，因此，它难以为 普通用户使用，这也是本文所关注的最主要问题。关于事务内存更详细的讨论， 见第3 、4 章。 2 3小结 本章首先介绍了共享存储的体系结构和早期的共享存储并行编程模型，接着 介绍了o p e 蝴p 并行编程模型的运行过程和缺点，并分析了它采用锁机制所带来 的各种缺陷，最后介绍事务内存技术的概念、相对于o p e 州p 的优点以及它的不 足。 1 0 第3 章软件事务内存 3 3 研究现状 随着各个领域对并行计算的需求日益增大，以及多核处理器在桌面系统中的 日渐普及，人们愈发关注共享存储系统的编程问题。经过十多年的探索，t m 取 得了很大的研究进展。本文选取其中具有代表性的四个s t m 系统来阐述这一领 域的研究现状。 3 3 1w s t m w s t m ( h a 耐s2 0 0 3 ，f l 镯e r2 0 0 7 ) 是基于字的、o b s 缸佻t i o n 骶e 的s 1 m ，用c 语言实现，通过提供一些a p i 函数，将访问共享数据的细节封闭起来。这些a p i 函数包括： v o i ds t m s t a n ( ) ：开始一个新事务； s 缸nw o r ds r e a d ( a d 出a ) ：读共享存储字； s 缸i lw o r ds t m w r i t e ( a d d ra ，s t i nw o r dw ) ：写共享存储字； v o i ds t m a b o n ( ) ：撤消处于活动状态的事务； b o o l e a i ls t m c o m m i t ( ) ：提交事务，返回是否提交成功； b o o l e a l ls 1 m v a l i d a t e ( ) ：判断当前活动事务的一致性； v o i ds t m w a i t ( ) ：遇到冲突时进行阻塞。 w s t m 系统包括三个主要的数据结构： i 应用堆( a p p l i c “o nh e a p ) 并行线程准备使用的、拥有真实数据的共享存储区域。 2 所有权记录( o r e c s ：h a l s h1 a b l eo fo w n e r s h i pr e c o r d s ) 在w s t m 中，通过将应用堆中共享数据的地址与o r e c 关联来协调事务。每 个o r e c 都有固定的大小，它要么存放一个版本号( 表示。嗽当前没被任何事务占 有) ，要么存放指向占有当前o r e c 的事务的事务描述符。事务只有在执行 s 1 m c o 姗i t 时才能获得o r e c s 。当一个事务拥有某个o r e c 时，它便拥有该o r e c 中所有的共享存储地址。 3 事务描述符( t r a n s a c t i o nd e s c 嘶 t o r ) 每个事务都通过它的事务描述符来访问共享存储。事务描述符由若干事务 入口组成，这些入口通过访存操作( s t m r e a d 和s t m 嘶t e ) 创建。每个入口又包 括五个元素，即：共享存储字的地址、内存字的内容、相应的o r e c 的版本号、 内存字在提交时待更新的新值以及o r e c 待更新的新版本号。对于一个所有权记 录，如果有多个事务描述符入口与它对应，那么这些入口中版本信息必须一致。 1 3 第3 章软件事务内存 当一个事务发现其它事务的描述符在它准备读( s 眦e a d 或s t m w r i t e ) 或请 求提交( s t m c o 舢i t ) 的o r e c 中时，则冲突发生，这时需要进行冲突处理( 下一章 讨论) 。 a l a 2 a 1 0 1 a 1 0 2 a p p l i c a t i o n h e a p： t r a n s a c t i o nd e s c r i p t o r s 1 0 0 。t x l 2 0 0 r l 、 - 一卜 s t a t u s ：u n d e c i d e b a l ：( 1 0 0 ，1 5 ) 一 ( 2 0 0 ，1 6 ) a 2 ：( 2 0 0 。2 1 ) ( 1 0 0 ，2 2 ) 3 0 0诲v e r s i o n 2 1 4 0 0 图3 1w s l m 系统结构示例 图3 1 是w s t m 数据结构的一个示例。在图中，应用堆包含共享数据字的 地址( a l ，a 2 ，a 1 0 1 ，a 1 0 2 ) 和数据( 1 0 0 ，2 0 0 ，3 0 0 ，4 0 0 ) ：所有权记录中a l 和a l o l 映射到 。眦r l ，a 2 和a 1 0 2 映射到o r e cr 2 ；在事务描述符表中，事务t ) 【1 准备更新a 1 和 a 2 的值，它已经获得了r l ，可以修改a l 了，但为了修改a 2 ，仍需要申请r 2 。 基于字的s t m 系统可用于固定粒度的字访问，但对于其它一些自定义的复 杂数据结构，如链表、树等，就不适用了。 3 3 3o s i m o s t m ( f m s e r2 0 0 7 ) 是基于对象的、l o c k 盘e e 的s t m ，用c 语言实现，它将 待操作的特定数据结构封装成对象的形式，按照原子的方式访问和更新。 o s t m 系统包括三个主要的数据结构： 1 对象头( o b j e c th e a d e r ) 每个共享对象被封装成一个对象头。事务通过“打开 这些对象头，并返回 在对象头中封装的、指向共享对象的指针，可以访问该对象。一个事务可以同时 打开多个对象头。 2 事务描述符( t m s a c t i o nd e s c r i p t o r s ) 每个事务都使用事务描述符保存它正在使用的对象的列表。事务描述符还 包含一个状态位( u n d e c i d e d ，a b o r t e d ，c o m m i t t e d 或者r e a d c h e c k i n g ) ，一个只读列表( 保存事务以只读模式打开的当前对象) 和一个读写 列表( 保存事务以读写模式打开的当前对象) 。 3 对象句柄( o 场e c th a l l d l e s ) 1 4 第3 章软件事务内存 事务描述符的两个列表( 只读列表和读写列表) 都包含若干对象句柄。对象句柄由指向对象头的引用组成。当事务试图提交时，通过句柄验证对象内容的一 致性，并保证对任何对象的更新对其它线程都可见。 当某事务想访问共享对象时，它首先必须通过对象头“打开这些对象，“打 开 操作在事务描述符中创建一个对象句柄。如果事务以只读模式打开一个共享 对象，则增加相应的对象句柄到该事务的只读列表：否则( 以读写模式打开) ， 除增加旬柄到其读写列表外，还要创建一个该对象的影子复制( s h a d 笺j i l 堇鋈跨i i 秀冀i 雕蹀蓁翼李囊钎孺雨僻一m 谨霪塞阳陈；商蓁e 薹蕈往。栝蒿；孺拍萋 袒彤配骋兜托班雾蓁薹妄雾誓雾；篇醛墼霎雾酲； 茎! 薹二萋囊蓁蓁冀冀需薹羹鬟g 蓠薹；萋羹耄薹薹羹鋈萋奏薹耋 羹萝琶厶篓季整良仝雇；活= ；t m s a c t i o n d e s c r i p t o r ) 。事务描述符是每个 线程只有一个，包括状态位、私有的读写列表。如果事务描述符的状态位( s t a t u s ) 为。c o m m i t t e d ”，则数据对象的新版本( da _ c ao b i e c t n e wv e r s i o n ) 为当前共享对 象的值；如果为“a b o r t e d ”，则旧数据指针有效，数据对象的旧版本( d 稚lo b j e c t ol dv e r s i o n ) 为当前共享对象的值；如果为“a c t i v e ”，则在撤消t 之前任何事务都 不能读或写该对象。r s t m 的数据结构如图3 7 所示。 图3 7r s t m 的数据结构图 上述的各种基于对象的s t m 中，o s t m 的数据结构是事务驱动的( 每个事 务一个数据结构) ，而d s t m 和r s t m 是对象驱动的( 每个对象一个数据结构) 。 34 冲突处理机制 34 1 概述 1 x 第3 章软件事务内存 指向新版本的对象。 图3 3d s t m 共享对象结构图 事务对象的当前版本( 最后一次提交的版本) 决定于最后一次以写模式打开 该对象的事务的状态。如果该事务处于活动状态，则旧对象是当前版本，新对象 是可能的新版本( 当事务提交时，其初值为旧对象的影子复制) ：如果该事务被成 功提交，则新对象就是当前版本，如图3 4 所示；如果事务被撤消，则旧对象是 当前版本，如图3 5 所示。 e o m r n i t t e d 图3 4 最后一次打开对象的事务成功提交 1 6 舅罾 一一一一一 一一一一一一一 一一一一一 一一一一一一一 翼乳 第3 章软件事务内存 一纠! = 竺! 兰! ：! 兰 j 一珏e vo b j e 、 o l 哇o b j e 伉 、 o l d l o c a t o f 、 l 岬磊i 忑 f - 一 n e v 、o b 3 e c 乞 i o l do b j e “ 珏e wl o e a t o r 图3 5 最后一次打开对象的事务被撤消 d s t m 2 0 0 6 提供了两个工厂( f - a c t o r ) ，) 来实现原子对象： 1 o b s t m c t i o n - 舶e 工厂 和d s t m 2 0 0 3 的对象操作方式相同。 2 s h a d o w 工厂 这是一种有锁的s t m 机制，它使用短临界区以降低打开对象的开销，在未来 的体系结构中，这种临界区会被由硬件支持的小事务所替代。 对于每个接口定义的属性( 即s 毗e t 方法) ，s h a d o w 工厂会同时生成一个常规 域和一个s l l a ( 1 0 w 域，见图3 6 ( a ) 。事务还拥有两个方法： b a c k u p ( ) ：拷贝每个常规域的值到它的s h a d o w 域； r e s t o r e ( ) ：拷贝它的s h a d o w 域的值到常规域。 通常，当某事务t 打开一个对象时，它检查最后一个写该对象的事务的状态。 如果是提交，则该对象的常规域拥有对象的当前值，t 调用b a c k