DeadLock에 관해서 알아보자

* 본 내용은 운영체제를 공부하며 추후 복습하기 위해 포스팅하는 게시물입니다.

 

DeadLock(교착상태)

DeadLock을 설명할 때 교차로에서 차들이 서로에게 막혀 움직이지 못하는 그림이 자주 참고된다. 그렇다면 운영체제에서 DeadLock이란 무엇을 의미할까? 위키백과의 정의를 인용해보면 두개 이상의 작업이 상대방의 작업이 완료되기를 기다리며 자신의 작업을 수행하지 못하는 상태를 의미한다. 이것만 보면 DeadLock이 무엇인지 감이 잡히지 않을것이다. 운영체제에서 DeadLock이 무엇인지, 그리고 어떻게 발생하는지 자세히 알아보자

 

 

DeadLock 발생조건

1) Mutual Exclusion : 자원을 사용할 때 하나의 프로세스만 사용되는 특성을 의미

2) Hold And Wait : 프로세스가 자원을 요청할 때 자신이 할당받은 자원은 소유하고 있음을 의미

3) No Preemption : 할당받은 자원은 프로세스 스스로 반납하지 않는 한 자원은 빼앗기지 않음을 의미 

4) Circular Wait : 자원을 요청하는 프로세스와 자원을 할당받은 프로세스 간 순환이 발생하는 것을 의미 

 

* 4가지 조건을 모두 충족할 때 DeadLock이 발생한다.

 

자원은 공유를 할 수 없기 때문에 Mutual Exclusion 조건은 반드시 충족된다. 공유를 하면 안되는 이유를 알고 싶다면 이전에 포스팅한 게시물을 참고하면 된다. 2021.03.19 - [운영체제] - Race Condition(경쟁 상태)이 발생하는 사례란?

자원은 빼앗길 수 있는 자원과 빼앗겨서는 안되는 자원으로 나뉜다. 빼앗겨서는 안되는 자원이 존재하기 때문에 No Preemption 조건도 충족되어야 한다. 

프로세스를 수행하기 위해서 자원이 필요한대 필요한 자원들은 다른 프로세스가 사용하고 있기 때문에 대기한다. 대기를 하다가 자원을 사용한 프로세스가 자원을 반납하면 대기하는 프로세스는 자원을 할당받아야 하는데 상대방에서도 동일하게 대기하기 때문에 DeadLock이 발생한다. 즉, 이 과정에서 Circular Wait과 Hold And Wait 조건이 충족되어 DeadLock 발생하며 운영체제에서 DeadLock이란 프로세스가 필요한 자원을 얻지 못해 수행하지 못하고 무한히 대기하는 상태이다. 

 

이런 DeadLock을 운영체제는 4가지 방법으로 대처할 수 있다. 

1) DeadLock Prevention

 - DeadLock이 발생하기 전 발생조건 4가지 중 하나라도 충족시키지 않음으로써 DeadLock을 예방한다.

 - Mutual Exclusion, No Preemption 조건은 반드시 충족시켜야 하는 조건이기 때문에 나머지 조건을 충족시키지 않는다.

 - 자원을 가지고 자원을 요청할 때 DeadLock이 발생할 가능성이 존재하기 때문에 프로세스 생성 후 완료되기 까지 필요한 모든 자원을 할당받는 방법과 요청한 자원을 할당받을 수 있을때만 자원을 가지고 있는 방법이 있다.

 

2) DeadLock Avoidance

 - 자원에 관한 인스턴스 개수에 따라 회피하는 알고리즘이 다르다.

 - 인스턴스가 1개일 때 자원 할당 그래프 알고리즘, 2개 이상일 때 Banker's 알고리즘을 사용한다.

 

자원 할당 그래프 알고리즘

• 프로세스와 자원을 그래프로 표현하여 프로세스가 자원을 요청 할 때 Circle이 생길 가능성이 존재하면 할당가능함에도 불구하고 할당하지 않음으로써 DeadLock을 회피한다.

Banker's 알고리즘

• 자원에 관한 인스턴스를 나타내는 개수를 테이블로 표현하는 알고리즘이다.
• 프로세스가 실행 될 때 완료되기 까지 필요한 자원 수를 표현하며, 할당된 자원 수도 테이블로 표현한다.
• 프로세스 마다 필요한 총 자원 수 - 할당된 자원 수를 통해 앞으로 필요한 자원 수도 테이블로 표현한다.
• 프로세스가 자원을 요청할 때 할당할 수 있는 가용자원이 있음에도 불구하고 앞으로 필요한 자원 수가 가용자원보다 많다면 자원을 할당하지 않는다.

3) DeadLock Detection And Recovery

 - DeadLock이 발생되어 프로세스가 느려지거나 이상을 감지되면 탐지 후 회복한다.

 - 회피와 마찬가지로 자원에 관한 인스턴스가 1개일 때와 2개이상일 때 탐지하는 알고리즘이 다르다.

 - 인스턴스가 1개일 때 자원 할당 그래프 알고리즘, 2개 이상일 때 Banker's 알고리즘을 사용한다. 

 - 탐지에 관한 알고리즘 수행시간은 O(n^2)이다.

 - 탐지 후 회복은 DeadLock에 관련된 모든 프로세스를 죽이거나, 관련된 프로세스를 하나씩 죽이거나, 프로세스로부터 자원을 빼앗는 방법이 존재한다.

 - 빼앗는 방법의 경우 같은 프로세스만 자원을 빼앗길 가능성이 존재하기 때문에 특정 프로세스가 Starvation이 발생할 수 있다.

 

4) DeadLock Ignorance

 - DeadLock은 자주 발생하지 않으며 예방하거나 회피, 탐지 후 회복으로 대처를 할 경우 많은 오버헤드가 발생하기 때문에 현대의 운영체제는 DeadLock을 무시하는 행동을 취한다. 

 - DeadLock이 발생하면 프로레스가 느려지는 이상반응이 생기기 때문에 사용자가 프로세스를 종료시킨다.