Deadlock

·2020년 8월 26일
1

Deadlock이란?

데드락(교착상태)이란, 두 개 이상의 작업이 서로 상대의 작업이 끝나기만을 기다리느라 결국 모두 아무것도 하지 못하는 상태를 말한다. 여러 개의 작업이 동시에 실행되는 프로그래밍인 멀티 프로세스, 멀티 스레드 프로그래밍에서 발생할 수 있는 이슈다. (일단 여기서는 멀티 프로세스 기준으로 작성하겠습니다..)




Deadlock 발생 조건

데드락이 발생하기 위한 조건에는 4가지가 있다. 이 4가지 조건을 모두 만족해야만 데드락이 발생한다.

1. 상호 배제 (Mutual Exclusion)

프로세스 간의 공유 자원은 한 번에 하나의 프로세스에만 할당된다.

즉, 여러 프로세스가 동시에 공유 자원을 사용할 수 없다.

2. 점유 대기 (Hold and Wait)

프로세스가 공유 자원을 점유하면서, 다른 공유 자원을 얻기 위해 대기하고 있는 상태를 말한다.

프로세스 1이 자원 B를 점유하고 있고, A를 사용하기 위해 대기하고 있다고 가정해보자.

그리고 다른 프로세스 2는 B를 사용하기 위해 대기하고 있는 상황이다. 프로세스 2는 1의 작업이 끝날 때까지 대기할 수밖에 없다.

3. 비선점 (No Preemption)

프로세스가 한 자원을 점유하고 있으면, 이를 다른 프로세스가 뺏을 수 없다.

4. 순환 대기 (Circular Wait)

다른 프로세스의 자원을 가지기 위해 대기하는 상황이 동그란 형태로(???) 만들어진 것이다.

점유 대기의 예시를 가져와 마저 이어가보도록 하자.

프로세스 1은 B를 점유하고 있고, A를 사용하고자 함.
프로세스 2는 C를 점유하고 있고, B를 사용하고자 함. → 1이 B를 내놓을 때까지 대기
프로세스 3은 D를 점유하고 있고, C를 사용하고자 함. → 2가 C를 내놓을 때까지 대기
프로세스 4는 A를 점유하고 있고, D를 사용하고자 함. → 3이 D를 내놓을 때까지 대기
4는 3의 작업이 끝나기를, 3은 2의 작업이 끝나기를, 2는 1의 작업이 끝나기를 기다린다.

즉, 1이 B를 내놓아야 최종적으로 4가 자원을 사용할 수 있는데 1은 또 4가 A를 내놓는 것을 대기함 .. 에바




Deadlock 예방하기

데드락은 위 4가지 조건이 모두 충족해야 발생하기 때문에, 이 중 하나의 조건만 해제해주면 데드락 발생을 막을 수 있다.

1. 상호 배제 조건 해제

여러 프로세스가 동시에 공유 자원을 사용할 수 있도록 한다.

하지만 이러면 부작용이 너무 많이 발생한다. 그러므로 상호 배제 자체를 없애는 것은 패스 !

2. 점유 대기 조건 해제

프로세스 실행 전에 필요한 모든 자원을 할당시킨다.

모든 자원을 프로세스가 할당받지 못하면 프로세스를 실행하지 않는다.

결과적으로 실행중인 프로세스가 어떠한 자원을 점유한 상태로 다른 자원을 위해 대기하는 일이 없어진다.

하지만 한 번에 모든 자원을 요구하고 할당받는 것은 효율적이지 않다. 또한 starvation이 발생할 수 있다.

3. 비선점 조건 해제

말 그대로 점유하고 있는 자원을 다른 프로세스가 뺏을 수 있도록 한다.

(읽기만 해도 아주 위험해 보이죠? 프로세스가 사용하던 자원을 갑자기 뺏긴다면 .. 😇)

4. 순환 대기 조건 해제

해제할 4가지 있는 중 그나마 실현 가능한? 해제 할 만한? 조건이다.

프로세스들이 원형으로 꼬리의 꼬리를 물지만 않으면 된다.

먼저, 자원에 순서를 부여한다. 프로세스는 이 번호 순서대로만 자원을 요구할 수 있다. 
예를 들어 프로세스 1이 B 자원을 가지고 있으면, A는 요구할 수 없고 C, D, .. 를 요구할 수 있다.

하지만 4번을 포함한 모든 조건 해제 방식은 비효율적이고, 현실적으로 불가능한 경우도 있다.




Deadlock 회피하기

1. 자원 할당 그래프 알고리즘 (Resource Allocation Graph)

프로세스가 자원을 요청하고자 할 때, 자원 할당 그래프탐색해서 순환 대기 상태가 나타나는 지 확인한다.

(하지만 자원을 요청할 때마다 그래프를 탐색한다면 많은 비용이 발생한다.)

아무튼 !

순환 대기 상태가 나타나는 것을 확인했다면 이 상태로부터 벗어나야 한다. 두 가지 방법이 있다.

  1. 데드락을 일으킨 프로세스 종료

    교착 상태의 모든 프로세스를 종료시키거나, 교착 상태가 사라질 때까지 프로세스를 하나씩 종료시킨다.

    • 하나씩 종료한다면, 어떤 순서로 종료시킴 ?

      → 종료시키는 기준을 따로 만든다. (Cost Model) ex. 우선 순위, 총 수행 시간

  2. 자원 선점(=뺏어버리기!)

    선점하고자 하는 자원을 점유하는 프로세스를 종료시킨 후, 그 자원을 뺏는다.

    • 선점할 자원은 어떤 기준으로 고르는데 ?

      → 역시나 Cost Model 필요함

2. 은행원 알고리즘 (Banker's Algorithm)

데드락이 발생할 수 있는 상태를 불안전 상태로, 그렇지 않은 상태를 안전 상태라 했을 때

안전 상태가 될 것이 100% 보장되는 경우에만 요청을 받아들인다.

은행에 2000원이 있고, 고객 3명이 동시에 대출을 요청하는 상황이라고 가정해보자.

🐶 A : 저는 5000원만 모이면 안전 상태가 되는데 지금 2000원이 모자라요 .. 
🐶 B : 저는 3000원만 모이면 안전 상태가 되는데 지금 3000원이 모자라요 ..
🐶 C : 저는 7000원만 모이면 안전 상태가 되는데 지금 1000원이 모자라요 ...

이 때 현재 가지고 있는 자원인 2000원으로 안전 상태를 만들 수 있는 고객은 ? A와 C

이렇게 현재 가지고 있는 자원으로 안전 상태를 만들 수 있는 경우에만 자원을 할당해준다.




Reference

https://ggodong.tistory.com/98

https://ko.wikipedia.org/wiki/교착_상태

https://kim-hoya.tistory.com/16

profile
이사중.. (티톨버림..)

0개의 댓글