두 변수로 메모리 순서 비교하기

공유 메모리·NUMA·일관성에서 위치 하나의 값을 맞추는 캐시 일관성과, 여러 위치에 대한 접근이 보이는 순서를 정하는 메모리 일관성 모델은 다른 문제라고 했습니다. 이 글에서는 두 변수 X와 Y만 쓰는 아주 짧은 예로 그 차이를 직접 계산합니다. 이렇게 어떤 결과가 가능한지를 묻는 짧은 동시 실행 예를 리트머스 테스트(litmus test)라고 부릅니다.

두 코어의 프로그램

처음에 X = Y = 0이고, 각 읽기와 쓰기는 중간에 쪼개지지 않는다고 하겠습니다. 코어 A는 X에 1을 쓴 뒤 Y를 읽어 rA에 담고, 코어 B는 Y에 1을 쓴 뒤 X를 읽어 rB에 담습니다. rA와 rB는 각 코어가 자기만 쓰는 값이고, 괄호 안은 아래에서 쓸 연산의 이름입니다.

질문은 두 코어가 모두 0을 읽는 (rA, rB) = (0, 0)이 가능한가입니다. 각 코어는 자기 변수를 먼저 쓰고 상대 변수를 나중에 읽으므로, 직관적으로는 둘 가운데 적어도 하나는 1을 읽을 것 같습니다. 이 예는 프로그램에 적힌 순서와, 쓰기가 다른 코어에게 보이게 되는 순서를 구별하려는 것입니다. C나 C++ 프로그램에서 보통 변수로 이렇게 데이터 경쟁을 일으키면 컴파일러가 순서를 바꿀 수도 있으므로, 이 예를 그런 프로그램의 결과 예측으로 쓰면 안 됩니다.

순차 일관성에서는 불가능하다

순차 일관성(sequential consistency, SC)은 모든 코어의 메모리 연산을 하나의 줄로 세울 수 있고, 그 줄에서 각 코어의 연산은 프로그램 순서대로 놓이며, 읽기는 줄에서 그보다 앞선 가장 최근의 쓰기를 본다는 모델입니다. 1979년 Leslie Lamport가 정의한 것으로, 사람이 프로그램을 읽으며 기대하는 동작에 가장 가깝습니다. 이 예에서는 AX가 AR보다, BY가 BR보다 앞서야 하므로 가능한 줄은 여섯 가지입니다.

여섯 가지 어디에도 (0, 0)은 없습니다. 이유를 순서의 관계로 보일 수도 있습니다. rA = 0이려면 AR이 BY보다 앞서야 하고, rB = 0이려면 BR이 AX보다 앞서야 합니다. 여기에 프로그램 순서 AX가 AR보다, BY가 BR보다 앞선다는 조건을 이으면 AX, AR, BY, BR, AX의 순서로 한 바퀴를 돌게 되어, 한 줄 위에 놓을 수 없습니다.

저장 버퍼가 있으면 가능하다

실제 CPU는 쓰기를 마칠 때까지 기다리지 않으려고, 쓸 값을 먼저 코어 안의 저장 버퍼(store buffer)에 넣어 두고 다음 명령어를 진행합니다. 버퍼의 값은 나중에 공유 메모리에 반영되어 다른 코어에게 보이게 됩니다. 이 교재의 모델에서는 쓰기를 버퍼에 넣는 일(AX, BY)과 공유 메모리에 반영하는 일(AF, BF)을 따로 나누겠습니다. 이 예에서는 각 코어가 자기 버퍼에 있는 주소를 다시 읽는 일이 없으므로, 읽기는 모두 공유 메모리에서 합니다.

두 쓰기가 모두 버퍼에 머무는 동안 두 읽기가 공유 메모리의 0을 읽었으므로 (0, 0)이 나옵니다. 마지막에는 공유 메모리가 X = Y = 1로 맞추어지지만, 이미 읽은 rA와 rB는 바뀌지 않습니다. 캐시 일관성이 각 위치의 값을 맞추어 주어도 여러 위치 사이의 순서는 따로라는 것이 이 예의 요점입니다. 이 저장 버퍼 모델은 설명을 위해 만든 것이며, 실제 CPU의 메모리 모델을 모두 대신하지는 않습니다.

모든 순서를 나열해 확인한다

