C++ MultiThread) std::atomic과 SpinLock

오늘은 좀 어려운 주제에 대해 논하고자 한다.
C++에서 멀티스레드를 구현할 때 C++ 11에서 추가된 std::thread를 사용할 수 있다.
thread의 생성자에 void 함수와 함수의 인자를 넣어 멀티스레드 환경에서 프로그램을 동작시킬 수 있다.
 
하지만 스레드 간에는 명령 순서가 보장되지 않아 예상과는 다른 결과가 나올 수 있다.
 

#include <iostream>
#include <thread>
#include <vector>

void increment(int &count) {
    for (int i = 0; i < 100'000; i++) {
        count++;
    }
}

int main() {
    int count = 0;
    std::vector<std::thread> v;

    for (int i = 0; i < 10; i++) {
        v.push_back(std::thread(increment, std::ref(count)));
    }

    for (auto &t : v) {
        t.join();
    }

    std::cout << count << std::endl;
}

 

출력: 193924

예상대로면 한 개의 스레드당 100,000번씩 count를 증가시켜서 총 1,000,000이 되어야 하지만 스레드 함수인 increment 내에서 이루어지는 동작에서 다른 스레드의 개입이 존재하기 때문에 결과가 달라진다.
 
예를 들면,
스레드 2에서 count를 증가시키기 전에 3444로 읽었을 때
스레드 1에서 count를 증가시켜 3445가 되었지만
스레드 2에서는 이미 3444로 읽었기 때문에 1을 증가시켜 3445가 될 수 있다.
 
이 경우 count를 2번 증가시켰음에도 최종적으로 값이 1만 증가한 상태가 된다.
 
 
그렇다면 count++ 연산은 어떻게 처리되는 것인가?

     7:         count++;
 mov         eax,dword ptr [count]  
 mov         ecx,dword ptr [eax]  
 add         ecx,1  
 mov         edx,dword ptr [count]  
 mov         dword ptr [edx],ecx

 
어셈블리 코드를 보면 count에 있는 값을 1 증가시키기 위해
CPU는 총 5번의 명령을 수행한다.

count 변수의 주소를 eax 레지스터에 저장하고,
eax 레지스터에 있는 주소가 가리키는 값을 ecx 레지스터에 저장하고,
ecx 레지스터의 값을 1 증가시키고,
count 변수의 주소를 edx 레지스터에 저장한 다음,
ecx 레지스터의 값을 edx 레지스터에 있는 주소가 가리키는 값(count)에 저장한다.

 
즉, 이 5번의 명령 사이에 다른 스레드의 명령이 존재한다면 결과가 달라지는 것이다.
 
그렇다면 다른 스레드의 개입을 막거나, 5개의 명령을 하나로 묶을 수 있다면 정상 처리될 것이라고 짐작할 수 있다.
 
 

std::atomic

std::atomic은 C++11에서 등장한 키워드로 위에서 얘기한 여러 명령들을 하나로 묶는데 쓰인다.
atomic 이란 그 자체로 원자 단위라는 뜻이 되며 위 명령들을 더이상 쪼갤 수 없는 '원자'처럼 만들겠다라고 생각하면 된다.
 
std::atomic을 사용한 코드를 보자.

#include <iostream>
#include <thread>
#include <vector>

void increment(std::atomic<int> &count) {
    for (int i = 0; i < 100'000; i++) {
        count++;
    }
}

int main() {
    std::atomic<int> count = 0;
    std::vector<std::thread> v;

    for (int i = 0; i < 10; i++) {
        v.push_back(std::thread(increment, std::ref(count)));
    }

    for (auto &t : v) {
        t.join();
    }

    std::cout << count << std::endl;
}

출력: 1000000

위에서 본 것처럼 count 변수를 std::atomic<int>로 감싸고 있다.
이렇게 하면 count++ 처럼 증분 연산을 할 때 위에서 얘기한 5개의 명령을 하나의 명령처럼 처리할 수 있게 되어 다른 스레드의 개입을 막을 수 있다.
 

     7:         count++;
 push        0  
 mov         ecx,dword ptr [count]  
 call        std::basic_ostream<char,std::char_traits<char> >::_Sentry_base::_Sentry_base (0F21988h)

어셈블리어에서 보면 count의 주소를 ecx 레지스터에 저장하고 count의 값을 증가시키는 함수를 call 명령으로 부르는 것으로 짐작된다.
아마 하드웨어상에서 count++ 연산을 내부적으로 원자적으로 처리하는 것으로 보인다.
 

Lock-Free Programming

atomic의 경우 Lock-Free Programming이라고 하는 효율적인 멀티스레드 구현을 위해 자주 사용되는 키워드이다.

