데드락(DeadLock)

(데드락 회피에 자원할당 그래프, 데드락 무시 추가해야함)

데드락이란

운영체제에서 데드락(교착상태)이란, 시스템 자원에 대한 요구가 뒤엉킨 상태입니다.

즉, 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황을 일컫습니다.

 

데드락의 발생조건

발생 조건 4개를 모두 충족해야 데드락이 발생한다.

 

1. 상호배제

한 번에 프로세스 하나만 해당 자원을 사용할 수 있다 사용 중인 자원은 다른 프로세스가 사용하려면 요청한 자원이 해제될 때 까지 기다려야한다.

임계 구역을 두 개 이상의 프로세스가 동시에 접근하지 못 하도록 하는 과정에서 발생

 

임계 구역이란

다중 프로그래밍 기법에서 두 개 이상의 프로세스가 운영될 때 서로 공유하게 되는 자원

 

2. 점유대기

자원을 최소한 하나 보유하고 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야한다.

즉 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있기 때문에 원형 형태의 교착상태처럼 서로 물고 물리는 상황이 발생한다.

 

3. 비 선점

이미 할당된 자원을 강제로 빼앗을 수 없다.

 

4. 순환대기

대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.

ex. 프로세스의 집합 {P0, P1, ,…Pn}에서 P0는 P1이 점유한 자원을 대기하고 P1은 P2가 점유한 자원을 대기하고 P2…Pn-1은 Pn이 점유한 자원을 대기하며 Pn은 P0가 점유한 자원을 요구해야 한다.

 

교착상태(데드락) 해결법

1. 교착상태(데드락) 이 발생하지 않도록 예방 (예방)

2. 교착상태(데드락) 발생 가능성을 인정하면서도 적절하게 회피 (회피)

3. 교착상태(데드락) 발생을 허용하지만 교착상태를 탐지하여 교착상태에서 회복하기 (회복)

 

1. 교착상태(데드락) 예방

예방하는 방법은 시스템의 처리량이나 효율성을 떨어트리는 단점이 있다.

 

1) 상호배제 부정

한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 합니다.

그러나 추후 동기화 관련 문제가 발생할 수 있습니다. 즉 신뢰성 보장이 불가능합니다.

 

2) 비선점 부정

언제든 실행 중인 프로세스나 공유자원을 중단하거나 빼앗을 수 있게 한다.

교착 상태 예방 방법으로 가장 현실적이고 실현 가능한 방식이다.

 

3) 점유 대기 부정

각 프로세스는 한 번에 자신에게 필요한 모든 자원을 요구해야하며 이 요구가 만족되지 않으면 작업을 진행할 수 없다.

즉 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류해서, 나중에 또다른 자원을 점유하기 위한 대기 조건을 성립하지 않도록 합니다.

 

그리고 모든 프로세스에 각 자원 유형별로 할당 순서를 부여한다. 즉 만일 한 프로세스가 주어진 유형의 자원을 할당받았으면 그 프로세스는 순서에 따라 나중에 위치하는 유형의 자원만을 요구할 수 있게 한다.

 

4) 순환 대기 부정

자원을 순환 형태로 대기하지 않도록 일정한 한 쪽 방향으로만 자원을 요구할 수 있도록 합니다.

즉 순환 대기 상태를 선형 대기 상태로 변경한다.

 

2. 교착상태 (데드락) 회피

회피 법은 예방법보다는 조금 덜 제한적인 방법으로 예방법의 단점을 일부 해결할 수 있다.

request를 받아 들이기 전에 미래에 데드락이 일어날 확률을 계산해보고 "기다려" 하기

 

안정상태(safe state)

시스템의 프로세스들이 요청하는 모든 자원을, 데드락을 발생시키지 않으면서도 차례로 모두에게 할당해 줄 수 있는 상태

 

불안정 상태

즉, 데드락 발생 가능성이 있는 상황이며, 교착 상태(데드락)는 불안정 상태일 때 발생할 수 있다.

안전 순서

특정한 순서로 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 데드락이 발생하지 않는 순서

 

프로세스가 자원을 요구할 때 시스템이 안전 상태를 유지할 수 있는 프로세스의 자원 요구만 할당하여 주는 방안으로 자원 분배를 교착상태가 발생하지 않는 범위내에서 하는 방안

 

교착상태 회피 방안으로 사용하는 알고리즘에는 다익스트라가 제안한 기법인 은행원 알고리즘이 대표적이다.

 

은행원 알고리즘

최소한 고객 한명에게 대출해줄 금액은 항상 은행이 보유하고 있어야한다

