사전 원자 연산
개념

원자 연산

gabury1고친 사람 github-actions[bot]

원자 연산은 여러 스레드가 같은 값을 동시에 고쳐도 고친 몫이 사라지지 않게 해 주는 연산입니다. 중간 단계를 남에게 보이지 않고 한 번에 끝납니다. 카운터를 하나 올리거나 깃발 하나를 세우는 작은 고치기에 씁니다. 데이터베이스가 말하는 원자성과는 이름만 닮았습니다. 원자 연산은 프로세서가 메모리의 값 하나를 다루는 수준에서 돕니다.

쉽고 빠른 이해

원자 연산은 여러 스레드가 함께 쓰는 값을 한 번에 고쳐 주는 연산입니다. 예를 들어 방문자 수를 하나 올리는 일을 두 스레드가 동시에 해도 둘 다 반영됩니다.

이게 없으면 「하나 올리기」 같은 한 줄 코드도 읽기·더하기·쓰기 세 단계로 쪼개집니다. 그 틈에 다른 스레드가 끼어들면 한쪽이 올린 값이 덮여 사라집니다.

어떻게 도는가:

  1. 프로세서가 그 값을 잠깐 혼자 쥡니다
  2. 읽고 고치고 쓰기를 한 동작으로 끝냅니다
  3. 다 끝난 뒤에야 다른 스레드가 그 값에 손댈 수 있습니다

대가도 있습니다. 보통 읽기·쓰기보다 느립니다. 스레드가 한 값에 몰리면 서로 기다리느라 더 느려집니다.

한계도 있습니다. 원자 연산은 값 하나만 지켜 줍니다. 값 여럿을 함께 바꿔야 하면 락이 필요합니다. 락은 한 번에 한 스레드만 코드 구간에 들어가게 막는 장치입니다.

상세

은행의 번호표 기계를 떠올려 봅시다. 손님 둘이 같은 순간에 버튼을 눌러도 같은 번호표가 두 장 나오지 않습니다. 기계는 번호를 뽑는 일과 다음 번호로 넘기는 일을 한 동작으로 합니다.

스레드는 한 프로그램 안에서 따로 도는 실행 흐름 하나입니다. 서버는 요청을 스레드 여럿에 나눠 맡겨 동시에 처리합니다. 이 스레드들은 같은 메모리를 함께 씁니다.

원자 연산(atomic operation)은 다른 스레드가 중간 상태를 볼 수 없게 한 번에 끝나는 메모리 연산입니다. 밖에서 보면 이 연산은 끝까지 다 됐거나 아직 시작도 안 했거나 둘 중 하나입니다. 서버의 요청 수 카운터가 대표 예입니다. 요청을 받는 스레드 여럿이 카운터 하나를 동시에 올립니다.

한 줄짜리 코드가 왜 한 번에 끝나지 않는지에서 시작해, 프로세서가 그 틈을 막는 방법과 원자 연산의 대가, 쓸 때와 안 쓸 때까지 차례로 봅니다.

한 줄 코드 안의 세 단계

카운터를 하나 올리는 코드 count++ 를 쪼개 봅시다. 개요에서 말한 프로세서는 CPU(Central Processing Unit, 중앙 처리 장치)입니다. 소스에서는 한 줄이지만 CPU 는 이 일을 세 단계로 합니다.

  1. 메모리에서 count 의 값을 읽어 옵니다
  2. 읽어 온 값에 1을 더합니다
  3. 더한 값을 메모리에 다시 씁니다

스레드 하나만 돌면 문제가 없습니다. 스레드 둘이 동시에 돌면 두 스레드의 단계가 섞일 수 있습니다. 아래 그림은 count 가 5일 때 두 스레드가 거의 같은 순간에 하나씩 올리는 장면입니다.

sequenceDiagram
    participant A as 스레드 A
    participant M as 메모리 · count
    participant B as 스레드 B
    A->>M: 읽는다
    M-->>A: 5
    B->>M: 읽는다
    M-->>B: 5
    A->>M: 6 을 쓴다
    B->>M: 6 을 쓴다
    Note over A,B: 두 번 올렸는데 6 이다

