SW

교착 상태(Deadlock)란? 발생 조건부터 해결 방법까지 총정리

korea-dobby 2025. 2. 20. 13:30

안녕하세요 박사과정 도비입니다.

오늘은 개발자 면접 질문 중 하나인 교착 상태에 대해 알아보겠습니다.

과연 교착상태가 뭔지, 이를 예방하거나 탐지하기 위해선 어찌해야하는지 등을 작성해놓았으니,

이를 참고하여 봐주시면 감사하겠습니다.

목차

  1. 교착 상태(Deadlock) 정의
  2. 교착 상태 발생 시나리오
  3. 데드락 발생 조건(4가지)
  4. 데드락 예방(Prevention) vs. 회피(Avoidance)
  5. 데드락 탐지(Detection) & 회복(Recovery)
  6. 자주 묻는 질문(FAQ)

1. 교착 상태(Deadlock) 정의

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

  • 두 개 이상의 프로세스(또는 스레드)가 서로가 가진 자원을 기다리면서 무한정 대기 상태(Wait)에 빠지는 상황을 말합니다.
  • 쉽게 말해 “한정된 자원”을 여러 프로세스가 동시에 점유하려고 하다가, 서로 상대방이 점유 중인 자원을 추가로 필요로 해서 기다리는 상황이 영구적으로 지속되는 것을 의미합니다.

예시로 외나무 다리 양 끝에서 두 사람이 서로 비켜주길 기다리기만 하는 상황을 떠올리면 됩니다. 결국 둘 다 움직이지 못하고 멈춘 상태가 됩니다.

프로세스와 스레드의 차이는 아래 블로그를 참고해주세요!

 

쓰레드(Thread)와 프로세스(Process), 개발자의 필수 면접 질문

안녕하세요. 컴퓨터공학 박사과정 도비입니다. 오늘은 프로그램 실행의 기본 단위인 프로세스(Process)와,...

blog.naver.com

 

2. 교착 상태 발생 시나리오

  1. 프로세스1이 자원1을 획득
  2. 프로세스2가 자원2를 획득
  3. 프로세스1은 자원2를 추가로 필요로 하여 대기
  4. 프로세스2는 자원1을 추가로 필요로 하여 대기
  5. 각 프로세스가 필요한 자원이 상대방에 의해 점유되고 있어, 모두가 무한 대기에 빠짐

이처럼, 이미 할당된 자원을 해제하지 않는 한 양쪽 모두 앞으로 진행할 수 없게 됩니다. 이것이 바로 Deadlock(교착 상태)입니다.

 

Deadlock 예시

3. 데드락 발생 조건 (4가지)

교착 상태가 발생하려면 아래 네 가지 조건이 모두 충족되어야 합니다.

  1. 상호 배제(Mutual Exclusion)
    • 자원은 한 번에 오직 한 프로세스만 사용할 수 있어야 합니다.
    • 예) 프린터, 파일, 세마포어 등
  2. 점유 대기(Hold and Wait)
    • 최소 한 프로세스가 자원을 점유하고 있으면서, 다른 자원을 추가로 요청하며 대기합니다.
  3. 비선점(No Preemption)
    • 이미 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없습니다.
  4. 순환 대기(Circular Wait)
    • 두 개 이상의 프로세스가 원형을 이루며 자원을 대기합니다.
    • 예) P1이 자원A를, P2가 자원B를 점유하고 있고, P1이 자원B를, P2가 자원A를 기다리는 순환 구조

이 네 가지 중 하나라도 성립하지 않으면 교착 상태가 발생하지 않습니다. 따라서 데드락을 예방하려면 이 조건들을 깨뜨리는 전략을 사용할 수 있습니다.

4. 데드락 예방(Prevention) vs. 회피(Avoidance)

4.1 데드락 예방(Prevention)

데드락 발생 조건(4가지) 중 하나를 사전에 제거함으로써 교착 상태를 원천적으로 봉쇄하는 방법입니다.
다만, 자원 낭비나 프로세스 진행이 비효율적이라는 단점이 있을 수 있습니다.

  • 상호 배제 부정
    • 여러 프로세스가 동시에 자원을 사용하는 것을 허용(공유 가능 자원으로 설계).
  • 점유 대기 부정
    • 모든 자원을 프로세스 시작 전에 한꺼번에 할당(추가 요청을 방지).
  • 비선점 부정
    • 프로세스가 자원을 추가로 요청하면, 이미 점유 중인 자원을 반납하도록 설계(강제 선점).
  • 순환 대기 부정
    • 자원에 고유 번호를 매기고, 무조건 번호가 낮은 자원부터 차례대로만 할당하는 규칙을 적용(원형 대기 구조 방지).

 

