천 리 길도 한 걸음부터 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비트 포인터의 경우에 앞자리가 많이 남기 때문에 비슷한 방법으로 구현이 가능하기는 한데, 지저분해진다. 좀 더 쉬운 방법이 있을 것 같다)

며칠전부터 메모리 풀을 하나 만들고 있다. 목표는 가볍고 사용하기 쉬우면서 현재 참여하고 있는 프로젝트에 쉽게 적용을 할 수 있도록 하는 것이다. 메모리 풀은 그 특성상 다수의 쓰레드에서 접근이 가능해야해서 쓰레드 안정성이 확보되어야 한다.

쓰레드 안정성을 확보하는 가장 쉬운 방법은 동기화 객체를 사용하는 방법이다. 윈도우 환경하에서 가장 쉽게 쓸수 있는 객체는 CRITICAL_SECTION이고 이걸 사용하면 만드는건 껌이다. 그러나 critical section은 꽤나 무거운 객체이면서 동시에 락이 되었을때 강제로 쓰레드 스위칭(context switching)이 일어나게 되므로 고도로 최적화된 서버 프로그램에서는 성능을 갉아 먹는 원인이 될 수 있다.

그래서 최신 유행인 lock-free를 이용해서 첨단을 걷는 현대인 됨과 동시에 불같이 빠른 메모리 풀을 만들자는 결심을 했다. 솔직히 만드는게 어렵지는 않았다. 간단한 테스트를 통과할때까지 "와 나 천재아니야"라는 생각도 했다.

본격적인 테스트가 필요하다. 몇날 며칠을 견뎌야하는 서버 프로그램에서 이 녀석이 말썽을 부린다면 아주 고통스런 시간을 보내게 될테니 말이다. 테스트 시나리오는 랜덤한 개수의 메모리 블럭을 얻고 해제해는 행동을 2개 이상의 쓰레드에서 횟수를 점점 늘려가는 것이다. 수천번은 가볍게 통과한다. 정말 그때는 고지가 눈앞에 있는 것 같았다.

테스트 횟수를 수십억번으로 설정한다. 문제가 발생했다. 몇번을 반복해도 항상 비슷한 오류를 경험한다. 아무리 코드를 검토해도 오류를 찾을 수가 없다. 슬슬 짜증나기 시작할 무렵 외부의 도움을 받기로 결심했다.

경건한 마음으로 google 신께 신탁을 했더니, 나와 같은 길을 간 사람들의 흔적을 엄청 나게 많이 보여주신다. 그들의 코드와 내 코드를 비교하는데 아무리 봐도 내 코드가 이상한데가 없다(그따위 코드를 떡하니 블로그 따위에 자랑스래 올려둔 놈들은 반성 좀 해라. 그 코드들 중에는 심지어 컨퍼런스에서 발표한 코드도 있었다). 하여튼 그 놈들이 이상없다고 올려논 코드를 신뢰할 수 없게된 상태에서 내 코드의 로직을 몇날며칠 동안 코피 쏟으며 고민한 끝에 문제를 찾았다.

문제를 찾고 나서 그 문제에 대한 해법을 찾다가 이 바닥에서 꽤나 유명한 문제라는 사실을 발견하게 됐다. 이름하야 ABA problem 이다. 링크를 보면 자세한 설명이 있는데다가 내가 저질러 놓은 것과 거의 비슷한 예제 코드까지 있다. 젠장. (10년도 넘기는 했지만, 그래도 OS 수업을 나름 열심히 들었는데 왜 이런 이름을 들어본 기억이 없을까)

아직 코드 수정이 끝나지는 않았지만 대략 해결 방법이 눈에는 보인다. 이 문제에서 짜증나는 점은 이미 수도 없이 많은 사람들이 이 문제로 고민했는데 나는 모르고 있었다는 점이다. ABA problem이라는 이름만이라도 알고 있었다면 훨씬 빨리 사태를 파악하고 해결까지 했을것이다.

결론은?

무식은 수족을 고생시킨다. 아는 것이 힘이니, 공부 좀 하자. 공부해서 남주는거 아니다.