두 스레드가 모두 5를 읽었습니다. 둘 다 6을 썼습니다. 스레드 A 가 올린 몫은 스레드 B 의 쓰기에 덮여 사라졌습니다. 이렇게 한쪽이 고친 값이 다른 쪽 쓰기에 묻히는 일을 갱신 손실이라고 합니다.

결과가 스레드의 실행 순서에 따라 달라지는 상황을 경쟁 상태라고 부릅니다. 갱신 손실은 경쟁 상태가 낳는 결과의 하나입니다. 원자 연산은 세 단계를 하나로 묶어 그 틈을 없앱니다.

반쪽만 쓰인 값

틈은 읽고 고치고 쓰는 사이에만 있지 않습니다. 쓰기 하나도 쪼개질 수 있습니다.

CPU 가 한 번에 처리하는 데이터 크기를 워드라고 합니다. 워드보다 큰 값은 두 번에 나눠 써야 합니다. 예를 들어 32비트 CPU 가 64비트 값을 쓰면 앞 32비트와 뒤 32비트를 따로 씁니다. 아래 그림은 그 두 쓰기 사이에 다른 스레드가 값을 읽는 장면입니다.

sequenceDiagram
    participant A as 스레드 A
    participant M as 메모리
    participant B as 스레드 B
    A->>M: 앞 32비트에 새 값을 쓴다
    B->>M: 64비트 값을 읽는다
    M-->>B: 앞은 새 값 · 뒤는 옛 값
    A->>M: 뒤 32비트에 새 값을 쓴다
    Note over A,B: 아무도 쓴 적 없는 값을 읽었다

스레드 B 는 새 값 반쪽과 옛 값 반쪽이 섞인 값을 얻었습니다. 어느 스레드도 쓴 적이 없는 값입니다. 이런 읽기를 찢어진 읽기라고 부릅니다. 원자적 읽기와 원자적 쓰기는 값 전체가 한 번에 오가게 해 이것을 막습니다.

프로세서가 내주는 원자 명령

원자 연산은 CPU 의 명령으로 돕니다. CPU 가 갖춘 원자 명령은 대개 아래 네 가지입니다.

표의 「쓰는 곳」 칸에 나오는 락은 한 번에 한 스레드만 코드 구간에 들어가게 막는 장치입니다. 값 여럿을 한 덩어리로 바꿀 때 씁니다.

명령 한 번에 하는 일 쓰는 곳
원자적 읽기 · 쓰기 값 전체를 한 번에 읽거나 쓴다 깃발 · 상태 값
교환 새 값을 쓰고 옛 값을 돌려준다 락 잡기
가져와 더하기 값을 더하고 더하기 전 값을 돌려준다 카운터 · 번호 발급
비교 후 교환 지금 값이 기대한 값일 때만 새 값을 쓴다 락 프리 자료구조

표의 첫 줄은 값을 옮기기만 합니다. 나머지 셋은 읽고 고치고 쓰기를 한 명령으로 합니다. 이런 명령을 묶어 읽기-수정-쓰기 명령이라고 부릅니다. 갱신 손실을 막는 것은 이 묶음입니다.

비교 후 교환은 compare-and-set이라고도 부릅니다. 이 명령은 「내가 읽은 뒤로 아무도 안 바꿨으면 쓴다」를 한 번에 합니다. 다른 원자 연산 대부분을 이 명령 위에 지을 수 있습니다.

표 끝 줄의 락 프리 자료구조는 락 없이 원자 명령만으로 여러 스레드가 함께 쓰게 만든 자료구조입니다. 비교 후 교환이 그 바탕입니다.

어떤 CPU 는 비교 후 교환 대신 두 명령의 짝으로 같은 일을 합니다. 첫 명령은 값을 읽으며 표시를 남깁니다. 둘째 명령은 그 뒤로 아무도 그 값을 안 건드렸을 때만 씁니다. 이 짝을 load-linked 와 store-conditional 이라고 부릅니다.