4.2 데드락 회피(Avoidance)

시스템이 자원을 할당할 때, 미리 시뮬레이션하여 교착 상태가 발생할 가능성이 있다면 자원 할당을 보류(대기)하는 방식입니다.

  • 은행원 알고리즘(Banker's Algorithm)
    • 은행에서 고객들의 돈(자원) 요구를 모두 충족하기 위해 먼저 할당을 가정하고, 시스템이 안정 상태(Safe State)를 유지할 수 있는지 확인합니다.
    • 안전하다면 자원을 할당하고, 위험하다면 다른 프로세스가 자원을 해제할 때까지 대기합니다.
  • 자원 할당 그래프(Resource-Allocation Graph) 알고리즘
    • 자원과 프로세스를 노드로 두고, 요청 간선과 할당 간선으로 연결한 그래프를 구성합니다.
    • 프로세스가 자원을 요구할 때 간선을 변경했을 경우 사이클(Cycle)이 발생하는지 검사합니다.
      • 사이클이 생기면 교착 상태 위험이 있다고 보고 자원 할당을 하지 않습니다.
      • 사이클이 없으면 안전하므로 자원을 할당합니다.

5. 데드락 탐지(Detection) & 회복(Recovery)

이미 교착 상태가 일어나도록 허용하고, 문제가 생기면 그때 탐지 알고리즘을 통해 확인하고 회복하는 방식입니다.

5.1 탐지(Detection)

  • 자원 할당 그래프나 교착 상태 탐지 알고리즘을 정기적으로 실행하여 데드락 여부를 파악합니다.
  • 탐지 알고리즘은 오버헤드(추가 비용)가 발생하기 때문에, 시스템 성능에 영향을 줄 수 있습니다.

5.2 회복(Recovery)

  • 프로세스 종료
    • 교착 상태에 빠진 모든 프로세스를 강제 종료하거나, 하나씩 종료해 교착 상태 해소 여부를 확인합니다.
  • 자원 선점
    • 교착 상태에 빠진 프로세스가 점유 중인 자원을 강제로 빼앗아 다른 프로세스에게 넘깁니다(해당 프로세스 일시정지).
    • 우선 순위가 낮은 프로세스나 작업량이 적은 프로세스부터 자원을 회수하여 시스템을 회복시킵니다.

6. 자주 묻는 질문(FAQ)

Q1. 데드락(교착 상태)가 뭔가요? 발생 조건을 간단히 말해 주세요.

  • 데드락은 여러 프로세스가 서로의 자원을 기다리면서 무한 대기에 빠지는 상태입니다.
  • 상호 배제, 점유 대기, 비선점, 순환 대기 등 4가지 조건이 동시에 충족되어야 발생합니다.

Q2. 은행원 알고리즘(Banker's Algorithm)은 무엇인가요?

  • 교착 상태를 회피하는 기법 중 하나입니다.
  • 프로세스가 자원을 요청할 때, 미리 자원 할당을 가정해보고 시스템 전체가 안전 상태를 유지할 수 있는지 검사한 뒤 할당 여부를 결정합니다.

Q3. 기아 상태(Starvation)와 데드락은 같은 건가요?

  • 기아 상태는 특정 프로세스가 계속 자원 할당 우선순위에서 밀려 무한정 대기하는 현상이고,
  • 데드락은 서로가 자원을 기다리는 순환 구조가 발생해 아무도 진행할 수 없는 상태입니다.
  • 즉, 발생 원리와 특징이 다릅니다. 대표 예시로 “식사하는 철학자 문제”가 있습니다.

마무리

교착 상태(Deadlock)는 운영체제(Operating System)의 동시성 제어에서 가장 중요한 이슈 중 하나입니다.
자원을 효율적으로 할당하되, 시스템이 멈춰버리는 사태를 피하기 위한 다양한 알고리즘(예방·회피·탐지·회복)을 살펴봤습니다.

  • 교착 상태 예방: 한 번이라도 발생 조건을 부정(깨뜨리는)하여 애초에 데드락을 막는 방식
  • 교착 상태 회피: 교착 상태가 발생할 위험을 미리 시뮬레이션하여 안전할 때만 자원을 할당
  • 교착 상태 탐지 & 복구: 실제로 데드락이 발생해도, 이를 탐지하고 프로세스를 종료하거나 자원을 선점하여 문제를 해결

시스템 규모가 커지고, 자원 사용이 복잡해질수록 데드락 문제가 발생할 확률도 높아집니다. 개발 단계에서부터 동시성 제어와 자원 할당 로직을 꼼꼼히 설계해야 안전(Safe)하고 효율적인 시스템을 구축할 수 있습니다.

저작자표시 (새창열림)