교착 상태

 

 

 

---

 

교착 상태는 무엇이며 어떻게 해결할까?

 

 

---

 

 

 

 

교착 상태 (Deadlock)

 

--

교착 상태는

일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상을 말한다.

 

--

 

 

 

 

자원 할당 그래프 (Resource-Allocation Gragh)

 

--

자원 할당 그래프는

어떤 프로세스가 어떤 자원을 사용하고 있고, 어떤 자원을 기다리고 있는지를 표현하는 간단한 그래프다.

 

• 프로세스  :  원형
• 자원  :  사각형
• 사용 가능한 자원의 수  :  점
• 프로세스가 어떤 자원을 할당받아 사용 중  :  자원(점)에서 프로세스(원형)를 향한 화살표
• 프로세스가 어떤 자원을 기다리는 중  :  프로세스(원형)에서 자원(점)을 향한 화살표

 

--

 

 

 

 

교착 상태 발생 조건

 

--

교상 상태가 발생하는 조건 4가지

• 상호 배제
• 점유와 대기
• 비선점
• 원형 대기

위 4가지 조건이 모두 만족될 때 교착 상태가 발생할 가능성이 생긴다.

 

 

 

상호 배제 (Mutual Exclusion)

자원은 한 번에 하나의 프로세스만 접근(사용)이 가능하다는 조건이다.

만약 하나의 자원에 여러 프로세스가 접근(사용)이 가능하다면
자기 차례를 기다리지 않고 바로 자원 사용할 수 있으니 교착 상태가 발생하지 않을 것이다.

 

 

 

점유와 대기 (Hold and Wait)

최소 하나의 자원을 보유(사용중)한 상태에서

다른 자원도 사용하기 위해 기다리는 프로세스가 존재해야 하는 조건이다.

만약 자원을 사용하고 있으면서 추가로 다른 자원도 사용하기 위해 기다리고 있지 않다면
해당 프로세스는 작업이 정상적으로 동작하고 있다는 의미고,
사용 중이던 자원도 반납을 하게 되므로, 교착 상태가 발생하지 않을 것이다.

 

 

 

비선점 (No Preemption)

프로세스가 사용중인 자원을 자발적으로 해제(반납) 하지 않는 한,

다른 프로세스는 해당 자원을 강제로 가져갈 수 없다는 조건이다.

자원을 다른 프로세스가 강제로 가져갈 수 있다면 교착 상태가 발생하지 않을 것이다.

 

 

 

원형 대기 (Circular Wait)

각 프로세스가 다른 프로세스가 보유(사용중)한 자원을 기다리는 형태로

원형(순환) 구조를 이루고 있어야하는 조건이다.

뫼비우스 띠의 형태와 달리 시작과 끝이 존재한다면
결국 끝 지점에서는 자원을 기다리다 사용을 할 수 있게 될 것이므로, 교착 상태가 발생하지 않을 것이다.

--

 

 

 

 

교착 상태 해결 방법

 

--

교착 상태를 해결하기 위한 3+1가지 방법

• 예방  :  미리 교착 상태 발생에 대한 조건을 충족하지 않도록 시스템 설계하는 방법
• 회피  :  자원 요청 시 교착 상태의 위험을 예측하여 회피하는 방법
• 회복  :  교착 상태가 발생했을 때 이를 탐지하고, 프로세스를 중단 또는 자원 회수를 통해 시스템 복구하는 방법
• 무시  :  교착 상태가 발생하면 시스템을 재부팅하는 방법 (일반적으로 교착 상태 발생 확률이 낮은 시스템에서 사용)

 

 

교착 상태 예방

1. 자원의 상호 배제를 없애면?

모든 자원들은 공유가 가능해지므로, 이론적으로 교착 상태는 일어날 수 없다.

다만 현실적으로 모든 자원의 상호 배제를 없애기는 어렵기 때문에 해당 방식은 다소 무리가 있다.

 

2. 점유와 대기를 없애면?

이미 자원을 사용(보유) 중이라면 다른 자원을 사용하기 위해 대기를 못하므로, 이론적으로 교착 상태는 일어날 수 없다.

(만약 필요 자원이 3개라면 동시에 3개의 자원을 모두 할당하거나, 아예 할당하지 않아야 한다.)