캐시 라인을 잠깐 혼자 쥐는 방식

원자 명령은 세 단계 사이에 아무도 못 끼어들게 해야 합니다. CPU 는 이 일을 메모리를 곁에 복사해 두는 방식으로 풉니다.

요즘 CPU 에는 코어가 여럿 있습니다. 코어는 CPU 안에서 명령을 실행하는 단위입니다. 코어가 여럿이면 스레드 여럿이 정말로 같은 순간에 돕니다.

메모리는 코어에 비해 느립니다. 그래서 코어마다 메모리 일부를 곁에 복사해 두는 CPU 캐시를 둡니다. 자주 쓰는 값은 메모리까지 가지 않고 캐시에서 꺼냅니다.

캐시는 메모리를 캐시 라인이라는 일정한 크기의 덩어리로 나눠 들고 옵니다. 값 하나만 필요해도 그 값이 든 덩어리째 복사합니다.

코어마다 캐시가 따로 있으니 같은 값의 사본이 여러 캐시에 생길 수 있습니다. 사본끼리 값이 다르면 곤란합니다. 그래서 캐시끼리 사본을 맞추는 규칙이 하드웨어에 들어 있습니다. 이 규칙을 캐시 일관성 프로토콜이라고 합니다.

원자 명령을 실행하는 코어는 그 값이 든 캐시 라인을 잠깐 혼자 쥡니다. 다른 코어의 캐시에 있던 사본은 지워집니다. 명령이 끝날 때까지 다른 코어는 그 캐시 라인을 읽지도 쓰지도 못하고 기다립니다.

옛 CPU 는 메모리로 가는 버스 전체를 잠가서 같은 일을 했습니다. 버스는 CPU 와 메모리를 잇는 통로입니다. 버스를 잠그면 상관없는 다른 메모리 접근까지 멈춥니다. 캐시 라인 하나만 쥐는 방식은 막는 범위를 그 값 하나로 좁힌 것입니다.

flowchart TD
    subgraph C1["코어 1 · 원자 명령 실행 중"]
        K1["코어 1"] --> H1["캐시 1 · count 가 든 캐시 라인 · 혼자 쥠"]
    end
    subgraph C2["코어 2"]
        K2["코어 2"] --> H2["캐시 2 · count 사본 지워짐 · 기다림"]
    end
    H1 -->|버스| MEM["메모리"]
    H2 -->|버스| MEM

그림에서 코어 1 은 count 가 든 캐시 라인 하나만 쥡니다. 코어 2 는 그 캐시 라인을 기다립니다. 버스는 잠그지 않으므로 메모리로 가는 통로는 열려 있습니다.

정렬이 필요한 까닭

값이 자기 크기의 배수인 주소에서 시작하면 정렬되었다고 합니다. 예를 들어 8바이트 값이 8의 배수 주소에서 시작하면 정렬된 것입니다.

캐시 라인도 자기 크기의 배수인 주소에서 시작합니다. 아래 예는 캐시 라인을 64바이트로 둡니다. 그러면 캐시 라인은 0번, 64번, 128번 주소에서 시작합니다.

64는 8의 배수입니다. 그래서 8의 배수 주소에서 시작한 8바이트 값은 다음 캐시 라인의 시작 주소를 넘지 않습니다. 정렬된 값은 캐시 라인 하나 안에 다 들어가고, CPU 는 그 캐시 라인 하나만 쥐고 원자 명령을 끝냅니다.

정렬되지 않은 값은 두 캐시 라인에 걸칠 수 있습니다. 아래 그림에서 60번 주소에서 시작한 8바이트 값은 앞 4바이트가 캐시 라인 0 에, 뒤 4바이트가 캐시 라인 1 에 놓입니다.

