교착상태(Deadlock)

교착 상태(Dead lock)

두 개 이상의 프로세스들이 다른 프로세스가 점유하고 있는 자원을 기다릴 때 교착상태가 발생한다. 가령 A 프로세스와 B 프로세스가 있다고 할 때 A,B 프로세스를 끝내기 위해서 둘 다 a,b 리소스가 필요할 때 A와 B 프로세스가 각각 a 리소스와 b 리소스를 점유하고 있어 A,B 둘다 해결되지 않고 무한정 기다리고 있게 되는 경우를 예로 들 수 있다.

이러한 교착 상태가 발생하기 위해서는 4개의 조건이 동시에 만족되어야 한다. (4가지 조건이 모두 만족한다고 꼭 교착상태가 발생하지는 않지만 교착 상태가 발생하면 4가지 조건을 만족한다)

1. 상호 배제 (Mutual exclusion)

한 번에 한 프로세스만 리소스를 사용할 수 있다.

2. 대기와 보유 (Hold and wait)

적어도 하나의 리소스를 보유한 프로세스가 다른 프로세스가 보유한 추가 리소스를 획득하기 위해 대기한다.

3. 선점 없음 (No preemption)

리소스는 보유한 프로세스가 작업을 완료한 후에만 자발적으로 해제될 수 있다.

4. 환형 대기 (Circular wait)

P0가 P1이 보유한 리소스를 기다리고, P1이 P2가 보유한 리소스를 기다리는 등, 대기 프로세스 집합 {P0, P1, …, Pn}이 순환 대기하는 경우이다. 마지막으로, Pn이 P0이 보유한 리소스를 기다린다.

해결 방법

교착 상태 예방

교착 상태가 발생하는 조건 4가지중 한 가지만 배제하면 예방이 된다.

1. 상호 배제 조건을 배제

근본적으로 불가능 하다. 동기화 문제라던가 동시 접근 자체가 근본적으로 불가능한 경우도 많다.

2. 대기와 보유 조건을 배제

수행전 자원 요구는 한번에 하는 경우(one-shot allocation method)이다. 해당 프로세스에 필요한 자원이 하나라도 사용중이면 프로세스가 실행되지 못하므로 기아 현상이 발생 할 수 있다.

3. 선점 없음 조건을 배제

현재 즉시 사용할 수 없는 자원 요청 시 선점하게 하는 방식으로 예를 들면 아래와 같다. 프로세스 A가 실행되기 위해서는 a 자원이 필요하기에 a 자원을 쓰고 있는 B 프로세스에게서 자원을 선점해버린다. 그럴 B 프로세스가 구동되기 위해서는 새로운 자원이 필요한데 이 자원을 받기 위한 과정에서 기아 현상이 발생할 수 있다. 또한 애시당초 선점이 불가능한 자원의 경우도 있다. ex) 프린터

4. 환형 대기 조건을 배제

모든 자원에 우선순위를 매기고 우선순위가 높은 자원을 사용하기 위해서는 그보다 우선순위가 낮은 자원을 점유를 해제하게 하는 방법이다.
이 경우 새로운 자원이 유입될 경우 다시 모든 자원에 우선 순위를 매겨야하며 우선 순위가 높은 자원과 낮은 자원 두 개 다 필요할 경우 우선순위 높은 자원을 쓰고, 점유 해제후에 낮은 자원을 쓰고, 쓴 걸 다시 점유 해제하고 우선 순위 높은 자원을 쓰는 방식으로 해야해서 Overhead가 크고 복잡하다.

교착 상태 회피

자원을 할당할 때 교착상태에 빠지지 않을 것이라고 예상되는 경우에만 자원을 할당하는 방식으로 교착 상태를 회피한다. 교착 상태 회피를 위한 여러 알고리즘이 존재한다.

알고리즘을 논하기 전에 다음 자료구조부터 정의하고 들어가겠다.

1. m은 자원의 종류, n은 프로세스의 수

2. Available[m] : 현재 사용가능한 자원의 수를 나타낸다.
Available[i] = k 일 경우 i종류의 자원을 k개 사용가능하다는 뜻이다.

3. Max[n,m] : 2차원 배열로 크기가 n x m이다. 각 자원 유형으로부터
각 프로세스별로 최대 자원 요구를 정의한다.
예를 들어 Max[i,j]=k라면 프로세스 i는 자원 유형 j중 최대로 k개를 요청할 수 있다.

4. Allocation[n,m] ; 2차원 배열로 크기가 n x m이다. 각 자원 유형별로
각 프로세스에 할당된 자원을 정의한다.
예를 들어 Allocation[i,j]=k는 프로세스 i는 현재 자원 유형 j를 k개 할당받고 있다는 뜻이다.

5. Need[n,m] : 2차원 배열로 크기가 n x m이다. 각 자원 유형별로
각 프로세스에 필요한 나머지 자원을 정의한다.
예를 들어 Need[i,j]=k는 프로세스 i는 현재 자원 유형 j를 k개가 더 필요하다는 뜻이다.

6. Request[n,m] :  2차원 배열로 크기가 n x m이다. 각 자원 유형별로
각 프로세스가 요청한 자원을 정의한다.
예를 들어 Request[i,j]=k는 프로세스 i는 현재 자원 유형 j가 k개가 필요하다는 뜻이다.

1. 안정 상태 알고리즘

안정 상태 알고리즘은 아래와 같다.

// Work와 Finish는 각각 길이가 m과 n인 벡터이다.
   Work=Available
   finish[i] = false (i = 0,1,2....)
