c++ - 在线程编程中保护简单列表？

Question

我正在阅读一本 POSIX 线程书籍以进行一些练习，并且我试图找出在一个简单的单链表中我需要互斥保护的地方作为一个小练习题。例如，如果我有一个节点结构列表:

template <typename T>
struct Node
{
    Node<T>* next;
    T data;
};

Node<T>* head = NULL;

//Populate list starting at head...


[HEAD] --> [NEXT] --> [NEXT] --> [NEXT] --> [...] --> [NULL]

我有两个或更多线程。任何线程都可以在列表中的任何位置插入、删除或读取。

似乎如果你只是试图保护单个列表元素(而不是整个列表)，你永远不能保证另一个线程不会修改下一个*指针指向的那个，所以你不能保证安全和维护的不变量。

有没有比让对它的所有操作都使用相同的互斥锁更有效地保护这个列表的方法？我本来以为有，但我真的想不到。

另外，如果它是双向链表，情况会改变吗？

Answer 1

如果您想使用单向链表执行细粒度锁定方法(即每个节点一个锁)，那么您需要执行以下操作:

1. 将两个哨兵节点添加到 head 的列表中和 tail .这两个节点都有与之关联的锁，每个新节点都将添加到它们之间。
2. 对于遍历列表的所有函数，在将下一个节点分配给 current 之前，您需要获得对下一个节点的锁定。指针。在获得下一个节点的锁之前，您也不能释放当前节点的锁。如果您还使用 prev遍历的指针，您将保持对该“前一个”节点的锁定，直到您重新分配 prev指向 current 的指针指针。
3. 要添加一个节点，您需要锁定将位于您要添加的节点两侧的两个节点。因此，例如，您将有一个 prev节点指针，和一个 current节点指针。您将首先锁定 prev 上的互斥体。节点，然后锁定 current 上的互斥锁节点，并在 prev 之间添加新节点和 current节点。
4. 如果你要删除一个节点，你会再次锁定 prev 中的互斥体。和 current节点(按此顺序)，然​​后您可以删除 current节点。

请记住，第 3 步和第 4 步之所以有效，是因为第 2 步遍历列表需要获取节点上的锁。如果您跳过该步骤，您将最终创建悬挂指针和其他与错误分配指针相关的问题，因为另一个线程更改了当前线程下列表的拓扑结构。