Queue, Stack (for concurrent 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는 나중에도 쓰이므로 기억해두자.