임베디드 스터디 - 상호배제와 임계구역, 피터슨 알고리즘

경쟁 조건(Race Condition)이란

• 두 스레드가 공유 자원에 동시에 접근할 때 실행 순서에 따라 결과가 달라지는 현상
• counter++는 코드 한 줄이지만 어셈블리 수준에서는 3단계로 분해된다:

LOAD   R0, [counter]   ; 메모리에서 값 읽기
ADD    R0, R0, #1      ; 레지스터에서 +1 계산
STORE  [counter], R0   ; 결과를 메모리에 저장

• 두 스레드가 동시에 LOAD를 수행하면 같은 값을 읽게 되고, 나중에 STORE한 쪽이 먼저 쓴 값을 덮어씌워 버린다.

---

임계구역(Critical Section)

• 공유 자원에 접근하는 코드 구간을 임계구역 이라 한다.
• 임계구역 문제를 올바르게 해결하려면 아래 3가지 조건을 모두 만족해야 한다.

조건	이름	의미
1	상호배제	임계구역 안에 오직 한 스레드만 존재
2	진행	임계구역이 비어 있을 때 대기 중인 스레드는 반드시 진입할 수 있어야 함
3	한정대기	특정 스레드가 임계구역 진입을 무한정 기다리지 않아야 함

• 조건 ④가 깨지면 → 데드락 (DeadLock) 발생
• 조건 ⑤가 깨지면 → 기아현상 (Starvation) 발생

---

피터슨 알고리즘(Peterson’s Algorithm)

• 하드웨어 지원 없이 소프트웨어만으로 두 스레드 간 상호배제를 구현하는 알고리즘
• 공유 변수 두 개를 사용한다:
  • flag[2] — 각 스레드의 임계구역 접근 의사 표시 (“나 들어가고 싶다”)
  • turn — 양보할 스레드 번호 (“상대방에게 양보”)

// 스레드 i (상대방 j = 1 - i)
flag[i] = true;        // 진입 의사 표시
turn = j;              // 상대방에게 양보
while (flag[j] && turn == j);  // 상대가 원하고 AND 내가 양보 중이면 대기
// --- 임계구역 ---
flag[i] = false;       // 진입 의사 철회

turn = j (양보)로 설정하는 이유

• turn = i (내 차례 주장)로 설정하면 두 스레드가 동시에 진입 시도 시 상호배제 위반이 발생한다.
• turn = j (상대에게 양보)로 설정하면, 두 스레드가 동시에 진입할 때 마지막으로 turn을 쓴 쪽이 양보한 상태로 남아 대기한다.
• 결과적으로 반드시 한 쪽만 임계구역에 진입하게 된다.

동시 진입 시나리오

T0: flag[0]=true, turn=1   →  T0이 마지막으로 turn 작성
T1: flag[1]=true, turn=0   →  T1이 마지막으로 turn 작성

turn == 0 이면 → T0 대기, T1 진입
turn == 1 이면 → T1 대기, T0 진입

---

현대 시스템에서의 한계

피터슨 알고리즘은 3가지 조건을 모두 만족하지만, 현대 멀티코어 환경에서는 두 가지 문제가 발생한다.

문제	원인	해결책
컴파일러 캐시	컴파일러가 공유 변수를 레지스터에 캐시	volatile 키워드
명령어 재배치	CPU가 Out-of-Order로 실행 순서 변경	메모리 배리어 (Memory Barrier)

• 메모리 배리어 예시:

flag[0] = true;
__sync_synchronize();          // 이 줄 이전 쓰기가 반드시 먼저 완료됨을 보장
turn = 1;

• 현대 OS는 피터슨 대신 하드웨어 원자적 명령어(test-and-set, compare-and-swap)를 활용한다.