멀티스레드 실행과 데이터 경쟁

멀티스레드 실행과 데이터 경쟁 (Multi-threaded executions and data races)

요즘 프로그램은 여러 스레드가 동시에 돌아가는 경우가 많죠. 그런데 스레드들이 같은 메모리를 건드리면 어떤 일이 벌어질까요? C++이 이 문제를 어떻게 규정하는지, 그리고 "데이터 경쟁"이 왜 위험한지 살펴볼게요.

출처: cppreference

본문

실행 스레드(thread of execution)는 프로그램 안의 제어 흐름으로, 특정 최상위 함수를 호출하는 것으로 시작해요(std::thread, std::async, C++20부터는 std::jthread 또는 다른 방법으로). 그리고 그 스레드가 이후에 실행하는 모든 함수 호출을 재귀적으로 포함해요.

• 어떤 스레드가 다른 스레드를 생성하면, 새 스레드의 최상위 함수에 대한 초기 호출은 만드는 스레드가 아니라 새 스레드가 실행해요.
• 어떤 스레드든 프로그램의 어떤 객체와 함수에도 잠재적으로 접근할 수 있어요.
  • 자동(automatic) 및 스레드 지역(thread-local) 저장 기간을 가진 객체도 포인터나 참조를 통해 다른 스레드가 접근할 수 있어요.
  • 호스티드(hosted) 구현에서는 C++ 프로그램이 둘 이상의 스레드를 동시에 실행할 수 있어요. 각 스레드의 실행은 이 페이지의 나머지 부분이 정의하는 대로 진행돼요. 전체 프로그램의 실행은 모든 스레드의 실행으로 구성돼요.
  • 프리스탠딩(freestanding) 구현에서는 프로그램이 둘 이상의 실행 스레드를 가질 수 있는지가 구현 정의(implementation-defined)예요.

std::raise를 호출한 결과로 실행되지 않는 시그널 핸들러의 경우, 시그널 핸들러 호출이 어느 실행 스레드에 속하는지는 불특정(unspecified)이에요.

데이터 경쟁 (Data races)

서로 다른 실행 스레드가 서로 다른 메모리 위치에 동시에 접근(읽기와 수정)하는 것은 항상 허용돼요. 방해(interference)도 없고 동기화 요구사항도 없어요.

두 표현식 평가가 충돌(conflict)한다는 것은, 하나가 메모리 위치를 수정하거나 그 메모리 위치에서 객체의 수명(lifetime)을 시작/종료하고, 다른 하나가 같은 메모리 위치를 읽거나 수정하거나, 그 메모리 위치와 겹치는 저장 공간을 차지하는 객체의 수명을 시작/종료하는 경우를 말해요.

충돌하는 두 평가가 있는 프로그램은, 다음 중 하나에 해당하지 않으면 데이터 경쟁을 가져요:

• 두 평가가 모두 같은 스레드나 같은 시그널 핸들러에서 실행되는 경우, 또는
• 두 충돌 평가가 모두 원자 연산(atomic operation)인 경우(std::atomic 참고), 또는
• 충돌하는 두 평가 중 하나가 다른 하나보다 happens-before(앞서 일어남) 관계인 경우(std::memory_order 참고).

데이터 경쟁이 발생하면 프로그램의 동작은 정의되지 않아요(undefined).

(특히, std::mutex의 해제(release)는 다른 스레드가 같은 뮤텍스를 획득하는 것과 synchronized-with 관계이며, 따라서 happens-before가 돼요. 그래서 뮤텍스 잠금으로 데이터 경쟁을 막을 수 있어요.)

데이터 경쟁이 얼마나 위험한지 두 예시를 비교해 볼게요.

int cnt = 0;
auto f = [&] { cnt++; };
std::thread t1{f}, t2{f}, t3{f}; // undefined behavior

cnt가 평범한 int라 세 스레드가 동시에 수정하면 데이터 경쟁이 일어나요. 반면에 원자 타입을 쓰면:

std::atomic<int> cnt{0};
auto f = [&] { cnt++; };
std::thread t1{f}, t2{f}, t3{f}; // OK

이제는 안전해요. std::atomic 덕분에 cnt++가 원자적으로 수행되니까요.

컨테이너 데이터 경쟁 (Container data races)

표준 라이브러리의 모든 컨테이너는 std::vector<bool>을 제외하고, 같은 컨테이너의 서로 다른 요소에 들어 있는 객체의 내용을 동시에 수정해도 절대 데이터 경쟁이 발생하지 않는다는 것을 보장해요.

std::vector<int> vec = {1, 2, 3, 4};
auto f = [&](int index) { vec[index] = 5; };
std::thread t1{f, 0}, t2{f, 1}; // OK
std::thread t3{f, 2}, t4{f, 2}; // undefined behavior

t1과 t2처럼 서로 다른 요소(0, 1)를 수정하는 건 괜찮아요. 하지만 t3와 t4가 같은 요소 2를 동시에 수정하면 데이터 경쟁이 돼요.

std::vector<bool> vec = {false, false};
auto f = [&](int index) { vec[index] = true; };
std::thread t1{f, 0}, t2{f, 1}; // undefined behavior

std::vector<bool>은 예외예요. 요소 하나가 실제로는 비트 하나라서, 서로 다른 요소라도 같은 메모리 위치를 공유할 수 있기 때문이에요.

메모리 순서 (Memory order)

