Deadlock

1. deadlock 발생 조건

- 다음 네 조건이 모두 충족될 때 deadlock이 발생한다.

(1) 자원을 한 순간에 한 프로세스만이 사용 가능(mutual exclusion)

(2) 프로세스가 점유하고 있는 자원은 다른 프로세스가 강제로 빼앗을 수 없음(no preemption)

(3) 어떤 프로세스가 수개의 자원을 동시에 점유해야 작업을 처리할 수 있는데 그 중 일부 자원만 점유하고 있다 할 때, 나머지 자원을 얻을 때까지 점유 중인 자원을 계속 점유하면서 무한 대기함(hold and wait)

(4) ‘자원 -> 자원을 점유하는 프로세스 -> 프로세스가 요청하는 자원’ 순으로 방향그래프를 구성했을 때 그 방향그래프에 사이클이 존재함(circular wait)

- 한 종류 자원에 둘 이상 인스턴스가 존재하는 상황이라면 네 가지 조건이 모두 충족되더라도 deadlock이 발생되지 않을 수 있다. 만약 deadlock을 일으킬 수 있는 사이클이 존재하더라도 여러 자원에 인스턴스가 풍부해서 사이클이 점유하는 인스턴스보다 여유 인스턴스가 더 많이 있다면 deadlock이 발생되지 않는다.

- starvation 문제는 프로세스가 대기열에 오래 머무를수록 그 프로세스의 자원 할당 우선순위를 높임으로써 해결할 수 있지만(aging) deadlock 문제는 그와 같은 방식으로는 해결할 수 없다는 차이가 있다.

2. deadlock을 처리하는 방법

1) 현재 시스템의 자원-프로세스의 특성을 deadlock 발생 조건과 다르도록 설정하여 데드록을 예방(deadlock prevention)

(1) mutual exclusion 조건 변경

• 독점적으로 사용하는 자원을 없앤다.

• 공유할 수 없는 자원이 반드시 있기 때문에 deadlock 문제가 발생하는 것이므로 현실적으로 이런 방식으로 deadlock을 예방하는 것은 불가능하다.

(2) no preemption 조건 변경

• 자원을 프로세스가 점유하고 있더라도 다른 프로세스가 이를 요청하면 즉시 양도한다.

• CPU나 메모리 같이 점유를 뺏기기 전 상태를 저장해두었다가 다시 점유할 기회가 왔을 때 이를 복구하기 쉬운 매체에서 사용할 수 있는 방법이다. 다만 이렇게 해결할 경우 overhead가 커지며, 이처럼 무조건적 양도 방식으로는 우선순위가 낮은 프로세스는 starvation 문제에 빠질 수 있다는 등의 단점이 있다.

(3) hold and wait 조건 변경

• 둘 이상의 자원이 필요한데 어느 하나를 즉시 점유할 수 없다면, 점유했던 모든 자원을 즉시 반납한다(all or nothing).

• 각 프로세스에게 각자가 앞으로 필요할 자원을 모두 미리 할당하는 식으로 구현할 수 있다. 각 프로세스가 자신이 필요할 자원을 모두 알기 어렵다는 점, 당장 사용할 것도 아닌 자원을 선점했다는 점에서 낭비라는 점, 적은 자원만 필요로 하는 프로세스가 starvation 위험이 높아진다는 점 같은 단점이 있다.

(4) circular wait 조건 변경

• 각 자원별로 할당 순서를 정해, 프로세스가 오직 그 순서대로 자원을 얻게 되었을 때에만 자원을 할당한다.

• 이 경우 (a)프로세스의 자원 할당 여부가 자원별 할당 순서를 정하는 기준에 크게 의존하고 (b)반드시 그 순서로 자원을 얻어야 할 필요가 없는 경우에도 순서가 강제된다는 등의 단점이 있다.

2) 프로세스에 자원을 할당해도 deadlock이 발생하지 않을 정도로 자원 인스턴스가 풍부한 경우에만 자원을 할당하고 그렇지 않은 경우에는 프로세스에 대한 자원 할당을 대기함으로써 데드록 회피(deadlock avoidance)

- deadlock은 기본적으로 여러 프로세스가 한정된 자원 인스턴스 내에서 서로 경쟁하기 때문에 발생하는 것이므로, 자원 인스턴스가 충분히 풍부한 경우에만 프로세스에게 자원을 할당하고 그렇지 않은 경우에는 자원 할당을 대기하는 방식으로도 deadlock을 피할 수 있다. 이 경우 ‘자원 인스턴스가 풍부하다’라는 상황을 어떻게 정의할지가 문제가 된다.

- 이를 구현하는 방법으로서 banker’s algorithm이 있다. banker’s algorithm은 (1)각 프로세스에게 각자가 사용할 자원별 최대 인스턴스 수를 미리 수집하고 (2)현재 자원을 요청하는 프로세스에게 그 프로세스에게 미리 수집했던 최대 자원 인스턴스 수를 모두 할당 할 수 있을 정도로 현재 가용 자원이 풍부하면 그 프로세스에게 자원을 할당하고, 부족하면 (설사 가용 자원이 현재 요구하는 자원 인스턴스 수보다는 여유가 있어도) 그 프로세스에게 자원 할당을 대기한다.

- 데드록 회피는 기본적으로 각 프로세스가 최대로 사용할 자원 수를 미리 수집해야 하는데 이는 부정확할 수 있고, 또 아무리 현재 자원에 여유가 상당해도 항상 프로세스가 당장 최대 자원을 요청할 경우에 대비해 자원 할당을 자제하는 경향이 있어 자원 낭비가 있고 비효율적이다.

3) 일단 수행하되, deadlock이 발생한 듯 보이면 그때 복구(deadlock detection and recovery)

- 일단 수행하되, 시스템 수행이 느려지는 등 deadlock이 발생한 듯 보이면 그때 deadlock 발생 여부를 검사하여(자원의 인스턴스가 하나면 사이클 검사 방법으로, 둘 이상이면 banker’s algorithm과 유사한 방법으로 deadlock 발생 여부를 검사한다) deadlock이 발생했다면 관련된 프로세스를 모두/하나씩 종료시키거나 deadlock이 사라질 때까지 프로세스가 가진 자원을 빼앗아 보되 이로 인해 발생할 overhead를 최소로 할 프로세스의 자원을 빼앗는 식으로 문제를 해결하는 방법이다.

- 프로세스가 가진 자원을 빼앗는 식으로 recovery를 하면, 자원을 빼앗긴 프로세스가 다시 자원을 얻거나 한번 빼앗긴 후 다시는 자원을 얻지 못하는 문제(starvation)가 있을 수 있다. 이 경우, 프로세스가 자원을 뺏는 패턴을 변경하거나 프로세스가 자원을 빼앗긴 횟수를 세는 변수를 따로 설정해 한 프로세스만 자원을 뺏기는 것을 피하도록 하여 문제를 해결할 수 있다.

4) 그냥 놔두기(deadlock ignorance)

- deadlock은 발생하는 경우가 매우 드문 데 반해 위에 언급된 방법들은 매우 큰 overhead를 요하는 방법이기에, unix를 포함하여 현재 쓰이는 대부분의 OS는 deadlock에 대해 별다른 조치를 취하지 않으며 deadlock 발생 시 사용자가 직접 일일이 프로세스를 종료시켜 문제를 해결하게 하고 있다.