在线程编程中的Guard简单列表？ [英] Guard simple list in threaded programming?

问题描述

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

I'm reading a POSIX threading book for some practice, and I was trying to work out where I'd need mutex guards in a simple singly-linked list as a little practice problem. For example, if I had a list of node structures:

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

Node<T>* head = NULL;

//Populate list starting at head...


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

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

and I had two or more threads. Any thread can insert, delete, or read at any point in the list.

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

It seems if you just try and guard individual list elements (and not the whole list), you can never guarantee another thread isn't modifying the one the next* pointer points to, so you can't guarantee safety and maintenance of invariants.

有效的方式来保护这个列表，使其上的所有操作使用相同的互斥？

Is there any more efficient way to guard this list than making all operations on it use the same mutex? I would have thought there was but I really can't think of it.

此外，如果是双向链表，情况会发生变化？

Also, if it were a doubly linked list does the situation change?

推荐答案

如果你想用单链表（即每个节点一个锁）做一个细粒度锁定方法，那么你将需要要执行以下操作：

If you want to-do a fine-grained locking approach with a singly linked list (i.e., one lock per node), then you will need to-do the following:

1. 将头添加两个哨兵节点和 tail 。这两个节点都有与它们相关联的锁，每个新节点将在它们之间添加。


2. 对于遍历列表的函数，您需要获取下一个节点，然后将其分配给当前指针。您还不能释放当前节点上的锁定，直到您获得下一个节点上的锁定。如果您还使用 prev 指针进行遍历，则您将在上一个节点上保留锁定，直到重新分配 prev 指向当前指针。


3. 要添加一个节点，您需要锁定两个节点将要在您添加的节点的任一侧。例如，你会有一个 prev 节点指针，和一个 current 节点指针。首先在 prev 节点上锁定互斥锁，然后在当前节点上锁定互斥锁， prev 和当前节点之间的新节点。


4. 正在删除一个节点，您将再次在 prev 和 current 节点中锁定互斥体您可以删除当前节点。

1. Add two sentinel nodes to the list for the head and tail. Both these nodes have locks associated with them, and every new node will be added between the two of them.
2. For ever function that traverses the list, you need to obtain a lock on the next node before you assign it to a current pointer. You also cannot release the lock on the current node until you've obtained the lock on the next node. If you are also using a prev pointer for traversal, you will keep the lock on that "previous" node until you re-assign the prev pointer to the current pointer.
3. For adding a node, you will need to lock the two nodes that are going to be on either side of the node you're adding. So for instance, you would have a prev node pointer, and a current node pointer. You would first lock the mutex on the prev node, and then lock the mutex on the current node, and add the new node in-between the prev and current node.
4. If you are removing a node, you would again lock the mutex in the prev and current node (in that order) and then you can remove the current node.

请记住，和＃4工作，因为步骤＃2，其中遍历列表需要获得节点上的锁。如果你跳过这一步，你将最终创建悬挂指针和其他与错误分配的指针相关的问题，因为另一个线程改变了当前线程下的列表的拓扑。

Keep in mind that steps #3 and #4 work because of step #2 where traversing the list requires obtaining locks on the nodes. If you skip that step, you will end up creating dangling pointers and other problems related to mis-assigned pointers as another thread changes the topology of the list underneath the current thread.

这篇关于在线程编程中的Guard简单列表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！