sjo200 - CS 대학원 수업 정리 블로그

1. 개념

 transactional memory는 간단하게 operation 뭉텅이를 atomic하게 실행시켜주는 transaction을 위한 메모리이다. 만약 다른 코어에서 내가 쓴 메모리에 접근했다면, contention이 일어난 것인데 이를 언제 detect할 것인지 등에 대해(구현 방법에 대해) 얘기할 것이다.

2. 동작방법

 단순하게 한 transaction을 실행할 때 다른 코어에서 그 메모리를 건드리지 않으면 실행(commit? update?)한다. 아니면 Undo 한다(Haswell 기준). Undo는 transaction을 실행하기 전 메모리에 기록해놓는 것인데, Haswell은 hardware transactional memory가 구현되어 있어서 해당 hardware operation도 있고, 저장할 레지스터들도 다 준비되어 있다.

3. Design choices

 transactional memory를 구현하려면 세 가지를 고려해야 한다.

a. concurrency control - pessimistic: conflict가 많이 일어난다고 가정하고 lock을 걸고 실행한다.

   optimistic: conflict가 별로 없다고 가정하고 실행하고 validate해보고, Undo를 결정한다.

b. version management - eager: 바로 메모리에 써보고, Undo-log를 만든다.

lazy: 쓰지 않고, Redo-log를 만든다.

c. conflict detection - eager: lock 걸고 바로 확인해본다.

lazy: 다 실행하고 확인해본다.

구현방법은 링크로 대체한다.

https://www.slideshare.net/zzapuno/kgc2013-3

1. 개념

 멀티코어에서 모든 작업을 다같이 완료했음을 다같이 알기 위해서는 barrier가 필요하다. 이 말은, barrier로 몇 쓰레드가 먼저 실행되지 않도록 막는다는 말이다.

2. Sense-Reversing Barrier

 모두가 볼 수 있는 count를 만들고, size를 넣는다. 그리고 각 쓰레드는 mySense라는 flag를 갖고, sense라는 global flag가 있다. 쓰레드는 완료했을 경우 fetchAndDecrement로 count를 감소시키고, 반환된 값이 1이면 마지막임을 알 수 있다. 마지막이 아니면 while(mySense != sense)로 spin lock을 하고 마지막이라면 count를 size로 다시 set 해준 뒤 sense = mySense를 실행한다. 그럼 동시에 모든 쓰레드가 풀려난다. 가장 쉽게 생각할 수 있는 방법이면서 count에 bottleneck이 발생하여 가장 좋지 않은 방법이다. 각 쓰레드마다 다른 쓰레드를 기다리는 것을 await()라고 하자. 위 로직은 하나의 await() 구현방법이다.

3. Combining Tree Barrier

 combining tree를 만들듯이, Sense-Reversing Barrier의 size를 2로 정하고, 그것을 하나의 노드로 사용한다. 그래서 뒤에 await()가 실행된 쓰레드는 부모의 await()를 재귀 실행하고, 돌아와서 count를 다시 2로 set한뒤 sense = mySense를 실행한다. 앞에 실행된 쓰레드는 while(sense != mySense)로 기다린다.(이건 각 노드마다 공유되는 sense가 하나씩 있다.)

장점은 bottleneck이 없지만, 단점은 local spinning을 하기 때문에 NUMA에 부적합하다.

4. Tournament Tree Barrier

 NUMA에서 사용할 수 있도록, 그리고 RMW operation이 필요없게 tree를 만들어보자. structure를 미리 만드는데, winner와 loser를 미리 정해놓는다. winner에만 부모로 갈 수 있게 포인터를 설정해준다. 만약 loser가 먼저 들어오면, winner의 flag를 바꿔준뒤 자신의 flag에 spinning한다. winner는 자신의 flag가 바뀔때까지 spin하고, 바뀌면 부모의 await()를 재귀로 실행한다. 그리고 재귀 실행이 끝나면 파트너(loser)의 flag를 바꿔줘서 loser가 돌아갈 수 있게 하고 끝낸다.

bottleneck이 없고, fixed location spinning 하기 때문에 NUMA에 사용할 수 있다.

5. Dissemination Barrier

 아름다운 방법으로 Barrier를 구현할 수 있는데, cache coherence가 좋지 않다. 한 round 마다 2^k (k = 0, 1, 2,..) 다음 번째의 쓰레드에게 자신의 상태를 알리고, 2^k가 size를 넘으면 그만둔다. log n 번의 round로 완료할 수 있다.

