개요
Lock free는 Operation이 여러개가 동시에 진행되는 상황에서, 반드시 하나의 Operation은 끝까지 (Complete)수행됨을 보장하는 Data-structure혹은 Program을 의미한다. Lock-free는 Lock을 사용하지 않기 때문에, 프로그래머가 Lock의 시점을 일일이 지정하지 않아도 되며, Deadlock과 같은 장애도 일어나 지 않고, Scalability측면에서도 이점을 가져온다. 그러나 단점으로는 반드시 복수의 Atomic operation을 사용해야 하며 이는 Multiprocess환경에서 Cache coherence의 부담을 야기 하기 때문에, 반드시 Lock과 비교하여 빠르다고 할 수 없다는 점이 존재한다. 사실 대부분의 환경에서 짧고 Scalability가 중요하지 않는 프로그램 블럭을 Spinlock으로 보호하는 것이 제일 성능적으로 이점인 경우가 대다수이다.
Lock은 프로그램의 진행을 보장하지 않는다. 따라서 Lock이 있는 환경에서는 Deadlock, Livelock과 같은 상황이 일어날 수 있다. Lock freedom은 프로그래머가 이러한 조건을 신경쓰지 않아도, 동시성을 달성할 수 있게 해주는 패턴을 의미한다. 물론 Lockfreedom을 만족시키는 구조체를 작성하는 것은 동시성에 대한 고민을 하면서 작성하게 된다.
Lock freedom의 keyidea는 Single-instruction commit이다. 즉 CAS처럼 Atomic instruction을 활용하여서, commit point를 만들고, 그 시점에 동기화를 진행하는 것으로 Lock-free를 구현하게 된다.
Lock의 분류
Wait-free ⊆ lock-free ⊆ obstruction-free ⊆ nonblocking
- Wait-free: 모든 동시에 진행되는 작업들이 반드시 동시에 수행되어 종료됨을 보장한다.
- Lock-free: 동시에 진행되는 작업중에 하나의 작업은 반드시 끝남을 보장한다.
- Obstrcution-free: 만약 하나의 작업이 수행중이라면, 그 작업이 끝남을 보장한다.
- Nonblocking: 하나의 작업이 block되더라도, 다른 작업이 영향받아 block되지 않음을 보장한다.