비순차적 명령어 처리 Out of Order Execution (OoOE)
멀티스레드 프로그래밍에서는 코드가 정확하고, 디스어셈블리로 봐도 아무런 문제가 없는 프로그램일 지라도 아주 낮은 확률로 예기치 않은 동작을 하며, 이는 반드시 버그로 이어진다.
#pragma region 피터슨의 알고리즘
volatile int g_victim = 0;
volatile bool g_flags[2] = {false, false};
void Lock(int myId)
{
int otherId = 1 - myId;
g_flags[myId] = true;
g_victim = myId;
while(g_flags[otherId] && g_victim == myId) {}
}
void Unlock(int myId)
{
g_flags[myId] = false;
}
#pragma endregion
위 소스코드는 가장 단순한 Lock알고리즘으로 알려진 피터슨의 알고리즘의 구현이다.
Lock(...)메서드를 이용해 현재 스레드 아이디로 잠금을 걸면 다른 스레드는 희생자(victim)가 되어 입계지점에 진입하지 못하고 while문 안에서 대기하게 된다.
앞 장인 데이터 레이스에서는 C++11의 mutex를 사용했을때는 결과는 정상적이었으나 엄청난 오버헤드를 발생시켰다. 따라서 위와 같이 간단한 Lock알고리즘이라면 적은 오버헤드로 원하는 결과를 출력하는 프로그램을 만들 수 있을지도 모른다.
원본 소스코드
#include <iostream>
#include <vector>
#include <chrono>
#include <thread>
using namespace std;
using namespace chrono;
volatile int g_sum = 0;
#pragma region 피터슨의 알고리즘
volatile int g_victim = 0;
volatile bool g_flags[2] = {false, false};
void Lock(int myId)
{
int otherId = 1 - myId;
g_flags[myId] = true;
g_victim = myId;
while(g_flags[otherId] && g_victim == myId) {}
}
void Unlock(int myId)
{
g_flags[myId] = false;
}
#pragma endregion
void threadFunc(int threadId)
{
for(int i = 0; i < 25000000; ++i)
{
Lock(threadId);
g_sum += 2;
Unlock(threadId);
}
}
void main()
{
auto startTime = high_resolution_clock::now();
thread t1 = thread{threadFunc, 0};
thread t2 = thread{threadFunc, 1};
t1.join();
t2.join();
auto deltaTime = high_resolution_clock::now() - startTime;
cout << 2 << "Threads.\t" << duration_cast<milliseconds>(deltaTime).count() << "ms\tSum = " << g_sum << endl;
getchar();
}
피터슨락을 적용한 전체 소스코드이다. 간단한 실험을 위해 2장에서 사용했던 소스코드를 2스레드 전용으로 변경하였을 뿐 기본은 동일하나 실행 결과는 1억이 출력되지 않았다.
1억보다 146이 모자라는 결과가 나왔다. 이것은 데이터 레이스로 발생하는 현상과는 다르다. 2Thread 상황에서 데이터 레이스가 발생한다면 1억의 절반인 5천이 조금 넘는 숫자가 나왔을 것이다. 그렇다면 피터슨 알고리즘의 코드에 버그가 있는 것일까?
원인 분석
비순차적 명령어 처리(Out of order execution, OoOE)는 CPU에서 특정 작업이 지연됨에 따라 낭비될 수 있는 명렁 사이클을 이용하기 위한 방식이다. 말 그대로 명령어를 순서대로 처리하지 않는다. 이러한 행동이 어떻게 성능 향상으로 이어질 수 있는지에 대해 다음 설명을 보자.
값 A는 CPU의 캐시에 있고, 값 B는 없어서 메모리를 읽어와야 하는 상황일 때
var c = B;
var d = A;
위와 같은 코드를 만난다면 어떻게 처리하는게 더욱 효과적일까?
순차적 처리
- 값 B를 캐시에서 찾음
- 캐시 미스가 발생하고 값 B를 메모리에서 읽어 옴
- 값 c를 할당한 뒤, 메모리에서 읽어 온 값 B로 초기화 (이 과정에서 값 A가 캐시에서 사라짐)
- 값 A를 캐시에서 찾음
- 캐시 미스가 발생하고 값 A를 메모리에서 읽어 옴
- 값 d를 할당한 뒤, 메모리에서 읽어 온 값 A로 초기화
비순차적 처리
- 값 B가 필요한 코드를 만났지만 캐시 미스라 일단 대기
- 값 A가 필요한 코드를 만났고 캐시 히트
- 값 d를 할당한 뒤, 캐시 히트한 A로 초기화
- 값 B를 메모리에성 읽어 옴
- 값 c를 할당한 뒤, 메모리에서 읽어 온 값 B로 초기화
답은 당연히 2번이다. 순차적으로 처리하였을 경우라면 두 번의 메모리 IO가 발생하지만 순서를 바꾸는 것만으로 한번에 해결할 수 있다.
이 OoOE 때문에 Lock(...)메서드 while문에서 조건으로 사용되는 g_flags[otherId]값은 아주 가끔씩 g_flags[myId] = true;로 갱신되기 이전의 값일 수 있으며 그 결과 버그가 된다.
mfence를 사용한 문제 해결
우리가 앞서 컴파일러의 최적화를 무시하기 위해 volatile키워드를 사용했었다. 이 경우에도 CPU 최적화를 막을 수 있는 방법이 존재한다.
void Lock(int myId)
{
int otherId = 1 - myId;
g_flags[myId] = true;
g_victim = myId;
_asm mfence;
while(g_flags[otherId] && g_victim == myId) {}
}
위와 같이 CPU가 OoOE를 하지 못하도록 fence를 쳐 주면 된다.
기존 코드의 디스어셈블리
어셈블리가 익숙한 독자라면 byte ptr[eax+107549Ch]라는 주소 공간이 g_flags[myId]라는 것을 발견할 수 있을것이다. 여기에 1을 대입한 뒤, cmp문을 사용해 byte ptr [eax+107549Ch]의 값과 0을 비교하고 있는데 이 부분이 while문의 조건이다.
데이터 레이스 문제에서 volatile로 문제를 해결했을 때에는 디스어셈블리로 보면 버그가 확인되었지만 OoOE는 디스어셈블리로 문제의 원인을 확인하는것이 불가능하다.
_asm mfence가 추가된 디스어셈블리
_asm mfence를 추가하면 디스어셈블리에서 바로 볼 수 있다. 이 키워드로 인해 CPU는 이 경계를 넘나들며 OoOE 최적화를 하지 않는다.
실행 결과는 매우 만족스럽다. mutex (2Threads 11539ms)를 사용했을 때 보다는 월등히 빠르며, 큰 의미를 가지지는 않지만 _asm Atomic (2Threads 942ms)을 사용했을 때보다도 근소하게 빨리 결과가 출력되었다.
이렇듯 멀티스레드 프로그래밍은 프로그래머에게 프로그래밍 뿐만 아니라 컴파일러, CPU의 아키텍쳐 등 폭 넓은 학습을 강요하여 진입장벽을 높힌다. 그러나 CPU의 성장이 둔화되고 멀티코어로 발전하게 된 지금, 하드웨어의 성능을 충분히 끌어낼 수 있는 멀티스래드 프로그래밍은 앞으로 더욱 중요해 질 것이다.
조금 더 알아보기 - 1
C++11에서는 멀티스레드 프로그래밍에 필요한 내용들이 대거 표준으로 등제되었다.
위와같은 OoOE문제도 _asm블록을 사용하지 않고 C++11만으로도 프로그래밍 할 수 있다.
// C++11 atomic 을 사용한 경우
// #include <atomic>
void Lock(int myId)
{
int otherId = 1 - myId;
g_flags[myId] = true;
g_victim = myId;
atomic_thread_fence(std::memory_order_seq_cst);
while(g_flags[otherId] && g_victim == myId) {}
}
직접 실행해보면 결과는 정확하게 출력되나 _asm mfence보다 다소 느린것을 확인할 수 있다. 이는 C++11이 정식으로 멀티스레드 프로그래밍을 지원하기 시작한지 얼마 되지 않아 최적화가 덜 되었기 때문으로 생각된다.
아직도 실행성능이 중요한 프로그램에서 C++은 가장 먼저 고려되는 언어이다. 하물며 멀티스레드 프로그래밍을 정식으로 지원하며 최신 프로그래밍 페러다임을 모두 섭렵해가는 Modern C++의 미래에 귀추가 주목된다.
조금 더 알아보기 - 2
피터슨의 알고리즘 예에서는 결과적으로 OoOE가 발생하였고 그것을 막는 과정을 보여주었다. 그러나 OoOE를 눈으로 확인할 수 있는 방법은 없을까? 다음 예제 프로그램으로 OoOE가 얼마나 발생하는지 확인할 수 있다.
#include <iostream>
#include <thread>
using namespace std;
const int SIZE = 100000000;
volatile int x, y;
int x_log[SIZE], y_log[SIZE];
void x_up_thread()
{
for(int i = 0; i < SIZE; ++i)
{
x = i;
y_log[i] = y;
}
}
void y_up_thread()
{
for(int i = 0; i < SIZE; ++i)
{
y = i;
x_log[i] = x;
}
}
void main()
{
thread t1 = thread{x_up_thread};
thread t2 = thread{y_up_thread};
t1.join();
t2.join();
int OoOECount = 0;
for(int i = 0; i < SIZE; ++i)
{
if(x_log[i] == x_log[i + 1] && y_log[x_log[i]] == y_log[x_log[i] + 1])
{
if(y_log[x_log[i]] == i)
++OoOECount;
}
}
cout << "메모리 불일치 횟수: " << OoOECount << endl;
getchar();
}
위 프로그램은 짧지만 얼핏 이해하기 어려운 부분이 존재한다. 이해를 돕기 위해 그림을 준비했다.
x_up_thread()에서는 x값을 0부터 1억(SIZE)까지 증가시키며 그와 동시에 y의 i번째 값이 무엇인지 기록한다.
y_up_thread()의 동작도 마찬가지로 y값을 0부터 1억까지 증가시키며 그와 동시에 x의 i번째 값이 무엇인지 기록한다.
위 그림에서는 x_log[i]의 값이 이미 기록된 상태로 표현했만 이는 이해를 돕기 위함이며 실제와는 다르다. 실제로는 어떤 스레드의 함수가 먼저 처리될지 전혀 예측할 수 없다.
이제 main()함수에서 처리되는 내용을 살펴보자. 왼쪽이 x_log의 내용, 오른쪽이 y_log의 내용이다.
이미 알고있겠지만 멀티스레드 프로그램에서는 어떤 스래드가 얼마나 여러번 처리될지 예측할 수 없다. 따라서 y_up_thread()가 여러번 처리되는 경우도 있을 수 있으며, x_log[i]와 그 다음 값이 같은 경우가 존재할 수 있다.
위 그림에서는 x_log[1]의 값과 그 다음 값이 2로 같았다. 이 값을 인덱스로 y_log[2]와 그 다음 값을 살펴보면 같지 않았다. 이 경우 OoOE가 발생하지 않은 경우이다.
다른 경우로 예를들어보자.
- i값이 2일 때
- x_log[2]와 그 다음 값이 5로 같다.
- y_log[5]와 그 다음 값이 2로 같다.
먼저 왼쪽의 x_log를 살펴보면 y값이 6이 되기 전에 x_log[3]이 기록되었다. 이는 x_log[3]이 5인것으로 확인할 수 있다. 이 순간 y값을 알 수 있는 y_log[x_log[2]]를 살펴보면 이 때의 y값은 2였다고 한다. 여기까지는 문제 없다.
위 그림은 이해를 돕기위한 얘시로 실제와 다를 수 있으나 x_log들의 값이 순차적이지 않는것은 실제로 발생할 수 있는 경우이다.
그러나 그 다음인 y_log[6]의 값이 2가 되려면 적어도 x_log[3]은 이미 6보다 같거나 커야 한다. 해당 시점보다 미래이기 때문이다. 만약 y_log[6]도 2라면 그것은 스레드 안에서 명령의 순서가 뒤바뀐 OoOE가 발생한 경우이다. 프로그램의 실행 결과는 다음과 같다.
2개의 스레드로 1억번을 수행했을 경우 787회 발생하였다면 확률로는 고작 0.000787% 이다. 이러한 내용을 고려하지 않고 멀티스레드 프로그램을 만들었다면 재현조차 어려운 악성 버그의 쓴맛을 보게될 것이다.