Race-Bedingung in ConcurrentBitSet

Question

Ich versuche, gleichzeitige Bit-Set in Java zu erstellen, die Größenerweiterung (im Gegensatz zu fester Länge, mit ist ziemlich trivial) ermöglicht. Hier ist ein Kernbestandteil der Klasse (andere Methoden sind jetzt nicht wichtig)

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(); 
} 

} 

Leider scheint es, dass es ein Rennen hier Zustand.

Hier ist Beispiel Testcode, der jedes Mal für ein paar Bits fehlschlagen konnte - es sollte alle bis Bit 300 drucken, aber es gibt einige zufällige Nullen dort, an verschiedenen Orten jedes Mal. Ein PC bekomme ich nur wenige, auf anderen gibt es 8-10 Nullen auf ungeraden/geraden Positionen in der Reihe.

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()); 

Beispiel von dem, was ich bekommen 11111111111111111111111111111111111111111111111111111101111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111100000000000000000000 11111111111111111111111111111111111111110111111111111111111111110101111111111111111111110101011111111111111111111111111111111111010101111111111111111111111111111111111101010111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100000000000000000000

Es ist schwer zu debuggen (als etwas komplexer neigt Race-Bedingung verschwinden lassen), aber es sieht an der Stelle, wie, wo zwei Threads versuchen, um die Größe des Arrays zur gleichen Zeit zu erweitern, eine, die fehlschlägt und erneut versucht, während die Schleife beschädigte Daten von aiaRef.get() am nächsten Teil des loop - Teils enthält, den sie bereits besucht hat (wie andere Threads, wenn sie versuchen, es zu erweitern) endet mit einigen Nullen im Inneren.

Hat jemand eine Idee, wo der Fehler ist?

Answer 1

Das Problem ist, dass aiaRef.compareAndSet() nur Schutz vor einem gleichzeitigen Ersatz, weil AtomicReference ‚s einzige Aufgabe ist es, die Unteilbarkeit der Referenz zu schützen. Wenn das referenzierte Objekt gleichzeitig geändert während wir das Array neu erstellen, wird compareAndSet() erfolgreich sein, da es den gleichen Verweis gegen sich selbst vergleicht, aber es möglicherweise einige Änderungen verpasst haben.