9

如果我在多线程环境中有一个不同步的 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. 您可以通过在类上进行同步来解决此问题(将同步关键字移动到方法中),但可能存在其他错误。一个更安全、更易于维护的解决方案是使用 java.util.concurrent 中的一些东西。
  3. 我发布的代码中没有“最终一致性保证”,确保读者看到作者更新的一种方法是使用 volatile 关键字。
  4. 回想起来,激发这个问题的一般问题是试图在 java 中使用锁定写入来实现无锁读取,但是我的(已解决的)问题是一个集合,这可能会让未来的读者感到不必要的困惑。因此,如果我发布的代码不明显,则通过一次允许一个作者对不受多个阅读器线程保护的“某个对象”执行编辑来工作。编辑的提交是通过原子操作完成的,因此读者只能获得编辑前或编辑后的“对象”。当/如果读取器线程获得更新时,它不能发生在读取中间,因为读取发生在“对象”的旧副本上。在 java 提供更好的并发支持之前,可能已经发现并证明以某种方式破坏了一个简单的解决方案。
4

5 回答 5

13

与其尝试推出您自己的解决方案,不如使用ConcurrentHashMap作为您的集合并将所有值设置为某个标准值?(一个恒定的likeBoolean.TRUE会很好用。)

我认为这种实现适用于多读者少作者的场景。甚至还有一个构造函数可以让您设置预期的“并发级别”

更新: Veer 建议使用Collections.newSetFromMap实用方法将 ConcurrentHashMap 转换为 Set。由于该方法需要Map<E,Boolean>我的猜测,它在将所有值设置为Boolean.TRUE幕后执行相同的操作。


更新:解决海报的例子

这可能是我最终会采用的方式,但我仍然对我的极简主义解决方案如何失败感到好奇。– 迈尔斯汉普森

您的极简主义解决方案只需稍作调整即可正常工作。我担心的是,虽然现在很少,但将来可能会变得更加复杂。很难记住在制作线程安全的东西时假设的所有条件——尤其是当你在几周/几个月/几年后回到代码中进行看似微不足道的调整时。如果 ConcurrentHashMap 以足够的性能满足您的所有需求,那么为什么不使用它呢?所有令人讨厌的并发细节都被封装掉了,即使是 6 个月后,你也很难把它搞砸!

在您当前的解决方案生效之前,您确实需要至少进行一次调整。正如已经指出的,您可能应该将volatile修饰符添加到global's 声明中。我不知道你是否有 C/C++ 背景,但当我得知volatile Java中的语义实际上比C 中复杂得多时,我感到非常惊讶。如果您打算在 Java 中进行大量并发编程,那么最好熟悉Java 内存模型的基础知识。如果您没有对引用进行global引用volatile,那么在他们尝试更新它之前,没有线程可能会看到值的任何更改global,此时输入synchronized块将刷新本地缓存并获取更新的参考值。

但是,即使添加了volatile,仍然存在很大的问题。这是一个有两个线程的问题场景:

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

现在线程AB都在块内,并且它们具有相同的集合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;    
  }
}

这个错误足够阴险,以至于其他答案都没有解决它。正是这些疯狂的并发细节让我建议使用已经调试过的 java.util.concurrent 库中的一些东西,而不是尝试自己组装一些东西。我认为上述解决方案会奏效——但再次搞砸它有多容易?这会容易得多:

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

由于引用是final您无需担心使用过时引用的线程,并且由于ConcurrentHashMap内部处理了所有令人讨厌的内存模型问题,您不必担心监视器和内存屏障的所有令人讨厌的细节!

于 2012-08-15T04:28:44.600 回答
7

根据相关的Java教程

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

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

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(使用前者实现 a Set)提供的写时复制集合语义。


DaoWen也建议,您是否考虑过使用ConcurrentHashMap? 他们保证for像您在示例中所做的那样使用循环将是一致的。

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

在内部,an用于Iterator增强.forIterable

您可以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) {
  ...
}
于 2012-08-15T04:16:24.917 回答
1

我认为您最初的想法是合理的,并且道文在消除错误方面做得很好。除非你能找到可以为你做所有事情的东西,否则最好理解这些东西,而不是希望某个神奇的课程能为你做这件事。神奇的课程可以让你的生活更轻松并减少错误的数量,但你确实想了解他们在做什么。

ConcurrentSkipListSet 在这里可能会为您做得更好。它可以摆脱你所有的多线程问题。

但是,它比 HashSet 慢(通常——HashSets 和 SkipLists/Trees 很难比较)。如果您为每次写入进行大量读取,那么您所拥有的将会更快。更重要的是,如果您一次更新多个条目,您的读取可能会看到不一致的结果。如果您希望只要有条目 A 就会有条目 B,反之亦然,则跳过列表可能会给您一个而没有另一个。

使用您当前的解决方案,对于读者来说,地图的内容始终是内部一致的。一次读取可以确保每个 B 都有一个 A。可以确保该size() 方法给出了迭代器将返回的元素的精确数量。两次迭代将以相同的顺序返回相同的元素。

换句话说,allUpdatesGoThroughHere 和 ConcurrentSkipListSet 是解决两个不同问题的两个很好的解决方案。

于 2012-08-15T20:25:06.630 回答
-1

synchronized通过制作替换,global volatile就写时复制而言,你会没事的。

尽管分配是原子的,但在其他线程中,它没有按照对引用对象的写入进行排序。需要有一个happens-before关系,你可以通过avolatile或同步读取写入来获得。

一次发生多个更新的问题是分开的 - 使用单个线程或您想要在那里执行的任何操作。

如果您将 asynchronized用于读取和写入,那么它是正确的,但是对于需要切换的读取,性能可能不是很好。AReadWriteLock可能是合适的,但您仍然会有写入阻塞读取。

发布问题的另一种方法是使用 final 字段语义来创建一个(理论上)可以安全发布的对象。

当然,也有可用的并发集合。

于 2012-08-15T04:09:41.607 回答
-1

你能用这个Collections.synchronizedSet方法吗?来自 HashSet Javadoc http://docs.oracle.com/javase/6/docs/api/java/util/HashSet.html

Set s = Collections.synchronizedSet(new HashSet(...));
于 2012-08-15T04:15:35.870 回答