한 달 동안 묵혀둔 글을 이제야 반 정도 정리 하고 올린다. 경고: 저는 TM을 전공하는 사람이 아니라 내용에 오류가 있을 수 있습니다. 여러 개념을 나름대로 최대한 정확하게 설명하려고 노력했으나 틀릴 수도 있습니다.

1. 트랜잭셔널 메모리의 개념

멀티스레드 및 병렬 프로그래밍이 어려운 이유는 여러 가지가 있겠지만 큰 이유 중 하나로 뮤텍스, 세마포어, 그리고 크리티컬 섹션으로 대표되는 락(lock)에 있다. 여러 스레드가 접근할 수 있는 자료는 락을 보호를 해야만 프로그램의 정확성을 어느 정도¹⁾ 보장할 수 있다. 그런데 락을 빼먹거나 그러면 버그가 나기 십상이고 이런 버그는 잡기가 매우 어렵다. 또, 락은 우선순위 역전 현상, 데드락, 락 콘보이 같은 많은 문제를 만들어 낸다.

그런데 락을 가지고 멀티스레드 프로그램을 정확하게 짜는 것도 어렵지만, 높은 성능을 내도록 짜는 건 더 어렵다. 특히 락은 확장성(scalability)에 많은 문제를 가지고 있다. 점점 프로세서의 코어는 많아 지는데 많은 스레드가 락을 놓고 경쟁을 벌리는 것은 성능을 저하시킨다. 그래서 락-프리(lock-free) 자료구조 같은 것이 대안으로 제시되고 있고 실제 성능도 훌륭하다. 그런데 이 락-프리는 현재 CPU의 지원으로는 뮤텍스처럼 일반화 할 수 없다. 각 자료구조 타입에 따라 특화 해야 하고 어떤 경우는 하드웨어의 제약(한번에 데이터를 atomic하게 교환할 수 있는 양이 제한적)으로 모든 연산을 락-프리로 만들 수 없다.

그래서 이런 문제를 해결하는 방법으로 1993년에 Herlihy 교수는 Transactional Memory (이하 TM)을 제안한다. 트랜잭션은 DB에서 볼 수 있는 바로 그 개념. 여러 단계의 작업을 한번에 처리 되는 것처럼 보이게 하는 것이다. 이걸 기본 CPU 명령어로 지원한다면 훨씬 쉬운 병렬 프로그래밍을 할 수 있다. TM으로 간단히 될 수 있는 대표적인 코드 예를 살펴보자²⁾.

void TransferValue(FIFO Q1, FIFO Q2) {
  Q1.lock.acquire();
  Q2.lock.acquire();
  v = Q1.dequeue();
  Q2.enqueue(v);
  Q2.lock.release();
  Q1.lock.release();
}

FIFO(피포가 아니라 파이포라고 읽습니다) 형태의 큐가 두 개 있다. Q1에서 값을 하나 뽑아 Q2로 옮기는데 이 작업을 원자적으로³⁾ 하고 싶다. 그러면 어쩔 수 없이 위 코드처럼 만들 수 밖에 없다. 아무리 큐 자체가 락-프리로 구현되어 deque/enque를 원자적으로 할 수 있다 하더라도, 이런 작업 같은 것은 어쩔 수 없이 락을 직접 쓸 수 밖에 없다. 그런데 결정적으로 이 코드는 데드락에 빠질 수 있다(이것은 연습 문제로 남깁니다 :-).

그렇다면 TM이 있다면 위 코드가 어떻게 바뀔까?

void TransferValue(FIFO Q1, FIFO Q2) {
  atomic {
    v = Q1.dequeue();
    Q2.enqueue();
  }
}

프로그래머가 의도한 “두 큐의 값을 원자적으로 전달하기” 딱 이것만 기술하고 나머지는 atomic이라는 마법과 같은 구문으로 묶는다. 그러면 프로세서나 컴파일러, 혹은 이 둘이 알아서 해결 해준다. 당연히 데드락 문제는 사라진다. 어떠한가? 정말 이렇게 될 수 있다면 얼마나 프로그래밍 하기 편할까!!!

트랜잭션의 개념을 좀 더 정확히 정의해보자. 앞서 언급했듯이 트랜잭션의 기본 개념은 데이터베이스에서 가져온 것이다. 트랜잭션은 다음과 같은 두 성질을 만족 시켜야 한다.