스레드가 메모리 위치에서 값을 읽을 때, 초기 값, 같은 스레드에서 쓴 값, 또는 다른 스레드에서 쓴 값을 볼 수 있어요. 스레드가 쓴 값이 언제 다른 스레드에게 보이는지의 순서에 대한 자세한 내용은 std::memory_order를 참고하세요.

전진 진행 (Forward progress)

방해 자유 (Obstruction freedom)

표준 라이브러리 함수에 블록되지 않은 스레드가 하나만 있고, 그 스레드가 lock-free 원자 함수를 실행한다면, 그 실행은 완료가 보장돼요(모든 표준 라이브러리 lock-free 연산은 obstruction-free예요).

잠금 자유 (Lock freedom)

하나 이상의 lock-free 원자 함수가 동시에 실행될 때, 그중 적어도 하나는 완료가 보장돼요(모든 표준 라이브러리 lock-free 연산은 lock-free예요. 캐시 라인을 계속 훔쳐가는 것처럼 다른 스레드에 의해 무한히 live-lock되지 않도록 보장하는 것은 구현의 몫이에요).

진행 보장 (Progress guarantee)

유효한 C++ 프로그램에서, 모든 스레드는 결국 다음 중 하나를 수행해요:

• 종료한다.
• std::this_thread::yield를 호출한다.
• 라이브러리 I/O 함수를 호출한다.
• volatile glvalue를 통한 접근을 수행한다.
• 원자 연산이나 동기화 연산을 수행한다.
• 자명한 무한 루프(아래 참고)의 실행을 계속한다.

스레드가 위 실행 단계 중 하나를 수행하거나, 표준 라이브러리 함수에서 블록되거나, 블록되지 않은 동시 스레드 때문에 완료되지 않는 lock-free 원자 함수를 호출하면, 그 스레드는 진행(progress)한다고 말해요.

이 규칙 덕분에 컴파일러는 관찰 가능한 동작이 없는 모든 루프를 제거·병합·재배열할 수 있어요. 증명할 필요 없이 말이죠. 실행 스레드가 이런 관찰 가능한 동작 중 하나도 수행하지 않고 영원히 실행될 수 없다고 가정할 수 있기 때문이에요. 다만 자명한 무한 루프에는 예외가 있어서, 이건 제거되거나 재배열될 수 없어요.

자명한 무한 루프 (Trivial infinite loops)

자명하게 빈 반복문(trivially empty iteration statement)은 다음 형태 중 하나와 일치하는 반복문이에요:

while ( condition ) ;                          (1)
while ( condition ) { }                        (2)
do ; while ( condition ) ;                     (3)
do { } while ( condition ) ;                   (4)
for ( init-statement condition(optional) ; ) ;              (5)
for ( init-statement condition(optional) ; ) { }            (6)

자명하게 빈 반복문의 제어 표현식의 변환된 값이, 명시적으로 상수 평가(manifestly constant-evaluated)했을 때 상수 표현식이고 그 값이 true로 평가되면, 그 반복문은 자명한 무한 루프예요.

자명한 무한 루프의 루프 본문은 std::this_thread::yield 함수를 호출하는 것으로 대체돼요. 이 대체가 프리스탠딩 구현에서 일어나는지는 구현 정의예요.

for (;;); // 자명한 무한 루프, P2809부터 잘 정의됨
for (;;) { int x; } // undefined behavior

동시/병렬/약한 병렬 전진 진행

• 동시 전진 진행 (Concurrent forward progress): 스레드가 동시 전진 진행 보장을 제공하면, 다른 스레드(있다면)가 진행 중인지와 무관하게, 종료되지 않는 한 유한한 시간 안에 (위에서 정의한 대로) 진행해요. 표준은 메인 스레드와 std::thread, std::jthread(C++20부터)로 시작한 스레드가 동시 전진 진행 보장을 제공하기를 권장하지만, 강제하지는 않아요.
• 병렬 전진 진행 (Parallel forward progress): 스레드가 병렬 전진 진행 보장을 제공하면, 아직 어떤 실행 단계(I/O, volatile, 원자, 동기화)도 수행하지 않은 경우에는 결국 진행할 것이라는 것을 구현이 보장할 필요는 없어요. 하지만 일단 한 단계를 실행하고 나면, 그 스레드는 동시 전진 진행 보장을 제공해요(이 규칙은 임의 순서로 태스크를 실행하는 스레드 풀의 스레드를 설명한 것이에요).
• 약한 병렬 전진 진행 (Weakly parallel forward progress): 스레드가 약한 병렬 전진 진행 보장을 제공하면, 다른 스레드가 진행 중인지와 무관하게 결국 진행한다는 것은 보장되지 않아요. 이런 스레드도 전진 진행 보장 위임(forward progress guarantee delegation)으로 블록하면 진행이 보장될 수 있어요. 스레드 P가 어떤 스레드 집합 S의 완료에 이 방식으로 블록하면, S의 적어도 한 스레드는 P와 같거나 더 강한 전진 진행 보장을 제공해요. 그 스레드가 완료되면 S의 다른 스레드도 유사하게 강화돼요. 집합이 비면 P는 블록이 풀려요. C++ 표준 라이브러리의 병렬 알고리즘은 라이브러리 관리 스레드들의 불특정 집합의 완료에 전진 진행 위임으로 블록돼요. (C++17부터)

결함 보고 (Defect reports)

더 알아보기

• 메모리 모델
• std::memory_order
• std::atomic