在Java中,我可以依赖于原子的引用赋值来实现写入时的复制吗？

Question

如果我在多线程环境中有一个不同步的java集合,并且我不想强制集合的读者同步^[1],那么我是一个同步编写器并使用引用赋值的原子性可行的解决方案吗？就像是:

private Collection global = new HashSet(); // start threading after this

void allUpdatesGoThroughHere(Object exampleOperand) {
  // My hypothesis is that this prevents operations in the block being re-ordered
  synchronized(global) {
    Collection copy = new HashSet(global);
    copy.remove(exampleOperand);
    // Given my hypothesis, we should have a fully constructed object here. So a 
    // reader will either get the old or the new Collection, but never an 
    // inconsistent one.
    global = copy;    
  }
}

// Do multithreaded reads here. All reads are done through a reference copy like:
// Collection copy = global;
// for (Object elm: copy) {...
// so the global reference being updated half way through should have no impact 

滚动自己的解决方案似乎经常在这种情况下失败,所以我有兴趣了解我可以用来阻止对象创建和阻止我的数据使用者的其他模式,集合或库.

---

[1]原因是与写入相比,读取花费的时间很长,再加上引入死锁的风险.

---

编辑:在一些答案和评论中有很多好的信息,一些要点:

1. 我发布的代码中存在一个错误.全局同步(命名错误的变量)可能无法在交换后保护同步块.
2. 您可以通过在类上同步(将synchronized关键字移动到方法)来解决此问题,但可能存在其他错误.更安全,更易维护的解决方案是使用java.util.concurrent中的内容.
3. 我发布的代码中没有"最终的一致性保证",确保读者确实看到作者更新的一种方法是使用volatile关键字.
4. 经过反思,推动这个问题的一般问题是尝试用java中的锁定写入实现无锁读取,但是我的(已解决)问题是一个集合,这可能会为将来的读者带来不必要的混淆.因此,如果不明显,我发布的代码通过允许一个编写者一次对"某个对象"进行编辑来进行编辑,而这些编辑正在被多个读取器线程不受保护地读取.编辑的提交是通过原子操作完成的,因此读者只能获得编辑前或编辑后的"对象".当/如果读者线程获得更新时,它不会在读取过程中发生,因为读取发生在"对象"的旧副本上.在Java中提供更好的并发支持之前,可能已经发现并证明在某种程度上被破坏的简单解决方案.

Answer 1

而不是尝试推出自己的解决方案,为什么不使用ConcurrentHashMap作为您的集合,只需将所有值设置为某个标准值？(一个常数就好了Boolean.TRUE.)

我认为这个实现适用于许多读者少数作家的情况.甚至还有一个构造函数可以让你设置预期的"并发级别".

更新: Veer建议使用 Collections.newSetFromMap实用程序方法将ConcurrentHashMap转换为Set.由于该方法采用Map<E,Boolean>我的猜测,它将所有值设置Boolean.TRUE为幕后操作同样如此.

更新:解决海报的例子

这可能就是我最终会遇到的问题,但我仍然对我的极简主义解决方案如何失败感到好奇. - 迈尔斯汉普森

您的极简主义解决方案可以通过一些调整来正常工作.我担心的是,虽然它现在很小,但未来可能会变得更加复杂.在制作线程安全的东西时很难记住你所假设的所有条件 - 特别是如果你在几周/几个月/几年后回到代码中做出看似微不足道的调整.如果ConcurrentHashMap以足够的性能完成所需的一切,那么为什么不使用它呢？所有令人讨厌的并发细节都被封装起来,即使是6个月 - 从现在起你将很难搞砸它!

在当前解决方案起作用之前,您至少需要进行一次调整.正如已经指出的那样,你应该将volatile修饰符添加到global声明中.我不知道你是否有C/C++背景,但当我得知volatile Java中的语义实际上比C语言复杂得多时,我感到非常惊讶.如果您计划在Java中进行大量并发编程,那么熟悉Java内存模型的基础知识是个好主意.如果你不提及global一个volatile基准,然后它可能是没有线程永远不会看到任何改变的值global,直到他们尝试更新它,此时进入synchronized块将刷新本地缓存,并得到更新后的基准值.

然而,即使增加了volatile仍然存在巨大的问题.这是一个有两个线程的问题场景:

