LockFreeAlgorithm

UserPreferences

1. 개요
2. 목록
1. Lock-free Stack
2. Lock-free Queue
3. 링크

1 개요

락을 사용하지 않는 다중 스레드용 알고리즘/자료구조. 락 때문에 성능이 심각할 정도로 떨어져 본 적은 없다만, Lock Free~ 왠지 기분 좋은 단어가 아닌가.

일반적으로 CPU 레벨에서 제공하는 아토믹 연산을 가지고 구현한다. 그렇기 때문에 연산 지원 여부라던지, 메모리 정렬 문제라던지 꽤 신경써줘야 한다. 윈도우즈에서 제공하는 아토믹 연산은 여기에 가면 나와있다. 어셈블리를 좀 더 안다면 뭔가 새로운 세계가 열릴 것도 같은데...


2008-01-08
대략 1년 동안 이래저래 사용해본 결과, 아직은 시기상조라는 결론에 도달했다. 일단 코드가 어떻게 돌아가는지 이해하기가 어려운 데다가 버그가 발생해도 재현이 매우 어렵다. 간단한 스핀락 정도야 별 문제가 없다만... 머리 좋은 분들이 안정적인 코드 짜줄 때까지 기다리자.

2 목록

일단은 윈도우즈 전용이다. *nix 계열에 InterlockedXXX 함수 시리즈가 있는지는 모르겠다. 있겠지. 있다면 함수만 바꿔줌으로서 별 무리 없이 컴파일 될 수도? 아 몰라. 나중에 갈 일 생기거든 생각하자.

그런데 가만히 생각해 보면, 스택이든 큐든 들어가는 아이템이 갯수가 정해져 있지 않다면, 메모리를 동적으로 할당해서 노드를 추가해야 한다. 그렇다면 메모리 할당 안에서 일어나는 직렬화는 어떻게 할 것인가? 이 안에서 락 쓰면 말짱 도루묵 아닌가? 풀(pool) 방식의 할당자를 만든 다음, 그 안에서 스핀락을 이용해 직렬화를 하면 부담은 줄겠으나, 뭔가 근본적인 해결책이 아니다. 근본적인 해결을 위해서는 (커널 레벨의) 락을 사용하지 않는 메모리 할당자가 필요하다!



2.1 Lock-free Stack

XP 이상에서는 SList 함수군을 이용해서 간단하게 만들 수 있다.


////////////////////////////////////////////////////////////////////////////////
/// \file LockFreeStack.h
/// \author excel96
/// \date 2006.9.29
////////////////////////////////////////////////////////////////////////////////

#pragma once

////////////////////////////////////////////////////////////////////////////////
/// \class cLockFreeStack
/// \brief 락을 따로 사용하지 않는 스택. XP 이상에서만 사용 가능하다.
////////////////////////////////////////////////////////////////////////////////

template 
<
    typename T,
    template <typename> class AL = std::allocator
>
class cLockFreeStack
{
private:
#pragma pack(push)
#pragma pack(MEMORY_ALLOCATION_ALIGNMENT)
    /// 유저 데이터를 저장하기 위한 구조체.
    struct NODE
    {
        SLIST_ENTRY List;
        T           Data;
    };
#pragma pack(pop)

    SLIST_HEADER m_ListHead;  ///< 리스트 헤드.
    AL<NODE>     m_Allocator; ///< 메모리 할당자.


public:
    /// \brief 생성자.
    cLockFreeStack()
    {
        InitializeSListHead(&m_ListHead);
    }

    /// \brief 소멸자.
    ~cLockFreeStack()
    {
        Clear();
    }


public:
    /// \brief 데이터를 추가한다.
    /// \param data 추가할 데이터.
    void Push(const T& data)
    {
        NODE* newNode = m_Allocator.allocate(1);
        m_Allocator.construct(newNode, NODE());
        newNode->Data = data;
        InterlockedPushEntrySList(&m_ListHead, &newNode->List);
    }

    /// \brief 데이터를 뽑아낸다.
    /// \param data 뽑아낸 데이터를 쓸 변수.
    /// \return bool 데이터를 뽑아낸 경우에는 true를 반환하고, 
    /// 데이터가 없는 경우에는 false를 반환한다.
    bool Pop(T& data)
    {
        PSLIST_ENTRY entry = InterlockedPopEntrySList(&m_ListHead);
        if (entry)
        {
            NODE* node = reinterpret_cast<NODE*>(entry);
            data = node->Data;
            m_Allocator.destroy(node);
            m_Allocator.deallocate(node, 0);
            return true;
        }

        return false;
    }

    /// \brief 모든 데이터를 삭제한다.
    void Clear()
    {
        T data;
        while (Pop(data))
            ;
    }


private:
    /// \brief 복사 생성 금지.
    cLockFreeStack(const cLockFreeStack&) {}

    /// \brief 대입 금지.
    cLockFreeStack& operator = (const cLockFreeStack&) { return *this; }
};





2.2 Lock-free Queue

큐 같은 경우에는 삽입/삭제가 일어나는 곳이 서로 다르므로 약간 복잡하다.


////////////////////////////////////////////////////////////////////////////////
/// \file LockFreeQueue.h
/// \author excel96
/// \date 2006.9.29
////////////////////////////////////////////////////////////////////////////////

#pragma once

////////////////////////////////////////////////////////////////////////////////
/// \class cLockFreeQueue
/// \brief 락을 따로 사용하지 않는 큐. 98 이상에서는 사용 가능하다.
////////////////////////////////////////////////////////////////////////////////

template 
<
    typename T,
    template <typename> class AL = std::allocator
>
class cLockFreeQueue
{
private:
#pragma pack(push)
#pragma pack(MEMORY_ALLOCATION_ALIGNMENT)
    struct NODE
    {
        NODE* Next;
        T     Data;
    };
#pragma pack(pop)

