B-4: 동기화와 데드락

안녕하세요, 홍순구 튜터입니다. CS 기초 여섯 번째 시간이에요.

지난 두 시간(B-2·B-3) 동안 멀티스레드를 이야기하면서, 제가 자꾸 한 단어를 흘렸어요. 경쟁 상태(race condition). 한 프로세스 안의 여러 스레드가 코드·데이터·힙을 공유하니까(스택과 레지스터만 따로 갖고요), 둘이 동시에 같은 값을 건드리면 결과가 꼬인다고요. 은행 잔액 1000원에서 두 스레드가 각각 100원씩 출금했는데 잔액이 900원이 되는 사고 — 분명히 800원이어야 하는데 출금 한 번이 증발하는 그 황당한 일, 기억하시죠?

오늘은 그 사고를 제대로 막는 법을 배웁니다. 한 번에 하나의 스레드만 들어가게 줄을 세우는 임계 구역과 상호 배제, 그걸 구현하는 잠금장치인 뮤텍스와 세마포어, 그리고 면접 단골인 둘의 차이까지요.

그런데 이 잠금장치를 잘못 얽으면 새로운 사고가 터집니다. 서로가 서로의 자물쇠를 쥔 채 상대가 풀어주기만 기다리며 영영 멈춰버리는 상황이에요. 좁은 사거리에서 네 방향 차가 서로 앞을 막아 아무도 못 가는 그 교착이요. 이게 데드락(deadlock, 교착 상태)이고, 오늘 후반부의 주인공입니다. 데드락이 생기는 네 가지 조건과 그걸 푸는 법, 그리고 유명한 식사하는 철학자 문제로 오늘을 마무리해요.

동기화와 데드락은 운영체제 면접에서 가장 끈질기게 파고드는 영역이에요. "race condition이 뭔가요"·"뮤텍스와 세마포어의 차이가 뭔가요"·"데드락의 네 조건을 말해보세요" — 이 셋은 거의 반드시 나옵니다. 오늘 원리부터 잡아서, 외운 한 줄이 아니라 풀어서 답할 수 있게 만들어요.

오늘 우리가 걸을 길은 이렇습니다.

   오늘의 여정 — 동기화와 데드락

   ① 경쟁 상태 — 동시에 건드리면 왜 값이 꼬이나 (면접 단골)
   ② 임계 구역·상호 배제 — 한 번에 하나만 들여보내기
   ③ 뮤텍스 — 자물쇠 하나로 잠그기
   ④ 세마포어 — 열쇠 N개로 인원을 세기
   ⑤ 뮤텍스 vs 세마포어 — 면접 1순위 비교
   ⑥ 데드락 — 서로 기다리다 멈추는 네 가지 조건
   ⑦ 데드락 처리 — 예방·회피·탐지·회복
   ⑧ 식사하는 철학자 — 데드락을 한 그림에 담기

①~⑤는 "어떻게 안전하게 공유하나"의 이야기(동기화), ⑥~⑧은 "안전하게 하려다 오히려 멈춰버리는" 이야기(데드락)예요. 동기화로 한 문제를 풀면 데드락이라는 새 문제가 따라오는, 운영체제의 영원한 줄다리기를 오늘 만납니다.

💡 오늘 수업의 핵심 — "공유 데이터를 동시에 건드리면 값이 꼬이는 경쟁 상태를, 임계 구역에 한 번에 하나만 들이는 상호 배제로 막고(뮤텍스·세마포어), 그 잠금이 서로 얽혀 영영 멈추는 데드락은 네 조건 중 하나를 깨서 푼다" 🎯

🎯 학습 목표

• 경쟁 상태(race condition)가 왜 생기는지 설명하고, 임계 구역·상호 배제로 그것을 막는 원리를 이해합니다.
• 동기화 도구인 뮤텍스·세마포어(·모니터·스핀락)를 구분하고, 면접 1순위인 뮤텍스 vs 세마포어의 차이를 막힘 없이 답합니다.
• 데드락의 네 가지 필요조건과 처리 기법(예방·회피·탐지·회복)을 설명하고, 식사하는 철학자 문제로 그것을 한 그림에 정리합니다.

Step 1: "경쟁 상태 — 동시에 건드리면 왜 값이 꼬이나"

B-2와 B-3에서 멀티스레드를 이야기할 때, 한 프로세스 안의 여러 스레드는 코드·데이터·힙을 공유한다고 했어요(스택과 레지스터만 따로 갖고요). 공유한다는 건 편리하지만 동시에 위험합니다. 둘 이상의 스레드가 같은 데이터를 동시에 읽고 쓰면, 결과가 누가 먼저 도느냐에 따라 달라져버려요. 이렇게 실행 순서(타이밍)에 따라 결과가 들쭉날쭉해지는 상황을 경쟁 상태(race condition)라고 합니다. 여러 스레드가 한 값을 두고 경주하듯 달려들어 생기는 문제라는 뜻이에요.

왜 이런 일이 생길까요? 핵심은 우리가 한 줄로 쓴 코드가 사실은 한 동작이 아니라는 것입니다. 예를 들어 잔액에 1만 원을 더하는 이 한 줄을 봅시다.

   balance = balance + 1      // 잔액에 1(만원)을 더한다

사람 눈엔 한 동작이지만, CPU 입장에선 세 단계로 쪼개집니다. A-2에서 본 명령어 사이클을 떠올리면 자연스러워요.

   1) balance 값을 메모리에서 읽어 레지스터로 가져온다   (read)
   2) 레지스터에서 +1 한다                              (modify)
   3) 그 결과를 다시 balance 메모리에 쓴다              (write)

이 "읽고-고치고-쓰는"(read-modify-write) 세 단계 도중에 다른 스레드가 끼어들면 사고가 납니다. 두 스레드가 잔액 10(만원)에 각각 1씩 입금하는 상황을 시간순으로 따라가 봅시다.

   balance = 10        (만원 단위, 두 스레드가 함께 보는 공유 잔액)

   time   Thread A                Thread B
   ──────────────────────────────────────────────────
   t1     read  → 10
   t2                             read  → 10
   t3     +1 → 11
   t4                             +1 → 11
   t5     write balance = 11
   t6                             write balance = 11
   ──────────────────────────────────────────────────
   결과 = 11   →  정답은 12였다 (입금 한 번이 흔적도 없이 사라졌다)

