Process Management - Deadlocks

이영민·2023년 3월 29일

데드락 운영체제

운영체제

목록 보기

5/11

대기중인 프로세스들이 다시는 그 상태를 변경 할 수 없으면 이런 상황을 Deadlicks(교착 상태)라고 한다.

1. System Model

시스템은 경쟁하는 프로세스들 사이에 분배되어야 할 유한한 수의 자원들로 구성된다. ( CPU, 파일, I/O 장치들..)
프로세스는 자원을 사용하기 위해 다음과 같은 순서를 따른다.
1. 요청: 자원을 요청한다. 만약 자원이 지금 다른 프로세스가 사용중이라면 대기한다.
2. 사용: 프로세스가 자원을 사용해 요청을 수행한다.
3. 방출: 프로세스가 자원을 방출한다.
이러한 시스템 모델에서 모든 프로세스가 다른 프로세스에 의해서만 발생될 수 있는 사건(예를 들어, 스스로 그 상태를 변경할 수 없는 경우)을 기다린다면 Deadlock(교착 상태)에 빠지게 된다.

2. Deadlock의 특징

다음과 같은 네가지 상황이 동시에 일어날 때 Deadlock이 발생할 가능성이 있다.

Mutual exclusion;
Hold - and - wait: 프로세스가 최소 하나의 자원을 점유한 채, 현재 다른 프로세스에 의해 점유된 자원을 얻기 위해 대기해야 한다.
No preemption: 프로세스가 어떤 자원을 사용하고 있는 것을 선점할 수 없다. 자원은 그 프로세스에 의해 자발적으로 방출되어야 한다.
Circular wait: p0,p1,…,pn의 대기하는 프로세스가 서로 점유한 자원을 대기할 때.

3. Resource Allocation Graph

정점V와 간선E로 구성된 그래프로 V에는 활성 프로세스의 집합인 P와 자원의 집합인 R로 구성된다.
P→R: 프로세스가 자원 R을 사용하기 위해 대기중이다.
R→P: 프로세스 P에 자원 R이 할당된 것을 의미한다.
아래의 자원 할당 그래프를 보면
- 프로세스 P1은 R2를 점유하며 R1 한개를 기다리며 대기중인 상태이다.
- 프로세스 P2는 R1과 R2를 점유하며 R3를 기다리며 대기중인 상태이다.
- 프로세스 P3은 자원 R3를 점유한 상태이다.
- 위의 상태는 P3의 자원할당이 끝나면 자원들이 프로세스에 순차적으로 할당된다.
- 만약 P3가 R2를 기다리며 대기중인 상태가 된다면 교착상태(Deadlock)이 된다.
자원할당 그래프가 Cycle로 닫힌 형태를 보이면 교착상태인 것을 알 수 있다.

사이클 형태이지만 P2 혹은 P4의 프로세스가 종료되면 다른 프로세스들에게 자원을 할당할 수 있으므로 교착상태가 아니다. 반면 오른쪽은 완전히 닫힌 형태이므로 교착상태이다.

4. Deadlocks 처리방법

A. Prevention

교착상태 예방은 교착상태가 되지 않도록 교착상태 발생 조건 네 가지 중 하나라도 발생하지 않게 방지하는 방법이다.
상호 배제(Mutual Exclusion) 조건 방지
1. 공유가 불가능한 자원에서 상호 배제가 일어난다.
2. 여러 프로세스가 자원에 대한 동시 접근을 보장받으면 상호 배제가 깨어지게 되어 교착상태를 예방할 수 있음.
3. 어떤 자원들은 근본적으로 공유가 불가능하기 때문에 교착상태를 예방하기 어렵다고 할 수 있음.(ex. 프린터)
점유 대기(Hold-and-wait) 조건 방지
1. 점유 대기 조건을 부정하기 위해서는 프로세스가 작업을 수행하기 전에 필요한 자원들을 모두 요청하고 획득해야한다.
2. 프로세스 하나를 실행하는데 필요한 모든 자원을 먼저 다 할당하고 끝나면 다른 프로세스에 자원을 할당한다.
3. 프로세스가 자원을 전혀 갖고 있지 않을 때만 자원 요청을 허용해주는 방법도 있다.
4. 자원의 이용률이 낮아지고 기아 상태가 발생할 수 있다.
비선점(No preemption) 조건 방지
1. 서로 모든 자원에 대한 선점을 허용한다.
2. 프로세스가 할당받을 수 없는 자원을 요청하는 경우, 기존에 가지고 있던 자원을 모두 반납하고 새 자원과 이전 자원을 얻기 위해 대기하도록 한다.
순환 대기(Circular wait) 조건 방지
1. 자원에 고유한 번호를 할당하고 번호 순서대로 자원을 요구하도록 한다.

B. Avoidance

교착상태 회피는 프로세스가 일생동안 요구하고 사용할 자원에 대한 부가적인 정보를 미리 제공할 것을 요구하고 이러한 정보를 바탕으로 운영체제는 어떤 요청에 대해 프로세스가 기다려야할지 말지를 결정한다.
자원 요청이 있을 때마다 교착 상태 회피 알고리즘을 사용하는 것은 상당한 오버헤드이다.
안정&불안정 상태
- 불안정 상태일 때 데드락이 무조건 발생하는 것은 아니지만, 발생할 확률이 있으므로 교착상태 회피 알고리즘은 불안정 상태를 허락하지 않는다.
알고리즘
- 자원할당 그래프 알고리즘: 자원 할당 그래프에서 어떤 프로세스가 요청하는 자원을 대기한다면 교착상태가 일어나는지 안일어나는지 판단하는 알고리즘이다.
- 은행원 알고리즘: 프로세스 시작 시 자신이 필요한 각 자원의 최대 개수를 선언하고 각 프로세스에서 자원요청이 있을 때 시스템이 안정 상태로 유지되는 경우에만 자원을 할당한다. 만약 불안정 상태가 된다면 대기한다.