교착 상태 (deadlock)

A 프로세스가 점유한 자원을 B 프로세스의 자원을 점유해야 실행 완료된다고 할 때 B 프로세스는 자원을 얻기 위해 무한정 대기 상태

 

 

 

 

 

 

자원 할당 그래프 (resource allocation graph)

 

 

자원을 할당 받았을 때

 

 

 

자원 할당 받기를 기다리는 경우

 

 

 

 

 

교착 상태 발생 조건 (모두 만족 시켜야 함)

 

1. 상호 배제

• 프로세스간 자원을 공유 할 수 없을때
• 비선점을 보장

 

 

2. 비선점

• 프로세스간 자원을 빼앗을 수 없을때

 

 

※ [임계영역]은 상호 배제 & 비선점 보장

 

 

 

3. 점유와 대기

• 프로세스가 다른 자원을 할당 받기를 대기하고 있는 상태

 

 

4. 원형 대기

•  프로세스가 서로 자원을 양보하지 않음

 

 

 

 

◎ 참고 : starvation & deadlock 차이

• starvation : 우선 순위가 낮은 프로세스들이 CPU를 할당 받지 못해 실행이 지연되는 문제
• deadlock : 교착상태에 빠진 프로세스들의 무한정 대기 상태

 

 

 

 

 

 

 

 

 

교착 상태 해결법

 

1. 교착 상태 예방(deadlock prevention)

•  교착 상태 발생 조건(상호 배제, 비선점, 점유와 대기, 원형 대기) 중에서 하나라도 발생되지 않도록 막기
• 상호 배제 막기 : 임계영역과 상호 배제 보장 불가 
• 비선점 막기 : starvation 발생
• 점유와 대기 막기 : 일괄 작업 방식으로 처리하게 됨
• 원형 대기 막기 : 자원을 한 방향으로 사용해야 함

 

2. 교착 상태 회피(deadlock avoidance)

• 시스템이 안정 상태이면 자원 할당 (available >= expect)
• 시스템이 불안정 상태이면 자원 할당 안함 (available < expect)
• banker's algorithm : 최대 자원 수 (max)를 요구한다는 경우를 가정 (자원 낭비 심함)

 

 

banker's algorithm 변수

 

 

 

 

 

3. 교착 상태 검출 및 복구(deadlock detection & recovery)

• 교착상태를 발생시킨 프로세스 강제종료하고 교착상태 발생 전으로 복구