교착상태 DeadLock

DeadLock은 하나 또는 여러 개의 프로세스가 일어날 수 없는 사건을 영원히 기다리는 상태를 말한다.

DeadLock 발생조건

• 상호 배제
  • 한 번에 프로세스 하나만 해당 자원을 사용할 수 있다. 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야한다.
• 점유 대기
  • 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.
• 비선점
  • 이미 할당된 자원을 강제로 빼앗을 수 없다.
• 순환 대기
  • 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.

DeadLock 해결법

DeadLock 해결법은 크게 3가지로 분류할 수 있다.

• DeadLock 발생하지 않도록 예방하기
• DeadLock 발생 가능성을 인정하면서 적절하게 회피하기
• DeadLock 발생을 허용하지만 DeadLock을 탐지하여, DeadLock**에서 회복하기**

DeadLock 예방

DeadLock의 발생조건 4가지 중 하나라도 발생하지 않게 하는 것이 DeadLock을 예방하는 방법이다. 즉, 각각의 조건을 부정하여 DeadLock 발생 가능성을 차단한다.

• 상호 배제 부정 : 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다.
• 점유 대기 부정 : 프로세스 실행되기 전 필요한 모든 자원을 할당한다.
• 비선점 부정 : 이미 다른 프로세스에게 할당된 자원이 선점권이 없다고 가정할 때, 높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록 한다.
• 순환 대기 부정 : 자원을 순환 형태로 대기하는 것이 아닌 자원에 고유한 번호를 할당하고, 번호 순서대로 자원을 요구하도록 한다.

DeadLock 회피

예방법을 사용하면 시스템의 처리량이나 효율성을 떨어트리는 단점이 발생할 수 있다.

회피법은 예방법보다는 조금 덜 제한적인 방법으로 예방법의 단점을 일부 해결할 수 있다.

DeadLock 회피법에서는 Safe sequence, Safe state등이 있다.

시스템의 프로세스들이 요청하는 모든 자원을, DeadLock을 발생시키지 않으면서도 차례로 모두에게 할당해 줄 수 있다면 Safe state(안정 상태)에 있다고 말한다.

그리고 이처럼 특정한 순서로 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 DeadLock이 발생하지 않는 순서를 찾을 수 있다면, 그것을 Safe sequence(안전 순서)라고 한다.

Unsafe state(불안정 상태)는 안전 상태가 아닌 상황을 말한다. 즉, DeadLock 발생 가능성이 있는 상황이다. 불안정 상태가 DeadLock보다 좀 더 큰 집합이다.

이처럼 회피 알고리즘은 자원을 할당한 후에도 시스템이 항상 Safe state에 있을 수 있도록 할당을 허용하는 것이 기본 특징이다. 대표적으로 은행원 알고리즘이 존재한다.

은행원 알고리즘(Banker’s Alogorithm)

다익스트라가 제안한 기법으로, 은행에서 모든 고객의 요구를 충족할 수 있도록 현금을 대출해주는 것에서 유래되었다. 은행원 알고리즘은 자원 할당 결정전에 예상되는 모든 자원의 최대 할당량을 가지고 시뮬레이션 하여 Safe state에 들 수 있는지 여부를 검사하여 교착상태의 가능성을 미리 조사하는 알고리즘 이다.

<예시> 시스템은 총 12개의 자원을 가지고 있다고 가정

(t=t0)	최대 자원 요청량	할당중인 자원량	남은 필요한 자원의 양
P0	10	5	5
P1	4	2	2
P2	9	2	7

현재 할당 중인 자원량의 합 은 5+2+2 = 9 입니다. 시스템은 총 12개의 자원을 가지고 있으므로 현재 상태에서 가용 자원량은 12 - 9 = 3 이 된다.

여기서 가용자원을 어느 프로세스에게 할당해주느냐에 따라서 자원을 효율적으로 이용할 수 있게 된다.

• 남은 가용자원 3개를 P1에게 할당 => 가용자원은 3 - 2 = 1
• P1의 작업이 끝나고 할당되어 있던 자원 4개 반납 => 가용자원은 1 + 4 = 5
• 남은 가용자원 5개를 P0에게 할당 => 가용자원은 5 - 5 = 0
• P0의 작업이 끝나고 할당되어 있던 자원 10개 반납 => 가용자원은 0 + 10 = 10
• 남은 가용자원 10개 중 7개를 P2에게 할당 => 가용자원은 10 - 7 = 3
• P2의 작업이 끝나고 할당되어 있던 자원 9개 반납 => 가용자원은 3 + 9 = 12

이렇게 P1 - P0 - P2 순서로 자원 할당 시 Safe sequence를 만족하게 된다.

그러나 은행원 알고리즘의 경우 미리 자원의 최대 요구량을 알아야 하고, 할당할 수 있는 자원의 수가 일정해야 하는 등등 사용에 제약조건이 많다.

이처럼 교착상태 회피 방법의 가장 큰 문제는 문제 발생에 대한 일관성과 가정이 완벽할 것이라는 것을 보장하기가 현실적으로 어렵다는 점이다.

시스템의 규모가 작은 운영체제라면 고려해볼 만한 방법이지만, 멀티 리소스, 멀티 프로세스의 복잡한 운영체제 환경에서는 자원 할당 그래프를 분석하면서 Safe state를 파악하기가 상당히 어렵다.

자원 할당 그래프 알고리즘(Resource-Allocation Graph Algorithm)

자원 할당 그래프에 예약 간서을 추가하여 예약 간선으로 설정한 자원에 대해서 만 자원 할당을 요청할 수 있고 사이클이 형성되지 않을 때만 자원을 할당받는 방법이다.

DeadLock 탐지

시스템에 데드락이 발생했는지에 대한 여부를 탐색하고 회복 기법 알고리즘에 활용하는 것을 의미한다. 교착상태가 탐지되었다면 회복 기법을 통해 교착상태를 복구한다.

그러나 탐지 기법은 지속적으로 교착상태를 확인하는 작업이 필요하기 때문에 오버헤드(성능 저하)가 발생하게 된다.

DeadLock 회복

교착상태 회복 기법은 교착상태가 발생했을 때 해결하는 기법을 의미한다.

1. 사용자 처리

교착상태에 있는 프로세스 중 하나의 프로세스를 사용자가 강제 종료

2. 시스템 처리

1. 프로세스 중지
   • 교착상태에 속해있는 모든 프로세스를 중지
   • 교착상태가 해결될 때까지 한 프로세스씩 중지
2. 자원 선점
   • 프로세스들로부터 자원을 빼앗아 교착상태가 해결될 때까지 다른 프로세스들에게 자원을 할당