[Concurrency] Atomic Operation: Memory Fence와 Memory Ordering

이 포스트는 atomic 연산에서 고려해야하는 메모리 순서에 대해 다룬다.
예시 코드는 Rust지만, Rust를 몰라도 내용은 이해할 수 있을 것이다.

메모리 펜스(Fence)와 순서(Ordering)는 Atomic operation 기반의 동시성 처리에 있어서 가장 중요한 핵심 요소다. 이걸 제대로 알지 못하고 쓴다면 Atomic을 쓰는 의미가 전혀 없다.

Out Of Order 현상

fence라는 것이 왜 필요한지를 알려면, CPU의 구조와 최적화 기법에 대해 알아야 한다.
현대의 컴파일러들은 필수적으로 인스트럭션 수준의 빠른 병렬처리를 위해 파이프라이닝(Pipelining)이라는 최적화를 수행한다.

그러려면 인스트럭션들을 빠르게 병렬로 돌리기 위해서 명령어의 순서를 마음대로 조작하는 경우가 많다.

만약 코드가 다음의 순서로 정의되었더라도

1. C = A+B

2. X = Y+Z

컴파일러가 이걸 뒤집어버릴 수도 있는 것이다.

1. X = Y+Z

2. C = A+B

이건 싱글스레드 환경에서는 문제가 없지만, 동시성 환경에서는 문제가 된다.

파이프라이닝 외에도 컴파일러나 하드웨어 수준 최적화에서 이렇게 순서를 꼬아놓는 원인은 몇가지 더 있다.

Memory Fence

그래서 저렇게 순서가 망가지는 상황 속에서 최소한의 안전장치를 마련하는 것을 메모리 펜스라고 부른다.
Arm에서는 이걸 Memory Barrier라고 부른다.

x86에서는 sfence/mfence/lfence와 같은 명령어를 통해 이러한 기능을 제공하고, 다른 프로세서들도 독자적인 일련의 명령어로 이러한 기능을 제공한다.

여기서 중요한 점은, 고급 언어에서 atomic 연산들을 다룰 때에도 이러한 개념을 어느정도 알고 사용해야 한다는 것이다.
대다수의 추상화된 atomic operation 함수들은, Ordering을 어떻게 처리할지를 지정하도록 되어있다.

Ordering 옵션은 언어를 불문하고 보통 아래와 같은 형태로 정의된다.

1. Relaxed: 아무 제약 없음
2. Acquire: 이 명령 이후에 선언된 read가 절대 이 명령 이전에 실행되지 않음.
3. Release: 이 명령 이전에 선언된 write가 절대 이 명령 이후에 실행되지 않음.
4. AcqRel: 읽기는 Acquire, 쓰기는 Release로 처리
5. SecCst: 이 명령 앞뒤의 read/write 명령의 순서를 엄격하게 앞뒤 그대로 유지

그래서 여러개의 atomic으로 동시에 읽고 쓰는 작업을 할때는 Acquire, 쓰기 작업을 할때는 Release를 써서 인스트럭션 순서가 꼬이지 않게 하는 것이 기본이다.
하지만 각 atomic이 독립적이고 서로 참조관계가 없다면 Relaxed만 사용하는 것이 가장 빠르다.

SecCst는 가장 엄격한 Ordering인데, 이걸 써야 하는 상황이 온다면 뭔가 코드를 잘못 짠게 아닌지를 먼저 고민해봐야 한다. 일반적인 상황에서는 이걸 사용할 일이 거의 없고, 쓰더라도 Atomic을 쓰는 의미가 없다.

한번 코드와 함께 동작 원리와 필요성을 간단히 설명해보겠다.

Relaxed Ordering

Relaxed Ordering은 가장 단순한 구조의 memory ordering이다. 단순히 연산이 atomic하게 실행된다는 것만이 보장된다. 단순한 만큼 빠르지만, 여러개의 atomic operation이 있을 때 그 실행 순서가 보장되지 않는다는 문제가 있다.

예를 들어, 다음과 같은 코드가 있다고 가정하겠다.

use std::sync::{atomic::AtomicI64, Arc};

fn main() {
    let x = Arc::new(AtomicI64::new(0));
    let y = Arc::new(AtomicI64::new(0));

    let thread1 = {
        let x = x.clone();
        let y = y.clone();
        std::thread::spawn(move || {
            let y_value = y.load(std::sync::atomic::Ordering::Relaxed);
            x.store(y_value, std::sync::atomic::Ordering::Relaxed);

            println!("y_value = {}", y_value);
        })
    };

    let thread2 = {
        let x = x.clone();
        let y = y.clone();
        std::thread::spawn(move || {
            let x_value = x.load(std::sync::atomic::Ordering::Relaxed);
            y.store(4444, std::sync::atomic::Ordering::Relaxed);

            println!("x_value = {}", x_value);
        })
    };

    thread1.join().unwrap();
    thread2.join().unwrap();
}

x와 y의 초기값은 0이다.
첫번쨰 스레드에서는 y의 값을 가져와서 x에 할당하고
두번째 스레드에서는 x의 값을 가져오지만 사용하지는 않고, y에 4444라는 숫자값을 할당한다.

이건 실제 스레드 실행 순서에 따라 다르겠지만, x_value 변수는 보통 0 값을 가질 것이라 기대할 것이다.
왜냐하면 x 값은 y 값에 의존적인데, 두번째 스레드에서는 x 값을 먼저 가져온 다음에 y에 값을 할당하기 때문이다.

그런데, Relaxed Ordering을 사용할 때는 x_value가 4444를 가지는 이상한 상황이 생길 수도 있다.

Relaxed Ordering의 실제 동작은 플랫폼에 따라 크게 다르다.

