[바미] Deadlock의 해결방안

안녕하세요. 오늘은 Deadlock을 어떻게 해결해야 하는지에 대해 알아보도록 하겠습니다.

 

일단 Deadlock이 무엇인지, 어떤 원인으로 발생하는지는 아래의 글을 참고 하시면 더 좋을 것 같습니다.

[바미] Go - DeadLock & channel에 대해 알아보자.

교착상태를 간단하게 말해보자면 프로세스들의 집합이 더 이상 진행을 못하고 영구적으로 블록(대기)되어 있는 상태를 얘기합니다.

 

교착상태가 발생하는 조건

교착상태가 발생하기 위해서는 우선 세 가지 조건이 기본적으로 필요합니다.

1. 상호 배제 조건 : 한 순간에 한 프로세스만이 자원을 사용할 수 있다. 즉 한 프로세스에 의해 점유된 자원을 다른 프로세스들이 접근할 수는 없다.
2. 점유대기 조건 : 이미 자원을 보유한 프로세스가 다른 자원을 요청하며 기다리고 있다.
3. 비선점 조건 : 프로세스에 의해 점유된 자원을 다른 프로세스가 강제적으로 빼앗을 수 없다.

위 세 가지가 만족되면 교착상태가 발생할 수 있는 조건을 갖추게 된 것입니다.

이러한 상황에서 환형 대기 조건을 갖춘다면 교착상태가 발생하게 됩니다.

 

환형 대기

아래 그림과 같이 프로세스는 진행하기 위해 어떤 자원을 필요로 하지만 그 자원은 다른 프로세스에 의해 사용 중이며 반환되지 않는 상태가 환형으로 이루어진 상태입니다. (아래와 같은 그래프를 자원 할당 그래프라고 합니다.)

프로그램에서 교착상태가 발생하는 것은 매우 치명적입니다.

교착상태를 해결하기 위한 몇몇 방법들이 고안되었는데 교착상태의 예방, 회피, 발견이 각각 그 방법들입니다.

이어서 세 가지 방법에 대해 간단하게 알아보도록 하겠습니다.

교착상태 예방

교착상태 예방은 교착상태가 발생할 가능성을 없애는 것인데 위에서 교착 상태가 발생하는 조건들인 상호 배제,

점유 대기, 비선점, 환형 대기의 네 가지 조건중 한 가지를 허용하지 않는 것이 교착상태 예방의 방법입니다.

 

이를 위해서는 다음과 같은 가정이 필요한데

• 프로세스 수가 고정되어 있어야 한다.
• 자원의 종류와 수가 고정되어 있어야 한다.
• 프로세스가 요구하는 자원 및 최대 자원의 수를 알아야 한다.
• 프로세스는 반드시 자원을 사용 후 반납해야 한다.

하지만 현실적으로 상호 배제와 점유대기 조건을 배제하는 것은 좋지 않은 선택입니다. 또한, 자원 요청이 있을 때마다 알고리즘을 사용한다는 것은 상당한 overhead죠.

unsafe state라서 반드시 deadlock이 발생하지는 않음.

 

비선점 조건은 프로세스가 요구한 자원을 보유하고 있는 프로세스가 자원을 반납하도록 할 수 있을 것이며,

환형 대기 조건은 자원 할당에 순서를 부여 함으로써 조건을 배제할 수 있을 것입니다.

교착상태 회피

교착상태 회피는 상호 배제 ,점유대기, 비선점 조건을 허용합니다. 또한 자원 할당 순서를 미리 정하지도 않습니다.

단지 자원이 할당되었을 때 교착상태가 발생할 수 있는지를 미리 검사해서 교착상태가 발생 가능하다면 자원 할당을 거부합니다.

 

이 방법은 자원의 가용 개수와 프로세스의 자원 요구량을 미리 알고 있어야 합니다.

 

교착상태 회피에는 2가지 기법이 있습니다.

