使用C/C++进行乐观读取和锁定STM(软件事务存储器)

Question

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

1. 读取的任何地址的值都存储在读取集中.这意味着事务检查正在读取的任何位置未被锁定,并且它们等于或小于本地存储的版本时钟值.
2. 写入的任何地址的值都存储在写集中,以及要写入这些位置的值.
3. 一旦整个写入事务完成(并且这可以包括读取和写入多个位置),事务将尝试使用针对地址进行散列的散列表中的锁定来锁定要写入的每个地址. '价值.
4. 当所有写入地址都被锁定时,全局版本时钟以原子方式递增,并且新增加的值在本地存储.
5. 写入事务再次检查以确保读取集中的值尚未使用新版本号更新或未被其他线程锁定.
6. write-transaction使用从步骤#4存储的新值更新该内存位置的版本标记,并将写入集中的值提交到内存
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可以调用node,以便成员的读取next实际上是从已经释放的一段内存中读取.由于读是乐观的,内存的释放指向node中Thread B不会被检测到Thread A.这不会导致可能的崩溃或分段错误吗？如果是这样的话,如何在不锁定读取的内存位置的情况下避免这种情况(教科书和论文表示的内容都是不必要的)？

Answer 1

简单的答案是delete副作用,而且交易不能很好地应对副作用.

逻辑上,因为事务可以随时回滚,所以无法在事务中释放内存.

我不认为对"如何处理"有一个通用的答案,但一种常见的方法是将delete调用推迟到提交时间.STM API应该自动执行此操作(例如,提供自己的delete功能并要求您执行此操作),或者通过提供一个挂钩,您可以在其中注册"在提交时执行的操作".然后,在事务期间,您可以在事务提交时注册要删除的对象.

处理已删除对象的任何其他事务都应该通过版本检查和回滚失败.

希望有所帮助.一般来说,副作用没有一个简单的答案.这是每个单独的实现必须提出处理机制的东西.