Written November 4, 2008 in Computer
밑의 글(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이 일어나는게 흔치 않아서)
정도라…
- 임의의 알고리즘을 wait-free로 만들어주는 universal construction(만능 구성?) 이란게 있긴하다. 근데 이건 성능면으론 꽝. 단순히 이론적인 관점에서 접근한거라서… [↩]
대부분의 플랫폼에서 — 사실 이게 없는 SMP 머신은 내가 아는 범위 내에서 없다 – Compare-and-swap 이라 부르는 연산을 지원한다.[1] 이 명령어는 CAS( address, expected_value, new_value ) 의 형태로 쓰이는데, address의 값이 expected_value 이면 new_value로 바꾸고, 그렇지 않으면 바꾸지 않는다. 그리고 성공 여부나 이전 값을 반환하는 형태로 되어있다.
이런 원시적인(…) 동기화 명령어를 사용하면 링크드 리스트 기반의 스택을 락(lock)없이 [...]
Entries RSS
3 Comments