这是一个答案的链接,其中概述了 TL2 STM 算法,并提供了几篇关于实现它以及如何将普通代码机械地转换为 STM 代码的相当易读的论文的链接:
Stackoverflow:您如何实现软件事务内存?
显然,这是一个活跃的研究领域,因此有很多方法。对给定问题最有效的方法取决于手头问题的并发性和读/写比率。
关于 TL2 算法,您的问题:
...允许两个线程在同一个事务中执行似乎没用。他们将读取彼此的写入,并且交易块内的计算将是错误的。
它是关于在事务期间看到什么数据(读取集)或更新(写入集),而不是它们正在执行什么代码。TL2 算法允许进行推测性工作,而无需持有任何锁,保持写入集对每个线程都是私有的,直到提交。在提交时,事务获取写锁,然后执行最终版本检查读取集版本是否仍然匹配主值版本(公共提交值),然后再将更新刷新到主值以增加其版本。当然,事务可以在提交之前看到它自己的私有更新和任何提交的主值,但不同的 tx 看不到彼此未刷新的写入集。如果其他一些事务同时提交并更改了读取集中看到的主版本,则 tx 被中止。这在应用程序逻辑运行时强制保持一致性而不持有锁。上面链接中的论文有更多的细节和优化。
另外,当两个线程同时进入同一个事务时会发生什么?这不会导致某种竞争条件吗?
是的,如果线程正在读取另一个线程将更新的值,那么线程在执行不同的工作时会与 TL2 竞争。由于在最终一致性检查中中止,工作可能会被丢弃。当发生这种情况时,您应该编写代码重试多次,直到您获得一致的读取,最终导致成功提交。希望是,如果您的服务器上有许多内核,您将通过偶尔丢弃内核的工作来获得比使用阻塞内核的粗粒度锁更多的总吞吐量。另一个希望是 STM 可以比手工制作避免死锁的最佳细粒度锁定方法更直接。显然,吞吐量取决于实际的应用程序逻辑和冲突。
由于两者都试图修改相同的共享内存,因此两者都需要重新启动并且问题会无限期地继续下去,除非系统介入并告诉一个线程对其进行冷却(有点像锁=)
您提到的活锁是通过在提交时锁定主值来避免的。以主值内存地址的升序内存顺序获取所有锁,您将不会出现死锁。两个线程之一将首先获得它需要的所有锁。另一个会阻塞。然后第一个线程将执行其读取集一致性检查,刷新它的写入集以增加主值,然后释放锁。第二个线程最终将获得它的所有锁,然后执行其读取集一致性检查,并由于看到该线程增加了它在其应用程序逻辑中使用的主值的版本而中止事务。
显然,这种提交时间锁定策略会阻塞线程,但不会在任意应用程序逻辑运行时保持锁定。这个关键部分可以积极调整。这些论文甚至提到了处理器指令,这些指令要求线程在持有这些锁的同时不间断地运行。