happens-before

happens-before 는 두 일 가운데 어느 쪽이 먼저인지를 시계 없이 정해 줍니다. 기준은 시각이 아니라 한쪽이 다른 쪽에 영향을 줄 수 있었느냐입니다. 분산 시스템에서는 서버 사이의 사건 순서를 이것으로 따집니다. 멀티스레드 프로그램에서는 한 스레드가 쓴 값이 다른 스레드에 보이는지를 이것으로 따집니다.

상세

회의에서 바뀐 일정을 팀원에게 쪽지로 알린다고 해 봅시다. 쪽지를 읽은 팀원은 새 일정대로 움직입니다. 쪽지를 받기 전에 잡은 약속은 새 일정을 모른 채 잡은 약속입니다.

이 절은 두 장면으로 happens-before 를 봅니다. 하나는 스레드 둘이 변수를 함께 쓰는 짧은 자바 코드입니다. 다른 하나는 서버 둘이 메시지를 주고받는 장면입니다. 먼저 두 장면에 공통인 규칙을 세웁니다. 그다음 장면마다 그 규칙이 무엇을 막아 주는지 봅니다.

영향을 줄 수 있었다는 관계

happens-before 는 규칙 셋으로 생깁니다. 규칙을 적기 전에 낱말 둘을 정합니다.

실행 흐름은 명령을 하나씩 차례로 처리하는 주체입니다. 한 프로그램 안의 스레드가 실행 흐름입니다. 분산 시스템의 서버 한 대도 실행 흐름입니다.

사건은 실행 흐름이 겪는 일 하나입니다. 변수에 값을 쓰는 것, 락을 잡는 것, 메시지를 한 통 보내는 것이 각각 사건 하나입니다.

사건 a 가 사건 b 보다 happens-before 라는 말은 a 가 b 에 영향을 줄 수 있었다는 뜻입니다. 이 문서에서 「a 가 b 보다 앞」은 a happens-before b 를 줄인 말입니다. 시각을 말할 때는 「앞」 대신 「이르다」·「늦다」를 씁니다.

이 관계는 아래 세 규칙으로만 생깁니다.

1. 같은 실행 흐름 안에서는 먼저 처리한 사건이 앞입니다
2. 한 흐름이 무언가를 넘기고 다른 흐름이 그것을 받으면, 넘긴 사건이 받은 사건보다 앞입니다
3. a 가 b 보다 앞이고 b 가 c 보다 앞이면, a 는 c 보다 앞입니다

규칙 2 에서 무엇을 넘기고 받는지는 장면마다 다릅니다. 첫머리의 쪽지가 그 예입니다. 서버 사이에서는 메시지를 보내고 받는 것입니다. 스레드 사이에서는 락을 놓고 잡는 것 같은 동기화 동작입니다.

동시라는 말의 뜻

세 규칙을 어떻게 이어 붙여도 어느 쪽으로도 닿지 않는 두 사건이 있습니다. 이런 두 사건을 동시라고 부릅니다. 서로에게 영향을 줄 수 없었던 사이라는 뜻입니다.

쪽지를 받기 전에 팀원이 잡은 약속과 회의에서 바꾼 일정이 동시입니다. 둘 사이를 잇는 쪽지가 아직 없었기 때문입니다.

동시는 같은 시각에 일어났다는 뜻이 아닙니다. 벽시계로 몇 초 차이가 나도 둘 사이를 잇는 메시지나 동기화가 없으면 동시입니다. 거꾸로 시각이 이르다는 것만으로는 happens-before 가 되지 않습니다.

부분 순서는 모든 쌍이 아니라 일부 쌍에만 앞뒤가 정해지는 순서입니다. 동시인 쌍이 남으므로 happens-before 는 부분 순서입니다.

모든 쌍에 앞뒤를 정하는 순서는 전체 순서라고 합니다. happens-before 는 동시인 쌍을 남긴다는 점에서 전체 순서와 다릅니다.

스레드 사이에서 쓴 값이 보이는지

재료는 스레드 둘이 변수 둘을 함께 쓰는 짧은 자바 코드입니다. 먼저 happens-before 가 없을 때 무엇이 깨지는지 봅니다. 그다음 낱말 하나를 더해 고칩니다.

