문서 편집 권한이 없습니다. 다음 이유를 확인해주세요: 요청한 명령은 다음 권한을 가진 사용자에게 제한됩니다: 사용자. 문서의 원본을 보거나 복사할 수 있습니다. [[분류: 동시성 프로그래밍]] == 개요 == 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되지 않음을 보장한다. == 종류 == # [[Treiber stack]] # [[Michael-Scott queue]] # [[Circular buffer]] # [[Work-stealing deque]] Lock free 문서로 돌아갑니다.