LockFreeStack Trouble Shooting

안녕하세요 대학생 개발자입니다.

락프리에 대한 언급이 있었던지 1주일쯤 지났습니다.

아마 보신분들이 실제로 개발을 해보셨을지는 모르겠습니다만 락프리 알고리즘을 구글링했을때 나오는 의사코드를 보고 코딩을 하셨던분들은 간단히 테스트 해봤을때에는 전혀 문제가 발생하지 않았을겁니다.

하지만 여러 스레드에서 초당 몇백만건의 push, pop을 하게되면 여러 문제가 발생할 수 있는데요.

 

 

그럼 시작하도록 하겠습니다.

그래서 무슨문제가 발생하는데?

아마 이 부분이 제일 궁금할 것 같습니다.

저도 이 문제를 찾기위해서 거의 2주일 가까운 시간을 소모하면서 메모리 로그를 봤던 것 같습니다.

사실 이 트러블슈팅의 과정을 올리는게 맞는지 모르겠습니다만... 뭐 이건 제 포트폴리오가 될것이니 이런것도 올려도 상관없을 것 같다는 생각이 들었습니다.

 

아마 코드를 제대로 짜셨다면 두가지의 큰 문제가 발생할겁니다.

 

첫번째는 메모리 엑세스 위반에 관한 건일겁니다.

두개의 pop이 동시에 실행되었을때 하나는 delete를 수행하고 하나는 delete를 수행하지 못할겁니다.

하지만 이런 문제가 있을 수 있죠

while(true)
{
    currentTop = this->_Top;
    nextNode = currentTop->_Next;

    if(CAS(...)) break;
}

delete currentTop;

두개의 스레드가 동시에 접근한다고 가정을하면 하나는 currentTop을 받아온 상태로 Quantum Time을 모두 소모하든 혹은 더 우선순위가 높은 스레드가 등장하든 해서 컨텍스트 스위칭이 되었고 그 사이에 다른 스레드가 delete currentTop까지 진행을 해버린겁니다.

그리고 currentTop까지 받아온 스레드가 다시 실행을 하려고 할때 currentTop->_Next 구간에서 메모리 엑세스 위반이 나오게 될겁니다.

이유는 delete된 메모리에 대한 디커밋 때문입니다.

 

저는 직접 이 문제를 찾으려고 다른 스레드에서 delete를 했다는 메모리 로그와 실제 currentTop이 가르키고 있는 메모리뷰를 확인했었습니다.

그리고 그 메모리는 실제로 디커밋 되어서 메모리뷰에서 확인할 수 없었습니다.

 

문제에 대한 해결은 생각보다 간단했습니다.

메모리가 디커밋 안되면 된다.

즉 저는 락프리 스택을 구현하기 위한 메모리풀을 제작했고 당연히 메모리풀은 하나의 자료구조 형태로 되어있을 겁니다.

그리고 락프리 스택을 만들기 위한 메모리풀이므로 이 메모리풀에서 락이 걸려버린다면 의미가 없어질겁니다.

그래서 이 메모리풀 또한 락프리 자료구조로 되어있는 메모리풀을 사용했습니다.

 

어... 듣다보니 좀 이상한것 같습니다.

락프리 스택에서 디커밋이 일어나기 때문에 메모리풀을 쓰는데 그 메모리풀이 락프리라니 말만 들으면 해결을 하기위해 또 문제를 만드는것 아니냐고 생각하실수 있습니다.

 

하지만 메모리풀의 경우에는 T타입을 요구하면 T*를 반환하지만 스택은 T타입을 요구하면 T타입을 입력하게되죠.

즉 스택의 경우에는 노드와 데이터가 따로 분리되어있었지만 메모리풀의 경우에는 노드와 데이터가 하나로 붙어다닌다는 점이 다른점으로 이부분을 잘 캐치 하신다면 문제가 없다는걸 아실 수 있을겁니다.

