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인 알고리즘은 보기가 거의 힘든데,

• 만들기 힘들고 ((임의의 알고리즘을 wait-free로 만들어주는 universal construction(만능 구성?) 이란게 있긴하다. 근데 이건 성능면으론 꽝. 단순히 이론적인 관점에서 접근한거라서…)) 
• 만들어도 lock-free 보다 성능이 잘 나오기가 힘들며,
• 대부분의 경우 lock-free로도 충분하다 (실제로 starvation이 일어나는게 흔치 않아서)

정도라…