1. Misconception: Lock free algorithm은 항상 lock-based algorithm 보다 빠른것인가?

- Lock free algorithm은 사실상 cache traffic이 씹창나는 busy waiting 방법이다.

- 만약 간단한 시스템이면 lock free algorithm이 빠르지만, 복잡한 시스템(Job이 여러개 있는 등)에서는 더 느릴 수 있다.


2. Lock free algorithm의 핵심은 무엇인가? lock-based algorithm하고는 무엇이 다른가?

- Lock free algorithm은 busy waiting하는 방법이지만 lock-based algorithm은 contention 발생 시, 자신의 pCPU를 yield 하는 방법이다.


3. Lock-free stack이란?

- Push: top pointer에 CAS를 걸어 top을 업데이트

- Pop: 위와 마찬가지


4. Lock-free queue란?

- Enqueue: 1. tail->next update 2. tail move

- 두 개의 공유 변수 접근이 일어나므로 두번의 CAS가 일어난다. 단, 두 CAS 사이에는 critical section으로 보호되지 않으므로, tail move를 모든 쓰레드에서 일으킨다.

- Dequeue: 1. head := head->next

- 단, Enqueue에서 split CAS가 발생했으므로, 큐 empty시, Enq-1 -> Deq-1 -> Enq2가 발생된다면 세그멘테이션 폴트가 일어난다. 이를 방지하기 위해 tail move 후, 1번을 수행한다.


5. Lock-free list란?

- insert: 1. new node -> next := next node 2. CAS with previous node

- delete: 1. mark deleted node 2. CAS(check deleted) with next node


6. ABA problem

- 메모리 재사용되는 상황에서 나타나는 문제로, stack: top->A->B->C 에서 A 딜리트 후, top->B->C로 만드려고 하는데, 만들기 직전에 pop B/push A로 top->A->C로 만들어도 ptr가 변하지 않았기 때문에 의도와 잘못된 결과(top->A->B, where B is invalid)를 내는 상황이다.

- Workaround: 메모리 주소 하위 비트에 레퍼런스 카운터를 넣는다.



결론: 복잡한 시스템 (멀티 프로듀서/컨슈머 or + async jobs)에서는 lock-free가 적합하지 않다. 적은 수의 프로듀서/컨슈머에서는 잘 동작한다.