보이시나요? 두 스레드가 둘 다 "10"을 읽은 뒤 각자 "11"을 계산해 썼기 때문에, 분명히 두 번 입금했는데 잔액은 11이 됐어요. 정답은 12인데 입금 한 번이 사라진 거죠. 만약 t5에서 A의 쓰기가 끝난 뒤에 B가 읽었다면 결과는 12로 정확했을 겁니다. 즉 결과가 운(실행 순서)에 좌우되는 게 경쟁 상태의 본질이에요.

이 문제의 뿌리를 한 단어로 부르면 원자성(atomicity)의 부재입니다. "원자"처럼 더는 쪼개지지 않아야 할 동작(읽고-고치고-쓰기)이 중간에 쪼개져 다른 스레드가 끼어들 틈이 생긴 거예요. 그러니 해법의 방향은 분명합니다. "이 세 단계가 끝날 때까지는 아무도 끼어들지 못하게" 묶어주면 됩니다. 어떻게 묶느냐가 다음 Step부터의 이야기예요.

비유하면 두 사람이 같은 통장을 공유하는데, 각자 종이 장부를 보고 잔액을 고쳐 쓰는 상황이에요. 둘 다 "잔액 10만 원"을 보고, 각자 1만 원을 더해 "11만 원"이라고 적습니다. 나중에 적은 사람이 먼저 적은 사람의 기록을 덮어쓰니, 입금 한 번이 날아가죠. 한 명이 장부를 다 고칠 때까지 다른 사람이 장부를 못 보게 막아야 이 사고가 안 납니다.

🎯 면접에서는 이렇게 답하세요

"경쟁 상태는 둘 이상의 스레드가 공유 데이터에 동시에 접근해 읽고 쓸 때, 실행 순서에 따라 결과가 달라지는 문제입니다. 원인은 balance = balance + 1 같은 한 줄이 사실 읽기-수정-쓰기 세 단계로 쪼개지는데, 그 도중에 다른 스레드가 끼어들기 때문입니다. 두 스레드가 같은 값을 읽고 각자 고쳐 쓰면 한쪽 갱신이 덮어써져 사라지죠. 핵심은 이 연산이 원자적이지 않다는 점이고, 그래서 해당 구간을 한 번에 하나의 스레드만 실행하도록 상호 배제로 막아야 합니다."

💡 그러니 우리가 보호해야 할 건 코드 전체가 아니라, 공유 데이터를 건드리는 그 좁은 구간이에요. 그 구간을 뭐라 부르고 어떻게 한 명씩만 들여보내는지 — 다음 Step에서 임계 구역과 상호 배제를 봅니다.

Step 2: "임계 구역과 상호 배제 — 한 번에 하나만 들여보내기"

Step 1에서 우리가 보호해야 할 건 코드 전체가 아니라 공유 데이터를 건드리는 좁은 구간이라고 했어요. 이 구간에 정식 이름이 있습니다. 임계 구역(critical section, 임계 영역이라고도 함)이에요. "임계"는 "아슬아슬한 경계"라는 뜻으로, 여러 스레드가 함께 들어오면 사고가 나는 위험 구간이라 이렇게 부릅니다. 잔액을 읽고-고치고-쓰는 그 세 줄이 바로 임계 구역이죠.

경쟁 상태를 막는 원리는 한 문장입니다. 임계 구역에는 한 번에 하나의 스레드만 들어가게 한다. 한 스레드가 임계 구역에서 일하는 동안 다른 스레드는 입구에서 기다리고, 그 스레드가 다 끝내고 나와야 다음 스레드가 들어갑니다. 이렇게 한 번에 하나만 허용하는 것을 상호 배제(mutual exclusion)라고 해요. 서로(mutual)를 밀어낸다(exclusion)는 뜻으로, 한 명이 들어가 있으면 나머지는 배제된다는 의미입니다.

비유는 1인용 화장실이 딱이에요. 안에 사람이 있으면 문을 잠그고, 밖의 사람들은 줄 서서 기다립니다. 안의 사람이 나와 문이 열려야 다음 사람이 들어가죠. 화장실(임계 구역)에 한 번에 한 명(상호 배제)이라는 규칙이 있으면, 두 사람이 동시에 들어가 부딪히는 사고(경쟁 상태)가 안 납니다.

   한 스레드가 임계 구역을 드나드는 흐름

     [ 진입 구간 ]   lock 획득 시도 (막혀 있으면 여기서 대기)
          │
          ▼
     [ 임계 구역 ]   ← 공유 데이터를 건드리는 구간: 한 번에 하나만
          │
          ▼
     [ 퇴출 구간 ]   lock 반납 (기다리던 다음 스레드를 깨움)

   그 바깥의 나머지 코드는 공유 자원과 무관 → 자유롭게 병렬 실행

그림처럼 임계 구역 앞에는 진입 구간(들어가도 되는지 확인하고, 안 되면 대기)이 있고, 뒤에는 퇴출 구간(다음 사람에게 자리를 넘김)이 있어요. 우리가 곧 배울 뮤텍스·세마포어가 바로 이 진입·퇴출을 구현하는 도구입니다.

그런데 "한 번에 하나만"이라는 규칙 하나만으로는 부족해요. 좋은 상호 배제 방법이 갖춰야 할 조건이 세 가지 있습니다.

• 상호 배제(mutual exclusion): 한 스레드가 임계 구역에 있으면 다른 스레드는 못 들어간다. (가장 기본)
• 진행(progress): 임계 구역이 비어 있는데 아무도 못 들어가는 일은 없어야 한다. (괜히 막아두지 않기)
• 유한 대기(bounded waiting): 들어가려고 기다리는 스레드는 언젠가 반드시 들어갈 수 있어야 한다. (영원히 차례가 안 오는 일 방지)

세 번째 유한 대기를 어기면, 한 스레드가 운 나쁘게 계속 밀려 영영 못 들어가는 기아(starvation, 굶주림) 상태에 빠져요. B-2의 스케줄링에서 잠깐 만났던 그 굶주림이 여기서도 나옵니다. 좋은 잠금장치는 이 셋을 모두 만족해야 해요.

🎯 면접에서는 이렇게 답하세요

