#5 - 1) 교착상태 (Deadlock)

※ 이 글을 작성하기 전에 본인은 이 분야의 전문성을 가진 전문가가 아님을 미리 밝힙니다. ※

#1) 교착상태(Deadlock) 란 ?

교착상태는 다중 프로그래밍 시스템에서 상호배제(Mutual Exclusion)에서 나타낼 수 있는 문제점으로, 2개 이상의

프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상을 교착상태라고 한다.

교착상태를 그림으로 표현하면 위의 그림처럼 표현할 수 있다.

대문자로 적혀진 'A', 'B', 'C', 'D'를 프로세스로, 소문자로 적힌 'a', 'b', 'c', 'd'를 각 프로세스가 현재 점유하고 있는 자원이라고 가정해보자.

A , B , C , D 4개의 프로세스가 존재할 때, 위의 그림과 같이 A는 B가 가진 자원 'b'를 사용하고 싶어하고, B는 C가 가진 자원 'c'를, C는 D가 가진 자원 'd'를 D는 A가 가진 자원'a'를 사용하고 싶어하는 상황이 교착상태이다.

즉 ! 어느 한 프로세스를 강제적으로 종료해주지 않으면 마치 컴퓨터가 정지된 것처럼 보이는 현상이다.

교착상태는 "프로세스들에게 자원을 자유롭게 할당하는 과정에서 발생할 수 있는 현상" 이다.

 

#2) 교착상태 발생조건

교착상태의 발생조건은 다음과 같이 4가지 조건이 있다.

1. 상호배제 : 한 번에 한 개의 프로세스만이 공유 자원을 사용할 수 있어야 한다.

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

                     사용하기 위해서 대기하는 프로세스가 필요하다.

3. 비선점 : 다른 프로세스에 할당된 자원은 사용이 끝날 때 까지 강제로 빼앗을 수 없다.

4. 환형대기 : 공유 자원과 공유 자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된

                 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야 한다.

 

#3) 교착상태 해결 방법

교착상태를 해결하는 방법으로는 크게 4가지 방법이 있다.

1. 교착상태 예방 기법

2. 교착상태 회피 기법

3. 교착상태 발견 기법

4. 교착상태 회복 기법

위와 같이 크게 4가지 기법이 있다. 이 기법들에 대해서 알아보자.

 

#3 - 1) 교착상태 예방 기법

예방 기법은 교착 상태가 애초에 발생하지 않도록 예방하는 방법으로써, #2에서 이야기한 "교착상태 발생조건 4가지" 중, 하나를 부정함으로써 가능한 기법이다.

그렇다면 위의 4가지 조건들을 하나씩 부정해보자.

 

1. 상호배제 : 한 번에 한 개의 프로세스만이 공유 자원을 사용할 수 있어야 한다.

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

공유 자원을 여러 개의 프로세스가 동시에 사용할 수 있도록 만든다는 것인데, 사실상 이렇게 되면 공유 자원에 대한

관리가 이루어질 수 없고 제대로 프로그램이 작동될 수가 없어서 현실적으로 불가능한 부정 방법이다.

 

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

                     사용하기 위해서 대기하는 프로세스가 필요하다.

   점유와 대기 부정 : 프로세스가 실행되기 전에 필요한 모든 자원을 다 할당할 때 까지 실행되지 않도록 하거나, 반대로

                            자원을 요청하기 위해서는 어떠한 자원도 가지지 않았을 때 요청이 가능하도록 한다.

이를 위해서는, 프로세스가 실행되기 위해서 필요한 자원에 대한 정보를 미리 파악해야 하는데 이 정보를 파악하는데

많은 시간 낭비가 발생하고 드는 비용, 자원에 대한 내용 저장 및 관리가 굉장히 어려워서 문제점이 굉장히 많은 부정 방법이다. 또한, 실현했다고 가정하면, 많은 자원들이 사용되지 않으면서 오랫동안 할당만 되어 있기 때문에 자원의 효율성이 굉장히 낮아진다.

또한, 기아상태(Starvation)가 발생할 수 있다. 여기서 기아상태 라는 것은, 자주 사용되는 여러개의 자원을 필요로 하는 프로세스가 필요로 하는 자원 중 어느 하나라도 다른 프로세스에 할당되어 있는 동안 무한히 기다려야 하는 현상을 의미한다.

즉 ! 부정 하려면 할 수는 있지만, 단점도 굉장히 많고 실제 구현에 난해한 부분이 많아서 주로 사용되지는 않는 방법이다. 이를 위해 자원 사용에 대한 프로세스들의 우선순위를 할당하는 방식으로 이를 구현하기도 한다.

 

3. 비선점 : 다른 프로세스에 할당된 자원은 사용이 끝날 때 까지 강제로 빼앗을 수 없다.

   비선점 부정 : 다른 프로세스에 할당된 자원을 가져와서 사용 가능하게 한다.

이 부정방법 또한 공유 자원에 대한 동기화에 대한 의미가 깨져버리는 방식으로 실질적으로 부정하는 것이 불가능한 방법이다.

 

4. 환형대기 : 공유 자원과 공유 자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된

                 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야 한다.

   환형대기 부정 : 선형대기로 만들어서, 필요한 자원들을 순차적으로 획득한 후 실행되게 한다.