1. 프로세스 시작 거부 : 프로세스가 시작하려 할 때 요구하는 자원 할당이 교착상태 발생의 가능성이 있으면, 프로세스를 시작시키지 않는다.
2. 자원 할당 거부 : 수행 중인 프로세스가 요구하는 추가적인 자원 할당이 교착상태 발생의 가능성이 있으면, 자원을 할당하지 않는다. 자원 할당 거부 방법은 Banker's algorithm 이라고도 불린다.
   • 뱅커 알고리즘에 대해 자세히 알기

교착상태 발견

먼저 자원을 새로 할당할 때마다 가용 자원가 할당 자원의 수를 갱신해가며 교착 상태를 발견할 수 있습니다.

이 방식은 지속적으로 확인하는 작업이 필요하기 때문에 성능 저하가 발생하게 되죠.

• 탐지 알고리즘

1. 대기 그래프(wait-for graph)

주기적으로 대기 그래프에 주기가 있는지 탐지 알고리즘을 호출하여 deadlock을 탐지합니다.

대기 그래프에 cycle이 있다면 deadlock을 의미하는데 대기 그래프에서 Pi→Pj는 프로세스 Pi가 Pj프로세스가 보유하고 있는 자원을 기다리고 있음을 나타냅니다.

 

각 자원 유형마다 instance가 하나 있는 경우 자원 할당 그래프를 변형한 대기 그래프를 사용하여 deadlock을 탐지합니다.

2. 은행원 알고리즘(Banker’s Algorithm)

각 자원 유형마다 instance가 여러 개 있는 경우 은행원 알고리즘을 사용하여 deadlock을 탐지한다. deadlock avoidance에서 사용하는 알고리즘과는 차이가 있습니다.

• 각 프로세스의 자원 요청 개수를 사용한다.
• 현재 상태가 safe state인지 확인한다.
• unsafe state라면 deadlock이라고 판단한다.

 

첫 번째로 3만원 더 필요한 첫번째 고객에게 3만원을 빌려주고 첫번째 고객이 일을 해결하고 갚을 때까지 기다렸다가 다른 고객에게 돈을 빌려주는 방법이 있고, 두 번째 고객에게 남은 4만원을 빌려주고 두번째 고객이 일을 해결하고 갚을 때까지 기다리는 방법이 있습니다만, 하지만 세번째 고객에게는 통하지 않습니다.

은행은 4만원이 남아있는데, 세번째 고객은 5만원이 더 필요하기 때문이죠. 돈을 빌려줄 수 있고, 다시 돈을 돌려 받을 수 있는 상태를 safe state라고 합니다.

1. 고객1 - 고객2 - 고객3
2. 고객2 - 고객1 - 고객3
3. 고객2 - 고객3 - 고객1

이런 순서대로 모든 고객에게 돈을 빌려줄 수 있고 이를 safe state가 존재한다고 합니다.

근데, 만약에 60원이 필요한 고객3이 너무 급하다고 25원 말고 45원을 달라고 했다고 가정했을 때

은행에 남는 돈은 5원 밖에 없게 되는데 이 상황에서는 세 고객 중 아무도 해결해 줄 수 없게 됩니다.

이 상태를 unsafe state, deadlock이라고 하죠.

• 탐지 알고리즘 호출 주기 오버헤드가 있기 때문에 얼마나 자주 deadlock이 발생하는지 얼마나 많은 프로세스가 deadlock에 연루되어 있는지에 따라 호출 빈도를 조절해야 한다.
  • 자원을 요청했는데도 즉시 할당되지 못하는 시점에 호출.
  • 주기적으로 일정 시간마다 호출.
  • cpu 이용률이 특정 값 이하로 떨어지는 시점에서 호출.

4. 교착상태 회복

deadlock에 있는 프로세스를 종료하는 방식이다. 종료에는 2가지 방식이있습니다.

1. deadlock의 프로세스를 모두 중지.
2. deadlock이 제거 될 때까지 한 프로세스씩 중지.

참조

운영체제 교착상태에 대해

Deadlock관련 알고리즘

 

뱅커알고리즘