使用细粒度方法线程安全地删除链表节点

Question

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

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

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

Answer 1

我假设您正在谈论单链表,因为您从未在节点删除中指定'prev'.给定一个单独链接的节点列表,每个节点都由一个锁保护,它可能描述如下:

Head ==> A ==> B ==> C ==> D ==> Tail
               ^     ^
               |     |
        Thread 1     Thread 2

假设线程1将删除节点B.巧合的是,线程2将尝试同时删除节点C. 您提供的步骤可能执行如下:

Thread 1                Thread 2
----------------------  ----------------------
Lock B                  Lock C
A->next = C or D; <=??  B->next = D;    <== B could be dead already
B->next = NULL;         C->next = NULL;
B->deleted = 1;         C->deleted = 1;
Unlock B                Unlock C

在这种情况下,结果是不可预测的.如果线程2稍微超过线程1执行,那么一切都应该没问题.线程1的第二行将执行"A-> next = D",因为线程2已经改变了D-旁边的B->但是,如果线程1稍微超前于线程2,那么A-> next指向死节点C ,死节点B被修改,节点D丢失.

因此,您可能会尝试锁定要删除的节点,然后在修改之前锁定"prev".步骤可以执行如下:

Thread 1                Thread 2
----------------------  ----------------------
Lock B                  Lock C
Lock A                  waiting for B
A->next = C;            waiting for B
Unlock A                waiting for B
B->next = NULL;         waiting for B
B->deleted = 1;         waiting for B
Unlock B                Lock B         <= locking dead node
                        B->next = D;   <= assigning to dead node
                        Unlock B
                        C->next = NULL;
                        C->deleted = 1;
                        Unlock C

所以,这仍然不是线程安全的.A->接下来指向死节点C,死节点B被锁定并使用,并且D丢失.我们所做的就是确保上面的错误情况可靠地发生.

在锁定要删除的节点之前,这里的解决方案似乎需要锁定'prev' .

Thread 1                Thread 2
----------------------  ----------------------
Lock A                  Lock B
waiting for B           Lock C
waiting for B           B->next = D;
Lock B                  Unlock B  
A->next = D;            C->next = NULL;
Unlock A                C->deleted = 1;
B->next = NULL;         Unlock C
B->deleted = 1;         
Unlock B                

A->下一个指向D,现在删除B和C.

Answer 2

你可能想看看这个演示文稿.从幻灯片#39开始,它以清晰和具象的方式演示了如何实现细粒度的链表锁定(幻灯片的注释也添加了一些解释).该演示文稿基于(或取自......)一本名为"多处理器编程艺术"的书.

Answer 3

它是线程安全的假设你锁定的范围(这意味着什么锁定,没什么可在C中使用的官方术语"范围"做)是足够大的.

如果它只锁定当前节点p,那么你不能依赖其他线程不进入和prev/ head或(或者tail就此而言)并因此削弱你.

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

我们无法从给出的代码中告诉您锁的范围,但我会提到另一个(无关的)事情.

您可能应该免费p或将其添加到免费列表中以便重复使用.只需将其next指针设置为null并将其deleted标志设置为1,就无法在需要重用它时找到它.这将导致内存泄漏.可能是这样做的代码没有显示,但我想我会提到它,以防万一.

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

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

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

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

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

但是在尝试改变任何东西之前你必须锁定所有三个.

这甚至会阻止它进行并发插入操作,只要插入锁定插入点两侧的两个"节点",当然,它们将它们锁定在同一方向上.

不确定在列表上迭代的程度如何.你可能可以使用一个系统,你最初锁定head变量和第一个节点,然后释放head.

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

但是,最重要的是,即使使用细粒度的锁定范围,您也可以确保线程安全.