Garbage collection이 왜 문제? concurrent한 데이터 구조는 당연히 여러 쓰레드가 접근하고 있습니다. 그래서 당연히 이 모두가 사용을 마쳤을 때 free를 해주어야 하겠죠? 근데 그 타이밍 잡기가 어렵습니다. 그래서 나온 게 Hazard Pointer와 Epoch-based Reclamination입니다. Hazard Pointer 가장 단순한 방식입니다. 포인터 사용하기 전 protect해 주고, 다 쓰면 unprotect해 줍니다. 그리고 collect를…
Harris Linked List 어느 블로그에서 본 글 source 저 소스에 따르면 Concurrency 관련 논문들을 읽지 않는 이상 이게 뭔지 보통 모를 거래요. 왜냐? 가장 빠르고 단순한 Non blocking Linked list이지만, 실용적이지는 않다네요. Harris 링크드리스트에서 head와 tail 노드는 항상 존재합니다. 지워지지 않아요. 이 소스의 저자는 해리스 링크드리스트가 중국 직소 퍼즐(본문의…
Lock Free? Lock free가 진짜 락이 없다는 뜻은 아닙니다. Lock free는 하나의 작업은 꼭 완료가 된다는 조건이래요. (one of the ongoing operation is completed someday) 비슷한 조건으로 * Obstruction free : 하나의 쓰레드만 실행 될 때 그 작업은 무조건 완료됨 * Wait free : 모든 작업이 꼭 완료됨 가 있습니다. 하나의 작업이 꼭 완료가…