6. Static Tree Barrier

 가장 이상적인 방법이다. 각 쓰레드 번호에 노드 하나씩 있다고 생각하고, 이진트리를 구성해보자. 그리고 missing child number(아직 자식노드 둘에게서 신호가 안왔을 때 2)를 저장한다. 그럼 leaf node는 그 number가 0이고, 자식이 있는 노드는 자식 개수만큼 있다. 해당 number가 0일때까지 spin 하고, 0이 되면 부모 number를 하나 빼준다. 그리고 global sense flag를 spin한다. root에서 0이 되면 global sense flag를 바꿔준다.

bottleneck 없고, cache coherence도 보장할 수 있다. massage passing architecture에서는 root가 자식에게, 그 노드는 또 자식에게 notify 해주면 된다.

1. 개념

 멀티코어 몇 개로 얼마만큼의 성능향상이 있을 수 있는지, 어떻게 일을 분배해야 최적으로 분배하는지, 분배하는건 어떻게 하는지 알아본다.

2. 성능향상에 관한 몇 가지 공식

Define work: total time on one processor

Define critical path length: longest dependency path, 

can't beat that(아무리 많은 코어라도, 이거만큼은 걸린다)

T_1 = time needed on one processor

T_p = time needed on p processor

T_inf = critical path length(time needed on infinite processor)

work law:  T_p >= T_1 / p

critical path law: T_p >= T_inf

 - optimal scheduler is greedy

proof of near-optimality도 한 번 보면 좋다.( T_p <= T_1 / p + T_inf ) 

이 부분은 위 공식만 적당히 이해하고 가면 괜찮았다. 암달의 법칙 보는 느낌

3. work stealing

 일을 분배할 때, 쓰레드마다 Double Ended queue(DEQueue)를 가지고 거기에 Runnable을 넣는다. 쓰레드는 자기 deque에서 하나씩 빼서 일을 실행한다. owner는 popBottom()으로 빼서 일하고, pushBottom()으로 일을 저장한다. 근데 일이 없으면 다른 쓰레드로 랜덤하게 가서 popTop()을 하는데, 다른 백수(thief)랑 contention이 일어날 수 있으니까 CAS를 한다. 이 또한 ABA problem이 발생할 수 있기 때문에, stamp를 사용해서 두 개를 비교하는 CAS를 사용하여 stamp와 일을 확인한 뒤 뺏어온다. isEmpty()의 경우, 여러 쓰레드에서 실행할 수 있으므로 linearizability를 보장하는게 좋을 것이다. 그리고 가능하다. 왜냐하면 top.getReference()로 확인한 뒤, bottom을 확인하고 비교하면 top은 줄어들기만 하므로, linearizability를 보장할 수 있다고 하는데... 책에서 보고 다시 찾으려니까 잘 안보인다

-----------더 볼거리--------------

1. balancer의 구현

- synchronization

public class Balancer {

  Boolean toggle =TRUE;

  public synchronized int traverse(t) {

    if(toggle)

      toggle = FALSE; return 0;

    toggle = TRUE; return 1;  

  }   

}

- CAS

while(true) {

    boolean prior = toggle.get();

    if(toggle.compareAndSet(prior, !prior)) {

        return (prior? 0 : 1);

    }

}

1. 개념

 array-based PQ, Tree-based PQ, Heap-based PQ, Skip-list-based PQ가 있다. removeMin, add를 할 수 있는 structure를 만들 것이다.

2. array-based PQ

 그냥 array에 priority 값을 index로 사용하고, removeMin을 하면 0부터 차례대로 읽어나가는 것이다. 예상 가능한 문제점들이 있다. 쉬우니까 생략한다.

3. tree-based PQ

 priority 값을 index로 사용하는데, 그 위로 모든 노드 값이 0인 binary tree가 있다고 생각하자. add를 하면 root까지 올라가야 하는데, 올라갈때 오른쪽으로 올라간다면 그 부모노드에게 ++, 왼쪽으로 가면 그대로 둔다. removeMin을 하면 root에서 1 이상이면 -- 후 왼쪽으로 이동, 아니면 오른쪽으로 이동한다. 각 operation별의 concurrency는 있겠지만, 둘이 동시에 실행하면 add가 채 끝나기 전에 removeMin에게 overtaken 될 수 있다. 무슨 말이냐면, 다른 노드에 의해 자신까지 올 수 있는 길이 생길 수 있다는 것인데, 총 8개의 노드(1~8)가 있을 때, 3, 4에 add 하고, 3을 담당한 쓰레드가 heap 상의 인덱스 1에서 멈추고, 4를 담당한 쓰레드는 완료했다고 치자. 그리고 removeMin 하면 3이 overtaken 된다.

