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

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

동시성 프로그래밍에서 공유 자원에 대한 안전한 접근은 항상 중요한 과제다. 전통적으로 뮤텍스 락과 같은 **비관적 락(Negative Lock)** 방식을 사용해왔다. 이 방식은 크리티컬 섹션에 진입하기 전에 반드시 락을 획득해야 하며, 락을 얻지 못하면 코드 실행 자체가 블록된다.

하지만 이와는 다른 접근 방식이 있다. 바로 **낙관적 락(Optimistic Lock)** 방식인데, 이는 "일단 실행하고 나중에 검증하자"는 철학을 가지고 있다.

## 낙관적 접근: 트랜잭셔널 메모리

**소프트웨어 트랜잭셔널 메모리(Software Transactional Memory, STM)**는 이러한 낙관적 접근을 구현한 대표적인 기술이다. STM은 크리티컬 섹션의 코드를 투기적으로 실행한 후, 실행 과정에서 다른 스레드와의 경합이 감지되지 않았을 때만 그 결과를 메모리에 실제로 커밋한다. 마치 데이터베이스의 트랜잭션처럼 작동하는 것이다.

이러한 방식은 락을 기다리는 시간을 줄이고, 데드락 가능성을 원천적으로 차단할 수 있다는 장점이 있다.

## 하드웨어와 소프트웨어 구현

트랜잭셔널 메모리는 구현 방식에 따라 두 가지로 나뉜다.

* **Hardware Transactional Memory (HTM)**: CPU 레벨에서 직접 지원하는 방식
    
* **Software Transactional Memory (STM)**: 소프트웨어적으로 구현하는 방식
    

HTM은 성능면에서 우수하지만 하드웨어 지원이 필요하다는 제약이 있다. 반면 STM은 순수하게 소프트웨어로 구현되어 범용성이 높으며, 실제로 Haskell이나 Clojure 같은 함수형 언어에서 핵심 동시성 메커니즘으로 채택되고 있다.

## TL2: 실용적인 STM 구현

STM을 실제로 구현하는 방법은 여러 가지가 있지만, 그 중에서도 **Transaction Locking II (TL2)** 알고리즘은 성능과 구현 복잡도 사이의 균형을 잘 맞춘 대표적인 방법이다.

그런고로 이 글에서는 STM의 특징을 좀 더 알아보고, TL2의 구현에 대해 설명할 것이다.

---

# STM의 특징

STM은 뮤텍스와 같은 비관적 락과는 성질이 다르다. STM은 중요한 특징 네 가지를 가지고 있는데

1. 트랜잭션 중의 코드가 2회 이상 실행될 가능성이 있다.
    
    * 경합이 발견된 후에는 트랜잭션을 재시도하므로 2회 이상 실행될 수 있다.
        
2. 트랜잭션 중에 부작용이 있는 코드는 실행하지 않는다.
    
    * 트랜잭션이 여러 번 발생하면 그에 따라 특정 코드가 여러 번 실행될 수 있어 의도치 않은 결과를 만들 수 있는데,
        
3. 데드락이 발생하지 않는다.
    
    * 경합이 감지되면 쓰고, 그렇지 않으면 재시도하기 때문에 식사하는 철학자와 같은 문제를 해결할 수 있다.
        
4. 여러 트랜잭션 처리를 합성할 수 있다.
    
    * STM에서는 임의의 트랜잭션 처리를 임의로 조합해 실행 가능하다.
        
    * 뮤텍스에서는 데드락, 락프리에서는 전용 데이터 구조 문제 때문에 임의로 조합하기 어렵지만, STM에서는 어떤 조작도 임의로 조합 가능하다.
        

---

# TL2 알고리즘

TL2의 타입은 아래와 같다.

| 타입 | 용도 |
| --- | --- |
| Memory | 메모리 초기화, 락, 버전 관리에 이용 |
| STM | 실제로 트랜잭션을 실행하기 위해 이용 |
| ReadTrans | Read 트랜잭션 시 메모리 읽기에 이용 |
| WriteTrans | Write 트랜잭션 시 메모리 읽기, 쓰기에 사용 |
| STMResult | 트랜잭션 반환값 타입 |
|  |  |

## 코드

러스트로 구현된 TL2 알고리즘은 다음과 같다.

