Deadlock(교착 상태)

두 개 이상의 프로세스가 서로 상대방이 점유하고 있는 자원을 요구하며 무한정 대기하는 상태다.

교착 상태 발생 조건

아래 4가지 조건이 모두 동시에 성립할 때만 교착 상태가 발생한다. 반대로 말하면, 이 중 하나라도 깨뜨리면 교착 상태는 해결된다.

1. 상호 배제(Mutual Exclusion): 자원은 한 번에 하나의 프로세스만 사용 가능

2. 점유 대기(Hold and Wait): 최소한 하나의 자원을 보유한 채로 다른 프로세스에 할당된 자원 대기

3. 비선점(No Preemption): 다른 프로세스가 보유한 자원을 강제로 빼앗을 수 없음

4. 원형 대기(Circular Wait): 대기 프로세스의 집합이 순환 형태로 자원을 대기(A는 B의 자원을, B는 C의 자원을, ... , Z는 A의 자원을 대기)

교착 상태 해결

운영체제는 교착 상태를 미연에 방지하거나, 발생 후 해결하기 위해 다양한 기법을 사용한다.

1. 예방

교착 상태 발생 조건 4가지 중 하나를 근본적으로 제거하여 발생 자체를 막는 방법이다.

• 상호 배제 부정: 모든 자원을 공유 가능하게 설정(현실적으로 불가능)

• 점유 대기 부정: 프로세스 시작 시 필요한 모든 자원을 한 번에 할당하거나, 자원이 없을 때만 요청 가능하게 함(자원 효율성 저하)

• 비선점 부정: 자원을 점유한 프로세스가 다른 자원을 요청할 때 거절당하면, 가지고 있던 자원까지 모두 반납하고 대기(상태 복구 비용 발생)

• 원형 대기 부정: 모든 자원에 고유 번호를 매기고, 번호 순서대로만 자원을 요청하도록 제한(가장 현실적인 예방책)

이 중 원형 대기 부정이 가장 합리적인 방법이며, 그 이유는 다음과 같다.

• 자원을 할당할 때 순서를 정하여 할당하여 원형 대기는 더이상 발생하지 않게 되면서 간단하게 해결 가능

• 자원을 할당할 때 순서를 정하는 작업에 대한 자원이 소모되고, 순서를 할당하는 방법에 따라 자원을 사용하는 효율이 달라질 수 있음

2. 회피

교착 상태가 발생할 가능성이 있는 자원 할당을 애초에 하지 않는 방법으로, 시스템을 안전 상태(Safe State)와 불안전 상태(Unsafe State)로 구분하여 관리한다.

• 안전 상태: 모든 프로세스가 데드락 없이 정상적으로 종료될 수 있는 자원 할당 순서(안전 순서열)가 존재하는 상태

• 불안전 상태: 안전 순서열이 없어 교착 상태가 발생할 수도 있는 상태

3. 탐지 및 회복

교착 상태 발생을 허용하되, 주기적으로 검사하여 발생 시 복구하는 방법이다.

• 탐지: 자원 할당 그래프를 통해 사이클 존재 여부를 주기적으로 검사(검사 오버헤드 발생)

• 회복

  • 프로세스 종료: 교착 상태에 빠진 모든 프로세스 종료 또는 사이클이 없어질 때까지 하나씩 종료

  • 자원 선점: 교착 상태의 프로세스로부터 자원을 빼앗아 다른 프로세스에 할당(기아 현상 발생 가능)

4. 무시

교착 상태가 발생해도 아무런 조치를 취하지 않는 방법이다.

• 교착 상태는 매우 드물게 발생하는데, 이를 해결하기 위한 비용(예방/회피/탐지)이 더 크다고 판단할 때 사용

• 윈도우, 리눅스 등 대부분의 현대 운영체제가 채택하고 있는 방식(문제 발생 시 사용자가 재부팅하여 해결)

참고자료

• 혼자 공부하는 컴퓨터 구조+운영체제