"임계 구역은 여러 스레드가 공유하는 자원에 접근하는 코드 구간으로, 동시에 둘 이상이 들어가면 경쟁 상태가 납니다. 그래서 한 번에 하나의 스레드만 임계 구역에 들어가게 하는데, 이를 상호 배제라고 합니다. 올바른 상호 배제는 세 조건을 만족해야 합니다. 한 명만 들어가는 상호 배제, 비어 있으면 들어갈 수 있는 진행, 기다리면 언젠가 반드시 들어가는 유한 대기입니다. 마지막을 어기면 특정 스레드가 영영 못 들어가는 기아가 생깁니다. 또 임계 구역은 병렬성을 위해 가능한 한 좁게 잡는 게 좋습니다."

💡 그럼 이 "한 번에 하나만"을 실제로 어떻게 구현할까요? 가장 기본 도구가 자물쇠 하나로 문을 잠그는 뮤텍스예요. 다음 Step에서 만납니다.

Step 3: "뮤텍스 — 자물쇠 하나로 잠그기"

상호 배제를 구현하는 가장 기본 도구가 뮤텍스(mutex)예요. 이름부터가 mutual exclusion(상호 배제)을 줄인 말이라, "상호 배제 전용 자물쇠"라는 뜻이죠. 동작은 자물쇠 그 자체예요. 임계 구역에 들어가기 전에 잠그고(lock), 나오면서 푼다(unlock). 누군가 이미 잠가뒀으면, 들어가려는 스레드는 문 앞에서 기다립니다.

   mutex.lock()             // 자물쇠를 잠근다 (이미 잠겨 있으면 풀릴 때까지 대기)
   balance = balance + 1    // ← 임계 구역: 나 혼자만 실행
   mutex.unlock()           // 자물쇠를 푼다 (기다리던 스레드 하나가 들어옴)

이렇게 감싸두면, 한 스레드가 lock()으로 자물쇠를 쥔 동안 다른 스레드는 lock()에서 멈춰 기다려요. Step 1의 그 사고 — 둘 다 10을 읽어 11을 쓰던 — 가 원천적으로 막힙니다. 한 스레드가 읽고-고치고-쓰기를 다 끝내고 unlock() 할 때까지, 다른 스레드는 잔액을 아예 못 보거든요.

뮤텍스의 핵심 성질이 하나 있어요. 소유권(ownership)입니다. 자물쇠를 잠근 스레드만 그 자물쇠를 풀 수 있어요. 화장실 문을 잠근 사람이 직접 열고 나와야지, 밖에 있는 사람이 마음대로 열 수 없는 것과 같죠. 이 "잠근 자가 푼다"는 성질이 뒤에서 세마포어와 뮤텍스를 가르는 결정적 차이가 됩니다(Step 5에서 짚어요).

그런데 기다리는 방식에 두 갈래가 있어요. 하나는 방금처럼 잠들어 기다리는 것입니다. 자물쇠가 잠겨 있으면 그 스레드는 대기 상태로 들어가 CPU를 양보하고(B-1의 상태 전이도에서 Waiting), 자물쇠가 풀리면 깨어나죠. CPU를 안 쓰니 효율적이지만, 잠들고 깨우는 데 비용(컨텍스트 스위칭)이 듭니다.

다른 하나가 스핀락(spinlock)이에요. 잠들지 않고 "열렸나? 열렸나?" 하며 자물쇠를 계속 확인하는 방식입니다. 빙글빙글 돈다(spin)고 해서 스핀락이에요. 잠들고 깨우는 비용이 없어서, 아주 잠깐만 기다리면 될 때(임계 구역이 몇 줄뿐일 때)는 오히려 빠릅니다. 하지만 기다림이 길어지면 그동안 CPU를 헛돌리며 낭비하죠. 비유하면 잠드는 뮤텍스는 번호표 뽑고 의자에 앉아 기다리는 손님, 스핀락은 창구 앞에 서서 "아직요? 아직요?" 계속 묻는 손님이에요. 잠깐이면 서 있는 게 빠르고, 오래면 앉는 게 낫습니다.

참고로 뮤텍스를 실제 코드에서 어떻게 쓰는지(자바의 synchronized나 ReentrantLock 같은) 구체적인 사용법은 언어 과목(java-basic 등)에서 깊게 다뤄요. 여기선 "자물쇠 하나로 한 명만 들여보낸다, 잠근 자가 푼다"는 원리까지 잡으면 충분합니다.

🎯 면접에서는 이렇게 답하세요

"뮤텍스는 상호 배제를 위한 자물쇠로, 임계 구역 앞에서 lock, 뒤에서 unlock 합니다. 이미 잠겨 있으면 다른 스레드는 대기하죠. 핵심 성질은 소유권으로, 잠근 스레드만 풀 수 있습니다. 대기 방식은 두 가지인데, 잠들었다 깨어나는 일반 뮤텍스는 CPU를 양보하지만 컨텍스트 스위칭 비용이 들고, 스핀락은 잠들지 않고 계속 확인하며 기다려 그 비용이 없는 대신 기다리는 동안 CPU를 씁니다. 그래서 임계 구역이 아주 짧고 멀티코어일 때는 스핀락이, 대기가 길 때는 잠드는 뮤텍스가 유리합니다."

💡 뮤텍스는 "한 명만"이에요. 그런데 "동시에 세 명까지는 괜찮아" 같은, 정원이 있는 상황도 있죠. 화장실은 1칸이지만 스터디룸은 좌석이 여러 개인 것처럼요. 이걸 다루는 도구가 다음 Step의 세마포어입니다.

Step 4: "세마포어 — 열쇠 N개로 인원을 세기"

뮤텍스가 "한 명만"이라면, 세마포어(semaphore)는 "N명까지"예요. 세마포어는 사용 가능한 자원의 개수를 세는 카운터를 가진 잠금장치입니다. 원래 "semaphore"는 기차역의 신호기(깃발로 진행·정지를 알리는 장치)를 뜻하는 말인데, 여기선 "지금 몇 개 남았는지 알려주는 신호"라고 생각하면 돼요.

동작은 카운터를 올렸다 내렸다 하는 거예요. 두 연산이 있습니다.

