在线程之间共享二进制数组

Question

我有一个多线程的应用程序,工作正常.然而,它正在达到锁争用问题(通过快照java堆栈并查看最新等待来检查).

每个线程都会从列表中删除对象,并拒绝每个对象或将其放入Bin中.

Bins最初为null,因为每个都很昂贵(并且可能有很多).

导致争用的代码看起来大致如下:

public void addToBin(Bin[] bins, Item item) {
   Bin bin;
   int bin_index = item.bin_index
   synchronized(bins) {
      bin = bins[bin_index];
      if(bin==null) {
        bin = new Bin();
        bins[bin_index] = bin;
      }
   }
   synchronized(bin) {
     bin.add(item);
   }
}

bins数组上的同步是瓶颈.

一位同事建议我使用双重检查锁定来解决这个问题,但我们不确定究竟会涉及到什么使其安全.建议的解决方案如下所示:

public void addToBin(Bin[] bins, Item item) {
   int bin_index = item.bin_index
   Bin bin = bins[bin_index];

   if(bin==null) {
     synchronized(bins) {
        bin = bins[bin_index];
        if(bin==null) {
          bin = new Bin();
          bins[bin_index] = bin;
        }
     }
   }

   synchronized(bin) {
     bin.add(item);
   }
}

这是安全的和/或是否有更好/更安全/更惯用的方式来做到这一点？

Answer 1

正如Malt的回答中所述,Java已经提供了许多可用于解决此问题的无锁数据结构和概念.我想使用AtomicReferenceArray以下命令添加更详细的示例:

假设bins是一个AtomicReferenceArray,以下代码在null条目的情况下执行无锁更新:

Bin bin = bins.get(index);
while (bin == null) {
    bin = new Bin();
    if (!bins.compareAndSet(index, null, bin)) {
        // some other thread already set the bin in the meantime
        bin = bins.get(index);
    }
}
// use bin as usual

从Java 8开始,有一个更优雅的解决方案:

Bin bin = bins.updateAndGet(index, oldBin -> oldBin == null ? new Bin() : oldBin);
// use bin as usual

节点:Java的版本8是-同时还无阻塞-感知比上面的Java 7的版本,由于速度较慢的事实,updateAndGet将始终更新即使该值不会改变阵列.根据整个bin更新操作的总成本,这可能会或可能不会忽略不计.

另一个非常优雅的策略可能是在将数组移交给工作线程之前,bins用新创建的Bin实例预先填充整个数组.由于线程不必修改数组,这将减少与Bin对象本身同步的需要.填充数组可以通过使用Arrays.parallelSetAll(自Java 8)轻松完成多线程:

Arrays.parallelSetAll(bins, i -> new Bin());

更新2:如果这是一个选项取决于您的算法的预期输出:最终bins数组将完全,密集或只是稀疏地填充？(在第一种情况下,预填充是可取的.在第二种情况下,它取决于 - 经常.在后一种情况下,它可能是一个坏主意).

更新1:不要使用双重检查锁定!这不安全!这里的问题是可见性,而不是原子能.在您的情况下,读取线程可能会获得部分构造(因此损坏)的Bin实例.有关详细信息,请参阅http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html.

Answer 2

Java具有各种出色的无锁并发数据结构,因此实际上不需要为这类事物使用具有同步的数组.

ConcurrentSkipListMap是一个并发的,已排序的键值映射. ConcurrentHashMap是并发未排序的键值.

您可以简单地使用其中一个而不是数组.只需将地图键设置为您已经使用的整数索引,就可以了.

还有Google的ConcurrentLinkedHashMap和Google的Guava Cache,它们非常适合保存有序数据和删除旧条目.