zwo*_*wol 4 c algorithm concurrency data-structures
我需要一个满足这些有点不寻常(AFAIK)要求的数据结构:
当然,最后一项要求是杀手.我有一个玩具实现,它会在全局链表中引发全局锁定,但如果信号处理程序中断了一个关键部分,那将会死锁.
(我知道在信号处理程序中执行任何代码的所有问题;出于这个问题的目的,让我们关注如何在可能中断插入或删除时使ForAll崩溃和死锁安全.)
如果这些集通常很小,那么在Insert和Delete方法中对列表的线性搜索足够快,那么您可以使用使用compare-and-swap的无锁链表实现.搜索提供了许多解释和示例.
http://www.google.com/search?q=lock+free+linked+list
列表的所有更新都是作为原子操作(比较和交换)完成的,因此中断不会导致问题.