여러 코어 혹은 CPU를 활용하는 측면에서나 과도하게 Thread가 생성되는 비효율성을 줄이는 측면에서나 ThreadPool은 좋은 해답이 된다.
그러나 일반적인 ThreadPool의 구현에서도 병목이 되는 부분이 생기는데, 바로 ThreadPool에 맡겨질 WorkItem 들을 담고 있는 Queue 부분이다.
ThreadPool에 있는 여러 Thread가 하나의 Queue에서 WorkItem을 가져가려고 하는 Race Conditon이 발생하기 때문에 동기화가 필요하다. 특히 코어 혹은 CPU가 늘어나면 Thread도 그 만큼 많아지므로 경합(Contention)이 더욱 심해진다.
결국 하나의 Queue를 사용하는 ThreadPool은 확장성(scalability)이 떨어진다.
이런 경합이 발생하는 문제를 해결하는 방법은 의외로 간단할 수 있다. Queue를 하나만 사용해서 생기는 문제이기 때문에, Queue를 여러개 사용하면 된다. 즉 Thread마다 하나씩 Queue를 가질 수 있게 두는 것이다.
Thread 마다 자신의 전용 Queue를 만들어 두고, 해당 Thread에서 ThreadPool에 WorkItem을 추가하는 부분이 나오면 자신의 Queue에다가 추가해 두고, 또한 WorkItem을 처리할 때도 자신의 Queue에서 WorkItem을 가져다가 처리하게 되면 ThreadPool의 다른 Thread와 하나의 Queue를 두고 경합하는 상황을 피할 수 있다.
위 부분을 읽으면서 어렴풋이 느끼겠지만, 이건 뭔가 부족한 해결방법이다.
예를 들어 하나의 WorkItem을 처리하면 새로운 WorkItem이 여러개 생기는 형태의 작업인 경우에는, ThreadPool에 있는 Thread 중에 하나의 Thread에만 집중적으로 WorkItem이 몰리게 되는 현상이 발생하게 된다. 즉 한 Thread에는 작업이 넘쳐나는데, 다른 Thread는 놀고 있게 된다. Thread의 효율적인 활용에 문제가 생기게 되는 것이다.
이렇게 Thread 전용의 Queue를 사용함으로써 생기는 Thread간 불균형을 해결하기 위한 방법이 Work Stealing이다.
개념은 쉽다. 한 Thread가 자신의 Queue에 더이상 처리할 WorkItem이 없다면 다른 Thread의 Queue에 있는 WorkItem을 가져다가(Steal) 자신이 실행하는 것이다.
앞서 설명한 ThreadPool에 이 Work Stealing 기능을 추가하면, 혹 다른 Thread에 WorkItem이 집중되는 상황이 생기더라도, 여유가 있는 Thread가 그 WorkItem을 가져다가 실행시키게 될 것이므로 WorkItem은 비교적 공평하게 ThreadPool의 Thread들에게 분배가 된다.
따라서 확장성을 높이면서도 Thread가 비균등 현상을 해결할 수 있는 ThreadPool을 만들 수 있게 된다.
하지만...
얼핏 느낀분들도 있을거라 생각하는데, Work Stealing 기능을 추가한다는 것은 결국 하나의 Queue을 여러 Thread가 동시에 엑세스 할 가능성이 생긴다는 것을 의미한다. Queue를 소유한 Thread와 그 Queue에서 Work Steal을 하려는 Thread 말이다. 결국 Thread 전용으로 사용되는 Queue도 엑세스 할때 동기화 되어야 한다는 말이된다.
이렇게 되면 ThreadPool 전체에 하나의 Queue를 두고 사용하는 경우와 별반 나아질게 없다.(물론 조금은 나아지겠지만...)
처음 목표가 ThreadPool내의 Thread간에 경합과 동기화를 줄이려는 것이었는데, 이렇게 되고 보니 여전히 경합과 동기화를 피할 수 없게 된다.
ThreadPool의 Thread들에 고르게 WorkItem이 분배된 경우에는, Thread는 대부분 자신의 Queue에서만 WorkItem을 가져오기 때문에 동기화가 필요없는 경우이지만, 이때도 자신의 Queue를 엑세스 하기 위해 동기화 도구를 거쳐야만 한다.
하지만 우리에겐 또다른 무기가 있으니 바로 Lock-Free하게 구현된 Deque(Double Ended Queue)다.
Deque는 다들 알듯이, Queue와 달리 front와 end 모두에서 push와 pop이 가능한 자료구조다.
이제 Thread 전용의 Queue 대신에 Thread 전용의 Lock-Free Deque를 사용한다고 해보자.
시나리오는 이렇다.
Thread는 WorkItem이 생기면 자신의 Deque의 front에 push를 해 둔다. 그리고 자신이 WorkItem을 처리해야 할 것 같으면 Deque의 front에서 WorkItem을 pop해서 가져온다. 이 경우, Deque의 front에서 push와 pop은 하나의 Thread에 의해서만 이루어 지기 때문에 동기화가 필요없다.
그리고 다른 Thread가 해당 Thread의 Deque에서 Work Steal을 하는 경우에는 Deque의 end에서 pop을 한다. 이때 end에서 pop하는 부분을 Lock-Free하게 구현하는 것이다.
이렇게 되면 해당 Thread는 대부분 Deque의 front에서 작업이 이루어지고, 다른 Thread는 Deque의 end에서 작업이 이루어 진다.
결국 Deque안에 WorkItem이 몇개없는 상황 즉 front와 end가 가까운 경우가 아니면, 두 Thread가 경합을 벌일 경우가 현저히 줄어들게 된다.
(물론 노는 Thread가 많아서 Work Steal을 하려는 Thread들 끼리 경합이 발생할 수도 있지만, 이건 어짜피 노는 Thread들 끼리 경합이므로 그렇게 낭비라고 보기 어렵다.)
이렇게 되면 최대한 Thread의 Locality를 높이면서, 필요한 경우에도 Thread간 경합을 최소로 줄인 ThreadPool을 만들 수 있게 된다.
Intel의 TBB 나 .NET의 Parallel Extension등의 병렬 프로그래밍 라이브러리에 있는 ThreadPool은 거의 기본적으로 Work Stealing으로 구현된 ThreadPool이다.
ps)
노파심에서 덧붙이면,
ThreadPool 전체에서 하나의 Queue를 사용하는 경우라도, 이 Queue를 Lock-Free로 구현하면 간단하게 확장성을 확보할 수 있지 않을까 생각할 수 있다.
하지만 Lock-Free 자료구조라는 것이 동기화 도구를 사용하지 않도록 하여 Thread의 활동성(liveness)이 제한되는 상황, 예를 들어 Context Switch 같은 것들이 되지 않도록 하는 것일 뿐이지, 경합 자체를 줄여주는 것은 아니다. Lock-Free 자료구조라 하더라도 Thread가 많아지면 경합에 의해 손실되는 시간이 늘어나게 된다.
하지만 위에 설명한 Deque을 이용한 방법은 가능한 여러 Thread가 마주치지 않게 하는, 즉 경합자체를 줄이는 방법이라는 것을 염두해 둘 필요가 있다.
댓글 없음:
댓글 쓰기