[운영체제] 데드락

데드락이란?

데드락은 2개 이상의 작업이 자원을 점유하고 있는 상태에서 서로의 자원을 무한정 기다리게 되어

어떤 작업도 더 이상 진행할 수 없는 상태를 말한다.

교착상태라고도 한다.

 

---

데드락의 필요조건

데드락의 필요조건는 총 4가지로

상호 배제, 비선점, 점유 대기, 순환 대기가 있다.

 

1. 상호배제

한 프로세스가 자원을 사용하고 있는 중이라면, 다른 프로세스는 해당 자원을 같이 쓸 수 없다는 것이다.

상호 배제 조건을 만족하지 않는다면, 서로의 자원을 무한정 기다리는 것이 아니라 그냥 같이 사용하면 되기 때문에, 데드락 상황이 발생하지 않는다. 

 

2. 비선점

한 프로세스가 자원을 사용하고 있는 상황에서 다른 프로세스가 해당 자원을 선점할 수(빼앗을 수) 없다는 것이다.

비선점 조건을 만족하지 않는다면, 자원이 필요하면 선점하면 되기 때문에 데드락이 발생하지 않는다.

 

3. 점유 대기

프로세스가 자원을 점유하고 있는 동시에 다른 자원을 기다리는 상황이어야 한다.

다른 프로세스가 필요로 하는 자원을 점유하면서 다른 프로세스가 가지고 있는 자원을 기다려야만 데드락이 발생한다.

 

4. 순환 대기

프로세스 간의 관계가 원을 이뤄 서로 자원을 양보하지 않는 상황이여야 한다.

프로세스들이 점유하고 있는 자원과 기다리는 자원을 도식화 하면 사이클이 발생해야 한다는 것이다.

사이클이 발생하는 상황과 사이클이 발생하지 않는 상황은 그림으로 이해하는 것이 더 쉽다.

 

 

 (1) 사이클 발생

사이클 발생

- 실선 화살표: 프로세스가 자원을 점유 (방향은 자원에서 프로세스로)

- 점선 화살표: 프로세스가 자원을 대기 (방향은 프로세스에서 자원으로)

 

이런 상황이라면 각 프로세스가 점유과 대기를 하고 있는 상태가 사이클이 발생한 것이다.

어느 프로세스도 양보하지 않는 상황이다.

 

2. 사이클 발생X

사이클 발생 x

사이클이 발생하는 그림에서 달라진 점은 Process3이 대기하는 자원이 1이 아니라 4인 것이다.

이러한 상황의 경우 사이클이 발생하지 않았다.

따라서 Process3부터 자원 4를 대기하고 있다가 점유한 후에 정상적으로 종료하고, Process2도 자원 3을 대기하고 있었다가 Process3이 자원을 해제했기 때문에 자원3을 점유한 후 종료하면 된다. 이렇게 차례대로 자원을 점유할 수 있다.

 

---

데드락 해결방법

해결방법으로는 예방, 회피, 검출 및 회복이 있다.

1. 예방

예방한다는 것은 바로 위에서 본 데드락의 필요조건이 발생하지 않도록 미리 예방한다는 것이다. 즉, 조건을 무력화시킨다는 것이다.

간단하지만 문제가 있다.

 

 

- '상호 배제'를 예방한다는 뜻은, 한 자원을 동시에 사용한다는 것인데, 이는 critical section(임계구역)을 보호하지 못한다는 문제가 있다.

 

- '비선점'을 예방한다는 뜻은, 한 프로세스가 다른 프로세스가 점유하고 있는 자원을 선점할 수(빼앗을 수) 있다는 것이다.

  만약 선점할 수 있다면, 어떤 기준으로 선점할지 정할 것이다. 예를 들어 우선순위가 높은 프로세스가 우선순위가 낮은 프로세스가 점유하고 있는 자원을 선점할 수 있다고 해보자. 이러할 경우 우선순위가 낮은 프로세스는 끝까지 자원을 점유하지 못하고 아사할 가능성이 있다.

 

- '점유 대기'를 예방한다는 것은 어떤 프로세스가 한 프로세스를 점유하고 있다면 강제로 다른 프로세스를 대기하지 못하도록 하는 것이다.

이 방법을 사용하면 필요한 자원을 모두 점유하거나, 아니면 아무것도 점유하지 못하거나 둘 중 하나일 것이다.

그렇다면 프로세스마다 어떤 자원을 사용할지 미리 알아야 하는데 현실적으로 불가능하고

당장 자원이 필요하지 않더라도 앞으로 쓸 자원까지 모두 점유하기 때문에 자원의 활용성이 떨어진다.

또한 자원이 많이 필요한 프로세스일수록 자원을 점유하기 힘들어지기 때문에 아사 현상이 발생할 수 있다.

이러한 문제들로 점유대기를 예방한다는 것은 좋은 선택이 아니다.

 

- '순환 대기'를 예방한다는 것은 프로세스들의 점유와 대기 모양이 사이클이 발생하지 않도록 하는 것이다.

