한정된 대기 (Bounded Waiting)

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

본질: 한정된 대기 (Bounded Waiting)는 임계 구역(Critical Section) 보호 알고리즘의 3대 필수 조건 중 마지막으로, 프로세스가 임계 구역에 진입하겠다고 요청한 시점부터 허락될 때까지 다른 프로세스들이 새치기해서 먼저 들어가는 '횟수'에 수학적인 한계(Bound)가 있어야 한다는 원칙이다.

가치: 아무리 상호 배제(안전)와 진행(활력)이 완벽하더라도, 우선순위가 낮다는 이유로 영원히 락(Lock)을 얻지 못하고 굶어 죽는 **기아 상태(Starvation)**가 시스템에 발생하는 것을 논리적으로 원천 봉쇄하는 '공정성(Fairness)'의 절대 기준이다.

융합: 현대 운영체제에서는 이를 보장하기 위해 스핀락이나 세마포어의 대기 큐(Wait Queue)를 구현할 때 FIFO(First-In, First-Out) 자료구조를 적용하거나 에이징(Aging) 기법을 융합하여 "언젠가는 반드시 내 차례가 온다"는 강건한 신뢰를 제공한다.

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

개념: "한정된 대기(Bounded Waiting)"란 단순히 "대기 시간이 짧다"는 뜻이 아니다. 내가 대기줄에 서 있는 동안, 다른 녀석들이 내 앞으로 새치기해서 임계 구역에 들어갈 수 있는 **횟수(Bound)**가 무한대($\infty$)가 아니어야 한다는 수학적 엄밀함을 뜻한다. (예: 최악의 경우라도 내 앞에 3명만 지나가면 내 차례가 무조건 온다).
필요성: 상호 배제(Mutex)로 데이터가 깨지는 것을 막았고, 진행(Progress) 조건으로 데드락을 막았다. 그런데 방이 비었을 때 "누가 들어갈래?"를 결정할 때마다 매번 '우선순위가 가장 높은 VIP'만 들여보낸다면? 평민 프로세스는 시스템이 끝날 때까지 단 한 번도 방에 들어가지 못하고 굶어 죽는다(기아 상태). 시스템의 신뢰도를 보장하려면 모든 참여자에게 "유한한 시간 내의 진입"을 개런티해야 했다.
💡 비유: 놀이공원에서 줄을 섰을 때, VIP 프리패스 손님들이 계속 온다고 해서 일반 손님 줄이 영원히 멈춰있게 놔두지 않고, **"VIP가 3팀 들어가면 무조건 일반 손님 1팀을 들여보낸다"**는 규칙을 세워 일반 손님도 언젠가는 반드시 놀이기구를 타도록 보장하는 것과 같다.
등장 배경: 피터슨 알고리즘이나 베이커리 알고리즘 같은 초창기 소프트웨어 락 설계 시, 특정 프로세스가 무한 루프에 빠지거나 특정 패턴으로 타이밍이 꼬였을 때 한 놈만 영원히 CPU를 못 잡는 취약점이 발견되었다. 이를 막기 위해 데이크스트라가 임계 구역 알고리즘의 세 번째 자격 요건으로 Bounded Waiting을 명문화했다.

  [한정된 대기(Bounded Waiting)의 파괴 vs 준수 시뮬레이션]

  [ ❌ Bounded Waiting 실패 (기아 발생) - LIFO 큐 사용 시 ]
  1. P1 진입 요청 ─▶ 대기 큐: [P1]
  2. P2 진입 요청 ─▶ 대기 큐: [P1, P2] (P2가 더 늦게 왔으나 맨 앞을 차지)
  3. P3 진입 요청 ─▶ 대기 큐: [P1, P2, P3] 
  ▶ 방이 비었을 때: 가장 늦게 온 P3가 먼저 들어감. 계속 새 놈이 오면 P1은 평생 못 들어감!
  ▶ Bound = 무한대 (∞)

  [ ✅ Bounded Waiting 달성 (공정성 보장) - FIFO 큐 사용 시 ]
  1. P1 진입 요청 ─▶ 대기 큐: [P1]
  2. P2 진입 요청 ─▶ 대기 큐: [P1, P2] (P2는 무조건 P1 뒤에 섬)
  3. P3 진입 요청 ─▶ 대기 큐: [P1, P2, P3]
  ▶ 방이 비었을 때: 맨 앞의 P1이 무조건 들어감.
  ▶ Bound = 내 앞의 대기자 수 (유한함)

