Atomic Operations
From DevNote
Contents |
Atomic Operation의 정의
Atomic operation은 다음과 같은 상태를 만족하여야 한다.[1]
- 일련의 모든 연산이 끝날 때까지 다른 프로세스는 그 연산에 따른 어떠한 변화도 알 수 없다.
- 전체 연산 중 어느 하나라도 실패할 경우 모든 연산은 실패하며 시스템은 전체 연산이 시작하기 전의 상태로 복구된다.
이것은 Atomic operation의 일반적인 정의이며, 여기서 우리가 관심을 가지고 알아보고자 하는 것은 CPU가 지원하는 Instruction 중에 Atomic한 것들이다. 특히, 멀티스레드 프로그래밍에서 Atomic operation은 스레드나 프로세스간의 동기화를 위한 Lock을 사용하지 않아도 되기 때문에 프로그램의 효율성과 속도를 높일수 있다는 점에서 매우 중요하다. 최근에 개발된 대부분의 CPU는 몇가지 Atomic operation을 지원한다. 내부적으로는 윈도우가 지원하는 Lock도 이러한 CPU의 Atomic operation을 사용한다. 이에 관해서는 나중에 설명할 Spinlock에서 자세히 다루겠다.
Atomic Operation의 필요성
멀티스레드 프로그램에서 여러 스레드간 공유되는 리소스들은, 여러 스레드가 서로 동시에 액세스 하는 이른바 레이스 컨디션(race condition)을 막기 위해 보통 lock을 사용합니다. (윈도우즈의 경우 Critical Section). 이러한 각 리소스 간의 동기화(synchronization) 문제는 오래 전부터 연구되어 왔으며, 최근에는 하드웨어에서 지원되는 Atomic operation의 개발로 많은 문제가 해결되고 있으며 lock-free 알고리즘이나 자료구조를 위한 툴로 가장 많이 사용되고 있다.
IA-32에서의 Atomic Operation
32비트 인텔 CPU (IA-32)에서 지원되는 Atomic Operation에 관해 알아보자. 다음과 같은 인텔의 CPU 연산들 앞에 LOCK을 붙여 해당 연산을 Atomic하게 만들 수 있다. 즉, 스레드간의 동기화를 신경쓰지 않아도 된다. 자세한 것은 인텔사 웹싸이트에서 제공되는 개발자 매뉴얼을 참고하기 바란다.
ADD, ADC, AND, BTC, BTR, BTS, CMPXCHG, CMPXCH8B, DEC, INC, NEG, NOT, OR, SBB, SUB, XOR, XADD, XCHG.
Atomic Operation 예제
아래 몇가지 Atomic Operation 함수 예제를 각각의 Win32 API와 그에 해당되는 어셈블리코드를 함께 리스트하였다. #ifdef 내부 블럭은 어셈블리 코드이며 #else 부분은 같은 기능을 하는 Win32 API 이다. (Win32의 Atomic operation은 Interlocked로 시작한다).
어셈블리 코드에서 사용된 lock prefix를 주의 깊게 보기 바란다. lock 다음의 연산은 atomicity가 보장되어 다른 스레드와의 동기화를 염려하지 않아도 된다.
먼저, 어떤 변수에 임의의 값을 atomic하게 대입하는 함수를 작성하여 보자. 여기에는 임의의 변수값을 다른값과 교환하는 AtomicExchange가 사용되었다. *value 의 값이 set 값으로 바뀌고 원래 *value 값이 return 값으로 돌아온다. 어셈블리를 보면 lock xchg 가 사용되었다.
다음은 변수 i를 0으로 초기화하는 경우이며, 다른 스레드는 초기화가 진행되는 동안 변수 i를 읽거나 쓸 수 없다.
AtomicExchange(&i, 0);
그렇다면 위의 코드는 아래 크리티컬 섹션을 사용하는 경우와 무엇이 다른가? 결과는 같지만 위의 경우가 CPU에서 지원되는 atomic operation을 사용하므로 단지 변수 하나의 값을 바꾸려는 경우 매우 효율적이다. 윈도우의 크리티컬 섹션은 비교적 효율적으로 만들어져 있으나, 원하는 락을 얻지 못할 경우, 스레드는 대기상태로 전환되고 다른 스레드로 컨텍스트 스위치가 일어나며 이것은 CPU 입장에서 상당한 CPU 싸이클을 사용하는 매우 비싼 작업이다. Atomic Operation은 스레드 컨텍스트 스위치를 발생시키지 않는다.
EnterCriticalSection(&cr); i = 0; LeaveCriticalSection(&cr);
여기서, 많은 개발자들이 Atomic Operation에 관해 잘못 이해하고 있는 부분을 확실하게 짚고 가보자. 아래와 같이 스레드간 공유변수를 1만큼 증가시키는 C 코드는 Atomic할까? 간단해 보이는 이 문장하나는 실제 CPU 입장에서는 read, modify, write라는 3단계를 거치게 된다. 굳이 멀티프로세서가 아닌 하나의 CPU상에서도 이 세단계의 어느 과정 중에서도 다른 스레드로 컨텍스트 스위치가 일어날 수 있으며, 이경우 결과는 예측할 수가 없다. 즉, 스레드 A가 1단계를 거처 g_count의 값을 읽어온 다음 스레드 B가 다시 같은 g_count의 값을 읽어 1 증가 시키고 메모리에 쓸 수 있다. 그럼 2만큼 증가되었어야할 g_count는 1밖에 증가되지 못한다.
이러한 단순한 연산도 lock으로 보호되어야만 안전하다. 여기서 AtomicIncrement는 이러한 동기화 문제를 하드웨어적인 로우레벨(low level)에서 해결하여 준다.
g_count++; 1. read g_count -> register0 2. add 1, register0 3. write register0 -> g_count
//---------------------------------------------------------------------------
static inline long AtomicExchange (
volatile long * value,
long set
) {
#if defined(_M_IX86) && defined(INLINE_ASSEMBLY)
_asm {
mov ecx, value
mov eax, set
lock xchg dword ptr [ecx], eax
}
#else
return InterlockedExchange(
(LPLONG)(value),
set
);
#endif
}
다음 AtomicIncrement와 AtomicDecrement는 이름 그대로 파라미터로 전달된 변수의 값을 1씩 증가 혹은 감소시킨다. 어셈블리 코드를 보면, 왜 lock inc와 lock dec를 사용하지 않고 lock xadd를 사용하였는지 의문이 생길 수 있다. 이 이유는 Win32의 Interlocked API의 return 값과 동일하게 만들어 주기 위함이다. 즉, AtomicIncrement는 원래 값보다 1증가된 값을 AtomicDecrement는 1감소된 값을 return 한다.
xadd는 두 operand값을 교환한 후 첫번째 operand에 두 값을 합한 값을 넣는다. 연산이 끝나면 EAX 레지스터에는 포인터 변수의 원래 값이 들어가 있게 되므로 각각 EAX 레지스터를 함수의 값을 1 증가, 1 감소하여 원하는 return 값을 만든다. (EAX 레지스터가 항상 함수의 return 값으로 사용된다)
간단한 사용예는 다음과 같다.
static long i = 0; ... AtomicIncrement(&i); ... AtomicDecrement(&i);
//---------------------------------------------------------------------------
static inline long AtomicIncrement (
volatile long * value
) {
#if defined(_M_IX86) && defined(INLINE_ASSEMBLY)
// do not use 'lock inc' to make return value same as Win32 API
_asm {
mov ecx, value
mov eax, 1
lock xadd dword ptr [ecx], eax
inc eax
}
#else
return InterlockedIncrement((LPLONG)(value));
#endif
}
//---------------------------------------------------------------------------
static inline long AtomicDecrement (
volatile long * value
) {
#if defined(_M_IX86) && defined(INLINE_ASSEMBLY)
_asm {
mov ecx, value
mov eax, -1
lock xadd dword ptr [ecx], eax
dec eax
}
#else
return InterlockedDecrement((LPLONG)(value));
#endif
}
이번에는 임의의 값을 더해주는 AtomicAdd함수이다. 이에 해당하는 Win32 API는 InterlockedExchangeAdd으로 이 Win32 함수는 return 값으로 *value 에 increment 값을 더하기 전 원래 값을 되돌리므로 어셈블리 코드에서도 lock xadd 연산 후에 EAX 레지스터 값을 변경하지 않았다.
//---------------------------------------------------------------------------
static inline long AtomicAdd (
volatile long * value,
long increment
) {
#if defined(_M_IX86) && defined(INLINE_ASSEMBLY)
_asm {
mov ecx, value
mov eax, increment
lock xadd dword ptr [ecx], eax
}
#else
return InterlockedExchangeAdd(
(LPLONG)(value),
increment
);
#endif
}
마지막으로 앞으로 특히 Lock-Free 알고리즘에서 매우 중요하게 사용될 비교후 교환(Compare-And-Swap)에 해당하는 AtomicCompareExchange 함수를 보자. 이 함수는 *value 값이 compare 와 같은 경우에만 set 값으로 교환한다. 마찬가지로 *value의 원래 값이 되돌아 온다. 만약 *value 와 compare 값의 비교 결과가 다른 경우 아무런 연산도 일어 나지 않는다. 이 함수를 호출할때 성공 여부를 알기 위해서는 다음과 같은 방법을 사용할 수 있다.
i 의 값이 0 인 경우에만 i 값을 set 값으로 변경한다고 할때 다음과 같이 AtomicCompareExchange의 리턴값이 0 인지 비교할 수 있다.
if (AtomicCompareExchange(&i, set, 0) == 0) {
// 성공
}
else {
// 실패
}
//---------------------------------------------------------------------------
static inline long AtomicCompareExchange (
volatile long * value,
long set,
long compare
) {
#if defined(_M_IX86) && defined(INLINE_ASSEMBLY)
_asm {
mov ecx, value
mov edx, set
mov eax, compare
lock cmpxchg dword ptr [ecx], edx
}
#else
return (long) InterlockedCompareExchange(
(PVOID *)(value),
(PVOID) (set),
(PVOID) (compare)
);
#endif
}
그런데, 왜 AtomicCompareExchange 가 Lock-Free 알고리즘에서 중요하게 사용되는 것일까? 다음에 물론 자세히 설명하겠지만 여기서 간단히 설명 한다면 다음과 같다. 멀티스레드 프로그램에서 각 스레드간 공유되는 변수들을 읽거나 쓸 때 동기화를 위해 보통 Lock을 사용하여 Critical Section을 만든다. 이렇게 만들어진 Critical Section 은 하나의 스레드만 들어갈 수 있으므로 스레드간 동기화가 이루어진다. 하지만, Lock-Free 의 경우 Lock 을 사용하지 않기 때문에 다른 스레드가 이미 그 변수의 값을 변경했을 가능성있다. 하지만, 그 확률은 대체적으로 낮으므로, 변경되지 않았을 것이라 가정하는 낙관적인(Optimistic) 방법이 Lock-Free에 사용된다. 이 때 AtomicCompareExchange 이용하여 공유변수가 가정하는 값과 같으면 다음 단계로 넘어가고 만약 변경되었다면, 재시도하는 방법을 사용하면 Lock 없는 멀티스레드 프로그래밍이 가능하다.
한가지 예를 들어보겠다. 공유변수 g_x의 값을 xxx값으로 lock-free하게 바꾸는 예제이다.
volatile long g_x; // <-- 스레드간 공유되는 글로벌 변수라 가정
....
void LockFree () {
for (;;) {
volatile long capture = g_x;
...
long old = AtomicCompareExchange(&g_x, xxx, capture);
if (capture != old)
continue;
// 이제 old 에 g_x 가 xxx값으로 바뀌기 바로전 값이 있으므로 이를 이용하여 다른 작업이 가능 합니다.
break;
}
}
