[CS기초] Deadlock(데드락)

Deadlock

Deadlock(교착 상태)은 둘 이상의 프로세스나 스레드가 서로가 가진 자원을 기다리며 영원히 진행되지 못하는 상태를 말하는데요. 운영체제에서 자원 할당과 동기화 문제가 발생했을 때 전형적으로 나타나는 동시성 버그 중 하나입니다.

 

 

Deadlock이 발생하는 4가지 조건 (Coffman Conditions)

Deadlock이 발생하려면 다음 네 가지 조건을 동시에 만족해야 합니다:

1. 상호 배제(Mutual Exclusion)
   • 한 자원을 동시에 둘 이상의 프로세스가 사용할 수 없음
2. 점유 및 대기(Hold and Wait)
   • 자원을 점유한 프로세스가 추가 자원을 기다림
3. 비선점(No Preemption)
   • 다른 프로세스가 점유한 자원을 강제로 회수할 수 없음
4. 환형 대기(Circular Wait)
   • 프로세스들이 원형으로 자원을 서로 기다리는 상황

이 네 가지 조건 중 하나라도 깨지면 Deadlock은 발생하지 않게 됩니다.

 

 

예시: 두 개의 스레드와 두 개의 락

// Thread 1
lock(A);
lock(B);

// Thread 2
lock(B);
lock(A);

Thread 1은 A를 점유한 채 B를 기다리고, Thread 2는 B를 점유한 채 A를 기다리는 상황으로, 이때 Deadlock 발생하게 됩니다.

 

 

Deadlock 예방/회피/복구

Deadlock은 크게 3가지 방식으로 다루게 됩니다.

• 예방(Prevention)
  • Deadlock 조건 중 하나를 명시적으로 제거
  • 자원 요청을 한 번에 다 받도록 요구하기 등
• 회피(Avoidance)
  • Deadlock이 발생하지 않는 안전한 상태만 유지
  • 대표 알고리즘: Banker’s Algorithm
• 탐지 및 복구(Detection and Recovery)
  • Deadlock을 허용하되, 주기적으로 탐지 후 복구
  • 사이클 탐지 후 프로세스 강제 종료하기 등

 

마치면서

Deadlock은 겉보기엔 프로그램이 정지한 것처럼 보이지만, 내부적으로는 자원을 서로 기다리느라 아무 일도 하지 못하는 상태인데요. 이는 디버깅이 까다롭고 해결이 어려워, 설계 단계에서 예방하는 것이 가장 바람직합니다. 동시에 잘 돌아가던 것들이, 서로를 기다리며 모두 멈추게 되는 것이 바로 Deadlock의 아이러니입니다.