你如何实现软件事务内存？

Question

就实际的低级原子指令和内存栅栏而言(我假设它们已被使用),您如何实现STM？

对我来说神秘的部分是,给定一些任意代码块,您需要一种方法可以在之后返回并确定每个步骤中使用的值是否有效.你是怎么做到的,你如何有效地做到这一点？这也似乎表明,就像任何其他"锁定"解决方案一样,您希望保持关键部分尽可能小(以减少冲突的可能性),我是对的吗？

此外,STM可以简单地检测"在执行计算时进入该区域的另一个线程,因此计算无效"或者它是否可以实际检测是否使用了破坏的值(因此运气时有时两个线程可以同时执行相同的临界区需要回滚)？

Answer 1

有些论文真的很难读,但有两篇非常简洁明了:

Transactional Locking II,Dave Dice,Ori Shalev,Nir Shavit,用任何语言描述"TL2"STM算法.

Deuce:Java中的无创软件事务内存,Guy Korland,Nir Shavit,Pascal Felber,它解释了一个加载时类转换器,它将常规java类转换为内存类,这些类具有执行STM的附加字节码.这与问题相关,因为该论文解释了如何将没有STM的代码机械转换为在任何OO语言中执行STM的代码.

Deuce框架允许您插入您想要使用的实际算法; 包括TL2算法.由于Deuce框架是Java,以下讨论使用Java术语,但仅假设您使用OO语言编写.

下面将概述TL2方法.这些论文与其他方法有关,但研究一种算法可以回答很多问题.

你如何实施STM？对我来说神秘的部分是,给定一些任意代码块,您需要一种方法可以在之后返回并确定每个步骤中使用的值是否有效.

关于TL2如何执行STM的一个简短答案是"簿记",然后仅在提交时使用写锁定.阅读纸张以获得精细细节,但板刷轮廓如下.您可以在原始代码中使用的每个属性都有一个getter和setter.在转换后的代码中,还会有属性的版本号以及添加到getter和setter的附加代码.您需要将事务中读取的每个属性的版本记录为事务"读取集".您可以通过让每个getter将所看到的属性版本添加到threadlocal链表中来实现.您还需要在线程局中将写入缓冲为"写入集",直到您提交为止.请注意,如果您有一个给定字段,则getter方法需要检查并返回给定字段的threadlocal写入设置值.这样你就可以在你的读取中看到未提交的写入,但在你提交之前没有其他线程会看到它们.

在提交时,您将对要编写的每个属性执行写锁定.虽然您有锁,但请仔细检查您的读数是否仍然有效; 您在事务中读取的属性尚未由另一个事务更新到更高版本.如果是这样,那么您的业务逻辑可能无效,因为您可能具有不一致的读取,因此您需要回滚整个事务.如果最后的检查通过,那么你通过刷新你的写集来提交,删除这些属性的版本,释放写锁,最后清除写集和读集线程局列表.

本文解释说,如果检测到自tx开始以来已经写入了正在读取的属性,该算法可以提前中止.本文有一些巧妙的技巧来加速只读事务.它甚至可以解决哪些块是只读的以及哪些块是读写的技巧.任何对这类事情表示兴趣的人都应该享受这两篇论文.

上面的论文中的Deuce框架展示了如何通过在加载时将新的java字节码注入到类中来更改所有getter和setter.其他语言可以有一个特殊的编译器或预处理器,它们将普通代码执行相同的机械转换为STM启用的代码.特别是使用Deuce,您的源代码对象可以具有简单的getter setter对,但是在运行时转换的类已经丰富了进行书本工作的getter setter.

将常规代码转换为STM代码(特别是在运行时)很有趣,但如果您需要实际编写支持STM的数据结构,则不需要任何魔术酱.相反,只需创建一个Ref带有a get()和a 的类,并set(x)在由Ref句柄组成的数据结构对象之间建立每个关系.在您get和set您的Ref班级中,您可以完成线程本地书籍.然后,您可以实现简单版本的"TL2"或任何其他适用于您的数据结构以及读取与写入并发的算法.