[다이어그램 해설] 한정된 대기 조건은 "스케줄링의 공정성"을 대변한다. 내가 아무리 찌질한 프로세스라도 큐(Queue)에 들어간 이상, 내 위로 새치기하는 놈의 숫자가 딱 정해져 있어야(Bounded) "언젠가는 끝난다"라는 예측이 가능해진다.

📢 섹션 요약 비유: 은행 창구에서 번호표 기계가 고장 나서 직원 맘대로 손님을 부르는 곳은 한정된 대기가 깨진 곳입니다(기아 발생). 하지만 번호표를 뽑고 대기 인원수가 10명이라고 적혀있으면, 아무리 느려도 내 앞에 10명만 지나가면 내 차례가 온다는 '한정된 대기'가 완벽히 증명됩니다.

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

하드웨어 명령어(TAS)의 약점: 한정된 대기 불만족

원자적 하드웨어 명령어인 TestAndSet (TAS)나 CompareAndSwap (CAS)를 단독으로 써서 스핀락을 만들면 상호 배제와 진행은 100% 만족하지만, 한정된 대기는 만족하지 못한다.

  // TAS를 이용한 단순 스핀락 (Bounded Waiting ❌)
  while (TestAndSet(&lock) == 1) {
      // 계속 빙빙 돈다 (누가 먼저 락을 잡을지 아무런 보장이 없음)
  }

[이유]: 100개의 스레드가 위 while 문에서 미친 듯이 돌고 있다고 치자. 락이 0으로 풀리는 찰나의 순간, 100명 중 누가 1을 쓰고 들어갈까? 아무런 큐(Queue)도 없기 때문에 순전히 CPU 메모리 버스를 선점한 운 좋은 놈이 들어간다. 만약 지독하게 운이 나쁜 스레드가 있다면, 락이 10만 번 풀리고 닫히는 동안 계속 간발의 차로 타이밍을 놓쳐 영원히 방에 들어가지 못할 수 있다. (기아 상태 발생)

완벽한 3조건을 달성하는 구조: 램포트의 빵집 알고리즘 (Bakery Algorithm)

순수 소프트웨어만으로 "한정된 대기"까지 100% 만족시킨 가장 위대한 알고리즘 중 하나다. 번호표(Ticket) 개념을 도입했다.

임계 구역에 들어가려는 프로세스는 **번호표(가장 큰 숫자 + 1)**를 뽑는다.
번호표 숫자가 가장 작은 프로세스가 먼저 들어간다. (FIFO 구조 모방)
만약 번호표가 우연히 같게 뽑혔다면, 프로세스 ID (PID)가 작은 놈이 먼저 들어간다.

이렇게 하면, 내가 번호표를 10번으로 뽑았다면 그 이후에 온 놈들은 무조건 11번, 12번을 받기 때문에 내 앞으로 새치기할 수 있는 확률은 0%가 된다. (Bound가 명확해짐).

📢 섹션 요약 비유: 빵집에서 번호표 기계(Bakery Algorithm)가 없으면, 빵이 나올 때마다 아줌마들이 벌떼처럼 몰려들어 힘센 사람만 계속 빵을 사 가고 약한 아이는 하루 종일 빵을 못 삽니다(TAS 스핀락의 한계). 번호표를 뽑게 하면, 아이도 "내 앞에 5명만 사 가면 내 차례야"라고 확신(Bounded)할 수 있습니다.

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

운영체제의 락(Lock) 구현: 큐(Queue)의 중요성

현대 운영체제가 뮤텍스(Mutex)나 세마포어(Semaphore)를 만들 때, TestAndSet만 쓰지 않고 **대기 큐 (Wait Queue)**를 결합하는 이유가 바로 한정된 대기 조건을 만족시키기 위함이다.

구현 방식	한정된 대기 만족 여부	결과
순수 Spinlock (TAS만 사용)	❌ 불만족	운 나쁜 스레드는 평생 CPU만 갈구고 못 들어감
Mutex (대기 큐 결합)	✅ 만족	못 들어가면 OS가 스레드를 재우고(Sleep), 큐(FIFO)에 줄 세워서 락 풀리면 맨 앞놈을 깨워줌

"Bounded Waiting" vs "Wait-Free"

최신 동시성 프로그래밍에서는 한정된 대기를 넘어선 궁극의 개념들이 등장한다.

