Intro

c++의 atomic library는 병렬환경에서 저수준의 원자적인 연산을 일관적으로 지원하기 위해 만들어진 인터페이스이다.
여기세어 원자적인 연산이란 무엇인가? 나누어지지 않는.. 중간 단계가 외부로 노출되지 않는.. 그런 의미이다.

여기서 원자적인 연산이란 보통은 매우 저수준의 작업들을 말하는데,
더하기(+), 빼기(-), 비교(==) 따위와 같은 매우 기본적인 연산들이다.

혹자는 이런 작업들이 그 자체로 이미 atomic operation이라고 생각할 수도 있지만, 그렇지는 않다.
예를 들어 다음과 같이 변수 a에 1을 더하는 작업을 수행한다고 쳐보자.

int a = 0;
a += 1;
// a == 1

이 때 내부적으로 컴파일을 통해 어떤 기계언어가 생성되고 CPU가 처리하는지 생각해봐야 한다.

CPU 내부에는 레지스터(register)라고 하는 volatile storage가 존재한다. 메모리는 CPU와 독립된 하나의 HW인 반면,
레지스터는 CPU 안에 하나의 패키지로서 존재하며 CPU가 실질적으로 어떤 작업을 하기 위한 가장 심연?의 기억장치라고 생각해야 한다.

우리가 보통 PC(Program Counter)라고 부르는 정보도 레지스터에 저장되며, 보통 여러 개의 레지스터가 각각의 역할이 존재하여 현재 CPU가 실행 중인 상태를 기억한다.

따라서 우리가 Context Switching이라고 부르는 작업(현재 프로세스의 작업 상태를 저장하고, 다음 프로세스의 작업 상태로 전환되는 작업)은 보통 현재 프로세스의 레지스터 상태를 메모리에 저장하고, 다음 프로세스의 레지스터 상태를 CPU로 불러오는 작업이 포함된다.

int a = 0;
a += 1; // 어떻게 CPU에서 처리될까?
// a == 1

만약 위 코드가 주어지면 어떤 식으로 컴파일되어 CPU에서 실행될까?

1. a가 저장된 메모리의 주소(스택)로부터 a의 값을 레지스터로 불러오고(load),
2. CPU의 HW 차원에서 설계된 덧셈기를 통해 1을 더한 뒤(add),
3. 다시 이를 메모리 주소로 출력(fetch)한다.

따라서 a += 1이란 작업에는 총 3단계의 작업 load -> add -> fetch 작업이 수행되는 것이다.

당연히 이는 레지스터-메모리 두 기억장치가 사용되기 때문이고, 이제 만약 멀티스레드 환경을 생각해보면 무언가 문제가 생기리라 짐작할 수 있다.

Atomic Operation

먼저 어떤 상황이 문제가 되는지는 간단히 상상할 수 있다. 병렬 CPU 컴퓨터에서 두개의 스레드 T1과 T2가 하나의 공유변수를 다루고 있다고 생각해보는 것이다.

T1: load a // a값을 T1을 실행 중인 CPU레지스터로 불러온다.
T2: load a // a값을 T2을 실행 중인 CPU레지스터로 불러온다.
T1: add a, 1 // a += 1
T2: add a, 1 // a += 1
T1: fetch a // a == 1
T2: fetch a // a == 1

즉, 두 개의 스레드가 각각 a에 대해서 1을 한 번씩 더했는데, 결과는 1이 된 것이다.
이러한 문제는 결국 멀티코어 환경에서 각 코어마다 각자의 캐시(레지스터)를 지니고 있기 때문이다.

c++는 멀티스레드 환경에서 이러한 작업들을 안전하게 제어할 수 있도록 mutex, conditional_variable 등의 기능을 제공하지만, 이들은 좀 더 복잡하고 추상적인 작업을 제어하기 위한 기능이다.

std::atomic은 매우 단순한 데이터(int, uint, long, bool)들에 대한 작업을 lock이 없이도 atomic하게 제어하는 인터페이스이다.

std::atomic<int> a = {};
// initialize

a++;//a == 1
--a;//a == 0

a.fetch_add(5); // a == 5; a++ 등의 전위증가, 전위감소, 후위증가, 후위감소는 overloading을 통해 구현되어있지만, a += 5 등은 지원되지 않는다.
a.fetch_sub(7); // a == -2;

atomic 객체는 몇 개의 기능을 추상화하여 제공하는데, 크게 보면 3가지 종류이다.

1. load : 말 그대로 객체의 값을 메모리로부터 불러오고
2. store : 변수의 값을 메모리로 저장하고
3. read-modify-write: 변수를 읽어서 수정하고 변경...

read-modify-write의 경우 다음과 같이

fetch_add, fetch_sub, fetch_and, fetch_or, fetch_xor, compare_exchange_weak, compare_exchange_strong 등이 있다.

