13장. 교착상태

여러 프로세스는 각자가 필요한 자원을 할당받아 실행되는데, 이 과정에서 무한히 자원을 할당 받지 못하고 기다리다가 정지해버리는 교착상태가 발생할 수 있다.

 

13-1. 교착상태란

1) 식사하는 철학자 문제

원형 식탁에 앉아있는 철학자들의 앞에는 포크 두개로 먹을 수 있는 각자의 음식이 있고 각자 오른쪽에 포크 하나가 있을 때, 두개의 포크를 들기 전까지 철학자는 생각하는 시간을 가지며 기다려야 한다면 모든 철학자가 동시에 포크를 들어 식사를 할 때 어떤 철학자도 식사를 할 수 없는 상황

이렇게 일어나지 않을 사건을 기다리며 진행이 멈추는 현상을 교착상태(DeadLock)이라고 한다.

 

식사하는 철학자 문제에서

철학자 =프로세스 or 스레드

포크 = 자원, 임계구역

생각하는 행위 = 자원을 기다리는 것

으로 비유할 수 있다.

 

교착상태는 뮤텍스 락 등 다양한 상황에서 발생할 수 있으며 해결을 위해서는 

1) 교착상태가 발생했을 때의 상황을 정확히 표현하기

2) 교착상태가 일어나는 근본적이유 알기

를 해야한다.

 

2) 자원 할당 그래프

자원 할당 그래프: 교착상태가 발생했을 때의 상황을 한눈에 쉽게 표현하는 그래프

그래프 규칙

1. 프로세스는 원으로, 자원의 종류는 사각형으로 표현

2. 사용할 수 있는 자원의 갯수는 자원 사각형 내에 점으로 표현

3. 프로세스가 어떤 자원을 할당받아 사용중이라면 자원에서 프로세스를 향해 화살표를 표시

4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시

자원 할당 그래프 예시(출처 혼공컴운 책)

식사하는 철학자 문제처럼 자원할당 그래프가 원의 형태를 띌 때 교착상태가 발생한다.

교착상태가 발생하는 자원할당 그래프의 원의 형태(출처 혼공컴운 책)

 

3) 교착상태 발생 조건

어떤 환경일 때 교착상태가 발생하는가?

교착상태가 발생할 조건에는 네가지가 있고 네개를 다 충족할 때 교착상태가 발생한다. 하나라도 충족하지 않을 경우 교착상태는 발생하지 않는다.

 

1. 상호 배제

해당 자원을 한번에 하나의 프로세스만 이용할 수 있을 때

 

2. 점유와 대기

어떠한 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다릴 때

 

3. 비선점

어떠한 프로세스도 다른 프로세스의 자원을 강제로 빼앗아 사용할 수 없을 때

 

4. 원형 대기

프로세스들이 원의 형태로 자원을 대기할 때

 

<확인 문제>

1. 교착상태에 대한 설명으로 옳지 않은 것

정답 = 4번 : 식사하는 철학자 문제에서 단 한명이 식사를 할 때는 교착상태 발생 x

2. 교착상태가 발생할 수 있는 네가지 조건

: 1. 비선점 2. 상호배제 3. 원형대기 4, 점유와 대기

3. 자원 할당 그래프 중 교착상태가 발생할 위험이 있는 그래프

정답 = 2번 : 원형 그래프

 

 

13-2. 교착상태 해결 방법

교착상태 해결 방법에는 크게 세가지가 있다. 그것은 바로 예방, 회피, 검출 후 회복

 

1) 교착상태 예방

= 교착상태 필요 조건 네가지 중 하나를 충족하지 못하게 하는 방법

 

1. 상호 배제 제거

: 모든 자원을 공유 가능하게 만든다. 현실성 x

 

2. 점유와 대기 제거

: 자원을 일부만 갖고 기다리는 상황 자체를 없애 모두 갖거나 아예 갖지 않거나 하는 방식

자원의 활용률 떨어짐. 많은 자원을 필요로 하는 프로세스가 무한정 기다리는 기아현상 발생 가능

 

3. 비선점 조건 제거

: 이용중인 프로세스로부터 자원을 빼앗을 수 있게 함

cpu자원에서는 가능하지만 프린터에서는 불가능 하듯 범용성이 떨어지는 방식

 

4. 원형대기 조건 제거

: 모든 자원에 번호를 붙이고 오름차순으로 자원을 할당

비교적 현실적이고 실용적이지만 수많은 자원에 번호를 붙이는 것이 간단하지 않고 어떤 번호인지에 따라 특정 자원의 활용률이 떨어질 수 있음

2) 교착상태 회피

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

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

 

 

안전 순서열 = 교착상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서

모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태, 안전 순서열대로 프로세스들에 자원을 배분한 상태 = 안전 상태

교착상태가 발생할 수도 있는 상황, 안전 순서열이 없는 상황 = 불안전 상태

 

교착상태 회피 방식은 항시 안전상태를 유지하도록 프로세스들의 최대 요구량과 현재 사용량 순서를 잘 조율하여 자원을 할당하는 것.

 

3) 교착상태 검출 후 회복

교착상태 예방과 회피는 교착상태 발생을 막기 위한 노력이였다면 검출 후 회복 방법은 교착상태가 발생한 것을 인정하고 교착상태 검출 후 조치를 취하는 방식이다.

 

프로세스들이 자원을 요구할 때 마다 할당하며 교착상태 발생 여부를 주기적으로 검사하여 다음과 같은 방식으로 회복

1) 선점을 통한 회복

: 교착 상태가 해결될 때 까지 다른 프로세스로부터 자원을 강제로 빼앗아 한 프로세스씩 자원을 몰아줌

 

2) 프로세스 강제 종료를 통한 회복

: 강제 종료를 통해 가장 확실하고 단순한 방법으로 해결. 작업 내용을 잃게 될 위험이 있음.

 

+ 교착상태 무시

드물게 발생하는 교착상태의 잠재적 문제를 아예 무시하는 방법. 타조가 문제에 처했을 때 모른척 한다는 것을 따와 타조 알고리즘이라고도 부른다.

 

<확인 문제>

1. 교착상태를 회복하는 방법에 대해 옳지 않은 것

정답 = 2번 : 교착상태를 검출한 후에 선점을 통한 회복, 강제 종료를 통한 회복 가능

2. 5개 -> 남은 자원 3 - 2 (p2의 요구량 4에서 현재 사용량 2이므로 2만큼 필요함) + 4 (p2가 프로세스를 올바르게 종료한 뒤 자원 반납) = 3-2+4 = 5

3. 교착상태 대처 방법 중 타조 알고리즘이란 교착 상태를 무시하는 방법

4. 교착상태 예방 - 정답 : 4번 : 원형대기 조건을 제거해야 예방 가능