Ins*_*ges 8 multithreading synchronization data-structures
我必须设计一个在多线程环境中使用的数据结构.基本API很简单:插入元素,删除元素,检索元素,检查元素是否存在.结构的实现使用隐式锁定来保证单个API调用的原子性.在我实现这一点后,很明显,我真正需要的是几个API调用的原子性.例如,如果调用者在尝试插入元素之前需要检查元素是否存在,即使每个单独的API调用都是原子的,他也不能原子地执行此操作:
if(!data_structure.exists(element)) {
data_structure.insert(element);
}
这个例子有些尴尬,但基本的一点是,在我们从原子上下文返回后,我们不能再信任"exists"调用的结果(生成的程序集清楚地显示了两次调用之间上下文切换的次要机会).
我目前要解决的问题是通过数据结构的公共API公开锁.这样客户端就必须明确锁定东西,但至少他们不必创建自己的锁.是否有一个更好的常见解决方案来解决这些问题？只要我们参与其中,您能否就线程安全设计提供一些好的文献？
编辑:我有一个更好的例子.假设元素检索返回引用或指向存储元素的指针而不是它的副本.在调用返回后,如何保护调用者以安全地使用此指针\引用？如果您认为不返回副本是一个问题,那么请考虑深层副本,即应该还复制其指向内部的另一个对象的对象.
谢谢.
您要么提供外部锁定机制（不好），要么重新设计 API，例如putIfAbsent. 后一种方法例如用于 Java 的并发数据结构。
而且，当涉及到此类基本集合类型时，您应该检查您选择的语言是否已在其标准库中提供它们。
[编辑]澄清一下：外部锁定对类的用户不利，因为它引入了潜在错误的另一个来源。是的，有时，对于并发数据结构来说，性能考虑确实比外部同步数据结构更糟糕，但这种情况很少见，而且通常只能由比我拥有更多知识/经验的人来解决/优化。
在下面威尔的回答中可以找到一个也许很重要的性能提示。[/编辑]
[edit2]鉴于您的新示例：基本上您应该尝试保持集合的同步和元素的同步尽可能地分开。如果元素的生命周期与其在一个集合中的存在绑定在一起，那么您将遇到问题；当使用GC时，这种问题实际上变得更简单。否则，您将不得不使用一种代理而不是原始元素来放入集合中；在最简单的 C++ 情况下，您可以使用boost::shared_ptr，它使用原子引用计数。在此插入通常的性能免责声明。当您使用 C++ 时（正如我怀疑您谈论指针和引用一样），boost::shared_ptr和的组合boost::make_shared应该足以满足一段时间。[/编辑2]