4. Heap-based PQ

 이건 add, removeMin 둘다 자식노드와 부모노드를 lock하는데, 부모노드부터 lock한다. removeMin은 예상할 수 있듯이, 셋을 lock하여 어디로 내려갈지 정하는 것이고, add는 둘을 lock 하여 올라간다. add할때는 node의 상태를 busy로 바꿔서 parent가 busy면 아닐때까지 lock을 잠그려고 시도하고 풀고 반복하면서 spin lock하고, parent는 lock을 잡은 채로 큰 자식노드와 부모노드를 바꾸고 그곳으로 내려간다. 즉 removeMin은 add에 상관없이 쭉쭉 내려가고, add는 서로 순서가 바뀌지 않게 조심해서 올라간다. add가 보던게 removeMin에 의해서 올라갈 수 있기 때문에, 자신의 id가 node에 없다면 그냥 올라간다. 따라서 concurrency가 있으므로 linearizable 하다.

5. skip-list-based PQ (lazy skip-list)

 linearizable 하지 않지만, 앞에서 배웠듯이 quiescent consistency를 만들어낼 수 있다. 그리고 heap-based PQ를 성능에서 압도한다. 그냥 removeMin은 skip-list에서 첫 번째 원소를 빼는 것이고, add는 추가하는 것이다. 물론, lazy skip-list에서 발생한 문제는 또 일어날 것이고, 그렇기 때문에 말했듯이 constraint로 quiescent consistency를 만들어내야 한다. 

1. 개념

 skip-list란, 메모리를 list보다 더 많이 사용해서 (그리고 여러 데이터를 스킵해서) 빠르게 이동하여 볼 수 있게 하는 structure이다. 포인터를 많이 사용해서, 이진탐색과 같은 time complexity를 갖게 된다. skip-list의 한 노드는 여러개의 포인터를 가진다. 가장 윗 level의 포인터가 같은 level인 데이터를 가리키고, 그 밑의 level의 포인터는 그 밑의 level의 데이터를 가리킨다. 이미지를 보면 이해가 빠를 것이다.

 contains를 실행할 땐, 이진탐색으로 찾듯이 가장 위 포인터를 보고 크면 밑으로 한칸씩 내려가서 보고, 작거나 같으면 그 포인터로 이동하면 된다. remove는 해당 node의 포인터들이 가리키는 level과 어떤 노드가 자신을 가리키는지 레벨별로 알아야 한다. 이를 prev[], succ[]으로 찾아 list에서 했듯이 포인터 하나하나를 이어줘서 노드를 삭제시킨다. add 할땐 add 할만한 위치를 찾아서 random level로 넣어준다.

2. lock-based skip-list

 list 구현하듯이, add, remove, contains operation을 실행할 때 락을 걸고 한다. 포인터들을 다 옮겨주면 된다. 근데, 바로다음의 lock-free에서 할 수 있는 concurrency는 여기서 할 수 없다. 예를 들어, remove시 포인터를 제일 위부터 차례대로 바꿔주면, 다른 operation의 실행에 영향이 없다. 왜냐하면 그 노드를 볼 때, 윗 레벨의 포인터가 없으면 그냥 그 노드는 그보다 낮은 레벨인 노드와 같이 취급할 것이기 때문이다. 노드를 lock하기 때문에 이런 concurrency를 얻지 못한다. 

3. lock-free skip-list

 list에서는 어떻게 lock-free로 구현했는지 잘 생각해보자. AtomicMarkableReference를 썼고, CAS도 당연히 썼다. 다 똑같이 적용된다. 바로 앞서 말했듯이, remove에서 포인터를 하나씩 없애갈 수 있다. CAS에서 실패하면 다시 찾아가서 CAS 하는것도 똑같다. 또 똑같이 AtomicMarkableReference가 없으면 list에서 생긴 (add가 remove된 데이터에 연결해놓고 true를 리턴하는 그 문제)문제가 똑같이 생긴다.

