使用C / C ++进行乐观读取和锁定STM（软件事务内存）

I've been doing some research on STM (software transactional memory) implementations, specifically on algorithms that utilize locks and are not dependent on the presence of a garbage collector in order to maintain compatibility with non-managed languages like C/C++. I've read the STM chapter in Herlihy and Shavit's "The Art of Multiprocessor Programming", as well as read a couple of Shavit's papers that describe his "Transactional Locking" and "Transactional Locking II" STM implementations. Their basic approach is to utilize a hash-table that stores the values of a global version-clock and a lock to determine if a memory location has been touched by another thread's write. As I understand the algorithm, when a writing transaction is performed, the version-clock is read and stored in thread-local memory, and a read-set and write-set are also created in thread-local memory. Then the following steps are performed:

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

1. The values of any addresses read are stored in the read-set. This means that the transaction checks that any locations being read are not locked, and they are equal to or less than the locally stored version clock value.

读取的任何地址的值都存储在读取集中。这意味着事务检查正在读取的任何位置未被锁定,并且它们等于或小于本地存储的版本时钟值。

2. The values of any addresses written are stored in the write-set, along with the values that are to be written to those locations.

写入的任何地址的值都存储在写集中,以及要写入这些位置的值。

3. Once the entire write-transaction is complete (and this can include reading and writing to a number of locations), the transaction attempts to lock each address that is to be written to using the lock in the hash-table that is hashed against the address' value.

一旦整个写入事务完成(并且这可以包括读取和写入多个位置),事务将尝试使用针对地址进行散列的散列表中的锁定来锁定要写入的每个地址。 '价值。

4. When all the write-set addresses are locked, the global version clock is atomically incremented and the new incremented value is locally stored.

当所有写入地址被锁定时,全局版本时钟以原子方式递增,并且新增加的值被本地存储。

5. The write-transaction checks again to make sure that the values in the read-set have not been updated with a new version-number or are not locked by another thread.

写入事务再次检查以确保读取集中的值尚未使用新版本号更新或未被另一个线程锁定。

6. The write-transaction updates the version-stamp for that memory location with the new value it stored from step #4, and commits the values in the write-set to memory

write-transaction使用从步骤#4存储的新值更新该内存位置的版本标记,并将写入集中的值提交到内存

7. The locks on the memory locations are released

释放内存位置上的锁

If any of the above check-steps fail (i.e., steps #1, #3, and #5), then the write-transaction is aborted.

如果上述任何检查步骤失败(即步骤#1,#3和#5),则中止写入事务。

The process for a read-transaction is a lot simpler. According to Shavit's papers, we simply

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

1. Read and locally store the global version-clock value

读取并本地存储全局版本时钟值

2. Check to make sure the memory locations do not have a clock value greater than the currently stored global version-clock value and also make sure the memory locations are not currently locked

检查以确保内存位置的时钟值不大于当前存储的全局版本时钟值,并确保内存位置当前未锁定

3. Perform the read operations

执行读取操作

4. Repeat step #2 for validation

重复步骤#2进行验证

If either step #2 or #4 fail, then the read-transaction is aborted.

如果步骤#2或#4失败,则中止读取事务。

The question that I can't seem to solve in my mind though is what happens when you attempt to read a memory location inside an object that is located in the heap, and another thread calls delete on a pointer to that object? In Shavit's papers, they go into detail to explain how there can be no writes to a memory location that has been recycled or freed, but it seems that inside of a read-transaction, there is nothing preventing a possible timing scenario that would allow you to read from a memory location inside of an object that is has been freed by another thread. As an example, consider the following code:

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

Thread A executes the following inside of an atomic read-transaction: linked_list_node* next_node = node->next;

线程A在原子读事务中执行以下内容:linked_list_node * next_node = node-> next;

Thread B executes the following: delete node;

线程B执行以下操作:删除节点;

Since next_node is a thread-local variable, it's not a transactional object. The dereferencing operation required to assign it the value of node->next though actually requires two separate reads. In between those reads, delete could be called on node, so that the read from the member next is actually reading from a segment of memory that has already been freed. Since the reads are optimistic, the freeing of the memory pointed to by node in Thread B won't be detected in Thread A. Won't that cause a possible crash or segmentation fault? If it does, how could that be avoided without locking the memory locations for a read as well (something that both the text-book as well as the papers denotes is unnecessary)?

由于next_node是线程局部变量,因此它不是事务对象。为其分配node-> next的值所需的解除引用操作实际上需要两个单独的读取。在这些读取之间,可以在节点上调用delete,以便下一个成员的读取实际上是从已经释放的一段内存中读取。由于读取是乐观的,因此线程B中节点指向的内存释放将不会在线程A中检测到。这不会导致可能的崩溃或分段错误吗?如果是这样的话,如何在不锁定读取的内存位置的情况下避免这种情况(教科书和论文表示的内容都是不必要的)?

1 个解决方案

#1

The simple answer is that delete is a side effect, and transactions do not play nice with side effects.

简单的答案是删除是副作用,而交易不能很好地处理副作用。

Logically, because transactions can be rolled back at any time, you can't deallocate memory in the middle of a transaction.

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

I don't think there is a single universal answer to "how this shall be handled", but a common approach is to defer the delete call until commit-time. The STM API should either do this automatically (for example providing their own delete function and requiring you to do that), or by giving you a hook where you can register "actions to perform on commit". Then during your transaction you can register an object to be deleted if and when the transaction commits.

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

Any other transaction working on the deleted object should then fail the version check and roll back.

处理已删除对象的任何其他事务应该无法通过版本检查并回滚。

Hope that helps. There isn't a simple answer to side effects in general. It's something each individual implementation will have to come up with mechanisms to handle.

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