낙관적 동기화 방식으로 구현된 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_Optimistic
{
private:
    Node head;
    Node tail;

public:
    Set_Optimistic()
    {
        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)
    {
        Node* pNode = &head;
        while(pNode->key <= pPred->key)
        {
            if(pNode == pPred)
            {
                return pPred->pNext == pCurr;
            }
            pNode = pNode->pNext;
        }
        return false;
    }

    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)
                {
                    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* 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 true;
                }
                else
                {
                    pCurr->Unlock();
                    pPred->Unlock();
                    return false;
                }
            }
            pCurr->Unlock();
            pPred->Unlock();
        }
    }
};

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

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

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

이번에 사용될 노드는 세밀한 동기화때 사용했던 노드와 같은 형태이다. 그러나 자료구조가 동작하는 알고리즘이 개선되어 잠금의 수가 크게 줄어든다.

Set_CoarseGraind의 맴버 필드

class Set_Optimistic
{
private:
    Node head;
    Node tail;

public:
    Set_Optimistic()
    {
        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)
    {
        Node* pNode = &head;
        while(pNode->key <= pPred->key)
        {
            if(pNode == pPred)
            {
                return pPred->pNext == pCurr;
            }
            pNode = pNode->pNext;
        }
        return false;
    }
    /*...*/
}

낙관적 동기화의 동작 방식은

1. 노드들을 탐색할때는 잠금을 걸지 않음
2. 탐색이 종료되면 잠금을 획득하고 유효성 검사
3. 유효하다면 진행, 아니라면 처음부터 다시 수행

하는 방식으로 진행된다. 이 코드에서 bool Validate(...)가 바로 3번에 해당하는 동작인 것이다. 잠금을 획득하고 들어온 뒤 &head부터 다시 탐색하여 pPred까지 도달하는지, pPred->pNext가 pCurr인지 확인하는 코드로 이루어져 있다.

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

돌 다리도 두들겨 보고 건너는 심정으로 하나하나 잠금을 획득했던 세밀한 동기화와는 다르게 깨끗한 탐색부분을 볼 수 있다. 탐색이 다 끝나면 pPred와 pCurr 모두에 잠금을 획득하고 if문을 통해 유효성을 검사한다. 유효할 뿐만 아니라 Add가능하다면(중복된 키값이 없다면) 새 노드를 만들어 리스트에 추가하고 return true로 빠져나오게 된다. 만약 유효하지 않는다면 pPred와 pCurr의 잠금을 해제하고 Line 5: while(true)로 돌아가 다시 수행하게 된다.

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)
            {
                pPred->pNext = pCurr->pNext;
                pCurr->Unlock();
                pPred->Unlock();
                // delete pCurr;
                return true;
            }
            else
            {
                pCurr->Unlock();
                pPred->Unlock();
                return false;
            }
        }
        pCurr->Unlock();
        pPred->Unlock();
    }
}

전반적으로 Add와 똑같지만 // delete pCurr부분을 보자. 리스트에서 제거된 노드를 왜 delete하지 않았을가? 정답이 바로 떠오른다면 멀티스레드 프로그래밍에 소질이 있는 사람일 것이다. 세밀한 동기화와 다르게 탐색에서는 잠금을 획득하지 않는다.

어떤 스레드가 Remove(...)를 통해 노드를 리스트에서 제거하고 delete하려는 순간 다른 스레드는 그 곳을 지나가는 도중 일 수도 있다.

만약 그렇게 된다면 Null Pointer Exception이 발생하게 되고 프로그램은 사망하게 된다. 그렇다면 저 곳을 지나가던 다른 스레드의 동작은 문제없이 진행될까? 그림을 통한 실험으로 알아보자.

낙관적 동기화로 구현된 Set의 동작 예제

0. 초기상태

자료구조가 위와 같은 상태에 있을 때

• A스레드: 17을 삭제
• B스레드: 20을 삽입

하는 상황을 가증해보자.

1. A스레드가 17을 삭제하기 위해 pPred(3), pCurr(17)까지 탐색

2. B스레드가 20을 삽입하기 위해 pPred(17), pCurr(21)까지 탐색

3. A스레드가 pPred(3), pCurr(17)에 대한 잠금 획득

이 동작 중에 B스레드가 자신의 pPred(17), pCurr(21)에 잠금을 획득하려 한다면 pPred(17)의 잠금을 획득하지 못하고 대기하게 된다.

4. A스레드가 유효성검사를 수행하고 17을 삭제(리스트에서 제거)

head부터 출발하여 pPred까지 도달하는데 성공하였으며, pPred->pNext가 pCurr인 것을 확인할 수 있다.

5. B스레드가 pPred(17), pCurr(21)에 대한 잠금을 획득

B스레드는 A스레드가 잠금을 반환한 이후에야 pPred(17), pCurr(21)에 대한 잠금을 획득할 수 있다. B스레드는 아직 pPred(17)이 삭제되었다는것을 알지 못한다. 다른 스레드의 동작과 관계 없이 진행될 수 있는 논블로킹 알고리즘의 특징을 확인할 수 있다.

잠금을 획득한 B스레드는 유효성검사를 수행하였으나 tail이 등장할 때 까지 pPred를 발견할 수 없었다.

6. B스레드는 처음부터 다시 20을 삽입하기 위한 위치를 탐색

데이터를 삽입하는 일련의 과정은 연결리스트의 동작과 동일하므로 생략하도록 한다.

이처럼 Remove(...)동작 시 리스트에서 제거된 노드를 delete하지 않는것은 의도된 사항이며 이로 인해 스레드들은 병렬성을 유지하면서도 정상적으로 동작하게 된다는 것을 알 수 있다.

Set_CoarseGraind.Contains(int value)

bool Contains(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 true;
            }
            else
            {
                pCurr->Unlock();
                pPred->Unlock();
                return false;
            }
        }
        pCurr->Unlock();
        pPred->Unlock();
    }
}

추가와 삭제에서 이 장의 어려운 부분은 다 넘어갔으므로 탐색부분에서 특별히 어려울점은 없다.

실행 결과

세밀한 동기화와 다르게 성능이 크게 개선되었으며, 스레드 수가 증가함에 따라 병렬성도 증가하는 모습을 보였다. 그러나 제법 만족스러운 Set을 만들었다고 하기에는 남겨진 문제들이 존재한다.

• 기아를 겪을 수 있다.
• 메모리를 delete하지 않는다.
• 유효성 검사에 대한 오버해드

먼저 이 프로그램은 기아를 겪을 수 있다.

단적인 예로 특정 스레드가 작업을 수행하려 할 때, 다른 스레드들이 앞선 노드에서 지속적으로 추가/제거를 반복하고 있다면 이 스레드가 하는 일은 이론적으로 영원히 기아에 빠질 수 있다. 하지만 기아상태를 겪는 경우는 흔치 않은 경우이므로 실제로는 대부분 제대로 작동한다.

다음으로 코드에서 실질적인 delete를 수행하지 않는다.

이것은 스레드간의 병렬동작 시 이미 지워진 노드에 접근하여 프로그램이 죽는 경우를 막기 위한 조치였지만 결과적으로는 메모리 릭이라 할 수 있다.

마지막으로 유효성 검사에 따른 오버헤드이다.

삽입, 삭제, 탐색의 과정에서 모두 유효성검사를 수행한다. 이는 빈번한 잠금에 비하면 엄청 작은 오버해드이긴 하지만 알고리즘의 시간복잡도로 따지면 최소 O(2N)이 소비되는 동작이다. 그것도 유효성 검사에 실패한 경우까지 고려한다면 더욱 길어질 것이다.