compare_exchange란 말 그대로 비교해서 바꾸는 작업(3항 연산처럼)을 atomic하게 수행하겠다는 말인데, weak와 strong의 경우 임베디드 시스템이 아니라면 큰 신경쓰지 않아도 될 것 같다.

기능 자체는 간단하니 cppreference를 참고하길 바란다.

Reordering

atomic operation을 통해 우리는 flag나 int 형태의 데이터를 안전하게 변경하고 읽을 수 있게 됐다.

그럼 이제 끝인가? 그렇지 않다..

atomic 객체는 보통 그 자체로도 의미있는 데이터를 담을 수 있지만, atomic 객체를 통해 lock-free한 형태의 로직을 작성하기 위해서 많이 사용된다. 즉, atomic 객체에 대한 읽기와 쓰기 작업이 보통 다른 작업과 함께 동반된다는 것.

예컨데 다음과 같은..

// Main Thread
std::atomic_flag flag;

// Sub Thread
void do_something() {
    int x, y, z ...;
    something1();
    // flag가 set일 경우 return false. 만약 unset일 경우 set하고 return true
    if(flag.test_and_set()) {

        // 예컨데 something2()를 하는 동안 다른 스레드에 의한 something2 재실행을 막을 수 있다.
        something2();
        // flag unset.
        flag.clear();
    }
    ...
}

여기까진 OK. 위 코드를 보면 atomic 객체에 대한 작업(test_and_set, claer 등)은 모두 atomic함이 보장되기 때문에 다른 스레드에 끼어들거나 간섭받을 여지가 없이 안전하다.

그러면 무엇이 문제인가? 컴파일러가 명령어를 재배치(Reordering)하는 것이 문제이다.
다음의 상황을 살펴보자.

std::atomic<int> a{};
std::atomic<int> b{};

// Thread 1
a.store(1); // a == 1
int x = b.load(); // x == b

// Thread 2
b.store(1); // b == 1
int y = a.load(); // y == a

과연 이 코드의 실행 결과 (x, y)는 어떻게 될까? 정답은 "모른다"이다.
x가 1이라고 가정하면, b.store(1)이 실행됐다는 의미이고 이 때 x의 초기화 전에 a.store(1)이 실행되니까....

이런 가정을 확실히 얘기할 수 없다는 것이다.

위 코드가 컴파일하고 나면(대충 그렇다고 생각하자.)

std::atomic<int> a{};
std::atomic<int> b{};

// Thread 1
int x = b.load(); // x == b
a.store(1); // a == 1


// Thread 2
int y = a.load(); // y == a
b.store(1); // b == 1

뭐 이렇게 바뀔 수도 있는 것이고.. 우리가 컴파일러의 규칙이나 테크닉을 완전히 알 수 있는 것도 아니니..

보통 이런 경우를 위해 memory barrier(혹은 fence)라고 하는 개념이 있다.

컴파일러에게 특정 연산의 순서를 마음대로 바꾸지 못하도록 울타리를 치는 것이다.

c++는 심지어 이런 기능도 표준으로 제공한다..

std::atomic<int> a{};
std::atomic<int> b{};

// Thread 1
a.store(1); // a == 1
std::atomic_thread_fence();
// 컴파일 이후에도 두 연산의 순서는 절대 fence를 뛰어넘지 못한다.
int x = b.load(); // x == b

// Thread 2
b.store(1); // b == 1
std::atomic_thread_fence();
// 컴파일 이후에도 두 연산의 순서는 절대 fence를 뛰어넘지 못한다.
int y = a.load(); // y == a

이제는 좀 더 실행결과를 예측할 수 있다.

(x, y) == (1, 0) or (0, 1) or (1, 1)

뭐 이런게 무슨 의미가 있나?라고 생각할 수도 있다. 그러나 다음과 같이 producer-consumer 패턴에서 spin lock을 이용하는 경우를 생각해보자.

// Main Thread
std::shared_ptr<int> data = make_shared<int>();
...

// Producer thread
void producer(std::shared_ptr<std::atomic<bool>> flag, std::shared_ptr<int> data) {
    *data = 10;
    flag->store(true);
}

// Consumer thread
void consumer(std::shared_ptr<std::atomic_flag> flag, std::shared_ptr<int> data) {
    while(!flag.load());
    std::cout << "Data : " << *data << std::endl;
}

자 이제 만약 임의로 컴파일러가 명령어를 재배치할 수 있다고 가정해보자.
그러면 consumer thread를 실행한 결과는 0일 수도 10일 수도 있다. 이유는 재배치때문이다.

대신에 여기서 fence를 설치하면

// Main Thread
std::shared_ptr<int> data = make_shared<int>();
...

// Producer thread
void producer(std::shared_ptr<std::atomic<bool>> flag, std::shared_ptr<int> data) {
    *data = 10;
    std::atomic_thread_fence();
    flag->store(true);
}

