编写一个包含整数的 ArrayList，它将被并发访问

Question

要求是，我需要写一个整数的ArrayList。我需要线程安全地访问不同的整数（写入、读取、增加、减少），还需要允许最大并发性。

每个整数的运算也比较特殊，像这样：

最频繁的操作是阅读
其次频繁的操作是只有大于零时才减一。或者，加一（无条件）
Adding/removing元素很少见，但仍然需要。

我想到了 AtomicInteger。然而，这变得不可用，因为我想要的原子操作是比较如果不为零，然后减少。然而，AtomicInteger 提供的原子操作是比较相等，然后设置。如果你知道在这种情况下如何应用AtomicInteger，请在这里提出。

我想的是像这样同步对每个整数的访问：

ArrayList <Integer> list;
 ... ...
// Compare if greater than zero, and decrease
MutableInt n = list.get(index);
boolean success = false;
synchronized (n) {
    if (n.intValue()>0) { n.decrement(); success=true; }
}

// To add one
MutableInt n = list.get(index);
synchronized (n) {
    n.increment();
}

// To just read, I am thinking no need synchronization at all.
int n = list.get(index).intValue();

我的方案有副作用吗？维护数百甚至数千个同步整数是否有效？

更新：我还认为允许并发访问每个元素是不切实际的，也没有好处，因为实际的并发访问受处理器数量的限制。也许我只是用几个同步对象来保护List的不同部分，就够了吗？

再就是实现add/delete的操作，它是线程安全的，但对其他操作的并发影响不大。我在想ReadWriteLock，对于add/delete，需要获取写锁，对于其他操作（改变一个整数的值），需要获取读锁。这是正确的做法吗？

Answer 1

我认为您使用读锁来访问列表并为列表上的 add/remove 使用写锁是正确的。

您仍然可以使用 AtomicInteger 作为值：

// Increase value
value.incrementAndGet()

// Decrease value, lower bound is 0
do {
    int num = value.get();
    if (num == 0)
        break;
} while (! value.compareAndSet(num, num - 1)); // try again if concurrently updated

Answer 2

我认为，如果您可以接受固定大小的列表，那么使用单个 AtomicIntegerArray 比使用多个 AtomicInteger 是更好的选择：

public class AtomicIntList extends AbstractList<Integer> {

  private final AtomicIntegerArray array;

  public AtomicIntList(int size) {
    array=new AtomicIntegerArray(size);
  }
  public int size() {
    return array.length();
  }
  public Integer get(int index) {
    return array.get(index);
  }
  // for code accessing this class directly rather than using the List interface
  public int getAsInt(int index) {
    return array.get(index);
  }
  public Integer set(int index, Integer element) {
    return array.getAndSet(index, element);
  }
  // for code accessing this class directly rather than using the List interface
  public int setAsInt(int index, int element) {
    return array.getAndSet(index, element);
  }
  public boolean decrementIfPositive(int index) {
    for(;;) {
      int old=array.get(index);
      if(old<=0) return false;
      if(array.compareAndSet(index, old, old-1)) return true;
    }
  }
  public int incrementAndGet(int index) {
    return array.incrementAndGet(index);
  }
}

直接访问此 class 而不是通过 List<Integer> 接口的代码可以使用方法 getAsInt 和 setAsInt 来避免装箱转换。这是一种常见的模式。由于方法 decrementIfPositive 和 incrementAndGet 无论如何都不是 List 接口的一部分，因此它们始终使用 int 值。

Answer 3

作为此问题的更新...我发现最简单的解决方案，即为所有可能的冲突方法同步整个代码块，结果证明是最好的，即使从性能的角度来看也是如此。同步代码块解决了这两个问题 - 访问每个计数器，以及 add/delete 个元素到计数器列表。

这是因为 ReentrantReadWriteLock 的开销非常高，即使只应用读锁也是如此。与 read/write 锁的开销相比，操作本身的成本非常小，任何额外的锁定都不值得这样做。

ReentrantReadWriteLock的API文档中的声明需要高度重视："ReentrantReadWriteLocks... is typically worthwhile only when ... and entail operations with overhead that outweighs synchronization overhead".

编写一个包含整数的 ArrayList，它将被并发访问

Write an ArrayList with integers which will be accessed concurrently

java

concurrency

multithreading

synchronization

atomic