Deadlock(교착상태)

1. 교착 상태의 정의

2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 가다리며 작업을 더 이상 진행하지 못하는 상태를 교착 상태(deadlock)라고 한다.

2. 교착 상태의 발생

컴퓨터 시스템에서 교착 상태는 시스템 자원, 공유 변수(또는 파일), 응용 프로그램 등을 사용할 때 발생할 수 있다.

2.1 시스템 자원

교착 상태는 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생한다. 어떤 프로세스가 임계구역으로 보호되는 프린터, 스캐너, CD 레코더 등 동시에 같이 사용할 수 없는 시스템 자원을 할당받은 후 양보하지 않는 경우를 예로 들 수 있다.

가령 프로세스 P1이 프린터를 할당받은 후, CD 레코더를 기다리고 프로세스 P2는 CD 레코더를 할당받은 후 프린터를 기다리면 교착 상태가 발생한다.

2.2 공유 변수

교착 상태는 공유 변수를 사용할 때도 발생한다. 임계구역 문제를 해결하기 위한 코드로, 무한 대기를 막지 못해 교착 상태가 발생하는 경우이다. 프로세스 P1이 lock1을 true로 만들고, P2가 lock2를 true로 만든다면, P1으로 돌아왔을 떄 while문이 실행되어 무한 반복된다. P2도 while이 실행되어 무한히 반복된다.

P1과 P2 둘 다 임계구역에 들어가지 못하는 교착 상태가 발생하는 것이다. 이처럼 한 변수를 할당 받은 상태에서 다른 변수를 기다리면 교착 상태가 발생한다.

2.3 응용 프로그램

데이터베이스 같은 응용 프로그램에서도 교착 상태가 발생한다. 여러 프로세스가 데이터베이스에 저장된 데이터를 사용할 때는 데이터의 일관성을 유지해야 한다. 또한, 데이터의 일관성을 유지하기 위해 lock을 사용해야하는데 이 떄 교착 상태가 발생할 수 있다.

3. 자원 할당 그래프(resource allocation graph)

자원 할당 그래프는 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리는 지를 나타내는 방향성이 있는 그래프이다.

프로세스는 원으로, 자원은 사각형이며 자원에서 프로세스로 가는 화살표는 프로세스가 자원을 할당받은 것이며, 프로세스가 자원을 향하는 화살표는 프로세스가 자원을 원한다는 것(기다리는 다는 것)이다.

여러 프로세스가 하나의 자원을 동시에 사용하면 이를 다중 자원(mutiple resource)이라고 부른다. 다중 자원은 수용할 수 있는 프로세스 수를 사각형 안에 동그라미로 표현한다.

이를 이용하여 유명한 문제인 식사하는 철학자 문제를 보도록 하자

3.1 식사하는 철학자 문제

철학자 4명이 둥그런 식탁에 둘러앉아 식사를 한다고 하자, 이때 왼쪽에 있는 포크를 잡은 뒤 오른쪽에 있는 포크를 잡아야 식사가 가능하다는 조건이 있다.

다음과 같이 철학자들은 프로세스와 같고, 포크는 자원과 같다. 따라서 철학자들은 왼손을 들어 포크를 집으면 자원을 할당받지만 오른족의 포크를 할당받기를 기다리게 된다. 그러나 오른쪽 포크는 이미 선점되었고, 서로가 서로의 자원을 요구하지만 자신의 자원을 내놓지않아 교착상태(deadlock)에 걸린다.

철학자 문제에서 교착 상태가 발생하는 조건을 정리하면 다음과 같다.

1. 철학자들은 서로 포크를 공유할 수 없다. -> 자원을 공유하지 못하면 교착 상태가 발생한다.
2. 각 철학자들은 다른 포크를 빼앗을 수 없다. -> 자원을 빼앗을 수 없으면 자원을 놓을 때까지 기다려야 하므로 교착 상태가 발생한다.
3. 각 철학자들은 왼쪽 포크를 잡은 채 오른쪽 포크를 기다린다. -> 자원 하나를 잡은 상태에서 다른 자원을 기다리기 때문에 교착 상태가 발생한다.
4. 자원 할당 그래프가 원형이다. -> 자원을 요구하는 방향이 원을 이루면 양보를 하지 않기 때문에 교착 상태가 발생한다.

