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

동시성 프로그래밍에서 공유 자원에 대한 안전한 접근은 항상 중요한 과제다. 전통적으로 뮤텍스 락과 같은 비관적 락(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은 중요한 특징 네 가지를 가지고 있는데

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

TL2 알고리즘

TL2의 타입은 아래와 같다.

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

코드

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

tl2.rs:

// 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:

// 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비트에 버전 번호를 기입한다. 이 구조로 인해 단일 아토믹 연산으로 락 상태와 버전을 동시에 확인할 수 있다.

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

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

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)
}

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

WriteTrans

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

지연된 쓰기

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

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

Read-Your-Write 의미

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단계 커밋 프로토콜

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 원칙으로 하나라도 실패하면 모든 락을 해제하고 재시도한다.

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 검증: 가장 중요한 최적화가 포함된 단계다.

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

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

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

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단계 - 커밋: 실제 메모리에 쓰기를 수행하고 락을 해제한다.

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의 동작을 구체적으로 보면, 각 철학자가 두 포크를 동시에 잡으려 할 때:

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

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

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

Comments

Programming

공평한 배타 제어

More from this blog

락프리 데이터 구조와 알고리즘

공평한 배타 제어

KernelSnitch[논문 리뷰]

멀티태스크와 액터 모델

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

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

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

TL2: 실용적인 STM 구현

STM의 특징

TL2 알고리즘

코드

Memory

ReadTrans

WriteTrans

지연된 쓰기

Read-Your-Write 의미

STM

5단계 커밋 프로토콜

TL2의 핵심 특성

데드락 방지

ABA 문제 해결

높은 동시성

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

Command Palette

Comments

Programming

공평한 배타 제어

More from this blog

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

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

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

TL2: 실용적인 STM 구현

STM의 특징

TL2 알고리즘

코드

Memory

ReadTrans

WriteTrans

지연된 쓰기

Read-Your-Write 의미

STM

5단계 커밋 프로토콜

TL2의 핵심 특성

데드락 방지

ABA 문제 해결

높은 동시성

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