Lock Based Concurrent Data Structure (2)

현재 우리가 계속해서 주목하고 있는 이슈는 Linked List에서 Lock을 사용 해야 하는데

Node 별로 Lock을 분산 시킬 것이냐 아니면 Lock을 하나만 쓸 것이냐 에 대한 것이다.

병행성을 좋게 하면 성능이 좋을 것이라는 기대를 하면서 Lock을 분산 시켜봤지만

Overhead가 커지면서 성능이 오히려 떨어질 수도 있다는 얘기 까지 했다.

 

이러한 이슈를 그대로 가지고 Concurrent Queues에 대해서 살펴보자.

Concurrent Queues

기본 아이디어는 Lock을 두 개를 사용하고, dummy node라는 것을 사용한다.

Lock을 하나만 사용했을 때는 bottle neck이 발생할 수 있기 때문에 head와 tail로 분리한다.

dummy node는 꺼내는 것 끼리는 경쟁이 발생할 수 있어도 node를 추가하는 것과

꺼내는 것은 서로 경쟁이 발생하지 않도록 한다.

초기 상태는 tmp node와 dummy node가 존재하는 상태이다.

그리고 Head와 Tail이 존재하는데, Head는 제일 앞을 가리키고 Tail은 제일 뒤를 가리킨다.

또 앞에서 설명한 것처럼 2개의 lock은 Head를 이용해서 무언가 일을 할 때 필요한 head_lock과

tail을 이용할 때 필요한 tail_lock이다.

tail_lock은 주로 node를 삽입할 때 사용한다.

 

Enqueue를 먼저 보면 뒷 쪽에 들어가게 되는데, 우선 tmp를 먼저 만들고

malloc을 통해서 받은 주소가 들어가게 된다.

받은 value 값을 tmp->value에 넣어준다. 그리고 제일 끝 부분이기 때문에 tmp->next = NULL 이 된다.

이를 link에 삽입만 하면 되는데, tail 관련된 일이기 때문에 tail_lock을 사용한다. (dequeue에서는 head_lock을 사용한다)

그래서 현재 tail의 next에다가 tmp를 넣어주었고 tail을 tmp로 지정했다.

 

또한 이렇게 Enqueue를 하면서 동시에 Dequeue를 병렬 수행이 가능하다.

Dequeue에서는 tmp를 만들어서 입력으로 받은 q의 head의 값을 넣는다.

그리고 new_head를 만들어서 tmp의 next 값을 넣어준다.

이후 new_head의 value에 인자로 들어온 value 값을 넣고 new_head를 q의 head에 넣어주었다.

즉 기존에 가지고 있던 q의 head를 가리키고 있던 dummy node가 사라지고 새로운 dummy가 생기게 했다.

 

여기까지 Concurrent Queue를 정리하면 Thread가 아무리 많아도 Enqueue를 가진 연산끼리, Dequeue를 가진 연산끼리

경쟁을 할 뿐 Enqueue를 가진 연산과 Dequeue를 가진 연산이 서로 경쟁하지는 않는다.

덕분에 뒤에서 집어넣고 앞에서 꺼내는 연산은 동시에 벌어질 수 있다.

다만 여기에서는 Queue에 아무것도 없을 때 Dequeue를 통해 꺼내려고 하는 경우 wait 하는 기능이나

꽉 찬 상태로 아무도 읽지 않았을 때 Enqueue를 하려고 하면 wait 하는 기능은 구현 되지 않았다.

Concurrent Hash Table

이제부터는 Linked List나 Concurrent Queue로 Hash Table을 어떻게 구현할 것이냐에 대한 문제이다.

Concurrent Hash Table은 좀 더 상위 구조에서 여러 개의 Linked List를 사용한다.

Key 값이 어느 범위이냐에 따라 분산해서 Linked List에 넣는데,

코드에서 말하는 BUCKETS 이라는 것은 Linked List들 중 하나를 가리킨다.

 

lists는 Hash Table 전체를 포함하는 배열 형태의 변수이고

이것을 초기화 한다는 것은 이 List를 초기화 하는 것이다.

 

Hash에 insert를 하는 것은 Key 값에 따라 판단 후 분산해서 넣는다.

Lookup도 마찬가지로 같은 index를 사용해서 찾는다.

 

공교롭게도 key가 한 쪽으로 몰렸다면 어쩔 수 없이 Bottle neck이 생기게 될 것이다.

하지만 key가 골고루 분포 되어 있다면 연산이 여러 개의 list로 분산될 것이고 그에 따라 병렬성을 기대할 수 있다.

즉 앞에서 배운 Linked List나 Concurrent Queue를 이용해서 상위 구조인 Hash Table을 만든 것이다.

 

아래 그래프는 앞에서 보았던 그래프처럼 각 자료구조의 성능을 나타내는 그래프이다.

O가 그려진 그래프는 단순히 Concurrent List를 이용한 경우에 대한 성능이고

X가 그려진 그래프는 Concurrent Hash Table을 이용했을 때에 대한 성능이다.

이 그래프 역시 main 함수에서 Thread를 4개 정도 만들었고, 각 Thread가 하는 일은 만 번 이상의 loop을 돌면서

O의 경우 Concurrent Queue에서 Enqueue를, X의 경우 Hash Insert를 호출했다고 보면 된다.

이 그래프에서는 두 가지 자료구조 다 Single Queue를 사용한다.

하지만 Hash Table의 경우 그러한 Single Queue를 여러 개 사용해서 분산 효과를 기대한다.

 

결과를 보면 알 수 있듯이 Hash Table은 Concurrent List에 비해 훨씬 적은 시간이 걸린 것을 볼 수 있다.

 

Concurrent Queue의 경우 Linked List가 한 개 밖에 없어서 head와 tail로 Enqueue와 Dequeue의 경쟁은 피했을지라도

Enqueue끼리의 경쟁, Dequeue끼리의 경쟁은 피할 수 없기 때문에 반복을 많이 할수록 느려질 수 밖에 없다.

 

결론적으로 lock을 분산하는 것은 병행성을 확보하는데 큰 도움은 되는데, 반드시 성능으로 이어지진 않는다.