4. lazy skip-list

 이번엔 다시 lock을 사용한다. 포인터마다 각각, 즉 노드마다 level 갯수만큼 mark bit를 두고, mark bit가 있는 포인터만 사용한다. remove할땐 locked-based에서 했던 것처럼 윗 level부터 mark를 지워나가면 된다. 여기서 logical remove가 끝나면 physical remove를 어떤 시점에서 하긴 해야하는데, 이것 때문에 다른 문제가 발생한다. remove 되고있는 곳에 contains를 하는 쓰레드가 있는데 remove가 끝나고 다른 쓰레드가 똑같은 값을 가진 노드를 추가해버려서 return false할 수 있기 때문이다. 이것 때문에 quiescent consistency가 보장되지 않아서 약간의 constraint를 추가하여 consistency를 얻어야한다. 그러나 그 제약이 미치는 영향은 크지 않아서 성능은 제일 좋다고 한다.

- Closed-Address Hash Sets (Unbounded)

1. 개념

 list, stack, shared counter를 concurrent하게 만드는 방법을 알아보았으니, 이번에는 Hash set도 concurrent하게 만들어보자. hash set은 add, remove, contains operation을 지원한다.

2. Coarse-grained hash set

 그냥 접근할 때 락 건다. bucket array 하나 잡고, hash function에 따라 해당하는 bucket에 operation을 실행한다. bucket 안에 여러개를 저장하면, 포인터로 연결해서 sequential하게 찾아야한다. resize는 add 했을때 조건이 되면 resize한다. sequential programming.

3. Fine-grained hash set

 이건 bucket마다 lock을 건다. 주의할 점은 resize 할때 bucket은 커지지만, lock 개수는 커지지 않으므로 lock 개수가 L개라면, modulo L 로 락에 접근해야 한다.

4. Lock-free hash set

 lock-free 하게 만들려면 생각 좀 많이 해봐야 할 것이다. 이전에 구현하던 방법대론 안되니까 List를 사용해야 한다. List를 만들고, bucket은 short cut이 되면 hash set이 구현된다. 근데 이 short cut으로 연결하려는데 recursive split-ordering이란 순서대로 bucket을 sentinel node에 연결해야 한다. 여기서 sentinel node란 data에 연결되는 포인터가 두 개 이상이 되지 않도록(contention이 쉽게 많이 일어나므로), 시작지점 더미 노드를 만드는 것이다. sentinel node는 보통 queue에서도 head, tail과 같이 데이터가 아닌 부분을 말한다. 

 recursive split-ordering으로 2 bits에 대해 순서를 매기면, 00, 01, 10, 11 을 다 뒤집어서 생각하면 된다. 00은 00번째, 01은 10번째, 10은 01번째, 11은 11번째인데, 즉 0, 2, 1, 3 순 대로 sentinel node가 위치하게 된다. 그리고, 데이터는 자신의 좌측에서 가장 가까운 sentinel의 bit와 자신의 LSB(least significant bits)가 같아야 한다. 따라서, sentinel node를 (x)로 표현하고 데이터는 x 로 표현해서 어떤 hash set을 나타내면, 

head->(0)->8->4->(2)->6->2->(1)->5->(3)->3->tail 

다음과 같이 표현할 수 있다. 여기서 3 bits로 늘리자고 하면, 다시 recursive split-ordering을 통해 4, 5, 6, 7의 순서를 정할 수 있고, LSB에 따라 데이터를 넣어주면 된다.

 이렇게 데이터를 만들고 나면, add, remove, contains는 쉽게 CAS로 만드는 방법을 생각할 수 있다.

- An Open Addressed Hash Set (array-based)

5. Cuckoo hashing

 Cuckoo란, 새의 일종인데 남의 새집에 가서 알들을 치워버리고 자신의 알을 낳는 종이다. Cuckoo Hashing은 array 두 개를 갖고 두 hash function을 가진다. 데이터를 add 할때, 첫 번째 array에 가서 무조건 바꿔본다. 바꿔서 null 이면 멈추고, 데이터가 있으면 두 번째 array로 가서 똑같이 한다. 그 때에도 데이터가 있으면 resize 한다. 이걸 concurrent하게 할려면, 2 dimension array로 리스트 테이블을 만들어야 하는데, 이건 책을 보는게 낫다. 나중에 쓰일 일도 없을 것이다.

