DeadLock

DeadLock의 개념

• 프로세스가 자원을 얻지 못해서 다음 일을 처리하지 못하는 상태를 말한다. 교착상태라고도 하는데 보통 시스템적으로 한정적인 자원을 여러 곳에서 동시에 사용하려고 할 때 발생한다.

• 예를 들어, 자원 A를 가진 프로세스 P1과 자원 B를 가진 프로세스 P2가 있을 때, P1은 B를 필요로 하고 P2는 A를 필요로 한다면 두 프로세스는 서로 자원을 얻기 위해 무한정 기다리게 됩니다.

데드락의 발생의 4가지 조건

데드락은 주로 멀티 프로그래밍 환경에서 한정된 자원을 여러곳에서 사용하려 할 때 발생한다. 데드락이 발생하기 위해서는 아래 4가지 조건을 만족해야 한다.

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

• 순환 대기 (Circular wait) : 프로세스의 집합에서 순환 형태로 자원을 대기(Wait)

• 점유 대기 (Hold & Wait) : 공유 자원에 대한 접근 권한을 가진 채(Lock)로 다른 프로세스에 할당되어 사용되고 있는 자원을 점유하기 위해 대기(Wait) 하는 프로세스가 존재하는 경우

• 상호 배제(Mutual Exclusion) : 한 번에 한 프로세스만 공유 자원에 접근 가능하며, 접근 권한이 제한적일 경우.

데드락의 해결방법

• 예방 : 데드락 발생조건 중 하나를 제거하면서 해결하는 방법 즉, 비선점, 순환대기, 점유대기, 상호배제 중 하나를 제거한다.

• 회피 : 데드락이 발생할 시기를 피해가는 방법. 대표적으로 은행원 알고리즘을 사용하는 방법이 있다.

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

• 무시 : 데드락 발생을 무시하고 지나가는 방법.

은행원 알고리즘

데드락을 해결하기 위한 방법중 "회피"에 해당하는 방법이다.
데드락에 빠질 수 없는 상태를 안전상태라고 했을 때 안전 상태인 경우에만 요청을 수락하여 자원을 할당하고 안전상태가 아닌 요청들에 대해서는 안전상태가 될 때까지 계속해서 요청을 거절하며 데드락을 회피하는 알고리즘 이다.