본문 바로가기
컴퓨터/Server

Lock Free

by 김짱쌤 2015. 4. 28.

Lock Free

지금까지 자원 Lock의 필요성과 여러가지 Lock의 활용방식을 공부했다. 논리적 측면에서 Deadlock 이슈를 피해서 lock을 사용한다면, 문제없이 자원공유가 가능한 것처럼 보인다^^. 하지만 멀티 쓰레드 프로그래밍의 어려움은 여기서 부터 시작한다. 앞에서 조금씩 언급했지만, 무차별적인 Lock은 기아현상을 유발할 수 있다. 사용자가 느끼기에 중요한 쓰레드가 상대적으로 별로 중요하지 않은 쓰레드에 밀려서 자원획득을 못하고 있을 가능성도 있다. 프로그래머가 프로그래밍을 잘하면 해결할 수 있는 문제라고 생각할지도 모른다.

그럼 성능이슈는 어떤가? CRITICAL_SECTION을 사용하는 Mutex역시 시스템 자원이다. Lock을 거는것 하나하나가 시스템 자원요청이라고 생각하면 락을 거는 것 자체가 오버헤드이다. 게다가 자원을 얻을 때까지 나머지 대기 쓰레드는 Blocking 상태에 빠진다. 이전에 네트워크 이벤트 핸들링을 함께하신 분들이라면, 멀티 쓰레드에서 Blocking방식을 사용한다는 것 자체가 숨이 턱턱막히지 않는가? 자원을 자주 사용하는 게 아니라면 문제 없지만, 정말 빈번하게 접근해야하는 공유 자원이라면? 만약 서버의 수많은 워커쓰레드가 클라이언트 세션들의 목록을 공유하고 루프마다 한번씩 전체 클라이언트 세션을 순회하고 업데이트 한다면? 세션에 접근할 때마다, 다음번 세션으로 이동 때마다 lock unlock이 반복된다면? 이러면 차라리 싱글쓰레드 서버가 빠른 상황이 연출될 것이다.(실제로 그렇다!)

이래서야 멀티 쓰레드 프로그래밍을 하는 이유가 사라진다. 하지만 여전히 컴퓨터는 프로세서 개수를 늘이는 방향으로 진화하고 있으니, 어딘가의 누구가 만든 무언가의 방법이 있을 것이다. 그런것들을 통칭 Non-Blocking (공유 자원 관리) 알고리즘이라 한다.

Non-Blocking 알고리즘

Non-Blocking 알고리즘에는 등급이 있다. 가장 이상적인 것은 전체 쓰레드가 공유 자원을 일관적으로 사용하면서도 대기하지 않고 그냥 진행되는 것이다. 이것을 Wait-Free 수준의 알고리즘이라고 한다. 현시창이므로 Wait-Free를 제대로 구현하려면 많은 제약이 따른다. 그래서 매우 한정적인 상황에서만 Wait-Free 알고리즘을 적용할 수 있다. 일반적인 경우 Lock-Free 수준의 알고리즘을 사용한다. 항상 하나 이상의 자원이 유한한 단계에 획득되어서 그 사용을 끝마친다. 어떤 쓰레드가 자원을 획득할지 결정적이지 않으므로, 여전히 기아현상을 완전히 극복할 수는 없다. 이보다 낮은 단계의 Obstruction-Free 수준이 있다. 한개를 제외하고 다른 모든 쓰레드를 대기시키면 대기아닌 쓰레드가 자원을 획득하여 유한한 단계에 다 사용을 끝마칠 수 있다. 충돌중인 쓰레드를 멈추게해야한다는 점에서 진정 Non-Blocking이라고 부르기엔 좀 문제가 있지 않은가 하고 생각한다.

Lock-Free 알고리즘의 구조

자꾸 Lock-Free거리는데 실제로 Lock-Free를 어떻게 구현하는 것인가? 결론부터 말하자면 Atomic 연산을 통해 Lock-Free를 구현한다. 시스템에서(하드웨어 수준에서) 원자성을 보장하는 연산을 atomic 연산이라고 한다. Windows에서 Atomic연산들은 보통 Interlocked**로 제공된다. atomic 연산은 실행이 한번에 완료되는 것을 보장하므로, 쓰레드 동기화 문제에서 쉽게 벗어날 수 있다.

