Java의 lock-free 및 크기 제한 대기열

Question

Java의 잠금 해제 대기열 구현을 this 게시에 따라 확장하려고합니다.

내 구현에는 원자 변수/참조 만 사용하도록 제한되어 있습니다. 내 대기열에 최대 크기가 있어야합니다. 따라서 putObject()는 큐가 가득 차면 차단해야하고 큐가 비어 있으면 getObject()가 필요합니다.

현재 잠금 장치를 사용하지 않고이를 해결하는 방법을 모르겠습니다.

예를 들어 AtomicInteger를 사용할 때 수정 작업은 원자 적입니다. 그러나 putObject() 및 getObject()에서 check-and-modify-situation을 처리해야한다는 문제가 여전히 남아 있습니까? 그래서 현재 대기열 크기를 확인한 후에 대기열에있는 스레드가 중단되는 상황이 여전히 존재합니다.

현재 내 제한 사항으로이 문제를 해결할 수 있습니까?

그것은 일반적으로 링 버퍼를 이용하여 해결하는 매우 일반적인 문제

Answer 1

주선. 이것은 Disruptor 라이브러리처럼 네트워크 어댑터가 사용하는 것입니다. Disruptor와 Ring Buffer로 할 수있는 좋은 예를 살펴 보시기 바랍니다.

Answer 2

제대로 작동하는 잠금없는 대기열이있는 경우 최대 크기를 추가하는 것은 AtomicInteger를 추가하고 적절한 시간에 수표, inc, dec를 수행하는 것만 큼 쉽습니다.

요소를 추가 할 때 기본적으로 대기열의 위치를 ​​미리 예약합니다. 뭔가처럼 :.

while (true) { 
    int curr = count.get(); 
    if (curr < MAX) { 
     if (count.compareAndSet(curr, curr + 1)) { 
      break; 
     } 
    } 
    else { 
     return FULL; 
    } 
} 

그런 다음 새 요소를 추가하고 그것을 연결 점점 , 그냥 평소처럼 머리를 액세스하고 대기열에서 반환하는 모든 것을이 있는지 확인할 수 있습니다. 예인 경우 반환하고 카운터를 내립니다. 그렇지 않은 경우 비어 있음을 반환합니다. 큐가 실제로 비어 있는지 확인하기 위해 카운터를 사용하지 않고 있습니다. 카운터가 1 일 수 있기 때문에 미리 예약 방식으로 인해 큐에 연결된 것이 없습니다. 그래서 나는 당신의 큐가 당신에게 "나는 내 안에 뭔가가있다"라고 말할 수있는 방법을 가지고 있다고 믿는다. 그렇지 않으면, 결코 작동하지 않을 것이다.