事务内存

维基百科,自由的百科全书
跳转至: 导航搜索

事务内存是一种并行程序设计的方式,其来自于数据库管理系统(DBMS)中的事务(Transaction)概念。事务内存目前有两种实现方式,基于软件的STM(Software Transactional Memory)和基于硬件的HTM(Hardware Transactional Memory)。


背景[编辑]

采用任务并行时必须考虑线程间同步的问题:最初步也是最通常的方法是使用,只有获得了锁的线程在允许访问临界区,但是使用锁会发生一些问题,诸如优先级反转(Priority inversion)、死锁(Deadlock)、护航(Convoying)等问题;于是后来产生了无锁编程(Lockless programming)的概念,即使用原子操作(Atomic Operations)和同步路障(Memory barrier)来完成线程间同步的功能,这种方法规避了使用锁时出现的上述问题并极大的提高了并行度,但是面临着原子操作本身功能局限性和组合性(Compositionality)不佳的问题。原子操作的局限性使得无锁编程的算法设计很难,组合性则是指数个同步的原子对象组合应该也是一个同步的原子对象。

事务的概念[编辑]

事务的概念源自于数据库管理系统(DBMS)中数据库事务的概念。在数据库管理系统中,事务必须满足ACID性质,即原子性,一致性,隔离性和持久性。原子性指的是事务中的动作要么全部执行,要么一个都不执行;一致性指的是任何时刻,数据库必须处于一致性状态,即必须满足某些预先设定的条件;隔离性是指一个事务不能看见其他未提交事务所涉及到的内部对象的状态,而持久性则是指一个已提交的事务对数据库系统的改变必须是永久的。

事务内存的分类和涉及到的基本术语[编辑]

事务内存按照更新数据时的机制不同,可分为 延迟更新(deferred-update) 和 直接更新 (direct-update) 两大类。延迟更新软件事务内存的基本思想是一个线程僅改變屬於自己的資料副本,如果未與其他线程发生冲突,最終的提交 (Commit) 动作則可順利完成,副本內容抄到正本之上;如果失败則取消回朔 (Abort / Rollback),丟棄副本即可。直接更新则是一個綫程暫時獨佔和直接更新資料正本,提交得到確認,只須解除獨佔設定,容許其他綫程往後存取;直接更新需要資料的原始值作為副本,倘若運算最終無法完成,可作回朔之用。

根据在事务冲突时的处理机制不同,又可以分为 悲观乐观的并发控制(pessimistic & optimistic concurrency control)两大类。在悲观的并发控制中,冲突一旦发生就必须要得到侦测并加以解决,而在乐观的并发控制里,冲突的侦测和解决可以延迟,只要是在事务提交之前进行就可以了。

事务还有粒度(granularity)的概念:最容易让程序员理解的粒度是对象粒度;在此粒度下,任何冲突发生的判决是在对象范围内进行的:即使两个事务修改的内存块不重合,只要他们是在同一个对象内,那么就可以判断这两个事务冲突。更精细的粒度是字粒度(word granularity)和字节粒度(byte granularity),在这两种粒度下,冲突的检测更精细,更利于事务内存系统性能的提升,但是却会给程序员带来不小的麻烦。

软件事务内存(STM)[编辑]

软件事务内存的实现包括原子对象(Atomic object)、冲突判决器(Conflict manager)。其中原子对象的实现是最重要的,它是各事务之间通信同步的媒介。原子对象的实现又分为顺序性实现和事务实现:其中事务实现还要要求实现同步和恢复(recovery)功能,同步功能即意味着要求有检测事务冲突的能力,而恢复功能则意味着需要在事务失败的时候将对象回滚到事务执行之前的状态。目前提出的原子对象一般是基于读/写冲突(Read/Write conflict)的机制:原子对象提供两个接口,一个为读接口,一个为写接口,通过读接口可以得到一个可以读的对象,而通过写接口则可以得到一个可以写的对象。为了检测冲突(即多个事务并发时的同步情况),事务中可以设立两个集合,一个为读集(Read set),一个为写集(Write set),分别记录该事务所要处理的读写原子对象集。如果一个事务的读集或写集与另一个事务的写集有交叉,则表明两个事务冲突,需要冲突判决器进一步采取决策。

硬件事务内存(HTM)[编辑]

昇陽電腦Rock微處理器將支援硬件事務內存。

Azul Systems在2009年推出的 Vega 2 微處理器支援硬件事務內存。[1]

相关的话题[编辑]

參考資料[编辑]

  1. ^ Java on a 1000 Cores - Tales of Hardware / Software CoDesign

参考书目[编辑]

  1. Transactional Memory,Synthesis Lectures on Computer Architecture,MarkD. Hill, University of Wisconsin, Madison