진행 (Progress)

핵심 인사이트 (3줄 요약)

본질: 진행 (Progress)은 임계 구역(Critical Section) 보호 알고리즘이 갖춰야 할 3대 필수 조건 중 두 번째로, **"임계 구역이 비어 있고 들어가길 원하는 프로세스들이 있다면, 그중 하나는 반드시 무한한 지연 없이 진입해야 한다"**는 활력(Liveness) 보장 원칙이다.

가치: 락(Lock)을 너무 강하게 걸거나 설계가 잘못되어 프로세스들이 서로 "네가 먼저 가"라며 양보만 하다가 아무도 임계 구역에 들어가지 못하고 시스템이 영원히 멈추는 교착 상태(Deadlock)나 라이브락(Livelock)을 수학적으로 원천 금지한다.

융합: 상호 배제(Mutual Exclusion)가 데이터의 '안전성'을 위한 브레이크라면, 진행(Progress)은 시스템의 '생산성'을 위한 엑셀레이터다. 이 둘 사이의 모순을 해결하기 위해 피터슨 알고리즘은 turn이라는 양보 변수를 통해 진행 조건을 완벽히 충족시켰다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

개념: 임계 구역 문제(Critical Section Problem)를 해결하는 알고리즘이 정당성을 인정받기 위한 데이크스트라의 3대 조건(상호 배제, 진행, 한정된 대기) 중 하나다.
필요성: 개발자가 데이터가 깨지는 것(Race Condition)이 너무 무서운 나머지, "아무도 못 들어가게 문을 철저히 잠가버리자"라고 코드를 짜면 데이터는 안전하겠지만 프로그램은 0%에서 평생 멈춰있는다. 또한, 남을 배려한답시고 서로 양보만 하는 로직을 짜면 핑퐁 치다가 아무도 문을 열지 못한다. 즉, "들어갈 놈이 있으면 반드시 누군가는 들어간다"는 강제적 전진(Progress)의 보증 수표가 필요했다.
💡 비유: 좁은 문(임계 구역) 앞에 두 명의 신사가 섰을 때, 서로 **"먼저 들어가시죠" "아닙니다. 먼저 들어가시죠"**라며 10년 동안 문 앞에서 인사만 하고 아무도 방에 들어가지 못하는 바보 같은 멈춤 현상(Deadlock)을 방지하는 **'강제 입장 규칙'**과 같다.
등장 배경: 상호 배제만 만족하는 초창기 소프트웨어 알고리즘들은 두 프로세스가 거의 0.0001초 차이로 동시에 접근할 때, 서로의 락 변수를 보고 "어? 쟤가 쓰려나 보다" 하고 둘 다 멈춰버리는 교착 상태(Deadlock) 버그를 빈번하게 일으켰다. 학계는 이런 '멈춤' 자체를 알고리즘의 실패로 규정하고 '진행(Progress)'이라는 엄격한 평가 잣대를 추가했다.

  [진행(Progress) 조건이 깨진 최악의 소프트웨어 락 (Strict Alternation)]

  (상황: P0과 P1이 교대로만 들어가게 만든 코드. 초기 turn = 0)

  [ 프로세스 0 ]                     [ 프로세스 1 ]
  while (turn != 0) { }          while (turn != 1) { }
  // 임계 구역 진입                   // 임계 구역 진입
  turn = 1;  (P1에게 턴 넘김)      turn = 0;  (P0에게 턴 넘김)

  🚨 참사 발생 (Progress 붕괴)
  1. P0이 임계 구역을 쓰고 나와서 turn을 1로 바꿨다.
  2. 그런데 P1은 지금 딴일 하느라 바빠서 임계 구역에 들어갈 생각이 1도 없다.
  3. P0이 다시 임계 구역에 들어가고 싶은데, turn이 1이라 평생 무한 루프를 돈다!
  ▶ 결과: 방(임계 구역)이 텅텅 비어있는데, P0 혼자 못 들어가고 굶어 죽음 (진행 실패).

[다이어그램 해설] 이 코드는 "상호 배제"는 완벽히 만족한다(절대 둘이 동시에 못 들어감). 하지만 "진행" 조건에서 0점을 받는다. 임계 구역에 들어갈 의사가 없는 프로세스(P1)가, 들어가고 싶어 하는 프로세스(P0)의 진입을 막아버렸기 때문이다. 진행 조건의 핵심은 **"임계 구역 밖에서 놀고 있는 놈이, 들어가려는 놈을 방해하면 안 된다"**는 것이다.

