无锁原子更新到不可变地图 [英] Lock-free atomic update to immutable Map

问题描述

给出Javaslang/Vavr 不变地图，以及更新该地图的函数:

Given a Javaslang / Vavr immutable map, and a function that updates that map:

private Map<Foo, Bar> myMap = HashMap.empty();

public void setBar(Foo foo, Bar bar) {
  myMap = myMap.put(foo, bar);
}

如何确保两次同时调用不同的Foo键的setBar()都记录其更新?

How can I ensure that two concurrent calls to setBar() for different Foo keys will both have their updates recorded?

// thread A
setBar(fooA, barA)

// thread B
setBar(fooB, barB)

似乎有可能会交叉插入这些呼叫，从而导致以下风险:

It seems like there's a risk that the calls will be interleaved such that:

1. 线程A获取{}
2. 线程B获得{}
3. 线程B计算{} + fooB -> barB = {(fooB -> barB)}
4. 线程B将myMap设置为{(fooB -> barB)}
5. 线程A计算{} + fooA -> barA = {(fooA -> barA)}
6. 线程A将myMap设置为{(fooA -> barA)}
7. 线程B的更新丢失了

1. thread A gets {}
2. thread B gets {}
3. thread B computes {} + fooB -> barB = {(fooB -> barB)}
4. thread B sets myMap to {(fooB -> barB)}
5. thread A computes {} + fooA -> barA = {(fooA -> barA)}
6. thread A sets myMap to {(fooA -> barA)}
7. thread B's update is lost

使用AtomicReference，或多或少地基于

Using AtomicReference, I came up with the following, more or less based on the ConcurrentStack methods in the "Nonblocking Algorithms" section of Java Concurrency in Practice.

private AtomicReference<Map<Foo, Bar>> myMap = 
  new AtomicReference<>(HashMap.empty());

public void setBar(Foo foo, Bar bar) {
  Map<Foo, Bar> myMap0;
  Map<Foo, Bar> myMap1;
  do {
    myMap0 = myMap.get();
    myMap1 = myMap0.put(foo, bar);
  } while (!myMap.compareAndSet(myMap0, myMap1));
}

这是正确的吗?如果是这样，它是否是我可能会获得的良好实现，还是有更简单的方法(例如，缺少实现该模式的Java 8 AtomicReference API)?

Is this correct? And if so, is it as good an implementation as I'm likely to get, or is there something simpler (e.g. some Java 8 AtomicReference API I'm missing that implements this pattern)?

推荐答案

在这种情况下，使用AtomicReference是好的.您可以使用快捷方式

Using AtomicReference is good in this case. You can use the shortcut method

public void setBar(Foo foo, Bar bar) {
    myMap.updateAndGet(map -> map.put(foo, bar)));
}

相反.请参见 AtomicReference.updateAndGet 的javadoc.默认的Java实现与Java 8中的默认实现完全相同.

instead. See the javadoc for AtomicReference.updateAndGet. The default java implementation is exactly the same as yours in Java 8.

这篇关于无锁原子更新到不可变地图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！