대단위 동기화 방식으로 구현된 Set 만들기

지난 장에서는 모든 자료구조를 멀티스레드 락프리 자료구조로 변경가능한 범용적인 구현방식으로 Queue를 구현하였다. 그러나 범용적으로 손쉽게 가려는 욕심이 치명적인 성능저하로 이어져 결국 실제로 사용할 수 없는 코드가 되고 말았다. 이번 장에서는 간단한 자료구조인 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;

    Node() {}

    Node(int value)
        : key(value)
    {
    }
};

class Set_CoarseGraind
{
private:
    Node head;
    Node tail;
    mutex setLock;

public:
    Set_CoarseGraind()
    {
        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)
    {
        setLock.lock();
        Node* pPred = &head;
        Node* pCurr = pPred->pNext;

        while(pCurr->key < value)
        {
            pPred = pCurr;
            pCurr = pCurr->pNext;
        }

        if(pCurr->key == value)
        {
            setLock.unlock();
            return false;
        }
        else
        {
            Node* pNew = new Node(value);
            pNew->pNext = pCurr;
            pPred->pNext = pNew;
            setLock.unlock();
            return true;
        }
    }

    bool Remove(int value)
    {
        setLock.lock();
        Node* pPred = &head;
        Node* pCurr = pPred->pNext;

        while(pCurr->key < value)
        {
            pPred = pCurr;
            pCurr = pCurr->pNext;
        }

        if(pCurr->key == value)
        {
            pPred->pNext = pCurr->pNext;
            delete pCurr;
            setLock.unlock();
            return true;
        }
        else
        {
            setLock.unlock();
            return false;
        }
    }

    bool Contains(int value)
    {
        setLock.lock();
        Node* pPred = &head;
        Node* pCurr = pPred->pNext;

        while(pCurr->key < value)
        {
            pPred = pCurr;
            pCurr = pCurr->pNext;
        }

        if(pCurr->key == value)
        {
            setLock.unlock();
            return true;
        }
        else
        {
            setLock.unlock();
            return false;
        }
    }
};

Set_CoarseGraind 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 동작을 수행하며 처리속도를 측정하는 프로그램이다. 이 장에서는 다양한 방식으로 Set을 구현할 것이며 ThreadFunc(), main()등의 중복되는 코드는 반복하여 소개하지 않는다. 대단위 동기화의 개요는 모든 동작 직전에 자료구조 전체를 잠그는 것이다. 이제부터 세부 내용을 살펴보자.

class Node

class Node
{
public:
    int key = 0;
    Node* pNext = nullptr;

    Node() {}

    Node(int value)
        : key(value)
    {
    }
};

대단위 동기화로 구현된 Set의 Node는 별다른 설명이 필요하지 않을 정도로 단순한 형태를 가지고 있다. 값을 뜻하는 key와 연결리스트의 다음포인터를 가지는 pNext를 가진다.

Set_CoarseGraind의 맴버 필드

class Set_CoarseGraind
{
private:
    Node head;
    Node tail;
    mutex setLock;

public:
    Set_CoarseGraind()
    {
        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;
        }
    }
    /*...*/
}

이 장에서 구현하게 될 Set은 head와 tail의 보초노드가 있는 구현방식이다. 보초노드란 key값의 최대, 최소값을 가지며 연결리스트의 경계가 되는 노드를 말한다. 처음에는 아무 노드도 없기때문에 head.pNext는 곧장 &tail을 가리킨다.

지금까지와 마찬가지로 main에서는 스레드 수를 변경해 가며 같은 동작을 반복한다. 따라서 재사용을 위한 Init 메서드가 필요하며 그 구현은 모든 Node들을 지워주는 것이다.

그리고 대단위 동기화에서 자료구조 전체를 잠그는데 사용되는 mutex가 눈에 띈다.

0x80000000는 32bit signed int의 최소값이며 2진수로는 1000 0000 0000 0000 0000 0000 0000 0000, 10진수로는 -2,147,483,648 이다. 0x7FFFFFFF는 32bit signed int의 최대값이며 2진수로는 0111 1111 1111 1111 1111 1111 1111 1111, 10진수로는 2,147,483,647 이다.

Set_CoarseGraind.Add(int value)

bool Add(int value)
{
    setLock.lock();
    Node* pPred = &head;
    Node* pCurr = pPred->pNext;

    while(pCurr->key < value)
    {
        pPred = pCurr;
        pCurr = pCurr->pNext;
    }

    if(pCurr->key == value)
    {
        setLock.unlock();
        return false;
    }
    else
    {
        Node* pNew = new Node(value);
        pNew->pNext = pCurr;
        pPred->pNext = pNew;
        setLock.unlock();
        return true;
    }
}

대단위 동기화의 개요에 따라 Add동작을 처리하기 전 자료구조 전체를 잠근다. 그 뒤 pPred와 pCurr 포인터로 리스트를 한칸씩 검색해가며 인자로 들어온 value가 들어올 위치를 탐색한다. 만약 이미 값이 이미 있다면 unlock후 false를 리턴, 값이 없다면 새 노드를 만들어 삽입하고 unlock후 true를 리턴하게 된다.

Set_CoarseGraind.Remove(int value)

bool Remove(int value)
{
    setLock.lock();
    Node* pPred = &head;
    Node* pCurr = pPred->pNext;

    while(pCurr->key < value)
    {
        pPred = pCurr;
        pCurr = pCurr->pNext;
    }

    if(pCurr->key == value)
    {
        pPred->pNext = pCurr->pNext;
        delete pCurr;
        setLock.unlock();
        return true;
    }
    else
    {
        setLock.unlock();
        return false;
    }
}

Remove도 처리 직전 자료구조 전체를 잠근다. Add와 마찬가지로 pPred와 pCurr를 이용해 한칸씩 검색해가며 value를 찾는다. 값이 있으면 연결된 부분을 변경한 뒤 지우고 unlock후 true를 리턴, 없으면 unlock후 false를 리턴한다. 연결리스트의 기본적인 동작이기때문에 이해하는데 큰 어려움은 없으리라 생각된다.

Set_CoarseGraind.Contains(int value)

bool Contains(int value)
{
    setLock.lock();
    Node* pPred = &head;
    Node* pCurr = pPred->pNext;

    while(pCurr->key < value)
    {
        pPred = pCurr;
        pCurr = pCurr->pNext;
    }

    if(pCurr->key == value)
    {
        setLock.unlock();
        return true;
    }
    else
    {
        setLock.unlock();
        return false;
    }
}

마지막으로 살펴볼 Contains도 마찬가지로 전체를 잠그고 시작한다. 탐색 방법은 Add나 Remove와 동일하며 값이 발견되었을때는 unlock후 true를 리턴, 없다면 unlock후 false를 리턴한다.

실행 결과

실행결과를 보면 다음과 같다.

mutex를 사용했기 때문에 확실히 오버헤드가 느껴진다. 뿐만 아니라 스레드 수가 증가함에 따라 실행 속도도 같이 증가하기 때문에 멀티스레드를 사용함에 따라 오히려 손해를 보고 말았다.