Deadlock(교착 상태) Solution

1. 교착 상태 해결 방법

이전 시간에 교착 상태에는 4가지 필요조건이 있다고 했다.

1. 상호 배제(Mutual exclusion)
2. 비선점(Non-preemption)
3. 점유와 대기(hold and wait)
4. 원형 대기(circular waiting)

이들 중 하나라도 성립이 안되면 교착 상태가 걸리지 않는다.

교착상태를 해결하는 방법은 예방(prevention), 회피(avoidance), 검출(detection), 회복(recovery)가 있다.

1. 교착상태 예방: 교착 상태를 유발하는 네 가지 조건을 무력화한다.
2. 교착상태 회피: 교착 상태가 발생하지 않는 수준으로 자원을 할당한다.
3. 교착상태 검출: 자원 할당 그래프(resource allocation graph)를 사용하여 교착 상태를 발견한다.
4. 교착상태 회복: 교착 상태를 검출한 후 해결한다.

1.1 교착 상태 예방

교착 상태를 유발하는 4가지 조건이 발생하지 않도록 무력화하는 방식이다. 교착 상태는 상호 배제, 비선점, 점유와 대기, 원형 대기라는 4가지 조건을 동시에 충족해야 발생하기 때문에 이중 하나라도 막는다면 교착 상태가 발생하지 않는다. 그러나 이 방법은 실효성이 적어 잘 사용되지 않는다.

1.2 교착 상태 회피

자원 할당량을 조절하여 교착 상태를 해결하는 방식이다. 즉 자원을 할당하다가 교착 상태를 유발할 가능성이 있다고 판단되면 자원 할당을 중단하고 지켜보는 것이다. 그러나 자원을 얼마만큼 할당해야 교착 상태가 발생하지 않는다는 보장이 없기 때문에 실효성이 적다.

1.3 교착 상태 검출과 회복

교착 상태 검출은 어떤 제약을 가하지 않고, 자원 할당 그래프를 모니터링하면서 교착 상태가 발생하는지 살펴보는 방식이다. 만약 교착 상태가 발생하면 교착 상태 회복 단계가 진행된다. 교착 상태를 검출한 후 이를 회복시키는 것은 결론적으로 교착 상태를 해결하는 현식적인 접근 방법이다.

2. 교착 상태 예방

교착 상태 예빵은 교착 상태를 유발하는 4가지 조건 중 하나라도 발생하지 않도록 막아 교착 상태를 처리하는 방법이다. 말 그대로 사전 예방하는 것이므로 다음과 같은 4가지 방법이 있다.

2.1 상호 배제(mutual exclution) 예방

시스템 내에 있는 상호 배타적인 모든 자원, 즉 독점적으로 사용할 수 있는 자원을 없애버리는 방법이다. 시스템 내의 모든 자원을 공유할 수 있다면 교착 상태가 발생하지 않는다. 식사하는 철학자 문제에서도 모든 철학자가 포크를 누가 점유하는 것이 아닌 공유할 수 있다면 교착 상태가 발생하지 않을 것이다. 변수나 파일도 공유하면 교착 상태가 없다.

그러나 현실적으로 모든 자원을 공유할 수 없으며 상호 배제를 적요하여 보호해야 하는 자원이 있다. 가령 포크를 공유화하여 동시에 사용한다는 것은 말이 안되는 것과 같다. 또한 자원을 공유하게 됨으로서 임계구역(critical section)이 보호받지 못하는 문제가 생기기도 한다.

2.2 비선점(non-preemption) 예방

모든 자원을 빼앗을 수 있도록 만드는 방법이다. 식사하는 철학자 문제에서 옆 사람의 포크를 빼앗을 수 있다면 교착 상태가 발생하지 않는다. 그런데 임계구역(critical section)을 보호하기 위해 잠금을 사용하면 자원을 빼앗을 수 없다. 따라서 시스템의 모든 자원을 빼앗을 수 있도록 하지 못한다.

