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

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 已经将 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”。

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 都被删除了。