게으른 동기화 방식으로 구현된 Set 만들기

낙관적 동기화 방식은 멀티스레드에서 병렬성을 유지하면서도 락의 횟수를 크게 줄여 성능을 향상시켰다. 그러나 아직도 유효성 검사를 위해 반복 탐색해야 하며 계속 탐색에 실패하여 기아현상이 생길 수 있는등의 잠재적인 문제가 치명적이다. 유효성 검사를 반복 탐색하지 않고 해결할 수 있는 방법은 없을까?

동기화 방식

대단위 동기화 Coarse-Grained Synchronization
세밀한 동기화 Fine-Grained Synchronization
낙관적 동기화 Optimistic Synchronization
게으른 동기화 Lazy Synchronization
논 블로킹 동기화 Non-Blocking Synchronization

이번 장에서는 게으른 동기화방식으로 멀티스레드 Set을 구현해 본다. 유효성 검사를 반복 탐색하지 않고 해결할 수 있을 뿐만 아니라 일반적인 컨테이너 형태의 자료구조에서 가장 많이 호출되는 Contains(...)를 무 대기등급으로 개선할 수 있게 된다.

전체 소스코드

#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;
    bool isDeleted = false;

    Node() {}

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

    void Lock()
    {
        nodeLock.lock();
    }

    void Unlock()
    {
        nodeLock.unlock();
    }
};

class Set_Lazy
{
private:
    Node head;
    Node tail;

public:
    Set_Lazy()
    {
        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 Validate(Node* pPred, Node* pCurr)
    {
        return (!pPred->isDeleted)
            && (!pCurr->isDeleted)
            && (pPred->pNext == pCurr);
    }

    bool Add(int value)
    {
        Node* pPred = nullptr;
        Node* pCurr = nullptr;
        while(true)
        {
            pPred = &head;
            pCurr = pPred->pNext;
            while(pCurr->key < value)
            {
                pPred = pCurr;
                pCurr = pCurr->pNext;
            }
            pPred->Lock();
            pCurr->Lock();

            if(Validate(pPred, pCurr))
            {
                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;
                }
            }
            pCurr->Unlock();
            pPred->Unlock();
        }
    }

    bool Remove(int value)
    {
        Node* pPred = nullptr;
        Node* pCurr = nullptr;
        while(true)
        {
            pPred = &head;
            pCurr = pPred->pNext;
            while(pCurr->key < value)
            {
                pPred = pCurr;
                pCurr = pCurr->pNext;
            }
            pPred->Lock();
            pCurr->Lock();

            if(Validate(pPred, pCurr))
            {
                if(pCurr->key == value)
                {
                    pCurr->isDeleted = true;
                    pPred->pNext = pCurr->pNext;
                    pCurr->Unlock();
                    pPred->Unlock();
                    // delete pCurr;
                    return true;
                }
                else
                {
                    pCurr->Unlock();
                    pPred->Unlock();
                    return false;
                }
            }
            pCurr->Unlock();
            pPred->Unlock();
        }
    }

    bool Contains(int value)
    {
        Node* pCurr = &head;
        while(pCurr->key < value)
        {
            pCurr = pCurr->pNext;
        }

        return (pCurr->key == value)
            && (pCurr->isDeleted == false);
    }
};

Set_Lazy 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();
}

pPred와 pCurr에 잠금을 걸고 유효성 검사를 하는등의 전체적인 구조가 크게 변하지는 않았다. Node클래스와 유효성검사의 변경점을 차차 살펴보도록 하자.

앞서 구현했던 것과 크게 달라지지 않았다. 이 동기화의 개요는 다음과 같다.

각 노드에 marked가 있어 true면 제거된것으로 처리ㅋ 순회시 대상노드를 잠글 필요가 없고 유효성을 판단하기 위해 다시 순회하지 않아도 된다.

class Node

class Node
{
public:
    int key = 0;
    Node* pNext = nullptr;
    mutex nodeLock;
    bool isDeleted = false;

    Node() {}

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

    void Lock()
    {
        nodeLock.lock();
    }

    void Unlock()
    {
        nodeLock.unlock();
    }
};

Node클래스를 살펴보면 새롭게 bool isDeleted가 추가된 것이 보인다. 이 플래그를 이용하여 낙관적 동기화의 유효성 검사처럼 반복 탐색하는 과정을 생략할 수 있게 된다.

Set_CoarseGraind의 맴버 필드