block-beta
columns 2
  L0["캐시 라인 0 · 주소 0~63"] L1["캐시 라인 1 · 주소 64~127"]
  A["정렬된 8바이트 · 56~63 · 캐시 라인 0 안"] space
  B["안 정렬된 8바이트 · 60~67 · 두 캐시 라인에 걸침"]:2

그러면 CPU 는 두 덩어리를 따로 다뤄야 합니다. 무슨 일이 나는지는 CPU 마다 다릅니다. 원자성을 보장하지 않는 CPU 가 있습니다. 오류를 내고 멈추는 CPU 도 있습니다. 두 캐시 라인을 함께 잡느라 크게 느려지는 CPU 도 있습니다.

그래서 원자 연산에 쓰는 값은 정렬된 주소에 둡니다. 언어가 내주는 원자 타입은 대개 이 정렬을 알아서 맞춥니다.

언어가 내주는 원자 연산

개발자가 CPU 명령을 직접 쓰는 일은 드뭅니다. 백엔드 코드에서는 언어와 라이브러리가 원자 연산을 감싸 내줍니다.

Java 에서는 AtomicInteger 같은 클래스가 이 일을 맡습니다. 아래 코드는 두 스레드가 각자 10만 번씩 카운터를 올린 뒤 값을 봅니다. 마지막 두 줄의 오른쪽 주석이 그 줄이 내는 값입니다.

Java
int plain = 0;
AtomicInteger atomic = new AtomicInteger();

// 스레드 둘이 각자 10만 번씩 실행
plain++;
atomic.incrementAndGet();

plain         // 200000 보다 작을 수 있다
atomic.get()  // 200000

plain++ 는 앞에서 본 세 단계로 쪼개져 갱신 손실이 납니다. incrementAndGet 은 원자 연산으로 돌아 한 번도 잃지 않습니다.

다른 언어도 같은 것을 갖춥니다. C 는 _Atomic 타입 지정자와 <stdatomic.h> 헤더를, C++ 는 std::atomic 템플릿을 둡니다. Go 는 sync/atomic 패키지로 내줍니다.

원자 연산이 지켜 주지 않는 순서

원자 연산은 값 하나가 쪼개지지 않게 지켜 줍니다. 그 값 앞뒤에 있는 다른 메모리 읽기·쓰기의 순서는 따로 정해야 합니다. 그 까닭을 깃발 하나를 세우는 장면으로 봅니다.

CPU 와 컴파일러는 속도를 내려고 서로 상관없어 보이는 메모리 접근의 순서를 바꿉니다. 이것을 재배치라고 합니다. 스레드 하나 안에서는 결과가 같아서 티가 안 납니다. 다른 스레드가 지켜보면 뒤바뀐 순서가 보일 수 있습니다.

예를 들어 스레드 A 가 데이터를 다 채운 뒤 「준비됨」 깃발을 원자적으로 세운다고 합시다. 스레드 B 는 깃발이 선 것을 보고 데이터를 읽습니다. 재배치 때문에 깃발이 데이터보다 먼저 보이면 B 는 덜 채운 데이터를 읽습니다. 아래 그림은 B 에게 보이는 순서대로 그렸습니다.

sequenceDiagram
    participant A as 스레드 A
    participant M as 메모리 · B 에게 보이는 순서
    participant B as 스레드 B
    Note over A: 코드에 적은 순서는 데이터 → 깃발
    A->>M: 준비됨 깃발을 세운다 · 먼저 보인다
    B->>M: 깃발을 읽는다
    M-->>B: 섰다
    B->>M: 데이터를 읽는다
    M-->>B: 옛 값
    A->>M: 데이터를 쓴다 · 늦게 보인다

A 는 코드에 데이터 쓰기를 먼저 적었습니다. 그런데 B 에게는 깃발이 먼저 보이고 데이터는 나중에 보였습니다. 그 사이에 데이터를 읽은 B 는 옛 값을 얻습니다.

그래서 원자 연산에는 순서를 얼마나 세게 지킬지를 함께 고르게 합니다. 이 세기를 메모리 순서라고 합니다. 가장 센 쪽은 모든 원자 연산이 한 줄로 늘어선 것처럼 보이게 합니다. 가장 약한 쪽은 값 하나의 원자성만 지키고 앞뒤 순서는 맡지 않습니다.

