DCAS 및 배열 기반 Lock-Free Deque을 구현해봤습니다.

DCAS 구현은 Multi-word CAS를 구현해봤습니다. 여기를 참고하시면 됩니다.
참고한 논문은 http://people.csail.mit.edu/shanir/publications/DCAS2001.pdf 이 링크 타시면 바로 나옵니다.

#include "dcas.h"

/*
 * Refered to this paper:
 * “DCAS-BasedConcurrentDeques” by O Agesen et al.
 */

template<class T, size_t N>
struct lock_free_fixed_deque
{
    void pushBack(T* data)
    {
        while (push(back, 1, reinterpret_cast<size_t>(data)) != 0);
    }

    void pushFront(T* data)
    {
        while (push(front, N - 1, reinterpret_cast<size_t>(data)) != 0);
    }

    T* popBack()
    {
        return reinterpret_cast<T*>(pop(back, N - 1));
    }

    T* popFront()
    {
        return reinterpret_cast<T*>(pop(front, 1));
    }

private:
    lockfree_op::atomic_ext front, back{ .value = 1 };
    std::array<lockfree_op::atomic_ext, N> arr;

    size_t getOldAtom(
        lockfree_op::atomic_ext& atom)
    {
        lockfree_op::atomic_captured captured;
        do
        {
            captured = lockfree_op::cas1(atom,
                0, lockfree_op::value_status_t::NORMAL,
                0, lockfree_op::value_status_t::NORMAL);
        } while (captured.status != lockfree_op::value_status_t::NORMAL);

        return captured.value;
    }

    size_t push(
        lockfree_op::atomic_ext& atom,
        size_t increment,
        size_t data)
    {
        while (true)
        {
            size_t oldAtom = getOldAtom(atom) % N;
            size_t newAtom = (oldAtom + increment) % N;
            size_t oldElement = getOldAtom(arr[oldAtom]);
            size_t saveAtom = oldAtom;
            std::array<lockfree_op::cas_requirement, 2> requirements{
                lockfree_op::cas_requirement{
                .atom = atom, .expectedValue = oldAtom,
                .newValue = (oldElement == 0 ? newAtom : oldAtom) },
                lockfree_op::cas_requirement{
                .atom = arr[oldAtom], .expectedValue = oldElement,
                .newValue = data }
            };

            if (lockfree_op::dcas(requirements))
                return oldElement;

            if (requirements[0].expectedValue == saveAtom)
                return 1;
        }
    }

    size_t pop(
        lockfree_op::atomic_ext& atom,
        size_t increment)
    {
        while (true)
        {
            size_t oldAtom = getOldAtom(atom) % N;
            size_t newAtom = (oldAtom + increment) % N;
            size_t oldElement = getOldAtom(arr[newAtom]);
            size_t saveAtom = oldAtom;
            std::array<lockfree_op::cas_requirement, 2> requirements{
                lockfree_op::cas_requirement{
                .atom = atom, .expectedValue = oldAtom,
                .newValue = (oldElement == 0 ? oldAtom : newAtom) },
                lockfree_op::cas_requirement{
                .atom = arr[newAtom], .expectedValue = oldElement,
                .newValue = 0 }
            };

            if (lockfree_op::dcas(requirements))
                return oldElement;

            if (requirements[0].expectedValue == saveAtom &&
                requirements[1].expectedValue == 0)
                return 0;
        }
    }
};

Memory reclamation은 사용자가 하도록 deque에 push/pop되는 값을 포인터로 한정했습니다.

이전 글과 마찬가지로 적극적인 코드 리뷰 환영합니다 :grinning:

1 Like