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

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

1. 개념

 mutex를 할때, multi-core architecture에서는 주로 spin lock을 사용한다. lock-free이기도 하고, 보통 critical section을 실행하는데는 오래 걸리지 않기 때문이다.

2. TAS(Test-And-Set)

 TAS는 구현하기 편하다. 하지만 그 외에 좋은점이 아무것도 없다. lock을 얻을 때까지 while문에서 getAndSet이나 하고있으니 다른 코어의 cache hit ratio도 상관없고, 나만 생각하고 getAndSet 계속 돌리다가 내가 true로 만들었으면 진입하는 것이다. 이 때 getAndSet으로 인해 값이 false로 계속 쓰여진다면, 다른 코어들이 접근하는 해당 Atomic boolean은 valid bit이 0이 되고, 다시 갱신하기 위해 bus broadcasting을 한다. 이게 뭐냐면, 메모리에 접근해서 읽기 전에 다른 코어중에 그 값을 최신으로 가진 코어가 있는지 물어보는 것이다. broadcasting을 들은 다른 코어들은, 멈추고 그 값이 있는지 확인하게 된다. 따라서 총체적 난국으로 시간이 오래 걸리게 된다.

3. TTAS(Test-And-Test-And-Set)

 TTAS의 장점: 구현하기 쉽다. 읽어보고 들어갈만 하면(false이면) getAndSet을 해보니까 TAS보다 hit ratio가 높다.

 TTAS의 단점: 아직 멀었다. 코어 몇개만 되도 시간은 오래 걸린다.

4. Exponential Back-off

 TTAS를 해보는데, 경쟁에서 밀렸으면 연속으로 밀린 횟수 k에 대해, 2^k millisecond를 기다렸다가 하는 방법이다. 2^k는 단순히 예시이고, Delay_MIN, Delay_MAX를 정해서 일정 딜레이부터 2배씩 기다리고, 너무 많이 기다리면 안되니까 MAX를 넘으면 2배를 하지 않게 한다. 그래도 아직 멀었다.

5. Anderson's lock (Array-based lock)

 여기서부터 scalable lock이다.(아마 ideal한 시간-constant time-으로 lock을 걸 수 있다는 말인 것 같다) boolean array flag[]를 하나 잡고, 첫 번째만 true로 만든다. 1씩 증가하는 index tail이 처음 true를 가리키고, 쓰레드가 오면 가리키는 index를 주고 1 증가한다. 그리고 쓰레드는 받은 flag[index]가 true 될때까지 spin lock한다. 그러므로 unlock 할땐 자기 뒷자리의 false를 true로 만들어준다.

 주의할 점은, boolean끼리 붙어있으면 cache line 하나에 여럿이 올라가니까 cache line만큼 띄워줘야 valid bit이 변하지 않고 돌게 된다. 단점은 space complexity가 O(NL)이다(N = number of thread, L = number of lock).

6. CLH, MCS lock

 CLH는 Anderson's lock을 linked list로 구현해서 unbounded로 만든 것이다. 근데 왜 그러는지 모르겠는데 자기 앞에 놈의 boolean을 보고 lock을 얻는 방식이다. unlock, lock할때 자기 boolean을 뒤집는다. MCS는 정상적으로, 자기걸 보면서 lock을 얻고 unlock할땐 뒤에놈의 boolean을 바꿔주는 방법이다. CLH는 따라서 NUMA에서 사용하지 못하는데, memory가 각자 다른 core는 cluster가 다른 것인데, cluster간의 통신은 시간이 memory 통신보다 더 오래 걸린다. 따라서 매우 비효율적인 spinlock이 발생할 수 있다. MCS는 자기 boolean을 확인하므로 NUMA에서 사용가능하다. 그리고 abortable하게 만들 수 있는데, 이건 그냥 자기 노드 안에 prev 라는 포인터를 하나 만들어서 뒤를 가리키게 만들면 abort 한 것으로 알려주는 것이다. 더미노드 AVAILABLE이란걸 만들어서 가리키면, CLH와 같이 락을 넘기겠다는 표현을 하는것도 가능하다.

이외에 composite lock, hierarchical lock 이 있지만 크게 배울 내용은 아닌 것 같고, 수업때 공들여 설명하는 내용도 아니다.