class Set_Lazy
{
private:
    Node head;
    Node tail;

public:
    Set_Lazy()
    {
        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 Validate(Node* pPred, Node* pCurr)
    {
        return (!pPred->isDeleted)
            && (!pCurr->isDeleted)
            && (pPred->pNext == pCurr);
    }
    /*...*/
}

유효성 검사를 하는 bool Validate(...)의 내용이 순회를 하지 않도록 변경되었다. 먼저 pPred와 pCurr에 잠금을 걸어야 하는건 동일하다. 그리고 두 노드 모두 지워진 노드가 아니면서 pPred->pNext == pCurr인지를 체크한다. bool isDeleted 필드를 추가함으로 인해 리스트 전체를 한번 더 순회하지 않더라도 유효성 검사가 가능하다.

Set_CoarseGraind.Add(int value)

bool Add(int value)
{
    Node* pPred = nullptr;
    Node* pCurr = nullptr;
    while(true)
    {
        pPred = &head;
        pCurr = pPred->pNext;
        while(pCurr->key < value)
        {
            pPred = pCurr;
            pCurr = pCurr->pNext;
        }
        pPred->Lock();
        pCurr->Lock();

        if(Validate(pPred, pCurr))
        {
            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;
            }
        }
        pCurr->Unlock();
        pPred->Unlock();
    }
}

프로그램의 소스코드 자체는 낙관적 동기화와 동일하다. 그러나 내부적으로 bool Validate(...)의 동작이 처음부터 다시 탐색하는것이 아니라 pPred와 pCurr의 isDeleted만 확인하는 방식으로 변경되었기 때문에 성능은 대단히 개선되었다고 할 수 있다.

Set_CoarseGraind.Remove(int value)

bool Remove(int value)
{
    Node* pPred = nullptr;
    Node* pCurr = nullptr;
    while(true)
    {
        pPred = &head;
        pCurr = pPred->pNext;
        while(pCurr->key < value)
        {
            pPred = pCurr;
            pCurr = pCurr->pNext;
        }
        pPred->Lock();
        pCurr->Lock();

        if(Validate(pPred, pCurr))
        {
            if(pCurr->key == value)
            {
                pCurr->isDeleted = true;
                pPred->pNext = pCurr->pNext;
                pCurr->Unlock();
                pPred->Unlock();
                // delete pCurr;
                return true;
            }
            else
            {
                pCurr->Unlock();
                pPred->Unlock();
                return false;
            }
        }
        pCurr->Unlock();
        pPred->Unlock();
    }
}

삭제동작 또한 pCurr->isDeleted = true;가 추가된것을 제거하고는 낙관적동기화와 동일하다. 게으른 동기화의 가장 큰 목적은 낙관적 동기화에서 유효성 확인을 위한 반복탐색을 제거하는 것이었기 때문에 일단은 이정도로 충분하다.

Set_CoarseGraind.Contains(int value)

bool Contains(int value)
{
    Node* pCurr = &head;
    while(pCurr->key < value)
    {
        pCurr = pCurr->pNext;
    }

    return (pCurr->key == value)
        && (pCurr->isDeleted == false);
}

지금까지 낙관적 동기화와 거의 동일한 Add(...)와 Remove(...)였다면 Contains(...)는 대단히 짧아진것을 볼 수 있다. 개으른 동기화에서 Contains(...)는 유효성 검사를 하기위한 반복탐색이 필요없을 뿐만 아니라 위치를 찾아가기 위한 pPred도 필요없으며, 심지어 노드를 잠글 필요도 없어졌다. 이로서 완벽하게 무 대기등급의 락프리 알고리즘으로 동작하게 된다. 일반적인 자료구조의 상황에서 삽입이나 삭제의 횟수보다 탐색의 횟수가 많은것을 생각하면 이것은 상당히 유용하다고 볼 수 있다.

실행 결과

스레드	대단위 동기화	세밀한 동기화	낙관적 동기화	게으른 동기화
1	1512	48010	3003	1340
2	3811	33553	2169	1032
4	4392	22064	1388	824
8	5106	16115	776	550
16	20346	33249	894	436

이제는 확실히 쓸만해졌다는 느낌이 드는 측정 결과이다. 단일스레드 상태에서 대단위동기화보다 빨랐으며 스레드 수 증가에 따라 병렬성도 증가하는것을 확인할 수 있다. 뿐만 아니라 반복 탐색으로 이해 스레드가 기아에 빠지는 문제도 해결할 수 있었다. 다만 개으른 동기화에서도 문제는 남아있다.

실제 delete는 언제 수행해야 하는가?
Add(...)와 Remove(...)가 블로킹 알고리즘이다. 개선할 수는 없는가?

조금 더 알아보기 - shared_ptr

이 예제가 실려있는 멀티프로세서 프로그래밍(모리스 헐리히, 니르 샤비트 공저/김진욱, 하재승 공역)에는 위 예제가 java로 작성되어 있다. 따라서 지워지는 시점은 JVM의 GC가 결정할 일이며 프로그래머가 간섭할 수 없다.(다만 어느정도 유도할 수 있으나 책의 범위와 벗어난다고 생각하여 생략) C++에서 메모리 누수없는 개으른 동기화를 구현하기 위해서는 삭제된 리스트들을 별도로 관리하는 FreeList등을 만들어 이 자료구조가 완전히 필요 없어졌을 때 별도로 삭제해주는 방법을 구현하거나 다음에 소개될 shared_ptr을 사용하면 된다. 그러나...

