교착 상태(Dead Lock) 발생의 필수조건과, 교착 상태 해결방안

교착 상태(Dead Lock) 발생의 필수조건과, 교착 상태 해결방안

---

1. 다른 프로세스의 작업 완료 무한 대기, 교착 상태의 개요

개념	- 두 개 이상의 프로세스가 다른 프로세스의 작업 완료를 기다리면서 더 이상 작업을 진행하지 못하는 상태

-   컴퓨터 시스템에서 교착 상태는 시스템 자원, 공유 변수(또는 파일), 응용 프로그램 등을 사용할 때 발생

---

2. 교착 상태 발생의 필수조건

가. 교착 상태 발생 자원 할당 그래프

교착 상태 발생 자원 할당 그래프	자원 할당 그래프 설명
	- 자원을 공유하지 못하면 교착 상태 발생 - 자원을 빼앗을 수 없으면 자원을 놓을 때까지 기다려야 하므로 교착 상태 발생 - 자원 하나를 잡은 상태에서 다른 자원을 기다리면 교착 상태 발생 - 자원을 요구하는 방향이 원을 이루면 양보를 하지 않기 때문에 교착 상태 발생

- 프로세스 P1~P4는 왼쪽의 자원을 점유하고 오른쪽의 자원을 기다리는 상황으로 교착 상태 발생.

 

나. 교착 상태 발생의 필수조건 설명

필수조건	설명
상호 배제 (mutual exclusion)	- 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 하고, 배타적인 자원은 임계구역으로 보호되기 때문에 다른 프로세스가 동시에 사용할 수 없어 배타적인 자원 사용시 교착 상태 발생
비선점 (non-preemption)	- 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 하고 자원을 빼앗을 수 없으면 공유할 수 없으므로 교착 상태 발생
점유와 대기 (hold and wait)	- 다른 프로세스가 필요로 하는 자원을 점유하고 있으면서 또 다른 자원을 기다리는 상태가 되면 교착 상태 발생
원형 대기 (circular wait)	- 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어지면 프로세스 들이 서로 양보하지 않기 때문에 교착 상태 발생

- 교착 상태는 상호 배제, 비선점, 점유와 대기, 원형 대기를 모두 충족해야 발생

 

3. 교착 상태 해결방안

가. 교착 상태 해결방안

개념	교착 상태 예방	- 교착 상태를 유발하는 네 가지 조건 무력화
	교착 상태 회피	- 교착 상태가 발생하지 않는 수준으로 자원 할당
	교착 상태 검출	- 자원 할당 그래프를 사용하여 교착 상태 발견
	교착 상태 회복	- 교착 상태를 검출 후 해결

- 교착 상태 예방 기법은 사실상 무력화가 불가능

 

나. 교착 상태 해결을 위한 주요 기법

해결방안	주요기법	설명
예방	상호 배제 예방	- 시스템 내 상호 배타적은 모든 자원, 즉 독점적으로 사용할 수 있는 자원을 없애는 방법
	비선점 예방	- 모든 자원을 빼앗을 수 있도록 만드는 방법 - 우선순위가 낮은 프로세스는 아사 현상 발생 가능
	점유와 대기 예방	- 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법
	원형 대기 예방	- 점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법
회피	Banker’s 알고리즘	- 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당하는 알고리즘
	Safety 알고리즘	- 안정 순열이 존재하는지 판별하는 알고리즘
검출	타임아웃	- 일정 시가 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법
	자원 할당 그래프	- 자원 할당 그래프를 통해 시스템 내 프로세스가 어떤 자원을 사용하고 있는지, 기다리고 있는지 확인하여 검출
회복	프로세스 종료	- 한 개 이상의 프로세스를 중지시켜 교착상태를 회복
	자원 선점	- 프로세스 들로부터 자원을 빼앗아서 교착상태가 해결될 때까지 다른 프로세스들에게 할당

- 하나의 자원을 여러 개의 프로세스가 동시에 사용할 수 있는 경우에는 교착 상태 검출이 복잡