制作C哈希表的最佳策略,线程安全

编辑：

通常,无锁算法的工作方式如下：

>安排您的数据结构,以便对于您打算支持的每个函数,您可以在一个原子操作中确定其结果是否有效(即,其他线程未读取其??输入,因为它们已被读取并承诺;除非您提交,否则不会更改其他线程可见的状态.这将涉及利用特定于平台的功能,例如Win32的原子比较和交换或Cell的缓存行保留操作码.
>每个受支持的函数都会成为一个循环,重复读取输入并尝试执行工作,直到提交成功为止.

在争用率非常低的情况下,这是对锁定算法的性能优势,因为函数大多数是第一次成功,而不会产生获取锁的开销.随着争用的增加,收益变得更加可疑.

通常,可以原子操作的数据量很小 – 通常是32位或64位 – 因此对于涉及许多读取和写入的函数,生成的算法变得复杂并且可能很难推理.出于这个原因,最好是为您的问题寻找和采用成熟的,经过良好测试和易于理解的第三方无锁解决方案,而不是自己滚动.

Hashtable实现细节将取决于散列和表设计的各个方面.我们希望能够成长吗？如果是这样,我们需要一种方法将旧表中的批量数据安全地复制到新表中.我们是否期望哈希冲突？如果是这样,我们需要一些走路碰撞数据的方法.我们如何确保另一个线程不会删除返回它的查找与使用它的调用者之间的键/值对？也许某种形式的引用计数？ – 但谁拥有参考？ – 或者只是复制查找值？ – 但是如果价值很大怎么办？

无锁堆栈很容易理解,并且实现相对简单(从堆栈中删除一个项目,获取当前顶部,尝试用它的下一个指针替换它,直到你成功,返回它;添加一个项目,获得当前顶部并将其设置为项的下一个指针,直到您成功将指向该项的指针编写为新的顶部;在具有保留/条件写入语义的体系结构上,这就足够了,在仅支持CAS的架构上,您需要附加一个随机数或版本数字到原子操纵的数据,以避免ABA problem).它们是以原子锁自由方式跟踪密钥/数据的可用空间的一种方法,允许您将键/值对(实际存储在哈希表条目中的数据)减少到指针/偏移量或两个,一个小的使用您的架构的原子指令操纵足够的数量.还有其他人.

然后读取成为查找条目的情况,检查kvp与请求的密钥,执行任何操作以确保在我们返回它时保持有效值(获取副本/增加其引用计数),检查条目hasn自从我们开始读取以来已被修改,如果是这样,则返回值,撤消任何引用计数更改并重复读取(如果不是).
写作将取决于我们在碰撞方面所做的工作;在简单的情况下,它们只是找到正确的空槽并编写新的kvp的情况.
以上内容大大简化,不足以产生您自己的安全实现,特别是如果您不熟悉无锁/无等待技术.可能的并发症包括ABA问题,优先级倒置,特定线程的饥饿;我没有解决哈希冲突问题.

nbds页面链接到excellent presentation的真实世界方法,允许增长/碰撞.其他人存在,快速谷歌找到了很多论文.

无锁等待免费算法是研究的迷人领域;我鼓励读者到谷歌周围.也就是说,天真无锁实现可以很容易看起来合理,并且在大多数情况下表现正确,而实际上却是微妙的不安全.虽然掌握这些原则非常重要,但我强烈建议您使用现有的,易于理解且经过验证的实施,而不是自己动手实施.