您如何实现软件事务存储? [英] How do you implement Software Transactional Memory?

问题描述

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

In terms of actual low level atomic instructions and memory fences (I assume they're used), how do you implement STM?

对我来说，神秘的部分是，给定了一些任意的代码块，您需要一种回溯的方法，然后确定每个步骤中使用的值是否有效.您如何做到这一点，以及如何有效做到这一点?这似乎还暗示着，就像任何其他锁定"解决方案一样，您希望将关键部分保持尽可能小(以减少冲突的可能性)，对吗?

The part that's mysterious to me is that given some arbitrary chunk of code, you need a way to go back afterwards and determine if the values used in each step were valid. How do you do that, and how do you do it efficiently? This would also seem to suggest that just like any other 'locking' solution you want to keep your critical sections as small as possible (to decrease the probability of a conflict), am I right?

此外，STM是否可以简单地检测执行计算时另一个线程进入了该区域，因此该计算无效"，或者它可以实际检测是否使用了破坏性的值(因此，幸运的是，有时两个线程可以执行相同的关键操作部分同时进行，而无需回滚)?

Also, can STM simply detect "another thread entered this area while the computation was executing, therefore the computation is invalid" or can it actually detect whether clobbered values were used (and thus by luck sometimes two threads may execute the same critical section simultaneously without need for rollback)?

推荐答案

最简单的答案是取决于".有成千上万种根本不同的实现，几乎可以想象得到.

The simplest answer is "it depends". There are tons of radically different implementations working in pretty much any way imaginable.

对我而言，神秘的部分是，给定了一些任意的代码块，您需要一种回溯的方式来确定每个步骤中使用的值是否有效.您如何做到这一点，以及您如何有效地做到这一点?

The part that's mysterious to me is that given some arbitrary chunk of code, you need a way to go back afterward and determine if the values used in each step were valid. How do you do that, and how do you do it efficiently?

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

One solution is to use versioning. Every time an object is modified, its version number is updated. While the transaction is running, you validate each accessed object's version, and when the transaction commits, you verify that the objects are still valid. This validation can be a simple integer comparison (if transaction_start_version >= object_version, the object is valid), so it can be done fairly efficiently.

这似乎还暗示着，就像任何其他锁定"解决方案一样，您希望将关键部分保持尽可能小(以减少发生冲突的可能性)，对吗?

This would also seem to suggest that just like any other 'locking' solution you want to keep your critical sections as small as possible (to decrease the probability of a conflict), am I right?

很有可能.我认为一些实现已经采用了假设/要求一切作为事务的途径，但是是的，在大多数实现中，事务都是经过特殊标记的代码块，并且事务运行的时间越长，则越大可能导致交易回滚的冲突机会.

Very likely. I think a few implementations have gone the route of assuming/requiring everything to be a transaction, but yes, in most implementations, transactions are specially marked chunks of code, and the longer a transaction runs, the larger the chance of a conflict that may cause transactions to roll back.

此外，STM是否可以简单地检测执行计算时另一个线程进入了该区域，因此该计算无效"，或者它可以实际检测是否使用了破坏性的值(因此，幸运的是，有时两个线程可以执行相同的关键操作部分同时进行，而无需回滚)?

Also, can STM simply detect "another thread entered this area while the computation was executing, therefore the computation is invalid" or can it actually detect whether clobbered values were used (and thus by luck sometimes two threads may execute the same critical section simultaneously without need for rollback)?

后者.请记住，TM中的想法是保护数据，而不是 code .

The latter. Keep in mind that the idea in TM is to protect data, rather than code.

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

Different code paths may access the same variable in different transactions. This has to be detected by the TM system. There's no real notion of "this area", since that refers to code, rather than data. The TM system doesn't care what code is executing, it tracks what data is being modified. In that way, it differs entirely from critical sections (which protect code, rather than data)

这篇关于您如何实现软件事务存储?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！