[c++] CAS 구현 및 ABA 문제 해결 :: mutex(spin lock)와의 비교

Mutex와의 비교

코드

#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;
        }
        cout << size << endl;
    }

    void push(Node* newNode) {
        Node* oldHead;

        mut.lock();
        oldHead = head;
        newNode->next = oldHead;
        head = newNode;
        mut.unlock();
    }
    Node* pop() {
        Node* oldHead; Node* newHead;

        mut.lock();
        if ((oldHead = head) == nullptr) {
            mut.unlock();
            return nullptr;
        }
        newHead = oldHead->next;
        head = newHead;
        mut.unlock();
        return oldHead;
    }
};

LFStack* FreeList;
LFStack* HeadList;

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

    int num = 10000; // 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 = 5; // 스레드 갯수
    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;
}

 

결과

• 실행조건

노드 갯수	thread	while문 수행횟수
100,000	5	10,000

• 결과

구분	FreeList 노드 수	HeadList 노드 수
1	40,000	60,000
2	100,000	0
3	96,091	3,909

lock 기법으로 상호배제를 해주었기 때문에, 결과는 정확하게 잘 나온다.

 

성능 비교

실행 조건

노드 갯수	while문 수행횟수	(n,m)
100,000개	10,000회	각 스레드에서 (10,10)

비교하기 위해 조건을 맞춰주었다.

구분	thread 갯수
1	10
2	100

결과 1

구분	memory 소비	CPU 사용시간(ms)
Counter (lock-free)	7.2MB	2755
Mutex (lock)	6.8MB	9259

<Counter>

<Mutex>

 

결과 2

구분	memory 소비	CPU 사용시간(ms)
Counter (lock-free)	7.1MB	29661
Mutex (lock)	12.5MB	98597

<Counter>

 

<Mutex>

 

해석

 Counter를 이용한 lock-free 기법과 Mutex를 이용한 lock 기법의 CPU 사용시간은 3배 가까이 차이가 났다. 이는 lock 기법 사용 시 Blocking 프로그램이 되므로 스레드들이 lock 병목현상을 일으키기 때문이라고 해석된다.

 또한 Counter를 이용한 기법은 스레드의 수가 증가해도 메모리 사용량이 비슷했는데, Mutex 기법은 스레드의 수가 증가함에 따라 메모리 사용량도 증가하였다. 이는 long long 정수형을 사용하는 Counter 기법의 경우 블록이 끝나면 해당 변수가 소멸되지만, Node* 객체 포인터형을 사용하는 Mutex 기법의 경우 GC가 없는 c++에서 메모리가 그대로 남아있기 때문이다.

 결론적으로 lock-free 기법은 ABA 문제를 해결할 수 있고, 구현 시 Overhead를 줄일 수 있다면 thread가 병렬로 많이 동작하는 상황에서 lock의 병목이 일어나는 lock 상호배제 기법을 대체하기 위한 좋은 방안이 될수있다.

 

참고 사이트

https://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution

http://www.cplusplus.com/reference/atomic/atomic/compare_exchange_weak/

https://felixblog.tistory.com/23

https://aerocode.net/117

https://stackoverflow.com/questions/20173766/why-does-stdatomictcompare-exchange-should-not-suffer-from-aba-issue

https://modoocode.com/270

https://www.sysnet.pe.kr/2/0/1458

https://ozt88.tistory.com/38

https://decdream.tistory.com/342

https://mountrivers.github.io/p014garbage/

https://m.blog.naver.com/jjoommnn/130129196122

https://stackoverflow.com/questions/42854116/why-does-automatic-garbage-collection-eliminate-aba-problems

https://en.wikipedia.org/wiki/ABA_problem

https://blog.naver.com/jjoommnn/130040068875?proxyReferer=https%3A%2F%2Fwww.google.com%2F

https://docs.microsoft.com/ko-kr/cpp/cpp/left-shift-and-right-shift-operators-input-and-output?view=vs-2019

https://dojang.io/mod/page/view.php?id=472

https://docs.microsoft.com/ko-kr/cpp/intrinsics/interlockedcompareexchange-intrinsic-functions?view=vs-2019

 

 

=> 끝