[c++] CAS 구현 및 ABA 문제 해결 :: 문제 정의, 기본 CAS 구현

목차

1. 문제 정의
2. lock free 구현
3. ABA 해결
   1. int형 구현(+ Hazard pointer)
   2. Counter
   3. 그 외의 방법들
4. mutex lock(spin lock)과의 비교

 

문제 정의

문제

Linked List 자료구조에서 push()와 pop() 연산을 구현한다. Linked List는 FreeList와 HeadList 두가지가 있으며 여러 스레드가 두 개의 List를 번갈아가며 push, pop 연산을 수행한다. 스레드들이 각각 연산을 수행하기 위해서는 List들에 대한 상호배제가 필요하다.

해석

상호 배제에는 여러가지 방법이 있지만, 크게 두가지로 나눌 수 있다. lock 변수의 조건을 체크하며 반복문을 돌고 있는 spin lock과, lock 변수 없이 계속 시도하면서 적절한 때에 동작을 수행하는 lock free 기법이 그것이다. spin lock과 lock free 기법의 차이점은 이름에서 드러나듯이 lock 변수의 유무이다. lock을 이용한 임계구역 구현이 각 스레드가 하나씩 접근할 수 있게 만든거라면, lock free의 CAS 기법은 모든 스레드가 접근하려고 계속 애쓰다가 무작위적으로 타이밍에 맞는 스레드가 접근하는 것이다. lock free 기법을 활용하면 임계구역을 구현하지 않아도 되고, lock 변수 병목이 줄어드며 병렬화 정도를 향상시킬 수 있다.

lock free 기법에는 CAS가 대표적이고, 이를 구현하는 방법은 C++, C# 등 여러 가지 언어에서 지원하고 있다. 하지만 CAS 구현 시 ABA 문제라는 것이 일어날 수 있는데, 이는 프로그래머가 각자 해결해야하는 부분이다.

CAS 이용 시 동작과정은 어떻게 되며, ABA 문제가 일어났을 때 해결할 수 있는 방법은 무엇이 있는지 살펴보자. 또한 마지막 이러한 lock free 기법이 spin lock 과 비교해서 어떠한 차이가 있는지 비교해보자.

 

lock free (CAS) 구현

원리

우선 lock free 기법 중 CAS에 대해서 살펴보자.

Compare-and-Swap 연산은 대표적인 lock-free 기법이다. 변경하고자 하는 변수를 사용하여 변경하고자 하는 값을 계산한 다음, _(변수의 값이 변하지 않았다면, 변수의 값에 계산한 값 할당)_의 과정을 원자적으로 시행한다. 결국 하드웨어 상에서는 이 과정을 원자적으로 행하기 위해 lock signal을 뿌리는 식으로 구현된다.

먼저 이렇게 node A, B, C가 존재하고 A->B->C 순으로 이어져있는 LinkedList가 있다고 가정하자. 이 때, pop 연산을 수행하여 node A를 제거하려고 한다.

변경하고자 하는 변수인 head를 사용하여 변경하고자 하는 값 newHead를 계산한 다음, (head가 oldHead와 같가면, head에 newHead 할당)의 과정을 수행한다.

c++에서는 CAS 연산시 atomic_compare_exchange_weak라는 함수를 사용할 수 있다. 코드로 표현하자면 다음과 같다.

Node* CAS(){
    Node* oldHead; Node* newHead;
    do {
        if ((oldHead = head) == nullptr) {
            return nullptr;
        }
        newHead = oldHead->next;
    } while (!atomic_compare_exchange_weak(&head, &oldHead, newHead));
}

전체 코드를 살펴보자.

 

코드

여러 스레드로 동작하는 LinkedList의 CAS 연산을 구현해본 코드이다.

#include <iostream> 
#include <thread>
#include <vector> 
#include <atomic>
#include <random>
#include <mutex>

using namespace std;

class Node {
public:
    int value;
    Node* next;
    Node() : value(0) { next = NULL; }

    Node(int k_value) {
        next = NULL;
        value = k_value;
    }
};

int node_n;

//random 구현
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> dis(0, 10);

//출력을 위한 mutex
mutex mut;

