我正在阅读一本 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]
我有两个或更多线程。任何线程都可以在列表中的任何点插入、删除或读取。
看来,如果您只是尝试保护单个列表元素(而不是整个列表),您永远无法保证另一个线程不会修改 next* 指针指向的元素,因此您无法保证不变量的安全性和维护。
有没有比让其上的所有操作都使用相同互斥锁更有效的方法来保护此列表?我本来以为会有,但我实在想不到。
另外,如果它是一个双向链表,情况会改变吗?
如果您想使用单链表(即每个节点一个锁)执行细粒度锁定方法,那么您将需要执行以下操作:
- 将两个哨兵节点添加到列表中
head
and tail
。这两个节点都有与之关联的锁,每个新节点都会添加到它们之间。
- 对于遍历列表的函数,在将下一个节点分配给其他节点之前,您需要获得下一个节点的锁。
current
指针。在获得下一个节点上的锁定之前,您也无法释放当前节点上的锁定。如果您还使用prev
遍历的指针,您将保持对该“前一个”节点的锁定,直到您重新分配prev
指向的指针current
指针。
- 要添加节点,您需要锁定要添加的节点两侧的两个节点。例如,你会有一个
prev
节点指针,和一个current
节点指针。您首先需要将互斥锁锁定在prev
节点,然后锁定互斥锁current
节点,并在之间添加新节点prev
and current
node.
- 如果要删除节点,您将再次锁定互斥体
prev
and current
节点(按该顺序),然后您可以删除current
node.
请记住,步骤 #3 和步骤 #4 之所以有效,是因为步骤 #2 中遍历列表需要获取节点上的锁。如果跳过该步骤,当另一个线程更改当前线程下列表的拓扑时,您最终将创建悬空指针以及与错误分配的指针相关的其他问题。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)