multi threading 환경에서 두 개 이상의 스레드가 shared data 를 동시에 write 하면서 동기화되지 않은 상태일 때 프로그램 실행 결과가 interleaving (명령어 섞임)에 따라 달라지는 오류스레드는 addr space를 공유해서 여러 스레드가 code, heap, global variable 공유하기 때문에 동시에 접근 가능하다. 그러나 연산은 대부분 cpu에서 atomic하지 않고 변수에서 레지스터로 읽어오는 mov, 연산을 수행하는 add 등의 연산, 다시 결과를 변수에 쓰는 mov 총 3단계로 이루어진다. 그래서 특정 스레드의 작업 결과가 동기화되기 전에 접근해서 읽은 값으로 작업을 수행하면 업데이트가 정확하게 반영되지 않을 수 있다. lost update!!t1이 50..

동시성 lock free는 전체 시스템이 멈추지 않고 progress하는 것을 보장한다. 어떤 스레드가 일부 중단되더라도 전체적인 연산은 계속 progress한다. = 최소한 하나의 스레드는 매번 forward progress그러나 개별 스레드가 반드시 완료된다는 보장은 없다. = 다른 스레드가 무한히 뒤로 밀릴 수 있는 starvation 가능성 대신 CAS 같은 원자적 연산, HW primitive로 쉽게 구현할 수 있다. wait free는 모든 스레드가 유한한 step 내에서 반드시 함수와 연산을 끝낸다는 것을 보장한다. 가장 강력한 동시성 보장이지만 구현 복잡도가 매우 높다. 어떤 스레드도 무한 루프나 무한 retry에 빠지지 않는다. = 경쟁이 심하더라도 모든 스레드가 bounded tim..