Wait-free vs. lock-free

밑의 글(Lock-free stack과 성능)에서 글꼬리에 “wait-free 와 lock-free의 포함 관계는 어떤가?”와 그 의미를 물었다. 
정답자도 나왔고하니, 간단히 설명. 

영문 위키 백과에 이에 대한 설명이 있는데, 의미 부분만 간단히 짤라서 인용하면,

Wait-freedom is the strongest non-blocking guarantee of progress, combining guaranteed system-wide throughput with starvation-freedom. An algorithm is wait-free if every operation has a bound on the number of steps it will take before completing.

이다. 한글로 다시 말하자면, 어떤 알고리즘의 모든 연산이 완료될 때 까지 밟는 단계(명령어 수로 봐도)가 유한한(상수는 아님에 주의) 경우 wait-free이다.

 

비슷하게 느껴질 lock-free는,

Lock-freedom allows individual threads to starve but guarantees system-wide throughput. An algorithm is lock-free if every step taken achieves global progress (for some sensible definition of progress). All wait-free algorithms are lock-free.

다. 다시 말해, 개별 스레드는 starvation을 겪을 수 있지만(즉 진행을 못함), 전체적으로는 항상 진행해야 lock-free.

차이는 개별 스레드의 진행을 보장하냐 마느냐임. (어느 쪽이든 전체적으론 진행한다).
그리고 인용된 부분에도 나오지만, 개별 스레드도 무조건 진행하게되는 wait-free는 당연히 lock-free인게 자동으로 보장된다. 

 

ps. 사실 wait-free이면 좋다. 하지만 정말 중요한건, “실제로 더 좋은 성능이 나오는가” 하는 것.
실제 시스템에서 wait-free인 알고리즘은 보기가 거의 힘든데,

  • 만들기 힘들고[1] 
  • 만들어도 lock-free 보다 성능이 잘 나오기가 힘들며,
  • 대부분의 경우 lock-free로도 충분하다 (실제로 starvation이 일어나는게 흔치 않아서)

정도라…

  1. 임의의 알고리즘을 wait-free로 만들어주는 universal construction(만능 구성?) 이란게 있긴하다. 근데 이건 성능면으론 꽝. 단순히 이론적인 관점에서 접근한거라서… []

Author: rein

나는 ...

3 thoughts on “Wait-free vs. lock-free”

  1. “모든 연산이 그 연산이 완료될 때까지 밟는 과정의 수(the number)에 bound되면”이란 조건이랑 “모든 연산이 완료될 때 까지 밟는 단계(명령어 수로 봐도)가 유한한(상수는 아님에 주의)”이란 조건이 같은 의민건가?

    그러니까 내 말은 내가 보기에는 wait-free 란게 어떤 연산을 아무런 제약 없이돌렸을 때나 병행해서 돌렸을 때나 같은 시간안에 끝나야 한다는 의미인 것 같은데.

    내가 영어를 잘못해석하고 있는 건지;;

  2. 같은 시간 안에 끝난다기보단, 어떤 상한선이 있다는 얘기죠.
    그게 같은 시간이 되는건 사실상 힘든게 대부분의 wait-free 알고리즘이,

    1. 작업을 시작해서 변경 사항을 만들어내고
    2. 이걸 반영하는데, 자기가 (다른 스레드를) 도울게 없나 보고
    3. 있으면 돕고, 자기꺼 시도
    4. 실패해도 다른 스레드가 도와줄꺼라 믿고 종료

    하는 식으로 돌아서 명확히 “같은 시간”이라고 말할건 잘 안나와요;
    다만 일정 상한선 안에서 다른 스레드가 돕게되서 어떻게든 되긴하지만요(…)

  3. 오, 그렇군 ㅎㅎ 난 waitfree에 대해서는 아예모르니. 다만 위키피디아 영어의 한글 해석에 국한한 이야기였음.

Leave a Reply