여러 atomic 연산이 있는데 그중에 Lock free에 가져다 쓰기 가장 좋은 것이 CAS(Compare-and-set/swap, windows에서 비슷한 함수는 InterlockedCompareExchange)이다. 지금 쓰려고 하는 대상이 현재 쓰레드의 맥락에서 일관적이면, 변경을 가하고 그렇지 않으면 fail로 떠서 대기하지 않고 바뀐 상태로 쓰레드의 로컬정보를 갱신한뒤 다른 작업을 진행하는 것이다. Non-blocking I/O와 유사하게 체크해서 성공하면 계획대로 작업을 수행하고, 실패하면 다른작업을하다가 다시 체크를 하는 구조를 갖게된다.

Stack자료구조에서 Push하는 예제코드를 보면 쉽게 이해할 수 있다.

//http://www.gamedevforever.com/83 펌
void Push(Node* pNewNode)
{
   do{
      //이번 try의 top를 체크한다.
      Node* t = pTopNode;    
      //일단 새로 넣을놈의 next를 이번 try의 top으로 놓고
      pNewNode->pNext = t;   
   //내가 아는 top이 지금도 탑이면 pNewNode를 넣는다. atomic이라는게 중요!
   }while( !CAS(&pTopNode, t, pNewNode) ); //실패하면 다음번 try
}

ABA 문제

사실 위 예제는 사용할 수 있는 코드가 아니다. ABA라고 불리는 문제때문이다.




위 그림이 문제가 발생하는 지점을 설명하고 있다. 기존의 TopNode는 A이다. Pop을 하려는 쓰레드 1은 top을 A로 저장하고 next를 B로 저장할 거다. 그런데 중간에 다른 쓰레드 2가 끼어들어서 A랑 B둘다 Pop해 버렸다. 일반적인 상황이면 CAS체크에서 Fail이 뜨겟지만 멀티쓰레드의 세계는 오묘하다. 우리가 최적화를 위한 메모리풀 또는 오브젝트풀을 사용한다면 A가 쓰던 메모리 공간을 그대로 재사용할 수 있는 상황이 충분히 있다. 그래서 쓰레드 3이 중간에 또 끼어들어서 원래 A의 주소 그대로 Push를 해버렸다. 그리고나서 쓰레드 1이 CAS체크를 하면 Fail이 뜨지를 않는다! 그럼 이미 Pop해서 FreeList에 있는 B가 어이없이 스택의 Top이 되는 괴현상이 발생한다. 

이 문제는 CAS로 주소 값만 비교하다보니 자료구조 자체의 일관성을 보장하기 힘들다는 점에서 시작한다. 자료구조의 일관성은 단순히 하나의 주소만으로 체크하기 힘든 경우가 많기 때문이다. 따라서 일관성을 보장하는 다른 방법을 고안해야한다. stack pop에서도 마찬가지로 자료구조의 일관성을 체크하는 다른 방법을 고안해야한다. 해결 방법은 다양할 것으로 예상되나, 내가 찾은 솔루션은 pop count를 포함한 double check CAS를 사용한다. 

// http://15418.courses.cs.cmu.edu/spring2013/article/46참조
void Pop() {
  do{
    Node* top = mTopNode;
    int pop_count = mPopCount;
    Node* new_top = top->next;   
  //top과 popCount를 더블 쳌!
  }while( !double_compare_and_swap(&s->top, top, new_top, 
                                   &s->pop_count, pop_count, pop_count + 1) );
}


'컴퓨터 > Server' 카테고리의 다른 글

DB 연동하기  (0) 2015.05.09
멀티쓰레드 서버 버그잡기  (0) 2015.05.04
Thread Local Storage  (0) 2015.04.26
read-write lock  (2) 2015.04.26
DeadLock  (0) 2015.04.25