아마 이 부분에 대해서는 예전에 올렸었던 싱글 스레드 전용 메모리풀에 관한 글을 읽으셨다면 이해하실수 있는 부분이라고 생각합니다.

 

그럼 락프리 메모리풀이 왜 필요한지에 대한 정리는 끝났습니다.

락프리 메모리풀의 구현은 락프리 스택을 만들었던 로직과 거의 동일하기 때문에 따로 언급하지 않겠습니다.

 

 

두번째는 소위 ABA Prob라고 불리는 최근에 사용했던 메모리를 다시 얻어오는 힙의 특성 때문에 발생합니다.

이 문제또한 동일하게 pop 연산을 수행하는 도중에 발생할 것입니다.

while(true)
{
    currentTop = this->_Top;
    nextNode = currentTop->_Next;

    if(CAS(...)) break;
}

delete currentTop;

currentTop을 가져온 뒤 다른 스레드가 pop을 하고 다시 push했을때 우연히 같은 메모리를 가져오게 된다면 currentTop에 들어가있는 노드는 유효하지만 이전에 얻어낸 노드와는 전혀 다른 노드가 되어있을겁니다.

이 노드를 pop하는 순간 문제가 될 수 있겠죠...

그리고 메모리풀을 사용하게 된다면 이 ABA prob는 훨씬더 많이 발생할겁니다.

 

이 부분은 적게는 수십건 수백건의 로그를 확인해야지 원인을 분석할 수 있습니다.

 

이 문제를 해결하기 위해서는 DoubleCAS라고 불리는 알고리즘이 필요합니다.

DoubleCAS는 16바이트에 대한 원자적인 비교, 스왑 연산을 수행해주는 함수입니다.

그를 위해서 Top노드와 함께 비교할 8바이트의 추가적인 변수하나가 필요하겠습니다.

그리고 Top노드의 변경이 되었는지 여부를 확인함과 동시에 추가적인 8바이트 공간을 사용해서 변경당시의 그 카운트값과 동일한지를 확인할 겁니다.

그리고 그 8바이트의 카운트값을 원자적으로 증가시킬겁니다.

 

물론 이방법 외에도 방법이 있긴합니다.

x64의 경우 포인터 변수는 일반적으로 유저영역 16테라바이트를 제외한 영역을 가르키지 않습니다.

그러니까 상위 바이트를 이용해서 DoubleCAS처럼 구현할 수 있습니다.

뭐... 둘중에 하나를 선택하셔서 하면 될 것 같습니다만... 쉬운건 역시 DoubleCAS가 더 간단하긴합니다.

 

뭐... 생략된 부분이 너무 많다보니 설명은 간략했습니다.

하지만 두번째 건은 찾기도 힘들고 문제를 찾는다고해도 해결하는데 있어서 좀 고민이 많이 필요합니다.

제가 이렇게 글을 감질나게 쓰는 이유는... 제 포트폴리오를 위해서 모든걸 공개하는것도 좋긴하겠지만 제 글을 보고 서버 개발에 뛰어드신 분이 스스로 개발 능력을 향상시키는것 또한 중요하기 때문입니다.

 

그러니 해결을 못하셨다면 해답을 보고서라도 원인을 찾아내시기 바랍니다.

 

 

자 그럼 오늘의 글도 여기서 끝이났습니다.

요새 글이 많이 짧아지고 내용도 거의 심플하게만 공개를 하고있습니다.

뭐... 예전에 비해서 시간이 많이 없는것도 사실이긴 합니다만 중요한건 멀티스레딩 감각이란건 실제로 개발해보지 않으면 절대 늘지 않기때문에 락프리 트러블슈팅을 통해서 본인의 멀티스레딩 감각을 키우기를 바라는 마음으로 내용을 많이 공개하지 않고있습니다.

 

오늘도 긴글 읽어주셔서 감사합니다.

다음글에서 더 좋은 내용으로 돌아오겠습니다.

그럼 안녕히 계세요.