(9) 데드락 ( Dead lock)

1. 데드락이란?

1-1) 정의

프로세스가 자원을 얻지 못해서 다음을 처리하기 못하는 상태, 교착 상태
- 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생

 

1-2) 데드락의 원인

> 서로 원하는 자원

P1 : R1 소비 중, R2 원함

P2 : R2 소비중, R1 원함

→ 서로 원하는 자원을 가지고 있기 때문에 영원히 wait상태에 빠지는 것

 

 

2. 데드락 발생 조건

※ 주 발생 경우

1. 멀티프로세스 환경에서 한전된 자원을 얻기 위해 서로 경쟁하는 상황에서
2. 한 프로세스가 자원을 요청했을 때, 동시에 그 자원을 사용할 수 없는 경우 wait 상태로 전환
3. wait 상태의 프로세스들이 실행 상태로 변경될 수 없을 때 주로 발생

 

> 다음의 4가지 조건이 모두 성립해야 dead-lock 일어날 수 있음
   ( 필요조건 )

• 상호 배제( Mutual exclusion )
  자원은 한번에 한 프로세스만 사용할 수 있음 - 한 process에 할당 된 자원은 사용하는 동안 풀로 소유
• 점유 대기( Hold and Wait )
  최소한 하나의 자원을 점유하고 있으면서, 다른 프로세스에 할당되어 사용하고 있는 자원을
  추가로 점유하기 위해 Wait 하는 프로세스가 존재해야 함
• 비선점( Non-preemtion )
  다른 프로세스에 할당된 자원은 process termination 전 까지, 강제로 회수될 수 없음
• 순환대기( Circular Wait )
  프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함
  - 서로가 원하는 자원이 현재 서로의 메모리에서 사용중이어야 함

 

 

3. Dead-lock 의 처리

3-1) 예방

교착 상태 발생 조건 중 하나를 제거하면서 해결 ( 자원낭비가 심한 해결방식 ) 

• 상호 배제 부정 : 여러 프로세스가 공유 자원 사용
  IPC의 공유 메모리와 비슷한 개념?
  https://korshika.tistory.com/144?category=970462
• 점유대기 부정 : 프로세스 실행 전 모든 자원을 할당
• 비선점 부정 : 선점방식 사용 == 자원 점유중인 프로세스가 다른 자원을 요구할 때 가진 자원 반납
• 순환대기 부정 : 자원에 고유번호 할당 후 순서대로 자원 요구

 

3-2) 회피

교착 상태 발생하는지 검사 후 피해나가는 방식

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

• 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 것에서 착안
• 프로세스가 자원을 요구할 때, OS가 자원 할당 이후에도 안정한지 검사 후 교착상태 회피
• 안전상태시 자원 할당 else 다른 프로세스들이 자원 해지까지 대기

 

3-3) 탐지 & 회복

교착 상태가 되도록 허용한 다음 회복시키는 방법

( 자원 요구는 수용하고, 이후 매번 탐지 + 회복하는 방식 )

 

(a) 탐지

- 매 자원 요청 시 "탐지 알고리즘"이 동작하므로 그에 대한 오버헤드 발생

(b) 회복

- 교착상태를 일으킨 프로세스를 종료 / 할당 자원 해제 시켜 회복하는 방법

- 프로세스 종료 방법

• 교착상태의 프로세스를 모두 중지
• 교착상태가 제거될 때 까지 하나씩 프로세스 중지

- 자원 선점 방법

• 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당
  (해당 프로세스 일시정지 시킴)
• 우선 순위가 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원 선점

---

참조

https://gyoogle.dev/blog/computer-science/operating-system/DeadLock.html

데드락(DeadLock) | 👨🏻‍💻 Tech Interview

https://m.blog.naver.com/dong5053/220717510273

운영체제 - 교착상태, 기아상태, 은행가 알고리즘