这也似乎表明,就像任何其他"锁定"解决方案一样,您希望保持关键部分尽可能小(以减少冲突的可能性),我是对的吗？

TL2具有保持写锁定然后进行最终检查和写入的关键时期,这很容易理解和优化,而无需了解应用程序业务逻辑.如果为每个数字分配一个唯一的属性,则可以通过按升序获取锁来轻松避免死锁.值得注意的是,假设提交检查将通过,所有业务逻辑都是以推测方式完成的.在执行任意缓慢的业务逻辑时,您不会持有锁.您可以进行多个Web服务查找或减慢数据库调用,并且在提交之前不会进行任何锁定.显然,专业人士将调整通用关键部分.

本文明确指出,该算法可能会更频繁地中止特定业务逻辑所需的.通用算法不知道特定脏读是否不会影响实际写入结果.理解实际业务逻辑的手写逻辑可以知道在给定的脏读取集不需要回滚时的特殊情况.但是,如果您要编写大量代码,并且应用程序中回滚的可能性非常低,则通用机械STM方法可能会导致更少的错误并且性能良好.

此外,STM可以简单地检测"在执行计算时进入该区域的另一个线程,因此计算无效"或者它是否可以实际检测是否使用了破坏的值(因此运气时有时两个线程可以同时执行相同的临界区需要回滚)？

TL2方法的全部内容与读取或写入的数据无关,而是与执行此操作的代码有关.这是你得到和设定的,重要的; 以及在刷新所有写入之前是否有任何其他线程在你的脚趾上行走.代码所需要的只是您拥有a begin(),commit()并且rollback()在业务逻辑中启动,结束和中止事务.即便如此,也可以生成代码.使用Java,您可以使用方法上的@Transactional注释标记您的方法,然后生成代码,这些代码将您的方法调用包装在try/catch/finally中,将begin/commit/rollback作为idiomic java.Deuce在类加载时注入这样的逻辑.

再一次,您不需要在您自己的启用STM的数据结构中开始/提交/回滚这样的魔术酱.您可以明确地将所有内容放入数据结构逻辑代码中,以在任何OO语言中创建您自己的显式启用STM的类.

Answer 2

最简单的答案是"它取决于".有许多根本不同的实现以几乎任何可想象的方式工作.

对我来说神秘的部分是,给定一些任意代码块,您需要一种方法可以在之后返回并确定每个步骤中使用的值是否有效.你是怎么做到的,你如何有效地做到这一点？

一种解决方案是使用版本控制.每次修改对象时,都会更新其版本号.在事务运行时,您验证每个访问对象的版本,并在事务提交时验证对象是否仍然有效.此验证可以是简单的整数比较(如果transaction_start_version >= object_version对象有效),因此可以相当有效地完成.

这也似乎表明,就像任何其他"锁定"解决方案一样,您希望保持关键部分尽可能小(以减少冲突的可能性),我是对的吗？

很可能.我认为一些实现已经走了假设/要求一切都是事务的路线,但是,在大多数实现中,事务是特别标记的代码块,事务运行的时间越长,冲突的可能性就越大.导致事务回滚.

此外,STM可以简单地检测"在执行计算时进入该区域的另一个线程,因此计算无效"或者它是否可以实际检测是否使用了破坏的值(因此运气时有时两个线程可以同时执行相同的临界区需要回滚)？

后者.请记住,TM中的想法是保护数据而不是代码.

不同的代码路径可以访问不同事务中的相同变量.这必须由TM系统检测.没有"这个区域"的真实概念,因为它指的是代码而不是数据.TM系统不关心正在执行什么代码,它跟踪正在修改的数据.这样,它完全不同于关键部分(保护代码而不是数据)

Answer 3

GHC的STM实现在第六部分中描述:

可组合内存事务.Tim Harris,Simon Marlow,Simon Peyton Jones,Maurice Herlihy.PPoPP'05:ACM SIGPLAN平行规划原理与实践研讨会,2005年6月,伊利诺伊州芝加哥市

第五节:

具有数据不变量的事务性内存.蒂姆哈里斯,西蒙佩顿琼斯.2006年3月TRANSACT '06