• wait(또는 P, acquire): 자원을 하나 쓰겠다고 요청. 카운터를 1 줄입니다. 카운터가 0이면(남은 게 없으면) 누군가 반납할 때까지 기다려요.
• signal(또는 V, release): 자원을 다 쓰고 반납. 카운터를 1 늘립니다. 기다리던 스레드가 있으면 하나 깨우죠.

   sem = Semaphore(3)   // 동시에 3개까지 허용 (카운터 = 3)

   sem.wait()           // 카운터 3 → 2, 입장 (0이면 대기)
   ...자원 사용...
   sem.signal()         // 카운터 2 → 3, 반납

비유는 좌석이 3개인 스터디룸이에요. 입구에 열쇠 3개가 걸려 있습니다. 들어가려는 사람은 열쇠를 하나 가져가고(wait, 카운터 −1), 나올 때 도로 건다(signal, 카운터 +1)고 해요. 열쇠가 다 나가 0개면, 다음 사람은 누군가 나와 열쇠를 걸 때까지 입구에서 기다립니다. 카운터가 곧 "지금 들어갈 수 있는 자리 수"인 거죠.

세마포어는 카운터의 최댓값에 따라 두 종류로 나뉘어요.

• 카운팅 세마포어(counting semaphore): 카운터가 N(1보다 큼). 동일한 자원이 여러 개일 때 씁니다. 예를 들어 데이터베이스 연결이 10개뿐인 풀(pool)에서 "동시에 10명까지만 연결 빌려가게" 제한할 때요.
• 이진 세마포어(binary semaphore): 카운터가 0 또는 1뿐. "쓸 수 있다(1)/없다(0)"만 표현하니, 사실상 뮤텍스와 비슷하게 한 명만 들여보내는 효과예요. (단, 똑같지는 않습니다 — 그 차이가 다음 Step의 핵심이에요.)

세마포어의 또 다른 쓰임새는 상호 배제가 아니라 "신호 보내기"예요. 한 스레드가 "내 작업 다 끝났어!"라고 다른 스레드에 알릴 때, 끝나면서 signal()을 하고 기다리던 쪽이 wait()로 받는 식이죠. 카운터를 0에서 시작해 "사건이 일어나면 +1"로 쓰면, 순서를 맞추는 신호등이 됩니다. 이 신호 용도는 뮤텍스에는 없는 세마포어만의 쓰임이에요.

마지막으로 친척 하나만 짚고 갈게요. 모니터(monitor)입니다. 뮤텍스·세마포어는 프로그래머가 lock/unlock, wait/signal을 직접 짝 맞춰 호출해야 하는데, 하나라도 빠뜨리면(예: unlock을 깜빡) 사고가 나죠. 모니터는 이 잠금을 언어 차원에서 자동으로 묶어주는 상위 도구예요. 공유 데이터와 그걸 다루는 코드를 한 덩어리로 감싸서, 그 안에 들어가면 자동으로 잠기고 나오면 자동으로 풀립니다. 자바의 synchronized가 대표적인 모니터예요. 프로그래머가 일일이 짝을 안 맞춰도 되니 실수가 줄죠. (구체적 사용법은 언어 과목 몫입니다.)

🎯 면접에서는 이렇게 답하세요

"세마포어는 사용 가능한 자원 개수를 세는 카운터를 가진 동기화 도구입니다. wait로 카운터를 줄이며 진입하고(0이면 대기), signal로 늘리며 반납합니다. 카운터가 1뿐이면 이진 세마포어로 상호 배제에, 1보다 크면 카운팅 세마포어로 동일 자원이 여러 개인 자원 풀(예: DB 커넥션 풀)을 제한하는 데 씁니다. 뮤텍스가 상호 배제 전용이라면, 세마포어는 그에 더해 한 스레드가 다른 스레드에 작업 완료를 알리는 신호 용도로도 쓸 수 있다는 점이 다릅니다."

💡 이진 세마포어는 "한 명만"이라는 점에서 뮤텍스와 똑 닮았어요. 그런데도 둘은 다릅니다. 무엇이 다를까요? 이게 운영체제 면접에서 가장 자주 나오는 질문 중 하나예요. 다음 Step에서 정면으로 비교합니다.

Step 5: "뮤텍스 vs 세마포어 — 면접 1순위 비교"

운영체제 면접에서 동기화를 물으면 거의 반드시 따라오는 질문이에요. "뮤텍스와 세마포어의 차이가 뭔가요?" 둘 다 공유 자원을 보호하는 잠금장치라 헷갈리기 쉬운데, 결정적 차이 두 가지만 잡으면 깔끔하게 답할 수 있습니다.

첫째, 소유권입니다. 이게 가장 중요해요. 뮤텍스는 잠근 스레드만 풀 수 있어요(소유권 있음). 세마포어는 누구든 signal로 카운터를 올릴 수 있습니다(소유권 없음). 화장실 문은 잠근 사람이 열고 나오지만, 스터디룸 열쇠는 내가 가져갔어도 옆 사람이 대신 걸어둘 수 있는 셈이죠. 이 차이 때문에 용도가 갈립니다. 뮤텍스는 "임계 구역을 한 명이 책임지고 들어갔다 나오는" 상호 배제에 맞고, 세마포어는 "자원 개수를 세거나, 한 스레드가 다른 스레드에 신호를 보내는" 데 맞아요.

둘째, 셀 수 있는 범위입니다. 뮤텍스는 잠김/풀림 두 상태뿐이라 한 번에 하나만 들여보냅니다. 세마포어는 카운터가 N까지 가니 한 번에 N개까지 허용하죠. 그래서 "딱 하나의 임계 구역 보호"는 뮤텍스, "동일한 자원이 여러 개인 풀 관리"는 세마포어가 자연스럽습니다.

표로 정리하면 이래요.

자주 나오는 함정 질문이 "이진 세마포어(카운터 1)는 뮤텍스랑 같은 거 아니냐"예요. 효과는 비슷하지만 같지 않습니다. 소유권이 없다는 그 차이 때문이에요. 이진 세마포어는 A 스레드가 wait로 잠그고 B 스레드가 signal로 풀어도 동작해요(소유자가 따로 없으니까). 뮤텍스라면 A가 잠근 걸 B가 푸는 건 규칙 위반이라 막힙니다. 그래서 "한 명만 보호"가 목적이면 소유권으로 실수를 잡아주는 뮤텍스가 더 안전하고, "신호 주고받기"가 목적이면 소유권이 없는 세마포어가 맞아요.

