순차일관성(sequential consitency)이란?

순차일관성은 컴퓨터 시스템에 관한 메모리 일관성 모델의 하나이며 정의를 Wikipedia에서 인용하면 “어떤 실행 결과도 모든 프로세서가 어떤 순서로 차례적으로 실행한 결과와 동일하며, 또한 각각의 프로세서의 처리 순서가 프로그램에서 한 대로다”라고 한다.

병렬 처리 중인 실행 결과가 항상 순차적으로 실행한 경우와 동등하다는 것이다.

예를 들면 다음과 같은 코드가 있다며

std::atomic<int> X(0), Y(0);
int r1, r2;

void thread1()
{
    X.store(1);
    r1 = Y.load();
}

void thread2()
{
    Y.store(1);
    r2 = X.load();
}

어떤 실행 결과라도 모든 프로세서가 어떤 순서로 순차적으로 실행한 결과와 같다 라는 것은 X와 Y의 결과가 {X, Y}={0, 1}, {1, 0}, {1, 1} 중 하나일 수 있으나 {0,0}은 논리적으로 일어날 수 없고 일어나서는 안 된다는 것이다.

각각의 프로세서의 처리 순서가 프로그램에서 지정된 대로다는 예를 들면 thread1 이라면 X.store(1) 와 r1=Y.load()의 실행 순서가 서로 바뀌지 않는다.
너무나 당연한 것 같지만 멀티 코어 환경에서는 순차일관성이 충족되지 않는 것이 많다.

리오더링(reordering)

멀티 코어 환경에서는 반드시 메모리 조작이 순서대로 이루어지지 않는다.

x = A;
y = B;

프로세서가 A와 B라는 값을 취득할 경우, A는 프로세서의 캐시에 존재하지 않고, B가 프로세서의 캐시에 존재했을 경우에는 실행 결과의 취득하는 타이밍이 바뀐다.

물론 A의 결과가 반환되는 것을 기다렸다가 B의 결과를 취득해도 좋지만 기다리는만큼 성능이 떨어지게 되므로 꼭 기다리는 것이 적절하다고 할 수 없다.

이처럼 상황에 따라서 명령 실행 순서가 바뀌는 것을 리오더링(reordering)라고 한다.

x86 메모리 모델에서의 리오더링

x86 메모리 모델에서는 TSO(total-store order model)를 지키고 있다.
TSO는 “load 끼리는 순서를 지키다. store 끼리는 순서를 지키고, store는 load를 추월하지 않는다.”라는 규칙이며, 동일 프로세서 내에서 순서일관성(processor consistency)은 유지되지만 멀티 프로세서에서는 명령 순서가 보장되지 않고 쓰기 직후에 읽기 명령을 내려도 최신의 것을 취득할 수 있다고는 할 수 없다.

아래는 이전에 나타낸 코드지만 멀티 프로세스 환경에서는 X.store와 Y.store가 메모리에 반영되기 전에 X.load와 Y.load 양쪽이 실행되고 r1=0, r2=0 이 될 수 있기에 따라서 이대로는 순차일관성이 없다는 것이다.

std::atomic<int> X(0), Y(0);
int r1, r2;

void thread1()
{
    X.store(1);
    r1 = Y.load();
}

void thread2()
{
    Y.store(1);
    r2 = X.load();
}

메모리 바리어

메모리 리오더링을 피하기 위한 방법으로 메모리 바리어(메모리 펜스)과 깨지는 메모리 조작 순서성을 제한하는 CPU 명령이 있다.

고 수준 언어에서는 메모리 바리어를 사용하여 구현되는 동기 프리미티브(synchronization primitive)를 사용하여 동기 처리를 구현하게 된다. 동기 프리미티브는 mutex나 세마포어 등의 병렬 실행을 위한 구조이다.

정리

• 순차일관성이란 “어떤 실행 결과도 모든 프로세서가 어떤 순서로 차례적으로 실행한 결과와 동일하며, 또한 각각의 프로세서의 처리 순서가 프로그램에서 지정한 대로이다”.
• 멀티 프로세스 환경에서는 리오더링에 의해 순차일관성이 유지되지 않을 경우가 존재한다.
• 리오더링을 막기 위해서 메모리 바리어를 이용한다.
• 메모리 바리어는 CPU 명령이고, mutex나 세마포어 등의 구현에 사용되고 있다

참고 http://tuning.hatenadiary.jp/entry/2014/12/30/032512