세밀한 동기화 방식으로 구현된 Set 만들기
대단위 동기화 방식으로 구현된 Set은 멀티스레드에서 문제없이 수행되었다. 그러나 스레드 수가 증가함에 따라 수행속도 또한 같이 증가하기 때문에 멀티스레드에서 효과적으로 동작하는 자료구조라 하기 어렵다. 따라서 이번 장에서는 병행성을 향상시켜 멀티스레드에서 이점이 있도록 구현해 보도록 한다.
동기화 방식
- 대단위 동기화 Coarse-Grained Synchronization
- 세밀한 동기화 Fine-Grained Synchronization
- 낙관적 동기화 Optimistic Synchronization
- 게으른 동기화 Lazy Synchronization
- 논 블로킹 동기화 Non-Blocking Synchronization
이번에 만들어볼 멀티스레드 Set의 구현 방식은 세밀한 동기화이다. 이것은 자료구조 전체를 한번에 잠그는 대단위 동기화와 다르게 개별 노드를 잠구는 것으로 멀티스레드에서 병행성을 향상킨다.
전체 소스코드
#include <iostream>
#include <chrono>
#include <vector>
#include <thread>
#include <mutex>
using namespace std;
using namespace chrono;
class Node
{
public:
int key = 0;
Node* pNext = nullptr;
mutex nodeLock;
Node() {}
Node(int value)
: key(value)
{
}
void Lock()
{
nodeLock.lock();
}
void Unlock()
{
nodeLock.unlock();
}
};
class Set_FineGrained
{
private:
Node head;
Node tail;
public:
Set_FineGrained()
{
head.key = 0x80000000;
tail.key = 0x7FFFFFFF;
head.pNext = &tail;
}
void Init()
{
while(head.pNext != &tail)
{
Node* pNode = head.pNext;
head.pNext = head.pNext->pNext;
delete pNode;
}
}
bool Add(int value)
{
head.Lock();
Node* pPred = &head;
Node* pCurr = pPred->pNext;
pCurr->Lock();
while(pCurr->key < value)
{
pPred->Unlock();
pPred = pCurr;
pCurr = pCurr->pNext;
pCurr->Lock();
}
if(pCurr->key == value)
{
pCurr->Unlock();
pPred->Unlock();
return false;
}
else
{
Node* pNew = new Node(value);
pNew->pNext = pCurr;
pPred->pNext = pNew;
pCurr->Unlock();
pPred->Unlock();
return true;
}
}
bool Remove(int value)
{
head.Lock();
Node* pPred = &head;
Node* pCurr = pPred->pNext;
pCurr->Lock();
while(pCurr->key < value)
{
pPred->Unlock();
pPred = pCurr;
pCurr = pCurr->pNext;
pCurr->Lock();
}
if(pCurr->key == value)
{
pPred->pNext = pCurr->pNext;
pCurr->Unlock();
pPred->Unlock();
delete pCurr;
return true;
}
else
{
pCurr->Unlock();
pPred->Unlock();
return false;
}
}
bool Contains(int value)
{
head.Lock();
Node* pPred = &head;
Node* pCurr = pPred->pNext;
pCurr->Lock();
while(pCurr->key < value)
{
pPred->Unlock();
pPred = pCurr;
pCurr = pCurr->pNext;
pCurr->Lock();
}
if(pCurr->key == value)
{
pCurr->Unlock();
pPred->Unlock();
return true;
}
else
{
pCurr->Unlock();
pPred->Unlock();
return false;
}
}
};
Set_FineGrained gSet;
const int NUM_TEST = 4000000;
const int KEY_RANGE = 1000;
void ThreadFunc(int num_Threads)
{
int key = 0;
for(int i = 0; i < NUM_TEST / num_Threads; ++i)
{
key = rand() % KEY_RANGE;
switch(rand() % 3)
{
case 0:
gSet.Add(key);
break;
case 1:
gSet.Remove(key);
break;
case 2:
gSet.Contains(key);
break;
default:
cout << "ERROR!" << endl;
exit(-1);
}
}
}
void main()
{
vector<thread> threads;
for(int i = 1; i <= 16; i *= 2)
{
threads.clear();
gSet.Init();
auto startTime = high_resolution_clock::now();
for(int j = 0; j < i; ++j)
{
threads.push_back(thread{ThreadFunc, i});
}
for(auto &t : threads)
{
t.join();
}
auto durationTime = high_resolution_clock::now() - startTime;
cout << "스레드 수: " << i << ", 걸린 시간: " << duration_cast<milliseconds>(durationTime).count() << endl;
}
getchar();
}
이 프로그램도 처음의 Set처럼 4백만번 동안 렌덤하게 Add, Remove, Contains 동작을 수행하며 처리속도를 측정하는 프로그램이다. 대단위 동기화 방식과는 순회하는 부분에서 락을 거는 방식이 다른것을 확인할 수 있다. 이제 코드의 세부를 하나씩 살펴보자.
class Node
class Node
{
public:
int key = 0;
Node* pNext = nullptr;
mutex nodeLock;
Node() {}
Node(int value)
: key(value)
{
}
void Lock()
{
nodeLock.lock();
}
void Unlock()
{
nodeLock.unlock();
}
};
대단위 동기화에서 mutex는 자료구조에 있었다.
그러나 세밀한 동기화에서는 병렬성 증가를 위해 자료구조 전체를 잠그지 않고 노드단위로 잠금을 수행해야 하기 때문에 mutex가 Node클래스에 포함되었다.
Set_CoarseGraind의 맴버 필드
class Set_FineGrained
{
private:
Node head;
Node tail;
public:
Set_FineGrained()
{
head.key = 0x80000000;
tail.key = 0x7FFFFFFF;
head.pNext = &tail;
}
void Init()
{
while(head.pNext != &tail)
{
Node* pNode = head.pNext;
head.pNext = head.pNext->pNext;
delete pNode;
}
}
/*...*/
}
여기까지는 비슷하다. 단, 자료구조 전체를 잠글 일이 없어졌으므로 mutex는 맴버변수에서 제거되었다.
Set_CoarseGraind.Add(int value)
bool Add(int value)
{
head.Lock();
Node* pPred = &head;
Node* pCurr = pPred->pNext;
pCurr->Lock();
while(pCurr->key < value)
{
pPred->Unlock();
pPred = pCurr;
pCurr = pCurr->pNext;
pCurr->Lock();
}
if(pCurr->key == value)
{
pCurr->Unlock();
pPred->Unlock();
return false;
}
else
{
Node* pNew = new Node(value);
pNew->pNext = pCurr;
pPred->pNext = pNew;
pCurr->Unlock();
pPred->Unlock();
return true;
}
}
대단위 동기화와는 다르게 자료구조가 어떤 일을 수행할때 자료구조 전체를 잠그지 않는다. 이 말은 노드를 순회할때 이 노드에 대한 락을 획득해야 한다는 것을 의미하는 것이다. 따라서 값이 바뀌는 부분 뿐만 아니라 순회할때도 하나하나 락을 획득하고 진행해야만 한다. 코드 사이사이에 노드를 잠그고 푸는 부분이 추가되어 다소 복잡해보이지만 개념적으로는 별로 어렵지 않다.
어떤 사람이 돌다리를 건넌다고 상상해보자.
- 왼발부터 진행한다고 할때 왼발이 딛을 돌이 고정되어있는지 확인하고 발을 내딛는다. (락을 획득한 뒤 진행)
- 그 다음으로 오른발을 내 딛으려면 다음 돌이 고정되었는지 확인한 뒤 발을 내딛는다. (락을 획득한 뒤 진행)
- 이제 왼발이 딛었던 돌은 필요가 없다. (진행한 노드는 락 반환)
- 원하는 값이 있는 노드를 찾을 때 까지 반복
그 밖의 동작은 어렵지 않다. 함수에서 return하기 전에 노드에 대한 잠금을 반환해야 하는 것은 당연하다.
Set_CoarseGraind.Remove(int value)
bool Remove(int value)
{
head.Lock();
Node* pPred = &head;
Node* pCurr = pPred->pNext;
pCurr->Lock();
while(pCurr->key < value)
{
pPred->Unlock();
pPred = pCurr;
pCurr = pCurr->pNext;
pCurr->Lock();
}
if(pCurr->key == value)
{
pPred->pNext = pCurr->pNext;
pCurr->Unlock();
pPred->Unlock();
delete pCurr;
return true;
}
else
{
pCurr->Unlock();
pPred->Unlock();
return false;
}
}
순환하는 부분은 Add(...)와 동일하다.
값을 발견했다면 pPred->pNext를 변경하고 락을 반환한 뒤 떨어져 나온 노드를 삭제한다.
Set_CoarseGraind.Contains(int value)
bool Contains(int value)
{
head.Lock();
Node* pPred = &head;
Node* pCurr = pPred->pNext;
pCurr->Lock();
while(pCurr->key < value)
{
pPred->Unlock();
pPred = pCurr;
pCurr = pCurr->pNext;
pCurr->Lock();
}
if(pCurr->key == value)
{
pCurr->Unlock();
pPred->Unlock();
return true;
}
else
{
pCurr->Unlock();
pPred->Unlock();
return false;
}
}
Contains(...)는 본질적으로 순회로 구성된 메서드이기 때문에 더 설명할 것이 없다.
실행 결과
| 스레드 | 대단위 동기화 | 세밀한 동기화 | 낙관적 동기화 | 게으른 동기화 | 논 블로킹 동기화 |
|---|---|---|---|---|---|
| 1 | 1512 | 48010 | 0 | 0 | 0 |
| 2 | 3811 | 33553 | 0 | 0 | 0 |
| 4 | 4392 | 22064 | 0 | 0 | 0 |
| 8 | 5106 | 16115 | 0 | 0 | 0 |
| 16 | 20346 | 33249 | 0 | 0 | 0 |
일단 소요된 시간이 어마어마해진것이 가장 눈에 띈다. 생각해보면 당연하다. 한번 동작할때 한번만 잠그는 대단위 동기화와 다르게 이것은 노드가 길어지면 길어질수록 더욱 빈번하게 잠금을 획득해야만 한다. 잠금이 많아질수록 오버해드로 인한 성능저하가 심해지는건 당연하다. 그러나 목적은 달성했다고 할 수 있다. 스레드 수가 증가함에 따라 걸리는 시간이 줄어디는것을 확인할 수 있다.