그나마 주로 사용되는 예방 기법이다. 중첩되어 있는 공유자원 사이에 요청 순서를 임의적으로 정해줌으로써 여러 개의 프로세스가 순환형 대기에 머물러 있게 되는 상황을 방지하는 기법이다.

 

위와 같이 부정방법들은, 실제로 구현이 난해한 방법들도 많고 불가능한 방법들도 많다. 가능하더라도 자원의 낭비가 심할 수 밖에 없는 방법들이 대부분이다.

 

#3 - 2) 교착상태 회피 기법

교착상태 회피기법은 교착상태가 발생할 가능성을 0으로 만드는 것이 아닌, 발생하더라도 피해가는 기법이다.

대표적인 방법으로 "은행원 알고리즘" 이 있다.

 

은행원 알고리즘은 "최소한 하나의 프로세스에게 할당해줄 만큼의 자원은 항상 CPU가 보유하고 있어야 한다" 라는 개념에서 나오게 된다.

특정 자원을 특정 프로세스에게 할당을 해줄 때, 이 할당으로 인해서 시스템이 교착상태에 빠질 가능성이 있는지 없는지를 판단해서 "안전상태"와 "불안전상태"로 나누는 것이다.

안전상태는 "시스템이 교착상태를 일으키지 않으면서 모든 프로세스들이 완료될 수 있는 상태" 를 의미한다.

불안전상태는 "교착상태가 발생할 수 있는 상태"를 의미한다.

즉 ! 프로세스가 특정 자원을 요청했을 때, 이를 수락함으로써 시스템이 불안전상태가 된다면, 안전상태가 될 때 까지 계속해서 이 요청을 거절하는 방식이다.

하지만 은행원 알고리즘은 다음과 같은 단점이 있다.

1. 할당할 수 있는 자원의 수가 일정해야 한다.

2. 프로세스의 수가 일정해야 한다.

3. 항상 안전상태를 유지해야 하므로, 자원에 대한 이용률이 굉장히 낮다.

4. 프로세스가 요구하는 최대 자원 요구량을 미리 알아야 한다.

5. 프로세스들은 반드시 유한 시간 내에 사용한 자원을 반납해야 한다.

이러한 가정들이 모두 이루어졌을 때 사용이 가능한 알고리즘이다보니, 실제로 이 알고리즘을 사용하는 사용률은 굉장히 낮다.

 

#3 - 3) 교착상태 회복 기법

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

회복기법은 사용자가 직접 처리하는 방법과 시스템에 의해 자동적으로 회복하게 하는 방법이 있다.

 

1. 사용자가 직접 처리

교착상태에 걸려있는 프로세스 중, 어느 하나의 프로세스를 사용자가 강제로 종료시켜 버리면 된다.

이를 통해 교착상태를 해결할 수 있다.

 

2. 시스템에 의해 처리

시스템에 의해 처리하는 방법으로는 다음과 같이 2가지 방법이 있다.

 

2 - 1) 프로세스 중지

프로세스 중지는 한 개 이상의 프로세스를 중지시킴으로써 교착상태를 회복하는 기법이다.

중지를 시킬 때는 "교착 상태에 속해 있는 모든 프로세스를 중지" 시키는 방법과 "교착 상태가 해결될 때 까지 한 프로세스씩 중지" 시키는 방법이 있다.

모든 프로세스를 중지시키는 방법은 확실하게 교착상태 해결이 가능하지만, 비용이 많이 든다는 단점이 있다. 왜냐하면 프로세스들이 오랫동안 연산을 했을 경우, 이 결과들을 다 폐기하고 다시 처음부터 진행을 해야 하기 때문이다.

하나의 프로세스 씩 중지시키는 방식은 모든 프로세스를 중지하는 것 만큼 비용이 많이 들지는 않지만, 모든 프로세스들을 탐색하면서 '교착상태 탐지 알고리즘'을 호출하여 교착상태 여부를 확인해야 하기 때문에 오버헤드가 크다는 단점이 있다.

 

2 - 2) 자원 선점

자원선점은 프로세스들로부터 자원을 빼앗아서 교착상태가 해결 될 때 까지 다른 프로세스들에게 할당해 주는 방식이다. 이 때, 다음과 같은 조건들을 생각해 주어야 한다.

1. 선점 프로세스 선택 : 필연적으로 종료되어야 할 프로세스의 선택(희생자 선택)은 비용 최소화를 위해 선점의 순서를

                               결정해야 한다. 비용의 요인으로는 "프로세스가 점유하고 있는 자원의 수", "프로세스가 지금까

                                지 실행하는데 걸린 시간" 등이 된다.

2. 복귀(Rollback) : 어떤 프로세스는 교착 상태 해결을 위해 완전히 중지시킨 후 재시작 해야 한다.

3. 기아(Starvation) : 비용에 근거한 희생자의 선택은 계속해서 동일한 프로세스가 희생자로 선택될 수 있다는 문제점이

                          있다. 따라서, 똑같은 프로세스가 계속해서 선점되지 않도록 방지해 주어야 한다.

                          하나의 방법으로는 비용에 "희생자로 선택된 횟수"를 포함시켜 주면 된다.