    NODE*    m_Head;      ///< 큐 헤드.
    NODE*    m_Tail;      ///< 큐 테일.
    AL<NODE> m_Allocator; ///< 메모리 할당자.


public:
    /// \brief 생성자.
    cLockFreeQueue()
    {
        m_Head = m_Allocator.allocate(1);
        m_Allocator.construct(m_Head, NODE());

        m_Tail = m_Head;
        m_Head->Next = NULL;
        m_Tail->Next = NULL;
    }

    /// \brief 소멸자.
    ~cLockFreeQueue()
    {
        Clear();
        m_Allocator.destroy(m_Head);
        m_Allocator.deallocate(m_Head, 0);
    }


public:
    /// \brief 데이터를 추가한다.
    /// \param data 추가할 데이터.
    void Push(const T& data)
    {
        NODE* oldTail = NULL;
        NODE* oldNext = NULL;

        // 새로운 노드를 할당한다.
        NODE* node = m_Allocator.allocate(1);
        m_Allocator.construct(node, NODE());
        node->Next = NULL;
        node->Data = data;

        // 테일 쪽의 Next 링크가 새로운 노드를 가르킬 때까지 루프를 돈다.
        bool addedNewNode = false;
        while (!addedNewNode) 
        {
            // 포인터들의 카피를 만든다.
            // 다른 스레드에서 테일 포인터를 변경할 수 있기 때문이다.
            oldTail = m_Tail;         
            oldNext = oldTail->Next; 

            // 테일 포인터가 변경되지 않았다면...
            if (m_Tail == oldTail) 
            {
                // 테일의 Next 포인터가 NULL이라면...
                if (oldNext == NULL) 
                {
                    // 테일의 Next 포인터 변경을 시도한다.
                    addedNewNode = CAS(&(m_Tail->Next), NULL, node);
                }
                // 테일의 Next 포인터가 NULL이 아니라는 말은, 
                // 다른 스레드에서 노드를 추가하고 있는 중이라는 말이다. 
                // 그러므로 테일 포인터 변경을 시도한다.
                else 
                {
                    CAS(&m_Tail, oldTail, oldNext);
                }
            }
        }

        // 테일 포인터가 새로운 노드를 가르키도록 변경한다. 실패할 수도 있는데,
        // 다른 스레드에서 처리해줄 것이므로 걱정할 필요 없다.
        CAS(&m_Tail, oldTail, node);
    }

    /// \brief 데이터를 뽑아낸다.
    /// \param data 뽑아낸 데이터를 쓸 변수.
    /// \return bool 데이터를 뽑아낸 경우에는 true를 반환하고, 
    /// 데이터가 없는 경우에는 false를 반환한다.
    bool Pop(T& data)
    {
        NODE* oldHead = NULL;
        NODE* oldTail = NULL;
        NODE* oldHeadNext = NULL;

        // 헤드 포인터가 다음 노드를 가르킬 때까지 루프를 돈다.
        bool advancedHead = false;
        while (!advancedHead) 
        {
            // 포인터들의 카피를 만든다.
            // 다른 스레드에서 테일 포인터를 변경할 수 있기 때문이다.
            oldHead = m_Head;
            oldTail = m_Tail;
            oldHeadNext = oldHead->Next;

            // 헤드 포인터가 변경되지 않았다면...
            if (oldHead == m_Head) 
            {
                // 헤드 포인터가 테일 포인터와 같다면...
                if (oldHead == oldTail) 
                {
                    // 헤드의 Next 포인터가 NULL이라면...
                    if (oldHeadNext == NULL) 
                    {
                        // 뽑아낼 아이템이 존재하지 않는다.
                        return false;
                    }

                    // 헤드의 Next 포인터가 NULL이 아니고, 
                    // 헤드가 테일과 같지 않다는 말은,
                    // 다른 스레드에서 테일에다 노드를 추가하고 있다는 말이다. 
                    // 테일 포인터를 업데이트한다.
                    CAS(&m_Tail, oldTail, oldHeadNext);
                }
                // 헤드 포인터가 테일 포인터와 다르다면...
                else 
                {
                    // 뽑아낼 아이템을 복사하고, 헤드 포인터를 뒤로 옮긴다.
                    data = oldHeadNext->Data;
                    advancedHead = CAS(&m_Head, oldHead, oldHeadNext);
                }
            }
        }

        m_Allocator.destroy(oldHead);
        m_Allocator.deallocate(oldHead, 0);

        return true;
    }

    /// \brief 모든 데이터를 삭제한다.
    void Clear()
    {
        T data;
        while (Pop(data))
            ;
    }


private:
    /// Compare and Swap
    bool CAS(NODE** location, NODE* comperand, NODE* newValue)
    {
        return comperand == InterlockedCompareExchangePointer(
            reinterpret_cast<volatile PVOID*>(location), newValue, comperand
            );
    }

    /// \brief 복사 생성 금지.
    cLockFreeQueue(const cLockFreeQueue&) {}

    /// \brief 대입 금지.
    cLockFreeQueue& operator = (const cLockFreeQueue&) { return *this; }
};

3 링크

• Some Notes on Lock-Free and Wait-Free Algorithms
  
• Programming Multi-threaded Architectures: Interlocked Operations
  
• Interlocked operations don't solve everything
  
• Application-Level Abstractions for Lock-Free Data Sharing
  
• Understand the Impact of Low-Lock Techniques in Multithreaded Apps
  
  
• Non-blocking Memory Allocator
  
• Allocating memory in a lock-free manner (PDF)
  
  
• High-Performance Synchronization for Shared-Memory Parallel Programs
  

• see also ThreadSynchronization
  

• CategorySystemProgramming