한 스레드가 변수에 쓴 값이 다른 스레드에 언제 보일지는 저절로 정해지지 않습니다. 컴파일러와 프로세서는 빨리 돌려고 읽기와 쓰기의 순서를 바꿉니다. 이것을 명령어 재배치라고 합니다.

한 스레드 안에서는 이 재배치가 드러나지 않습니다. 결과가 적은 순서대로 한 것과 같게 나오는 범위에서만 바꾸기 때문입니다. 재배치가 드러나는 것은 다른 스레드가 볼 때입니다.

아래 코드에서 스레드 A 는 값을 준비한 뒤 준비됐다는 표시를 켭니다. 스레드 B 는 표시가 켜진 것을 보고 값을 읽습니다.

int data = 0;
boolean ready = false;

// 스레드 A
data = 42;
ready = true;

// 스레드 B
if (ready) {
    int r = data;  // 42 또는 0
}

B 가 ready 를 true 로 읽었는데도 data 는 0 일 수 있습니다. A 의 두 쓰기가 B 에게는 바뀐 순서로 보였을 수 있기 때문입니다.

규칙으로 따지면 까닭이 보입니다. A 안에서는 규칙 1 로 data 쓰기가 ready 쓰기보다 앞입니다. 그런데 A 의 ready 쓰기와 B 의 ready 읽기 사이에는 동기화가 없습니다.

그래서 A 의 data 쓰기와 B 의 data 읽기는 동시입니다. B 가 data 를 42 로 읽을지 0 으로 읽을지는 보장되지 않습니다.

같은 변수를 두 스레드가 건드리고 적어도 하나가 쓰기라고 합시다. 이때 둘 사이에 happens-before 가 없는 상태를 데이터 경쟁이라고 합니다. 데이터 경쟁이 있는 코드는 돌 때마다 다른 값을 낼 수 있습니다.

volatile 로 관계를 세우기

고치는 법은 ready 선언에 volatile 을 붙이는 것입니다. volatile 은 여러 스레드가 함께 보는 변수에 붙이는 자바 키워드입니다.

volatile boolean ready = false;

volatile 변수에 쓴 사건은 그 값을 읽어 간 사건보다 앞입니다. 스레드 사이에 규칙 2 의 관계가 생긴 것입니다. 아래 그림에서 스레드 안의 화살표는 규칙 1 입니다. 스레드를 건너는 화살표는 규칙 2 입니다.

flowchart TD
    subgraph TA["스레드 A"]
        A1["data = 42"] --> A2["ready = true"]
    end
    subgraph TB["스레드 B"]
        B1["ready 읽기 · true"] --> B2["data 읽기"]
    end
    A2 -->|"volatile 쓰기 → 읽기"| B1

화살표를 따라가면 A 의 data = 42 에서 B 의 data 읽기까지 닿습니다. 규칙 3 으로 둘은 앞뒤가 되므로, ready 를 true 로 읽은 B 는 data 를 늘 42 로 읽습니다.

happens-before 는 그 순서대로 실행하라는 명령이 아닙니다. 결과가 그 순서대로 한 것과 같게만 나오면 컴파일러와 프로세서는 여전히 순서를 바꿀 수 있습니다. 막히는 것은 다른 스레드가 보는 결과를 바꾸는 재배치뿐입니다. 보장하는 것은 실행 순서가 아니라 보이는 결과입니다.

스레드 사이에 관계를 만드는 동작

volatile 말고도 규칙 2 를 세우는 동작이 여럿 있습니다. 자바에서 흔히 쓰는 것을 표로 모읍니다.

표의 첫 줄 덕분에 synchronized 블록 안에서 고친 필드는 다음에 같은 락을 잡은 스레드가 최신 값으로 읽습니다. 락은 상호 배제로 한 번에 한 스레드만 들어오게 막습니다. 그와 함께 고친 값이 다음 스레드에 보이게도 합니다.

표의 네 줄처럼 스레드 사이에 규칙 2 를 세우는 관계를 따로 synchronizes-with 라고 부릅니다. happens-before 는 이 관계와 규칙 1 을 규칙 3 으로 이어 붙여 만들어집니다.

서버 사이에서 사건의 앞뒤

