List
전에는 성긴 동기화를 사용해서 구현 했는데 생각보다 성능이 안나왔다.
그럼 이번에는 세밀한동기화를 한번 살펴보자
세밀한 동기화
- 전체 리스트를 한꺼번에 잠그는 것보다 노드를 잠그는 것이 병행성을 향상시킬 수 있다.
- 전체 리스트에 대한 잠금을 두는 것이 아니라 각각의 노드에 잠금을 둔다.
- Node에 Lock()과 Unlock 메소드를 구현해야 한다.
- Node의 next field를 변경할 경우에는 반드시 Lock()을 얻은 후 변경해야 한다.
그러니 성긴 동기화는 Lock을 리스트에 사용했지만, 이번에는 Node에 Lock을 거는 방법을 사용한다.
따라서 노드를 새로 넣을때도, 읽을때도 Lock을 해야 한다.
- 주의점
- add와 remove 시점의 pred, curr가 가리키는 노드는 locking이 되어 있어야 한다.
- head부터 node 이동을 할 때 lock을 잠그면서 이동해야 한다.
- 예를 들어 a의 잠금을 푸고 나서 b (a->next 였던)의 잠금을 한다면 그 사이에 다른 스레드에 의해 b가 제거될 수 있기 때문이다.
- 즉, 이동 시 pred이 잠금상태 일 때 동안 curr의 잠금을 획득한다.
#include <iostream>
#include <thread>
#include <mutex>
#include <vector>
#define MAX 10000
using namespace std;
using namespace std::chrono;
class Node
{
public:
int key;
Node* next;
mutex m;
Node() { key = 0; next = nullptr; }
Node(int key)
{
this->key = key;
next = nullptr;
}
~Node() = default;
void lock()
{
m.lock();
}
void unlock()
{
m.unlock();
}
};
class List
{
public:
Node head, tail;
mutex lock;
List()
{
head.key = 0x80000000;
tail.key = 0x7FFFFFFF;
head.next = &tail;
}
~List() {}
void Clear()
{
Node* ptr;
while (head.next != &tail)
{
ptr = head.next;
head.next = head.next->next;
delete ptr;
}
}
bool Add(int key)
{
Node* pred;
Node* curr;
pred = &head;
curr = pred->next;
pred->lock();
curr->lock();
while (curr != &tail)
{
pred->unlock();
pred = curr;
curr = curr->next;
curr->lock();
}
if (key == curr->key)
{
pred->unlock();
curr->unlock();
return false;
}
else
{
pred->unlock();
curr->unlock();
Node* node = new Node(key);
node->next = curr;
pred->next = node;
return true;
}
}
void Print()
{
Node* curr = head.next;
while (curr != &tail)
{
cout << curr->key << " ";
curr = curr->next;
}
cout << endl;
}
void Print(int count)
{
Node* curr = head.next;
for (int i = 0; i < count; i++)
{
cout << curr->key << " ";
curr = curr->next;
}
cout << endl;
}
};
List temp_list;
void Thread(int thread_count)
{
for (int i = 0; i < MAX / thread_count; i++)
{
temp_list.Add(i);
}
}
int main()
{
for (int i = 1; i <= 8; i *= 2)
{
temp_list.Clear();
steady_clock::time_point start_time = high_resolution_clock::now();
vector<thread> v;
for (int j = 0; j < i; j++)
{
v.emplace_back(thread(Thread, i));
}
for (int j = 0; j < v.size(); j++)
{
v[j].join();
}
steady_clock::time_point end_time = high_resolution_clock::now();
auto time = end_time - start_time;
int result_time = duration_cast<milliseconds>(time).count();
temp_list.Print(20);
cout << "스레드 갯수 : " << i << endl;
cout << "걸린 시간 : " << result_time << endl;
}
}
리스트에 add부분을 보면 계속해서 lock과 unlock을 반복해서 끝까지 가는것을 볼 수 있다.
이 전에 lock을 많이 호출하면 느려졌던걸 본 적 있는데 과연 결과는 어떻게 될까
이번에도 10000개의 리스트이다.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
스레드 갯수 : 1
걸린 시간 : 2552
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
스레드 갯수 : 2
걸린 시간 : 1048
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
스레드 갯수 : 4
걸린 시간 : 656
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
스레드 갯수 : 8
걸린 시간 : 378
확실히 쓰는 이유가 있을정도로 엄청나게 빨라졌지만, 이 전에 했던 성긴 동기화보단 느리다.