Operating System - 데드락(DeadLock)

데드락(DeadLock)

데드락이란?

ㆍ 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 현상을 말하며, 교착 상태라고도 부른다.

ㆍ 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생한다.

 

 

ㆍ Process 1과 Process 2가 Resource 1, 2 둘 다 얻어야 한다고 가정해본다.

ㆍ Process 1이 Resource 1을 얻고 Process 2가 Resource 2를 얻은 상태에서, Process 1은 Resource 2를 기다리고 Process 2는 Resource 1을 기다리게 된다.

ㆍ 하지만, 서로 원하는 자원이 상대방에게 할당되어 있기 때문에 두 프로세스는 무한정 기다리게 되는데 이러한 상태를 데드락(DeadLock) 상태라고 한다.

 

데드락이 주로 발생하는 경우

1. 멀티프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황에서 발생할 수 있다.

2. 어떤 프로세스가 자원을 요청했을 때, 그 시각에 해당 자원을 사용할 수 없는 상황이 발생할 수 있다. 이때 프로세스는 대기 상태로 들어간다.

3. 대기 상태로 들어간 프로세스들이 실행 상태로 변경될 수 없을 때 데드락 상태가 발생한다.

---

데드락(DeadLock) 발생 조건

ㆍ 데드락이 발생하기 위해서는 아래 4가지 조건이 모두 성립해야 한다. (단 하나라도 성립하지 않으면 데드락 문제는 해결이 가능하다.)

 

1. 상호 배제(Mutual Exclusion)

ㆍ 자원은 한 번에 하나의 프로세스만이 사용할 수 있어야 한다.

 

2. 점유 대기(Hold and Wait)

ㆍ 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.

 

3. 비선점(No Preemption)

ㆍ 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없아야 한다.

 

4. 순환 대기(Circular Wait)

ㆍ 프로세스의 집합에서 프로세스들은 순환 형태로 자원을 대기하고 있어야 한다.

---

데드락(DeadLock) 처리

교착 상태를 예방 & 회피

1. 예방(Prevention)

ㆍ 교착 상태 발생 조건 중 하나를 제거함으로써 해결하는 방법이다. 자원의 낭비가 심하다는 단점이 있다.

ㆍ 상호 배제 부정 : 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다.

ㆍ 점유 대기 부정 : 프로세스가 실행되기 전에 필요한 모든 자원을 할당한다.

ㆍ 비선점 부정 : 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 한다.

ㆍ 순환 대기 부정 : 자원에 고유한 번호를 할당하고 번호 순서대로 자원을 요구하도록 한다.

 

2. 회피(Avoidance)

ㆍ 교착 상태가 발생하면 피해나가는 방법이다.

ㆍ 은행원 알고리즘 : 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 데서 유래한 기법이다. 프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지를 사전에 검사하여 교착 상태를 회피하는 기법이다. 안정 상태에 있으면 자원을 할당하고, 그렇지 않으면 다른 프로세스들이 자원을 해지할 때까지 대기한다.

 

교착 상태를 탐지 & 회복

1. 탐지(Detection)

ㆍ 자원 할당 그래프를 통해 교착 상태를 탐지하는 방법이다.

 

 

ㆍ 위 그림은 자원 할당 그래프의 예시이다.

ㆍ 프로세스 P1으로부터 자원 R1으로의 간선은 P1 → R1으로 표현하며 이것은 프로세스 P1이 자원 R1을 요청하는 것으로, 현재 해당 자원을 기다리는 상태이다.

ㆍ 자원 R1으로부터 프로세스 P2로의 간선은 R1 → P2로 표현하며, 이것은 자원 P2가 프로세스 R1에 이미 할당된 것을 의미한다.

ㆍ자원을 요청할 때마다 탐지 알고리즘을 실행하기 때문에 그에 대한 오버헤드가 발생한다는 단점이 있다.

 

2. 회복(Recovery)

ㆍ 교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법이다.

ㆍ 프로세스를 종료하는 방법

     - 교착 상태의 프로세스를 모두 중지시킨다.

     - 교착 상태가 제거될 때까지 하나씩 프로세스를 중지시킨다.

ㆍ 자원 선점 방법

     - 교착 상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하며, 해당 프로세스를 일시 정지시킨다.

     - 우선순위가 낮은 프로세스, 수행된 횟수가 적은 프로세스 등을 위주로 프로세스의 자원을 선점한다.