LockFree

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

 

정말 오랜만에 글을 남기게 되었습니다.

한동안 락프리 개발에 시간을 많이 들였습니다..

사실 락프리라는 알고리즘이 나온지 얼마 안된 기술은 아닙니다.

문서상에 언급되는것만 해도 거의 10년이상된 오래된 기술입니다.

그런데 제가 이런걸 공부하는데 왜 이렇게 오래걸리게 되었냐하면 락프리는 순수하게 멀티스레딩으로 잘 작동되는지 확인이 필요합니다.

사실 만드는 시간보다 검증하고 에러 수정하는 작업에 더 많은 기간을 소모했던것 같습니다.

그리고 락프리 스택과 큐를 사용하기 위해서는 또 다른 문제가 생기는데 이부분에 대해서는 제가 나중에 글을 통해서 언급하도록 하겠습니다.

 

그럼 시작하겠습니다.

 

왜 락프리냐?

아마 일반적으로 락프리를 사용하는 경우라면 다음과 같은 경우일겁니다.

너무 많은 스레드들이 깨어나서 컨텍스트 스위칭으로 인한 퍼포먼스가 떨어지게 될까봐, 혹은 커널모드까지 진입하게 되었을시 너무 큰 퍼포먼스 손해등을 꼽을 수 있을 것 같습니다.

 

우선 전자의 경우에는 고민을 해봐야하는 부분이 있습니다.

지금 돌리고 있는 이 로직이 과연 정말 cpu하나를 온전히 다 소모하면서 그 작업이 완료되기를 기다려야되는 로직인지 혹은 그동안 다른로직이 돌았을때 결과적인 총 퍼포먼스가 증가하게 될지를 고민해야됩니다.

 

후자는 총 퍼포먼스의 부분이 아니라 그 스레드의 입장으로만 봤을때 나타나는 고민거리입니다.

당연히 스레드가 멈추게되면 다시 러닝 스레드로 돌아오기까지 시간이 소요될겁니다.

만약 로직은 상당히 짧아서 몇사이클 이내에 탈출이 가능하지만 락에 걸리게되어 스레드가 멈춰버린다면 당연히 그 만큼 그 로직이 느려지는것은 당연한 일일지도 모릅니다.

 

그러므로 우리는 이부분을 고려해서 락프리를 사용해야 될것입니다.

이부분에 대한 고려는 밑부분에서 언급하도록하고 일단은 넘어가도록 하겠습니다.

 

락프리... 실제로 많이쓰는건가?

적시에 사용한다면 확실한 장점이 있는 알고리즘임에도 불구하고 현업에서는 락프리로 도배하는 형태의 라이브러리는 잘 사용하지 않습니다.

이유는 락프리는 개인이 개발해야되는 알고리즘이면서 동시에 문제가 생겼을때 그 책임은 온전히 내가 져야하는 부분입니다.

그렇기 때문에 현업에서는 락프리를 사용하는 대신 그냥 이미 안전한 동기화 객체를 이용해서 락을 걸어버리고 들어가게되죠.

저는 그 부분에서 조금 프리했던 부분이 있습니다.

저는 당장 회사에 취업해있는 상태도 아닐뿐더러 라이브 서비스를 해야하는 서버를 만드는 사람이 아니므로 조금 더 실험을 해볼 수 있었고 문제가 생긴다면 그냥 끄고 고치면 그만이었기 때문에 라이브러리에 락프리를 넣으면서 실험을 해보려고 했던 겁니다.

 

 

락프리가 효율적이긴 한거야??

우리가 여기서 중요하게 따져봐야할 부분은 락프리가 동기화 객체에 락을 걸고 들어가는 알고리즘에 비해서 효율이 있는가 입니다.

사실 락프리라는 알고리즘은 결국에는 유저코드에서 그 작업이 될때까지 반복을 계속 수행하는 스핀락과 상당히 유사한 부분이 있습니다.

 

예전 글에서 스핀락을 사용하지 않는 이유에 대해서 언급드렸었습니다.

스핀락을 사용하지 않는 이유는 락이 걸린동안 다른 스레드가 작업을 할 수 있다면 전체적인 퍼포먼스가 증가하겠지만 지금당장 이 로직의 퍼포먼스만을 위해서 다른 로직을 돌리지 않아야 할만큼 중요한 것이 아니라면 그 로직 자체의 성능을 올리는데는 효과를 보겠지만 전체적인 성능 향상에는 그닥 이롭지 못하다는 점이었습니다.

 

