논블로킹 자료구조 Linked List 구현 - 성긴동기화

논블로킹 자료구조 Linked List

뮤텍스를 사용한 자료구조부터해서 논블로킹 자료구조까지 여러 단계 변화를 하며 각각에 대해서 성능향상을 비교해본다.

 

목표자료구조 - Set

1. 아이템의 중복을 허용하지 않음
2. 검색의 효율성을 위해 아이템은 정렬되어 저장됨
3. 삽입 삭제의 효율성을 위해 링크드리스트로 구현된다.
4. 값을 저장하고 있는 노드 뿐만 아니라, 무한대값을 갖고있는 보조노드를 두어 검색할때마다 널체크를 하지 않아도 된다.

구현할 메서드

1. Add
2. Remove
3. Contains(집합에 x가 있다면 true 반환)

---

실습 - 성긴동기화

성긴동기화 - Lock 하나로 동기화 객체 전체를 감싸는 경우

리스트는 하나의 잠금을 갖고 있으며 모든 메서드호출은  이 잠금을 통해 Critical Section으로 진행된다.

• 모든 메서드는 잠금을 가지고 있는 동안에만 리스트에 접근한다.

class NODE {
public:
    int key;
    NODE* next;

    NODE()
    {
        next = nullptr;
    }
    NODE(int x)
    {
        key = x;
        next = nullptr;
    }
    ~NODE() {};
};

class CLIST {
    NODE head, tail;
    mutex m_lock;
public:
    CLIST()
    {
        head.key = 0x8000'0000;
        tail.key = 0x7FFF'FFFF;
        head.next = &tail; // head tail은 연결되어있어야한다.
    }
    ~CLIST() {};

    // head하고 tail사이에 있는 모든 노드를 초기화
    void Clear()
    {
        NODE* ptr = head.next; // head의 다음부터 지우기
        while (ptr != &tail) // tail을 만날때까지
        {
            NODE* to_delete = ptr;
            ptr = ptr->next;
            delete to_delete;
            to_delete = nullptr;
        }
        head.next = &tail;
    }

    bool Add(int x)
    {
        NODE* pred = &head;

        // mlock위치 - head의 주소는 절대 바뀌지 않음.
        m_lock.lock();
        NODE* curr = pred->next;

        // 정렬되어있으니까 key가 x보다 작으면 다음노드로 이동
        while (curr->key < x)
        {
            pred = curr;
            curr = curr->next;
        }

        // 중복값 체크
        if (curr->key == x)
        {
            // return하기전에 unlock
            m_lock.unlock();
            return false;
        }
        else
        {
            NODE* new_node = new NODE(x);
            new_node->next = curr;
            pred->next = new_node;

            // return하기전에 unlock
            m_lock.unlock();
            return true;
        }
    }

    bool Remove(int x)
    {
        NODE* pred = &head;
        m_lock.lock();
        NODE* curr = pred->next;

        while (curr->key < x)
        {
            pred = curr;
            curr = curr->next;
        }

        if (curr->key != x)
        {
            m_lock.unlock();
            return false;
        }
        else
        {
            pred->next = curr->next;
            delete curr;
            curr = nullptr;
            m_lock.unlock();
            return true;
        }

    }

    bool Contains(int x)
    {
        NODE* pred = &head;

        m_lock.lock();
        NODE* curr = pred->next;
        while (curr->key < x)
        {
            pred = curr;
            curr = curr->next;
        }

        if (curr->key != x)
        {
            m_lock.unlock();
            return false;
        }
        else
        {
            m_lock.unlock();
            return true;
        }
    }
};

 

실행결과

const auto NUM_TEST = 40'0000;
const auto KEY_RANGE = 1000;

 

문제점

블로킹 자료구조다.

쓰레드간의 경쟁이 적을 경우 이 동기화가 좋은 선택이지만 경쟁이 많을경우 성능이 저하된다.

 

다음 포스팅

성긴동기화는 성능상 많은 결함이 있다. 이를 보안한 세밀한 동기화를 구현해보자.

---

출처

한국산업기술대학교 게임공학부 정내훈 교수님 강의 - 멀티코어 프로그래밍