1. 애초에 strong order를 지향하는 플랫폼(x86 등)에서는 Relaxed를 사용하더라도 Release-Acquire 방식과 거의 같게 동작해서 성능 이점이 거의 없다. 그리고 위와 같은 부작용도 없을 것이다.
2. 반면 weak order를 지향하는 플랫폼(arm 등)에서는 Relaxed를 사용하면 약간의 성능 향상이 있을 수 있다. 그리고 위에서 설명한 부작용도 함께 발생할 것이다.

Release-Acquire Ordering

이게 가장 일반적으로 사용되는 형태의 Ordering이다.
이 2개의 Ordering은 다음과 같은 최적화 방지를 보장한다.

1. Acquire가 있다면, Acquire 이후에 발생한 연산은 항상 그 이후에 실행되는 것이 보장된다.

2. Release가 있다면, Release 이전에 발생한 연산은 항상 그 이전에 실행되는 것이 보장된다.

그래서 Relaxed에서 발생했던 순서 꼬임 문제를 해결하려면, 아래와 같이 Release-Acquire를 적용할 수 있다.

보통 atomic으로 read/write 작업을 하면 읽어오고-쓰는 순서가 되니까, load에 Acquire를 주고 store에 Release를 주는 경우가 많다.

SeqCst Ordering

가장 강력한 형태의 Ordering이다.
이걸 사용하면 해당 연산 앞뒤에 달려있는 연산들은 순서가 전부 고정된다. 모든 스레드에서 일관된 단일 순서를 강요하는 것이다.

이건 어떤 플랫폼에서 사용하든 비효율적인 코드 최적화를 낳는다. memory fence 인스트럭션이 사방에 떡칠될 것이기 때문이다. 그래서 실제 사용은 자제하는 편이 좋다. 대체로는 Release-Acquire만으로도 충분하다.
Release-Acquire로도 안된다면 뭔가 설계가 잘못되었다고 보는 편이 타당하다.

다른 스레드 간의 순서 꼬임 관측

이건 여러 스레드에서 여러개의 atomic operation을 교차해서 사용할 때 발생할 수 있는 엣지케이스를 다룬다.

아래는 그냥 2개의 스레드에서 각각 덧셈을 수행하는 코드다. 별건 없다.

그냥 이런 느낌으로 단일 atomic을 쓸때는 아무 문제가 없고, 여러개의 atomic을 동시에 쓰더라도 큰 문제는 없다.

하지만 예를 들어 이런식으로 atomic을 핸들링하면

우리는 number의 store가 먼저 실행된 이후에 number2의 store가 실행될 것이라고 기대할 것이다.

보통은 그게 맞다. 단일 스레드에서는 그렇게 동작하기도 한다.
문제는 멀티스레드 환경에서는 그게 보장되지 않는다는 것이다.

그래서 의도적으로 재현하기는 꽤 어렵지만, thread2에서는 number가 0이면서 number2가 20인 기묘한 상황을 관측할 수도 있다.

아래는 순서 꼬임 현상을 재현할 수 있는 예제 코드다. 실행해놓고 좀 기다리면 현상을 관측할 수도 있을 것이다.

use std::sync::{atomic::AtomicI64, Arc};

fn main() {
    loop {
        let barrier = Arc::new(std::sync::Barrier::new(2));

        let number = Arc::new(AtomicI64::new(0));
        let number2 = Arc::new(AtomicI64::new(0));

        let thread1 = {
            let number = number.clone();
            let number2 = number2.clone();
            let barrier = barrier.clone();
            std::thread::spawn(move || {
                barrier.wait();
                number.store(10, std::sync::atomic::Ordering::Relaxed);
                number2.store(20, std::sync::atomic::Ordering::Relaxed);
            })
        };

        let thread2 = {
            let number = number.clone();
            let number2 = number2.clone();
            let barrier = barrier.clone();
            std::thread::spawn(move || {
                barrier.wait();
                let number = number.load(std::sync::atomic::Ordering::Relaxed);
                let number2 = number2.load(std::sync::atomic::Ordering::Relaxed);

                if number == 0 && number2 == 20 {
                    println!("number = {}", number);
                    println!("number2 = {}", number2);
                }
            })
        };

        thread1.join().unwrap();
        thread2.join().unwrap();
    }
}

플랫폼이나 프로세서, 최적화 수준에 따라서 재현률은 달라질 수 있다.

이건 서로 다른 CPU 캐시와 내부 버퍼가 동일한 메모리에 대해 서로 다른 값을 보유할 수 있기 때문에 발생한다.
즉, 다른 스레드가 오래된 값을 볼 수 있다는 것이다. 따라서 number와 number2는 저장되긴 했지만 아직 다른 스레드로 전파되지는 않은 것이다. 캐시 전파 순서는 저장 순서와 다를 수 있다.

이 문제는 비단 memory ordering에 한정된 문제는 아니다. ordering을 바꾸더라도 근본적인 해결을 할 수는 없고, 이러한 상황이 문제가 될 수 있다면 메모리 배리어나 mutex, lock 같은 수단으로 비관적인 락을 잡아야 한다.

참조
https://ko.wikipedia.org/wiki/%EB%A9%94%EB%AA%A8%EB%A6%AC_%EB%B0%B0%EB%A6%AC%EC%96%B4
https://velog.io/@codingskynet/C11-Memory-Model-Atomic%EB%B6%80%ED%84%B0-Lock-Free-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EA%B9%8C%EC%A7%80
https://stackoverflow.com/questions/55680665/how-to-understand-relaxed-ordering-in-stdmemory-order-c
https://doc.rust-lang.org/nomicon/atomics.html
https://preshing.com/20120930/weak-vs-strong-memory-models/