Ahn9807: 새 문서: 분류: 동시성 프로그래밍 == 개요 == Lock free는 Operation이 여러개가 동시에 진행되는 상황에서, 반드시 하나의 Operation은 끝까지 (Complete)수행됨을 보장하는 Data-structure혹은 Program을 의미한다. Lock-free는 Lock을 사용하지 않기 때문에, 프로그래머가 Lock의 시점을 일일이 지정하지 않아도 되며, Deadlock과 같은 장애도 일어나 지 않고, Scalability측면에서도 이점을 가져온다...

2024-05-22T05:08:34Z

새 문서: 분류: 동시성 프로그래밍 == 개요 == Lock free는 Operation이 여러개가 동시에 진행되는 상황에서, 반드시 하나의 Operation은 끝까지 (Complete)수행됨을 보장하는 Data-structure혹은 Program을 의미한다. Lock-free는 Lock을 사용하지 않기 때문에, 프로그래머가 Lock의 시점을 일일이 지정하지 않아도 되며, Deadlock과 같은 장애도 일어나 지 않고, Scalability측면에서도 이점을 가져온다...

새 문서

[[분류: 동시성 프로그래밍]]

== 개요 ==
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 - 편집 역사