그러면 이부분에서 그럼에도 불구하고 왜 락프리를 사용하는지 궁금하실겁니다.

 

지금 제가 사용하려는 락프리 자료구조의 경우에는 크게 스택과 큐의 삽입 제거 연산등으로 연산의 시간이 매우 짧은 연산들입니다.

이 경우에는 락프리를 통해 반복문을 돌면서 작업을 처리할 수 있을 때 까지 기다리는 것이 더 효율적일 수도 있습니다.

물론 스레드의 갯수가 코어를 넘어서게 된다면 매우 비효율적인 구조가 되겠지만 일반적으로 스레드 갯수는 코어갯수 이하게로 둔다는 점을 바탕으로 깔고 가기 때문에 이 부분은 문제삼지 않을 것입니다. 

 

결국 남는 이유는 만약 아주 짧은 사이클 안에 끝날 작업을 락을 걸어서 스레드가 멈춰버린다면 다시 그 스레드가 돌기까지의 시간이 꽤나 걸립니다.

스핀락이나 락프리와는 비교도 할 수 없을 정도의 시간이 소요될 겁니다.

즉 스핀락과 락프리는 그 로직의 대상이 아주 짧은 경우에는 이점으로 다가올 수 있다는 점에서 연산 시간 소요가 적은 스택의 푸시 팝, 큐의 인큐 디큐 연산에 접목 시키려고 한것입니다.

 

그럼 시작하겠습니다

이번글에서는 일단 락프리 스택에 대한 얘기만 할겁니다.

그럼 큐가 궁금하신분들은 다음 글을 기다리시거나 여러분들이 직접 내용을 맵핑하고 추론해서 만드시면 될 것 같습니다.

 

우리가 일반적으로 스택을 만들때 push, pop과 같은 기능이 들어갑니다.

template<typename T>
class stack
{
    void push(T value)
    {
        Node* newNode = new Node();
        newNode->val = value;
        newNode->next = _TopNode;
        _TopNode = newNode;
    }
    bool pop(T&ret)
    {
        Node* removeNode = _TopNode;
        if(removeNode == nullptr) return false;
        ret = removeNode->val;
        _TopNode = removeNode->next;
        delete removeNode;
        return true;
    }
};

그리고 push와 pop의 경우 대충 다음처럼 만들어 질 것 같습니다.

하지만 이 pop과 push연산은 멀티스레딩에 안전하지 않습니다.

 

먼저 push의 경우를 보겠습니다.

newNode->next = _TopNode;

_TopNode = newNode;

다음과 같이 연산이 되어있을때 newNode->next의 _TopNode와 그 바로 밑에줄의 _TopNode는 서로 다른 포인터일 수도 있습니다.

당연하죠 동시에 두개의 스레드가 접근했을때 그런 문제가 발생할 겁니다.

 

pop의 경우에도 다를건 없습니다.

removeNode = _TopNode;

...

_TopNode = removeNode->next;

이사이에서 removeNode의 next가 변할수 있다는점.

그리고 removeNode에 대입할때의 _TopNode와

removeNode->next를 대입할때의 _TopNode가 서로 다른 노드일 수 있다는점 등을 고려해본다면 문제가 있을 것 같습니다. 

 

우리는 스택을 만든다고하면 이런연산을 할 것 같습니다.

void push(T val)
{
    1. 새로운 노드 만들기
    2. 노드 값 초기화
    2-2 노드의 넥스트를 탑으로 바꾸기
    3. 탑을 새로운 노드로 바꾸기
}

이 로직 중 노드의 넥스트를 탑으로 바꾸기와 탑을 새로운 노드로 바꾸는 과정에서 문제가 생깁니다.

내가 위에서 세팅했던 탑과 아래에서 바꾸려고하는 실제 탑의 값이 서로 다를 수 있기 때문입니다.

째뜬 이런 이유로 해서 2-2와 3의 동작의 사이에는 안정성이 보장되지 않습니다.

 

그러면 우리는 이런 연산을 추가하면 좋을 것 같습니다.