Lock-Free란 mutex.lock 처럼 임계 영역으로의 동시접근을 막기 위해 사용되는 기법을 사용하지 않고 메모리 순서를 지정하여 스레드의 일관된 실행 순서를 보장할 수 있는 프로그래밍이라고 볼 수 있지만, 구체적으로는 더 넓은 범위에 해당한다.

위 그림의 플로우를 그대로 따라가보자.

Lock-Free Programming이 되기 위한 조건
1. 멀티스레드로 동작하는 프로그래밍을 하고 있는가? -> Yes
2. 스레드들이 서로 공유하는 메모리에 접근이 가능한가? -> Yes
3. 하나의 스레드에 의해 다른 스레드가 blocked(대기 상태로 전환, sleep)될 수 있는가? -> No

이 때, 단 한번이라도 조건을 만족하지 못하고 벗어나면 그것은 Lock-Free Programming이라 할 수 없다.

 

이에 대해 아주 잘 설명해놓은 사이트가 있다.

https://preshing.com/20120612/an-introduction-to-lock-free-programming/

An Introduction to Lock-Free Programming

 
위에서 소개하지 않는 방법으로 명령을 묶는 대신 상호 배제(Mutually Exclusive: Mutex) 원칙으로 다른 스레드의 개입을 막는 방법이 있다.
이는 std::mutex로 구현이 가능하다.
 
 

std::mutex

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

void increment(int &count, std::mutex &m) {
    std::lock_guard<std::mutex> lock(m);
    for (int i = 0; i < 100'000; i++) {
        count++;
    }
}

int main() {
    std::mutex mtx;
    int count = 0;
    std::vector<std::thread> v;

    for (int i = 0; i < 10; i++) {
        v.push_back(std::thread(increment, std::ref(count), std::ref(mtx)));
    }

    for (auto &t : v) {
        t.join();
    }

    std::cout << count << std::endl;
}

출력: 1000000

 
위 코드에서는 분명 count가 atomic 선언되지 않았음에도 정상적으로 출력된다.
그 이유는 mutex를 선언하여 한 스레드가 함수 스코프 내에서 실행되는 동안 다른 스레드의 개입이 없도록 하고 있기 때문이다.
 
lock_guard<mutex> 는 mutex::lock과 mutex::unlock 과정을 한 문장으로 줄여준다. 이는 스마트포인터처럼 작동하며 스코프를 벗어나면 자동으로 mutex를 unlock해준다.
 
하지만 std::mutex로 구현한 상호 배제의 경우 스레드 간 문맥 교환(Context Switching)이 더 많이 일어날 수 있다. (참고로 mutex::lock 기능을 사용하는 경우 바쁜 대기시키는 전통적인 mutex와 다르다. 일반적으로 알고 있는 mutex는 밑에서 설명할 SpinLock에 해당한다.)
쉬운 이해를 위해 코어당 1개의 스레드를 가지고 있고 2개의 코어로 동작하는 CPU가 있다고 하자.
 
1번 코어에서 mutex로 보호되는 자원을 가지고 작업을 하고 있으면 2번 코어에서는 이 자원을 할당받을 수 없으므로 block 상태가 되고 다른 스레드에게 코어를 할당하여 계속 작업을 이어나간다. 이 경우 문맥 교환이 발생한다.
만약 스레드 함수에서 매우 간단한 작업만 한다면 std::mutex로 상호 배제를 구현했을 때 문맥 교환의 비용이 단순히 스레드가 자원 할당을 기다리는 것보다 더 클 것이다.
 
따라서 매우 간단한 작업에 대해서는 스레드를 바쁜 대기(Busy Waiting) 상태로 만들어 문맥 교환이 일어나는 대신, 현재 스레드의 작업이 끝날때 까지 기다리게 한 다음 바톤을 이어받게 하는 것이 더 효율적이다.
 
이 경우 1번 코어에서 mutex로 보호되는 자원을 가지고 작업을 하는 동안 2번 코어에서는 이 자원을 할당받을 수 없으므로 block이 되는 대신 어떤 루프 안에서 계속 자원 할당을 기다린다. 2번 코어는 루프 안에서 대기하고 있기 때문에 다른 스레드에 코어를 할당하지 않으며 따라서 문맥 교환이 발생하지 않는다.
 
 

SpinLock

SpinLock 이란 어떤 스레드가 mutex로 보호된 자원을 가지고 작업하고 있는 동안 다른 스레드로 가서 작업하지 않고 대신 그 자원을 얻으려는 스레드를 대기시키는 것을 말한다. Spin은 이러지도 저러지도 못하고 빙빙 도는 상태를 의미한다.
SpinLock 클래스를 만들어 mutex를 구현하면 다음과 같다.

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

