소프트웨어 트랜잭셔널 메모리

소프트웨어 트랜잭셔널 메모리(Software Transactional Memory, STM)는 컴퓨터 과학에서 병렬 컴퓨팅에서 공유 메모리으로의 접근을 제어하기 위한 데이터베이스 트랜잭션과 유사한 동시성 제어 구조이다. 여기에서 트랜잭션은 공유 메모리에 읽기 및 쓰기를 수행하는 코드 조각을 가리킨다. 하나의 트랜잭션 안에서 수행되는 읽기 및 쓰기는 논리적으로 한 순간에 수행되는 것으로 이해할 수 있다. 트랜잭셔널 메모리를 하드웨어적으로 구현하는 아이디어는 1986년 톰 나이트의 논문에서 최초로 제안되었다. 1995년 니르 샤비트와 댄 투이터우는 이 아이디어를 소프트웨어적으로 구현한 소프트웨어 트랜잭셔널 메모리(Software Transactional Memory)를 발표하였다.

성능

현대의 다중 스레드 응용 프로그램에서 사용하는 락(lock)과 달리, 트랜잭셔널 메모리는 보다 낙관적인 전략을 사용한다. 트랜잭셔널 메모리를 사용하는 스레드는, 다른 스레드에서 실행되는 코드가 해당 메모리를 간섭하지 않을 것으로 가정하고 읽기 및 쓰기를 수행하며, 읽기와 쓰기를 수행한 메모리의 주소를 기록한다. 트랜잭션 영역의 수행이 완료되면, 해당 메모리 주소가 다른 스레드에 의해 변경되었는지 검사한다. 만약 변경이 없었다면, 트랜잭션은 올바르게 수행되었으므로 커밋(commit)이 이루어지고, 그렇지 않으면 트랜잭션은 실패한다. 트랜잭션이 실패했을 경우 트랜잭션을 재시도할지, 아니면 취소할지는 프로그래머가 선택할 수 있다. 또한 트랜잭션은 언제든 중간에 취소하여 트랜잭션 수행 이전 상태로 되돌아갈 수 있다.

기존의 락 기법에 비해 트랜잭셔널 메모리의 장점은, 더 많은 스레드가 동시에 수행될 수 있다는 것이다. 락이 해제되길 기다리며 대기하는 스레드가 없고, 충돌이 일어나지 않으면 모든 스레드가 자신의 코드 영역을 안전하게 수행할 수 있다.

그러나, 트랜잭셔널 메모리는 읽기 및 쓰기를 수행한 메모리 주소를 기록하는 오버헤드로 인해 약간의 성능 저하가 존재한다. 소프트웨어적으로 구현한 트랜잭셔널 메모리의 경우 이 오버헤드가 큰 편이다.

개념상의 장단점

트랜잭셔널 메모리를 사용하면 다중 스레드 프로그램을 훨씬 간단한 구조로 만들고, 여러 개의 객체 및 모듈을 안전하게 결합할 수 있다. 락 기반의 다중 스레드 프로그램에는 다음과 같은 문제들이 있다.

• 개념적으로 멀리 떨어진 것처럼 보이는 코드 사이의 상호작용에 대해 고려해야 한다.
• 교착 상태에 빠지는 것을 막기 위한 정책을 신중하게 설계하고 따라야 한다.
• 우선순위가 높은 스레드가 낮은 스레드의 락을 오랫동안 대기하여 충분한 연산시간을 얻지 못하는 우선순위 역전이 일어날 수 있다.

위의 세 가지 문제는 모두 버그를 일으키기 쉽고, 찾아내기 어려운 것으로 악명이 높다.

반면 트랜잭셔널 메모리는 각각의 스레드가 독립적으로 작동하는 스레드와 논리적으로 동일하기 때문에, 위와 같은 문제를 걱정할 필요가 없다. 교착 상태는 완전히 사라지거나, 혹은 트랜잭션 관리자에 의해 해결된다. 우선순위 역전 문제는 여전히 일어날 수 있지만, 우선순위가 높은 스레드는 높은 확률로 낮은 우선순위 스레드의 트랜잭션을 취소시킬 수 있으므로 상대적으로 적게 일어날 것이다.

반면 트랜잭셔널 메모리의 단점은, 트랜잭션이 실패할 경우 언제든 취소할 수 있어야 하기 때문에, 취소할 수 없는 작업은 트랜잭션 안에서 수행할 수 없다. 이것은 대부분의 입출력을 수행할 수 없다는 것을 의미한다. 이런 문제는 대체로 취소할 수 없는 작업을 버퍼에 담아두고 실제 작업은 트랜잭션 바깥에서 수행하는 방법으로 대부분 해결할 수 있다. 하스켈에서 구현된 소프트웨어 트랜잭셔널 메모리에서는 언어 설계가 이런 문제를 자동으로 배제한다.

또한 트랜잭셔널 메모리로 구현된 원자적 작업은 여러 개를 조합하여 더 큰 원자적 작업으로 만들 수 있다. 락 기반의 병렬 코드는 이런 일을 할 수 없다.

프로그램 예제

트랜잭셔널 메모리는 개념적으로 단순하므로, 기존 언어에 큰 변경을 가하지 않고도 쉽게 트랜잭셔널 메모리를 지원할 수 있다. 다음과 같이 임계 구역을 나타내는 문법과 유사하게 트랜잭셔널 메모리를 지원할 수 있다.

// 이중 연결 리스트에 새 노드를 원자적으로 추가함
atomic {
    newNode->prev = node;
    newNode->next = node->next;
    node->next->prev = newNode;
    node->next = newNode;
}