비유로 한 번에 정리하면 — 뮤텍스는 1인용 화장실 열쇠(한 명, 쓴 사람이 직접 반납), 세마포어는 좌석 N개짜리 스터디룸의 열쇠 꾸러미(N명, 아무나 반납 가능)입니다.

🎯 면접에서는 이렇게 답하세요

"둘의 차이는 소유권과 카운트입니다. 뮤텍스는 소유권이 있어 잠근 스레드만 풀 수 있고, 한 번에 하나만 허용하는 상호 배제 전용 도구입니다. 세마포어는 소유권이 없어 누구든 카운터를 올릴 수 있고, 카운터가 N까지 가서 동시에 N개를 허용합니다. 그래서 단일 임계 구역 보호는 뮤텍스, 동일 자원이 여러 개인 풀 관리나 스레드 간 신호 전달은 세마포어가 맞습니다. 카운터가 1인 이진 세마포어는 뮤텍스와 비슷해 보이지만, 소유권이 없어 다른 스레드가 풀 수 있다는 점에서 다릅니다."

💡 여기까지가 "공유를 안전하게"의 이야기였어요. 그런데 이 자물쇠들을 여러 개 쓰다 보면, 안전하게 하려던 게 오히려 프로그램을 통째로 멈춰버리는 사고로 번집니다. 후반부의 주인공 데드락으로 갑니다.

Step 6: "데드락 — 서로 기다리다 멈추는 네 가지 조건"

자물쇠로 공유 자원을 안전하게 지키는 법을 배웠어요. 그런데 자물쇠가 여러 개가 되면 새로운 함정이 생깁니다. 두 스레드가 서로 상대가 쥔 자물쇠를 기다리며 둘 다 영영 멈춰버리는 상황이에요. 이걸 데드락(deadlock, 교착 상태)이라고 합니다. "교착"은 서로 맞물려 옴짝달싹 못 한다는 뜻이에요.

B-3 마지막에 예고한 좁은 사거리 비유가 정확히 이거예요. 신호등 없는 사거리에 네 방향에서 차가 동시에 진입해, 각자 앞차의 뒤꽁무니에 막혀 있습니다. 모두가 "앞차가 빠지면 가야지" 하고 기다리는데, 그 앞차도 자기 앞차를 기다리고 있죠. 아무도 양보하지 않으면 넷 다 영원히 못 갑니다. 누가 고장 난 게 아니라, 서로가 서로를 기다리는 구조 자체가 멈춤을 만든 거예요.

코드로 보면 자물쇠 두 개를 엇갈려 잡을 때 생겨요.

   Thread A                      Thread B
   lock(L1)                      lock(L2)
   lock(L2)  ← B가 쥠, 대기       lock(L1)  ← A가 쥠, 대기
   ...                           ...

A는 L1을 쥐고 L2를 기다리고, B는 L2를 쥐고 L1을 기다립니다. 서로 상대가 쥔 걸 내놓길 바라지만 아무도 내놓지 않으니, 둘 다 멈춰요. Step 1의 경쟁 상태가 "동시에 들어가 값이 꼬이는" 사고였다면, 데드락은 그걸 막으려고 자물쇠를 쓰다가 "아무도 못 들어가 멈추는" 정반대 사고예요.

   자원 할당 그래프 (화살표가 고리를 이루면 데드락)

        Thread A  ─────▶  Lock 2
            ▲                 │
            │                 ▼
        Lock 1  ◀─────  Thread B

   ─────▶  요청(기다림):  A→L2,  B→L1
   ▲ / ▼   점유(가짐):    L1→A,  L2→B
   화살표를 따라 돌면  A→L2→B→L1→A  로 한 바퀴 → 순환 대기

자, 그럼 데드락은 아무 때나 생길까요? 아니에요. 데드락이 생기려면 네 가지 조건이 동시에 성립해야 합니다. 이걸 데드락의 네 가지 필요조건이라고 하고, 면접에서 "데드락 조건 네 개 말해보세요"로 단골이에요. 하나씩 사거리 비유로 볼게요.

• 상호 배제(mutual exclusion): 자원을 한 번에 하나의 스레드만 쓸 수 있다. → 사거리 한 칸엔 차 한 대만. (자원을 공유할 수 있으면 애초에 안 막힘)
• 점유 대기(hold and wait): 자원을 하나 쥔 채로 다른 자원을 기다린다. → 사거리 한 칸을 점령한 채 앞 칸이 비길 기다림.
• 비선점(no preemption): 남이 쥔 자원을 강제로 뺏을 수 없다. → 앞차를 강제로 밀어낼 수 없음. 스스로 빠져야 함.
• 순환 대기(circular wait): 기다림이 고리를 이룬다. A는 B를, B는 C를, …, 마지막은 다시 A를 기다린다. → 사거리 네 대가 시계방향으로 서로의 앞을 막아 원을 이룸.

이 네 가지가 모두 성립할 때만 데드락이 생깁니다. 뒤집으면, 넷 중 하나만 깨도 데드락은 안 생겨요. 이게 다음 Step에서 배울 데드락 처리의 핵심 열쇠입니다. 특히 네 번째 순환 대기가 데드락의 가장 도드라진 특징이라, "기다림이 고리를 이루는가"를 보면 데드락을 알아챌 수 있어요.

🎯 면접에서는 이렇게 답하세요

"데드락은 둘 이상의 스레드가 서로 상대가 점유한 자원을 기다리며 모두 무한정 멈추는 상태입니다. 생기려면 네 조건이 동시에 성립해야 합니다. 한 번에 하나만 쓰는 상호 배제, 자원을 쥔 채 다른 걸 기다리는 점유 대기, 뺏을 수 없는 비선점, 기다림이 고리를 이루는 순환 대기입니다. 이 넷은 필요조건이라, 데드락을 막으려면 넷 중 하나만 깨면 됩니다. 특히 순환 대기가 데드락의 가장 두드러진 특징입니다."

💡 그럼 실제로 그 조건을 어떻게 깰까요? 아니면 깨지 않고 다른 방법으로 막을까요? 데드락에 대처하는 네 갈래 전략 — 예방·회피·탐지·회복 — 을 다음 Step에서 봅니다.

