[운영체제] 데드락

1. 데드락

1.1. 데드락이란?

프로세스가 필요한 자원을 얻지 못해 멈춘 상태 
'교착 상태'라고도 부름 
한정된 자원을 여러 프로세스에서 접근하려고 할 때 발생함 

 

데드락

1.2. 데드락의 예시 

1. 위의 사진과 같이 각 프로세스가 자원을 점유한 채, 꼬리물기 식으로 자원을 요구하게 되면 무한정 wait 상태에 빠짐
2. 이러한 상황을 데드락이라고 함  

1.3. 데드락이 주로 발생하는 경우 

1. 멀티 프로그래밍 환경에서의 자원 경쟁 
2. 한 프로세스가 필요한 자원이 사용할 수 없는 상황이면 대기 상태에 들어가는데, 그 프로세스가 다시 돌아올 수 없으면 데드락 발생 

1.4. 철학자 문제 

1. 왼쪽 포크가 사용 가능해질 때까지 생각을 한다. 만약 사용 가능해지면 집어든다.
2. 오른쪽 포크가 사용 가능해질 때까지 생각을 한다. 만약 사용 가능해지면 집어든다.
3. 양쪽의 포크를 잡으면 정해진 시간만큼 식사를 한다.
4. 오른쪽 포크를 내려놓는다.
5. 왼쪽 포크를 내려놓는다.
6. 다시 1번으로 돌아간다.

만약 모든 철학자들이 동시에 자신의 왼쪽 포크를 잡는다면 모든 철학자들은 자기 오른쪽의 포크가 사용 가능해질 때까지 기다려야 하는데 이것을 교착 상태라고 한다

 

2. 데드락 발생 조건

2.1. 데드락 발생 조건? 

데드락이 발생할 수 있는 조건
4가지 모두 성립해야 발생하며, 한가지라도 해당되지 않으면 해결 가능하다.

 

2.2. 상호 배제 

1. 자원은 한번에 한 프로세스만 사용할 수 있음 

2.3. 점유 대기 

1. 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 있는 자원을 점유하기 위해 대기하는 프로세스가 존재해야 함

2.4. 비선점 

1. 다른 프로세스에 할당된 자원은 강제로 빼앗을 수 없음 

2.5. 순환 대기 

1. 프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함(위의 사진 처럼) 

 

3. 데드락 처리 

3.1. 예방 : 교착 상태 발생 조건 중 하나를 제거하며 해결, 자원 낭비가 심함 

1. 상호 배제 부정 : 여러 프로세스가 동시에 공유 자원을 사용하도록 한다.
2. 점유대기 부정 : 프로세스 실행전에 모든 자원을 한번에 할당함
3. 비선점 부정 : 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원을 반납하도록 함 
4. 순환대기 부정 : 자원에 고유 번호 할당 후 순서대로 자원을 요구하도록 함 

3.2. 회피 : 교착 상태 발생을 회피하는 방법 

1. 은행원 알고리즘 : 프로세스가 자원을 요구할 때, 시스템은 그 프로세스에게 해당 자원을 할당해도 안정 상태로 남아있는지 사전에 검사하는 방법, 만약 안정 상태면 자원을 할당하며, 아니면 다른 프로세스가 자원을 반납할때까지 대기함

3.3. 탐지 : 자원 할당 그래프를 통해 교착 상태 탐지 

1. 자원 요청 시, 탐지 알고리즘을 실행시켜야 하므로 오버헤드 발생

3.4. 회복 : 교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복하는 방법 

1. 프로세스 종료 : 교착 상태의 프로세스 모두 종료, 교착 상태가 제거될 때 까지 프로세스 하나씩 중지한다.
2. 자원 선점 방법 : 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당한다. (교착 상태의 프로세스는 일시 중지 상태로 전이한다) 

 

Reference

https://github.com/gyoogle/tech-interview-for-developer

gyoogle/tech-interview-for-developer

http://www.dt.co.kr/contents.html?article_no=2008022802011860739001

[알아봅시다] 철학자들의 만찬문제(The Dining-Philosophers Problem)