교착상태

개요

• 교착상태: Deadlock
• 두 개 이상의 프로세스가 서로의 작업이 끝나기만을 기다리고 있어 둘 다 영원히 끝나지 않는 상황을 가리킨다.

예시

semaphores A and B, initialized to 1

Process1	Process2
wait(A);	wait(B);
wait(B);	wait(A);

교착상태의 4가지 필요조건

• 아래 4가지 조건이 모두 만족되는 경우 데드락이 발생할 가능성이 있다.
• 하나라도 만족하지 않으면 절대 발생하지 않는다.

1. 상호 배제(Mutual exclusion)
   • 한 리소스는 한 번에 한 프로세스만이 사용할 수 있음
2. 점유와 대기(Hold and wait)
   • 어떤 프로세스가 하나 이상의 리소스를 점유하고 있으면서 다른 프로세스가 가지고 있는 리소스를 기다리고 있음
3. 비선점(No preemption)
   • 프로세스가 태스크를 마친 후 리소스를 자발적으로 반환할 때까지 기다림 (강제로 빼앗지 않는다)
4. 환형 대기(Circular wait)
   • Hold and wait 관계의 프로세스들이 서로를 기다림

교착상태의 방지법

• 사전에 교착상태가 발생하지 않도록 조치하거나, 발생한 뒤에 고치는 방법이 있다. 대표적으로 아래 세 가지로 나눈다.

1. 방지(Prevention, 예방)
   • 할당 구조 측면에서, 교착상태가 발생할 수 있는 요구조건을 만족시키지 않게 함으로써 교착상태를 방지한다.
   • 네 필요조건 가운데 하나가 성립하지 않도록 할당 규칙에 미리 제약을 건다. 예: 필요한 자원을 한꺼번에 요청(점유와 대기 제거), 자원에 번호를 매겨 오름차순으로만 요청(환형 대기 제거), 기다리게 되면 가진 자원을 내놓게 함(비선점 제거)
2. 회피(Avoidance)
   • 리소스 할당의 측면에서, 교착상태가 발생할 가능성이 있는 자원 할당(unsafe allocation)을 하지 않는다.
   • 할당할 때마다 시스템이 안전(safe) 상태로 남는지 검사해 안전한 범위 안에서만 자원을 준다.
   • 대표적으로 은행원 알고리즘, 자원 할당 그래프 알고리즘(예약 간선)이 있다.
3. 탐지 및 회복(Detection and Recovery)
   • 교착상태가 발생할 수 있도록 놔두고 교착상태가 발생할 경우 찾아내어 고친다.
   • 탐지 : 할당에 제약을 두지 않고 자원 할당 그래프(대기 그래프)를 주기적으로 감시해 사이클이 생겼는지 찾는다.
   • 회복 : 교착상태에 빠진 프로세스를 강제로 종료하거나(전부 또는 하나씩), 자원을 선점해 다른 프로세스에 넘기고 빼앗긴 프로세스를 되돌린다.

• 드물게 일어난다고 보고 대처하지 않는 방법(무시, 타조 알고리즘)도 있다. 범용 운영체제 대부분이 이렇다.
• 헷갈리기 쉬운 구분: 제약 없이 그래프를 계속 감시하는 것은 예방이 아니라 탐지이고, 프로세스 강제 종료는 회복이다. 필요조건은 비선점과 환형 대기이며 "선점", "선형 대기" 가 아니다.

참고

• 초기 원문 출처: [지식잡식 블로그]