📢 섹션 요약 비유: 화장실을 "남자 한 번, 여자 한 번" 교대로만 쓰게 법을 만들었습니다(Strict Alternation). 여자가 화장실을 다 쓰고 나왔는데, 기다리는 여자는 100명이고 남자는 단 한 명도 없습니다. 화장실이 비어있음에도 남자 차례라는 이유로 100명의 여자가 바지에 오줌을 싸는 멍청한 규칙이 바로 진행(Progress) 조건에 실패한 것입니다.

Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)

데이크스트라의 '진행(Progress)' 엄밀한 수학적 정의

임계 구역을 실행 중인 프로세스가 없을 때 (즉, 방이 비었을 때)
임계 구역으로 진입하고자 하는 프로세스들이 존재한다면 (대기자가 있다면)
나머지 구역(Remainder Section)에서 실행 중이 아닌 프로세스들만 다음 진입 후보 결정에 참여해야 하며,
이 결정은 유한한 시간 내에(without indefinite postponement) 무조건 이루어져야 한다.

이 복잡한 정의의 핵심은 3번이다. "나 화장실 안 갈 건데?" 하는 놈의 의사는 무시하고, "나 화장실 갈래!"라고 손든 놈들끼리만 합의해서 문을 열고 들어가라는 뜻이다.