이를 위해서는 원형이 아니라 직선 즉, 한 방향으로 자원을 점유하고 대기하면 된다는 것이다.

한 방향으로 점유하고 대기하기 위해선 자원마다 번호를 붙여서, 작은 숫자의 자원을 점유하고 있는 상황에서 큰 숫자의 자원을 점유하거나 대기하는 것은 허용하지만 반대로(작은 숫자 -> 큰 숫자)는 허용하지 않으면 된다.

하지만 이는 자원마다 어떻게 번호를 부여할지 애매하고 프로세스 작업을 진행할 때 유연성이 떨어진다는 문제가 있다.

 

결론 적으로 예방하는 방법은 좋은 방법이 아니다.

 

 

2. 회피

회피는 어느 수준 이상의 자원을 나누어주면 데드락이 발생하는지 파악해서 애초에 그 수준 이하로 자원을 나눠주는 방법으로 데드락을 회피하는 것이다.

 

회피 방법 중 대표적으로 은행원 알고리즘이 있다.

은행에서 대출을 해줄 때의 상황을 빗댄 것이다.

대출을 할 때 무조건 원하는 금액만큼 대출해주지 않고, 대출 금액이 가능한 범위일 때만 대출을 해주고 그렇지 않다면 거부하는 방식이다.

 

프로세스가 자원을 필요로하는 상황에서 안정상태라면 자원을 할당하도록 하고, 불안정상태라면 자원을 할당하지 못하도록 한다.

그렇다면 안정상태와 불안정 상태는 어떤 기준으로 나누는 것일까?

바로 시스템에서 가용 자원의 수(n개)를 체크하고 각 프로세스마다 더 필요로 하는 자원의 수(m1, m2, m3, ,,,개)를 체크한 후에,

m1, m2, m3,.. 중 하나라도 n개보다 작거나 같으면 안정상태이고 그렇지 않으면 불안정 상태이다.

(불안정 상태일 때 자원을 할당하더라도 데드락이 발생하지 않을 수 있다. 하지만 데드락이 발생할 가능성이 있기 때문에 자원을 할당하지 않는 것이다.)

 

하지만 은행원 알고리즘에도 문제는 있다.

이 방법도 각 프로세스가 사용할 자원을 미리 알고 있어야 한다. 현실적으로 불가능하다. 

그리고 시스템의 가용 자원 수를 계산해야하기 때문에 전체 자원의 수가 고정적이여야 한다. 이것도 현실적으로 불가능하다.

또한 자원을 할당할 수 있는 상황임에도 불구하고 불안정 상태이기 때문에 자원을 할당하지 않는 것은 자원의 낭비이다.

 

결론적으로 회피 방법도 사용하기에는 문제가 있다.

 

3. 검출 및 회복

데드락을 검출하여 회복하는 방법이다.

데드락을 검출하는 방법으로는 타임아웃과 자원 할당 그래프가 있다.

 

- 타임아웃

일정 시간 동안 작업이 진행되지 않은 프로세스를 데드락이 발생한 것으로 간주하는 것이다.

간단하지만 문제가 있다.

일정 시간 동안 작업이 진행되는 않은 이유가 데드락이 아닌 네트워크 문제, 작업 속도 등의 이유일 수도 있기 때문에

데드락을 검출하는 방법으로는 완전하지 않다.

 

- 자원 할당 그래프

자원 할당 그래프를 보면 어떤 프로세스가 어떤 자원을 점유 및 대기하고 있는지 알 수있기 때문에 데드락을 검출 할 수 있다.

(위에서 설명한 데드락 필요조건의 순환대기 그림을 보면 됩니다)

어떠한 제한을 하지 않으면서 데드락을 검출하는데 정확하다!!

하지만 자원 할당 그래프를 유지, 갱신, 사이클 검사 작업으로 오버헤드가 발생한다는 단점이 있다.

 

타임아웃과 자원 할당 그래프를 통해 데드락을 검출하면 이제 회복하는 단계이다.

회복하는 방법은 데드락을 발생시킨 프로세스를 강제로 종료하는 것이다.

데드락을 발생시킨 프로세스들을 동시에 종료할 수도 있고, 순서대로 종료하는 방법도 있다.

만약 프로세스를 동시에 종료하면, 또 데드락이 발생할 수 있기때문에 순서대로 종료하는 것이 더 나은 선택이다.

 

---

데드락 발생 시 실제로 사용하는 방법

윈도우나 리눅스 등 대표 운영체제에서 데드락을 발생 했을 때는 아무 조치도 취하지 않는다. (데드락 무시)

개발자가 개입해야한다...

https://en.wikibooks.org/wiki/Linux_Applications_Debugging_Techniques/Deadlocks

Linux Applications Debugging Techniques/Deadlocks - Wikibooks, open books for an open world

이 문서를 보면 데드락의 발생여부를 확인할 수 있는 방법이 나온다. 그리고 데드락 자동 검출 라이브러리도 소개해준다.

 

프로젝트를 하다가 데드락이 실제로 발생하면 이 포스터로 다시 돌아와서 해결 방법을 더 써야겠다.