class SpinLock {
public:
    void lock() {
        while (locked) {

        }

        locked = true;
    }

    void unlock() {
        locked = false;
    }

private:
    volatile bool locked = false;
};

void increment(int &count, SpinLock& s) {
    std::lock_guard<SpinLock> slock(s);
    for (int i = 0; i < 100'000; i++) {
        count++;
    }
}

int main() {
    SpinLock slock;
    int count = 0;
    std::vector<std::thread> v;

    for (int i = 0; i < 10; i++) {
        v.push_back(std::thread(increment, std::ref(count), std::ref(slock)));
    }

    for (auto &t : v) {
        t.join();
    }

    std::cout << count << std::endl;
}

출력: 234658

SpinLock 클래스는 lock()과 unlock() 함수를 가지고 있어서 std::lock_guard 로 RAII 패턴을 구현할 수 있다.
하지만 위 코드에는 문제가 있다.
 
바로 상호 배제를 완벽히 수행하지 못하고 있는 것인데, 코드를 살펴보면,
 
스레드들이 공통으로 참조하는 SpinLock 객체의 locked 변수가 true인 동안 다른 스레드들은 자원을 할당 받을 수 없도록 구현하는 것이 목적이다.
 
하지만 예를 들어,
 
A 스레드에서 함수를 마쳐서 locked가 false가 된 순간 B 스레드에서 루프를 그만 돌고 locked = true로 만든 다음 자기가 자원을 할당 받아 동작을 할 수 있게 되지만,
B 스레드가 루프를 벗어나서 locked = true로 만들기 전에 C 스레드가 locked가 false인 것을 확인하고 루프를 벗어날 수도 있다. 이 경우 B 스레드와 C 스레드가 임계 영역(Critical Section)에 동시에 존재하여 하나의 자원을 동시에 할당 받는 상태가 된다.
이렇게 되면 상호 배제가 지켜지지 않게 되면서 잘못된 결과가 나타난다.
 
여기서 우리는 문제의 원인이 while 루프를 벗어난 후에 locked = true로 설정하기 전에 다른 스레드의 개입이 존재할 수 있다는 것임을 알았다.
std::atomic을 통해 위 과정을 원자화할 수 있을까?
 
CAS(Compare And Swap) 이라고 하는 연산이 있다. 이 연산은 말 그대로 비교를 한 다음 교체를 하는데 이 연산을 Atomic 하게 수행하기 때문에 중간에 다른 스레드의 개입이 없게 된다.
 

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

class SpinLock {
public:
    void lock() {
        bool expected = false;
        bool desired = true;
        while (locked.compare_exchange_strong(expected, desired, std::memory_order::memory_order_relaxed) == false) {
            expected = false;
        }
    }

    void unlock() {
        locked.store(false);
    }

private:
    std::atomic<bool> locked = false;
};

void increment(int &count, SpinLock& s) {
    std::lock_guard<SpinLock> slock(s);
    for (int i = 0; i < 100'000; i++) {
        count++;
    }
}

int main() {
    SpinLock slock;
    int count = 0;
    std::vector<std::thread> v;

    for (int i = 0; i < 10; i++) {
        v.push_back(std::thread(increment, std::ref(count), std::ref(slock)));
    }

    for (auto &t : v) {
        t.join();
    }

    std::cout << count << std::endl;
}

출력: 1000000

 
CAS 연산을 하는 함수가 바로 compare_exchange_strong(_TVal& _Expected, const _TVal _Desired, ...) 이다.
 
_Expected는 기대되는 값이고 _Desired는 원하는 값이라고 직역되는데 이는 매우 헷갈린다.
여기서 보면 _Expected 변수를 참조 형태로, _Desired 변수를 값 형태로 가져오는걸 알 수 있는데, 이는 마치 _Expected의 값은 변경 가능성이 있고 _Desired는 변경 가능성이 없지만 다른 값을 이 값으로 바꿀 것처럼 보인다.
 
 
compare_exchange_strong 함수의 연산 과정을 살펴보자.
 

1. 자신의 값(this*)과 _Expected를 비교한다.
2. 두 값이 같은 경우, 자신의 값을 _Desired 로 바꾸고 true를 리턴한다.
3. 두 값이 다른 경우, _Expected의 값을 자신의 값으로 바꾸고 false를 리턴한다.

 
매우 복잡해 보이지만 위의 while 문에서 보면 왜 이렇게 연산이 되어야 하는 지 알 수 있다.

---

①먼저 locked와 expected 값을 비교한다.
만약 locked가 true라면(어떤 스레드가 자원을 사용 중이라면)
locked와 expected의 값은 서로 다르기 때문에
expected의 값을 locked의 값인 true로 바꾸고 false를 반환하며
while문의 조건을 만족하여 루프를 돌게 된다.
 