Bounded Waiting (한정된 대기): "네가 기다리긴 해야 하는데, 평생 기다리진 않을 거야. 언젠간 들어갈게." (락을 쓰는 기존 패러다임)
Lock-Free (락 프리): "누군가 한 명은 기다림 없이 무조건 전진해서 끝낼 거야. 나머지는 다시 시도해." (전체적인 시스템의 진행 보장)
Wait-Free (웨이트 프리): "줄 서는 것 자체를 없애줄게. 너를 포함한 모든 스레드가 유한한 스텝(명령어) 안에 100% 무조건 작업을 끝낼 거야." (현대 컴퓨터 공학의 끝판왕, 최고 난이도 자료구조)
📢 섹션 요약 비유: '한정된 대기'는 맛집 대기표를 뽑고 1시간 뒤에 입장하는 것입니다. '락 프리'는 식당에 들어가려다 꽉 차면 그냥 딴 데 갔다가 10분 뒤에 다시 와보는 눈치 게임입니다. '웨이트 프리'는 식당에 자리가 무한대라서 문을 열면 0.1초 만에 바로 밥을 먹을 수 있는 마법의 식당입니다.

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

실무 시나리오

리눅스 Ticket Spinlock과 MCS Spinlock의 도입: 원래 리눅스 커널의 스핀락은 TAS 기반의 눈치 게임이라 한정된 대기(공정성)가 박살나 있었다. 코어가 64개가 되자 재수 없는 코어 하나가 락을 못 잡아 커널 패닉이 터졌다.
- 아키텍처 혁신: 리눅스 진영은 스핀락에 빵집 알고리즘을 섞은 Ticket Spinlock을 도입하여 "먼저 스핀을 돈 코어가 먼저 락을 잡게(FIFO)" Bounded Waiting을 강제했다. 이후 락을 잡고 도는 행위가 남의 코어 캐시를 더럽히는 걸 막기 위해, 코어별로 자기 로컬 메모리에서만 스핀을 도는 MCS Spinlock / qspinlock으로 완전히 구조를 뒤엎어 공정성과 확장성을 동시에 잡았다.
Java의 ReentrantLock 공정성(Fairness) 옵션 선택: 실무 개발자가 자바에서 명시적인 락을 걸 때 new ReentrantLock(true) 와 new ReentrantLock(false) 중 하나를 선택해야 한다.
- true (Fair 모드): 한정된 대기(Bounded Waiting)를 100% 보장하는 모드. 먼저 락을 요청한 스레드가 먼저 들어간다(FIFO). 단점은 락을 넘겨줄 때마다 스레드를 깨우고 재우는 문맥 교환이 너무 많이 터져서 서버의 처리량(Throughput)이 절반으로 떨어진다.
- false (Non-fair 모드, 디폴트): 한정된 대기를 포기하는 모드. 방금 락을 푼 놈이 캐시가 뜨거우니까 바로 다시 락을 채가는 '새치기'를 허용한다. 기아 상태 위험이 있지만, 처리량이 10배 이상 빠르기 때문에 스프링 백엔드에서 99% 이 방식을 쓴다.

  ┌──────────────────────────────────────────────────────────────────┐
  │     락(Lock)의 공정성(Fairness)과 처리량(Throughput) 트레이드오프│
  ├──────────────────────────────────────────────────────────────────┤
  │                                                                  │
  │   [요구사항: 초당 10만 건 결제 처리 락 로직 구현]                │
  │                │                                                 │
  │                ▼ 비즈니스 요건 분석                              │
  │   "1만 번째 고객이 1초 이상 지연되면 소송이 걸리는가?"           │
  │          ├─ [예 (엄격한 지연시간 보장 필수)]                     │
  │          │      │                                                │
  │          │      ▼ 🚨 Fair Lock 강제 적용 (성능 포기)             │
  │          │  모두를 FIFO 큐에 일렬로 세움 (Bounded Waiting).      │
  │          │  ▶ 서버를 10대 더 사서 성능 저하를 돈으로 메꿈.       │
  │          │                                                       │
  │          └─ [아니오 (평균 10만 건 처리량이 더 중요함)]           │
  │                 │                                                │
  │                 ▼ ✅ Non-fair Lock (디폴트) 적용                 │
  │             새치기를 전면 허용하여 스레드 깨우는 시간을 삭제함.  │
  │             ▶ 1명의 고객이 재수 없게 5초 지연될(기아) 수 있으나, │
  │               나머지 99,999명은 0.1초 만에 결제 완료됨.          │
  └──────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 컴퓨터 공학 교과서에서는 "한정된 대기를 반드시 지켜라!"라고 가르치지만, 실무 아키텍트는 안다. "공정함(Fairness)은 가장 비싼 오버헤드다." 공정하게 줄을 세우는 행위 자체가 시스템의 스래싱을 유발하므로, 실무의 기본값은 한정된 대기를 살짝 무시(Non-fair)하여 전체 스루풋을 극대화하는 쪽으로 기울어져 있다.

