3

我已经阅读了两个完全不同的关于 STM 是如何实现的说明。也许两者都是有效的,或者一个是错误的,我希望有人能阐明。

采取 1(维基百科):允许所有线程修改共享内存,但事务中的每次读取和写入都会被记录。在事务结束时,系统检查其他线程是否没有同时对内存进行更改。如果未进行任何更改,则提交事务。否则,重新启动事务。

  • 问:如果这是一个有效的实现,那么允许两个线程在同一个事务中执行似乎是没有用的。他们将读取彼此的写入,并且交易块内的计算将是错误的。

取2(找不到源):当程序进入事务时,它会获取其中包含的所有变量的副本,并且可以对它们进行访问。在事务结束时,系统尝试用副本更新主控。如果自第一次复制后 master 没有更改,则提交事务。否则,重新启动事务。

另外,当两个线程同时进入同一个事务时会发生什么?这不会导致某种竞争条件吗?由于两者都试图修改相同的共享内存,因此两者都需要重新启动并且问题会无限期地继续下去,除非系统介入并告诉一个线程对其进行冷却(有点像锁=)我确定我是这里缺少一个概念。

4

2 回答 2

3

我不是专家,但读过几篇论文。与新技术提案一样,看起来一个小组提出了 STM,但其他​​小组的后续工作着眼于变体。不止你说的那两个。例如,这篇论文给出了一种在事务上具有阻塞锁的机制,而不是在你的两个中都采用积极的非阻塞方法:http: //pages.cs.wisc.edu/~david/courses/cs758/Fall2007/papers/ saha-mcrt-ppopp-2007.pdf 实现技术中唯一的共同点似乎是类似于数据库的事务语义。因此,研究的核心问题是这些语义是否会导致更好的程序和/或更高的效率。它们的实施方式有待商榷。

另外,当两个线程同时进入同一个事务时会发生什么?这不会导致某种竞争条件吗?由于两者都试图修改相同的共享内存,因此都需要重新启动...

并不真地。系统总是会取得进展,因为当 2 个或更多提交发生冲突时,日志允许将所有提交回滚到冲突事务开始的点。然后可以允许线程继续执行并按顺序提交。没错,这会导致重复工作,尤其是当单个对象需求量很大时。然而,只有当它比上下文交换更昂贵时,避免这种情况才是值得的。STM 的人打赌内存冲突是比较少见的。维基百科的方案在这个假设上特别激进。

于 2012-06-13T02:30:16.173 回答
1

这是一个答案的链接,其中概述了 TL2 STM 算法,并提供了几篇关于实现它以及如何将普通代码机械地转换为 STM 代码的相当易读的论文的链接:

Stackoverflow:您如何实现软件事务内存?

显然,这是一个活跃的研究领域,因此有很多方法。对给定问题最有效的方法取决于手头问题的并发性和读/写比率。

关于 TL2 算法,您的问题:

...允许两个线程在同一个事务中执行似乎没用。他们将读取彼此的写入,并且交易块内的计算将是错误的。

它是关于在事务期间看到什么数据(读取集)或更新(写入集),而不是它们正在执行什么代码。TL2 算法允许进行推测性工作,而无需持有任何锁,保持写入集对每个线程都是私有的,直到提交。在提交时,事务获取写锁,然后执行最终版本检查读取集版本是否仍然匹配主值版本(公共提交值),然后再将更新刷新到主值以增加其版本。当然,事务可以在提交之前看到它自己的私有更新和任何提交的主值,但不同的 tx 看不到彼此未刷新的写入集。如果其他一些事务同时提交并更改了读取集中看到的主版本,则 tx 被中止。这在应用程序逻辑运行时强制保持一致性而不持有锁。上面链接中的论文有更多的细节和优化。

另外,当两个线程同时进入同一个事务时会发生什么?这不会导致某种竞争条件吗?

是的,如果线程正在读取另一个线程将更新的值,那么线程在执行不同的工作时会与 TL2 竞争。由于在最终一致性检查中中止,工作可能会被丢弃。当发生这种情况时,您应该编写代码重试多次,直到您获得一致的读取,最终导致成功提交。希望是,如果您的服务器上有许多内核,您将通过偶尔丢弃内核的工作来获得比使用阻塞内核的粗粒度锁更多的总吞吐量。另一个希望是 STM 可以比手工制作避免死锁的最佳细粒度锁定方法更直接。显然,吞吐量取决于实际的应用程序逻辑和冲突。

由于两者都试图修改相同的共享内存,因此两者都需要重新启动并且问题会无限期地继续下去,除非系统介入并告诉一个线程对其进行冷却(有点像锁=)

您提到的活锁是通过在提交时锁定主值来避免的。以主值内存地址的升序内存顺序获取所有锁,您将不会出现死锁。两个线程之一将首先获得它需要的所有锁。另一个会阻塞。然后第一个线程将执行其读取集一致性检查,刷新它的写入集以增加主值,然后释放锁。第二个线程最终将获得它的所有锁,然后执行其读取集一致性检查,并由于看到该线程增加了它在其应用程序逻辑中使用的主值的版本而中止事务。

显然,这种提交时间锁定策略会阻塞线程,但不会在任意应用程序逻辑运行时保持锁定。这个关键部分可以积极调整。这些论文甚至提到了处理器指令,这些指令要求线程在持有这些锁的同时不间断地运行。

于 2012-09-09T14:20:09.430 回答