②하지만 locked가 false라면
locked와 expected 값이 서로 같기 때문에
locked의 값을 desired의 값인 true로 바꾸면서 true를 반환하고
while문의 조건을 만족하지 않아 루프를 벗어난다.

---

① 상황에서는 expected 값이 true가 되어버리는데
그러면 다음 루프에서 locked가 true(자원 사용 중)인 상태에서도 루프를 벗어나버리기 때문에
while문 안에서 expected를 다시 false로 만들어 주어야 한다.
 
여기서 헷갈리면 안되는 부분이 있는데
expected와 locked는 스레드들이 공유하는 변수가 아닌 하나의 스레드가 함수 내에서 사용하는 변수라는 것인데
while 루프를 반복하는 과정에서 문제가 없도록 하기 위해 존재하는 지역 변수이기 때문에
Atomic 하게 동작할 필요가 없다는 것이다. (물론 Atomic 하게 만들어 줄 수도 있다.)

 

번외) compare_exchange_strong와 compare_exchange_weak의 차이

compare_exchange_weak의 경우 spurious failure(거짓 오류)가 발생할 수 있다. 여기서 말하는 spurious failure 이란 this* 값이 expected 값과 같은데도 불구하고 CAS가 false를 반환할 수 있는 경우이다.

이 오류는 LL/SC 명령 집합을 사용하는 CPU 아키텍처(새 ARMs 같은)에서 발생할 수 있다.

 

따라서 약간의 오버헤드가 있지만 이런 failure가 발생하지 않도록 해주는 compare_exchange_strong을 쓰는 것이 권장되며, 오히려 최적화를 원한다면 코드의 다른 부분에서 찾는 것이 훨씬 나은 편이다.

(오버헤드라고는 적었지만 구체적으로 compare_exchange_weak가 가지는 성능상의 이익은 거의 없다고 봐도 된다.)

 

Memory Order

SpinLock의 lock 함수에서 std::memory_order::memory_order_relaxed 코드가 들어가있는데 이를 간단하게 알아보자.
 
다중 스레드 환경에서 하나의 공통 변수에 대해 읽고 쓰는 동작이 일어나면 메모리에 배치된 명령 순서가 뒤죽박죽인 경우 결과가 달라질 수 있다는 것은 위에서 확인했다.
이러한 명령 순서는 컴파일러가 최적화를 위해 임의로 조작하는 것인데
memory_order_relaxed로 지정을 해주면 컴파일러가 명령 순서를 조작할 때 느슨하게 배치한다.
 
여기서 느슨하게 라는 말은 스레드간 실행 순서를 보장하지 않겠다는 의미인데
심지어 이것은 하나의 스코프에서 다른 줄에 배치된 코드 순서 조차도 보장하지 않는다.

r = y.load(std::memory_order_relaxed);
x.store(r, std::memory_order_relaxed);

위 코드에서 보면 r에 y의 값을 로드하고 x에 r 값을 저장한다.
하지만 컴파일러가 최적화 과정에서 순서를 디바꿔 x에 r 값을 저장한 다음 r에 y 값을 로드할 수도 있다는 얘기이다.
 
atomic의 store또는 load 연산에서 memory_order의 기본 값은 memory_order_seq_cst이다.
여기서 seq_cst란 Seqentially Consistant 이며 순차적으로 일관된 순서를 의미한다.
 
위에서는 컴파일러가 최적화를 위해 명령 순서를 바꿀 수도 있다고 했는데
seq_cst로 명령 순서를 순차적으로 정렬해버리도록 하면 당연히 그만큼 최적화가 덜 일어나기 때문에
순차적 실행을 보장하지 않아도 되는 곳에서는 relaxed로 해주는 것이다.
 
expected와 desired 변수의 경우 다른 스레드에서 값을 바꿀 일이 없기 때문에 순차적 실행을 보장하지 않아도 되고 위 코드는 결과적으로 어셈블리상에서 명령 수 차이가 없었기에 유의미한 최적화라고는 보기 힘들다.

 

 

다음 시간에는 Memory Order과 함께 Acquire-Release Semantics를 구현하는 방법을 알아보자. 이를 알기 위해서는 세마포어 동기화라는 개념이 필요한데, 세마포어 동기화를 구현하면서 같이 이해해보는 시간을 가져보자.
 
 

Reference

https://modoocode.com/271

씹어먹는 C++ - <15 - 3. C++ memory order 와 atomic 객체>

https://currygamedev.tistory.com/21

[Thread] 스핀락(SpinLock)

https://en.cppreference.com/w/cpp/atomic/memory_order

std::memory_order - cppreference.com