6. Hopscotch hashing

 이건 좋다. concurrency도 되고, array-based라 cache coherence도 보장된다. 또한, 여기서 사용하는 constant H = 32일 경우, resize 할 확률은 1/32! 이다. 설명은 다음 페이지로 대체한다.

https://tessil.github.io/2016/08/29/hopscotch-hashing.html

1. 개념

Shared counting이란, 여러 쓰레드가 getAndInc를 한다고 생각하면 된다. 만약 진짜로 그렇게 한다면, bottleneck이 걸릴 것이므로, 이 챕터에서는 적은 contention으로 하게 해주는 structure를 소개할 것이다.

2. Software combining tree

 이건 좀 어려운 개념이다. 쓰레드(프로세서) 개수 / 2만큼 리프노드를 만들고, 쭉쭉 위로 둘씩 이어서 바이너리 트리를 만들어야 한다. 그리고 노드에서 contention하여 combining하는 것인데, combining하게되면, (왼쪽 노드가 combining 했을때) 오른쪽 노드 값을 합해서 부모노드로 들고 올라가는 것이다. 이후 distribute에서 왼쪽노드에 더해지기 전 값을 주고, 오른쪽노드에 왼쪽노드의 값을 더한 값을 주는 것이다. 편의를 위해 왼쪽, 오른쪽을 강제했다.

 이해를 돕기위해 다른 경우를 생각해보자. getAndInc에서는 먼저 접근한 놈은 상대적으로 나중에 접근한 놈보다 적은 값을 받는다. 나중에 접근한 놈은 먼저 접근한 놈부터 나중에 접근한 놈까지 더해진 값을 다 더해서 받기 때문이다. 이걸 combining tree와 같이 생각해보면 먼저 간 놈(combining 한 노드)이 적은 값을 받을 것이므로 나중에 간 combining 하지 못한 노드에게 큰 값을 주는 것이다. 코드를 보면 더 쉽게 이해될 것이다.

 장점으로는, contention을 한 노드에서 두 쓰레드만 하게 되므로 contention의 수가 대폭 줄어 효과적으로 contention을 해결할 수 있다. 그러나 단점으로는, 최악의 경우 n번의 counting을 할 때, O(nlogn)만큼 걸려서 오히려 비효율적이다. 따라서 많은 쓰레드가 contention하면서 counting할 때 사용하여야 좋은 structure이다.

3. counting network

 counting network는 balancer들을 여러개 사용해서 만드는 것이다. balancer란, 2개의 인풋에 2개의 아웃풋으로 만들어지는데, 한 토큰이 어느 인풋으로 들어오든 아웃풋이 매번 교차하면서 토큰을 내보내는 것이다. 따라서 어느 인풋으로 토큰을 주던지 두 아웃풋의 차이는 최대 1이다. 이걸 여러개 사용하면, 4개 인풋 4개 아웃풋인 모듈을 만들어 토큰이 차례대로 쌓이도록 할 수 있다. 이것을 network라고 한다.

 counting network를 쉽게 구성하는 방법에는 bitonic counting network, periodic counting network가 있다. 이는 검색하면 나오므로, 생략한다. 둘다 공통적으로, 재귀적인 구성을 통해 2^n의 인풋, 아웃풋을 가진 network를 만들 수 있다.

 어떻게 그게 가능한지 증명해보자. merger[k]를 k개 인풋 아웃풋인 network라고 하면, merger[k] 두개를 뒀을 때, 둘은 한 줄에서 약간 어긋나지만 잘 카운팅 될 것이다. 이를 merger[2k]인 두 개를 두고 인풋에 넣는다고 쳐도, 아웃풋은 비슷하게 어긋나지만 잘 카운팅 될 것이다. 어긋난다는 말은 한 줄씩 채워지지만, 마지막 줄의 빈 곳이 둘로 나눠질 수 있다는 것이다.

 여기서, 마지막에 merger 각자 아웃풋 1번째를 연결하는 밸런서 , 2번째를 연결하는 밸런서, ... 를 배치하면, 토큰은 올바르게 카운팅 된다. 이해가 안된다면 책을 보자.