진행 조건을 완벽히 충족시킨 피터슨의 알고리즘 (Peterson's Algorithm)

피터슨은 flag(의사 표현)와 turn(양보) 변수를 결합하여 이 문제를 뚫어냈다.

  ┌──────────────────────────────────────────────────────────────────────┐
  │         피터슨 알고리즘의 진행(Progress) 보장 시뮬레이션             │
  ├──────────────────────────────────────────────────────────────────────┤
  │                                                                      │
  │   [ 공유 변수: flag[0]=F, flag[1]=F, turn=0 ]                        │
  │                                                                      │
  │   상황: P0은 들어가고 싶고, P1은 관심 없음(나머지 구역에 있음)       │
  │                                                                      │
  │   [ P0 의 진입 시도 ]                                                │
  │   1. flag[0] = true;  (P0: "나 들어갈래!")                           │
  │   2. turn = 1;        (P0: "근데 P1 너도 갈 거면 먼저 가")           │
  │                                                                      │
  │   3. while (flag[1] == true && turn == 1) 확인                       │
  │      ▶ P1은 관심이 없으므로 flag[1]은 false 상태임.                  │
  │      ▶ while문 조건이 (false && true) 이므로 즉시 깨짐 (탈출!)       │
  │                                                                      │
  │   4. P0 즉시 임계 구역 진입 완료! ✅ (진행 조건 100% 만족)           │
  └──────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 앞선 교대(Strict Alternation) 알고리즘의 실패를 완벽히 극복했다. P1이 화장실 갈 생각이 없으면(flag[1] == false), P0은 turn이 1이든 0이든 상관없이 무사통과한다. 즉, "관심 없는 놈이 남의 발목을 잡지 못하게" 설계된 완벽한 알고리즘이다.

📢 섹션 요약 비유: P0과 P1이 문 앞에서 마주쳤을 때 "먼저 가시죠(turn)"라고 양보합니다. 그런데 P1이 "아, 저 화장실 안 가요(flag=false)"라고 하면, P0은 예의 차릴 필요 없이 그냥 문 열고 들어가면 됩니다. 불필요한 양보로 인한 무한 대기가 사라졌습니다.

Ⅲ. 융합 비교 및 다각도 분석 (Comparison & Synergy)

진행(Progress)의 실패 사례: 데드락 vs 라이브락

진행 조건이 깨지는 방식은 크게 두 가지로 나뉜다. 둘 다 시스템의 처리량이 0이 되는 재앙이다.

비교 항목	교착 상태 (Deadlock)	라이브락 (Livelock)
상태	차들이 사거리에서 꼬리를 물고 완전히 멈춰버림 (Sleep)	두 사람이 복도에서 마주쳐 계속 서로 피해주느라 계속 움직이는데 앞으로 못 감 (Busy)
CPU 사용량	0% (대기 상태이므로 자원 소모 없음)	100% (양보 연산을 하느라 CPU가 불탐)
발생 원인	Mutex/Semaphore를 잘못된 순서로 획득 시	동기화 로직에서 너무 과도한 양보(`yield`)를 코딩했을 때
진행(Progress) 조건	❌ 파괴됨. 방이 비었는데도 못 들어감	❌ 파괴됨. 계속 시도하지만 영원히 못 들어감

상호 배제(Mutual Exclusion)와의 아슬아슬한 줄타기

상호 배제만 너무 챙기면: "위험하니까 그냥 시스템 전원 끄자!" ─▶ 상호 배제 100% 달성, 진행 0%.
진행만 너무 챙기면: "일단 다 들어가고 봐!" ─▶ 진행 100% 달성, 상호 배제 0% (데이터 박살). OS 설계의 핵심은 이 두 극단적인 목표 사이에서 **안전(Safety)**과 **활력(Liveness)**을 동시에 달성하는 것이다.
📢 섹션 요약 비유: 은행 금고를 설계할 때 상호 배제(안전)만 생각하면 금고에 콘크리트를 부어버리면 됩니다. 도둑은 절대 못 털지만, 은행 직원도 돈을 못 꺼냅니다(진행 불가). 열쇠를 3개 만들어서 3명이 동시에 돌려야만 열리게(안전+진행) 만드는 것이 동기화입니다.

Ⅳ. 실무 적용 및 기술사적 판단 (Strategy & Decision)

실무 시나리오

스핀락 (Spinlock)에서의 진행 보장 구조: 멀티코어 환경에서 널리 쓰이는 커널 스핀락은 하드웨어 명령어인 TestAndSet을 쓴다.
- 원리: while(TestAndSet(&lock)) 구조는 락이 풀리는(0이 되는) 순간, 뺑뺑이 돌던 스레드 중 누군가 찰나의 순간에 1을 밀어 넣고 즉시 방으로 들어간다.
- 실무 평가: 락이 풀리면 "반드시 누군가는 즉시 들어간다"는 사실이 하드웨어적으로 보장되므로 진행(Progress) 조건이 완벽히 충족된다. (단, 누가 들어갈지는 몰라서 기아(Starvation)는 발생할 수 있다.)
분산 시스템(MSA)에서의 분산 락(Distributed Lock) 타임아웃: MSA 환경에서 Redis나 Zookeeper를 써서 분산 락을 걸었다. 서버 A가 락을 쥐었는데 갑자기 서버 A의 랜선이 뽑혀 죽어버렸다.
- 재앙: 서버 A는 영원히 락 해제(unlock()) 신호를 보내지 못한다. 방은 사실상 비었는데 서버 B와 C는 영원히 기다린다. 진행(Progress) 조건이 외부 요인에 의해 파괴된 것이다.
- 아키텍트 조치: 분산 락을 설계할 때는 **반드시 TTL (Time-To-Live, 만료 시간)**을 세팅해야 한다. "서버 A가 5초 동안 락을 안 풀면, A가 죽은 걸로 간주하고 락을 강제로 부숴라!"라고 설정해야만 분산 환경에서의 데드락을 막고 시스템 진행(Progress)을 복구시킬 수 있다.

  ┌───────────────────────────────────────────────────────────────────────┐
  │     교착 상태(Deadlock) 회피를 통한 시스템 진행(Progress) 보장 트리   │
  ├───────────────────────────────────────────────────────────────────────┤
  │                                                                       │
  │   [요구사항: 스레드들이 자원 A와 자원 B의 락을 동시에 잡아야 함]      │
  │                │                                                      │
  │                ▼ 락 획득 순서 설계                                    │
  │   스레드 1은 A ─▶ B 순서로 락을 잡고, 스레드 2는 B ─▶ A 순서로 잡는가?│
  │          ├─ [예 (교차 획득)]                                          │
  │          │      │                                                     │
  │          │      ▼ 🚨 시스템 진행 정지 (Deadlock 확정)                 │
  │          │  1번은 A를 쥐고 B대기, 2번은 B를 쥐고 A대기.               │
  │          │  ▶ 해결 불가. 타임아웃 걸고 프로세스 강제 킬 해야 함.      │
  │          │                                                            │
  │          └─ [아니오 (순서 강제 정렬)]                                 │
  │                 │                                                     │
  │                 ▼ ✅ 시스템 진행(Progress) 보장                       │
  │             모든 스레드가 무조건 A ─▶ B 순서로만 락을 잡게            │
  │             아키텍처 코딩 컨벤션으로 강제함. (Lock Hierarchy)         │
  │             ▶ 순환 대기(Circular Wait)가 원천 차단됨.                 │
  └───────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] "진행(Progress)"을 잃어버리는 가장 흔한 개발자의 실수가 락의 획득 순서(Lock Ordering)를 꼬아버리는 것이다. 데드락이 터지는 순간 시스템의 처리량(Throughput)은 영구적으로 0이 된다. 이를 막기 위해 C++나 Java 시니어 개발자들은 여러 개의 락을 잡을 때 메모리 주소값 순서 등 "무조건 한 방향으로만 락을 획득한다"는 룰을 세워 진행 조건을 철통방어한다.

