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

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

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

// ... lock acquisition here
// ... assumption found to be valid here
prev->next = p->next;
p->next = NULL;
p->deleted = 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 已经将 B->next 更改为 D。但是，如果线程 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->next指向死节点C，死节点B被锁定并使用，D丢失。我们所做的就是确保上述错误情况可靠地发生。

这里的解决方案似乎需要锁定“prev”before锁定要删除的节点。

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->next指向D，现在B和C都被删除了。