깃발 장면은 순서 보장을 걸어서 풉니다. 깃발을 세우는 쪽과 읽는 쪽이 모두 순서를 지키게 고르면, 깃발 앞에 적은 데이터 쓰기가 깃발보다 먼저 보입니다. 이 보장은 원자 연산이 아닌 보통 쓰기에도 미칩니다. 그래서 B 는 깃발이 선 것을 본 뒤에 다 채운 데이터를 읽습니다.

순서 보장은 공짜가 아닙니다. 그만큼 CPU 와 컴파일러가 재배치를 멈춰야 하기 때문입니다. 필요한 곳에는 순서를 강제하는 명령이 끼어드는데, 이 명령을 메모리 배리어라고 합니다.

값 하나를 넘는 일

원자 연산이 한 번에 다루는 것은 값 하나입니다. 대개 워드 하나입니다. 크게 잡아도 워드 둘입니다.

계좌 A 에서 돈을 빼고 계좌 B 에 더하는 일은 값 둘을 함께 바꿔야 합니다. 각각을 원자 연산으로 바꿔도 두 연산 사이에 틈이 남습니다. 아래 그림처럼 그 틈에 다른 스레드는 「A 에서만 빠진 상태」를 봅니다.

sequenceDiagram
    participant T1 as 스레드 1
    participant M as 메모리 · 계좌 A · B
    participant T2 as 스레드 2
    T1->>M: A 에서 뺀다 · 원자
    T2->>M: A 와 B 를 읽는다
    Note over T2: A 에서만 빠진 상태
    T1->>M: B 에 더한다 · 원자

값 여럿을 한 덩어리로 바꾸려면 락을 씁니다. 락을 쥔 스레드가 A 와 B 를 다 바꿀 때까지 다른 스레드는 들어오지 못합니다. 락 자체도 원자 연산으로 만듭니다. 교환이나 비교 후 교환으로 「잠김」 표시를 한 번에 세우는 식입니다.

데이터베이스의 트랜잭션이 말하는 원자성은 결이 다릅니다. 트랜잭션은 여러 쓰기 중 하나가 실패하면 전부 되돌려 반쪽 결과를 안 남깁니다. 원자 연산은 되돌리지 않습니다. 끼어들 틈을 처음부터 없앱니다. 두 뜻은 원자성 항목이 함께 가릅니다.

원자 연산의 대가

원자 연산이 보통 읽기·쓰기보다 더 치르는 대가는 셋입니다.

첫째, 원자 명령은 보통 명령보다 느립니다. 캐시 라인을 혼자 쥐려면 다른 코어의 사본을 먼저 지워야 합니다. 순서 보장을 함께 챙기면 그만큼 더 기다립니다.

둘째, 여러 스레드가 한 값에 몰리면 더 느려집니다. 그 값이 든 캐시 라인이 이 코어에서 저 코어로 계속 옮겨 다니기 때문입니다. 이렇게 한 값을 두고 다투는 것을 경합이라고 합니다. 코어가 늘수록 기다리는 시간도 늘어납니다.

셋째, 상관없는 두 값이 한 캐시 라인에 같이 들어 있어도 같은 일이 납니다. 스레드 A 는 값 x 를, 스레드 B 는 값 y 를 고친다고 합시다. 둘은 다른 값을 고치지만 캐시 라인 하나를 두고 다툽니다. 이것을 거짓 공유라고 부릅니다.

flowchart TD
    TA["스레드 A · 코어 1"] -->|x 를 고친다| X
    TB["스레드 B · 코어 2"] -->|y 를 고친다| Y
    subgraph LINE["캐시 라인 하나"]
        X["값 x"]
        Y["값 y"]
    end

