线程安全删除链表节点，使用细粒度方法 [英] Thread-safe deletion of a linked list node, using the fine-grained approach

问题描述

为什么以下用于删除链表中节点的代码段不是线程安全的?

Why is the following snippet for deleting a node in a linked list not thread safe?

注意每个节点都有自己的锁

edit: note every node has a lock of its own

// ... lock acquisition here
// ... assumption found to be valid here
prev->next = p->next;
p->next = NULL;
p->deleted = 1;

推荐答案

它是线程安全的，假设你的锁的作用域(意味着它锁定了什么，什么都不做)C) 中使用的官方术语范围"足够大.

It is thread safe assuming the scope of your lock (meaning what it locks, nothing to do with the official term "scope" used in C) is large enough.

如果它只锁定当前节点p，那么你就不能依赖其他没有进来的线程和prev(或head)code> 或 tail 就此而言)，因此削弱了你.

If it locks just the current node p, then you can't rely on other threads not coming in and playing with prev (or head or tail for that matter) and hence under-cutting you.

如果它锁定了整个结构，那么是的，它是线程安全的.

If it locks the entire structure, then yes, it is thread-safe.

我们无法从给定的代码中判断您的锁定范围，但我会提到另一件事(不相关).

We can't tell the scope of your lock from the code given but I will mention one other (unrelated) thing.

您可能应该免费 p 或将其添加到免费列表中以供重复使用.简单地将它的 next 指针设置为 null 并将它的 deleted 标志设置为 1 不会让你在需要重用它时找到它.这将导致内存泄漏.可能只是没有显示执行此操作的代码，但我想我会提到它，以防万一.

You should probably either free p or add it to a free list for re-use. Simply setting its next pointer to null and its deleted flag to 1 won't let you find it when you need to reuse it. That will lead to a memory leak. It may be that the code to do this just isn't shown but I thought I'd mention it, just in case.

根据您的编辑，您声明您使用的是细粒度方法(每个节点一个锁):

Based on your edit where you state you're using a fine-grained approach (one lock per node):

如果您锁定了您正在使用或更改的所有三个节点"，并且将它们锁定在一致的方向上，它仍然是线程安全的.

Provided you lock all three of the "nodes" that you're using or changing, and that you lock them in a consistent direction, it's still thread-safe.

我将节点"放在引号中，因为它也适用于 head 和 tail 指针.例如，如果要删除十节点列表中的第一个节点，则需要按顺序锁定 head 变量以及第一个和第二个节点.要删除单节点列表中的最后一个节点，您需要同时锁定 head 和 tail 变量和节点.

I put "nodes" in quotes since it also applies to the head and tail pointers. For example, if you want to delete the first node in a ten-node list, you need to lock the head variable and the first and second nodes, in that order. To delete the last node in a one-node list, you need to lock both the head and tail variables and the node.

锁定所有三个节点"将防止线程相互产生不利影响.

Locking of all three "nodes" will prevent threads from adversely affecting each other.

将它们锁定在一致的方向(例如从 head 到 tail)将防止死锁.

Locking them in a consistent direction (such as from head towards tail) will prevent deadlocks.

但是在尝试更改任何内容之前，您必须锁定所有三个.

But you have to lock all three before attempting to change anything.

如果插入锁定插入点任一侧的两个节点"，并且当然将它们锁定在同一方向，这甚至会阻止它进行并发插入操作.

This will even prevent it from concurrent insert operations provided the insert locks the two "nodes" on either side of the insertion point and, of course, locks them in the same direction.

不确定迭代列表的效果如何.您可能会使用一个系统，在该系统中您最初锁定 head 变量和第一个节点，然后释放 head.

Not sure how well iterating over the list would go though. You could probably get away with a system whereby you initially lock the head variable and the first node, then release head.

然后，当您完成该节点时，在释放当前节点之前锁定下一个.这样，您应该能够遍历列表而不受插入或删除的影响，而这种情况只会发生在您当前未使用的区域.

Then, when you've finished with that node, lock the next one before releasing the current one. That way, you should be able to iterate through the list without being affected by inserts or deletes, which can only happen in areas you're not currently working with.

但是，最重要的是您当然可以使其线程安全，即使使用细粒度的锁定范围也是如此.

But, the bottom line is that you can certainly make it thread safe, even with a fine-grained locking scope.

这篇关于线程安全删除链表节点，使用细粒度方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！