교착상태(Deadlock): 발생 조건과 처리 전략

서로가 가진 자원을 기다릴 때 시스템이 멈춘다

교착상태(Deadlock)는 둘 이상의 프로세스가 상대 프로세스가 점유한 자원을 요구하면서 무한히 대기하는 상태다. 제한된 자원을 여러 프로세스가 함께 쓰는 멀티프로그래밍 환경에서 자원 할당과 해제가 정상적으로 이어지지 않으면, 어느 프로세스도 다음 작업으로 진행하지 못하는 교착 상태(Stalemate)에 빠진다.

메모리, CPU, I/O 장치처럼 수량이 제한된 자원을 공유하는 환경, 비선점형 자원 할당 정책, 프로세스 간 동기화 문제가 이런 상태의 배경이 된다.

⤢✕

교착상태를 만드는 조건

교착상태는 다음 4가지 Coffman 조건이 모두 성립할 때 발생한다.

• 상호배제(Mutual Exclusion): 한 번에 한 프로세스만 자원을 사용할 수 있다.
• 점유와 대기(Hold and Wait): 프로세스가 자원을 보유한 채 다른 자원을 요청한다.
• 비선점(No Preemption): 다른 프로세스가 점유한 자원을 강제로 빼앗을 수 없다.
• 순환대기(Circular Wait): 프로세스들이 원형으로 연결되어 다음 프로세스가 가진 자원을 기다린다.

따라서 이들 조건 중 하나라도 제거하면 교착상태를 예방할 수 있다. 각 조건을 부정하는 방식이 예방 전략의 출발점이 된다.

자원 할당 정책에 따른 대응

예방(Prevention)은 교착상태의 필요조건 자체를 성립하지 않게 만드는 접근이다. 상호배제가 필요한 자원을 공유 가능한 자원으로 전환하는 방식은 현실적으로 어려울 수 있다. 대신 필요한 자원을 한 번에 할당해 점유와 대기를 막거나, 자원을 선점할 수 있게 설계하거나, 자원에 순서를 부여해 순환 구조를 차단하는 방식을 사용할 수 있다.

회피(Avoidance)는 자원을 배정할 때마다 시스템이 안전 상태에 남는지 확인한다. 은행원 알고리즘(Banker's Algorithm)과 자원 할당 그래프(Resource Allocation Graph)를 활용하며, 동적 자원 할당을 위해 최대 필요 자원량을 미리 파악해야 한다.

탐지와 복구(Detection & Recovery)는 교착상태를 허용하되 주기적으로 발생 여부를 검사하는 방법이다. 발견 뒤에는 프로세스를 종료하거나, 자원을 선점하거나, 체크포인트와 롤백을 이용해 복구할 수 있다.

발생 확률이 매우 낮고 처리 비용이 발생 빈도보다 큰 경우에는 무시(Ignore)를 택하기도 한다. Ostrich Algorithm으로도 불리는 이 방식은 UNIX, Windows 등 일부 운영체제에서 채택한다.

자원 할당 그래프로 보는 대기 관계

자원 할당 그래프에서 프로세스는 원, 자원 타입은 사각형으로 표현한다. 자원에서 프로세스로 향하는 간선은 할당 간선(Assignment Edge)이고, 프로세스에서 자원으로 향하는 간선은 요청 간선(Request Edge)이다.

그래프에 사이클(Cycle)이 있으면 교착상태 가능성을 확인해야 한다. 자원 인스턴스가 단일한 경우에는 사이클이 곧 교착상태를 뜻하지만, 다중 인스턴스 환경에서는 사이클만으로 교착상태라고 단정할 수 없어 추가 분석이 필요하다.

운영 환경에서 마주치는 교착상태

데이터베이스에서는 트랜잭션 간 락(Lock) 경쟁이 대표적이다. 타임아웃(Timeout)을 설정하고 데드락을 탐지한 뒤 희생자(Victim)를 선택하는 방식으로 처리한다.

운영체제에서는 파일 시스템 접근, 메모리 할당 경쟁, 디바이스 드라이버 충돌에서 교착상태가 나타날 수 있다. 네트워크 시스템에서는 패킷 라우팅 경로의 순환, 버퍼 교착 상태, 분산 시스템의 상호 대기가 같은 문제로 이어진다.

시스템 설계 단계에서 자원 획득 순서와 동기화 방식을 검토해야 한다. 운영 중에는 성능과 비용을 함께 고려해 예방, 회피, 탐지 및 복구, 무시 중 적절한 전략을 선택한다.