Step 7: "데드락 처리 — 예방·회피·탐지·회복"

데드락에 대처하는 길은 크게 네 갈래예요. 미리 못 생기게 하는 예방과 회피, 일단 두되 생기면 잡는 탐지·회복, 그리고 (놀랍게도) 그냥 무시입니다. 하나씩 봅시다. 다시 좁은 사거리로요.

1) 예방(prevention) — 네 조건 중 하나를 원천 차단

Step 6에서 데드락의 네 조건은 필요조건이라 하나만 깨도 데드락이 불가능해진다고 했죠. 예방은 이걸 정면으로 씁니다. 애초에 네 조건 중 하나가 성립할 수 없게 설계하는 거예요.

• 점유 대기 깨기: 필요한 자물쇠를 한꺼번에 다 잡거나, 하나라도 못 잡으면 가진 걸 다 내려놓게 한다. 쥔 채로 기다리는 일이 없어짐.
• 순환 대기 깨기(가장 실용적): 모든 자물쇠에 번호를 매기고, 항상 낮은 번호부터 잡게 강제한다. 그러면 "A는 L1→L2, B는 L2→L1"처럼 엇갈리는 일이 없어 고리가 안 생겨요. (둘 다 L1을 먼저 잡으려 하니, 한 명은 L1에서 기다릴 뿐 데드락은 안 납니다.)

사거리로 치면 "차는 반드시 시계방향으로만 진입" 같은 규칙을 박아 고리 자체를 못 만들게 하는 거예요. 단순하고 확실하지만, 자물쇠를 미리 다 잡으면 병렬성이 떨어지는 비용이 있습니다.

2) 회피(avoidance) — 위험한 상태로는 가지 않기

예방이 "조건을 아예 없애기"라면, 회피는 "자원을 내줄 때마다 이걸 내주면 데드락 위험이 있나 미리 계산해서, 안전할 때만 내주는" 방법이에요. 대표가 은행원 알고리즘(banker's algorithm)입니다.

은행원이 여러 고객에게 대출해줄 때, "이 돈을 빌려줘도 모든 고객이 언젠가 돈을 다 돌려받고 끝낼 수 있는가"를 미리 따져보고, 그런 안전한 상태(safe state)가 유지될 때만 빌려주는 거예요. 한 명이라도 끝까지 못 갚는 그림이 그려지면 대출을 보류합니다. 운영체제도 자원을 요청받으면 "이걸 주면 모두가 결국 끝낼 수 있나"를 계산해, 안전하면 주고 위험하면 기다리게 해요.

회피는 데드락을 깔끔히 막지만, 자원을 줄 때마다 계산해야 하고 각 스레드가 "최대 얼마나 쓸지"를 미리 알아야 해서 현실에선 무겁습니다. 그래서 이론적으로 유명하지만 실제로는 잘 안 써요.

3) 탐지·회복(detection & recovery) — 일단 두고, 생기면 잡기

미리 막는 비용이 부담스러우면, 그냥 데드락이 나게 두되 주기적으로 검사하는 방법도 있어요. 운영체제가 자원 할당 그래프(Step 6의 그 고리!)를 살펴 순환이 생겼는지 탐지하고, 발견하면 회복에 나섭니다. 회복 방법은 거칠어요. 고리에 걸린 프로세스 하나를 강제 종료하거나, 자원을 강제로 빼앗아(rollback) 고리를 끊습니다. 사거리에 경찰이 와서 한 대를 강제로 후진시켜 길을 트는 셈이죠.

4) 무시(ignore) — 타조 알고리즘

마지막은 어이없지만 현실적인 전략이에요. 그냥 무시하는 겁니다. 데드락이 아주 드물게만 생긴다면, 막는 데 드는 상시 비용보다 "어쩌다 멈추면 재시작"이 더 쌀 수 있거든요. 위험이 닥치면 머리를 모래에 박는 타조에 빗대 타조 알고리즘(ostrich algorithm)이라 불러요. 사실 우리가 쓰는 일반 운영체제(리눅스·윈도우) 상당수가 응용 수준의 데드락은 이렇게 둡니다. 예방·회피·탐지가 다 비싸니까요.

🎯 면접에서는 이렇게 답하세요

"데드락 처리는 네 가지입니다. 예방은 네 필요조건 중 하나를 원천 차단하는데, 모든 자물쇠에 순서를 매겨 순환 대기를 없애는 방법이 가장 실용적입니다. 회피는 자원을 줄 때마다 안전한 상태인지 계산해 위험하면 보류하는 것으로, 은행원 알고리즘이 대표지만 비용이 커 잘 안 씁니다. 탐지·회복은 데드락을 허용하되 주기적으로 순환을 검사해, 발견하면 프로세스를 강제 종료하거나 자원을 회수합니다. 마지막으로 데드락이 드물면 그냥 두는 무시(타조 알고리즘)도 현실적 선택이라, 실제 운영체제는 이들을 상황에 맞게 섞어 씁니다."

💡 네 조건과 네 처리법을 한 그림에 모아 정리하기에 딱 좋은 고전 문제가 있어요. 컴퓨터 과학에서 데드락 하면 빠지지 않는 식사하는 철학자입니다. 마지막 Step에서 만나요.

Step 8: "식사하는 철학자 — 데드락을 한 그림에 담기"

오늘 배운 걸 한 그림에 모으는 고전 문제로 마무리해요. 식사하는 철학자 문제(dining philosophers problem)입니다. 데이크스트라가 낸 문제로, 동기화와 데드락을 설명할 때 빠지지 않는 단골이에요.

상황은 이래요. 둥근 식탁에 철학자 다섯 명이 둘러앉아 있습니다. 철학자들은 생각하다가 배가 고프면 스파게티를 먹어요. 그런데 포크가 철학자들 사이사이에 다섯 개뿐이고, 스파게티를 먹으려면 양옆 포크 두 개를 모두 집어야 합니다. 한 철학자가 왼쪽 포크와 오른쪽 포크를 둘 다 들면 먹고, 다 먹으면 둘 다 내려놓죠.

   원탁에 철학자 5명과 포크 5개가 번갈아 앉음 (양옆 포크를 다 들어야 식사)

     P0 ── F0 ── P1 ── F1 ── P2 ── F2 ── P3 ── F3 ── P4 ── F4 ──▶ (다시 P0, 고리)

   사고: 다섯 명이 동시에 '왼쪽 포크부터' 집으면
         → 모든 포크가 누군가의 왼손에 들림
         → 각자 오른쪽 포크는 옆 사람이 쥐고 있어 영원히 대기
         → P0→P1→P2→P3→P4→(다시 P0) 로 기다림이 고리를 이룸 = 순환 대기 = 데드락