CHECK:   
   // 전체 프로세스 탐색간
   // 완료가 덜 되었고, 추가로 필요한 자원이 할당 가능할 경우
   if finish[i] == false && Need[i]<=Work
     Work = Work + Allocation[i];
     // i 프로세스를 완료 처리
     finish[i]=true
     go to CHECK
         
SAFTY_STATE:
   if finish[i] === true //(모든 i)
      // 시스템은 안정 상태
   //모든 i가 true가 아니면 불안정 상태

이러한 알고리즘에서 안정상태를 유지하는 요청은 받아들이되, 불안정 상태로 가는 요청은 모두 거절해버림으로써 교착 상태를 회피한다.

2. 자원 할당 그래프

단일 유형의 자원일때 사용하는 방법이다. 노드는 프로세스와 자원, 프로세스에서 자원으로 간선은 요청이고 자원에서 프로세스로의 간선은 할당이다. 그리고 점선은 claim 이라고 한다.

만약 실제로 요청을 하게되면 claim에서 request로 변경된다. claim 선이 없다면 안정적이나 어떻게 요청하느냐에 따라 불안정상태가 될수있다.

이 경우 A 프로세스에 할당되는 경우 안정적이기 때문에 A 프로세스에 할당된다.

3. Banker 알고리즘

다중 유형의 자원일때 사용하는 방법이다. 요청 이후에 불안정 상태가 된다면 이전 상태로 롤백하는 방식이다.

Request = i 프로세스의 request 배열
Request[i,j] = k // i 프로세스가 j 자원을 k개 요청

if Request[i] > Need[i] // 요청하는 값이 추가 필요한 자원보다 클 경우
// 에러 호출

if Request[i] > Available[i] // 사용가능한 자원보다 클 경우
// 대기

Available[i] = Available[i] - Request[i]
Allocation[i] = Allocation[i] + Request[i]
Need[i] = Need[i] - Request[i]

if safe_algorithm // 안정 상태일 경우
 // 그대로 할당
else
 // 프로세스는 대기, Available과 Allocation, Need 작업 롤백

교착 상태 탐지

분리해두긴 했지만 교착 상태 탐지와 회복은 항상 같이 따라온다. 탐지 알고리즘으로 교착상태인지 아닌지 확인하고 교착 상태인 경우 회복 알고리즘으로 복구하기 때문이다. 단일 자원일 때와 다중 자원일때 사용하는 방식이 다른데 단일 자원의 경우 아래와 같다.

wait for graph라고 불리는 그래프로 자원을 반납하는 것을 기다리는 것만 표기한 것인데 cycle이 존재한다면 교착상태이다

다음은 다중 자원간 교착 상태 탐지 알고리즘이다. 안정 상태 알고리즘과 크게 다르지 않다.

a. Work=Available로 초기화 한다.
   만약 Allocation[i]가 0이 아니면 Finish[i]가 false이고
   Allocation[i]가 0이면 Finish[i]는 true이다.
b. finish[i] = false 이고 Need[i]<=Work을 만족하는 i를 찾는다.
   이런 i가 없다면 d로 이동한다.   
c. Work = Work + Allocation[i];
   finish[i]= true
   b로 이동한다.   
d. 만약 finish[i]가 false라면 프로세스 i는 교착 상태이다.

다중 자원의 경우 본질적으로 안정 상태 알고리즘과 같다. 단지 안정 상태 알고리즘의 경우 할당하기전에 미리 확인해보는 반면 이 경우 할당하고나서 교착 상태인지 확인하는 점이 다르다.

이러한 탐지 알고리즘은 계속해서 구동해야 탐지가 되므로 백그라운드에서 계속 프로세스가 돌아가고 있으며 시스템에 부담이 된다. 그리고 어떤 프로세스가 데드락의 원인이 되는지 파악 할 수 있기 때문에 회복 알고리즘을 구동하는데 도움이 된다.

교착 상태 회복

1. 프로세스 중지

1) 데드락의 원인이 되는 모든 프로세스들을 일시에 중지

2) 교착상태 사이클이 제거될때까지 하나씩 프로세스 중지

제거시에 프로세스 우선 순위나 지금까지 사용시간, 혹은 남은 시간을 고려하여 먼저 중지시킬 수 있다.

2. 자원 선점

1) 희생 프로세스 선택

교착 상태에 빠진 프로세스들 중 하나를 선택하고 이 프로세스가 점유중인 자원을 빼앗아 다른 프로세스에게 할당하는 방법이다. 어느 프로세스를 선택할지 어떤 자원을 뺏어 올지에 대한 고려가 필요하다. 그리고 계속해서 희생당하는 프로세스만 희생당할 경우 기아 현상이 발생할 수 있기 때문에 이에 대한 가중치가 필요하다.

2) 복귀(Rollback)과 체크포인트(Checkpoint)

교착상태가 발생할 것으로 예상되는 프로세스를 주기적으로 저장해두었다가 교착 상태가 발생하면 가장 최근에 저장한 상태로 복구시켜 다시 실행시킨다.

결론

교착 상태를 예방하거나 회피하거나 탐지하거나 회복하는 방식의 경우 너무 overhead가 커서 현대 OS에서는 교착 상태가 발생 할 수 있는 작은 가능성을 무시해버리는 방식(Ostrich Deadlock)을 차용하고 있으며 희소한 확률을 뚫고 교착 상태 발생시 시스템을 재시작하거나 특정한 프로세스를 강제 종료하는 방법으로 해결한다.

참고 자료

• Operating System Concept (written by Silberschatz, Galvin and Gagne)
• 데드락(Dead lock) 해결 방법 - 운동개발좋아