그림에서 x 와 y 는 서로 다른 값이지만 한 캐시 라인에 들어 있습니다. 그래서 그 캐시 라인이 두 코어 사이를 계속 오갑니다. 자주 고치는 원자 변수끼리는 서로 다른 캐시 라인에 떨어뜨려 둡니다.

경합을 줄이는 흔한 방법은 카운터를 스레드마다 나눠 두는 것입니다. 각 스레드는 제 칸만 올립니다. 합계가 필요할 때만 칸들을 더합니다. Java 의 LongAdder 가 이 방식으로 돕니다.

쓸 때와 안 쓸 때

원자 연산을 고를지 말지는 두 물음으로 가립니다. 함께 바꿀 값이 하나인지, 그 값이 카운터이고 스레드가 몰리는지입니다.

flowchart TD
    Q1{"함께 바꿀 값이 하나인가"}
    Q1 -->|아니다| L["락이나 트랜잭션을 쓴다"]
    Q1 -->|그렇다| Q2{"카운터에 스레드가 몰리나"}
    Q2 -->|그렇다| S["스레드마다 나눠 세고 나중에 더한다"]
    Q2 -->|아니다| A["원자 연산을 쓴다"]

값 하나로 끝나는 일이 원자 연산의 몫입니다. 아래 표는 그런 일과 거기 쓰는 명령을 짝지은 것입니다.

쓰임 쓰는 명령
요청 수 · 오류 수 카운터 가져와 더하기
종료 · 준비됨 깃발 원자적 읽기 · 쓰기
다음 번호 발급 가져와 더하기
참조 카운트 가져와 더하기 · 빼기
한 번만 하는 초기화 비교 후 교환
락 구현 교환 · 비교 후 교환

참조 카운트는 객체를 가리키는 쪽이 몇인지 세는 값입니다. 0이 되면 객체를 치웁니다. 여러 스레드가 동시에 늘리고 줄이므로 원자 연산으로 셉니다.

한 번만 하는 초기화는 「아직 안 함」 표시를 「하는 중」으로 바꾸는 비교 후 교환으로 합니다. 여러 스레드가 동시에 시도해도 성공하는 스레드는 하나뿐입니다. 그 스레드만 초기화를 맡습니다.

조심할 것은 원자 연산 둘을 이어 붙여 하나처럼 쓰는 코드입니다. 연산 하나하나는 원자적이어도 그 사이에는 틈이 있습니다. 아래는 카운터가 10을 넘지 않게 하려던 코드입니다.

Java
if (n.get() < 10) {  // 둘 다 9 를 본다
  n.incrementAndGet(); // 결과는 11
}

두 스레드가 모두 9를 읽고 검사를 통과합니다. 그다음 둘 다 올려 11이 됩니다. 검사한 값과 고칠 때의 값이 달라질 수 있는 이 꼴을 검사 후 실행 경쟁이라고 부릅니다. 이럴 때는 비교 후 교환으로 검사와 쓰기를 한 번에 묶거나 락을 씁니다.

관련 항목

원자 연산이 지켜 주는 성질

가시성 · 메모리 순서 · 메모리 모델 · 선형화 가능성 · 순차 일관성

원자 연산을 이루는 프로세서 명령

compare-and-set · fetch-and-add · test-and-set · 원자적 교환 · load-linked · store-conditional · 읽기-수정-쓰기 · 메모리 배리어

원자 연산이 기대는 하드웨어 구성 요소

CPU · 코어 · CPU 캐시 · 캐시 라인 · 캐시 일관성 · MESI 프로토콜 · 버스 · 워드 · 정렬

원자 연산 위에 짓는 동기화 장치

락 · 뮤텍스 · 스핀락 · 세마포어 · 락 프리 · 참조 카운트

원자 연산으로 막는 동시성 고장

경쟁 상태 · 갱신 손실 · 찢어진 읽기 · 데이터 경쟁 · 검사 후 실행

원자 연산을 쓰다 부딪히는 고장

ABA 문제 · 거짓 공유 · 경합 · 락 경합 · 명령어 재배치

다른 이름: atomic operation · 아토믹 연산 · 원자 명령