[운영체제] 교착상태

독학사- 운영체제 편을 공부하고 정리한 내용입니다.

교착상태 deadlock

 

2개 이상의 프로세스가 서로 작업이 끝나기를 기다리는 상태로 더 이상 진행이 불가능한 상황을 교착상태라고 한다.

 

교착상태와 기아현상

• 기아현상: 다른 우선순위 프로세스가 완료되고 운영체제로부터 자원을 할당받을 때까지 기다리는 현상
• 교착상태: 여러 프로세스가 같이 자원을 사용하다 발생하는 더 이상 진행이 불가능한 상태가 되는 현상

- 교착상태 예시

교착상태

P1 프로세스는 프린터를 사용 중이면서 디스크에 대한 사용을 요청 중에 있다.

P2 프로세스는 디스크를 사용 중이면서 프린터에 대한 사용을 요청 중에 있다.

두 프로세스 중 한 프로세스가 자원을 반납하거나 사용 요청을 중지하지 않는 이상 더 이상 실행이 불가능하다. 

 

교착상태 필요조건

 

---- "자원에 대한 필요 조건"

1) 상호 배제 Exclusive use of resources

둘 이상의 프로세스가 한 자원을 동시에 사용할 수 없다.

• 프로세스, 메모리, 입출력 장치 등 자원은 한 프로세스만 사용 가능한 배타적인 자원이다.

2) 비선점 자원 Non-preemptible resources

사용되고 있는 자원은 선점되지 않는다.

 

 - 선점 자원과 비선점 자원

• 선점 자원: 선점을 당한 후 원래 프로세스에게 재할당될 때 문제가 되지않는 자원이다.
• ex) 메모리, 버퍼, 프로세서 등
• 비선점 자원: 선점을 당한 후 원래 프로세스에게 재할당될 때 문제가 되는 자원이다.
• ex) 프린터, 디스크 드라이브, 임계영역 등

---- "프로세스에 대한 필요 조건"

3) 점유와 대기 Hold and Wait

프로세스가 어떤 자원을 점유한 상태에서 다른 자원을 기다리는 상태여야 한다.

• 자원을 점유한 상태로 다른 프로세스가 점유 자원에 대한 사용을 방해한다.

4) 원형 대기 Circular Wait

점유와 대기를 하는 프로세스 간의 관계가 원(cycle)을 이루어야 한다.

 

※ 임계 영역과 교착상태

임계 영역에서 공유 자원에 대한 보호를 위해 잠금 기능이 있다면 공유 자원은 자동으로 둘 이상 프로세스에게 할당되지 않으며 (상호 배제) 선점되지 않는다. (비선점 조건)

따라서 임계 영역의 공유 자원을 사용하는 둘 이상의 프로세스가 점유와 대기, 원형 대기 관계를 만족한다면 교착상태가 발생한다.

 

교착상태 해결 방법

 

- 교착상태 예방 (Prevention)

필요조건	예방방법	문제점
상호 배제	모든 자원을 공유	모든 자원을 공유하는 것은 현실적으로 불가능
비선점	모든 자원 선점 가능	임계 영역에 대한 공유 자원 보호 문제 재할당시 문제가 되는 자원을 어떻게 처리할 것인가
점유와 대기	모든 자원을 한번에 할당	모든 자원을 할당하거나 하지않는 all or none 방식 사용하지 않는 자원에 대한 할당으로 자원 낭비 일괄 처리 방식으로 시스템 효율이 감소
원형 대기	자원에 순서를 부여	순서를 신중하게 부여해야함

 

- 교착상태 회피 (Avoidance)

• 프로세스마다 할당된 자원 상태를 감시하여 교착상태에 빠지는 상황을 피한다.

은행원 알고리즘

다익스트라가 제안한 교착상태를 회피하는 알고리즘으로 다음 상황을 가정한다.

• 프로세스 수가 고정
• 자원의 종류와 수가 고정
• 프로세스마다 요구하는 자원 종류 및 최대 자원의 수를 알고 있음
• 프로세스는 자원 사용 후 반드시 반납

은행원 알고리즘은 위 상황에서 교착상태에 빠지지 않는 안전한 프로세스 자원 할당 순서를 찾는 것이다.

 

- 예시

총 자원 수 = 11, 가용 자원 수 = 4
프로세스	요구되는 최대 자원 수	현재 할당된 자원 수	필요 자원 수
P1	5	2	3
P2	9	3	6
P3	6	1	5

P1 -> P3 -> P2 순서대로 자원을 할당하면 교착상태 없이 모든 프로세스를 완료할 수 있다.

 

실제 시스템은 프로세스 수와 자원의 수가 고정돼있지 않으며 프로세스마다 요구하는 자원 정보를 알고 있어야 한다.

 

- 교착상태 검출 (Detection)

• 타임아웃을 이용: 일정 시간 동안 작업이 진행되지 않으면 강제 종료한다.
• 자원 할당 그래프를 이용: 프로세스와 자원 간의 할당 및 요구에 대한 그래프를 그리고 사이클이 있는지 검사한다.

- 교착상태 회복 (Recovery)

• 특정 프로세스를 중단하거나 자원을 선점시킴으로 교착 상태로부터 벗어날 수 있다.