DeadLock

Deadlock

프로세스 또는 쓰레드는 운영체제(또는 다른 관리자)가 관리하는 자원(메모리, 파일, 디바이스 등등)을 사용하는데, 다중 프로세스/쓰레드 프로그래밍을 하면 이 자원을 공유하게 되는 일이 자주 발생한다. 각 쓰레드 또는 프로세스는 각기 독립적인 실행 흐름을 가지고 있기 때문에 자원에 동시 접근하는 경우가 발생할 수 있다. 공유자원이 비일관적으로 사용되는 것을 막기 위해서 자원의 관리자는 자원의 배타적 소유권을 유지하는 방법을 사용한다. Lock을 걸어서 여러 스레드가 동시에 공유자원을 사용하는 것을 막는 것이다. 그런데 관리자가 Lock을 잘못 사용하는 경우 어느 쓰레드도 자원을 영원히 사용할 수 없는 상태, 즉 Deadlock(교착상태)에 빠질 수 있다.

Deadlock이 발생하는 이유

위 그림의 상황은 Deadlock이 발생하는 경우를 매우 간략화시킨 그림이다. 여러개의 자원을 서로 다른 쓰레드가 동시에 원하는 상황이다. Thread 1과 Thread2가 작업을 진행하기 위해서는 Resource 1과 2가 동시에 필요하다. 그런데 작업을 진행하다보니 Thread1은 Resouce1을 얻었고 Thread2는 Resource2를 얻었다. 그리고 각각 남은 자원을 얻기 위해 대기 중이다. 이 대기는 누군가 하나 양보하지 않는 이상 영원히 풀리지 않는다. 하지만 어떻게 양보시킬 것인가? 방법이 없다면 프로그램을 껏다 다시 키는 수 밖에없다.

DeadLock의 발생 조건

우리가 짜는 대다수의 코드에서 복수개의 자원을 사용한다. 이대로 멀티 쓰레드 프로그램을 하면 우린 계속 Deadlock의 공포에서 벗어날 수가 없다. 우선 적을 분명히 이해해야한다. DeadLock이 발생하는 명확한 조건을 알아보자.

• 상호 배제 : 자원이 배타적으로 공유된다. 한번에 하나의 프로세스(또는 쓰레드)만이 특정 자원을 사용할 수 있다.
• 보유 후 대기 : 자원을 점유한 상태에서 또 다른 자원을 얻기위해서 대기상태에 빠질 수 있다.
• 비 선점 : 자원의 반환은 자원을 가진 프로세스(쓰레드)가 반납하지 않으면 선점(뺏어오는것)할 수 없다.
• 순환 대기 : 여러개의 프로세스 사이에서 점유-대기 상황이 순환적으로 형성된다.

DeadLock의 예방

가장 쉬운 방법은 위의 조건이 발생하지 않도록 미리 예방하는 것이다. Deadlock은 위 4가지 조건이 모두 충족한 상태가 아니면 발생하지 않는다. 그렇다면, 자원을 요청하는 방법에 제약을 걸어서 미리 예방하는 방법이 있다.

• 상호 배제 예방 : 상호 배제를 하지 않도록 하면, 공유 자원의 일관성을 해칠 수 있다. 가능하면 피하자.
• 보유 후 대기 예방 : 프로세스가 반드시 필요한 모든 자원을 한꺼번에 받도록 유도한다. 그 중 하나라도 받을 수 없다면 다 반환시켜 버린다.
• 비 선점 예방 : 그냥 자원을 뺏을 수 있도록 하자. 뺏기는 쓰레드도 대기중일 때만 뺏어야한다. 사용중일 때 뺏으면 큰일 난다...
• 순환 대기 예방 : 자원에 순서를 매긴다. (이후 Lock Hierarchy에서 자세히 설명할 예정) 프로세스는 자원의 순서에 따라서 요청해야한다.

Lock Hierarchy

순환 대기 예방법의 한 종류. 각 자원에 할당된 Lock에 우선순위를 매기고 다음과 같은 사용규칙에 의해 자원을 획득한다.

