如何实现软件事务内存？
https://stackoverflow.com/questions/1627600
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
就实际的低级原子指令和内存栅栏（我假设它们被使用）而言，您如何实现STM？
对我来说神秘的部分是，给定一些任意的代码块，您需要一种方法来返回并确定每个步骤中使用的值是否有效。您如何做到这一点以及如何有效地做到这一点？这似乎也表明，就像任何其他“锁定”解决方案一样，您希望使关键部分尽可能小（以减少冲突的可能性），我是对的吗？
另外，STM 是否可以简单地检测“在执行计算时另一个线程进入该区域，因此计算无效”，或者它是否可以实际检测是否使用了破坏值（因此幸运的是，有时两个线程可以同时执行相同的关键部分，而无需需要回滚）？
解决方案
最简单的答案是“它取决于”。有很多完全不同的实现工作几乎可以想象的任何方式。
对我来说神秘的部分是，给定一些任意代码块，您需要一种方法可以在之后返回并确定每个步骤中使用的值是否有效。你是如何做到这一点的，你如何有效地做到这一点？
一种解决方案是使用版本控制。每次修改对象时，都会更新其版本号。在事务运行时，您将验证每个访问对象的版本，并在事务提交时验证对象仍然有效。
此验证可以是简单的整数比较（如果 transaction_start_version＆gt; = object_version ，对象有效），因此可以相当有效地完成。
这也似乎表明，就像任何其他“锁定”解决方案一样，您希望保持关键部分尽可能小（以减少冲突的可能性），我是对的吗？
非常可能。我认为一些实现已经走了假设/要求所有成为事务的路线，但是，在大多数实现中，事务是特别标记的代码块，并且事务运行的时间越长，冲突可能导致交易回滚的可能性。
此外，STM可以简单地检测“在执行计算时进入该区域的另一个线程，因此计算无效”。或者它是否可以实际检测是否使用了破坏的值（因此运气时有时两个线程可以同时执行相同的临界区而无需回滚）？
后者。请记住，TM中的想法是保护数据，而不是代码。
不同的代码路径可以访问不同事务中的相同变量。这必须由TM系统检测。没有“这个区域”的真实概念，因为它指代码而不是数据。 TM系统不关心正在执行什么代码，它跟踪正在修改的数据。这样，它完全不同于关键部分（保护代码而不是数据）
其他提示
有些论文真的很难读，但有两篇非常简洁明了：
Transactional Locking II，Dave Dice，Ori Shalev，Nir Shavit 描述“TL2”表示“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链表中来实现。您还需要将写入缓冲为“写入集”。在一个threadlocal中直到你提交。请注意，如果您有一个给定字段，则getter方法需要检查并返回给定字段的threadlocal写入设置值。这样你就可以在你的读取中看到未提交的写入，但在你提交之前没有其他线程会看到它们。
在提交时，您将针对要编写的每个属性执行写锁定。虽然您有锁，但请仔细检查您的读数是否仍然有效;您在事务中读取的属性尚未由另一个事务更新到更高版本。如果是这样，那么您的业务逻辑可能无效，因为您可能具有不一致的读取，因此您需要回滚整个事务。如果最后的检查通过，那么你通过刷新你的写集来提交，删除这些属性的版本，释放写锁，最后清除写集和读集线程局列表。
该论文解释说，如果检测到自tx开始以来已经写入了正在读取的属性，该算法可以提前中止。本文有一些巧妙的技巧来加速只读事务。它甚至可以解决哪些块是只读的以及哪些块是读写的技巧。任何对这类事情表示兴趣的人都应该享受这两篇论文。
上面的论文中的Deuce框架展示了如何通过在加载时将新的java字节码注入到类中来更改所有getter和setter。其他语言可以有一个特殊的编译器或预处理器，它们将普通代码执行相同的机械转换为STM启用的代码。特别是使用Deuce你的源代码对象可以有简单的getter setter对，但是在运行时转换的类已经丰富了getter setter
GHC 的STM实施在第六部分中描述：
可堆叠内存交易。 Tim Harris，Simon Marlow，Simon Peyton Jones，Maurice Herlihy。 PPoPP'05：ACM SIGPLAN并行编程原理与实践研讨会，2005年6月，伊利诺伊州芝加哥
第五节：
交易记忆与数据不变量。蒂姆哈里斯，西蒙佩顿琼斯。 2006年3月TRANSACT '06
我建议您观看此演示文稿： http：// www。 infoq.com/presentations/Value-Identity-State-Rich-Hickey
在下半部分，它解释了如何在不将值保留在未定义状态的情况下更新值。例如 - 如果您想要以STM样式更新树，则根本不会更改以前的版本。假设 tree 是指向树根的指针。您创建的唯一内容是更改的节点（但它们可以引用树的原始快照中的节点。
然后在树指针上进行比较和交换。如果成功，那么每个人现在都会看到你的新树，而旧的树可以被垃圾收集。如果没有，那么你重复这个过程，你刚刚构建的树被垃圾收集。
最大的想法是，在实际交换新旧值之前，您不需要检测是否有其他人更改了树，因此没有“冲突”。或“破坏价值”或“破坏价值”来自典型的多线程编程。