손으로 몇 가지 순서를 시험하는 대신, 조건을 만족하는 모든 순서를 나열해 가능한 결과를 모읍니다. 순차 일관성에서는 쓰기와 반영을 하나의 사건으로 두고, 저장 버퍼 모델에서는 둘을 나눕니다. 마지막 경우에는 두 코어 모두 자기 쓰기가 반영된 뒤에야 읽기를 하도록 조건을 더하는데, 이것이 메모리 장벽(memory barrier, fence)이 하는 일을 흉내 낸 것입니다.

from itertools import permutations


def outcomes(buffered=False, fenced=False):
    events = ("AX", "AR", "BY", "BR", "AF", "BF") if buffered else ("AX", "AR", "BY", "BR")
    constraints = [("AX", "AR"), ("BY", "BR")]
    if buffered:
        constraints += [("AX", "AF"), ("BY", "BF")]
        if fenced:
            constraints += [("AF", "AR"), ("BF", "BR")]
    results, accepted = set(), 0
    for order in permutations(events):
        if any(order.index(first) > order.index(second) for first, second in constraints):
            continue
        accepted += 1
        x = y = 0
        ra = rb = None
        for event in order:
            if event == ("AF" if buffered else "AX"):
                x = 1
            elif event == ("BF" if buffered else "BY"):
                y = 1
            elif event == "AR":
                ra = y
            elif event == "BR":
                rb = x
        results.add((ra, rb))
    return accepted, sorted(results)


for buffered, fenced in ((False, False), (True, False), (True, True)):
    print(*outcomes(buffered, fenced))

6 [(0, 1), (1, 0), (1, 1)]
80 [(0, 0), (0, 1), (1, 0), (1, 1)]
20 [(0, 1), (1, 0), (1, 1)]

permutations는 사건들을 늘어놓는 모든 순서를 만들고, constraints의 각 쌍은 앞의 사건이 뒤의 사건보다 먼저여야 한다는 조건입니다. 조건을 어기는 순서는 버리고, 남은 순서마다 사건을 차례로 실행해 rA와 rB를 집합에 모읍니다. 쓰기가 공유 메모리에 반영되는 사건은 순차 일관성에서는 AX와 BY, 저장 버퍼 모델에서는 AF와 BF입니다.

첫 줄은 순차 일관성의 6가지 순서에서 앞의 표와 같은 세 결과만 나온다는 것이고, 둘째 줄은 저장 버퍼 모델에서 80가지 순서가 가능하며 (0, 0)이 결과에 들어간다는 것입니다. 셋째 줄은 두 코어 모두 반영을 기다린 뒤 읽게 하면 20가지 순서만 남고 (0, 0)이 다시 사라진다는 것입니다. 여기서 6, 80, 20은 이 모델에서 조건을 만족하는 순서의 수일 뿐, 실제 CPU에서 각 결과가 나올 확률이나 횟수가 아닙니다.

순서의 수는 손으로도 셀 수 있습니다. 순차 일관성에서는 네 자리 가운데 A의 두 사건이 놓일 자리를 고르면 순서가 정해지므로 $\binom42=6$입니다. 저장 버퍼 모델에서는 여섯 자리 가운데 A의 세 사건이 놓일 자리를 고르는 $\binom63=20$가지에, A 안에서 AR과 AF의 순서 2가지와 B 안에서 BR과 BF의 순서 2가지를 곱해 20 × 2 × 2 = 80입니다. 양쪽에 장벽을 두면 각 코어 안의 순서가 하나로 정해지므로 20가지만 남습니다.

장벽이 막는 것과 막지 못하는 것

두 코어 모두 "쓰기를 버퍼에 넣고, 반영이 끝나기를 기다린 뒤, 읽는다"는 순서를 지키게 하면 순차 일관성과 같은 결과만 남습니다. 한 코어에만 장벽을 두면 다른 코어는 여전히 자기 쓰기가 반영되기 전에 읽을 수 있어서 (0, 0)을 막지 못합니다. 그래서 장벽은 어느 코어의 어느 두 연산 사이의 순서가 필요한지 정확히 정해 그 자리에 두어야 합니다. 또 장벽은 순서만 정할 뿐, 갱신 손실에서 본 읽기, 더하기, 쓰기를 하나의 원자적 동작으로 만들어 주지는 않습니다.