여기서 사고가 납니다. 만약 다섯 명이 동시에 배고파져 모두 왼쪽 포크를 먼저 집으면, 모든 포크가 누군가의 왼손에 들려요. 이제 다들 오른쪽 포크를 집으려는데, 내 오른쪽 포크는 옆 사람의 왼쪽 포크라 이미 들려 있죠. 그래서 모두가 "옆 사람이 포크를 내려놓길" 기다리며 영원히 멈춥니다. 완벽한 데드락이에요.

이 상황에 Step 6의 네 조건이 그대로 다 들어 있어요.

• 상호 배제: 포크 하나는 한 번에 한 명만 든다.
• 점유 대기: 왼쪽 포크를 쥔 채 오른쪽 포크를 기다린다.
• 비선점: 남이 든 포크를 강제로 뺏을 수 없다.
• 순환 대기: 철학자0은 1의 포크를, 1은 2의 포크를, …, 4는 다시 0의 포크를 기다린다. 고리가 식탁을 한 바퀴 돈다.

그럼 어떻게 풀까요? Step 7의 처리법이 그대로 답이 돼요. 네 조건 중 하나를 깨면 됩니다.

• 순환 대기 깨기(가장 깔끔): 포크에 번호를 매기고 항상 낮은 번호 포크부터 집게 한다. 그러면 식탁의 이음매에 앉은 한 명(왼쪽 F4·오른쪽 F0을 쓰는 P0)만 집는 순서가 뒤집혀(오른쪽 먼저), 모두가 같은 방향으로 도는 고리가 끊깁니다.
• 점유 대기 깨기: 양쪽 포크가 둘 다 비어 있을 때만 집게 한다 (하나만 쥐고 기다리지 않기).
• 동시 인원 제한: 식탁에 최대 네 명만 앉히면 (세마포어 카운터 4!), 한 명은 반드시 두 포크를 다 잡아 먹고 빠질 수 있어 고리가 안 생겨요. ← 오늘 배운 세마포어가 여기서 쓰입니다.

세 번째 해법에서 보이듯, 식사하는 철학자는 세마포어·상호 배제·데드락 네 조건·데드락 처리가 한 문제에 다 녹아 있어요. 그래서 면접관이 이 문제로 동기화 전반을 한 번에 떠보기 좋은 거죠.

🎯 면접에서는 이렇게 답하세요

"식사하는 철학자 문제는 다섯 철학자가 사이의 포크 다섯 개를 공유하며, 먹으려면 양옆 포크를 모두 들어야 하는 상황입니다. 모두가 왼쪽 포크를 먼저 들면 각자 오른쪽 포크를 기다리며 데드락에 빠지죠. 데드락 네 조건이 모두 성립하는 전형적 예입니다. 해법은 조건 하나를 깨는 것으로, 포크에 번호를 매겨 낮은 번호부터 집게 해 순환 대기를 없애거나, 동시에 앉는 인원을 세마포어로 한 명 줄여 제한하거나, 양쪽 포크가 다 있을 때만 집게 합니다. 제한된 공유 자원을 데드락 없이 나눠 쓰는 동기화의 축소판입니다."

💡 여기까지가 동기화와 데드락이에요. 경쟁 상태를 막으려 자물쇠를 채웠고, 그 자물쇠가 얽혀 생기는 데드락을 네 조건과 네 처리법으로 다스렸습니다. 운영체제가 한 컴퓨터 안에서 자원을 나눠 쓰게 하는 이야기가 여기서 한 매듭을 지어요.

마무리

오늘 배운 핵심 세 가지

🎯 하나, 여러 스레드가 공유 데이터를 동시에 읽고 쓰면 실행 순서에 따라 값이 꼬이는 경쟁 상태가 생깁니다. balance = balance + 1이 읽기-수정-쓰기 세 단계로 쪼개지는 게 원인이죠. 이를 막으려면 공유 자원을 건드리는 임계 구역에 한 번에 하나의 스레드만 들이는 상호 배제가 필요하고, 그걸 구현하는 자물쇠가 뮤텍스와 세마포어입니다.

🎯 둘, 뮤텍스는 소유권이 있어 잠근 스레드만 풀 수 있고 한 번에 하나만 허용하는 상호 배제 전용 도구입니다. 세마포어는 소유권이 없고 카운터가 N까지 가서 동시에 N개를 허용하며, 자원 풀 관리나 스레드 간 신호에 씁니다. "한 명만 보호면 뮤텍스, N명 제한이나 신호면 세마포어" — 이 한 줄이 면접 1순위 질문의 답입니다.

🎯 셋, 자물쇠가 서로 얽혀 모두가 멈추는 데드락은 상호 배제·점유 대기·비선점·순환 대기 네 조건이 동시에 성립할 때만 생깁니다. 필요조건이라 하나만 깨면 막히죠. 처리법은 조건을 원천 차단하는 예방, 안전 상태만 허용하는 회피(은행원), 허용하되 잡는 탐지·회복, 드물면 두는 무시가 있고, 식사하는 철학자 문제가 이 모두를 한 그림에 담습니다.

다음 시간 예고

이걸로 운영체제 이야기가 한 매듭을 지었어요. 지난 네 번(B-1~B-4) 동안 우리는 줄곧 한 대의 컴퓨터 안을 들여다봤습니다. 운영체제가 프로세스와 스레드를 만들어(B-1·B-2), 메모리를 가상으로 나눠주고(B-3), 그 자원을 안전하게 공유하도록 동기화하는(B-4) 이야기였죠. 컴퓨터 한 대 안에서 자원을 나눠 쓰는 그림이 이제 완성됐어요.

