[운영체제] 데드락(Deadlock)에 대해서 알아보자.

 

오늘은 OS의 데드락(Deadlock)에 대해서 알아보는 시간을 갖도록 하겠다.

 

(1) 개념

 - 데드락은 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 가리킨다. 즉, 프로세스가 자원을 얻지 못해서 다음 일을 처리하지 못하는 상태이다. 교착 상태라고도 말하는데 보통 시스템적으로 한정된 자원을 여러 곳에서 동시에 사용하려고 할 때 발생한다. 다중 프로그래밍 환경에서 흔히 발생할 수 있는 문제이다.

 

ex)

프로세스 1이 리소스 1을 사용하고 있고, 리소스 2를 사용하기 위해 요청했으며

프로세스 2가 리소스 1을 사용하기 위해 요청했고, 리소스 2를 사용하고 있다면

 

프로세스 1 -> 리소스 1(사용 - Lock) / 리소스 2(요청 - Wait)

프로세스 2 -> 리소스 1(요청 - Wait) / 리소스 2(사용 - Lock)

 

상태에서 프로세스 1, 2 모두 다음 리소스를 얻지 못해 멈추게 된다. 이는 사거리의 모든 자동차가 서 있는 상태와 같다.

 

 

(2) 발생 조건 4가지

 

 ① 상호배제 (Mutual exclusion)

  - 자원은 한 번에 한 프로세스만 사용 가능하다.

  - 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다.

 

 ② 점유대기 (Hold and wait)

  - 자원을 최소한 하나 점유(Lock)하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기(Wait)하는 프로세스가 존재해야 한다.

 

 ③ 비선점 (No preemption)

  - 이미 할당된 자원을 강제로 빼앗을 수 없다.

 

 ④ 순환대기 (Circular wait)

  - 대기 프로세스의 집합이 순환 형태(Cycle)로 자원을 대기(Wait)하고 있어야 한다.

 

 

 

(3) 처리 조건 4가지

 

 ① 예방 (Prevention)

  - 데드락 발생 조건 중 하나를 제거하면서 해결하는 방법이다.

  - 즉, 상호 배제, 점유 대기, 비선점, 순환 대기 4가지 조건 중 하나를 제거한다.

 

 ② 회피 (Avoidance)

  - 데드락이 발생할 시 피해가는 방법이다.

  - 흔히, 은행원 알고리즘을 사용하여 피해간다.

 

 ③ 탐지 및 회복 (Detection & Recovery)

  - 자원 할당 그래프를 통해 데드락을 감지하며, 만일 데드락을 감지할 경우 이전 상태로 회복하는 방법이다.

  - 일부러 데드락을 발생시키고 감지해서 회복하는 경우도 있다.

 

 ④ 무시 (Ignore)

  - 데드락 발생을 무시하고 지나가는 방법이다.

 

 

 

*은행원 알고리즘

 - 데드락을 처리하는 방법 중 회피에 해당하는 알고리즘이다. 데드락에 빠질 수 있는 상태를 불완전 상태, 데드락에 빠질 수 없는 상태를 안전 상태 라고 가정했을 때, 운영체제는 이러한 안전 상태인 경우에만 요청을 허락하여 자원을 할당해주고, 나머지 요구들은 안전 상태가 될 때 까지 계속 거절하는 알고리즘이다.

 

즉, 은행원 알고리즘은 최소한 한 명에게 대출해줄 수 있는 돈을 가지고 있어야 한다는 뜻에서 나왔으며, 바꿔말하면 운영체제가 최소한 하나의 프로세스가 일을 수행할 수 있는 경우에만 요청을 허락하여 시스템의 자원을 할당해주는 것과 같다.

 

 

 

References

교착 상태 - 위키백과, 우리 모두의 백과사전

[OS] 2020.11.16. 오늘의 면접 Q&A