즉 최소한 프로세스 하나에게 할당할 자원은 항상 보유해야한다.

즉 은행원 알고리즘에서는 운영체제는 안전상태를 유지할 수 있는 요구만 수락하고 불안전 상태를 초래할 사용자의 요구는 나중에 만족될 수 있을 때까지 계속 거절합니다.

 

은행원 알고리즘이 제대로 수행되기 위해서는 3가지를 알아야한다.

각 프로세스가 자원을 얼마나 요청할 수 있는지

각 프로세스가 자원을 얼마나 요청할 수 있는지

시스템이 얼마나 자원을 보유하고 있는지

 

은행원 알고리즘의 단점

이 방법을 적용하기 위해서는 자원의 양이 일정해야한다.

이 방법을 적용하기 위해서는 사용자의 수가 일정해야한다.

모든 요구를 유한시간안에 할당하는 것을 보장해야한다. 즉 프로세스는 유한한 시간 안에 자원을 반납해야한다.

최대 자원 요구량을 미리 알아야한다.

항상 불안전상태를 방지해야하므로 자원 이용도가 낮다.

응답시간의 예측이 필요한 대화식 프로그램에는 적용이 불가능하다.

 

자원 할당 그래프 알고리즘

자원 유형마다 인스턴스가 하나 있는 경우 자원 할당 그래프 알고리즘을 사용하여 교착상태를 회피할 수 있다.
방법

• 자원 할당 그래프에 예약 간선을 추가합니다.
  • 예약 간선(claim edge) : 향후 요청할 수 있는 자원을 가리키는 점선으로 표시된 간선
• 프로세스 시작 전에 모든 예약 간선들을 자원할당 그래프에 표시합니다.
• 프로세스는 예약 간선으로 설정한 자원에 대해서만 요청할 수 있고 주기가 형성되지 않을 때에만 자원을 할당 받습니다.

3. 교착상태(데드락) 탐지 및 회복

먼저 시스템이 데드락 예방이나 회피법을 사용하지 않았을 때, 데드락이 발생할 수 있으니 여기에서 회복하기 위해 데드락을 탐지하고, 회복하는 알고리즘을 사용한다.

 

데드락 탐지

Allocation, Request, Available등으로 시스템에 데드락이 발생했는지 여부를 탐색

즉 은행원 알고리즘에서 했던 방식과 유사하게 현재 시스템의 자원 할당상태를 가지고 파악

이 외에도 자원 할당 그래프, 인접행렬을 통해 탐지 가능

 

데드락 회복

교착 상태를 회복하기 위해서 4 가지 방법이 있다.

 

1. 프로세스 1개 중단

교착상태가 발생한 프로세스 중에 중단할 하나를 정해서 그 프로세스를 중단하고 자원을 빼앗는 방법

 

프로세스 선정기준

1) 우선순위가 낮은 프로세스

2) 처리된 진행상태가 적은 프로세스

3) 자원을 적게 사용하고 있는 프로세스 선택 제거

4) 기아 상태나 문제가 있는 프로세스를 선택하여 제거

5) 정상 수행이 불가능한 모든 프로세스를 제거하고 다시 시작

 

2. 교착상태에 빠진 모든 프로세스 중단

계속 연산중이던 프로세스들도 모두 일시에 중단되어 부분 결과가 폐기될 수 있는 부작용이 발생할 수 있음

 

3. 프로세스 하나씩 중단 시킬 때 마다 탐지 알고리즘으로 데드락을 탐지하면서 회복

매번 탐지 알고리즘을 호출 및 수행해야 하므로 부담이 되는 작업일 수 있음

 

4. 자원 선점

프로세스에 할당된 자원을 선점해서, 교착 상태를 해결할 때까지 그 자원을 다른 프로세스에 할당해 주는 방법

 

 

4. 교착상태 무시(Ignore)

교착 상태를 해결할 때에도 문맥교환에 의한 오버헤드로 성능저하가 생긴다. 따라서 교착 상태가 정말 드물게 발생하는 경우(1년에 한번) 교착 상태 예방 또는 탐지와 관련된 지속된 오버헤드 및 성능 저하를 발생 시키는 것보다 교착 상태가 발생하도록 하고 필요에 따라 재부팅하는 것이 더 나을 수 있다.
(Unix 및 window를 포함한 대부분의 운영체제가 사용하는 방법)

 

참고

 https://yoongrammer.tistory.com/67 

https://frontalnh.github.io/2018/04/05/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EA%B5%90%EC%B0%A9%EC%83%81%ED%83%9C-deadlock-%EB%9E%80-%EB%AC%B4%EC%97%87%EC%9D%B8%EA%B0%80/