// Consumer thread
void consumer(std::shared_ptr<std::atomic_flag> flag, std::shared_ptr<int> data) {
    while(!flag.load());
    std::atomic_thread_fence();
    std::cout << "Data : " << *data << std::endl;
}

안전하게 consumer thread의 출력값이 10임을 보장할 수 있게 되는 것이다..

물론 지금까지 한 얘기는 fence의 개념과 std::memory_order를 소개하기 위한 작은 거짓말들이었다. 사실은 위 코드에 fence는 필요 없다...

Memory Ordering

std::memory_order는 위에서 얘기한 명령어 재배치을 효율적으로 제어하기 위한 인터페이스이다. std::atomic과 함께 사용하며, 크게 압축하면 4가지(+1가지)로 얘기할 수 있다.

1. releaxed: 재배치에 관련해서 아무런 관여도 하지 않겠다!
2. acquire: 이후에 등장할 명령어가 이전으로 재배치되지 못하도록 막자!
3. release: 이전에 등장한 명령어가 이후로 재배치되지 못하도록 막자!
4. acquire + release(=full fence): 이 지점을 기준으로 앞뒤로 명령어 재배치를 막자!

실은 이것이 전부이다.

좀 더 살펴볼까?
똑같이 위 예제를 살펴보자.

Relaxed Ordering

// Main Thread
std::shared_ptr<int> data = make_shared<int>();
...

// Producer thread
void producer(std::shared_ptr<std::atomic<bool>> flag, std::shared_ptr<int> data) {
    *data = 10;
    std::atomic_thread_fence();
    flag->store(true);
}

// Consumer thread
void consumer(std::shared_ptr<std::atomic_flag> flag, std::shared_ptr<int> data) {
    while(!flag.load());
    std::atomic_thread_fence();
    std::cout << "Data : " << *data << std::endl;
}

std::memory_order_relaxed는 앞서 얘기했듯 현재 실행할 atomic operation의 앞뒤 명령어에 대해 컴파일러가 자유롭게 재배치를 할 수 있도록 허용한다.

따라서 정말 atomic operation 이외에는 아무것도 기대할 수 없다.
어떤 경우에 쓸 수 있을까? atomic 객체에 관한 작업이 순서에 무관하면 사용해도 괜찮을 것이다.

// thread
void count(std::shared_ptr<std::atomic<int>> c) {
    for(int i = 0; i < 1000; i++) {
        c->fetch_add(1, std::memory_order_relaxed);
        // c = c + 1;을 atomic하게 수행
        // 순서와 관련이 없음을 알 수 있다.
    }
}

대신 다른 작업(spin lock처럼)과 관련되어있다면 당연히 아무런 동기화를 기대할 수 없을 것이다.

그래서 이용하는 것이 acquire-release 패턴

Acquire, Release Ordering

std::memory_order_acquire는 현재 작업 이후 명령어가 이전으로 재배치되지 못하도록 방지하고, std::memory_order_release는 반대로 barrier를 설치한다.
std::memory_order_acq_rel은 당연히 둘 다 수행한다는 개념.

마치 mutex의 lock과 unlock처럼 생각할 수 있다.
그러면 언제 사용하는가?

읽기 작업은 acquire, 쓰기 작업은 release, 읽고 쓰는 작업 둘다 하면 acq_rel이다.

// Main Thread
std::shared_ptr<int> data = make_shared<int>();
...

// Producer thread
void producer(std::shared_ptr<std::atomic<bool>> flag, std::shared_ptr<int> data) {
    *data = 10;
    flag->store(true, std::memory_order_release);
    // 반드시 *data = 10; 이후에 실행됨이 보장.
}

// Consumer thread
void consumer(std::shared_ptr<std::atomic_flag> flag, std::shared_ptr<int> data) {
    // 반드시 아래 cout 출력문 이전에 실행됨이 보장.
    while(!flag.load(std::memory_order_acquire));
    std::cout << "Data : " << *data << std::endl;
}

위 코드의 결과는 반드시 10이 나온다.
만약 다음과 같이 while 문에서 true를 얻었다고 하자.

while(!flag.load(std::memory_order_acquire));

그렇다는 것은 당연히! memory_order와 무관하게 아래 명령문이 실행되었단 의미이다.

flag->store(true, std::memory_order_release);

그런데 여기서 std::memory_order_release가 설정되었으니 절대로 다음과 같이 명령문이 재배치될 일은 없다.

flag->store(true, std::memory_order_release);
*data = 10; // 절대 불가!!!

또한 std::memory_order_acquire를 통해 다음 재배치도 절대 일어날 수 없다.

std::cout << "Data : " << *data << std::endl;
while(!flag.load(std::memory_order_acquire));