어떤 자원을 빼앗을 지라도 어떤 기준으로 빼앗을지, 빼앗은 시간 중 얼마나 사용할지 결정하기 어렵다. 또한 이러한 선점 방식은 starvation현상을 일으킨다. 가령 우선순위 별로 높은 프로세스가 자원을 무조건 먼저 선점해버린다면 우선 순위가 낮은 프로세스는 starvation 상태에 빠지게 된다. 무조건적으로 에이징을 사용하는 것도 해결방법은 아니다. 에이징을 사용하여 특정 조건 이상일 때는 무조건 해당 자원을 사용할 수 있도록 한다는 것 자체가 비선점 효과를 일으켜 데드락에 빠지게 할 수 있기 때문이다.

2.3 점유와 대기(hold and wait) 예방

프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법이다. 다시 말해 전부 할당하거나, 아니면 아예 할당하지 않는(all or nothing)방식을 적용하는 것이다. 이를 위해 프로세스는 시작 초기에 자신이 사용하려는 모든 자원을 한꺼번에 점유하거나, 그렇지 못할 경우 자원을 모두 반납해야 한다.

이 방법은 식하는 철학자 문제에서 왼쪽 포크를 잡은 상태에서 오른족 포크를 잡지 못하도록 하는 것과 같다. 이는 철학자들은 식사를 시작할 때 양손에 포크를 잡아야 하며, 그렇게 할 수 없다면 이미 잡은 포크는 내려놓아야 한다. 그러면 동작이 빠른 철학자가 먼저 식사를 할 것이다.

앞서 살펴본 상호 배제 예방과 비선점 예방은 자원에 대한 제약을 풀어버리는 것이다. 그러나 임계구역으로 보호받는 자원에 대한 제약을 풀기는 어렵다. 점유와 대기 예방은 자원이 아닌 프로세스의 자원 사용 방식을 변화시켜 교착 상태를 처리한다는 점에서 의미가 있다.

한편 점유와 대기 예방은 다음과 같은 단점이 있다.

1. 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어렵다: 프로세스가 필요한 자원을 모두 확보한 후 실행했는데 추가로 필요한 자원이 생기면 이를 다시 확보하기가 어렵다.
2. 자원의 활용성이 떨어진다: 프로세스가 앞으로 사용할 자원까지 미리 선점해버리기 때문에 그 자원을 필요로 하는 다른 프로세스의 작업이 진행되지 않는다. 당장 사용하지도 않을 자원을 미리 선점하여 자원 낭비가 심하다.
3. 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 자원 선점에 불리하다: 자원을 많이 사용하는 프로세스는 자원을 적게 사용하는 프로세스보다 자원을 동시에 확보하기가 어렵다. 그러므로 많은 자원을 사용하는 프로세스의 작업이 지연되는 starvation 현상이 발생한다.
4. 결국 일괄 작업 방식으로 동작한다: 점유와 대기 예방을 실제로 구현하면 거의 모든 프로세스가 일괄 작업 방식으로 처리된다. 필요로 하는 자원을 확보한 순서대로 실행하면 그 자원을 획득한 프로세스가 작업을 끝내야 다른 프로세스가 작업을 할 수 있다. 결국 모든 작업이 일괄 작업 방식으로 처리되어 시스템의 효율이 떨어진다. 자원을 확보한 프로세스가 자원을 잠깐 사용하든, 오래 사용하든 상관없다. 무조건 확보한 후 실행해야 하므로 다른 프로세스는 해당 자원을 기다리려야하고, 이는 일괄 작업 방식과 같다.

2.4 원형 대기(circular waiting) 예방

점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법이다. 프로세스들이 한 줄로 길게 늘어선다면 그 줄의 맨 끝에서부터 문제가 해결될 것이다. 자원을 한 병향으로만 사용하도록 설정함으로써 원형 대기를 예방할 수 있다. 즉 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당하는 것이다. 다시 말해, 숫자가 작은 자원을 잡은 상태에서 큰 숫자를 잡는 것은 허용하지만, 숫자가 큰 자원을 잡은 상태에서 작은 숫자를 잡는 것은 허용하지 않는다.

