中断安全集扫描

Question

我需要一个数据结构来满足这些不寻常的(AFAIK)要求：

支持的操作有:插入(set，item)，删除(set，item)和ForAll(set，和Delete )。典型的情况是，集合中只包含一个item.

1. Implementation必须在C中是可行的；特别是，对于您来说没有垃圾收集。
2. ForAll必须安全地从异步信号处理程序执行，其调用可能中断了插入或删除.

。

当然，最后一个要求是杀手。我有一个玩具实现，它在全局链接列表周围抛出一个全局锁，但是如果信号处理程序中断了一个关键部分，就会陷入死锁。

(我知道在信号处理程序中执行任何代码时存在的所有问题；为了解决这个问题，让我们关注一下如何使ForAll崩溃和死锁在可能中断插入或删除时是安全的。)

Answer 1

如果集合通常很小，使得在Insert和Delete方法中对列表的线性搜索足够快，那么您可以使用使用比较和交换的无锁链接列表实现。搜索给出了一些解释和例子。

http://www.google.com/search?q=lock+free+linked+list

列表的所有更新都是作为原子操作(比较和交换)完成的，所以中断不会造成问题。

Answer 2

我相信Jim的方法很好，但是使用小集合和不频繁的更新，您可能更喜欢实现最简单的软件事务内存形式。

structure.

• Make

• 读取指向该版本的当前版本(该版本的副本)的指针，并在更新中更新it.

• Compare-and-swap。如果CAS失败，请返回步骤1.

异步扫描是琐碎的-读和走。如果没有垃圾收集，您将需要使用类似于SafeRead的内容，并从Jim链接的文件中发布。