4. diffracting tree

 이젠 인풋이 하나인 밸런서를 써보자. 그럼 당연히 contention이 일어날 것이다. 이 때, concurrent stack에서 사용한 EliminationArray를 사용해보자. 두 쓰레드가 만나 서로의 아이디를 교환한 뒤, 수가 작은 놈은 위로 보내고, 큰 놈은 아래로 보낸다. 이게 다다. 근데 성능이 좋다. 중요한 점은 linearizability가 보장되지 않아서, pipelining 하듯이 보내면 concurrency가 생긴다고 한다. 책에서 그 말밖에 안했는데, 아마 depth가 같은 놈끼리 토큰을 동시에 보내면 그게 되지 않을까 싶다.

 이외에 structure 몇 개가 더 있는 것 같은데 강의하지 않았다.

1. 개념

 큐는 concurrent하게 만들고 싶어도, 그럴 껀덕지가 없다. 왜냐하면 head, tail의 영역이 구분되있고, 결국엔 한놈한놈씩 해야한다. 스택은 push, pop이 같은 곳에서 일어나므로, 적당히 교체하는 방법을 사용하면 concurrency를 얻을 수 있다. 그리고 이 둘은 Unbounded이다. 즉, 포인터로 연결되어 구현된다.

2. 큐

 개념에서 말했다시피, 껀덕지가 없다. 근데, 여기서는 메모리 관리에 중요한 개념인 ABA Problem을 배운다. garbage collection이 없는 언어는, 메모리 관리를 직접 해야한다. deque된 노드들을 free-list에 넣은 뒤, enque를 해야할 때, free-list에서 가져와서 tail 앞에 이어준다. 문제는, 쓰레드 A가 head->a->b->tail 에서 a를 remove해서 head가 b를 가리키기 직전인데, 다른 쓰레드가 b를 free-list로 먼저 보내버리면 쓰레드 A가 free-list에 들어간 b를 가리키게 된다. 이렇게 원 데이터쪽이 free-list의 데이터를 가리키게 되는 문제가 ABA Probelm이다. 그거말곤 그냥 lock-free queue 구현하는 내용이 먼저 나오는데, 별로 어렵지 않은 내용이므로 생략한다.

3. 스택

 스택은 껀덕지가 많다고 했다. 왜냐하면 동시에 push, pop 하는 경우를 선거에 빗대보도록 하자. 2012년 대선에서 내가 문재인을 뽑아야겠다고 친구에게 말했는데, 친구는 박근혜를 뽑겠다고 한다(모든건 가정일 뿐이다...). 이 때 다른 후보들은 어차피 사표이므로, 서로 투표해도 1표씩 올라가므로 표차이가 같을 것이고, 투표 안해도 표차이는 같을 것이다. 다 시간낭비하지 말고 놀러가자고 하자(실제로는 투표율이 정치인들에게 중요한 압박요소가 되므로 투표합시다...). 이걸 스택에 적용하면, 동시에 두 쓰레드가 와서 push, pop을 하려고 할때, 서로 교환해주면 좋지 않을까? top에서 contention을 일으키지 않고, throughput을 높일 수 있기 때문이다. 

 이 때문에, Exchanger<Item> 이라는 structure를 만들어야 한다. Exchanger.exchange를 하게 되면, 아무것도 없을 때 자리에 들어가 잠깐동안 누가 오는지 안오는지 기다려보고, 나와 반대되는(push-pop) operation이 접근해오면, 그놈과 Item을 swap한다. 내가 push이면 Item을 들고 있었으니 나중에 확인했을 때, null 이면 성공한 것이고, 아니면 push를 만난 것이므로 실패한 것이다. 이런 방식으로 Exchanger를 구현해놓고, tryPop, tryPush를 만든다. 이건 뭐냐면, 스택에 가서 pop, push 해보고 CAS에서 졌으면 Exchanger로 가서 exchange를 실행하는 것이다. 안되면 다시 또 pop, push 해보고, exchange하는걸 timeout까지 반복하는 것이다. 

 이 때, 쓰레드가 여럿일 것이므로, exchanger 하나로는 안될 것이다. 따라서 Exchanger array를 만들고, random한 인덱스에 접근하게 해주는 EliminationArray를 만들어야 한다. 이를 통해 여러 쓰레드가 동시에 접근해도 contention 없이 push, pop을 해주는 스택이 만들어진다. 조금만 생각해보면, 당연히 push, pop 비율이 50:50이 되야 성능이 좋다. 이 EliminationArray는 나중에도 쓰이므로 기억해두자.

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이다.