关 闭

新闻中心

EEPW首页 > 工控自动化 > 设计应用 > 事务存储结构的实现

事务存储结构的实现

作者:时间:2012-06-04来源:网络收藏

1 引言

本文引用地址:http://www.eepw.com.cn/article/202295.htm

随着多核处理器技术的不断更新和发展,传统的串行程序不论在效率上还是性能上都已经跟不上信息高速发展的脚步了,程序员不得不开发线程级并行以提高片上计算资源的使用效率,但也带来了新的挑战和问题。目前不同线程间的同步、对共享资源的访问等都是通过锁和信号量机制完成的。然而,这种传统的基于锁和信号量的并发系统存在明显的局限性。粗粒度的锁对大量的共享数据做了保护,但是可扩展性不好,因为即使在线程间不存在对共享数据的访问的情况下也可能会出现冲突阻塞现象;细粒度的锁虽然比粗粒度的锁扩展性能好,但由于算法设计的复杂性,普通程序员很难借助细力度的锁实现高效的应用。同时使用锁机制还会带来诸多问题,比如:死锁、优先级反转等,极大地影响了并行应用的效率和性能。

事务存储(Transactional Memory,TM)的使用是解决上述存在问题一个很好的办法[1]。通过将不同并行执行的线程事务化,用事务操作来代替锁机制能降低编程的复杂性。事务是被单线程执行的对内存进行读写的有序操作序列,其特性包括:原子性、隔离性、一致性和持久性。通常事务的执行过程为:调用事务入口函数(begin_transaction)开始执行事务,当事务执行完毕后调用提交函数(commit_transaction)开始提交工作,提交过程分为三个阶段(请求提交、开始提交和完成提交),执行完提交后此事务也就执行完毕,从而继续执行下面的事务。但如果事务在执行或提交过程中发生冲突或者错误,则通过其特有的回滚机制 (rollback)返回到此事务入口继续执行。事务的执行流程图如图 1所示。

图 1 事务执行流程

为了实现事务的这些特性,需有一个很好的TM系统来支持事务数据的版本管理(Version Management)和事务的冲突管理(Contention Management)。版本管理同时对新值(事务提交后可见)和原始的旧值(事务执行过程中发生了回滚的恢复数据)进行管理。根据数据存放方式的不同TM系统区分版本管理为:积极版本管理(Eager Version Management)和懒惰版本管理(Lazy Version Management)。积极版本管理是将新值置于目标存储区中,这样在提交时新值能够很快的得到执行,极大地降低了提交的时延;而懒惰版本管理是将原始的旧值置于目标存储区,虽然会增加提交的延时但是降低了当事务发生回滚后执行的延时。冲突管理是不同事务执行过程中对共享资源访问引发冲突而进行的冲突检测以及管理的机制。冲突管理有积极的(Eager)和懒惰的(Lazy)两种策略,如果冲突在读数据或写数据时立刻被发现而进行仲裁,这种冲突检测是积极的;如果冲突是在事务进行提交时才发现并仲裁的,这种冲突检测则是懒惰的。

目前,基于TM的硬件结构有很多种,图2中列出了目前几种流行的硬件结构根据版本管理和冲突管理而进行的分类。本文将介绍其中的一种结构——LogTM(日志事务存储),通过对其硬件结构(参见图3)、版本管理、冲突管理的实现,展现了此结构的优越性,并给后续研究提供参考和帮助。

图2 TM系统分类

2 LogTM的结构

LogTM是建立在多机系统中基于日志的TM实现,每个核都有独自的私有cache,并通过目录协议来维持数据的一致性。它采用的是积极的版本管理策略和积极的冲突管理策略。图3给出了LogTM的硬件结构,它通过增加一些寄存器和cache中的读/写位很好地完成了对事务的操作。

1.jpg

图3 LogTM的硬件结构 (图中黑框中为其特有结构)

2.1 版本管理(Version Management)

LogTM使用积极的版本管理,将新的执行数据存储在目标区域(目标地址)中,而将旧的数据存储在其它缓冲区。它通过在内存中开辟一块事务日志区域存储事务执行过程中被修改的数据(上文中提到的原始数据)和这些数据所对应的地址,新的执行数据则被保存在目标存储区(目标地址),当执行完成提交时,这些新数据将会立即生效;当事务执行过程中或提交时发生冲突或错误需要回滚时,则通过事务日志中记录的信息恢复出事务执行前的初始状态。

刚开始创建线程时,每一个线程对应着一个日志而且为日志分配一块虚拟存储区域,并将该日志基地址写入Log Base寄存器,当旧数据需要存储到日志时,LogTM通过Log Base寄存器中的值定位到日志的入口然后将旧数据的虚拟地址和值一同保存在日志中以便恢复时使用。为了减少冗余日志,LogTM为每一个cache块添加了对应的写(W)位,用此来标识该cache块在日志中的记录情况。当事务提交成功后,LogTM将对应cache块的写(W)标志位清0并将Log Pointer(日志指针)重新指向日志的入口处,以便处理后续事务。

LogTM也为每个cache块设置了一个读(R)标志位,就像上面我们讨论的写(W)标志位一样。在每个事务操作过程中LogTM同样将读标志位设置用于表示读操作的执行(如图4所示),而且在事务结束后,读标志位也清0。

这种积极的版本管理模式的缺点就是在事务发生冲突或错误需要回滚时执行比较慢,在回滚时,LogTM为了完成恢复必须将原始数据从日志中读到合适的目标地址中然后重置写(W)位,同时因为有很多数据记录在日志中,所以恢复过程必须按照由后向前(后进先出)的顺序进行。但在事务冲突比较少的情况下,这种模式能够带来高效的执行效率。

为了能更好的理解LogTM版本管理过程,图4通过一个例子进行了很好的分析。

(1)事务执行开始前的状态——cache数据块中存放着原始数据,每块的读(R)、写(W)位置0,LogBase(日志基址寄存器)指向日志入口地址,LogPtr(日志偏移指针)指向日志入口地址同时TMcount(事务计数器)置1代表正准备执行一个事务。


上一页 1 2 3 下一页

关键词: 存储结构

评论


技术专区

关闭