데드락(Dead Lock).md

데드락 (Dead Lock)

운영체제 속 데드락이란 시스템 자원에 대한 요구가 뒤엉킨 상태로, 둘 이상의 프로세스가 다른 프로세스가 소유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황이다.

발생 조건

• 상호 배제
  • 한 번에 프로세스 하나만 해당 자원을 사용할 수 있다.
• 점유 대기
  • 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.
• 비선점
  • 이미 소유한 자원을 강제로 빼앗을 수 없다.
• 순환 대기
  • 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.

해결방법

• 예방 (Prevention)
• 회피 (Avoidance)
• 탐지 & 회복 (Detection & Recovery)

예방 (Prevention)

발생 조건 4가지 중 하나라도 발생하지 않게 하는 것이 핵심이다.

• 상호 배제 방지 : 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다. -> 동기화 문제 발생할 수 있음
• 점유 대기 방지 : 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류한다. -> 자원 점유을 위한 대기 차단
• 비선점 방지 : 이미 할당된 자원이 선점권이 없다고 가정할 때, 높은 우선순위의 프로세스가 해당 자원을 선점하도록 한다. -> 뺏어오기 가능
• 순환 대기 방지 : 자원이 순환 형태로 대기하지 않도록 자원에 고유한 번호를 부여하고, 번호 순서대로 자원을 요구하도록 한다.
  

단점

• 시스템의 처리량이나 효율성이 떨어진다.
  
• 가장 제한적인 방법이다.

회피 (Avoidance)

• 안정 상태 (Safe State) : 프로세스들이 요청하는 모든 자원을 데드락 없이 차례로 모두 할당해 주는 경우
• 안전 순서 (Safe Sequence) : 데드락 없이 모든 자원을 할당해 주었을 때의 순서를 의미

즉, 불안정 상태일 때 데드락이 발생할 수 있는 상황이고, 회피는 자원 할당 후에도 시스템이 항상 안정 상태에 있도록 할당을 허용하는 것이다.

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

어떤 자원의 할당을 허용하는지에 대한 여부를 결정하기 전에, 미리 결정된 모든 자원들의 최대 가능한 할당량을 가지고 시물레이션해서 안정상태일 수 있는지 검사한다. 즉, 데드락의 발생 가능성을 미리 조사하는 것이다.

처음 시스템이 총 12개의 자원이 있다고 가정해보자.

(t = t0)	Max	Allocation	Need	Available
P0	10	5	5
P1	4	2	2
P2	9	2	7

P0~P2는 프로세스, Max는 각 프로세스의 최대 자원 요청량, Allocation은 현재 할당중인 자원의 양, Need는 남은 필요한 자원의 양이다.
현재 t0일 때 프로세스에 할당된 자원의 합은 5 + 2 + 2 = 9개이다. 따라서 사용가능한 남은 자원은 3개이다.
안전 순서를 찾아보자.

• P1은 2개를 추가로 할당받길 기다리고 있다. 남은 자원 수는 3개이므로 이중 2개를 P1에게 할당해준다. -> 사용 가능 자원 3 - 2 =1개.
• 실행이 끝난 P1은 자신에게 할당된 자원 4개를 반납한다. -> 사용 가능 자원 1 + 4 = 5개
• 모두 P0에게 할당해주면 P0도 실행 가능해진다. -> 사용 가능 자원 5 - 5 = 0개
• 실행이 끝난 P0은 자신에게 할당된 자원 10개를 모두 반납한다. -> 사용 가능 자원 0 + 10 = 10개
• 마지막으로 P2에게 자원 7개를 할당한다. -> 사용 가능 자원 10 - 7 = 3개
• 실행이 끝난 P2는 자신에게 할당된 자원 9개를 모두 반납한다. -> 사용 가능 자원 3 + 9 = 12개

따라서 안전 순서는 <P1, P0, P2>가 된다.

만약 P2가 처음 자원을 2개가 아닌 3개를 할당 받았다면 사용가능 자원은 2개 였을 것이다. 이 상황에서 P1에게 2개를 모두 할당하고, 끝난 뒤 반납해도 사용 가능 자원은 4개이므로 P0이나 P2을 해결할 수 없다.

단점

미리 최대 자원 요구량을 알아야 하고, 할당할 수 있는 자원 수가 일정해야하는 제약 조건이 존재한다.

탐지(Detection) & 회복 (Recovery)

• 탐지 기법

  • Allocation, Request, Available 등으로 데드락의 발생 여부 탐지 -> 은행원 알고리즘과 유사하게 자원 할당 상태로 파악
  • 자원 할당 그래프 이용
    

• 회복 기법 : 데드락을 탐지했다면, 순환 대기에서 벗어나는 회복 방법 사용

  • 프로세스 1개 이상 중단시키기
    • 데드락 상태의 모든 프로세스 중단 : 중간 단계 결과가 폐기되는 단점
    • 프로세스를 하나씩 중단하며 데드락 탐지 & 회복 : 매번 탐지해야 하므로 오버헤드가 큰 단점
  • 자원 선점하기
    • 프로세스에 할당된 자원을 선점하고 교착 상태를 해결할 때까지 그 자원을 다른 프로세스에 할당

---

Reference

• https://chanhuiseok.github.io/posts/cs-2/
• https://jwprogramming.tistory.com/12
• https://kukuta.tistory.com/281