std::shared_ptr로 구현된 개으른 동기화 Set

전체 소스코드

#include <iostream>
#include <chrono>
#include <vector>
#include <thread>
#include <mutex>
#include <memory>
using namespace std;
using namespace chrono;

class Node_sp
{
public:
    int key = 0;
    shared_ptr<Node_sp> pNext = nullptr;
    mutex nodeLock;
    bool isDeleted = false;

    Node_sp() {}

    Node_sp(int value)
        : key(value)
    {
    }

    void Lock()
    {
        nodeLock.lock();
    }

    void Unlock()
    {
        nodeLock.unlock();
    }
};

class Set_Lazy_sp
{
private:
    shared_ptr<Node_sp> pHead;
    shared_ptr<Node_sp> pTail;

public:
    Set_Lazy_sp()
    {
        pHead = make_shared<Node_sp>(0x80000000);
        pTail = make_shared<Node_sp>(0x7FFFFFFF);
        pHead->pNext = pTail;
    }

    void Init()
    {
        pHead->pNext = pTail;
    }

    bool Validate(shared_ptr<Node_sp> spPred, shared_ptr<Node_sp> spCurr)
    {
        return (!spPred->isDeleted)
            && (!spCurr->isDeleted)
            && (spPred->pNext == spCurr);
    }

    bool Add(int value)
    {
        shared_ptr<Node_sp> pPred = nullptr;
        shared_ptr<Node_sp> pCurr = nullptr;
        while(true)
        {
            pPred = pHead;
            pCurr = pPred->pNext;
            while(pCurr->key < value)
            {
                pPred = pCurr;
                pCurr = pCurr->pNext;
            }
            pPred->Lock();
            pCurr->Lock();

            if(Validate(pPred, pCurr))
            {
                if(pCurr->key == value)
                {
                    pCurr->Unlock();
                    pPred->Unlock();
                    return false;
                }
                else
                {
                    shared_ptr<Node_sp> pNew(new Node_sp(value));
                    pNew->pNext = pCurr;
                    pPred->pNext = pNew;
                    pCurr->Unlock();
                    pPred->Unlock();
                    return true;
                }
            }
            pCurr->Unlock();
            pPred->Unlock();
        }
    }

    bool Remove(int value)
    {
        shared_ptr<Node_sp> pPred = nullptr;
        shared_ptr<Node_sp> pCurr = nullptr;
        while(true)
        {
            pPred = pHead;
            pCurr = pPred->pNext;
            while(pCurr->key < value)
            {
                pPred = pCurr;
                pCurr = pCurr->pNext;
            }
            pPred->Lock();
            pCurr->Lock();

            if(Validate(pPred, pCurr))
            {
                if(pCurr->key == value)
                {
                    pCurr->isDeleted = true;
                    pPred->pNext = pCurr->pNext;
                    pCurr->Unlock();
                    pPred->Unlock();
                    return true;
                }
                else
                {
                    pCurr->Unlock();
                    pPred->Unlock();
                    return false;
                }
            }
            pCurr->Unlock();
            pPred->Unlock();
        }
    }

    bool Contains(int value)
    {
        shared_ptr<Node_sp> pCurr = pHead->pNext;
        while(pCurr->key < value)
        {
            pCurr = pCurr->pNext;
        }
        return (pCurr->isDeleted == false)
            && (pCurr->key == value);
    }
};

Set_Lazy_sp 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);
        }
    }
}

int 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();
    return 0;
}

이 소스코드는 기본적으로 앞에서 배웠던 개으른 동기화로 구현된 Set과 동일하다. 그러나 몇가지 차이점이 존재한다.

포인터 대신 shraed_ptr<T>을 사용
기존에 사용하던 Node대신 Node_sp사용 (내부의 pNext가 shared_ptr로 구현)
매인함수의 반환값이 void에서 int로 변경 (마지막에 return 0;추가)
주석 처리했던 delete하는 부분이 원천적으로 없음

기존에는 이 부분을 좀더 자세히 다루고 shared_ptr을 직접 구현해보는것도 기획했으나 아쉽게도 이 코드는 Windwos의 VS2013에서는 정상적으로 동작하지 않는다. 그렇다면 소스코드에 버그가 있는걸까? 리눅스의 gcc로 컴파일 옵션을 다음과 같이 설정하면 이 코드는 정상적으로 동작한다.

gcc -std=c++11 -lstdc++ -pthread 09_NB_List_Set_Lazy_sp_mn.cpp

위 코드를 Boost::shared_ptr로 바꿔도 gcc에서는 정상적으로 동작하는 프로그램이, VS2013에서는 중간에 종료되는 프로그램이 만들어진다. 이러한 불확실한 부분에 대해서는 좀더 다방면으로 조사되어야 할 필요가 있을 것이다. 리눅스 관련 내용을 도와주신 프로그래머 김영찬([email protected])님께 이자리를 빌어 감사의 말씀을 올린다.