同步对双向链表的访问

Question

我正在尝试在pthreads环境中实现C中的(特殊类型)双向链表,但是只使用C-wrapped同步指令,如原子CAS等,而不是pthread原语.(列表的元素是固定大小的内存块,几乎肯定不适合pthread_mutex_t它们内部.)我实际上并不需要完全任意的双向链表方法,只有:

• 插入列表末尾
• 从列表的开头删除
• 基于指向要移除的成员的指针在列表中的任意点处删除,该指针是从除了遍历列表之外的源获得的.

因此,描述此数据结构的更好方法可能是队列/ fifo,可以删除队列中的项目.

是否有标准方法来同步这个？我遇到了可能出现的死锁问题,其中一些问题可能是所涉及的算法所固有的,其他问题可能源于这样一个事实,即我正试图在有限的空间内工作,并对我能做的事情有其他限制.

编辑:特别是,如果要同时删除相邻的对象,我会坚持做什么.大概在删除对象时,您需要获取列表中上一个和下一个对象的锁定,并更新它们的下一个/ prev指针以指向彼此.但是如果任何一个邻居已经被锁定,这将导致死锁.我试图找出一种方法,任何/所有发生的删除可以走在列表的锁定部分,并确定当前正在删除过程中的最大子列表,然后锁定该子列表旁边的节点,以便整个子列表整体被移除,但我的头开始受伤.. :-P

结论(？):为了跟进,我确实有一些我想要工作的代码,但我也对理论问题感兴趣.每个人的答案都非常有用,并且结合了我在这里表达的限制之外的细节(你真的不想知道要删除的指针来自何处以及那里涉及的同步!)我现在决定放弃本地锁定代码并专注于:

• 使用大量较小的列表,每个列表都有单独的锁.
• 在获取锁定之前,最小化锁定所持有的指令数量并以内存(以安全的方式)戳戳,以减少在保持锁定时页面错误和缓存未命中的可能性.
• 测量人为负荷下的争用并评估这种方法是否令人满意.

再次感谢所有给出答案的人.如果我的实验不顺利,我可能会回到所概述的方法(特别是弗拉德),然后再试一次.

Answer 1

为什么不应用粗粒度的锁？只需锁定整个队列即可.

更精细(但不一定更有效,取决于您的使用模式)解决方案将分别使用读写锁定来进行读写.

对我来说,使用无锁操作似乎不是一个好主意.想象一下,某些线程正在遍历您的队列,同时删除"当前"项.无论您的遍历算法包含多少其他链接,所有项目都可能被删除,因此您的代码将无法完成遍历.

比较和交换的另一个问题是,使用指针,您永远不知道它是否真正指向相同的旧结构,或者旧结构已被释放,并且在同一地址分配了一些新结构.这可能是您的算法的问题,也可能不是.

对于"本地"锁定的情况(即,可以单独锁定每个列表项),一个想法是使锁定.对锁进行排序可确保无法实现死锁.所以你的操作是这样的:

通过指针p删除前一项:

1. 锁定p,检查(项目中可能使用特殊标志)项目仍在列表中
2. 锁定p->接下来,检查它是否为零并在列表中; 这样你就可以确保在此期间不会删除p-> next-> next
3. 锁定p-> next-> next
4. 在p->中设置一个标志,表示它不在列表中
5. (p-> next-> next-> prev,p-> next-> prev)=(p,null); (p-> next,p-> next-> next)=(p-> next-> next,null)
6. 释放锁

插入到开头:

1. 锁头
2. 在新项目中设置标志,指​​示它在列表中
3. 锁定新项目
4. 锁头 - >下一个
5. (head-> next-> prev,new-> prev)=(new,head); (new-> next,head)=(head,new)
6. 释放锁

这似乎是正确的,但我没有尝试这个想法.

从本质上讲,这使双链表工作就好像它是一个单链表.

如果你没有指向前一个列表元素的指针(当然通常就是这种情况,因为几乎不可能将这样的指针保持在一致状态),你可以执行以下操作:

通过指针c删除要删除的项目:

1. 锁定c,检查它是否仍然是列表的一部分(这必须是列表项中的标志),否则,操作失败
2. 获得指针p = c-> prev
3. 解锁c(现在,c可以被其他线程移动或删除,p也可以从列表中移动或删除)[为了避免重新分配c,你需要有一些像共享指针或至少一种这里列举项目的引用计数]
4. 锁定页
5. 检查p是否是列表的一部分(可以在步骤3之后删除); 如果没有,解锁p并从头重新开始
6. 检查p-> next是否等于c,如果没有,解锁p并从头开始重启[这里我们可以优化重启,不确定ATM]
7. 锁定p->下一个; 在这里你可以确定p-> next == c并且没有被删除,因为删除c将需要锁定p
8. 锁定p-> next-> next; 现在所有的锁都被拿走了,所以我们可以继续
9. 设置c不是列表的一部分的标志
10. 执行习惯(p-> next,c-> next,c-> prev,c-> next-> prev)=(c-> next,null,null,p)
11. 释放所有锁

请注意,只有指向某个列表项的指针无法确保该项未被释放,因此您需要进行一种引用计数,以便在您尝试锁定该项时不会销毁该项.

请注意,在最后一个算法中,重试次数是有界的.实际上,新项目不能出现在c的左侧(插入位于最右侧位置).如果我们的步骤5失败,因此我们需要重试,这只能通过同时从列表中删除p来引起.这样的移除可以发生不超过N-1次,其中N是列表中c的初始位置.当然,这种最坏的情况不太可能发生.

Answer 2

请不要严厉对待这个答案,但不要这样做.

你几乎肯定会遇到错误,并且很难发现错误.使用pthreads锁原语.他们是您的朋友,并且由深刻理解您选择的处理器提供的内存模型的人编写.如果你试图用CAS和原子增量等做同样的事情,你几乎肯定会犯一些你不会发现的微妙错误,直到它为时已晚.

这里有一个代码示例来帮助说明这一点.这个锁有什么问题？

volatile int lockTaken = 0;

void EnterSpinLock() {
  while (!__sync_bool_compare_and_swap(&lockTaken, 0, 1) { /* wait */ }
}

void LeaveSpinLock() {
  lockTaken = 0;
}

答案是:释放锁时没有内存障碍,这意味着锁中执行的某些写操作可能在下一个线程进入锁之前没有发生.哎呀!(也可能存在更多错误,例如,该函数不会在自旋循环内执行适合平台的产量,因此极大地浪费了CPU周期.&c.)

如果将双链表实现为带有sentinal节点的循环列表,则只需要执行两个指针分配以从列表中删除项目,并且只需要四个添加项目.我相信你能负担得起这些指针分配的写得很好的独占锁.

请注意,我假设您不是少数几个深刻理解记忆模型的人之一,因为世界上只有极少数记忆模型.如果你是这些人中的一员,那么即使你无法弄明白这一事实也应该表明它是多么棘手.:)

我也假设你问这个问题,因为你有一些你真正喜欢的代码.如果这只是一个学术练习,以便更多地了解线程(可能作为成为深层低级并发专家的一步),那么无论如何,请忽略我,并对内存细节进行研究您要定位的平台模型.:)