1. 원자성(Atomicity): 모두 수행하거나 아니면 아무것도 수행하지 않거나(All-or-Nothing),
2. 직렬성(Serializability): 한번에 하나씩 수행되어 그 순서를 정할 수 있음(사실 이 개념을 정확히 이해하려면 좀 더 공부를 해야 함).

다만 데이터베이스와 좀 다른 점은 이런 작업이 디스크가 아니라 메모리에서 일어나고 보통 트랜잭션의 크기가 짧다는 점도 들 수 있다. 그러나 핵심인 원자성과 직렬성은 보장이 된다.

TM이 가지는 장점을 좀 더 설명하면…

TM이 가지는 의미는 단순히 이것 뿐만이 아니다. 첫 번째 락으로 짠 코드는 비록 스레드가 하나만 있더라도 항상 락을 잡고 놓는 과정이 필요하다. 즉 최악의 상황을 가정하고 늘 락을 잡는다. 실제로는 99.9% 시간 동안 한 스레드만이 이 코드를 실행한다 하더라도 어쩔 수가 없다. 정말 불필요한 오버헤드다. 그런데 TM은 그렇지 않다. 키워드 atomic으로 묶인 부분은 (개념적으로, 실제 구현은 이렇게 간단하지 않음) 메모리 변화를 잠시 버퍼링 하였다가 TM 영역이 끝나는 지점에서 한방에 메모리를 변화시킨다. 그래서 다른 경쟁하는 스레드가 없다면 추가로 발생하는 오버헤드가 크게 줄어들 것이다. 물론 이건 하드웨어 수준에서 지원이 있어야만 한다.

좀 더 기초적인 이야기를 해보자. 락으로 보호된 코드 영역(크리티컬 섹션=임계영역)이 수 많은 스레드에 의해 실행된다 생각해보자. 그렇다면 이 임계 영역을 한 스레드가 수행하는 동안 다른 스레드는 기다리고 있어야 한다. 이 때, 이 락이 busy-waiting/spin-lock 구현이 아니라면 락을 잡지 못한 스레드들은 CPU를 사용하지 않고 잠을 잔다(=운영체제가 스케쥴링하지 않는다). 그리고 나중에 락이 풀리면 이 락을 기다리던 스레드들이 깨어나서 서로 경쟁해 누군가가 락을 잡는다. 여기서 또 락을 못 잡은 녀석은 잠을 자야만 한다.

그런데 이렇게 잠자고 깨어나는 것은 매우 큰 오버헤드를 가진다. 단순히 유저-커널 레벨 전환 뿐만 아니라 CPU 사용률 자체를 떨어뜨린다. 운영체제의 스레드 스케쥴링 단위는 밀리세컨드(ms, 1/1,000초) 단위로 프로세서가 데이터를 처리하는 기가 헤르즈와(1/1,000,000,000초)는 엄청난 시간의 차이다. 그래서 실제로 뮤텍스로 보호된 큐에 여러 스레드가 매우 바삐 접근하도록 시키면, CPU 사용률이 희한하게 100%가 되지 않고 적당한 수준에서 머물게 됨을 볼 수 있다. 많은 시간을 스레드가 잠자고 깨어나서 정신차리는데 시간을 허비하기 때문이다. 물론, 대안으로 스핀 락으로 이런 비용을 줄일 수는 있다. 그러나 역시 이상적이지 못하다. TM은 이 문제를 해결할 수 있다.

2. 그럼 이거 쓸 수 있는 건가요?

이 정도면 락이 왜 지랄 같은지 TM이 왜 끝내주는지(그러나 결코 TM이 만병 통치약이 아니다. 절대 오해 말 것!)는 잘 알 것이다. 그렇다면 도대체 이거 지금 쓸 수 있는 겁니까?

안타깝게도 지금 당장 실용적으로 TM을 쓸 수는 없다. 1993년에 최초로 TM 논문이 나온 이후 무수히 많은 사람들이 이것을 가지고 연구했고 지금도 매우 뜨거운 분야다. TM은 그 구현 방법에 따라 크게 몇 가지 방법으로 나뉘는데, 최근 가시적인 성과가 보이기 시작했다. 사실 이 포스팅을 쓰게 된 동기는 아래의 두 결과를 여러분들에게 알리고 싶어서 쓰려고 했다. 그런데 일단 TM의 개념부터 정확하게 알아야 하기 때문에 정작 하고 싶은 이야기는 다음에 –_-;

