使用细粒度方法对链接列表节点进行线程安全删除 [英] 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或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屋！