따라서 우리는 안전하게 consumer thread에서 실행문이 의도대로 실행됨을 보장할 수 있다.

acquire-release 패턴을 이용하면 하나의 atomic 객체에 대해서는 우리 의도대로 실행됨을 보장할 수 있다. 그런데 만약 atomic 객체를 여러개 다룰 경우 어떡할까?

Sequentially Consistency Ordering

Sequentially Consistency Ordering은 acquire-release에 더해 하나의 제약이 추가된 조건이다.

std::atomic<bool> x = {false};
std::atomic<bool> y = {false};
std::atomic<int> z = {0};
 
void write_x()
{
    x.store(true, std::memory_order_release);
}
 
void write_y()
{
    y.store(true, std::memory_order_release);
}
 
void read_x_then_y()
{
    while (!x.load(std::memory_order_acquire));
    if (y.load(std::memory_order_acquire))
        ++z;
}
 
void read_y_then_x()
{
    while (!y.load(std::memory_order_acquire));
    if (x.load(std::memory_order_acquire))
        ++z;
}
 
int main()
{
    std::thread a(write_x);
    std::thread b(write_y);
    std::thread c(read_x_then_y);
    std::thread d(read_y_then_x);
    a.join(); b.join(); c.join(); d.join();
    assert(z.load() != 0); // 주목할 부분
}

위와 같이 두개의 atomic 변수 x, y에 대해 총 4개의 스레드를 통해 작업을 진행한다.
출력 결과는 어떻게 될까?

2는 당연히 가능할 것이다. 1도 가능할까? 가능하다. 예컨데 x.store(true)먼저 일어나고 아직 y.store(true)가 일어나지 않은 시점에 read_x_then_y가 완료되면 가능하다.

그럼 0은? 얼핏 보면 불가할 것 같지만 이론적으론 가능하다.
왜냐하면.. x, y 그 자신의 operation은 atomic하게 실행되지만, x.store => y.store 라거나 y.store => x.store라는 순서가 보장되는 것은 아니다.

즉, 각 변수에 대한 partial order는 보장되지만, x, y 간의 연산까지 total order가 보장되는 것이 아니다.

// write_x
x.store(true, std::memory_order_release);
// read_x_then_y
while (!x.load(std::memory_order_acquire));

이 순서는 보장되지만

x.store와 y.store의 순서가 모든 스레드에 동일하게 관측되진 않는다는 것.
따라서 read_x_then_y와 read_y_then_x에서 관측하는 순서가 반대가 될 수 있다..

std::memory_order_seq_cst는 이런 상황을 방지하기 위한 가장 안전한 수준의 설정으로,
모든 변수의 atomic operation이 그 자신 뿐만 아니라 다른 atomic 변수들에 있어서도 atomic하게 작동하도록 한다.

즉, 모든 x.store, y.store, x.load, y.load, x.compare_exchange_... 이런 모든 작업이 seq_cst에서는 하나의 total order로 작동하는 것.

따라서 만약 어떤 스레드에서 x.store -> y.store 순서로 관측한다면 다른 스레드에서도 x.store -> y.store 순서로 관측해야 한다는 것이다.
이걸 도대체 어떻게 구현하는지는 나도 아직은 잘 모르겠다. 아마 CPU 아키텍처 자체에 이런 동기화 기능이 포함되어있는 것 같다.

하여튼 위 예시를 다시 살펴보면

std::atomic<bool> x = {false};
std::atomic<bool> y = {false};
std::atomic<int> z = {0};
 
void write_x()
{
    x.store(true, std::memory_order_seq_cst);
}
 
void write_y()
{
    y.store(true, std::memory_order_seq_cst);
}
 
void read_x_then_y()
{
    while (!x.load(std::memory_order_seq_cst));
    if (y.load(std::memory_order_seq_cst))
        ++z;
}
 
void read_y_then_x()
{
    while (!y.load(std::memory_order_seq_cst));
    if (x.load(std::memory_order_seq_cst))
        ++z;
}
 
int main()
{
    std::thread a(write_x);
    std::thread b(write_y);
    std::thread c(read_x_then_y);
    std::thread d(read_y_then_x);
    a.join(); b.join(); c.join(); d.join();
    assert(z.load() != 0); // 절대 불가!
}

이제 z == 0인 경우는 절대 발생할 수 없다.

만약 y == true 시점에 x == false라면 read_y_then_x에서 관측한 결과는

y.store(true)만 일어난 시점이다. 따라서 read_x_then_y 스레드에서 x.store(true)에 의한 결과 x == true를 관측한 시점에는 반드시 y.store(true)도 일어났어야만 한다(total ordering)!

따라서 z == 0은 절대로 발생할 수 없는 것이다.

요약

출처

• https://en.cppreference.com/w/cpp/atomic/memory_order#Sequentially-consistent_ordering
• https://modoocode.com/271