다음과 같이 자원에 숫자를 부여하고, 낮은 번호의 자원을 선점한 프로세스가 높은 숫자 번호의 자원을 대기하여 할당받을 수 있다. 그러나, 이 반대로 번호가 높은 자원을 선점한 프로세스는 번호가 낮은 자원을 대기할 수 없도록 한다.

이렇게 함으로서 우리는 하나의 정렬을 하는 것과 같다. 자원 선점을 오른쪽으로 다가갈 수 있도록은 할 수 있지만, 왼쪽으로는 못가게 함으로서 일렬로 만드는 것이다.

프로세스 P1은 자원 R1을 할당받은 상태에서 자원 R2를 기다리고, 프로세스 P2는 자원 R2를 할당받은 상태에서 자원 R1을 기다린다. 그런데 자원 R1의 번호가 작아서 프로세스 P2의 요청이 거절된다. 프로세스 P2는 R1자원을 할당받을 수 없어 강제 종료되고, 프로세스 P1은 R2를 할당받아 정상적으로 실행된다. 작은 번호의 자원을 쓸 수 없게 하면 자원 할당 그래프에 원형이 생기지 않는다.

원형 대기 예방은 모든 자원을 할당받아야 실행할 수 있는 점유와 대기 예방과 같이 프로세스 작업 방식에 대한 해결방법이다. 원형 대기 예방은 점유와 대기보다 완화된 방법이다. 그러나 이 또한 다음과 같은 단점이 있다.

1. 프로세스 작업 진행에 유연성이 떨어진다: 자원을 할당받지 못한 프로세스는 결국 자원을 얻지 못해 종료되는데 이는 중요한 프로세스가 자원을 할당받지 못해 사용자에게 불쾌함을 준다. 또한 프로세스 실행 과정에 있어 유연성이 떨어진다.
2. 자원의 번호를 어떻게 부여할 것인가?: 프로세스가 큰 번호의 자원을 사용한 후 작은 번호의 자원을 사용할 수 없기 때문에 자원에 번호를 붙이는 데 매우 신중해야 한다. 자원에 어떻게 번호를 붙이든 자원 사용에 제약이 따른다.

지금까지 살펴본 교착 상태 예방은 교착 상태를 유발하는 4가지 조건이 일어나지 않도록 제약을 가하는 방법이 있다. 그러나 자원을 보호하기 위해 상호 배제와 비선점을 예방하기 어려우며 점유와 대기, 원형 대기는 프로세스 작업 방식을 제한하고 자원을 낭비하기 때문에 사용할 수 없다.

3. 교착 상태 회피

3.1 교착 상태 회피의 개념

교착 상태 회피는 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어주는 방법이다. 교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고, 교착 상태가 발생하는 범위에 있으면 프로세스를 대기시킨다.

교착 상태 회피는 할당되는 자원의 수를 조절하여 교착 상태를 피한다. 교착 상태 예방은 프로세스의 작업 방식을 제약하기 때문에 사용할 수 없었는데, 교착 상태 회피는 시스템의 운영 방식에 변경을 가하지 않기 때문에 교착 상태 예방보다 좀 더 유연하다.

시스템에 총 20개의 자원이 있다고 가정했을 때 1개의 자원을 할당하면 교착 상태가 발생하지 않는다. 점유와 대기 조건이 충족되지 않기 때문이다. 그러나 20개의 자원을 모두 할당하면 교착 상태가 발행할 확률이 매우 높아진다. 자원을 많이 할당할수록 교착 상태가 발생할 확률이 커진다.

교착 상태 회피는 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태(safe state)와 불안정 상태(unsafe state)로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당한다.

