[c++] CAS 구현 및 ABA 문제 해결 :: ABA 해결_1. int형 구현

 

목차

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

 

ABA 해결

int형 구현

ABA 문제는 매개변수를 int형으로 구현하면 쉽게 해결할 수 있다. 하지만 문제점은 존재한다(뒷부분에 언급).

 

코드

#define _CRT_SECURE_NO_WARNINGS
#define NULL_INT -1 // NULL 값

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

using namespace std;

struct Node {
    int data;
    Node* next_node;
};

int node_n;
atomic<Node*> free_list;
atomic<Node*> head_list;

//출력을 위한 mutex
mutex mut;

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


void printNodes(int type) { // list 출력 함수
    Node* tmp;
    if (type == 0) {
        cout << "head_list ";
        tmp = head_list.load();
    }
    else {
        cout << "free_list ";
        tmp = free_list.load();
    }
    int num = 0;
    while (tmp != nullptr) {
        //cout << tmp->data << " ";
        tmp = tmp->next_node;
        num++;

        if (num > 100000) { // error 처리
            cout << "node is more than 100000" << endl;
            return;
        }
    }
    cout << endl;
    cout << num << endl;
}

void push(int data) {
    Node* tmp_node = new Node();
    tmp_node->data = data;
    Node* tmp;
    do {
        tmp = head_list.load();
        tmp_node->next_node = tmp;
    } while (!atomic_compare_exchange_weak(&head_list, &tmp, tmp_node));
}

void push_f(int data) {
    Node* tmp_node = new Node();
    tmp_node->data = data;
    Node* tmp;
    do {
        tmp = free_list.load();
        tmp_node->next_node = tmp;
    } while (!atomic_compare_exchange_weak(&free_list, &tmp, tmp_node));
}

int pop() {
    Node* tmp; Node* tmp_next;
    while (true) {
        if ((tmp = head_list.load()) == nullptr) {
            return NULL_INT;
        }
        // head_list에 data가 들어올 때까지 기다린다.

        if (tmp != head_list.load())
            continue;

        tmp_next = tmp->next_node;
        int data = tmp->data;

        if (atomic_compare_exchange_weak(&head_list, &tmp, tmp_next)) {
            return data;
        }
    }
}

int pop_f() {
    Node* tmp; Node* tmp_next;
    while (true) {
        if ((tmp = free_list.load()) == nullptr) {
            return NULL_INT;
        }
        // free_list에 data가 들어올 때까지 기다린다.

        if (tmp != free_list.load())
            continue;

        tmp_next = tmp->next_node;
        int data = tmp->data;

        if (atomic_compare_exchange_weak(&free_list, &tmp, tmp_next)) {
            return data;
        }
    }
}

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

    mut.lock();
    cout << n << " " << m << endl;
    mut.unlock();

    int num = 10000; // while문 반복 횟수
    while (num--) {
        for (int i = 0; i < n; i++)
        {
            // free_list에 있으면 head_list에 옮기는 작업
            int tmp = pop_f();
            if (tmp == NULL_INT)
                continue;
            push(tmp);
        }
        for (int i = 0; i<m; i++) {
            // head_list에 있으면 free_list에 옮기는 작업
            int tmp = pop();
            if (tmp == NULL_INT)
                continue;
            push_f(tmp);
        }
    }
}

int main() {
    // 노드 생성 및 free_list 삽입
    node_n = 100000; // 노드 갯수
    for (int i = node_n - 1; i >= 0; i--) {
        push_f(i);
    }


    // 스레드 생성 및 동작 시작 
    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();

    printNodes(0);
    printNodes(1);

    cin >> n;

}

 

결과

• 실행 조건

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

• 결과

구분	free_list 노드 수	head_list 노드 수	n-m의 합
정상1	62,775	37,225	3
정상2	100,000	0	0

이렇게 ABA 문제가 해결되는 것을 확인했다. 그렇다면 어떠한 원리로 ABA문제가 해결된걸까?

 

이유 분석

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

 

 그러면 다음과 같은 상태가 되는데, Node*형을 매개변수로 주고받을 때와는 다르게 push 함수 실행 시 기존에 0 노드가 아닌 새로운 0 노드를 만들어서 push하게 된다. 따라서 head와 tmp가 가리키는 메모리 주소가 다르므로 CAS 연산을 다시 수행하게 된다.

 

문제점

 이렇게 ABA문제가 해결되었지만, 메모리 문제가 남아있다. 위의 그림과 같이 tmp와 tmp_next가 가리키는 노드들의 메모리를 반납해주지 않으면 메모리 누수 현상이 발생한다. Garbage Collector 부분에서 언급해보자.

 

Garbage Collector

 Garbage Collector를 보유하고 있는 java의 경우 메모리 누수가 일어나지 않는다. GC는 어떤 메모리가 참조되지 않을 때까지 기다렸다가 메모리를 해제하기 때문이다.

 하지만 GC를 지원하지 않는 언어나 GC를 지원하더라도 lock-free GC가 아닌 경우에는 따로 구현을 해주어야한다. GC가 lock-free가 아니면 system 전체가 lock-free가 아니게 되기 때문이다.

 먼저 그냥 tmp를 delete 해보자. 이는 큰 문제가 발생할 수도 있지만 감안하고 실험해보겠다.

delete 첨부

<바뀐 코드만>

// pop, pop_f 함수

if (atomic_compare_exchange_weak(&head_list, &tmp, tmp_next)) {
    delete tmp; // 추가
    return data;
}

<결과>

 메모리를 해제해주었기 때문에 메모리 누수는 줄었지만 문제는 다른 thread가 tmp와 tmp_next를 참조하고 있었다면 delete 되어버려서 큰 문제가 발생할 수 있다. 이렇게 참조하던 노드 값이 쓰레기 값이 되어버리는 것이다.

결국 GC의 방식처럼 노드들은 다른 변수들이 참조하지 않을 때까지 삭제되지 않고 기다려야한다. 따라서 delete로 해결될 수 없다.

 

=> 새로운 해결법은 다음 포스팅에