다음 시간(C-1)부터는 시야를 컴퓨터 바깥으로 넓힙니다. 한 대 안의 이야기에서, 여러 컴퓨터가 서로 대화하는 네트워크의 세계로요. 브라우저에 주소를 치면 저편의 서버까지 어떻게 신호가 가닿는지, 그 길을 왜 계층으로 나누는지(OSI 7계층·TCP/IP 4계층), 그리고 TCP와 UDP가 어떻게 다른지를 배웁니다. 특히 이 과목의 핵심 그림 셋 중 마지막인 3-way handshake(연결을 세 번 인사로 맺는 과정)를 그곳에서 만나요. "TCP vs UDP"·"3-way handshake"는 네트워크 면접의 최단골이니, 단단히 준비해서 가겠습니다.

과제

[기초] 경쟁 상태를 손으로 따라가고, 임계 구역으로 막기

연필과 종이만 있으면 됩니다. 공유 잔액 balance = 10(만원)에 두 스레드 A, B가 각각 balance = balance + 1을 한 번씩 실행한다고 합시다. 각 실행은 읽기 → 수정 → 쓰기 세 단계로 쪼개집니다.

1. 두 스레드가 둘 다 읽기를 먼저 끝낸 뒤 각자 수정·쓰기를 하는 순서로 단계를 나열하고, 최종 balance가 얼마가 되는지 적어보세요. 정답(12)과 왜 달라지는지 한 줄로 설명하세요.
2. 이번엔 A가 읽기-수정-쓰기를 전부 끝낸 뒤 B가 시작하는 순서로 다시 나열하고, 최종 balance를 적어보세요. 1번과 결과가 다른 이유를 "원자성" 또는 "임계 구역" 단어를 써서 설명하세요.
3. 이 코드에서 임계 구역이 정확히 어느 부분인지 짚고, 뮤텍스의 lock()/unlock()을 어디에 넣어야 사고가 막히는지 의사코드로 적어보세요.

[응용] 데드락 네 조건을 식사하는 철학자에 매핑하고, 하나를 깨기

식사하는 철학자 문제(철학자 5명, 포크 5개, 양옆 포크를 다 들어야 식사)를 떠올리세요.

1. 데드락의 네 조건(상호 배제·점유 대기·비선점·순환 대기)이 이 문제에서 각각 어떻게 나타나는지 한 줄씩 적어보세요.
2. "철학자를 식탁에 최대 4명만 앉힌다"는 해법은 네 조건 중 무엇을 깨는 건지 고르고, 왜 그것으로 데드락이 사라지는지 설명해보세요. 이때 오늘 배운 어떤 동기화 도구를 쓰면 인원 제한을 구현할 수 있을지도 적으세요.
3. "포크에 번호를 매겨 항상 낮은 번호부터 집게 한다"는 해법은 네 조건 중 무엇을 깨는 건지 고르고, 다섯 명 중 누구의 집는 순서가 바뀌는지 한 줄로 설명해보세요.

[심화] "뮤텍스 vs 세마포어" 면접 답변과 꼬리 질문 대비하기

조사하고 정리하는 과제입니다.

1. "뮤텍스와 세마포어의 차이가 뭔가요?"에 대한 자기만의 답변을, 소유권과 카운트(셀 수 있는 범위) 두 축으로 정리해 적어보세요.
2. 이어질 법한 꼬리 질문에 대비해보세요. "이진 세마포어는 뮤텍스랑 같은 거 아닌가요?"에 대한 답을 소유권을 들어 두세 문장으로, "각각 언제 쓰나요?"에 대한 답을 실무 예(자원 풀·신호)를 들어 두세 문장으로 준비하세요.
3. (선택) 오늘 배운 스핀락이 잠드는 뮤텍스보다 유리한 상황과 불리한 상황을 각각 한 줄로 적고, 그 판단에 "컨텍스트 스위칭 비용"과 "코어 개수"가 어떻게 얽히는지 연결해보세요.

생각해볼 주제

1. 잠금은 정말 공짜로 안전을 줄까?

뮤텍스로 임계 구역을 감싸면 경쟁 상태가 사라져 안전해집니다. 그런데 임계 구역 안은 한 번에 한 스레드만 도니, 그 구간만큼은 멀티스레드가 무색하게 줄 서서(직렬로) 실행돼요. 게다가 자물쇠를 두고 여러 스레드가 다투면(락 경합) 기다림과 컨텍스트 스위칭 비용도 쌓이죠. 그렇다면 "안전하니까 일단 다 잠그자"는 어디서 문제가 될까요? 임계 구역을 잘게 쪼개 잠금을 여러 개 쓰면 병렬성은 살지만 오늘 배운 데드락 위험이 올라가고, 굵게 하나로 잠그면 안전하고 단순하지만 병렬성을 잃습니다. 안전과 성능 사이에서 잠금의 크기를 어떻게 정해야 할지 생각해보세요.

2. 데드락을 "무시"하는 것도 엔지니어링일까?

데드락을 막는 예방·회피·탐지는 모두 평소에 비용을 냅니다. 반면 타조 알고리즘은 데드락을 그냥 두다가 문제가 생기면 재시작하죠. 언뜻 무책임해 보이지만, 실제 운영체제 상당수가 응용 수준의 데드락엔 이 전략을 씁니다. 그렇다면 "막을 수 있는 사고를 일부러 안 막는" 결정은 어떤 근거 위에서 정당화될까요? 사고의 발생 확률과 한 번 터졌을 때의 피해, 그리고 막는 데 드는 상시 비용을 저울에 올려, 비행기 제어 시스템과 개인 PC의 게임이 왜 다른 선택을 해야 하는지 견주어 생각해보세요.

3. 재현되지 않는 버그를 어떻게 막을까?

경쟁 상태와 데드락은 타이밍에 좌우되는 비결정적 버그예요. 평소엔 멀쩡하다가 트래픽이 몰린 어느 날 한 번 터지고, 디버거를 붙여 한 줄씩 따라가면 타이밍이 바뀌어 재현조차 안 됩니다. "테스트했는데 안 나오던데요"가 통하지 않는 버그인 거죠. 그렇다면 눈으로 확인하기 어려운 이런 버그를 우리는 무엇에 기대 막아야 할까요? 운에 기대 "어쩌다 안 터지길" 바라는 것과, 설계 단계에서 "공유 데이터엔 반드시 잠금", "자물쇠는 항상 같은 순서로" 같은 규칙을 세워 구조적으로 불가능하게 만드는 것의 차이를 생각해보세요.