할당된 자원이 적으면 안정 상태가 크고, 할당된 자원이 늘어날수록 불안정 상태가 커진다. 그렇다고 불안정 상태에서 항상 데드락이 발생하는 것은 아니다. 데드락은 불안정 상태의 일부분이며, 불안정 상태가 커질수록 교착 상태가 발생할 가능성이 높아질 뿐이다. 교착 상태 회피는 안정 상태를 유지할 수 있는 범위 내에서 자원을 할당함으로써 교착 상태를 피한다.

3.2 은행원 알고리즘

교착 상태 회피를 구현하는 방법은 여러 가지인데 그중 하나는 다익스트라가 제안한 *은행원 알고리즘(banker's algorithm)이다. 은행이 대출을 해주는 방식, 즉 대출 금액이 대출 가능한 범위 내이면(안정 상태이면) 허용되지만 그렇지 않으면 거부되는 것과 유사하기 때문에 이렇게 불리게 되었다.

가령, 내가 우동 10개와 라면 30개를 준비했다고 하자, 나는 손님을 최대 10명만 맡을 수 있다. 10개 초과부터는 라면 11개를 줄 수 없기 때문이다. 그리고 우동 10개를 다 팔게되면 이후부터는 손님 30명을 받을 수 있게 된다. 가능한 자원 내에서 필요한 수를 가장 빠르게 맞출 수 있는 것을 먼저 처리하는 것이 은행원 알고리즘의 핵심이다.

• 은행원 알고리즘의 변수

변수	설명
전체자원(Total)	시스템 내 전체 자원의 수
가용 자원(Available	시스템 내 현재 사용할 수 있는 자원으 ㅣ수(가용 자원 = 전체 자원 - 모든 프로세스의 할당 자원)
최대 자원(Max)	각 프로세스가 선언한 최대 자원의 수
할당 자원(Allocation)	각 프로세스에 현재 할당된 자원의 수
기대 자원(Expect)	각 프로세스가 앞으로 사용할 자원의 수(기대 자원 = 최대 자원 - 할당 자원)

위의 표는 은행원 알고리즘에서 사용하는 변수이다. 은행원 알고리즘에서 각 프로세스는 자신이 사용할 자원의 최대 수(MAX)를 운영체제에 알려준다. 운영체제가 자원을 할당할 때 시스템의 상태를 파악하는 데 꼭 필요한 정보이기 때문이다.

각 프로세스에 할당된 자원의 수는 '할당 자원'에 표시된다. 각 프로세스마다 자신이 선언한 최대 자원에서 현재 할당된 자원의 수를 빼면 '기대 자원'이 된다. 또한 전체 자원에서 각 프로세스에 할당되고 남은 자원의 수가 '가용 자원'이다. 따라서 가용 자원은 전체 자원에서 모든 프로세스의 자원을 뺀 값이다. 자원을 할당할 때의 기준은 다음과 같다.

• 각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당한다. 가용 자원이 기대 자원보다 크다는 것은 그 자원을 사용하여 작업을 끝낼 수 있는 프로세스가 있다는 의미이므로 안정 상태이다.
• 가용 자원이 어떤 기대 자원보다 크지 않으면 할당하지 않는다. 가용 자원을 사용하여 작업을 마칠 수 있는 프로세스가 없다는 의미이므로 불안정 상태이다.

안정 상태: 각 프로세스의 기대 자원과 비교하여 자원이 크거나 같은 경우가 한 번 이상인 경우를 말한다.

다음의 그림은 안정 상태의 예이다. 시스템에 있는 전체 자원의 수는 14개이고, 각 프로세스가 필요로 하는 최대 자원의 수는 P1은 5, P2는 6, P3는 10개이다. 각 프로세스에 현재 할당된 자원은 프로세스 P1이 2개, 프로세스 P2가 4개, 프로세스 P3가 6개로 총 12개이다. 따라서 시스템 전체에서 사용할 수 있는 가용 자원은 2개이다. 또한 기대 자원은 프로세스가 선언한 최대 자원에서 현재 할당된 자원의 수를 뺀 값이므로 프로세스 P1은 3개, 프로세스 P2는 2개, 프로세스 P3은 4개이다.

안정 상태인 이유는 현재 가용 상태가 2개인데 프로세스 P2가 필요로 하는 자원이 2개이기 때문이다. 프로세스 P2가 가용 자원 2개를 사용하여 실행을 종료하면 이미 할당받아 사용하던 자원 6개를 반환하고, 이를 프로세스 P1이나 P3에 할당하면 전체 작업을 무리 없이 완료할 수 있다.

그런데 현재 가용 자원을 프로세스 P2가 아닌 다른 프로세스에게 나누어준다면 위의 그림은 불안정 상태가 된다. 프로세스 P1이나 P3에 가용 자원을 할당하면 기대 자원을 충족하지 못하기 때문에 작업을 미칠 수 없다. 프로세스 P2에 자원을 할당해야만 안정 상태를 계속 유지할 수 있다.

위의 그림은 불안정 상태이다. 가용 자원이 1개인데 이것으로는 어떤 프로세스의 기대 자원도 충족할 수 없다. 이는 현재 남은 자원으로는 어떤 프로세스도 끝낼 수 없다는 의미이다. 은행원 알고리즘에서는 현재 실행 중인 프로세스 가운데 하나라도 끝낼 수 있을 때 가용 자원을 할당해야 한다.

참고 영상
https://www.youtube.com/watch?v=lMNrmDUJ3GY

3.3 교착 상태 회피의 문제점

교착 상태 회피의 원칙은 교착 상태가 발생하지 않을 수준까지만 자원을 나누어주는 것이다. 하지만 여기에는 다음과 같은 문제가 있기 때문에 교착 상태 회피를 사용하지 않는다.

• 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다.
  교착 상태 회피 방식을 사용하려면 모든 프로세스가 자신이 사용할 자원을 미리 선언해야 하는데 이는 쉬운 일이 아니다. 또한 미리 선언한 자원이 정확하지 않으면 교착 상태 회피에서도 교착 상태가 발생할 수 있다.

• 시스템의 전체 자원 수가 고정적이어야 한다.
  은행원 알고리즘에서 안정 상태나 불안정 상태를 파악하려면 시스템의 전체 자원 수가 고정적이어야 한다. 그러나 일시적인 고장이나 새로운 자원이 추가되는 일이 빈번하므로 시스템의 자원 수가 유동적이다.

• 자원이 낭비된다.
  모든 불안정 상태가 교착 상태가 되는 것은 아님에도 불구하고 자원을 할당하지 않은 것은 자원 낭비이다. 프로세스에 따라 드물지만 최대 자원을 사용하지 않고 작업을 마치는 경우도 있다. 만약 P2 프로세스가 자원을 다 사용하지 않고 종료되면 자원 4개를 반납하기 때문에 다른 프로세스가 작업을 완료할 수 있다. 교착 상태 회피는 실제로 교착 상태가 발생하지 않는데도 발생할 것이라고 예상함으로써 프로세스에 자원에 할당하는 데 제약을 둔다.

4. 교착 상태 검출

4.1 교착 상태 검출의 개념

교착 상태 예방은 실제로 구현하기 어렵다. 교착 상태 회피는 구현할 수 있지만 자원을 낭비하는 문제가 있다. 따라서 교착 상태 해결 방법 중 가장 현실적인 것은 바로 교착 상태 검출이다. 교착 상태 검출은 운영체제가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시하는 방식이다. 만약 교착 상태가 발견되면 이를 해결하기위해 교착 상태 회복 단계를 밟는다.

교착 상태 검출은 타임아웃을 이용하는 방법과 자원 할당 그래프를 이용하는 방법이 있다.

4.2 타임아웃을 이용한 교착 상태 검출

타임아웃을 이용한 교착 상태 검출은 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법이다. 교착 상태가 자주 발생하지 않을 것이라는 가정하에 사용하는 것으로, 특별한 알고리즘이 없어 쉽게 구현할 수 있다. 그런데 이 방법은 다음과 같은 문제가 있다.

1. 엉뚱한 프로세스가 강제 종료될 수 있다.
   타임아웃 시간 동안 작업이 진행되지 않은 모든 프로세스가 교착 상태 때문에 작업이 이루어지지 않은 것은 아니다. 타임아웃을 이용하면 교착 상태 외의 다른 이유로 작업이 진행되지 못하는 모든 프로세스가 강제 종료될 수 있다.

2. 모든 시스템에 적용할 수 없다.
   여러 군데에 데이터가 나뉜 분산 데이터베이스의 경우에는 타임아웃을 이용하는 방법을 적용하기가 어렵다. 분산 데이터베이스는 데이터가 여러 시스템에 나뉘어 있고, 각 시스템이 네트워크로 연결되어 있다. 이러한 시스템에서는 원격지에 있는 프로세스의 응답이 없는 것이 교착 상태 때문인지, 네트워크 문제 때문인지, 단순 처리가 늦어지는 것인지 정확히 알 수 없다. 그러므로 타임아웃 방법을 적용하여 교착 상태를 파악하기 어렵다.

위와 같은 문제에도 불구하고, 타임아웃은 대부분의 DB와 운영체제에서 많이 선호된다. 이후에 나올 자원 할당 그래프를 이용하여 교착 상태를 찾는 방법은 작업이 너무 많아서 구현하기가 힘들기 때문이다. 자주 발생하지 않는 교착 상태를 찾기 위해 자원 할당 그래프를 유지하면서 모든 자원을 감시하기란 어려운 일이다. 그래서 타임아웃을 이용하는 방법을 '가벼운 교착 상태 검출'이라 부르고, 자원 할당 그래프를 이용하는 방법을 '무거운 교착 상태 검출'이라 부른다.

데이터베이스에서는 타임아웃으로 데이터의 일관성이 깨지는 문제를 해결하기 위해 데이터베이스에서는 체크포인트(check point)와 롤백(roll back)을 사용한다. 체크포인트는 작업을 하다가 문제가 발생하면 저장된 상태로 되돌아오기 위한 표시이다. 체크포인트를 설정하면 현재 시스템 상태가 하드디스크에 저장되는데, 이렇게 저장된 데이트를 스냅숏(snap shot)이라고 한다. 롤백은 작업을 하다가 문제가 발생하여 과거의 체크포인트로 되돌아가는 것을 말한다. 롤백이 일어나면 저장된 스냅숏을 복원하여 시스템 체크포인트 시점으로 되돌린다.

위의 그림은 체크포인트와 롤백을 사용하여 타임아웃을 처리하는 것을 보여준다. 데이터 베이스에서 중요한 데이터에 잠금을 요청하면 체크포인트를 만들고 해당 시점의 스냅샷을 저장한다. 그리고 잠금을 얻은 후에 작업을 계속 진행한다. 만약 타임아웃이 걸려서 프로세스를 중단하거나 잠검을 포기해야 한다면 롤백을 사용하여 체크포인트 시점으로 시스템을 복귀시킨다.

이러한 방식은 운영체제에도 적용된다. 윈도우에서 '특정 시점으로 복원'은 스냅샷과 롤백을 이용하여 운영체제를 복원시키는 작업이다.

4.3 자원 할당 그래프(Resource Allocation Graph)를 이용한 교착 상태 검출

교착 상태를 검출하는 또 다른 방법은 자원 할당 그래프를 이용하는 것이다. 자원 할당 그래프를 보면 시스템 내의 프로세스가 어떤 자원을 사용하고 있는 지 혹은 기다리고 있는지를 알 수 있다.

<교착 상태가 없는 자원 할당 그래프>

<교착 상태가 있는 자원 할당 그래프>

다음 그림은 교착 상태가 없는 자원 할당 그래프와 교착 상태가 있는 자원 할당 그래프이다.

• 교착 상태가 없는 자원 할당 그래프
  <교착 상태가 없는 자원 할당 그래프>에서 프로세스 P1은 프로세스 P2가 자원 R2를 다 사용하고 반환하기를 기다리고 프로세스 P4는 프로세스 P1을 프로세스 P3은 프로세스 P4를 기다리고 있다. 하지만 이 자원 할당 그래프에는 사이클이 존재하지 않는다. 그러므로 프로세스 P2가 작업을 마치고 자원 R2를 반환하면 나머지 프로세스의 작업이 계속 진행되며 결국 교착 상태가 발생하지 않는다.

• 교착 상태가 있는 자원 할당 그래프
  운영체제는 자원을 요청하거나 할당할 때마다 자원 할당 그래프를 갱신하는데, 이때 사이클이 발생하면 교착 상태가 검출된 것으로 판단한다. <교착 상태가 있는 자원 할당 그래프>는 프로세스 P2가 추가로 자원 R3을 요구하는 경우인데 P1->P2->P4->P1로 이어지는 사이클이 존재하기 때문에 운영체제는 교착 상태가 발생한 것으로 판단한다.

그러나 위의 그림은 단일 자원을 사용하는 경우를 말하는 것이고, 다중 자원인 경우에는 사이클이 생긴다고 무조건 교착 상태에 빠졌다고 판단할 수 없다.

다음과 같은 경우에는, 빨간색으로 자원의 수를 표시하였다. 이와 같은 경우가 다중 자원인 경우인데, R1이 자원이 2개이기 때문에 P4가 자원 R1을 할당받을 수 있고, R1과 R3를 풀어준다. R3를 P2가 얻게되고, P2는 R2, R3를 해제한다. 그리고 P1, P3가 자원을 할당받고 끝이난다. 따라서 사이클이 생긴다고 무조건 데드락에 걸리는 것은 아니다.

자원 할당 그래프를 이용하여 교착 상태를 검출하는 방법은 프로세스의 작업 방식을 제한하지 않으면서 교착 상태를 정확하게 파악할 수 있다는 것이 장점이다. 그러나 자원 할당 그래프를 유지하고, 갱신하고, 사이클을 검사하는 추가 작업으로 인해 오버헤드가 발생하는 단점이 있다. 이러한 추가 작업을 줄이기 위해 자원이 할당될 때마다 사이클 검사를 하는 것이 아니라 일정 시간마다 하는 방법도 있다.

5. 교착 상태 회복

교착 상태가 검출되면 교착 상태를 푸는 후속 작업을 한다. 이를 교착 상태 회복이라고 한다. 교착 상태 회복 단계에서는 교착 상태를 유발한 프로세스를 강제 종료한다. 프로세스를 강제로 종료하는 방법은 다음과 같이 두 가지가 있다.

• 교착 상태를 일으킨 모든 프로세스를 동시에 종료
  교착 상태를 일으킨 모든 프로세스를 동시에 종료하는 방법이다. 그런데 이 방법은 종료된 프로세스들이 동시에 작업을 시작하면 다시 교착 상태를 일으킬 가능성이 크다. 그러므로 모든 프로세스를 강제로 종료한 후 다시 실행할 때는 순차적으로 실행해야 하며, 이때 어떤 프로세스를 먼저 실행할 것인지 기준이 필요하다.

• 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
  교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료하면서 나머지 프로세스의 상태를 파악하는 방법이다. 프로세스를 종료할 때 어떤 프로세스부터 종료할 것인지 다음과 같은 기준이 필요하다.

  1. 우선순위가 낮은 프로세스를 먼저 종료한다.
  2. 우선순위가 같은 경우 작업 시간이 짧은 프로세스를 먼저 종료한다.
  3. 위의 두 조건이 같은 경우 자원을 많이 사용하는 프로세스를 먼저 종료한다.

교착 상태 회복 단계에서는 관련 프로세스를 종료하는 일 뿐만 아니라, 강제 종료된 프로세스가 실행되기 전에 시스템을 복구하는 일도 해야한다. 시스템 복구는 명령어가 실행될 때마다 체크포인트를 만들어 가장 최근의 검사 시점으로 돌아가는 식으로 한다. 그런데 이 방법은 작업량이 상당하여 시스템에 부하를 주므로 체크포인트를 무분별하게 사용하지 말고 선택적으로 사용해야 한다.

교착 상태 회복은 검출과 같이 사용되며 검출&회복으로 불리기도 한다.

정리하자면,
1. 예방은 데드락이 절대 발생하지 않도록 4가지 조건 중 하나를 막는 것이다.
2. 회피는 데드락이 발생할 가능성을 두지만, 이를 피할 수 있는 안정화 상태를 가려는 알고리즘을 채택하는 것이다.
3. 검출 및 회복은 데드락이 발생한 경우 처리하는 알고리즘을 선택하는 것이다.

6. 다중 자원과 교착 상태 검출

6.1 다중 자원과 사이클

[사진10]
위의 그림은 자원 R1은 두 프로세스가 동시에 사용할 수 있는 다중 자원이다. 마치 사이클이 생겨 교착 상태가 발생해보이지만 R1의 자원 수가 2개이므로 프로세스 P2가 자언 R1과 R2를 사용하여 작업을 마친 후 프로세스 P1이 자원 R2를 사용하여 작업을 마칠 수 있다. 따라서 교착 상태가 발생하지 않는다.

따라서 다중 자원의 경우 사이클이 있다고 해서 모두 교착 상태가 되는 것은 아니다. 다중 자원이 포함된 자원 할당 그래프에서는 대기 그래프를 그린 후 그래프 감소 방법을 이용하여 사이클을 찾는다.

6.2 대기 그래프와 그래프 감소

대기 그래프(wait for graph)는 자원 할당 그래프에서 프로세스와 프로세스 간에 기다리는 관계만 나타낸 그래프이다. 그리고 그래프 감소(graph reduction)는 대기 그래프에서 작업이 끝날 가능성이 있는 프로세스의 화살표와 관련 프로세스의 화살표를 연속적으로 지워가는 작업을 말한다. 여기서 작업이 끝날 가능성이 있는 프로세스란 기다리는 자원이 없는 프로세스를 가리킨다. 이렇게 다중 자원이 있는 대기 그래프에서 그래프 감소를 완료한 후에도 사이클이 남아 있다면 교착 상태가 발생한 것으로 판단한다.

<자원 할당 그래프>
다음의 그림에서 자원 R2는 두 프로세스가 동시에 사용할 수 있는 다중 자원으로 현재 프로세스 P2, P3에 할당되어 있다.

<대기 그래프>
다음은 위 그림의 대기 그래프로 화살표 위에 그래프 감소 순서를 표시했다. 대기 그래프는 프로세스가 가진 자원을 원하는 방향으로 그래프가 그어진다. 그령 P2, P3가 R2을 가지고 있으므로 P1은 P2,P3에 향하는 방향으로 간다. 그래프 감소 결과 사이클이 남아 있지 않으므로 교착 상태가 발생하지 않는다. 즉 프로세스 P2는 기다리는 자원이 없으므로 먼저 자원을 해제하고 P1이 R2를 갖고, P1이 해제되고 P4, P3 순서로 해제된다.

반면 다음과 같은 경우에는 데드락이 발생한다.

<자원 할당 그래프>

<대기 그래프>

위 그림은 작업이 끝날 수 없는, 즉 기다리는 자원이 없는, 프로세스가 없어 종료되는 프로세스가 없다. 따라서 그래프를 감소해도(위의 예제는 감소시킬 그래프가 없다) 여전히 사이클이 남아있어 교착 상태가 발생한다.

결론적으로 단일 자원만 있는 자원 할당 그래프에서는 사이클만으로 교착 상태 검출이 가능하지만 다중 자원을 사용할 대는 그래프 감소를 한 후 사이클이 남아 있는지 확인하여 교착 상태를 검출한다.