ConcurrentBitSetの競合条件

Question

Javaで並行ビットセットを作成しようとしていますが、これはサイズの拡張を可能にします（固定長ではなく、非常に簡単です）。クラスの中核部分です（他のメソッドは現在重要ではありません）

public class ConcurrentBitSet { 

static final int CELL = 32; 
static final int MASK = CELL - 1; 
final AtomicReference<AtomicIntegerArray> aiaRef; 

public ConcurrentBitSet(int initialBitSize) { 
    aiaRef = new AtomicReference<>(new AtomicIntegerArray(1 + ((initialBitSize - 1)/CELL))); 
} 

public boolean get(int bit) { 
    int cell = bit/CELL; 
    if (cell >= aiaRef.get().length()) { 
     return false; 
    } 
    int mask = 1 << (bit & MASK); 
    return (aiaRef.get().get(cell) & mask) != 0; 
} 

public void set(int bit) { 
    int cell = bit/CELL; 
    int mask = 1 << (bit & MASK); 
    while (true) { 
     AtomicIntegerArray old = aiaRef.get(); 
     AtomicIntegerArray v = extend(old, cell); 
     v.getAndAccumulate(cell, mask, (prev, m) -> prev | m); 
     if (aiaRef.compareAndSet(old, v)) { 
      break; 
     } 
    } 
} 

private AtomicIntegerArray extend(AtomicIntegerArray old, int cell) { 
    AtomicIntegerArray v = old; 
    if (cell >= v.length()) { 
     v = new AtomicIntegerArray(cell + 1); 
     for (int i = 0; i < old.length(); i++) { 
      v.set(i, old.get(i)); 
     } 
    } 
    return v; 
} 

public String toString() { 
    StringBuilder sb = new StringBuilder(); 
    for (int i = 0; i < aiaRef.get().length(); i++) { 
     for (int b = 0; b < CELL; b++) { 
      sb.append(get(i * CELL + b) ? '1' : '0'); 
     } 
    } 
    return sb.toString(); 
} 

} 

残念ながら、ここに競合状態があるようです。

ここでは、毎回数ビット失敗したサンプルテストコードです。ビット300まですべてのビットを出力する必要がありますが、毎回別の場所にランダムゼロがありません。私がほんの少ししか得ていない1台のPC、他には奇数/偶数の位置に8-10​​個のゼロがあります。 （複雑な何かが競合状態が消えるように傾向がある）のデバッグに

final ConcurrentBitSet cbs = new ConcurrentBitSet(10); 
    CountDownLatch latch = new CountDownLatch(1); 
    new Thread() { 
     public void run() { 
      try { 
       latch.await(); 
       for (int i = 0; i < 300; i += 2) { 
        cbs.set(i); 
       } 
      } catch (InterruptedException e) { 

      } 
     }; 
    }.start(); 
    new Thread() { 
     public void run() { 
      try { 
       latch.await(); 
       for (int i = 0; i < 300; i += 2) { 
        cbs.set(i + 1); 
       } 
      } catch (InterruptedException e) { 
      } 
     }; 
    }.start(); 
    latch.countDown(); 
    Thread.sleep(1000); 
    System.out.println(cbs.toString()); 

私が取得しています何の例は 11111111111111111111111111111111111111111111111111111101111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111100000000000000000000 11111111111111111111111111111111111111110111111111111111111111110101111111111111111111110101011111111111111111111111111111111111010101111111111111111111111111111111111101010111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100000000000000000000

それは難しいですが、それは2つのスレッドが試みる時点でのように見えますループの次の部分のaiaRef.get（）からの破損したデータでループが終了している間に、同じサイズで配列のサイズを同時に拡張することができます（すでにアクセスした部分それを拡張しようとしている）は内部でいくつかのゼロを持つことになります。

誰でもバグはどこですか？

Answer 1

問題がAtomicReferenceの唯一の仕事は、その参照のアトミック性を保護することであるためaiaRef.compareAndSet()のみ、同時交換に対する保護されていることです。アレイが再構築されている間に、参照されたオブジェクトが同時にが変更されたである場合、同じ参照をそれ自身と比較しているため、compareAndSet()が成功しますが、修正が失われている可能性があります。