atomic(원자적)으로 표시된 구역이 끝나면 트랜잭션이 완료된다. 이때 충돌이 없었다면 커밋되고, 있었다면 재시작될것이다. 임계 구역 문법은 또한 종료 조건을 명시할 수도 있다.

atomic (queueSize > 0) {
    // 큐에서 객체를 꺼내 사용함
}

위와 같은 코드는 기존의 시그널로 구현된 자료구조에 비해 훨씬 간단하게 코드를 구성할 수 있다. 만약 retry와 같은 문법을 지원할 경우 트랜잭션이 실패할 때의 동작을 더 정교하게 제어할 수 있다.

atomic {
    if (queueSize > 0) {
        remove item from queue and use it
    } else {
        retry
    }
}

예외가 발생할 경우, 대부분의 트랜잭셔널 메모리 시스템은 트랜잭션 전체를 취소시킨다.

구현상의 주의점

트랜잭셔널 메모리로 구현된 프로그램에서 주의할 점은, 트랜잭션 안의 코드가 트랜잭션 중간 단계의 잘못된 데이터를 읽을 수 있다는 것이다. 즉, 다른 트랜잭션이 해당 메모리를 변경하기 전의 상태와 변경한 후 달라진 상태가 나의 트랜잭션 안에서 섞일 수 있다. 충돌을 일으킨 트랜잭션은 종료되기 전에 취소되므로 잘못된 상태가 저장될 염려는 없지만, 잘못된 상태를 안전하게 처리하지 않으면 비정상적인 예외를 일으킬 수 있다는 점을 주의해야 한다.

atomic { if (x != y) while (true) { } } atomic { x++; y++; } 트랜잭션 A 트랜잭션 B

위와 같은 두 개의 트랜잭션이 시작할 때, x와 y가 서로 같다고 가정하자. 만약 두 트랜잭션이 락으로 구현되어 A가 실행되는 동안 B가 락을 기다린다면, x와 y는 항상 같은 값을 가지므로 A가 무한루프에 빠지는 일은 없을 것이다. 그러나 트랜잭셔널 메모리로 구현되었다면 B가 x를 변경하고 y를 변경하기 전에, A가 x와 y를 비교하여, A가 무한루프에 빠지는 상황이 발생할 수 있다. 이런 문제는 트랜잭션 중 일어나는 모든 예외를 처리하여 잘못된 트랜잭션을 취소시킴으로써 방지할 수 있다. 또한, 트랜잭셔널 메모리는 락과 함께 사용할 수 있으므로, 락을 이용해 이런 문제를 방지할 수도 있다.

소프트웨어 트랜잭셔널 메모리 vs 하드웨어 트랜잭셔널 메모리

기존 하드웨어 아키텍처의 캐시 및 버스 프로토콜을 변경하여 구현한 트랜잭셔널 메모리를 하드웨어 트랜잭셔널 메모리(Hardware Transactional Memory)라고 한다.

소프트웨어 트랜잭셔널 메모리(Software Transactional Memory)는 소프트웨어 라이브러리나 프로그래밍 언어의 하부 모듈로 구현할 수 있다.

과거의 RISC 프로세서들이 지원하는 Load-link / Store-conditional 연산 또한 일종의 트랜잭셔널 메모리이지만, 이 경우 한개의 워드에 대해서만 원자적으로 동작한다.

소프트웨어 트랜잭셔널 메모리

2005년 팀 해리스, 사이먼 말로, 사이먼 페이튼 존스, 모리스 헤를리히는 글래스고 하스켈 컴파일러로 구현한 소프트웨어 트랜잭셔널 메모리를 발표하였다. 이 시스템의 특징은 retry및 orElse 함수를 지원한다는 것이다. retry는 해당 트랜잭션이 실패했을 경우 트랜잭션을 자동으로 재시도하는 함수이고, orElse는 하나의 트랜잭션이 실패하면 또다른 트랜잭션을 시도하는 것이다. 이 함수들을 사용하면 프로그래머는 여러 개의 트랜잭션을 동시에 시도하면서 먼저 완료되는 트랜잭션을 기다릴 수 있다.

그 밖에 다음과 같은 언어에서 트랜잭셔널 메모리를 지원한다

• 하스켈의 기본 플랫폼인 Haskell Platform에는 STM 라이브러리가 포함되어 있다.
• Clojure 언어는 소프트웨어 트랜잭셔널 메모리를 기본으로 지원한다
• C/C++용으로 다양한 STM 라이브러리가 존재한다. 또한 "atomic" 키워드를 지원하는 C/C++용 컴파일러인 Intel STM Compiler Prototype이 있다.
• C#
• 커먼 리스프용 다중 플랫폼 STM 라이브러리인 CL-STM이 있다.
• 자바로 구현된 STM 라이브러리와, STM을 지원하는 가상 머신들이 존재한다.
• Objective Caml의 병렬 프로그래밍 라이브러리인 [sourceforge.net/projects/cothreads/ coThreads]의 하위 모듈인 STM 라이브러리를 사용할 수 있다.
• 파이썬

하드웨어 트랜잭셔널 메모리

다음과 같은 시스템들이 하드웨어 트랜잭셔널 메모리를 지원하거나, 지원할 예정이다.

• 썬 마이크로시스템즈에서 개발중이던 Rock 프로세서 (오라클에서 취소시킴)
• Azul Systems의 Vega 2 프로세서
• IBM의 세쿼이아 수퍼컴퓨터에 탑재된 BlueGene/Q 프로세서
• 인텔의 차세대 해스웰 아키텍처에 탑재될 예정임

외부 링크

• (영어) JVSTM – Java Versioned Software Transactional Memory
• (영어) Flexviews - materialized views act like software transactional memory for database relations