천 리 길도 한 걸음부터 RSS FEED

이전 글인 ABA problem에서 언급했던 lock free stack을 일부만 만들었다. 글을 쓰고 꽤 시간이 지났는데 여태 계속 삽질을 했던 것은 아니고, 한동안 잊고 있다가 생각나서 해결을 했다.

그런데 다시 글을 쓰게 된것은 문제를 완전히 해결한게 아니기때문이다. 32비트 환경에서는 문제를 쉽게 해결했는데 64비트 환경에서는 이게 또 쉽지 않아보인다.

우선 32비트 환경에서 해법은 이렇다. _InterlockedCompareExchange64라는 intrinsic을 이용해서 포인터+시퀀스를 비교해서 교체를 하는 방법을 이용했다. 아래의 공용체를 보면 해법이 바로 보일 것이다.

union Header {
    LONGLONG Alignment;
    struct {
        Strip* head;
        long   sequence;
    };
};

pop이나 push가 이뤄지면 sequence를 증가시켜서 ABA 문제를 피해가는 방법이다. 실제 CAS를 이용해서 포인터를 바꿔치기하는 부분은

_InterlockedCompareExchange64(&head_.Alignment, next, item.Alignment)

처럼 64비트 값(포인터 + sequence)를 한번에 교체하게 된다. 포인터 값이 겹치더라도 sequence가 증가하기때문에 ABA 문제는 확실히 피해갈 수 있다. _InterlockedCompareExchange64 intrinsic은 펜티엄 이상의 CPU에서 사용 가능하니 모든 환경에서 사용가능하다고 가정해도 문제 없을듯하다.

그러나 이 방법은 64비트 환경에서는 유효하지 않다. 포인터만해도 64비트가 되어버리니 여기다가 sequence같은 추가 값을 또 넣을 수가 없기 때문에 완전한 해결책이 아니다. 실제로 작성하고 있는 서버 프로그램은 64비트 환경에서 돌아가야하기때문에 해결 못했다에 더 가깝다.

64비트 환경에서는 좀 더 연구가 필요하다. (64비트 포인터의 경우에 앞자리가 많이 남기 때문에 비슷한 방법으로 구현이 가능하기는 한데, 지저분해진다. 좀 더 쉬운 방법이 있을 것 같다)