소프트웨어 트랜잭셔널 메모리
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
소프트웨어 트랜잭셔널 메모리(STM)는 다중 스레드 프로그래밍에서 공유 메모리 접근을 관리하는 기술이다. 락 기반 방식보다 낙관적인 동시성 제어를 사용하여 스레드가 다른 스레드의 작업을 고려하지 않고 공유 메모리를 수정하고 로그를 기록한다. STM은 개념적으로 다중 스레드 프로그램의 이해를 단순화하고 유지보수성을 높이지만, 락 기반 시스템보다 성능이 저하될 수 있다. STM은 소프트웨어 라이브러리나 프로그래밍 언어의 하부 모듈로 구현할 수 있으며, 다양한 프로그래밍 언어에서 지원된다.
더 읽어볼만한 페이지
- 트랜잭셔널 메모리 - 스카이레이크 (마이크로아키텍처)
스카이레이크는 인텔이 2015년에 출시한 6세대 코어 i 시리즈 마이크로아키텍처로, 14nm 공정으로 제조되었으며 DDR4 메모리 지원, Gen9 GPU 통합, 다양한 제품군 출시 등의 특징을 가지지만 하이퍼스레딩 문제와 스펙터 공격에 대한 취약점도 존재한다. - 트랜잭셔널 메모리 - IBM Z
IBM Z는 높은 가용성과 하위 호환성을 특징으로 하는 IBM의 메인프레임 제품군으로, 과거 애플리케이션 실행은 물론 TCP/IP, 웹 서버, 리눅스 등 개방형 표준 지원과 64비트 어드레싱을 통해 현대적인 워크로드에 맞춰 발전했으며, z/Architecture 기반의 64비트 물리/가상 공간 지원, 다수의 프로세서 유닛, 다양한 운영 체제 지원을 주요 특징으로 한다. - 프로그래밍 언어 주제 - 프로그래밍 패러다임
프로그래밍 패러다임은 프로그래머에게 프로그램 작성 방식을 제시하는 관점 또는 스타일이며, 구조적 프로그래밍을 시작으로 절차적, 객체 지향, 선언형 등으로 발전해 명령형, 선언형, 멀티 패러다임 프로그래밍 언어로 분류된다. - 프로그래밍 언어 주제 - 프로그램 최적화
프로그램 최적화는 컴퓨터 프로그램의 효율성을 높이는 과정으로, 더 효율적인 구현 방식을 선택하거나 불필요한 기능을 제거하여 문제 해결에 집중하며, 다양한 수준에서 플랫폼 의존적이거나 독립적인 기술을 활용하여 수행되지만, 특정한 품질 지표를 개선하기 위해 다른 측면을 희생하는 트레이드오프가 발생할 수 있다. - 프로그래밍 언어 구현 - 어셈블리어
어셈블리어는 사람이 이해하기 쉬운 니모닉 기호로 기계어 명령을 표현하는 저수준 프로그래밍 언어로서, 각 프로세서마다 사양이 다른 어셈블리어가 존재하며 하드웨어 직접 제어, 성능 최적화, 저수준 시스템 프로그래밍 등에 활용된다. - 프로그래밍 언어 구현 - 컴파일러
컴파일러는 고급 프로그래밍 언어로 작성된 소스 코드를 컴퓨터가 이해할 수 있는 저급 언어로 변환하는 프로그램으로, 어휘 분석, 구문 분석, 의미 분석, 최적화, 코드 생성 등의 단계를 거쳐 목적 코드를 생성하며, 네이티브 컴파일러, 크로스 컴파일러 등으로 분류되어 다양한 분야에서 활용된다.
| 소프트웨어 트랜잭셔널 메모리 | |
|---|---|
| 개요 | |
| 유형 | 동시성 제어 메커니즘 |
| 목적 | 공유 메모리 시스템에서 원자적인 읽기 및 쓰기 작업을 제공 |
| 특징 | |
| 장점 | 세분화된 잠금 및 교착 상태를 피할 수 있음 쉽게 구성 가능하고 재사용 가능 |
| 단점 | 디버깅이 어렵고, 성능 오버헤드가 발생할 수 있음 |
| 구현 | |
| 일반적인 접근 방식 | 낙관적 동시성 제어 잠금 기반 동시성 제어 |
| 프로그래밍 언어 지원 | C++ 자바 C# 하스켈 러스트 스칼라 파이썬 커먼 리스프 |
| 관련 개념 | |
| 관련 개념 | 데이터베이스 트랜잭션 원자성 일관성 격리성 지속성 동시성 제어 잠금 |
2. 성능
트랜잭셔널 메모리(STM)는 락 기반 방식보다 낙관적인 전략을 사용한다. 스레드는 다른 스레드의 작업을 고려하지 않고 공유 메모리를 수정하고 모든 읽기 및 쓰기를 로그에 기록한다.[5] 낙관적인 접근 방식은 동시성을 증가시킨다. 스레드는 리소스 접근을 위해 대기할 필요가 없으며, 다른 스레드는 락으로 보호되는 데이터 구조의 분리된 부분을 안전하고 동시에 수정할 수 있다.[5]
소프트웨어 트랜잭셔널 메모리(STM)는 다중 스레드 프로그램의 개념적 이해를 단순화하고 유지보수성을 높인다. 락 기반 프로그래밍은 코드 섹션 간의 상호작용, 교착 상태, 라이브락, 우선 순위 역전 등의 문제가 발생할 수 있다. 특히 락킹은 멀리 떨어져 있고 관련이 없어 보이는 코드 섹션에서 중첩된 작업과 부분적인 작업에 대해 생각해야 하는데, 이는 매우 어렵고 오류가 발생하기 쉽다.
소프트웨어 트랜잭셔널 메모리 (STM)는 개념적으로 단순하여 기존 언어에 큰 변경 없이도 쉽게 지원 가능하다. 임계 구역과 유사하게 `'''atomic'''`으로 표시된 구역을 사용해 트랜잭션을 표현할 수 있다.
STM(소프트웨어 트랜잭셔널 메모리)은 개념적으로 단순하여 프로그래머는 비교적 간단한 구문을 사용하여 STM을 사용할 수 있다.[6] Tim Harris와 Keir Fraser는 "경량 트랜잭션을 위한 언어 지원"에서 고전적인 ''조건부 임계 구역''(CCR)을 사용하여 트랜잭션을 나타내는 아이디어를 제안했다.[6] 가장 단순한 형태는 "atomic 블록"으로, 단일 순간에 논리적으로 발생하는 코드 블록이다.
소프트웨어 트랜잭셔널 메모리(STM)를 낙관적 읽기로 구현할 때, 완료되지 않은 트랜잭션은 일관되지 않은 상태(다른 트랜잭션에서 기록한 이전 값과 새 값을 혼합)를 읽을 수 있다. 이러한 트랜잭션은 결국 커밋에 실패하지만, 일관되지 않은 상태로 인해 치명적인 예외를 트리거하거나 무한 루프에 빠질 수 있다.
소프트웨어 트랜잭셔널 메모리(Software Transactional Memory, STM)는 소프트웨어 라이브러리나 프로그래밍 언어의 하부 모듈로 구현할 수 있다.
그러나 STM 시스템은 로그 유지 및 트랜잭션 커밋에 필요한 오버헤드로 인해 세분화된 락 기반 시스템보다 성능이 저하될 수 있다. 프로세서 수가 적을 경우 (애플리케이션에 따라 1~4개) 성능 저하가 발생할 수 있지만, 일반적으로 두 배 이상 느려지지는 않는다. STM 옹호자들은 이러한 성능 저하가 STM의 개념적 이점으로 정당화된다고 주장한다.[5]
이론적으로 n개의 동시 트랜잭션이 있을 때 최악의 경우 공간 및 시간 복잡도는 O(n)이다. 락 기반 알고리즘이 소프트웨어 트랜잭셔널 메모리보다 더 나은 시간 복잡성을 갖는 경우가 드물게 존재한다.[7]
STM은 락-프리 알고리즘으로 구현하거나 락을 사용할 수 있다. 락킹에는 인카운터-타임 락킹과 커밋-타임 락킹의 두 가지 유형이 있다.[7] 커밋-타임 방식의 예시로 Dice, Shalev, 및 Shavit이 구현한 "트랜잭셔널 락킹 II"이 있다.
3. 개념적 장단점
반면, STM은 각 트랜잭션을 단일 스레드 계산으로 간주하여 이러한 문제를 완화한다. 교착 상태 및 라이브락은 방지되거나 트랜잭션 관리자에 의해 처리된다. 우선순위 역전은 높은 우선순위 트랜잭션이 낮은 우선순위 트랜잭션을 중단시킬 수 있어 덜 발생한다.
하지만 트랜잭션은 재시도 및 중단될 수 있어야 하므로, 멱등성을 가져야 하고, 롤백 가능한 부작용이 있는 작업은 롤백 작업도 포함해야 한다. 이로 인해 일부 입출력 작업은 트랜잭션 내에서 수행하기 어렵다. 이러한 문제는 취소 불가능한 작업을 버퍼에 담아두고 실제 작업은 트랜잭션 바깥에서 수행하는 방법으로 해결할 수 있다. 하스켈과 같은 언어는 타입 시스템을 통해 트랜잭션 내에서 취소 불가능한 작업이 수행되는 것을 컴파일 시점에 방지한다.
Tim Harris, Simon Peyton Jones 등이 Concurrent Haskell 위에 STM을 구축하였는데, 이를 통해 임의의 원자적 연산을 더 큰 원자적 연산으로 합성할 수 있다. 이는 락 기반 프로그래밍에서는 불가능한 일이다.
4. 구성 가능한 연산
```
// 이중 연결 리스트에 새 노드를 원자적으로 추가함
'''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
}
}
```
예외 발생 시, 대부분의 트랜잭셔널 메모리 시스템은 트랜잭션 전체를 취소시킨다.
2005년, 팀 해리스(Tim Harris), 사이먼 말로우(Simon Marlow), 사이먼 페이튼 존스(Simon Peyton Jones), 모리스 허리히(Maurice Herlihy)는 동시성 하스켈(Concurrent Haskell) 기반의 STM 시스템을 설명했다. 이 시스템은 원자적 연산을 더 큰 원자적 연산으로 구성할 수 있게 한다. 이는 락 기반 프로그램에서는 불가능한 구성이다. 예를 들어, 스레드 안전한 삽입 및 삭제 연산을 가진 해시 테이블에서 항목 A를 테이블 t1에서 삭제하고 테이블 t2에 삽입하려 할 때, 중간 상태(어떤 테이블에도 항목이 없는 상태)는 다른 스레드에 보이지 않아야 한다. 해시 테이블 구현자가 이러한 요구 사항을 예상하지 못하는 한, 이를 충족할 방법이 없다. 즉, 개별적으로 올바른 연산(삽입, 삭제)은 더 큰 올바른 연산으로 구성될 수 없다.
STM은 두 연산을 트랜잭션으로 묶어 결합된 연산이 원자적이 되도록 하여 이 문제를 해결한다. `retry` 명령어는 실패한 트랜잭션에서 생성된 트랜잭션 로그를 사용하여 읽은 메모리 셀을 결정하고, 이러한 셀 중 하나가 수정되면 트랜잭션을 자동으로 다시 시도한다.
`orElse` 함수는 대안 구성을 위한 메커니즘을 제공한다. 하나의 트랜잭션을 실행하고, 해당 트랜잭션이 `retry`를 수행하면 두 번째 트랜잭션을 실행한다. 둘 다 다시 시도하면 관련 변경이 이루어지는 즉시 둘 다 다시 시도한다. 이는 POSIX 네트워킹 `select()` 호출과 유사하며, 호출자가 여러 이벤트 중 하나를 동시에 대기할 수 있도록 한다. 또한 차단 및 비차단 연산 간의 변환을 위한 간단한 메커니즘을 제공하는 등 프로그래밍 인터페이스를 단순화한다.
이 방식은 글래스고 하스켈 컴파일러(Glasgow Haskell Compiler)에 구현되었다.
5. 제안된 언어 지원
```
// 이중 연결 리스트에 노드를 원자적으로 삽입
'''atomic''' {
newNode->prev = node;
newNode->next = node->next;
node->next->prev = newNode;
node->next = newNode;
}
```
블록의 끝에 도달하면 가능하면 트랜잭션이 커밋되거나, 그렇지 않으면 중단하고 다시 시도한다. CCR은 트랜잭션이 작업을 수행할 때까지 대기할 수 있는 ''가드 조건''도 허용한다.
```
'''atomic''' (queueSize > 0) {
remove item from queue and use it
}
```
조건이 충족되지 않으면 트랜잭션 관리자는 다른 트랜잭션이 조건을 변경하는 ''커밋''을 할 때까지 대기한 후 다시 시도한다. 생산자와 소비자의 이러한 느슨한 결합은 스레드 간의 명시적인 시그널링에 비해 모듈성을 향상시킨다. "Composable Memory Transactions"[6]는 '''retry''' 명령어를 통해 한 단계 더 나아가 트랜잭션을 언제든지 중단하고 트랜잭션에 의해 이전에 읽은 ''일부 값''이 수정될 때까지 대기한 후 다시 시도할 수 있다.
```
'''atomic''' {
if (queueSize > 0) {
remove item from queue and use it
} else {
'''retry'''
}
}
```
트랜잭션 후반에 동적으로 다시 시도하는 이러한 기능은 프로그래밍 모델을 단순화하고 새로운 가능성을 열어준다.[6]
한 가지 문제는 예외가 트랜잭션 외부로 전파될 때 어떻게 동작하는가이다. "Composable Memory Transactions"[6]에서 저자는 예외가 일반적으로 Concurrent Haskell에서 예상치 못한 오류를 나타내기 때문에 트랜잭션을 중단해야 한다고 결정했지만, 예외는 진단 목적으로 트랜잭션 중에 할당되고 읽은 정보를 유지할 수 있다. 그들은 다른 설정에서는 다른 설계 결정이 합리적일 수 있다고 강조한다.
6. 구현상의 주의점
예를 들어, 처음에 x와 y가 같은 값을 가질 때, 다음과 같은 두 트랜잭션 A와 B를 고려해 보자.트랜잭션 A 트랜잭션 B
트랜잭션 A가 트랜잭션 B가 업데이트한 후의 x 값을 읽고, 트랜잭션 B가 업데이트하기 전의 y 값을 읽으면 무한 루프에 빠질 수 있다.
이러한 문제를 처리하는 일반적인 전략은 치명적인 예외를 가로채고 유효하지 않은 트랜잭션을 중단하는 것이다.
좀비 트랜잭션에 대한 정기적인 검사 없이, '썩은' 값을 읽지 않도록 보장하는 것을 불투명성(Opacity)이라고 한다. 불투명성을 보장하는 방법으로는 증분 검증(Incremental Validation)과 글로벌 버전 클록을 사용하는 방법 등이 있다. 증분 검증은 새로운 값을 읽을 때마다 이전에 읽은 값이 일치하는지 확인하는 방식이다. 글로벌 버전 클록은 트랜잭션 완료 시 증가하는 공유 카운터를 사용하여 다른 트랜잭션에 의한 갱신을 감지하는 방식이다.
7. 구현
2005년 팀 해리스, 사이먼 말로, 사이먼 페이튼 존스, 모리스 헤를리히는 글래스고 하스켈 컴파일러로 구현한 STM을 발표했다. 이 시스템은 '''retry'''(트랜잭션 실패 시 자동 재시도) 및 '''orElse'''(한 트랜잭션 실패 시 다른 트랜잭션 시도) 함수를 지원하여, 프로그래머가 여러 트랜잭션을 동시에 시도하고 먼저 완료되는 것을 기다릴 수 있게 한다.
다양한 언어 및 플랫폼에서 STM을 지원한다.7. 1. 소프트웨어 트랜잭셔널 메모리 (STM)
소프트웨어 트랜잭셔널 메모리(Software Transactional Memory, STM)는 소프트웨어 라이브러리나 프로그래밍 언어의 하부 모듈로 구현할 수 있다.
2005년 팀 해리스, 사이먼 말로, 사이먼 페이튼 존스, 모리스 헤를리히는 글래스고 하스켈 컴파일러로 구현한 STM을 발표했다. 이 시스템은 '''retry'''(트랜잭션 실패 시 자동 재시도) 및 '''orElse'''(한 트랜잭션 실패 시 다른 트랜잭션 시도) 함수를 지원하여, 프로그래머가 여러 트랜잭션을 동시에 시도하고 먼저 완료되는 것을 기다릴 수 있게 한다.
다양한 언어 및 플랫폼에서 STM을 지원한다.7. 2. 하드웨어 트랜잭셔널 메모리 (HTM)
기존 하드웨어 아키텍처의 캐시 및 버스 프로토콜을 변경하여 구현한 트랜잭셔널 메모리를 하드웨어 트랜잭셔널 메모리(Hardware Transactional Memory)라고 한다.[8][9][10][11][12][13][14][15][16] 과거의 RISC 프로세서들이 지원하는 Load-link / Store-conditional 연산 또한 일종의 트랜잭셔널 메모리이지만, 이 경우 한개의 워드에 대해서만 원자적으로 동작한다.
다음은 하드웨어 트랜잭셔널 메모리를 지원하거나, 지원할 예정인 시스템들이다.
참조
[1]
논문
An architecture for mostly functional languages.
https://web.archive.[...]
Proceedings of the 1986 ACM conference on Lisp and functional programming
[2]
논문
Transactional memory: architectural support for lock-free data structures.
Proceedings of the 20th annual international symposium on Computer architecture (ISCA '93). Volume 21, Issue 2, May 1993.
[3]
간행물
Software transactional memory.
Distributed Computing. Volume 10, Number 2. February 1997.
[4]
웹사이트
"software transactional memory" - Google Scholar
https://scholar.goog[...]
2013-11-10
[5]
웹사이트
Programming in the Age of Concurrency: Software Transactional Memory
http://channel9.msdn[...]
2007-06-09
[6]
서적
Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming - PPoPP '05
[7]
문서
Concurrency_control#Methods
[8]
웹사이트
Glasgow Haskell Compiler (GHC) Commentary: Software Transactional Memory (STM)
https://gitlab.haske[...]
[9]
웹사이트
Software Transactional Memory in C++: Pure Functional Approach (tutorial)
https://gist.github.[...]
[10]
웹사이트
Refs and Transactions
https://clojure.org/[...]
[11]
웹사이트
Poor man's STM in Node.js
https://github.com/r[...]
[12]
웹사이트
talhof8/kashmir
https://github.com/t[...]
[13]
웹사이트
Rust Package Registry
https://crates.io/cr[...]
[14]
웹사이트
Introduction to Software Transactional Memory ZIO
https://zio.dev/refe[...]
[15]
웹사이트
Kcas — STM based on lock-free MCAS
https://github.com/o[...]
[16]
웹사이트
Transactional memory (STM)
https://arrow-kt.io/[...]
[17]
논문
An architecture for mostly functional languages.
http://web.mit.edu/m[...]
Proceedings of the 1986 ACM conference on LISP and functional programming.
2013-11-01
[18]
간행물
Software transactional memory.
Distributed Computing. Volume 10, Number 2. February 1997.
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com