Linked Lists (for concurrent set)

1. 개념

 Linked list를 사용해서 concurrent set(동시에 add, remove, contains operation이 가능한 structure)을 만들 수 있다. coarse-grained synchronization 외 방법은 각자 장단점이 있으므로 상황에 따라 적절한 structure를 사용해야 한다. 또한, 이 장에 나오는 structure는 모두 unbounded이다. 즉, 포인터가 잇도록 구현하는 것이다.

2. Coarse-grained synchronization

 간단히 생각해서, 여러 개의 쓰레드가 동시에 오면 한놈만 실행시켜준다. head에 lock을 걸어서 operation을 실행시킨다. 당연히 sequential programming이며, bottleneck이 발생한다.

3. Fine-grained synchronization

 이것부터 어느정도 병렬 실행의 효과를 본다. 첫 번째 lock 잡고, 두 번째 lock 잡고, 첫 번째 lock 풀고, 세 번째 lock 잡고, 두 번째 lock 풀고, 네 번째 lock 잡고, ... 해서 필요한 lock을 잡을 때까지 진행하는데, 이를 hand-over-hand라고 한다. remove()를 실행할 땐 없앨 노드와 그 이전 노드의 lock, 총 두개가 필요하다. add()는 더해질 위치 이전 노드만 lock 하면 된다. 데이터가 적어서 lock을 많이 걸어도 상관 없으면, 일반적으로 좋다.

4. Optimistic synchronization

 이건 hand-over-hand 하지않고 그냥 필요한 lock 둘을 잡은 뒤, head에서 lock 잡은 앞의 노드까지 가서 그 앞의 노드 뒤가 lock 잡힌 그 뒷 노드가 맞는지 확인하고 operation하는 방법이다. 이것을 validation이라고 하는데, lock을 잡았더니 잡기 직전에 그 노드가 지워졌다고 하자. 그러면 지워진 노드에서 remove operation을 한 뒤 return true 할 것인데, 이미 지워진 노드를 지워놓고 잘 지웠다고 하면 안되므로, validation이 필요하다. validate에 실패하면, lock 풀고 처음으로 돌아가서 다시 lock 잡고 validate 해야한다.

5. Lazy synchronization

  노드에 mark bit를 추가하여, remove 할때 mark bit를 1로 만들면, logically deleted 된 것이고, 포인터를 그 노드에 가지않도록 바꿔주면 physically deleted이며, linearization point이다. 왜냐하면, 한 쓰레드가 contains operation 도중에 멈추는데, 그 노드가 remove 된 뒤, 똑같은 값의 노드가 add로 앞쪽에 생겨버리면 contains operation을 다시 실행하면 찾는 값이 실제로 있는데도 없다고 false를 반환할 것이다. 따라서 이것에 유의하여 실행순서를 약간 강제하던지, consistency를 포기해야 한다. (여기서 consistency란, 뇌피셜: 한 history를 실행했을때 항상 같은 결과가 나오는 것을 말한다. 정확한 정의는 나중에 quiescent consistency에서 말하겠다.)

6. lock-free synchronization

 쉽게 생각해서, 이때까지 구현한 것들 중 lock 거는 것을 CAS로 해결한다. 만약 CAS에 실패하면, 처음으로 돌아가서 다시 CAS 해야한다. 그런데, 여기서는 AtomicMarkableReference 라는게 필요하다. 내가 확인한 데이터가 CAS로 접근할 때, 다른 쓰레드가 아무도 건들지 않았는가 확인하는 것이다. head->a->c->tail 에서 a->c에 add(b) 하는 도중이면서 remove(a)를 한다면, head는 c를 가리키면서, 추가된 b도 c를 가리키게 되어 제대로 add가 되지 않을 것이다. 그러므로 mark bit 또한 CAS할때 동시에 CAS하여, 총 네 개의 파라미터를 가진 CAS를 해야한다(expected ref, update ref, expected mark, update mark). remove하는 도중에는 mark를 1로 만들고, remove 마지막에 0으로 만들어서 다른 operation이 mark를 보고 remove 도중인지 알 수 있도록 해야한다. 물론, 지금 말하는 mark는 lazy sync.의 mark를 대체하는 atomic mark이다.