실제 ISA의 메모리 모델은 이보다 훨씬 정교합니다. 예를 들어 RISC-V의 RVWMO 규격 원문은 전체 메모리 순서, 지켜지는 프로그램 순서, fence와 acquire, release의 조건을 정의합니다. 이 글의 모델은 저장 버퍼의 효과를 보이려고 만든 작은 모델이라, 실제 ISA의 결과, 컴파일러가 순서를 바꾸는 경우, 캐시 프로토콜, 입출력의 순서까지 확인한 것은 아닙니다.

더 깊이: TSO에서도 남는 저장 버퍼의 효과

x86과 SPARC는 기본으로 TSO(total store ordering)라는 메모리 모델을 씁니다. RISC-V의 Ztso 확장은 이런 아키텍처용으로 짠 코드를 옮기기 쉽게 하려고, RVWMO보다 강한 RVTSO 모델을 정의합니다. RVTSO에서는 모든 읽기가 acquire, 모든 쓰기가 release 표시를 붙인 것처럼 동작하므로, 순서를 맞추려고 넣던 장벽 대부분이 필요 없어집니다.

그런데 규격은 입출력용이 아닌 장벽 가운데 앞선 쓰기(PW)와 뒤의 읽기(SR)를 함께 지정한 장벽만은 RVTSO에서도 필요 없어지지 않는다고 밝힙니다. 쓰기 뒤에 오는 다른 주소의 읽기는 TSO에서도 순서가 지켜지지 않는다는 뜻이고, 이 글의 예가 바로 그 순서이므로 TSO에서도 그 자리에 장벽이 있어야 (0, 0)을 막을 수 있습니다. 규격은 또 RVWMO와 RVTSO 모두에서 하드웨어 스레드가 자기 저장 버퍼의 값을, 다른 하드웨어 스레드에게 보이기 전에 뒤의 읽기로 먼저 가져올 수 있다고 설명합니다.

Ztso는 새 명령어를 더하지 않지만, RVTSO를 가정하고 짠 코드는 Ztso를 지원하지 않는 구현에서 올바르게 실행되지 않습니다. 그래서 규격은 Ztso에서만 실행되도록 컴파일한 바이너리에 그 사실을 표시해 두어, 지원하지 않는 플랫폼이 실행을 거부할 수 있게 하라고 권합니다.

정리

• 리트머스 테스트는 짧은 동시 실행 예에서 어떤 결과가 가능한지를 묻는 방법이며, 여기서는 두 코어가 모두 0을 읽을 수 있는지를 물었습니다.
• 순차 일관성은 모든 연산을 프로그램 순서를 지키며 한 줄로 세우는 모델이고, 이 예에서 (0, 0)을 허락하지 않습니다.
• 저장 버퍼가 있으면 쓰기가 다른 코어에게 보이는 시점이 늦어져, 두 읽기가 모두 옛 값 0을 읽는 결과가 가능해집니다.
• 공유 메모리의 최종 값이 맞추어져도 이미 읽은 값은 바뀌지 않으므로, 위치마다 값을 맞추는 일과 여러 위치의 순서는 다른 문제입니다.
• 장벽은 정한 두 연산 사이의 순서를 지키게 하므로 필요한 코어의 필요한 자리에 두어야 하며, 읽기와 쓰기를 원자적으로 만들지는 않습니다.

연습 문제

1. 한 코어만 기다리면

코어 A에서만 X의 반영이 AR보다 먼저 일어나야 하고, 코어 B는 Y의 반영을 기다리지 않고 X를 읽을 수 있습니다. (0, 0)이 나오는 사건 순서를 하나 쓰세요. 실행이 끝난 뒤 X = Y = 1이라는 사실이 rA와 rB도 1이라는 뜻인가요?

2. 순서의 수 세기

저장 버퍼 모델에서 장벽이 없을 때 가능한 순서가 80가지인 이유를, A의 세 사건이 놓일 자리를 고르는 방법부터 시작해 설명하세요.

3. 장벽이 있어도 틀리는 경우

두 코어가 공유 변수 C를 읽고 1을 더해 다시 쓰는데, 각 코어의 읽기와 쓰기 사이에 장벽을 넣었습니다. 갱신 손실을 막을 수 있나요?

메모리 순서 문제를 풀 때는 쓰기를 내놓는 사건과 다른 코어에게 보이게 되는 사건을 나누어 적고, 각 읽기가 그 시점에 어느 값을 볼 수 있는지 따져 보세요. 다음 글 성능 계산과 종합 추적에서는 지금까지 다룬 내용을 성능을 계산하고 비교하는 방법으로 묶습니다.