• Sun에서 최초로 TM(여러 TM 구현 방법 중 Best-effort Hardware TM)을 구현한 프로세서의 성능을 올 해 발표하였다. 아직 갈 길이 멀지만 어쨌든 상당히 희망을 가질 수 있다. 논문은 여기서.
  
• AMD에서 한달 전, 최초로 x86에서 ASF, Advanced Synchronization Facility라는 역시 Sun의 방식과 비슷한 Best-effort HTM을 지원할 수 있는 명령어 집합을 제안하였다. 아직까지 구현한 것은 아니고 단순히 이런 명령어로 만들면 어떨까라는 제안을 한 것이다.

이 두 결과에 대한 자세한 이야기와 지금까지 제안된 TM의 구현 방법에 대해서는 나중에…

일단 결론

앞으로 5년 내에 정말 가시적인 변화가 올 것 같다. 정말 꿈에도 그리던, 락 사용을 최소화 할 수 있는 그런 프로그램을 만들 수 있다. 5년은 좀 짧다면, 10년 내에는 분명히 바뀔 것이다. 아무리 프로세서가 병렬로 가더라도 그걸 제대로 활용하지 못하면 무용지물이다. 그래서 병렬 프로그래밍을 쉽게 할 수 있도록 하드웨어에서 많은 지원을 해야만 한다. 위 두 결과물이 바로 대표적인 예이다.

이 모든 노력은 어떻게 하면 프로그래머에게 고생을 덜 시키고 더 훌륭한 프로그램을 만들게 할 수 있을까라는 고민에서 나온 것이다. 아주 과거 프로그래머들은 기계어를 모르고서는 빠르게 작동하는 프로그램을 만들 수 없었다. 그런데 프로세서가 워낙에 빨라지고 컴파일러 최적화가 뛰어나다 보니, 대부분의 경우 이런 걸 몰라도 된다. 지금은 멀티 스레드 프로그래밍을 하려면 공부해야 할 것이 넘쳐 난다. 그런데 또 이렇게 기술의 발전으로 이런 고민을 들 수 있게 된다. 분명 바람직한 일이지만 역시 프로그래머는 대충 해도 되는 직업??!!

한 줄 요약: 멀티스레드 프로그래밍을 좀 더 (혹은 매우) 쉽게 해주는 TM이라는 게 곧 실용화 될 것 같다.

1) 락으로 공유 데이터를 보호하면 데이터 레이스(data race)는 해결할 수 있다. 그러나 데이터 레이스의 없음이 곧 프로그램의 정확성을 뜻 하는 것이 아니다. 정확한 멀티스레드 프로그램과 데이터 레이스의 없음은 필요 관계도 충분 관계도 아니다. 그래서 좀 더 근원적인 개념으로 atomicity라는 개념이 있다(위에서 트랜잭션의 개념으로 설명한 atomicity와는 다르다). 이 개념은 많은 사람들이 정확한 멀티스레드 프로그램이 가져야 할 기본적인 개념으로 생각한다. 어떤 코드가 atomicity를 가지고 있다라는 뜻은 이 코드가 여러 스레드에 의해 어떠한 조합으로 실행이 되더라도(interleaving), 이 실행 결과와 동일한 결과를 만들어 내는 직렬 실행을 찾을 수 있음을 말한다(우왕 진짜 말로만 설명하려니 넘 어렵다) 그래서 아무리 TM이 실용화되어 뮤텍스를 다 없앨 수 있어도 여전히 멀티스레드 버그는 발생한다. Atomicity 개념에 대해 더욱 자세히 알고 싶으면 두 논문(1, 2)을 읽으면 된다. 병렬 프로그래밍에 관심 있는 분이라면 꼭 읽어 보실 것을 강력 추천.

2) 이제는 오라클이 된 Sun의 Mark Moir 박사의 강연에서 참고.

3) Atomicity, atomicitly의 번역을 원자성, 원자적으로 하는 것이 좀 우스꽝스럽지만 이 보다 더 정확한 표현을 찾기 힘들다. 실제 물리학에서는 원자가 더 작은 단위로 쪼개지지만 보통 원자는 더 쪼개질 수 없는 의미로 쓰이기 때문에 원자라는 단어를 직역해 쓰는 것이 적절해 보인다.