하지만 이러한 경우 자원의 활용률이 낮아질 우려가 존재한다.

한 프로세스에게 필요한 자원을 몰아준 뒤에 모두 수행이 끝나면 다름 프로세스에게 자원을 몰아주는 구조라서

당장 자원이 필요해도 기다릴 수 밖에 없는 프로세스와

사용하지도 않으면서 오랫동안 할당되는 자원을 다수 양산해야 하기 때문에 자원의 활용률이 낮아진다.

(필요한 자원이 3개지만 그 중 1개는 이미 다른 프로세스가 사용 중이라면 3개다 할당하지 않고 실행하지 않는다.)

즉, "기아 현상"이 발생할 우려가 있다.

 

3. 비선점을 없애면?

다른 프로세스가 할당 중인 자원을 기다리지 않고 강제로 가져다가 사용할 수 있으니, 교착 상태는 일어날 수 없다.

이 방법은 선점하여 사용할 수 있는 일부 자원에 대해서는 효과적이지만, (ex CPU 자원)

말 그대로 일부 자원에 대해서만 가능하며, 모든 자원이 이렇게 선점이 가능한 것은 아니다.

(ex 한 프로세스가 프린터를 이용하는 도중에 다른 프로세스가 프린터를 강제로 가져가 사용하기 어려움)

그래서 다소 범용성이 떨어지는 방법이다.

 

4. 원형 대기 조건을 없애면?

시작과 끝이 존재하므로 교착 상태는 일어날 수 없다.

이 방법은 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하여 시작과 끝을 구분 짓는 방식으로 구성한다.

해당 방식이 비교적 가장 현실적이고 실용적인 방식이지만,

단점으로는 수많은 자원에 번호를 붙이는 것은 어려울 뿐더러

각 자원에 어떤 번호를 붙이는지에 따라 특정 자원의 활용률이 떨어질 수도 있다.

 

결과적으로 예방하는 방법으로는 여러 부작용이 따르게 된다.

 

 

 

교착 상태 회피

교착 상태가 발생하지 않을 정도로만 조심하게 자원을 할당하는 방식으로

교착 상태는 한정된 자원을 무분별한 할당으로 인해 발생하는 문제라고 간주하고 해결하는 방법이다.

 

즉, 안전 순서열(Safe Sequence)이라는 규칙을 통해

프로세스들에게 분배할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 정도의 양만큼만

자원을 배분하는 방법이다.

 

안전 순서열 (Safe Sequence)는
교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 의미한다.

예시로
여러 프로세스가 운영체제에게 자원을 요청한 상황에서
자원 할당을 "자원 A" -> "자원 T" -> "자원 C" 순으로 할당하면 교착 상태가 발생하지 않는다고 가정하면
해당 자원 할당 순서가 "안전 순서열"이 된다.

 

안전 순서열에 대한 상태 종류

• 안전 상태 : "안전 순서열"을 통해 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태
• 불안전 상태  :  "안전 순서열"이 없어서 교착 상태가 발생할 수도 있는 상태

 

안전 상태인 경우 (예시)

안전 순서열  :  프로세스 B -> 프로세스 A -> 프로세스 C

 

위 그림처럼 안전 순서열을 따라서 자원을 할당하여 정상적으로 작업을 종료시켜 다시 자원을 회수여

정상적으로 모든 프로세스를 수행할 수 있게 된다.

 

다만 안전 순서열이 없다면

순서 상관없이 마음대로 자원을 할당하게 되어 남은 자원은 없고 아직 프로세스가 정상 동작하기에 필요한 자원이 모르게 되어 교착 상태에 빠질 수 있다.

 

결국 시스템이 안전 상태로 움직이는 경우에만 자원을 할당하도록 하여 교착 상태를 회피한다.

 

 

 

교착 상태 탐색 및 복구(회복)

이전까지 설명한 방법은 교착 상태를 막기 위한 방법이었다면

해당 방법은 교착 상태가 발생한 뒤에 조치하는 방법이다.

 

두 가지 방법

• 선점을 통한 회복  :  교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
  (다른 프로세스의 자원을 강제로 빼앗으면서 한 프로세스에 자원을 몰빵)
• 프로세스 강제 종료를 통한 회복  :  가장 단순하면서 확실한 방식

--