• 자원은 우선순위 순서대로 획득해야한다.
  자신이 획득한 Lock의 순번이 최대 n이라면, n < x 인 순번의 자원을 요청할 수 없다.
• 같은 순위의 자원에 대해서는 별도의 Lock예방을 한다. (ex 보유 대기 후 예방)

http://maxim.int.ru/bookshelf/PthreadsProgram/

Lock Hierachy의 일관성을 유지한다면, 위 그림처럼 자원 할당 그래프가 트리의 형태로 자원을 관리 할 수 있다. Tree인 그래프에서는 Cycle이 발생하지 않는다. 따라서 자원의 순환 대기 현상을 방지 할 수 있다.

DeadLock의 회피/탐지

자원 예방은 프로세스의 자원의 요청 방식을 제약한다는 점에서, 자원의 전체적인 이용률과 처리율에 나쁜 영향을 미칠 수 있다. 자원 관리자가 할당에 Deadlock이 발생할지를 '탐지'할 수 있다면 탐지된 결과에 따라서 안전성을 체크하고 자원할당을 스케쥴링하여 DeadLock을 '회피'하는 효과적인 공유를 이끌어 낼 수 있을 것이다.

http://tech.blog.framgia.com/vn/?p=1569

프로세스작업에 필요한 자원이 딱 하나씩만 있는 경우에는 자원 할당 그래프(Resource-Allocation-Graph)를 통해서 안전성을 검사할 수 있다. 요청을 edge로 자원과 프로세스를 vertex로 구성한 다음 순환이 발생하는 경우 안전하지 않다는 것을 알 수 있다. 하지만 관리자가 제공할 수 있는 자원의 개수가 여러개가 되면 문제는 좀더 복잡해 진다.

Banker's 알고리즘

은행원 알고리즘은 동일한 자원이 복수개가 있는 경우에도 Deadlock을 탐지/회피 할 수 있는 잘 알려진 알고리즘이다. 우선 각 프로세스들이 작업을 시작하기전에 필요한 자원의 종류와 최대 개수를 관리자에게 선언한다. 관리자는 자원에 대한 할당요청이 발생하면, 자원 시스템의 안전상태를 체크한다. 안전하지 않은 요청을 하는 프로세스들은, 다른 프로세스들이 자원을 반환하여 안전한 상태가 될 때까지 대기한다. 관리자는 현재 들어온 요청들에 대해서 자원을 할당하는 효과적인 순서를 찾고 그대로 수행한다.

필요한 자료 구조 (프로세스 개수: n, 자원 종류: m)

• Available: 가용 자원 개수 (vector of m)
• Max: 각 프로세스의 최대 자원 요구량 (n×m matrix)
• Allocation: 각 프로세스에게 현재 할당된 자원 개수 (n×m matrix)
• Need: 각 프로세스의 남은 자원 요구량 (n×m matrix)

Request[i][j] = k : 프로세스 P[i]가 자원 R[j]를 k개 요청하는 상황

1. Request[i][j] > Need[i][j] 이면 오류, 아니면 다음 단계로
2. Request[i][j] > Available[j] 이면 대기, 아니면 다음 단계로
3. P[i]에게 자원이 할당된 것을 가정하여 안전성 검사(아래에 설명)를 수행
4. 안전하면 자원할당, 아니면 자료구조 복구하고 P[i]는 대기

안전성 검사

std::array<int, m> Work = Available; //(m vector) 가용한 자원의 개수들
std::array<bool, n> Finish = {FALSE,}; //(n vector) 프로세스들의 진행 상태

//자원 할당가능한 프로세스 검색
for(auto i = 0; i < P.size(); ++i)
{
   if(Finish[i] == FALSE && (Need[i][j] < Work[j]) 
   {
      //쓴 자원 반환하고 Finish
      Work = Work + Allocation[i];
      Finish[i] = TRUE;
      i = 0; //다시 검색
   }
}

for(auto i = 0; i < P.size(); ++i)
{
   if(Finish[i] == FALSE) 
   {
       //끝나지 않은 프로세스가 있다면 안전하지 않음
       return false;
   }
}
//모든 프로세스의 자원 할당이 가능하면 안전상태
return true;