탑스팟 컴퓨터일반 30. 교착상태

* 교착상태(Dead Lock)

- 상호 배제에 의해 나타나는 문제점으로, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상

 

* 교착상태 발생의 필요 충분 조건

- 교착상태가 발생하기 위해서는 다음의 네 가지 조건이 충족되어야 하는데, 이 네 가지 조건 중 하나라도 충족되지 않으면 교착상태가 발생하지 않음

조건	설명
상호 배제 (Mutual Exclusion)	한 번에 한 개의 프로세스만이 공유 자원을 사용할 수 있어야 함
점유와 대기 (Hold and Wait)	최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 함
비선점 (Non-preemption)	다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 함
환형 대기 = 순환 대기 (Circular Wait)	공유 자원과 공유 자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야 함

 

* 교착상태의 해결 방법

기법	설명
예방 기법 (Prevention)	- 교착상태가 발생하지 않도록 사전에 시스템을 제어하는 방법 - 교착상태 발생의 네 가지 조건 중에서 어느 하나를 제거함으로써 수행됨 - 자원의 낭비가 가장 심한 기법임
회피 기법 (Avoidance)	- 교착상태가 발생할 가능성을 배제하지 않고 교착상태가 발생하면 적절히 피해나가는 방법 - 주로 은행원 알고리즘(Banker's Algorithm)이 사용됨 - 은행원 알고리즘(Banker's Algorithm) : E. J. Dijkstra가 제안한 것으로, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 데서 유래한 기법
발견 기법 (Detection)	- 시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견하는 것 - 교착상태 발견 알고리즘과 자원 할당 그래프 등을 사용할 수 있음
회복 기법 (Recovery)	- 교착상태를 일으킨 프로세스를 종료하거나 교착상태의 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복하는 것

 

* 은행원 알고리즘 (Banker's Algorithm)

- 최대 자원요구 수를 미리 알아야 다음 시스템의 상태를 예측할 수 있기 때문에 은행가 알고리즘은 이론상 가능하다

- '최소한 고객 한 명에게 대출해줄 금액은 항상 은행이 보유하고 있어야 한다' 는 개념에서 출발

 

* 은행원 알고리즘이 제대로 수행되기 위한 3가지

- 각 고객들이 얼마나 맥시멈으로 돈을 요구할지 (Max)

- 각 고객들이 현재 빌린 돈은 얼마인지 (Allocated)

- 은행이 보유한 돈이 얼마인지, 빌려줄 수 있는 돈이 얼마인지 (Available)

 

* 은행원 알고리즘 - 프로세스 예시

	Maximum Needs	Current Needs
P0	10	5
P1	4	2
P2	9	2

프로세스 P0, P1, P2가 있고, 운영체제는 12개의 자기 테이프 드라이브를 공유자원으로 가지고 있다. 프로세스 P0을 수행하는 데 10개의 테이프 드라이브 사용이 필요하고, P1은 4개, P2는 9개가 요구된다.

 

현재 시점 t0

P0이 5개 P1과 P2는 2개의 테이프 드라이브 사용중 / 사용가능한 드라이브 : 3개

→ 안정상태

 

다음 시점 t1

if : P2가 자원 하나를 더 요청하여 3개를 사용 중이라면..

사용 가능한 드라이브 : 2개

P0 : 5개 필요 → 불가

P1 : 2개 필요 → But, P1이 반환되어도 총 남는 테이프는 4개라서 P0나 P2 해결 불가

→ 불안정 상태

 

https://youtu.be/Z5t90U2SwG8