[OS] 교착상태(Deadlock, 데드락)의 정의, 발생 조건, 해결 방법

 

 

🚀

안녕하세요. 이번 포스팅은 NSC 전공시험이나 신입 기술면접에서도 자주 등장하는 주제인
교착상태(Deadlock)에 대해 한번 알아보고자 합니다.

 

 

🤔 교착상태란?

교착상태란 두 개 이상의 프로세스가 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며, 서로의 작업을 끝나기만을 기다리며 둘 다 영원히 끝나지 않는 상황을 뜻합니다.

위의 그림과 같이 자동차(프로세스)들이 각각의 도로(자원)를 점유한 상태에서 다른 자동차(프로세스)들이 사용하고 있는 도로(자원)를 사용하기 위해 대기하고 있지만, 도로 위에서 이러지도 저러지도 못하는 상황을 예시로 들 수 있겠습니다.

 

 

💣 교착상태의 발생 조건 4가지

교착상태는 아래의 4가지 조건이 모두 만족되는 경우(필요충분조건)에 발생할 가능성이 있으며,
하나라도 만족하지 않으면 교착상태가 발생하지 않습니다.

 

1. 상호 배제(Mutual Exclusion)

한 번에 한 개의 프로세스만이 공유자원을 사용할 수 있음

2. 점유 대기(Hold and Wait)

프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다림

3. 비선점(No Preemption)

프로세스가 작업을 마친 후 자원을 자발적으로 반환할 때까지 기다림
(이미 할당된 자원을 강제적으로 빼앗을 수 없음)

4. 순환 대기(Circular Wait)

프로세스의 자원 점유 및 점유된 자원의 요구 관계가 원형을 이루면서 대기하는 조건.
각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있음

 

 

💡 교착상태 해결방법

 

-  예방(Prevention)

교착상태 예방 방법은 교착상태가 애초에 일어나지 않도록 방지하는 방법으로 교착상태의 발생조건 4가지 중 하나를 부정함으로써 교착상태를 예방하는 방법입니다.

1. 상호 배제 부정

여러 개의 프로세스가 동시에 공유자원을 사용할 수 있음

2. 점유 대기 부정

프로세스가 실행되기 전에 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나, 자원이 점유되지 않은 상태에서만 자원 요청을 받도록 함

3. 비선점 부정

모든 자원에 대한 선점을 허용

4. 순환 대기 부정

자원을 선형으로 분류하여 고유 번호를 할당하고, 각 프로세스는 현재 점유한 자원의 고유번호보다 앞이나 뒤 한쪽 방향으로만 자원을 요구하도록 함

그러나 이렇게 교착상태 발생조건을 방지해서 데드락을 예방하는 방법은 시스템 처리량이나 자원 사용의 효율성을 떨어트리는 단점이 있습니다.

 

-  회피(Avoidance)

교착상태가 발생할 가능성이 있는 자원 할당(Unsafe allocation)을 하지 않고 안전한 상태(Safe state)에서만 자원 요청을 허용하는 방법입니다. 하지만 교착상태 회피를 하기 위해서는 아래와 같은 가정이 필요합니다.

• 프로세스 수 고정
• 자원의 종류와 수 고정
• 프로세스가 요구하는 최대 자원의 수를 알아야 함
• 프로세스는 자원 사용 후 반드시 반납

Safe state

safe sequence(교착상태를 발생시키지 않고 자원을 할당하는 순서)가 존재하며 모든 프로세스가 정상적으로 종료될 수 있는 상태를 의미

Unsafe state

교착상태가 발생할 가능성이 있는 상태

 

교착상태를 회피하기 위한 알고리즘으로 크게 두 가지가 있습니다. 

🔑 은행원 알고리즘(Banker's Algorithm)

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

기본 개념 자체는 "CPU는 최소한 하나의 프로세스에게 할당해줄 만큼의 자원을 항상 보유하고 있어야 한다" 입니다.

 

<예시> 시스템은 총 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)

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

자원 할당 그래프 : 프로세스가 어떤 자원을 사용 중이고, 어떤 자원을 기다리는지 방향성 있는 그래프로 표시한 것
예약 간선 : 향후 요청할 수 있는 자원을 가리키는 점선으로 표시된 간선

 

<예시> 그래프에서 사이클 발생 시 교착상태일 가능성이 있음

상호 배제 : R1, R2, R3, R4
점유 대기 : P1, P2
비선점 : O
순환 대기 : X
=> 교착상태 X

 

상호 배제 : R1, R2, R3, R4
점유 대기 : P1, P2, P3
비선점 : O
순환 대기 : O
=> 교착상태 O

상호 배제 : R1, R2
점유 대기 : P1, P3
비선점 : O
순환 대기 : O
=> 교착상태 X (P4가 R2를 해제하면 해결)

 

-  탐지(Detection)

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

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

 

-  회복(Recovery)

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

1. 사용자 처리

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

2. 시스템 처리

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