[운영체제] 데드락(Deadlock, 교착상태) 개념, 발생 조건 4가지 및 해결 방법 완전 정리

컴퓨터공학과 운영체제(OS) 시험이나 정처기, IT 전공 면접에서 "동시성(Concurrency)과 자원 관리"를 다룰 때 무조건 출제되는 단골 주제가 있습니다. 바로 데드락(Deadlock, 교착상태)입니다.

"두 개의 프로세스가 서로 상대방이 가진 자원을 기다리며 영원히 멈춰버린다면?"

데드락이 발생하는 정확한 정의부터 시험 필수 암기 요소인 4가지 필요조건, 그리고 이를 해결하기 위한 4가지 방법(은행원 알고리즘 포함)까지 시험에 필요한 핵심만 깔끔하게 정리해 드립니다!

1. 데드락(Deadlock, 교착상태)이란?

데드락(Deadlock)은 둘 이상의 프로세스가 서로가 점유하고 있는 자원을 요구하며 무한정 대기 상태에 빠지는 현상을 말합니다.

쉽게 말해, "외나무다리에서 두 사람이 서로 먼저 지나가라고 양보하지 않고 멈춰 서 있는 상태"라고 이해할 수 있습니다.

💡 식사하는 철학자 문제 (Dining Philosophers Problem)

데드락을 설명하는 가장 대표적인 비유입니다. 5명의 철학자가 양쪽에 놓인 젓가락을 둘 다 집어야만 식사를 할 수 있는데, 모든 철학자가 동시에 왼쪽 젓가락을 집어들면 아무도 오른쪽 젓가락을 집지 못해 영원히 식사를 하지 못하고 기아/교착 상태에 빠지게 됩니다.

2. 데드락 발생 4가지 필요조건 (★시험 서술형 1순위)

데드락은 다음 4가지 조건이 동시에 모두 만족할 때만 발생합니다. 단 하나라도 만족하지 않으면 데드락은 발생하지 않습니다!

1️⃣ 상호 배제 (Mutual Exclusion)

• 개념: 자원은 한 번에 한 프로세스만 사용할 수 있어야 합니다. (비공유 자원)

2️⃣ 점유와 대기 (Hold and Wait)

• 개념: 프로세스가 최소한 하나의 자원을 점유(Hold)한 상태에서, 다른 프로세스가 사용 중인 자원을 추가로 요구하며 대기(Wait)하고 있어야 합니다.

3️⃣ 비선점 (No Preemption)

• 개념: 다른 프로세스가 사용 중인 자원을 강제로 빼앗을 수 없으며, 자원을 점유한 프로세스가 스스로 사용을 끝내고 반납할 때까지 기다려야 합니다.

4️⃣ 순환 대기 (Circular Wait)

• 개념: 프로세스의 집합에서 대기 관선이 순환(Circle) 형태를 이루고 있어야 합니다. (예: $P_0$는 $P_1$의 자원을, $P_1$은 $P_2$의 자원을, $P_2$는 $P_0$의 자원을 대기)

3. 데드락 해결 방법 4가지

운영체제가 데드락을 다루는 방식은 크게 4가지 접근법으로 나뉩니다.

① 예방 (Prevention)

• 방식: 데드락 발생 4가지 조건 중 하나를 부정(차단)하여 사전에 데드락 발생 가능성을 없애는 방법입니다.
• 단점: 자원 이용률이 떨어지고 시스템 성능(Throughput)이 크게 저하됩니다.
  • 상호배제 부정: 모든 자원을 공유 가능하게 만듦 (실제 적용 어려움)
  • 점유대기 부정: 프로세스 실행 전 모든 자원을 한 번에 할당하거나, 자원이 없을 때만 요청
  • 비선점 부정: 다른 자원을 기다려야 할 때 보유 중인 자원을 강제로 반납(선점)하게 함
  • 순환대기 부정: 모든 자원에 고유 번호를 매기고 정해진 순서대로만 자원을 요청하게 함

② 회피 (Avoidance)

• 방식: 자원 할당 시 시스템이 '안전 상태(Safe State)'를 유지할 수 있는 경우에만 자원을 할당하는 동적 방법입니다.
• 대표 알고리즘: 다익스트라의 은행원 알고리즘 (Banker's Algorithm)
  • 안전 상태 (Safe State): 모든 프로세스가 데드락 없이 정상적으로 종료될 수 있는 안전 순서열(Safe Sequence)이 존재하는 상태
  • 불안전 상태 (Unsafe State): 데드락이 발생할 가능성이 있는 상태 (불안전 상태라고 해서 반드시 데드락인 것은 아님)

③ 검출 및 복구 (Detection & Recovery)

• 방식: 데드락 발생을 허용하되, 주기적으로 검출 알고리즘을 돌려 데드락이 발생했는지 확인하고 이를 복구합니다.
• 검출: 자원 할당 그래프(Resource Allocation Graph)를 통해 순환 대기 요소 탐색
• 복구 방식:
  • 프로세스 종료: 데드락에 빠진 모든 프로세스를 한 번에 강제 종료하거나, 하나씩 순차적으로 종료하며 데드락 해제 여부 확인
  • 자원 선점: 데드락 상태가 해결될 때까지 타 프로세스의 자원을 강제로 빼앗아 다른 프로세스에 할당 (롤백 기법 활용)

④ 무시 (Ignorance / 무시 및 무대응)

• 방식: 데드락이 드물게 발생하므로, 해결 비용이 더 크다고 판단하여 아무런 조치도 취하지 않고 무시하는 방법입니다.
• 대표 예시: 타조 알고리즘 (Ostrich Algorithm) - 현대의 대부분의 일반 OS(Windows, Linux 등)가 채택한 방식입니다. (데드락 발생 시 사용자가 직접 프로세스를 종료하거나 재부팅)

4. 한눈에 비교하는 데드락 해결책 (시험 요약표)

구분	주요 특징 및 기법	장점	단점 / 한계
예방 (Prevention)	4가지 발생 조건 중 하나를 깨뜨림	데드락 절대 불가능	자원 낭비 및 시스템 효율 저하
회피 (Avoidance)	은행원 알고리즘 (안전 상태 유지)	데드락 방지 가능	프로세스의 최대 자원 요구량을 미리 알아야 함
검출 및 복구	자원 할당 그래프 탐색 후 프로세스 종료	자원 이용률 높음	복구 시 프로세스 종료/롤백 오버헤드
무시 (Ignorance)	타조 알고리즘 (문제가 터지면 재부팅)	성능 오버헤드 0	데드락 발생 시 사용자 개입 필요

5. 시험 단골 출제 유형 체크

1. Q. 데드락 발생의 4가지 필요조건을 모두 쓰시오.
2. 👉 상호 배제(Mutual Exclusion), 점유와 대기(Hold and Wait), 비선점(No Preemption), 순환 대기(Circular Wait) 입니다.
3. Q. 은행원 알고리즘(Banker's Algorithm)은 데드락 해결 방법 중 어디에 해당하는가?
4. 👉 데드락 회피(Avoidance) 기법에 해당하며, 시스템이 안전 상태(Safe State)를 유지할 때만 자원을 할당합니다.
5. Q. 현대 OS(Windows, Linux)가 데드락 해결에 사용하는 기본 전략은?
6. 👉 데드락의 발생 빈도가 낮아 오버헤드를 줄이기 위해 무시(Ignorance/타조 알고리즘) 기법을 사용합니다.