[운영체제] Deadlock (1) - Definition

다중 프로그래밍 환경에서는 여러 프로세스들이 한정된 자원을 사용하려고 서로 경쟁하는 상황이 발생할 수 있습니다. 마치 아래의 그림과 같은 상황을 말합니다. 이를 Deadlock (교착상태)이라고 합니다.

 

Deadlock

이번 글에서는 이 Deadlock에 대해서 상세하게 살펴보고자 합니다.

 

1. Deadlock의 정의

우선 시스템은 유한한 개수의 자원(resource)들로 이루어집니다. 여기서 자원이라 함은, 예를 들면 CPU나 파일들, 또는 입출력 장치들을 뜻하며, 프로세스들은 이런 자원들을 사용하고자 할 때 요청(Request)을 보내야하고, 사용을 완료하면 방출(Release)을 해 주어야 합니다. 요청을 했을 때 자원이 이미 다른 프로세스에 의해 사용되고 있는 등의 이유로 허용이 되지 않으면, 자원을 얻을 수 있을 때까지 대기해야 합니다. 요청 시에는 open(), malloc(), wait()등의 함수들이 사용되고, 방출 시에는 close(), free(), signal()등의 함수가 사용됩니다. 

 

Deadlock의 정의는 '한 세트 내의 모든 프로세스들이 동일한 세트 내의 다른 프로세스들로 인해 발생할 수 있는 이벤트를 기다리고 있는 경우'입니다. 즉 모든 프로세스들이 서로의 이벤트가 일어나기 만을 기다리고 있어서 결국 아무 프로세스도 실행되지 못하는 상태를 뜻합니다.

 

2. Deadlock의 특성

Deadlock 상황에서는 프로세스들은 실행을 끝낼 수도 없으며, 다른 자원들을 사용할 수도 없기 때문에 다른 작업을 수행하는 것도 불가능합니다. 이러한 Deadlock이 성립되는 조건에 대해 알아보도록 하겠습니다.

 

1. Mutual Exclusion (상호 배제): 하나의 자원은 한 번에 하나의 프로세스만 사용할 수 있어야 합니다.

2. Hold and Wait (점유하며 대기): 프로세스는 최소 하나의 자원을 가진 채, 현재 다른 프로세스에 의해 점유되어 있는 자원을 추가로 얻기 위해 반드시 대기하고 있어야 합니다.

3. No Preemption (비선점): 자원들을 선점할 수 없어야 합니다. 모든 자원들은 프로세스가 작업을 완료한 뒤 자발적으로 방출하는 경우에만 방출될 수 있습니다.

4. Circular Wait (순환 대기): n개의 프로세스가 있다면, 1번 프로세스는 2번 프로세스의 자원을 대기하고, 2번 프로세스는 3번 프로세스의 자원을 대기하며, n번 process는 1번 프로세스의 자원을 대기하는 형태를 띄어야 합니다.

 

위의 네 가지 조건이 모두 성립될 경우에만, 우리는 그 상황을 Deadlock이라고 부릅니다.

 

3. 자원 할당 그래프 (Resource Allocation Graph)

Deadlock은 이 자원 할당 그래프를 이용해 더 정확하게 표현할 수 있습니다. 이 자원 할당 그래프는 방향 그래프 (Directed Graph)로서, 일반적인 그래프와 같이 정점(vertex)들과 간선(edge)들로 이루어져 있습니다. 그리고 이 정점들은 시스템 내의 프로세스들의 집합과 시스템 내의 자원들의 집합, 두 가지 타입으로 구별됩니다.

 

또한 한 프로세스의 vertex에서 한 자원의 vertex로 향하는 edge는 요청 간선(Request Edge)라고 부르고, 반대로 자원 vertex에서 프로세스 vertex로 향하는 edge는 할당 간선(Assignment Edge)라고 합니다. 그래프는 다음과 같이 그릴 수 있습니다. 

 

Resource Allocation Graph - No Daedlock

이 그래프에서 cycle이 생기지 않는 다면 Deadlock 일 가능성은 0입니다. 하지만 아래의 그림과 같이 cycle이 존재한다면, 이를 Deadlock이 존재하는 상황일 가능성이 생깁니다. 

 

Resource Allocation Graph - Deadlock

위의 그림은 현재 Deadlock 상황이 맞습니다. 세 개의 프로세스가 모두 서로서로 자원을 방출하기를 기다리고 있기 때문입니다. 하지만 아래의 그림은 분명히 cycle이 존재하지만 Deadlock 상황은 아닙니다. 

 

Resource Allocation Graph - No Daedlock

위 그림에서 분명히 P1-R1-P3-R2-P1의 cycle이 존재합니다. 하지만 P4가 R2를 방출하여 주면 자연히 해결이 되기 때문에 Deadlock으로 볼 수 없습니다. 즉, 그래프에 cycle이 존재하지 않으면 절대 Deadlock이 발생할 수 없고, cycle이 존재한다면 Deadlock 상황일 수도 있고 아닐 수도 있습니다.

 

 

 

 

 

오늘은 Deadlock의 개념과 특성, 그리고 자원할당 그래프에 대해서 공부해 보았습니다. 다음 글에서는 어떻게 Deadlock을 처리할 수 있는지에 대해서부터 공부해 보도록 하겠습니다. 읽어주셔서 감사합니다.