[운영체제] 프로세스 동기화 기법 (저수준)

1. 소프트웨어적 해결

그냥 변수를 읽고 쓰는 것만으로 상호 배제를 만들 수 있을까?
역사적으로 원자적 명령 없이도 가능하다는 것을 증명한 것에 의미가 있다.

피터슨 알고리즘

2개 프로세스(P0, P1)를 위한 해법이다. 공유 변수 두 개를 쓴다.

// 프로세스 i 의 코드 (상대는 j)\

flag[i] = true;                    // ① 나 들어가고 싶어
turn = j;                          // ② 근데 너 먼저 해 (양보)
while (flag[j] && turn == j) { }   // ③ 상대가 원하고 + 상대 차례면 대기

// ── 임계구역 ──

flag[i] = false;                   // ④ 나감

핵심 아이디어는 ②의 양보(turn = j) 다. 두 프로세스가 동시에 진입을 시도해도, turn에는 마지막에 쓴 값 하나만 남는다. 따라서 둘 중 정확히 하나만 while 조건을 빠져나가고, 다른 하나는 대기한다.

3대 요건 검증

• 상호 배제: 둘 다 임계구역에 있으려면 turn이 동시에 두 값이어야 하는데 불가능하므로 만족한다
• 진행: 임계구역이 비면 flag[j]가 false가 되어 상대가 즉시 진입 가능하다
• 유한 대기: 한 번 양보한 뒤에는 상대가 최대 한 번만 먼저 들어갈 수 있다

한계 : 하드웨어의 필요성

개념적으로 완전하지만 실무에서 쓰지 않는다.

• 확장성 : 기본형은 2개 프로세스 전용이다. N개로 일반화하면 복잡하고 무겁다.
• 바쁜 대기 (busy-wait) : while을 계속 돌며 CPU를 태운다.
• 메모리 재배열 / 가시성 : 메모리 연산이 작성한 순서대로 즉시 다른 코어에 보이는 것을 전제한다. 그러나 현대 CPU는 명령 재배열과 스토어 버퍼 때문에 flag[i]=true와 turn=j의 순서가 다른 코어에는 뒤바뀌어 보일 수 있다. 그 결과 메모리 배리어 없이는 알고리즘이 깨진다.

순서 보장을 하드웨어가 해주지 않는 한 안전하지도, 효율적이지도 않다.

2. 하드웨어적 지원 (원자적 명령어)

레이스 컨디션의 발생 원인은 읽기-수정-쓰기 가 중간에 끼어들 수 있기 때문이다.
그렇다면 읽고 → 수정하고 → 쓰기를 CPU가 한 번에, 중간에 아무도 못 끼어들게 실행하는 단일 기계어 명령을 제공하면 된다.
이것이 원자적 명령어이며, 모든 고수준 동기화 도구의 토대다.

대표적으로 TAS와 CAS가 있다.

🎈 Test-and-Set (TAS)

메모리의 값을 읽어서 반환함과 동시에 true(1)로 설정하는 동작을 하나의 원자적 명령으로 수행한다.

// 아래 전체가 '원자적으로' 실행된다
bool test_and_set(bool *target) {
    bool old = *target;
    *target = true;
    return old;
}

이걸로 스핀락을 만든다.

while (test_and_set(&lock)) { }   
// lock이 false면 true로 바꾸고 false 반환 → 진입

// ── 임계구역 ──

lock = false;

읽기와 쓰기가 원자적으로 묶여 있어, 두 스레드가 동시에 lock을 false로 보고 둘 다 진입하는 일이 불가능하다.

TAS 의 성능 문제

원자적 명령으로 상호 배제는 보장되지만, 스핀락은 바쁜 대기라 두 가지 비용이 있다.

• CPU 낭비 : 락을 기다리는 동안 아무 일도 안 하면서 루프를 돈다. 대기가 길면 손해.
• 캐시 라인 튕김 : 여러 코어가 동시에 스핀하면 test_and_set이 매번 쓰기를 하므로, 그 캐시 라인의 소유권이 코어들 사이를 계속 오가며 성능이 급락한다.

해결로 TTAS (Test-and-Test-and-Set) 를 쓴다
먼저 평범한 읽기로 락이 비어 보이는지 확인하고 비어 보일 때만 TAS를 시도한다.

🎈 Compare-and-Swap (CAS, lock-free)

현재 값이 예상 값과 같을 경우에만 새 값으로 업데이트한다. 만약 다른 스레드에서 값을 이미 변경했으면 업데이트를 하지 않으므로 동시성을 보장한다.

이 변수가 expected 값일 때에만 new 값으로 변경 를 원자적으로 수행하고, 성공 여부를 돌려준다.

// 아래 전체가 원자적으로 실행된다
int compare_and_swap(int *addr, int expected, int new_val) {
    int old = *addr;
    if (old == expected) *addr = new_val;
    return old;   // old == expected 였으면 성공
}

락을 거는 대신 값을 바꿔보고 그사이 누가 건드렸으면 실패 → 재시도 하는 패턴을 만든다.

do {
    old = counter;
} while (compare_and_swap(&counter, old, old + 1) != old);  

이 방식은 락을 잡지 않으므로 lock-free라 부르며, 데드락이 원천적으로 없다.
TAS보다 일반적이고 강력해 lock-free 자료구조의 기반이 된다.

ABA 문제

값이 A → B → A로 바뀌어 원래대로 돌아오면, CAS는 안 바뀌었다 라고 판단해 그 사이의 변경을 놓친다.

해결은 버전 스탬프를 함께 비교하는 것이다. 값에 카운터를 붙여 (값, 버전) 쌍으로 CAS하면 A(v1) → A(v3) 처럼 버전이 달라져 변경을 탐지할 수 있다.

(JPA @Version 기능이 이 발상이다.)

원자적 명령의 한계

• 개발자가 직접 스핀락을 짜는 것은 번거롭고 실수하기 쉽다.
• 바쁜 대기 문제가 남는다 (블로킹으로 재우려면 OS의 도움이 필요)
• N개 자원 허용, 조건이 만족될 때까지 대기 같은 더 다양한 구현을 하기 어렵다.

그래서 이 원자적 명령어 위에, 블로킹까지 지원하고 의미가 풍부한 고수준 추상화 (뮤텍스, 세마포, 모니터)를 세운다.