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까지 모든 코드를 인쇄해야하지만 매번 다른 위치에 임의의 0이 거의 없습니다. 하나는 하나의 PC를 나는 단지 몇 가지, 다른 거기에 행에 홀수/심지어 위치에 8-10 0이 있습니다. (복잡한 아무것도 경쟁 조건이 사라지게하는 경향이) 디버깅

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

는 어렵지만, 두 개의 스레드가 시도 시점에서처럼 보인다 루프의 다음 부분에있는 aiaRef.get()에서 손상된 데이터로 끝나는 동안 오류가 발생하여 다시 시도해야하는 배열의 크기를 확장합니다. 이미 방문한 부분 (다른 스레드가있는 경우 그것을 연장하려고 시도하고있다) 내부에 약간의 제로를 갖는 것을 끝낸다.

누구나 버그가있는 곳이 있습니까?

Answer 1

문제 AtomicReference의 작업 만이 참조의 자성을 보호하기 때문에 aiaRef.compareAndSet() 만, 동시 여분 대해 지키고된다는 것이다. 배열을 다시 빌드하는 동안 참조 된 객체가 동시에 이 수정 된 인 경우 compareAndSet()은 동일한 참조를 자체와 비교하기 때문에 성공하지만 일부 수정이 누락되었을 수 있습니다.