교착 상태

교착 상태

식사하는 철학자 문제

일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상을 교착 상태deadlock라고 한다.

자원 할당 그래프

프로세스는 원으로, 자원은 사각형으로 표현한다. 사용할 수 있는 자원의 개수는 사각형 내의 점으로 표현한다. 프로세스가 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시한다. 프로세스가 자원의 할당순서 대기 중이라면 프로세스에서 자원을 향해 화살표를 표시한다.

자원 할당 그래프의 예

교착 상태를 나타내는 자원 할당 그래프

교착 상태 발생 조건

상호 배제mutual exclusion

한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태

점유와 대기hold and wait

자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태

비선점nonpreemptive

어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태

원형 대기circular wait

자원 할당 그래프가 원형으로 그려지는 상태

교착 상태 해결 방법

예방, 회피, 검출, 회복

교착 상태 예방

자원의 상호 배제 제거

모든 자원을 공유 가능하게 한다-현실적으로 불가능

점유와 대기 제거

자원의 효율 저하, 많은 자원을 필요로 하는 프로세스에게 기아 현상 발생 우려

비선점 조건 제거

선점할 수 있는 일부 자원에 대해서는 효과적이나, 그러지 못한 자원들에 대해서는 의미가 없어 범용성이 떨어짐

원형 대기 조건 제거

자원에 번호를 붙이고, 오름차순으로 할당하면 예방 가능

교착 상태 회피

안전 상태-불안전 상태

안전 순서열

교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서

안전 상태

안전 순서열대로 프로세스들에 자원을 배분하여 교착 상태가 발생하지 않는 상태

불안전 상태

안전 순서열이 없는 상황, 교착 상태의 위험이 있다.