1. 我们从空集开始,或者global={}.线程A和B它们都在其线程本地缓存内存中具有此值.
2. 线程A获得synchronized锁定global并通过复制global新的密钥并将新密钥添加到集合来启动更新.
3. 当Thread A仍在synchronized块内时,Thread B将其本地值读入global堆栈并尝试进入synchronized块.由于Thread A当前位于监视器Thread B块内.
4. 线程A通过设置引用并退出监视器来完成更新,从而产生global={1}.
5. 线程B现在可以进入监视器并制作该global={1}集的副本.
6. 线程A决定进行另一次更新,读入其本地global引用并尝试进入该synchronized块.由于线程B当前持有锁定,{}因此没有锁定{1}并且线程A成功进入监视器!
7. 线程A还会复制以{1}进行更新.

现在线程A并且B都在synchronized块内,并且它们具有相同的global={1}集合副本.这意味着他们的一个更新将丢失!这种情况是由于您正在同步存储在synchronized块中更新的引用中的对象.您应该始终非常小心使用哪些对象进行同步.您可以通过添加新变量来充当锁来解决此问题:

private volatile Collection global = new HashSet(); // start threading after this
private final Object globalLock = new Object(); // final reference used for synchronization

void allUpdatesGoThroughHere(Object exampleOperand) {
  // My hypothesis is that this prevents operations in the block being re-ordered
  synchronized(globalLock) {
    Collection copy = new HashSet(global);
    copy.remove(exampleOperand);
    // Given my hypothesis, we should have a fully constructed object here. So a 
    // reader will either get the old or the new Collection, but never an 
    // inconsistent one.
    global = copy;    
  }
}

这个bug很阴险,其他答案都没有解决.这些疯狂的并发细节使我建议使用已经调试过的java.util.concurrent库中的东西,而不是尝试自己组合一些东西.我认为上述解决方案可行 - 但是再次搞砸会有多容易？这会更容易:

private final Set<Object> global = Collections.newSetFromMap(new ConcurrentHashMap<Object,Boolean>());

由于引用是final你不需要担心使用陈旧引用的线程,并且由于ConcurrentHashMap处理所有讨厌的内存模型内部问题,你不必担心监视器和内存障碍的所有讨厌的细节!

Answer 2

根据相关的Java教程,

我们已经看到增量表达式,例如c++,没有描述原子动作.即使非常简单的表达式也可以定义可以分解为其他操作的复杂操作.但是,您可以指定原子操作:

• 读取和写入对于引用变量和大多数原始变量(除了long和之外的所有类型double)都是原子的.
• 读取和写入对于声明的所有变量volatile(包括 long和double变量)都是原子的.

Java语言规范的第17.7节重申了这一点

无论是否将它们实现为32位或64位值,对引用的写入和读取始终是原子的.

看来你确实可以依赖于原子的引用访问; 但是,要认识到这并不能确保所有读者在读取global之后都会读取更新的值- 即此处没有内存排序保证.

如果你synchronized在所有访问中使用隐式锁定global,那么你可以在这里建立一些内存一致性......但是使用替代方法可能更好.

您似乎也希望集合global保持不变...幸运的是Collections.unmodifiableSet,您可以使用它来强制执行此操作.举个例子,你可能会做类似以下的事情......

private volatile Collection global = Collections.unmodifiableSet(new HashSet());

......那,或使用AtomicReference,

private AtomicReference<Collection> global = new AtomicReference<>(Collections.unmodifiableSet(new HashSet()));

然后Collections.unmodifiableSet,您也可以使用修改后的副本.

// ... All reads are done through a reference copy like:
// Collection copy = global;
// for (Object elm: copy) {...
// so the global reference being updated half way through should have no impact

您应该知道在这里制作副本是多余的,因为内部for (Object elm : global)创建Iterator如下...

final Iterator it = global.iterator();
while (it.hasNext()) {
  Object elm = it.next();
}

因此,global在阅读过程中没有机会切换到完全不同的值.

除此之外,我同意DaoWen所表达的观点 ......当有可能有替代方案java.util.concurrent时,你有没有理由在这里推出自己的数据结构？我想也许你正在处理一个较旧的Java,因为你使用的是原始类型,但问一下也不会有什么坏处.

您可以找到CopyOnWriteArrayList由其表兄提供的写时复制集合语义CopyOnWriteArraySet(Set使用前者实现).

DaoWen也建议,您考虑使用ConcurrentHashMap？他们保证for在您的示例中使用循环将是一致的.

类似地,Iterators和Enumerations在迭代器/枚举的创建时或之后的某个时刻返回反映哈希表状态的元素.

在内部,Iterator用于强化for过的Iterable.

你可以Set通过Collections.newSetFromMap以下方式制作一个:

final Set<E> safeSet = Collections.newSetFromMap(new ConcurrentHashMap<E, Boolean>());
...
/* guaranteed to reflect the state of the set at read-time */
for (final E elem : safeSet) {
  ...
}