void push(T val)
{
    1. 새로운 노드 만들기
    2. 노드 값 초기화
    2-2 노드의 넥스트를 탑으로 바꾸기
    if(내가 바꾸려고 하는 탑과 지금 탑이 동일한 값이라면?)
        3. 탑을 새로운 노드로 바꾸기
}

일반적으로 의사코드에는 CAS라는 이름으로 많이 등장하는 기능이 저기 if구절과 탑 노드를 바꾸기를 원자적인 연산으로써 대신하게 될겁니다

 

void push(T val)
{
    1. 새로운 노드 만들기
    1-1 원래 탑을 백업
    2. 노드 값 초기화
    2-2 노드의 넥스트를 백업해놓은 탑으로 바꾸기
    if(CAS(현재탑,변경하려고하는값,1-1에서 받아놓은탑)
        (3. 탑을 새로운 노드로 바꾸기) <- CAS연산에 포함되는작업
}

일종의 CAS연산이 commit의 역할을 하게 되는겁니다.

실제 1 ~ 2-2 까지의 연산은 스택에 영향을 끼치지 못하는 연산이지만 3번연산의 경우에는 실제 스택에 영향을 끼치는 로직이 되는것이죠.

하지만 2-2에서 얻은 탑과 3에서 바꾸려고하는 탑의 값이 다르다면 문제가 될 수 있기 때문에 이 작업의 원자성을 보존하고 그게 아니라면 작업을 하지 않는 CAS와 같은 함수가 필요했습니다.

 

그리고 원자성을 보장하는 함수는 예전 글에서 자주 언급했었습니다.

Interlocked 계열 함수는 연산의 원자성을 보장하고 있습니다.

그러므로 우리는 InterlockCompareExchange(Pointer,128,64등등)같은 함수를 사용할 겁니다.

함수 이름에서도 아실수 있겠지만 Compare + Exchange가 들어가게 됩니다.

CAS(Compare and Swap)와도 이름 컨셉이 잘 맞는것 같은 느낌이듭니다.

 

뭐... 팝은 이것과 동일합니다만 여러 문제가 있을겁니다.

이 문제들은 따로 공개하지는 않겠습니다.

이건 스스로 문제가 발생했을때 찾아서 해결할때 실력 향상이 되는 그런 문제들이라...

문제는 따로 공개하지 않고 여기서 마무리 하도록 하겠습니다.

 

 

갑자기 마무리라뇨...?

갑자기 마무리라고 하니 이상하게 생각하실수 있을겁니다.

락프리 스택에 대한 정리를 한다더니 왜 락프리 스택에대한 정리는 하다가 가느냐 생각하실수도 있습니다.

 

하지만 제가 이번 글을 쓰는 목적은 락프리가 어떻게 구현되느냐가 목적이 아니라 내가 왜 락프리를 써야되느냐에 대한 내용을 언급하기 위한 글이었기 때문에 사실상 락프리의 구현부는 상세하지도 않고... 심지어pop도 빠졌죠.

 

사실 락프리가 오랜 기간 지켜보면서 문제가 있는지 확인해야되는 알고리즘인건 맞지만 코드 자체가 길다거나 어마어마하게 어려운 느낌은 아닙니다.

물론 아까 말씀드렸던 문제점을 찾으시려면 상당히 심도있는 고민을 하셔야되겠습니다만...

 

힌트를 드리면 로그를 남기는 방법을 추천드리고 싶습니다.

물론 로그는 file이나 콘솔io를 말하는게 아니라 메모리상의 로그를 남기셔야되겠고...(file, console io들은 그자리에서 퀀텀타임 포기하기 때문에 느려지게되고 동기화도 걸려버려서 문제가 잘 안나타납니다...) push, pop할때마다 이 스레드가 어떤 탑을 어떤탑으로 바꿧고 그 때의 사이즈는 몇개인지... 등등 이런 모든것들을 다 확인할 수 있게 하셔서 문제가 터졌을때 어떤 스레드가 어떻게 잘못건드려서 이런 시나리오가 나왔는지 명백히 판단할 수 있다면 그건 락프리 알고리즘의 문제해결 부분의 좋은 포트폴리오로써 사용가능 하실겁니다.

 

자... 그럼 진짜로 떠나도록 하겠습니다.

그럼 오랜만에 긴글 읽어주셔서 감사합니다.

저는 다음글에서 더 좋은 내용을 가지고 돌아오겠습니다.

그럼 안녕히계세요.