📢 섹션 요약 비유: 골목길에서 양쪽 차가 빵빵거리며 서로 안 비키는 상황(데드락, 진행 불가)을 막으려면, 법으로 "무조건 남쪽에서 오는 차가 먼저 통과한다"라는 서열(Lock Ordering)을 강제해 줘야 도로에 차가 원활하게 흐릅니다.

Ⅴ. 기대효과 및 결론 (Future & Standard)

기대효과

진행(Progress) 조건을 완벽하게 충족하는 동기화 메커니즘을 적용하면, 시스템은 어떤 극악의 타이밍과 인터럽트 폭풍 속에서도 절대 멈춰 서지(Freeze) 않고, 초당 수십만 건의 트랜잭션을 끝없이 쳐내는 100%의 가용성(Availability)과 활력(Liveness)을 유지할 수 있다.

결론 및 미래 전망

초기 컴퓨터 과학자들은 피터슨 알고리즘처럼 소프트웨어 코드를 비틀어 진행 조건을 만족시키려 했으나, 최신 CPU의 난해함(캐시, 비순차 실행) 앞에서 모두 무너졌다. 현재는 OS 커널(Mutex)과 하드웨어 명령어(CAS)의 결합만이 진행 조건을 완벽히 보장하는 유일한 수단으로 인정받는다. 미래에는 락을 걸어서 남을 대기(Block)시키는 방식 자체를 혐오하는 락-프리(Lock-Free) 및 웨이트-프리(Wait-Free) 알고리즘이 클라우드 백엔드의 표준이 되고 있다. 웨이트-프리 자료구조는 다른 스레드가 무슨 짓을 하든 상관없이 '내 연산은 무조건 유한한 스텝 내에 끝난다'는 궁극의 진행(Progress)을 보장하는 현대 동시성 프로그래밍의 최고봉이다.

📢 섹션 요약 비유: 옛날엔 사거리에서 경찰(소프트웨어)이 손짓으로 통제하다가 교통 마비가 왔고, 신호등(하드웨어 락)을 세워 통제해도 기다리는 시간은 있었습니다. 미래의 웨이트-프리 도로는 아예 차들이 하늘을 날아 겹쳐서 지나가게(충돌 무시 알고리즘) 만들어, 누구도 브레이크를 밟지 않고 끝없이 직진(Progress)하는 환상적인 인프라입니다.

📌 관련 개념 맵 (Knowledge Graph)

개념 명칭	관계 및 시너지 설명
임계 구역 (Critical Section)	진행 조건이 평가되는 무대다. 이 구역이 비었을 때 누군가 들어갈 수 있느냐가 핵심 질문이다.
교착 상태 (Deadlock)	진행(Progress) 조건이 가장 처참하게 파괴되었을 때 시스템에 나타나는 현상의 이름이다.
상호 배제 (Mutual Exclusion)	진행 조건과 항상 트레이드오프(시소) 관계에 있는 1원칙. 이것만 지키려다 진행을 말아먹는 초보들이 많다.
한정된 대기 (Bounded Waiting)	진행(Progress)은 "누군가"는 들어간다는 뜻이고, 한정된 대기는 그 누군가가 "나"도 될 수 있다는 공평함의 영역이다.
피터슨 알고리즘 (Peterson's Algorithm)	`turn` 변수를 통해 "관심 없는 놈이 남을 막는" 진행의 모순을 완벽히 해결한 소프트웨어 알고리즘의 교과서다.

👶 어린이를 위한 3줄 비유 설명

화장실(임계 구역)이 텅텅 비어있는데, 밖에 서 있는 두 친구가 "네가 먼저 들어가", "아냐 네가 먼저 가" 하면서 하루 종일 양보만 하다가 바지에 오줌을 쌌어요 (교착 상태).
그래서 선생님이 **진행(Progress)**이라는 규칙을 추가했어요. "화장실이 비어있고 가고 싶은 사람이 있으면, 둘 중 한 명은 고민하지 말고 무조건 1초 안에 들어가라!"
이 규칙 덕분에 화장실이 텅텅 비어서 낭비되는 일 없이 아이들이 계속 시원하게 볼일을 볼 수 있는 쾌적한 유치원이 되었답니다!