서버 A 가 서버 B 에 요청을 보냅니다. B 는 그 요청을 받아 처리합니다. happens-before 는 원래 레슬리 램포트가 이런 장면의 사건 순서를 따지려고 happened before 라는 이름으로 세운 관계입니다.

서버 사이에서 규칙 2 를 세우는 것은 메시지입니다. A 가 요청을 보낸 사건은 B 가 그 요청을 받은 사건보다 앞입니다.

시각으로 순서를 매기면 안 되는 까닭은 기계마다 시계가 조금씩 어긋나 있어서입니다. 이 어긋남을 클록 스큐라고 합니다.

예를 들어 서버 A 가 자기 시계로 10:00:05 에 요청을 보냅니다. B 의 시계는 A 보다 3초 느립니다. 요청이 곧바로 도착하면 B 는 받은 시각을 10:00:02 로 남깁니다. 받은 사건이 보낸 사건보다 이른 시각으로 기록됩니다.

happens-before 는 시계 대신 메시지를 따라갑니다. 그래서 시계가 어긋나도 원인과 결과가 뒤집히지 않습니다.

이 관계를 사건마다 번호로 적어 두는 방법이 논리 시계입니다. 대표적인 것이 램포트 시계와 벡터 시계 둘입니다.

램포트 시계는 사건마다 번호 하나를 붙입니다. a 가 b 보다 앞이면 a 의 번호가 b 의 번호보다 작습니다. 그러나 번호만 보고는 두 사건이 앞뒤인지 동시인지 가리지 못합니다.

벡터 시계는 서버마다 칸을 하나씩 둔 번호 묶음을 붙입니다. 두 묶음을 칸마다 견주면 앞뒤인지 동시인지 가릴 수 있습니다.

관계를 세우는 비용

happens-before 는 공짜로 생기지 않습니다. 스레드 사이에서는 락이나 volatile 같은 동기화를 일부러 넣어야 생깁니다.

동기화에는 비용이 따릅니다. 락은 다른 스레드를 기다리게 합니다. volatile 은 그 앞뒤에서 다른 스레드가 보는 결과를 바꿀 수 있는 재배치를 못 하게 합니다. 순서를 바꿔 얻던 최적화가 그만큼 막힙니다.

서버 사이에서는 번호를 메시지마다 실어 보내야 합니다. 벡터 시계처럼 동시인지까지 가리려면 서버 수만큼 칸을 든 번호를 실어야 합니다. 그만큼 메시지가 커집니다.

따져야 하는 경우와 아닌 경우

여러 스레드가 락 없이 같은 변수를 읽고 쓰는 코드에서는 따져야 합니다. 플래그 하나로 다른 스레드에 「준비됐다」는 신호를 보내는 ready 코드가 그렇습니다. 서버 여러 대의 기록을 모아 무엇이 무엇의 원인이었는지 가릴 때도 따집니다.

한 스레드 안에서만 도는 코드는 따질 필요가 없습니다. 규칙 1 이 저절로 앞뒤를 정해 줍니다.

스레드끼리 변수를 나누지 않으면 따질 일이 없습니다. 나누더라도 공유 변수를 늘 같은 락 안에서만 읽고 쓰면 락이 관계를 세워 줍니다.

관련 항목

happens-before 가 속하는 상위 분류

메모리 모델 · 동시성 · 분산 시스템 · 부분 순서 · 인과 관계

happens-before 를 세우는 동기화 수단

락 · 뮤텍스 · 상호 배제 · volatile · synchronizes-with · 원자적 연산 · 메모리 배리어 · 세마포어

happens-before 가 없을 때 나는 오류와 그 원인

데이터 경쟁 · 경쟁 상태 · 가시성 · 명령어 재배치 · CPU 캐시 · 이중 검사 잠금

happens-before 를 번호로 적는 논리 시계

논리 시계 · 램포트 시계 · 벡터 시계 · 하이브리드 논리 시계 · 버전 벡터

happens-before 가 대신하는 시각 기준

벽시계 · 타임스탬프 · 클록 스큐 · NTP

happens-before 와 맞세워지는 순서 모델

전체 순서 · 프로그램 순서 · 순차 일관성 · 선형화 가능성 · 인과 일관성