이를 이용하여 교착 상태(deadlock)의 필요 조건을 정리해보자

4. 교착 상태 필요조건

철학자 문제를 보았듯이 교착 상태는 여러 가지 조건에 의해 발생한다. 교착 상태는 상호 배제(mutual exclusion), 비선점(non-preemption), 점유 대기(hold and wait), 원형 대기(circular wait)를 모두 충족해야 발생한다.

1. 상호 배제(mutual exclution): 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다. 배타적인 자원은 임계구역으로 보호되기 때문에 다른 프로세스가 동시에 사용할 수 없다. 따라서 배타적인 자원을 사용하면 교착 상태가 발생한다.

2. 비선점(non-preemption): 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다.

3. 점유와 대기(hold and wait): 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다.

4. 원형 대기(circular wait): 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다. 프로세스가 특정 자원에 대해 점유와 대기를 한다고 해서 모두 교착 상태에 빠지는 것은 아니다. 점유와 대기를 하는 프로세스들이 서로 방행하는 방향이 원을 이루면 프로세스들이 서로 양보하지 않기 때문에 교착 상태에 빠진다.

교착 상태 필요조건: 교착상태는 상호 배제 , 비선점, 점유와 대기, 원형 대기를 모두 충족해야 발생하고, 이 중 단 하나라도 충족하지 않으면 발생하지 않는다. 따라서 이 4가지를 교착 상태 필요조건이라고 한다.

상호 배제와 비선점 조건은 자원이 어떤 특징을 가지는 지를 나타내고, 점유와 대기, 원형 대기 조건은 프로세스가 어떤 행위를 하고 있는 지를 나타낸다.

4.1 식사하는 철학자 문제와 교착 상태 필요조건

1. 상호배제 : 포크는 한 사람이 사용하면 다른 사람이 사용할 수 없는 배타적인 자원이다. 따라서 상호 배제 조건을 만족한다.
2. 비선점 : 옆 사람의 포크를 강제로 빼앗을 수 없으므로 상호 배제가 성립되지 않는다.

상호 배제와 비선점 조건은 임계구역과 관련이 있다. 임계구역을 보호하기 위해 잠금 장치를 사용하면 상호 배제와 비선점 조건이 보장되기 때문에 교착 상태가 발생할 수 있다. 그런데 임계구역으로 보호되는 모든 자원이 교착 상태를 유발하는 것은 아니다. 임계구역의 자원을 사용하는 프로세스들이 점유와 대기, 원형 대기 상황에 처하면 교착 상태가 발생한다.

3. 점유와 대기 : 한 철학자가 포크를 들고, 다른 철학자의 포크를 얻을 것을 대기하고 있으므로 점유와 대기를 성립한다.
4. 원형 대기 : 식하는 철학자들은 서로가 서로의 포크를 원한다. 그 끝이 없는 원형 구조를 이루고 있기 때문에 원형 대기조건을 만족한다.

따라서, 식사하는 철학자 문제는 교착 상태의 필수 조건인 4가지를 만족하였으므로 교착 상태에 빠진 것이 맞다.

5. 아사(starvation)현상과 교착 상태(deadlock)

교착 상태와 아사 현상은 아니다. 아사 현상은 정책상 잘못이나 오류로 인해 특정 프로세스의 작업이 오래동안 이루어지지 않는 것을 말한다.

이전에 말한 최단 작업 우선 스케줄링 알고리즘(SJF)에서 작업 시간이 긴 프로세스가 작업 시간이 짧은 프로세스 때문에 작업이 진행되지 못하는 경우를 아사 현상이라고 했다. 아사 현상은 몇 번 이상 양보했다면 더 이상 양보하지 않도록 조정하는 aging 기법으로 해결할 수 있다. 즉, 몇 번 양보를 했냐가 우선순위가 더 높게 산정되는 것이다.

교착 상태(deadlock)은 아사 현상과 달리 정책상 잘못이나 오류가 없어도 자연적으로 발생한다. 따라서 교착 상태는 aging기법으로도 해결할 수 없고 정책을 바꾼다고 해서 막을 수도 없다. 교착 상태는 아사 현상보다 처리하기가 복잡하기 때문에 이를 해결하기 위한 다양한 방법이 제시되었다.