[`tl2.rs`](http://tl2.rs):

```rust
// TL2.rs - TL2 (Transactional Locking 2) 알고리즘 구현
use std::cell::UnsafeCell;
use std::collections::HashMap;
use std::collections::HashSet;
use std::sync::atomic::{AtomicU64, Ordering, fence};

// ===== 상수 정의 =====
// 스트라이프 크기: 메모리를 8바이트 단위로 관리
const STRIPE_SIZE: usize = 8; 

// 전체 메모리 크기: 512바이트
const MEM_SIZE: usize = 512; 

// ===== 메모리 구조체 정의 =====
pub struct Memory {
    mem: Vec<u8>,             // 실제 데이터를 저장하는 메모리 영역
    lock_ver: Vec<AtomicU64>, // 각 스트라이프의 락과 버전을 저장 (최상위 비트: 락, 나머지: 버전)
    global_clock: AtomicU64,  // 전역 버전 클락 (모든 트랜잭션이 공유하는 논리적 시간)
    shift_size: u32,          // 주소를 스트라이프 인덱스로 변환하기 위한 시프트 크기
}

impl Memory {
    pub fn new() -> Self {
        // 메모리 영역을 0으로 초기화
        let mem = [0].repeat(MEM_SIZE);

        // 스트라이프 크기는 2의 거듭제곱이어야 함 (8 = 2^3)
        // trailing_zeros()는 2진수에서 끝에서부터 0의 개수를 반환 (8 = 1000₂ → 3)
        let shift = STRIPE_SIZE.trailing_zeros(); 

        // 각 스트라이프에 대한 락/버전 정보를 초기화
        // 스트라이프 개수 = MEM_SIZE / STRIPE_SIZE = 512 / 8 = 64개
        let mut lock_ver = Vec::new();
        for _ in 0..MEM_SIZE >> shift {  // 64개의 스트라이프
            lock_ver.push(AtomicU64::new(0));  // 초기값: 락 해제 상태, 버전 0
        }

        Memory {
            mem,
            lock_ver,
            global_clock: AtomicU64::new(0),  // 전역 클락을 0으로 초기화
            shift_size: shift,
        }
    }

    // 전역 버전 클락을 1 증가시키고 이전 값을 반환
    // AcqRel 순서를 사용하여 메모리 순서 보장
    fn inc_global_clock(&mut self) -> u64 {
        self.global_clock.fetch_add(1, Ordering::AcqRel)
    }

    // 지정된 주소의 현재 버전을 반환
    // 최상위 비트(락 비트)를 제거하고 순수 버전만 반환
    fn get_addr_ver(&self, addr: usize) -> u64 {
        let idx = addr >> self.shift_size;  // 주소를 스트라이프 인덱스로 변환
        let n = self.lock_ver[idx].load(Ordering::Relaxed);
        n & !(1 << 63)  // 최상위 비트를 0으로 마스킹하여 버전만 추출
    }

    // 지정된 주소가 락되어 있지 않고 버전이 rv 이하인지 확인
    // TL2의 핵심: 락 비트와 버전을 동시에 확인
    fn test_not_modify(&self, addr: usize, rv: u64) -> bool {
        let idx = addr >> self.shift_size;
        let n = self.lock_ver[idx].load(Ordering::Relaxed);
        // 락이 걸려있으면 최상위 비트가 1이므로 n > rv가 됨
        // 락이 없어도 버전이 rv보다 크면 n > rv가 됨
        n <= rv
    }

    // 지정된 주소의 락을 원자적으로 획득 시도
    // fetch_update를 사용하여 compare-and-swap 연산 수행
    fn lock_addr(&mut self, addr: usize) -> bool {
        let idx = addr >> self.shift_size;
        match self.lock_ver[idx].fetch_update(
            Ordering::Relaxed, // 쓰기 시의 메모리 순서
            Ordering::Relaxed, // 읽기 시의 메모리 순서
            |val| {
                // 현재 값의 최상위 비트(락 비트) 확인
                let lock_bit = val & (1 << 63);
                if lock_bit == 0 { 
                    // 락이 해제되어 있으면 락 비트를 설정
                    Some(val | (1 << 63)) 
                } else { 
                    // 이미 락이 걸려있으면 실패
                    None 
                }
            },
        ) {
            Ok(_) => true,   // 락 획득 성공
            Err(_) => false, // 락 획득 실패
        }
    }

    // 지정된 주소의 락을 해제
    // fetch_and를 사용하여 최상위 비트만 0으로 설정
    fn unlock_addr(&mut self, addr: usize) {
        let idx = addr >> self.shift_size;
        self.lock_ver[idx].fetch_and(!(1 << 63), Ordering::Relaxed);
    }
}

// ===== 읽기 전용 트랜잭션 구조체 =====
pub struct ReadTrans<'a> {
    read_ver: u64,   // 이 트랜잭션의 읽기 버전 (시작 시점의 전역 클락)
    is_abort: bool,  // 충돌 감지 시 true로 설정
    mem: &'a Memory, // 메모리에 대한 불변 참조
}

impl<'a> ReadTrans<'a> {
    fn new(mem: &'a Memory) -> Self {
        ReadTrans {
            is_abort: false,
            // 트랜잭션 시작 시점의 전역 클락을 읽어서 일관된 스냅샷 확보
            read_ver: mem.global_clock.load(Ordering::Acquire),
            mem,
        }
    }

    // 메모리에서 데이터 읽기 (낙관적 읽기)
    // Double-checked locking 패턴 사용
    pub fn load(&mut self, addr: usize) -> Option<[u8; STRIPE_SIZE]> {
        // 이미 충돌이 감지된 경우 즉시 중단
        if self.is_abort {
            return None;
        }

        // 주소가 스트라이프 경계에 정렬되어 있는지 확인
        assert_eq!(addr & (STRIPE_SIZE - 1), 0);

        // 첫 번째 검사: 메모리가 락되어 있지 않고 읽기 버전 이하인지 확인
        if !self.mem.test_not_modify(addr, self.read_ver) {
            self.is_abort = true;
            return None;
        }

        // 메모리 펜스: 위의 검사 후 실제 읽기 전에 순서 보장
        fence(Ordering::Acquire);

        // 실제 메모리 데이터 복사
        let mut mem = [0; STRIPE_SIZE];
        for (dst, src) in mem
            .iter_mut()
            .zip(self.mem.mem[addr..addr + STRIPE_SIZE].iter())
        {
            *dst = *src;
        }

        // 강한 메모리 펜스: 읽기 완료 후 두 번째 검사 전에 순서 보장
        fence(Ordering::SeqCst);

        // 두 번째 검사: 읽기 도중 다른 트랜잭션이 수정했는지 확인
        if !self.mem.test_not_modify(addr, self.read_ver) {
            self.is_abort = true;
            return None;
        }

        Some(mem)
    }
}

// ===== 쓰기 트랜잭션 구조체 =====
pub struct WriteTrans<'a> {
    read_ver: u64,                                // 읽기 버전 (트랜잭션 시작 시점)
    read_set: HashSet<usize>,                     // 읽은 주소들의 집합
    write_set: HashMap<usize, [u8; STRIPE_SIZE]>, // 쓸 주소와 값들의 맵
    locked: Vec<usize>,                           // 락을 획득한 주소들의 리스트
    is_abort: bool,                               // 충돌 감지 플래그
    mem: &'a mut Memory,                          // 메모리에 대한 가변 참조
}

// 트랜잭션이 소멸될 때 자동으로 모든 락 해제
impl<'a> Drop for WriteTrans<'a> {
    fn drop(&mut self) {
        // 획득한 모든 락을 해제하여 데드락 방지
        for addr in self.locked.iter() {
            self.mem.unlock_addr(*addr);
        }
    }
}

impl<'a> WriteTrans<'a> {
    fn new(mem: &'a mut Memory) -> Self {
        WriteTrans {
            read_set: HashSet::new(),
            write_set: HashMap::new(),
            locked: Vec::new(),
            is_abort: false,
            // 트랜잭션 시작 시점의 전역 클락 획득
            read_ver: mem.global_clock.load(Ordering::Acquire),
            mem,
        }
    }

    // 메모리에 쓰기 (지연된 쓰기 - write-set에 저장만)
    pub fn store(&mut self, addr: usize, val: [u8; STRIPE_SIZE]) {
        // 주소 정렬 확인
        assert_eq!(addr & (STRIPE_SIZE - 1), 0);
        // write-set에 추가 (실제 메모리 쓰기는 커밋 시에)
        self.write_set.insert(addr, val);
    }

    // 메모리에서 읽기 (write-set 우선 확인)
    pub fn load(&mut self, addr: usize) -> Option<[u8; STRIPE_SIZE]> {
        // 충돌 감지 시 즉시 중단
        if self.is_abort {
            return None;
        }

        // 주소 정렬 확인
        assert_eq!(addr & (STRIPE_SIZE - 1), 0);

        // read-set에 주소 추가 (커밋 시 검증용)
        self.read_set.insert(addr);

        // write-set에 있는 경우 해당 값을 반환 (자신이 쓴 값 읽기)
        if let Some(m) = self.write_set.get(&addr) {
            return Some(*m);
        }

        // write-set에 없는 경우 실제 메모리에서 읽기 (ReadTrans와 동일한 로직)
        if !self.mem.test_not_modify(addr, self.read_ver) {
            self.is_abort = true;
            return None;
        }

        fence(Ordering::Acquire);

        let mut mem = [0; STRIPE_SIZE];
        for (dst, src) in mem
            .iter_mut()
            .zip(self.mem.mem[addr..addr + STRIPE_SIZE].iter())
        {
            *dst = *src;
        }

        fence(Ordering::SeqCst);

        if !self.mem.test_not_modify(addr, self.read_ver) {
            self.is_abort = true;
            return None;
        }

        Some(mem)
    }

    // write-set의 모든 주소에 대해 락 획득 시도
    // 모든 락을 획득할 수 있어야만 true 반환 (all-or-nothing)
    fn lock_write_set(&mut self) -> bool {
        for (addr, _) in self.write_set.iter() {
            if self.mem.lock_addr(*addr) {
                // 락 획득 성공 시 locked 리스트에 추가
                self.locked.push(*addr);
            } else {
                // 하나라도 락 획득 실패 시 즉시 false 반환
                // Drop trait에 의해 기존 락들은 자동 해제됨
                return false;
            }
        }
        true
    }

    // read-set의 모든 주소에 대해 검증 수행
    // 읽었던 데이터가 여전히 유효한지 확인
    fn validate_read_set(&self) -> bool {
        for addr in self.read_set.iter() {
            if self.write_set.contains_key(addr) {
                // write-set에 있는 주소는 자신이 락을 가지고 있음
                // 버전만 검사 (다른 트랜잭션이 중간에 수정했는지)
                let ver = self.mem.get_addr_ver(*addr);
                if ver > self.read_ver {
                    return false;
                }
            } else {
                // write-set에 없는 주소는 락과 버전 모두 검사
                if !self.mem.test_not_modify(*addr, self.read_ver) {
                    return false;
                }
            }
        }
        true
    }

    // 트랜잭션 커밋: 모든 쓰기를 실제 메모리에 반영
    fn commit(&mut self, ver: u64) {
        // 1. write-set의 모든 데이터를 실제 메모리에 복사
        for (addr, val) in self.write_set.iter() {
            let addr = *addr as usize;
            for (dst, src) in self.mem.mem[addr..addr + STRIPE_SIZE].iter_mut().zip(val) {
                *dst = *src;
            }
        }

        // 2. 메모리 펜스로 쓰기 완료 보장
        fence(Ordering::Release);

        // 3. 모든 주소의 락 해제 및 새 버전으로 업데이트
        for (addr, _) in self.write_set.iter() {
            let idx = addr >> self.mem.shift_size;
            // 락 비트를 0으로, 버전을 새 버전으로 설정
            self.mem.lock_ver[idx].store(ver, Ordering::Relaxed);
        }

        // 4. locked 리스트 초기화 (Drop에서 중복 해제 방지)
        self.locked.clear();
    }
}

// ===== STM 결과 타입 =====
pub enum STMResult<T> {
    Ok(T),    // 성공
    Retry,    // 재시도 필요 (충돌 감지)
    Abort,    // 중단 (취소)
}

// ===== 메인 STM 구조체 =====
pub struct STM {
    mem: UnsafeCell<Memory>, // 내부 가변성을 위한 UnsafeCell 사용
}

// 스레드 간 공유를 위한 안전성 마커
unsafe impl Sync for STM {}
unsafe impl Send for STM {}

impl STM {
    pub fn new() -> Self {
        STM {
            mem: UnsafeCell::new(Memory::new()),
        }
    }

    // 읽기 전용 트랜잭션 실행
    pub fn read_transaction<F, R>(&self, f: F) -> Option<R>
    where
        F: Fn(&mut ReadTrans) -> STMResult<R>,
    {
        loop {
            // 1. 새로운 읽기 트랜잭션 생성 (현재 전역 클락으로 스냅샷)
            let mut tr = ReadTrans::new(unsafe { &*self.mem.get() });

            // 2. 사용자 함수 실행 (투기적 실행)
            match f(&mut tr) {
                STMResult::Abort => return None,
                STMResult::Retry => {
                    if tr.is_abort {
                        continue; // 충돌 감지 시 재시도
                    }
                    return None; // 사용자가 명시적으로 재시도 요청
                }
                STMResult::Ok(val) => {
                    if tr.is_abort {
                        continue; // 충돌 감지 시 재시도
                    } else {
                        return Some(val); // 성공적으로 완료
                    }
                }
            }
        }
    }

    // 읽기-쓰기 트랜잭션 실행 (TL2의 핵심 로직)
    pub fn write_transaction<F, R>(&self, f: F) -> Option<R>
    where
        F: Fn(&mut WriteTrans) -> STMResult<R>,
    {
        loop {
            // 1. 새로운 쓰기 트랜잭션 생성
            let mut tr = WriteTrans::new(unsafe { &mut *self.mem.get() });

            // 2. 사용자 함수 실행 (투기적 실행 단계)
            let result;
            match f(&mut tr) {
                STMResult::Abort => return None,
                STMResult::Retry => {
                    if tr.is_abort {
                        continue; // 충돌 감지 시 재시도
                    }
                    return None;
                }
                STMResult::Ok(val) => {
                    if tr.is_abort {
                        continue; // 투기적 실행 중 충돌 감지
                    }
                    result = val;
                }
            }

            // 3. write-set의 모든 주소에 대해 락 획득 시도
            if !tr.lock_write_set() {
                continue; // 락 획득 실패 시 재시도
            }

            // 4. 전역 클락 증가 및 새 버전 번호 할당
            let ver = 1 + tr.mem.inc_global_clock();

            // 5. read-set 검증
            // 조건1: read_ver + 1 == ver (다른 트랜잭션이 커밋하지 않음)
            // 조건2: validate_read_set() 성공 (읽었던 데이터가 여전히 유효)
            if tr.read_ver + 1 != ver && !tr.validate_read_set() {
                continue; // 검증 실패 시 재시도
            }

            // 6. 커밋 수행 및 락 해제
            tr.commit(ver);

            return Some(result); // 성공적으로 완료
        }
    }
}

// ===== 편의성을 위한 매크로 =====

// 메모리 읽기용 매크로 - 실패 시 자동으로 Retry 반환
#[macro_export]
macro_rules! load {
    ($t:ident, $a:expr) => {
        if let Some(v) = ($t).load($a) {
            v
        } else {
            return tl2::STMResult::Retry;
        }
    };
}

// 메모리 쓰기용 매크로 - 단순히 store 호출
#[macro_export]
macro_rules! store {
    ($t:ident, $a:expr, $v:expr) => {
        $t.store($a, $v)
    };
}
```

[`main.rs`](http://main.rs):

```rust
// main.rs - TL2 STM을 사용한 식사하는 철학자 문제 해결
use std::sync::Arc;
use std::{thread, time};
mod tl2;

// ===== 상수 정의 =====
const NUM_PHILOSOPHERS: usize = 8; // 철학자 및 포크의 개수

// ===== 철학자 스레드 함수 =====
fn philosopher(stm: Arc<tl2::STM>, n: usize) {
    // 각 철학자는 고유한 번호 n을 가지며, 왼쪽과 오른쪽 포크를 사용

    // 포크의 메모리 주소 계산
    // 각 포크는 8바이트씩 할당되므로 8 * n 주소에 위치
    let left = 8 * n; // 철학자 n의 왼쪽 포크 주소
    let right = 8 * ((n + 1) % NUM_PHILOSOPHERS); // 오른쪽 포크 주소 (원형 배치)

    // 각 철학자는 500,000번 반복하여 식사 시도
    for _ in 0..500000 {
        // ===== 포크 획득 단계 =====
        // 양쪽 포크를 모두 들 수 있을 때까지 반복 시도
        while !stm
            .write_transaction(|tr| {
                // 트랜잭션 내에서 양쪽 포크의 상태를 확인
                let mut f1 = load!(tr, left); // 왼쪽 포크 읽기 (매크로 사용)
                let mut f2 = load!(tr, right); // 오른쪽 포크 읽기

                // 포크 상태 확인: 0 = 사용 가능, 1 = 사용 중
                if f1[0] == 0 && f2[0] == 0 {
                    // 양쪽 포크가 모두 비어있는 경우

                    // 포크를 사용 중으로 표시 (1로 설정)
                    f1[0] = 1;
                    f2[0] = 1;

                    // 메모리에 변경사항 저장 (write-set에 추가)
                    store!(tr, left, f1);
                    store!(tr, right, f2);

                    // 포크 획득 성공을 반환
                    tl2::STMResult::Ok(true)
                } else {
                    // 하나라도 사용 중인 경우 획득 실패
                    tl2::STMResult::Ok(false)
                }
            })
            .unwrap()
        // Option을 언래핑 (None은 트랜잭션 중단을 의미)
        {
            // while 루프: false가 반환되면 계속 시도
            // 다른 철학자가 포크를 사용 중이면 대기
        }

        // ===== 식사 시뮬레이션 =====
        // 실제로는 여기서 철학자가 생각하고 식사하는 시간을 시뮬레이션할 수 있음
        // 현재 구현에서는 즉시 포크를 내려놓음

        // ===== 포크 반납 단계 =====
        // 식사 완료 후 양쪽 포크를 모두 내려놓음
        stm.write_transaction(|tr| {
            // 현재 포크 상태를 읽어옴
            let mut f1 = load!(tr, left);
            let mut f2 = load!(tr, right);

            // 포크를 사용 가능 상태로 변경 (0으로 설정)
            f1[0] = 0;
            f2[0] = 0;

            // 메모리에 변경사항 저장
            store!(tr, left, f1);
            store!(tr, right, f2);

            // 반환값은 사용하지 않으므로 ()
            tl2::STMResult::Ok(())
        });

        // 포크 반납은 항상 성공해야 하므로 unwrap() 사용
        // (철학자는 자신이 가진 포크만 내려놓으므로 충돌 없음)
    }
}

// ===== 관측자 스레드 함수 =====
// 시스템의 일관성을 지속적으로 모니터링
fn observer(stm: Arc<tl2::STM>) {
    // 10,000번 반복하여 상태 관측
    for _ in 0..10000 {
        // ===== 현재 포크 상태 스냅샷 획득 =====
        // 읽기 전용 트랜잭션으로 모든 포크의 일관된 상태를 읽음
        let chopsticks = stm
            .read_transaction(|tr| {
                let mut v = [0; NUM_PHILOSOPHERS];

                // 모든 포크의 상태를 순차적으로 읽기
                for i in 0..NUM_PHILOSOPHERS {
                    v[i] = load!(tr, 8 * i)[0]; // i번째 포크의 상태
                }

                tl2::STMResult::Ok(v)
            })
            .unwrap(); // 읽기 트랜잭션은 항상 성공해야 함

        // 현재 포크 상태를 출력 (디버깅 및 모니터링용)
        println!("{:?}", chopsticks);

        // ===== 일관성 검사 =====
        // 불변식: 사용 중인 포크의 총 개수는 항상 짝수여야 함
        // 이유: 각 철학자는 항상 2개의 포크를 동시에 사용하므로
        let mut n = 0;
        for c in &chopsticks {
            if *c == 1 {
                // 사용 중인 포크 개수 세기
                n += 1;
            }
        }

        // 홀수 개의 포크가 사용 중이면 일관성 위반
        if n & 1 != 0 {
            // n % 2 != 0과 동일
            panic!("inconsistent: {} forks in use", n);
        }

        // 100마이크로초 대기 (관측 주기 조절)
        let us = time::Duration::from_micros(100);
        thread::sleep(us);
    }
}

// ===== 메인 함수 =====
fn main() {
    // STM 인스턴스 생성 (Arc로 래핑하여 스레드 간 공유)
    let stm = Arc::new(tl2::STM::new());
    let mut v = Vec::new();

    println!("Starting {} philosophers...", NUM_PHILOSOPHERS);

    // ===== 철학자 스레드들 생성 및 시작 =====
    for i in 0..NUM_PHILOSOPHERS {
        let s = stm.clone(); // STM 참조 복제 (Arc의 참조 카운트 증가)

        // 각 철학자를 별도 스레드에서 실행
        let th = std::thread::spawn(move || philosopher(s, i));
        v.push(th); // 스레드 핸들 저장 (나중에 join하기 위해)
    }

    // ===== 관측자 스레드 생성 및 시작 =====
    let obs_stm = stm.clone();
    let obs = std::thread::spawn(move || observer(obs_stm));

    println!("All threads started. Monitoring for inconsistencies...");

    // ===== 모든 철학자 스레드 완료 대기 =====
    for th in v {
        th.join().unwrap(); // 각 철학자 스레드가 완료될 때까지 대기
    }

    println!("All philosophers finished eating.");

    // ===== 관측자 스레드 완료 대기 =====
    obs.join().unwrap();

    println!("Program completed successfully - no inconsistencies detected!");
}
```

## Memory

Memory 타입에는 트랜잭션을 수행할 기본 함수를 정의한다. TL2는 512 바이트 메모리를 **스트라이프(8바이트 구역)** 라는 단위로 64개로 나누어 관리한다.

여기서 각 스트라이프의 락/버전 정보느 64비트로 구성되는데 최상위 비트에 락 상태를 기입하고 나머지 63비트에 버전 번호를 기입한다. 이 구조로 인해 단일 아토믹 연산으로 락 상태와 버전을 동시에 확인할 수 있다.

```rust
fn test_not_modify(&self, addr: usize, read_version: u64) -> bool {
    let current_value = self.lock_ver[addr >> 3].load(Ordering::Relaxed);
    current_value <= read_version
}
```

위의 함수와 같이 락이 걸려있으면 최상위 비트 값이 1이 되어 매우 커지므로 `current_value > read_version`이 되어 수정이 감지된다.

## ReadTrans

읽기는 다음 코드와 같이 작동한다.

```rust
pub fn load(&mut self, addr: usize) -> Option<[u8; STRIPE_SIZE]> {
    // 1. 첫 번째 일관성 검사
    if !self.mem.test_not_modify(addr, self.read_ver) {
        self.is_abort = true;
        return None;
    }
    
    fence(Ordering::Acquire);
    
    // 2. 실제 메모리 읽기
    let mut data = [0; STRIPE_SIZE];
    data.copy_from_slice(&self.mem.mem[addr..addr + STRIPE_SIZE]);
    
    fence(Ordering::SeqCst);
    
    // 3. 두 번째 일관성 검사
    if !self.mem.test_not_modify(addr, self.read_ver) {
        self.is_abort = true;
        return None;
    }
    
    Some(data)
}
```

1. 첫 번쨰 검사: 읽기 전에 메모리가 락X, 버전이 `read_ver` 이하인지 확인
    
2. 메모리 읽기: 실제 데이터를 복사, 메모리 펜스로 순서 보장
    
3. 두 번째 검사: 읽기 과정에서 다른 트랜잭션이 수정되었는지 확인 이 방식으로 락 없이도 일관된 읽기를 보장한. 다른 트랜잭션이 중간에 수정했다면 두 번째 검사에서 감지되어 재시도한다.
    

## WriteTrans

WriteTrans는 읽기-쓰기 트랜잭션을 처리하는 가장 복잡한 구조체다. 지연된 쓰기와 2단계 커밋 프로토콜을 구현한다.

### 지연된 쓰기

```rust
pub fn store(&mut self, addr: usize, val: [u8; STRIPE_SIZE]) {
    self.write_set.insert(addr, val);
}
```

`store` 연산은 실제 메모리에 즉시 쓰지 않고 `write_set`에만 저장한다. 실제 쓰기는 트랜잭션이 성공적으로 커밋될 때까지 지연된다. 이렇게 하면 중간에 충돌이 발생해도 실제 메모리는 변경되지 않아 롤백이 간단하다.

### Read-Your-Write 의미

```rust
pub fn load(&mut self, addr: usize) -> Option<[u8; STRIPE_SIZE]> {
    self.read_set.insert(addr);
    
    // write-set에 있으면 해당 값 반환
    if let Some(data) = self.write_set.get(&addr) {
        return Some(*data);
    }
    
    // 없으면 실제 메모리에서 읽기 (ReadTrans와 동일)
    // ...
}
```

트랜잭션 내에서 자신이 쓴 값을 읽을 때는 `write_set`의 값을 반환한다. 이를 통해 트랜잭션 내에서 일관된 메모리 뷰를 제공한다. 동시에 읽은 주소는 `read_set`에 기록하여 나중에 검증할 때 사용한다.

## STM

STM 구조체는 전체 트랜잭션 시스템의 진입점이다. TL2의 핵심인 5단계 커밋 프로토콜을 구현한다.

### 5단계 커밋 프로토콜

```rust
pub fn write_transaction<F, R>(&self, f: F) -> Option<R> {
    loop {
        // 1단계: 투기적 실행
        let mut tr = WriteTrans::new(unsafe { &mut *self.mem.get() });
        let result = match f(&mut tr) {
            STMResult::Ok(val) if !tr.is_abort => val,
            _ => continue,
        };
        
        // 2단계: 락 획득
        if !tr.lock_write_set() { continue; }
        
        // 3단계: 전역 클락 증가
        let ver = 1 + tr.mem.inc_global_clock();
        
        // 4단계: read-set 검증
        if tr.read_ver + 1 != ver && !tr.validate_read_set() {
            continue;
        }
        
        // 5단계: 커밋
        tr.commit(ver);
        return Some(result);
    }
}
```

**1단계 - 투기적 실행**: 사용자 코드를 실행하여 `read_set`과 `write_set`을 구성한다. 실제 메모리는 수정하지 않고 시뮬레이션만 한다.

**2단계 - 락 획득**: `write_set`의 모든 주소에 대해 락을 획득한다. All-or-Nothing 원칙으로 하나라도 실패하면 모든 락을 해제하고 재시도한다.

```rust
fn lock_write_set(&mut self) -> bool {
    for (addr, _) in self.write_set.iter() {
        if self.mem.lock_addr(*addr) {
            self.locked.push(*addr);
        } else {
            return false;  // 하나라도 실패하면 전체 실패
        }
    }
    true
}
```

**3단계 - 전역 클락 증가**: 전역 클락을 원자적으로 증가시켜 새로운 버전 번호를 할당한다. 이 버전 번호는 이 트랜잭션의 커밋 시간을 나타낸다.

**4단계 - read-set 검증**: 가장 중요한 최적화가 포함된 단계다.

```rust
if tr.read_ver + 1 != ver && !tr.validate_read_set()
```

이 조건의 핵심은 **빠른 경로(Fast Path)**다. 만약 [`tr.read`](http://tr.read)`_ver + 1 == ver`라면 이 트랜잭션이 시작된 이후 다른 트랜잭션이 커밋하지 않았다는 의미이므로, 복잡한 `read_set` 검증을 생략할 수 있다.

그렇지 않다면 세밀한 검증을 수행한다:

```rust
fn validate_read_set(&self) -> bool {
    for addr in self.read_set.iter() {
        if self.write_set.contains_key(addr) {
            // 자신이 락을 가진 주소: 버전만 확인
            let current_ver = self.mem.get_addr_ver(*addr);
            if current_ver > self.read_ver { return false; }
        } else {
            // 다른 주소: 락과 버전 모두 확인
            if !self.mem.test_not_modify(*addr, self.read_ver) {
                return false;
            }
        }
    }
    true
}
```

자신이 락을 가진 주소와 그렇지 않은 주소를 다르게 처리한다. 자신이 락을 가진 경우 다른 트랜잭션이 수정할 수 없으므로 버전만 확인하면 된다.

**5단계 - 커밋**: 실제 메모리에 쓰기를 수행하고 락을 해제한다.

```rust
fn commit(&mut self, ver: u64) {
    // 1. 실제 메모리에 쓰기
    for (addr, val) in self.write_set.iter() {
        self.mem.mem[*addr..*addr + STRIPE_SIZE].copy_from_slice(val);
    }
    
    fence(Ordering::Release);
    
    // 2. 락 해제 및 버전 업데이트
    for (addr, _) in self.write_set.iter() {
        let idx = addr >> self.mem.shift_size;
        self.mem.lock_ver[idx].store(ver, Ordering::Relaxed);
    }
}
```

메모리 쓰기 완료 후 락 비트를 0으로, 버전을 새 버전으로 원자적으로 설정한다.

## TL2의 핵심 특성

### 데드락 방지

TL2는 구조적으로 데드락이 불가능하다. 전통적인 락에서는 스레드 A가 락 X를 가지고 락 Y를 기다리고, 스레드 B가 락 Y를 가지고 락 X를 기다리는 상황이 발생할 수 있다.

하지만 TL2에서는 All-or-Nothing 락 획득 방식으로 부분적 락 획득 상태가 존재하지 않는다. 필요한 모든 락을 획득할 수 없으면 기존 락들을 모두 해제하고 처음부터 재시도한다.

### ABA 문제 해결

단순한 락 확인만으로는 ABA 문제가 발생할 수 있다. 값이 A에서 B로 변경된 후 다시 A로 돌아왔을 때, 값만 보면 변화가 없는 것처럼 보인다. TL2는 버전 번호를 통해 이를 해결한다. 값이 같아도 버전이 증가했다면 변경이 감지된다.

### 높은 동시성

읽기 트랜잭션은 락을 사용하지 않아 여러 읽기가 동시에 실행될 수 있다. 쓰기 트랜잭션도 커밋 단계에서만 락을 보유하므로 락 경합이 최소화된다.

## 식사하는 철학자 문제에서의 동작

철학자 문제에서 TL2의 동작을 구체적으로 보면, 각 철학자가 두 포크를 동시에 잡으려 할 때:

1. **투기적 실행**: 두 포크 상태를 확인하고 둘 다 비어있으면 사용 중으로 설정하는 계획을 세운다.
    
2. **락 획득**: 두 포크에 대한 편집권을 얻으려 시도한다. 하나라도 실패하면 포기하고 재시도한다.
    
3. **검증**: 포크 상태를 읽었을 때와 지금이 일치하는지 확인한다.
    
4. **커밋**: 성공하면 실제로 포크 상태를 변경하고 편집권을 반납한다.
    

이 과정을 통해 데드락 없이 안전하게 동시성 문제를 해결할 수 있다.