Lock-free stack과 성능

대부분의 플랫폼에서 — 사실 이게 없는 SMP 머신은 내가 아는 범위 내에서 없다 — Compare-and-swap 이라 부르는 연산을 지원한다.[1] 이 명령어는 CAS( address, expected_value, new_value ) 의 형태로 쓰이는데, address의 값이 expected_value 이면 new_value로 바꾸고, 그렇지 않으면 바꾸지 않는다. 그리고 성공 여부나 이전 값을 반환하는 형태로 되어있다. 

이런 원시적인(…) 동기화 명령어를 사용하면 링크드 리스트 기반의 스택을 락(lock)없이 만들 수 있다. 즉 top 이 스택의 맨 위를 가리키는 구현이라 할 때, push 같은건 아주 naive하게 만들면, 다음처럼 구현하면 된다. (절대로 이 스택 구현을 바로 쓰지 말 것. 자세히 설명하진 않지만 ABA 문제에 대한 고려가 없다)

bool push( T* const value )
{
    Node* old_top = top;
    Node<T> node = new Node( value, old_top );
    while( !compare_and_swap( top, old_top, node ) ) // top을 혼자 변경한 경우 성공. Node용 메모리 할당이 메모리 재활용 떄문에 ABA문제가 생길 수 있지만 여기서는 신경끈다(…)
    {
        // A 지점
        old_top = top;
        node->next = old_top;
    }

내가 알고 있던 구현은 ABA 문제에 대한 해결을 빼면 사실 여기까지다. 간단하고, 대부분의 프로그래머가 쉽게 인지할 수 있는 수준 의 코드일 법하다. 근데 사실 이 코드에서는 top 에서 엄청난 수의 경쟁(contention)이 생길 수 있고,  코어 수가 늘어나면 이 경쟁은 더 큰 비용을 낳는데도 더 많이 일어나게 된다. 즉, lock-free로 만들었다고 해서 “성능 잘나오네”는 아닐 거라는 점.

내 경우엔 사실 이게 별 수 없다고 생각했는데, The Art Of Multiprocessor Programming에서[2] 다루는 concurrent stack에는 아이디어가 두 개 더 들어가있더라.

Backoff scheme

우선 쉬운 녀석 먼저. 사실 코어 수가 늘어나면 1. 충돌할 확률이 높고 2. CAS 연산 자체가 수반할 비용이 증가한다. 그래서 경쟁이 있는 것 같으면(=즉 A 지점에 다다르면), 아예 back-off 해서 잠시 쉬어버리는 것. LAN/WLAN의 binary exponential backoff 비슷하게 생각해주면 OK.

이 정도까진 좀 더 생각해보면 나오는 아이디어.

Elimination array

스택에서 push()와 pop()은 서로서로 cancel-out 해버린다. 즉, concurrent한 push()와 pop() 호출은 사실 top을 수정 안하고 두 스레드가 값을 교환하면 끝이란 얘기.  저자 중 한명의 논문이고 이 아이디어를 좀 더 복잡하게 구현한 논문(A Scalable Lock Free Stack Algorithm)이 웹에 있던데 한 번 읽어보면 좋을듯.

일단 아이디어 자체는, lock-free(혹은 wait-free면 더 좋고(…) )하게 아이템을 교환할 수 있는 elimination array를 두고,

  1.  push/pop 하기 전에 elimination array의 랜덤한 index를 하나 고르고
  2. 그 위치에 push 혹은 pop 시도
  3. 적당한 timeout[3] 을 두고 다른 스레드가 오길 대기. 
  4. 3의 시도에서 바로 만나거나, 기다리다 만나거나 여튼 짝이 맞는 상대(push면 pop, 혹은 그 반대로)면 아주 즐겁게 값을 교환하고 스택을 떠남. 짝이 틀리면 1로 가서 재시도.
  5. 타임아웃이 일어나면 스택 자체에 push/pop 시도

하는 형태로 동작하게 하자는 것. 이러면 top 하나에서 compare-and-swap하며 생기는 병목을 막는 훌륭한 알고리즘이 된다. 심지어 이 elimination array 자체가 일종의 백오프 스킴으로도 작용함…

 

여튼 결론?을 내자면. 공부 좀 해야겠다(…). 공부해서 남 안준다 :p
읽고, 살펴보고, 실험해보면 재밌기도 하거니와 피와 살이 된다는 느낌. 특히나 SMP 내지는 multi-core architecture가 주류가 되어가는 지금 시점에는 주목도 많이 받고 / 연구 결과도 다시 살펴보게 되는 시점인듯하니.

 

 

ps. 여기서 지나가는 문제. lock-free이면 wait-free인가? wait-free이면 lock-free인가? 둘의 차이는?

  1. 멀티스레딩/멀티코어 쪽 글에서 흔히 CAS라 줄여 쓰며, 일상에서 가장 흔히 볼 수 있는 x86 아키텍쳐에서는 CMPXCHG라는 명령어로 존재한다. 더 자세한 사항은 위키백과를 참고 []
  2. 좋은 책인데 지금 환율이 떡실신이라가격이 orz 스럽다. []
  3. 이걸 적응적으로 + 동적으로 계산하는 방법도 설명함 []

Published by

rein

나는 ...

4 thoughts on “Lock-free stack과 성능”

  1. [10:00:12] @ | >>> “lock-free” < “wait-free”
    [10:00:12] @ | True
    [10:03:29] @rein_uriel | // 정답
    [10:03:30] @rein_uriel | …
    [10:03:33] @ | :$
    [10:03:45] @rein_uriel | 댓글로 쓰실듯(?)

    +ㅅ+ 정답기념 (이게 아냐)

  2. xenosoz / 정답(…). wait-free => lock-free는 보장됨. 반대는 그렇지 않음

    비오 / 열심히 생각하면 나온다고도 함(..)

  3. Pingback: rein's world

Leave a Reply