13

我一直在对 STM（软件事务内存）实现进行一些研究，特别是关于利用锁且不依赖于垃圾收集器的存在的算法，以保持与 C/C++ 等非托管语言的兼容性。我已经阅读了 Herlihy 和 Shavit 的“多处理器编程艺术”中的 STM 章节，并阅读了 Shavit 的几篇描述他的“事务锁定”和“事务锁定 II”的论文STM 实现。他们的基本方法是利用存储全局版本时钟和锁的值的哈希表来确定内存位置是否已被另一个线程的写入触及。据我了解该算法，当执行写入事务时，版本时钟被读取并存储在线程本地内存中，并且还在线程本地内存中创建读取集和写入集。然后执行以下步骤：

  1. 读取的任何地址的值都存储在读取集中。这意味着事务检查正在读取的任何位置是否未锁定，并且它们等于或小于本地存储的版本时钟值。
  2. 写入的任何地址的值与要写入这些位置的值一起存储在写入集中。
  3. 一旦整个写入事务完成（这可能包括读取和写入多个位置），事务就会尝试使用哈希表中的锁锁定要写入的每个地址，该锁针对地址进行哈希处理' 价值。
  4. 当所有的写集地址都被锁定时，全局版本时钟原子地递增并且新的递增值被本地存储。
  5. 写入事务再次检查以确保读取集中的值没有用新的版本号更新或没有被另一个线程锁定。
  6. write-transaction 使用它在步骤 #4 中存储的新值更新该内存位置的 version-stamp，并将 write-set 中的值提交到内存
  7. 内存位置上的锁被释放

如果上述检查步骤中的任何一个失败（即步骤#1、#3 和#5），则写入事务被中止。

读取事务的过程要简单得多。根据 Shavit 的论文，我们简单地

  1. 读取并在本地存储全局版本时钟值
  2. 检查以确保内存位置的时钟值不大于当前存储的全局版本时钟值，并确保内存位置当前未锁定
  3. 执行读取操作
  4. 重复步骤 #2 进行验证

如果第 2 步或第 4 步失败，则中止读取事务。

不过，我似乎无法解决的问题是，当您尝试读取位于堆中的对象内的内存位置并且另一个线程调用delete指向该对象的指针时会发生什么？在 Shavit 的论文中，他们详细解释了如何不能对已回收或释放的内存位置进行写入，但似乎在读取事务内部，没有什么可以阻止可能的时序场景允许您从已被另一个线程释放的对象内部的内存位置读取。例如，考虑以下代码：

Thread A在原子读取事务中执行以下操作：linked_list_node* next_node = node->next;

Thread B执行以下操作：delete node;

由于next_node是线程局部变量，因此它不是事务对象。为它分配虽然的值所需的取消引用操作node->next实际上需要两次单独的读取。在这些读取之间，delete可以调用 on node，以便从成员next读取实际上是从已释放的内存段读取。node由于读取是乐观的，因此in指向的内存的释放Thread B不会被检测到 in Thread A。这不会导致可能的崩溃或分段错误吗？如果是这样，如果不锁定内存位置以供读取，如何避免这种情况（教科书和论文都表示这是不必要的）？

4

1 回答 1

5

简单的答案是这delete是一个副作用，而交易对副作用的影响不大。

从逻辑上讲，因为事务可以随时回滚，所以不能在事务中间释放内存。

我认为“如何处理”没有一个通用的答案，但一种常见的方法是将delete调用推迟到提交时间。STM API 应该自动执行此操作（例如提供它们自己的delete函数并要求您执行此操作），或者为您提供一个挂钩，您可以在其中注册“提交时执行的操作”。然后，在您的事务期间，您可以注册一个在事务提交时要删除的对象。

任何其他在已删除对象上工作的事务都应该无法通过版本检查并回滚。

希望有帮助。一般来说，副作用没有简单的答案。这是每个单独的实现都必须提出机制来处理的事情。

于 2011-12-08T12:54:16.610 回答