📢 섹션 요약 비유: 놀이공원 입구에서 표를 검사할 때, 1명씩 정확히 줄을 세워서 검사하면(Fair Lock) 공평하지만 너무 늦게 들어갑니다. 그냥 문을 활짝 열어두고 눈치껏 우르르 밀고 들어가게(Non-fair Lock) 놔두면 얌전한 사람은 좀 늦게 들어가더라도 전체 1만 명이 입장하는 시간은 훨씬 빨라지는 실무적 역설입니다.

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

기대효과

알고리즘 설계 시 한정된 대기 조건을 완벽히 충족시키면, 수천 개의 스레드가 난립하는 상황에서도 특정 스레드가 무한 루프에 빠지거나 굶어 죽는 '사각지대(Blind Spot)' 없이, "최악의 응답 시간(Worst-case Latency)"을 수학적으로 증명하고 보장하는 철통같은 안전 시스템을 구축할 수 있다.

결론 및 미래 전망

데이크스트라의 3대 요건(상호 배제, 진행, 한정된 대기)은 반세기가 넘도록 운영체제 동기화의 헌법 역할을 해왔다. 하지만 오늘날 100코어가 넘는 클라우드 분산 환경에서는 이 헌법을 완벽히 지키려다 시스템이 멈춰버리는 딜레마(CAP 정리와 유사한 병목)에 부딪히고 있다. 이에 따라 미래의 동시성 패러다임은 한정된 대기를 위한 무거운 큐(Queue)를 버리고, 충돌이 나면 락 없이 우아하게 재시도하는(Retry) **소프트웨어 트랜잭셔널 메모리(STM)**나, 데이터를 읽을 때 락을 거는 대신 아예 최신 스냅샷(Copy-On-Write, RCU)을 던져주고 지나가게 만드는 극단적 락-프리 생태계로 진화하여, 대기(Waiting)라는 단어 자체를 사전에 지워나가고 있다.

📢 섹션 요약 비유: 한정된 대기는 "배급을 공평하게 받기 위해 완벽하게 한 줄 서기"를 강제하는 위대한 질서였습니다. 하지만 인류는 줄 서는 시간을 아끼기 위해 아예 "식량을 복사해서(Copy-On-Write) 전 국민의 집에 배달해 버려 줄 설 일 자체를 없애는" 풍요로운 무한 자원 아키텍처로 넘어가고 있습니다.

📌 관련 개념 맵 (Knowledge Graph)

개념 명칭	관계 및 시너지 설명
상호 배제 (Mutual Exclusion)	임계 구역 문제 해결의 1원칙. 이기적으로 1명만 들어가게 하는 규칙이라 한정된 대기와 충돌하기 십상이다.
진행 (Progress)	방이 비었으면 누구든 빨리 들어가게 하는 2원칙. 한정된 대기(공평함)와 진행(속도)은 영원한 트레이드오프다.
기아 상태 (Starvation)	한정된 대기(Bounded Waiting) 조건이 코딩 실수나 Non-fair 락으로 인해 깨졌을 때 발생하는 처참한 결과다.
스핀락 (Spinlock)	CPU 하드웨어(TAS)를 써서 빠르지만, 대기 큐(Wait Queue)가 없어 한정된 대기를 본질적으로 위반하는 락이다.
피터슨 알고리즘	이 3가지 헌법(상호배제, 진행, 한정된대기)을 소프트웨어 변수 2개(`turn`, `flag`)만으로 100% 충족시켜 낸 경이로운 알고리즘이다.

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

미끄럼틀을 탈 때, 상호 배제는 "한 번에 1명만 타!"라는 규칙이고, 진행은 "미끄럼틀 비었으면 아무나 빨리 타!"라는 규칙이에요.
그런데 덩치 큰 형들이 새치기해서 계속 미끄럼틀을 타면, 꼬마 친구는 해 질 때까지 한 번도 못 타는 슬픈 일(기아 상태)이 생겨요.
그래서 선생님이 **"내 앞에 3명이 탔으면 그다음엔 무조건 내 차례가 온다!"**라고 새치기 횟수에 제한을 두는 게 바로 한정된 대기라는 공평한 규칙이랍니다!