lock free vs wait free

동시성

 

lock free는 전체 시스템이 멈추지 않고 progress하는 것을 보장한다. 

어떤 스레드가 일부 중단되더라도 전체적인 연산은 계속 progress한다. 

= 최소한 하나의 스레드는 매번 forward progress

그러나 개별 스레드가 반드시 완료된다는 보장은 없다. 

= 다른 스레드가 무한히 뒤로 밀릴 수 있는 starvation 가능성 

대신 CAS 같은 원자적 연산, HW primitive로 쉽게 구현할 수 있다. 

 

wait free는 모든 스레드가 유한한 step 내에서 반드시 함수와 연산을 끝낸다는 것을 보장한다. 

가장 강력한 동시성 보장이지만 구현 복잡도가 매우 높다. 

어떤 스레드도 무한 루프나 무한 retry에 빠지지 않는다. 

= 경쟁이 심하더라도 모든 스레드가 bounded time 내에 연산을 완료하게 된다.