Brain피터슨 알고리즘 (Peterson's Algorithm)
핵심 인사이트 (3줄 요약)
- 본질: 피터슨 알고리즘 (Peterson's Algorithm)은 임계 구역 (Critical Section) 진입을 두 개의 공유 변수인 깃발 (
flag)과 차례 (turn)만을 사용하여 소프트웨어적으로만 제어하는 가장 우아한 2-프로세스 동기화 알고리즘이다.- 가치: 상호 배제 (Mutual Exclusion), 진행 (Progress), 한정된 대기 (Bounded Waiting)의 세 가지 필요조건을 동시에 100% 충족하는 최초의 최소화 증명 가능 알고리즘으로, 이후 하드웨어 기반 락의 이론적 토대가 되었다.
- 융합: 현대 CPU의 비순차 실행 (Out-of-Order Execution)과 컴파일러 최적화로 인해 이 알고리즘의 순서가 재배치될 수 있으므로, 메모리 배리어 (Memory Barrier) 또는 하드웨어 원자 명령어 (TAS, CAS)가 반드시 병행되어야 한다.
Ⅰ. 개요 및 필요성 (Context & Necessity)
- 개념: 1981년 게리 피터슨 (Gary L. Peterson)이公开发표한 알고리즘으로, 하드웨어 명령어 없이 오직 공유 변수 두 개 (
flag,turn)만으로 임계 구역 문제를 완벽히 해결한다. ($N$개 프로세스로 확장 가능한 데커 알고리즘의 2프로세스 단순화 버전이다.) - 필요성: 하드웨어의 도움 없이 "누가 먼저 들어갈 것인가?"를 결정하는 문제는, 단순히
if문과while문으로 짜면 "자기가 확인하는 찰나에 다른 놈이 들어와서 꼬이는 타이밍"이 존재한다. 이 미세한 타이밍을 이론적으로 완벽히 차단하는 최소한의 논리적 구조가 필요했다. - 💡 비유: 외나무다리에서 두 운전자가 만났을 때, 둘 다 "내가 먼저 건너갈래!" 하고 클랙션(flag)을 누르되, 마지막에 "你先走(당신 먼저 가세요)"라고 말하는(turn) 사람이 결국 상대를 통과시키는 양보의 미덕이다. 동시에 "你先走"를 외치더라도 turn 변수가 마지막에 덮어쓴 쪽이 상대를 보내주게 되어 충돌이 없다.
- 등장 배경: 1965년 데이크스트라의 세마포어 해결책은 수학적이나 복잡했다. 피터슨은 "기권(yield)이라는 한 줄의 코드"로 이를 압축하여, 1981년 ACM Transactions에서 정식 발표한 뒤로 전 세계OS 학부 수업의 바이블이 되었다.
[피터슨 알고리즘의 "你先走(turn)" 양보 메커니즘]
[ P0 (운전자 A) ] [ P1 (운전자 B) ]
1. "내가 먼저!" (flag[0] = true)
2. "你先走!" (turn = 1) 1. "내가 먼저!" (flag[1] = true)
2. "你先走!" (turn = 0)
[ 핵심 3단계:while 문 검증 (Critical 검문소) ]
P0의 내면: "P1이 깃발을 들었나(flag[1]==T), turn이 1(P1)이니?
→ 그럼 내가 양보. P1이 먼저 건너갈 때까지 대기."
P1의 내면: "P0이 깃발을 들었나(flag[0]==T), turn이 0(P0)이니?
→ 그럼 내가 양보. P0이 먼저 건너갈 때까지 대기."
결론: turn 변수가 마지막에 덮어쓴 쪽이
항상 상대방을 통과시키는 양보자(turn==자신)가 되어
둘 다 동시에 진입하는 것을 구조적으로 원천 차단!
[다이어그램 해설] 피터슨 알고리즘의 핵심은 turn이라는 양보 변수에 있다. 둘 다 먼저겠다면서 깃발을 세울 때, 마지막에 turn = 상대방으로 덮어쓴 프로세스가 항상 양보자가 된다. 둘 다 동시에 turn을 덮어쓸 때, 마지막 쓰기가 이기는 것이 아니라 turn의 최종값이 "누가 양보했는지"를 결정하는 핵심 비트다. 이 두 단계의 협상과정이야말로 경쟁 조건 없이 임계 구역을 통과하는 SOFTWAREONLY의 최종 해법이다.
- 📢 섹션 요약 비유: 서로 먼저 들어가겠다고 난투하는 세관에서, 마지막에 "네가 먼저どうぞ(turn)"라고 말한 사람이 양보하는 형평성 규칙입니다. 동시에 "どうぞ"를 외치더라도 상대방의 "你先走"에 이끌려 안전하게 순서가 결정됩니다.
Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)
알고리즘의 C 코드와 3가지 조건 증명
피터슨 알고리즘은 단 2개의 공유 변수(flag[2], turn)만으로 임계 구역 진입을 통제한다.
// 공유 변수 (Shared Variables)
bool flag[2] = {false, false}; // "내가 들어가겠다고 선언!"
int turn; // "누가 양보했는가?"
// 프로세스 i (0 또는 1)
// 프로세스 j는 다른 쪽 (1 - i)
void enter_critical_section(int i) {
int j = 1 - i; // 상대의 프로세스 번호
flag[i] = true; // 1. 내 깃발을 세운다 (진입 의사 표시)
turn = j; // 2. 일단 상대방에게 양보한다 (대인배 모드)
// 3. 상대가 깃발을 들었으면서, 차례도 상대방이면 무한 대기!
while (flag[j] && turn == j) {
/* do nothing (Busy Waiting) */
}
// while을 뚫었다 = 임계 구역 진입 성공!
}
void leave_critical_section(int i) {
flag[i] = false; // 4. 임계 구역 완료. 깃발을 내린다 (퇴장)
}
상호 배제 100% 증명 (Proof of Mutual Exclusion)
- 초기 상태: 두 프로세스가 임계 구역에 동시에 진입하려면,
while루프를 동시에 빠져나와야 한다. while루프를 빠져나오려면flag[j] == false(상대가 나갔음) 또는turn != j(양보자가 내가 아니게 됨)이어야 한다.flag[0]과flag[1]이 동시에true일 때,turn의 값은 마지막으로 덮어쓴 프로세스만 결정한다.- 따라서 두 프로세스가 동시에
while을 빠져나올 수 없으며, 오직 하나만 진입한다. (상호 배제 만족)
진행 (Progress) 증명
- P1이 임계 구역을 나가고자
flag[1] = false를 실행하면, - P0의
while(flag[1] && turn == 1)조건에서flag[1] == false이 되어while(false && ...)이 되어 즉시 탈출한다. - 따라서 빈 임계 구역에 들어가려는 프로세스는 즉시 진입할 수 있다. (진행 만족)
한정된 대기 (Bounded Waiting) 증명
- P0가 임계 구역에 진입한 뒤 P1이 진입을 시도하면, P1은
flag[1] = true; turn = 0로 설정하고 대기한다. - P0가 퇴장하며
flag[0] = false를 실행하면, P1은 대기 중이던while을 빠져나와 진입한다. - P1 진입 후 P0가 다시 시도하면, P1의
flag[1] = true때문에 P0은 대기해야 한다. 이는 P0의 대기 횟수가 1회로 제한됨을 의미한다. (한정된 대기 만족)
┌─────────────────────────────────────────────────────────────────────┐
│ 피터슨 알고리즘의 타임라인 동작 시각화 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ P0: ──flag[0]=T──turn=1──[while: F&&T=F]──[CRITICAL]──flag[0]=F─│
│ P1: ──────────────────────flag[1]=T──turn=0──[while: T&&T=T]──│
│ 대기 │
│ 시간 ───────────────────────────────────────────────────────────▶ │
│ │
│ P0의 enter: flag[0]=T, turn=1 → while(T && T) = T → 대기! │
│ P0의 leave: flag[0]=F → P1의 while(T && T) = F → P1 진입! │
└─────────────────────────────────────────────────────────────────────┘
[다이어그램 해설] P0이 먼저 깃발을 세우고 turn=1로 양보하면, P1이 뒤에 와서 turn=0으로 덮어쓴다. 이때 P1의 while 조건은 flag[0]=T && turn=0이 되어 T가 되어 P1이 대기하고, P0이 먼저 진입한다. P0이 퇴장하면 P1이 진입하는 완벽한 교대 시퀀스가 형성된다. 이 교대(Alternation)가 바로 한정된 대기의 핵심 증거다.
- 📢 섹션 요약 비유: 교차로에서 두 차가 동시에 진입하려 할 때, 마지막에 "你先走(네가 먼저)"를 외친 차가 멈추고 양보하는 형평성 게임입니다. 동시에 외치더라도 서로의 목소리를 듣는 순간 양보가 성립하여 충돌이 발생하지 않습니다.
Ⅲ. 융합 비교 및 다각도 분석 (Comparison & Synergy)
피터슨 알고리즘 vs 하드웨어 TAS (Test-And-Set)
현대 멀티코어 환경에서 피터슨 알고리즘의 운명은 완전히 달라졌다.
| 비교 항목 | 피터슨 알고리즘 (소프트웨어) | Test-And-Set (하드웨어) |
|---|---|---|
| 자원 | 변수 2개(flag, turn)만 사용 | CPU 1개 원자적Latch 명령 |
| 확장성 | 2개 프로세스만 가능 (N 확장 시 데커 등 무거움) | 스레드 1만 개도 while 1줄로 통제 가능 |
| 현대 CPU 적용 | ❌ 실패 (Out-of-Order에 순서 뒤틀림) | ✅ 성공 (버스 락으로 물리적 차단) |
| CPU 낭비 | 대기 중 Busy Wait (무한 루프) | 대기 중 Sleep 또는 Spin |
Out-of-Order Execution의 살인적 위협
현대 CPU의 비순차 실행은 피터슨 알고리즘의 논리적 증명을 무너뜨린다.
- 문제: 컴파일러 또는 CPU가 코드의 실행 순서를 최적화한다.
- 시나리오: P0이
flag[0]=true보다turn=1을 먼저 실행하도록 재배치하면?- P0이
turn=1을 먼저 실행한 뒤, CPU가 최적화를 위해flag[0]=true를 나중에 실행한다. - 이 찰나에 P1이
flag[1]=true; turn=0을 모두 실행하고 while을评估한다. - P1은
flag[0]=false를 보게 되어 while을 빠져나와 진입한다. - P0도 곧
flag[0]=true를 세우고 진입한다. 동시 진입 인정!
- P0이
┌─────────────────────────────────────────────────────────────────────┐
│ Out-of-Order 실행에 의한 피터슨 알고리즘 붕괴 시나리오 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ 정상 순서 (피터슨의 가정): │
│ P0: flag[0]=T → turn=1 → while() 대기 │
│ P1: flag[1]=T → turn=0 → while() 대기 (P0 진입) │
│ │
│ CPU가 순서를 뒤집은 경우 (Out-of-Order): │
│ P0: turn=1 ──▶ flag[0]=T (순서 뒤집힘!) │
│ ────────────────────────▶ P1이 flag[0]=F를 보고 진입! │
│ P1: flag[1]=T → turn=0 → while(T && F=F) → 진입 성공! │
│ ────────────────────────▶ P0도 곧 flag[0]=T 후 진입! │
│ 🚨 두 프로세스가 동시에 임계 구역 진입! 붕괴! │
└─────────────────────────────────────────────────────────────────────┘
메모리 배리어 (Memory Barrier) 의한 구원
이 문제를 해결하려면 컴파일러에게 "이 두 줄은 순서를 바꾸지 마라!"고 명령해야 한다.
void enter_critical_section(int i) {
int j = 1 - i;
flag[i] = true;
__asm__ __volatile__ ("mfence" : : : "memory"); // 메모리 배리어!
// 위 명령어는 이전의 모든 메모리 쓰기가 다음 것보다 먼저 완료됨을 보장.
turn = j;
while (flag[j] && turn == j) { /* do nothing */ }
}
- 📢 섹션 요약 비유: 피터슨 알고리즘은 종이 위의 도덕 규범이고, Out-of-Order CPU는 순서를 마음대로 바꾸는 성격 급한 사람입니다. 메모리 배리어는 "네가 먼저 말한 것부터 해라, 순서 바꾸지 마라!"고 강제하는 엄격한 선생님의 지시입니다.
Ⅳ. 실무 적용 및 기술사적 판단 (Strategy & Decision)
실무 시나리오
- 임베디드/RTOS 환경에서의 활용: 하드웨어 TAS 명령이 없거나 비싸게 매기는 소형 임베디드 시스템에서는, 메모리 배리어를 추가한 피터슨 알고리즘이 여전히 유효하다. 특히 단일 코어에서 인터럽트 기반 동기화에 활용된다.
- 교육적 가치: 피터슨 알고리즘은 임계 구역 문제의 세 가지 조건(상호 배제, 진행, 한정된 대기)을 어떻게 하면 최소화한 변수로 충족할 수 있는지를 보여주는 가장优雅한 교과서 예제다. 실무에서 직접 쓰는 것은 드물지만, 동시성 제어의 기본기로서 필수다.
┌─────────────────────────────────────────────────────────────────────┐
│ 동시성 제어 알고리즘 선정 아키텍처 결정 트리 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ [요구사항: 2개 스레드의 임계 구역 동기화] │
│ │ │
│ ▼ │
│ [ 하드웨어 원자 명령(TAS/CAS)이 있는가? ] │
│ ├─ 예 ──▶ [ ✅ 하드웨어 락 사용 (현대적 정답) ] │
│ │ - std::mutex, std::atomic 등 │
│ │ - Out-of-Order 안전, 성능 우수 │
│ │ │
│ └─ 아니오 (순수 소프트웨어만 가능) │
│ │ │
│ ▼ │
│ [ 2개 프로세스인가? ] │
│ ├─ 예 ──▶ [ ✅ 피터슨 + 메모리 배리어 ] │
│ │ - 임베디드, 단일 코어 환경 │
│ └─ 아니오 ──▶ [ ⚠️ 데커/표시 알고리즘 ] │
│ - N 확장 시 복잡도 폭발 주의 │
└─────────────────────────────────────────────────────────────────────┘
[다이어그램 해설] 피터슨 알고리즘은 하드웨어가 약하거나 특수한 환경(교육, 임베디드, 단일 코어)에서만 빛을 발한다. 최신 멀티코어 서버 환경에서는 std::mutex나 std::atomic이 피터슨 알고리즘보다 안전하고高性能이다. 실무 엔지니어는 "언제 하드웨어 도움 없이 소프트웨어만으로同步를 해야 하는가?"를 구분할 줄 알아야 한다.
- 📢 섹션 요약 비유: 피터슨 알고리즘은 기본기가 탄탄한 유학 파이팅입니다. 시험 준비(교육)나 도구(TAS)가 부족한 환경(임베디드)에서는 최고입니다. 하지만 대규모 회사(멀티코어 서버)에서는 관리 시스템(std::mutex)이 구조적으로 더 안전합니다.
Ⅴ. 기대효과 및 결론 (Future & Standard)
기대효과
피터슨 알고리즘은 하드웨어 명령어의 도움 없이도 공유 자원의 경쟁 조건을 완전히 제거할 수 있음을 수학적으로証明했다. 이最小化의 정신은 이후 lock-free 자료구조와 비교-교환(CAS) 알고리즘의 이론적 토대가 되었으며, 임계 구역 문제 해결의 모든 가능성을 탐구한歷史적里程碑다.
결론 및 미래 전망
피터슨 알고리즘은 1981년 당시에는革命적이었으나, 현대 CPU의 비순차 실행과 다중 코어 환경에서는 하드웨어 도움 없이는 안전하게 동작하지 않는다. 그러나 이 알고리즘이 提出한 "flag + turn"이라는 2변수 제어 메커니즘의 아이디어는, 이후Compare-And-Swap (CAS) 같은 하드웨어 원자 명령어의 설계 철학으로 직결된다. 궁극적으로 임계 구역 문제는 하드웨어와 소프트웨어가 협력할 때 가장 아름답게 해결되며, 피터슨 알고리즘은 그 협력의 출발점이었다.
- 📢 섹션 요약 비유: 피터슨 알고리즘은 自転車 발명 시절의 두 발로 발을 굴러前进하는 방식입니다. 간단하고优雅하지만, 현대의 고속 도로(멀티코어)에서는 자동차(하드웨어 락)가 필수적입니다. 하지만 自転車の 基本 원리는 현대 자동차 변속기의 핵심 설계 철학으로 살아 있습니다.
📌 관련 개념 맵 (Knowledge Graph)
| 개념 명칭 | 관계 및 시너지 설명 |
|---|---|
| 데커 알고리즘 (Dekker's Algorithm) | 피터슨보다 먼저 등장한 2프로세스 알고리즘으로, 피터슨이 이를 더 우아하게 압축했다. |
| 비순차 실행 (Out-of-Order Execution) | 피터슨 알고리즘의 소프트웨어적 안전성을 무너뜨리는 현대 CPU 최적화 기법이다. |
| 메모리 배리어 (Memory Barrier) | Out-of-Order에 의한 순서 뒤집기를防止하는 하드웨어/컴파일러 명령어다. |
| Test-And-Set (TAS) | 피터슨의 소프트웨어적 방법을hardware적으로 1클럭에 完成시키는 원자적Latch 명령어다. |
| 상호 배제 (Mutual Exclusion) | 피터슨이 flag와 turn 변수로 Achieved하려는 세 가지 필요조건의 첫 번째다. |
👶 어린이를 위한 3줄 비유 설명
- 두 명的小朋友가 같은 장난감(공유 자원)을都想玩 때, 둘 다 "내가 먼저!"(flag)라고 외치고, 마지막에 "네가 먼저玩"(turn)라고 말한 사람이 양보하는 게임이에요.
- 그런데 만약某一方이 "네가 먼저"를 말한 후에 급하게 말을 바꾸려 하면(Out-of-Order), 둘 다 동시에 장난감에 손을 대서 싸움이 나요.
- 그래서 선생님(메모리 배리어)이 "말한 순서대로만 해, 바꾸지 마!"라고 규칙을 세워주면, 피터슨 게임은 완벽하게 작동해요!