class LFStack {
private:
    Node * head;

public:
    void printNodes() {
        int size = 0;
        while (head != nullptr) {
            size++;
            head = head->next;
            if (size > 100000) {
                cout << "size over 100,000"<< endl;
                return;
            }
        }
        cout << size << endl;
    }

    void push(Node* newNode) {
        Node* oldNode;
        do {
            oldNode = head;
            newNode->next = oldNode;
        } while (!atomic_compare_exchange_weak(&head, &oldNode, newNode));
    }

    Node* pop() {
        Node* oldNode; Node* newNode;
        do {
            if ((oldNode = head) == nullptr) {
                return nullptr;
            }
            // head_list에 data가 들어올 때까지 기다린다.
            newNode = oldNode->next;
        } while (!atomic_compare_exchange_weak(&head, &oldNode, newNode));

        oldNode->next = nullptr;
        return oldNode;
    }
};

LFStack* FreeList;
LFStack* HeadList;

void subThread() {
    // random n, m
    int n = dis(gen);
    int m = dis(gen);

    int num = 1000; // while문 반복 횟수
    while (num--) {
        for (int i = 0; i < n; i++)
        {
            // free_list에 있으면 head_list에 옮기는 작업
            Node* tmp = FreeList->pop();
            if (tmp == nullptr)
                continue;
            HeadList->push(tmp);

        }
        for (int i = 0; i < m; i++) {
            // head_list에 있으면 free_list에 옮기는 작업
            Node* tmp = HeadList->pop();
            if (tmp == nullptr)
                continue;
            FreeList->push(tmp);
        }
    }

}

int main() {
    // free, head list 생성
    FreeList = new LFStack();
    HeadList = new LFStack();

    // 노드 생성 및 free_list에 삽입
    node_n = 100000; // 노드 갯수
    for (int i = node_n - 1; i >= 0; i--) {
        Node* node = new Node(i);
        FreeList->push(node);
    }

    // 스레드 생성 및 동작 시작 
    vector<thread> threads;
    int n = 3; // 스레드 갯수
    for (int i = 0; i < n; i++) {
        threads.emplace_back(subThread);
    }
    for (auto &t : threads)
        t.join();
    threads.clear();

    FreeList->printNodes();
    HeadList->printNodes();
    cin >> n;
}

random 구현은 time seed을 이용하면 쓰레드가 만들어지는 시각이 거의 동일하기 때문에 스레드 별로 변수 값이 다르게 나오지 않아서 Pseudo-random인 disgen을 사용하였다.

 

결과

• 실행 조건

노드 갯수	thread	while문 수행횟수
100,000개	3개	1,000회

이후의 시행에서는 thread는 5개, while문 최소 10,000회로 시행하였지만 이 코드는 오류가 많이 발생하기 때문에 thread 수와 while문 수행횟수를 축소하여 시행하였다.

 

• 결과

구분	free_list 노드 수	head_list 노드 수
정상작동	97,000	3,000
노드 감소	0	1
노드 증가	100,000개 이상	100,000개 이상

<정상 작동 시 결과>

97000 / 3000

<노드 감소 시 결과>

0 / 1

<노드 증가 시 결과>

size over 100,000 / size over 100,000

 

결과 분석

head가 가리키는 연결리스트가 다음과 같이 구성되어있고, 코드에 따라 tmp가 head를 load하고 tmp_next는 tmp가 가리키는 노드의 next_node를 가리킨다고 하자. 위의 그림까지 코드는 진행되었고, 이 때 다른 thread가 접근하여 headlist에 대한 pop => pop => push(0) 연산을 수행하였다.

그러면 다음과 같은 상태가 되는데, CAS연산을 시행하면 head와 tmp가 같으므로 tmp_next를 head에 대입하게 된다.

head와 free가 같은 노드를 가리키므로 노드의 수가 2배되어 노드가 증폭되어 나타날 수도 있으며, tmp가 가리키고 있는 노드들이 더이상 참조되지 않으면 사라져버린 것이므로 노드가 없어질 수도 있다.

 

결국 ABA 문제 때문에 노드 감소, 증가 현상이 나타나는 것이다.

 

ABA 문제를 해결해보자!

 

=> ABA 문제해결은 다음 포스팅에