[c++] CAS ๊ตฌํ˜„ ๋ฐ ABA ๋ฌธ์ œ ํ•ด๊ฒฐ :: ABA ํ•ด๊ฒฐ_3. Counter ๊ตฌํ˜„

 

๋ชฉ์ฐจ

  1. ๋ฌธ์ œ ์ •์˜
  2. lock free ๊ตฌํ˜„
  3. ABA ํ•ด๊ฒฐ
    1. intํ˜• ๊ตฌํ˜„(+ Hazard pointer)
    2. Counter
    3. ๊ทธ ์™ธ์˜ ๋ฐฉ๋ฒ•๋“ค
  4. mutex lock(spin lock)๊ณผ์˜ ๋น„๊ต

Counter

#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:
    long long CountedPtr;

public:
    void printNodes() {
        int size = 0;
        Node* head = reinterpret_cast<Node*>(CountedPtr);
        while (head != nullptr) {
            size++;
            head = head->next;
        }
        cout << size << endl;
    }

    long long getCount(long long cp) {
        return ((unsigned long long)cp >> 52); // ์™ผ์ชฝ ๋น„ํŠธ 0์œผ๋กœ ์ฑ„์šฐ๊ธฐ
    }
    long long setCount(long long count) {
        return count << 52;
    }

    void push(Node* newNode) {
        long long oldCP, newCP;
        unsigned long long newCount;
        do {
            oldCP = this->CountedPtr;
            newCount = getCount(oldCP) + 1; // count 1 ์ฆ๊ฐ€
            newNode->next = reinterpret_cast<Node*>(oldCP); // list์˜ head ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๊ฒŒ ํ•˜๊ธฐ
            newCP = setCount(newCount) + reinterpret_cast<long long>(newNode); // ๋ฐ”๊พผ ์นด์šดํ„ฐ์™€ node ๊ฒฐํ•ฉ
        } while (!(_InterlockedCompareExchange64(&(this->CountedPtr),newCP,oldCP)==oldCP)); //CAS
    }
    Node* pop() {
        long long oldCP, newCP;
        do {
            oldCP = this->CountedPtr;
            Node* popNode = reinterpret_cast<Node*>(oldCP);  // ๋งจ ์•ž ๋…ธ๋“œ ๊ตฌํ•˜๊ธฐ
            if (popNode == nullptr)
                return nullptr;
            newCP = (long long)(setCount(getCount(oldCP))) + reinterpret_cast<long long>(popNode->next); // counter๋Š” ๊ทธ๋Œ€๋กœ, node๋Š” ๋‹ค์Œ ๋…ธ๋“œ
        } while (!(_InterlockedCompareExchange64(&(this->CountedPtr),newCP,oldCP)==oldCP)); // CAS
        return reinterpret_cast<Node*>(oldCP);
    }
};

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;
}

 ๋Œ€๋ถ€๋ถ„์˜ 64bit CPU์—์„œ ๊ฐ€์ƒ ์ฃผ์†Œ๋ฅผ 52bit ๋ฐ–์— ์‚ฌ์šฉํ•˜์ง€ ์•Š๋Š”๋‹ค๋Š” ์ ์„ ์ด์šฉํ•œ ๋ฐฉ๋ฒ•์ด๋‹ค.

 

 ๊ฐ List๋Š” long long ํ˜• CountedPtr์ด๋ผ๋Š” ์ž๋ฃŒํ˜• ํ•˜๋‚˜๋กœ ์ด๋ฃจ์–ด์ ธ์žˆ๋‹ค. long long์€ 8byte ์ž๋ฃŒํ˜•์ด๋ฏ€๋กœ 64bit์˜ ์ฃผ์†Œ๋ฅผ ๋ชจ๋‘ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค. CountedPtr์˜ ํ•˜์œ„ 52bit๋Š” ์ฃผ์†Œ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š”๋ฐ์— ์“ฐ๊ณ , ์ƒ์œ„ 12bit๋Š” Count๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ๋ฐ์— ์“ฐ๊ธฐ๋กœ ํ•˜์ž.

 

 List๊ฐ€ ๊ฐ€๋ฆฌํ‚ค๋Š” ์ฒซ๋ฒˆ์งธ ๋…ธ๋“œ์˜ ์ฃผ์†Œ์™€ List์— push๊ฐ€ ์‚ฌ์šฉ๋œ ํšŸ์ˆ˜(Count)๋ฅผ ๊ฐ๊ฐ ํ•˜์œ„ 52bit, ์ƒ์œ„ 12bit์— ํ• ๋‹นํ•˜์—ฌ CountedPtr์„ ๋งŒ๋“ ๋‹ค. ABA ๋ฌธ์ œ๋Š” push๊ฐ€ ๋ฐœ์ƒํ•ด์•ผ์ง€๋งŒ ์ผ์–ด๋‚  ๊ฐ€๋Šฅ์„ฑ์ด ์žˆ์œผ๋ฏ€๋กœ pushํ•จ์ˆ˜ ์‹œํ–‰ ์‹œ์—๋งŒ Count๋ฅผ ์ฆ๊ฐ€์‹œ์ผœ์ฃผ์—ˆ๋‹ค. push ํ•จ์ˆ˜๊ฐ€ ์‹คํ–‰๋  ๋•Œ๋งˆ๋‹ค Count๋Š” 1์”ฉ ์ฆ๊ฐ€ํ•˜๋ฏ€๋กœ _InterlockedCompareExchange64 ์—์„œ ๋น„๊ต ์‹œ Count๊ฐ€ ๋‹ฌ๋ผ์ง€๋ฉด ์—ฐ์‚ฐ์ด ์ˆ˜ํ–‰๋˜์ง€ ์•Š๋Š”๋‹ค. ๋”ฐ๋ผ์„œ ABA ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค.

 

 pop ํ•จ์ˆ˜์—์„œ List์˜ ์ฒซ๋ฒˆ์งธ ๋…ธ๋“œ๊ฐ€ ๊ฐ€๋ฆฌํ‚ค๋Š” ๋‹ค์Œ ๋…ธ๋“œ๋ฅผ ๋ฐ›์•„์˜ค๋ ค๋ฉด CountedPtr์ด๋ผ๋Š” ์ •์ˆ˜ํ˜•์—์„œ Node์˜ ์ฃผ์†Œ์ธ Node*๋ฅผ ์ถ”์ถœํ•  ํ•„์š”๊ฐ€ ์žˆ๋‹ค. ์ด ๋•Œ๋Š” reinterpret_cast<Node*>(๋Œ€์ƒ) ์ด๋ผ๋Š” ์บ์ŠคํŒ… ์—ฐ์‚ฐ์„ ์‚ฌ์šฉํ•˜์—ฌ Node๋ฅผ ๋ถˆ๋Ÿฌ์˜จ๋‹ค.

 

 ๋˜ํ•œ Count๋„ 1 ๋Š˜๋ฆฌ๊ธฐ ์œ„ํ•ด ์ถ”์ถœํ•˜๋Š” ๊ณผ์ •์ด ํ•„์š”ํ•œ๋ฐ, Count๋Š” getCount์™€ setCount ํ•จ์ˆ˜๋ฅผ ๋”ฐ๋กœ ๊ตฌํ˜„ํ•˜์—ฌ ๋‹ค๋ฃจ์—ˆ๋‹ค. Count ์ถ”์ถœ ์‹œ ์œ ์˜ํ•  ์ ์€ CPU๋งˆ๋‹ค right shift ์—ฐ์‚ฐ ์‹œ 0๊ณผ 1 ์ค‘์— ์–ด๋–ค ๊ฐ’์ด ์ฑ„์›Œ์ง€๋Š” ์ง€๊ฐ€ ๋‹ค๋ฅด๋‹ค๋Š” ๊ฒƒ์ด๋‹ค. ๋”ฐ๋ผ์„œ unsigned ์ž๋ฃŒํ˜•์„ ์ด์šฉํ•˜์—ฌ ์Œ์ˆ˜๊ฐ€ ๋˜์ง€ ์•Š๋„๋ก(0์œผ๋กœ ์ฑ„์›Œ์ง€๋„๋ก) ๋งŒ๋“ค์–ด์ฃผ์–ด์•ผํ•œ๋‹ค. ์•„๋‹ˆ๋ฉด 0์œผ๋กœ ์ฑ„์›Œ์ฃผ๋Š” >>> ์—ฐ์‚ฐ์„ ์‚ฌ์šฉํ•ด๋„ ๋˜๋Š”๋ฐ c++์—๋Š” ํ•ด๋‹น ์—ฐ์‚ฐ์ด ์กด์žฌํ•˜์ง€ ์•Š๋Š”๋‹ค.

 

=> ABA๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ๊ธฐํƒ€ ๋ฐฉ๋ฒ•๋“ค์€ ๋‹ค์Œ ํฌ์ŠคํŒ…์—

๋ฐ˜์‘ํ˜•