교착 상태 (Deadlock) 해결법 — 예방, 회피, 검출 후 회복

앞선 글에서는 여러 프로세스가 서로 점유한 자원을 기다리며 더 이상 진행하지 못하는 교착 상태(Deadlock)를 살펴보았다.

 

교착 상태를 처리하는 방법은 크게 세 가지로 나눌 수 있다.

교착 상태 처리 방법
├─ 예방
│  └─ 발생 조건 자체를 제거
├─ 회피
│  └─ 안전한 경우에만 자원 할당
└─ 검출 후 회복
   └─ 일단 허용한 뒤 발생하면 처리

 

세 방식은 교착 상태를 바라보는 관점이 다르다.

• 예방: 교착 상태가 생길 조건을 미리 없앤다.
• 회피: 현재 상태를 계산하며 조심스럽게 자원을 할당한다.
• 검출 후 회복: 교착 상태가 발생할 수 있음을 인정하고 사후에 해결한다.

이번 글에서는 각 방식의 기본 원리와 차이를 정리한다.

 

---

1. 교착 상태 예방

교착 상태 예방(Deadlock Prevention)은 교착 상태의 네 가지 발생 조건 중 하나 이상이 성립하지 않도록 만드는 방식이다.

교착 상태가 발생하기 위해서는 다음 조건이 모두 만족되어야 한다.

1. 상호 배제
2. 점유와 대기
3. 비선점
4. 원형 대기

따라서 이 중 하나라도 제거하면 교착 상태를 예방할 수 있다.

 

---

[1] 상호 배제 조건 제거

상호 배제란 한 프로세스가 사용 중인 자원을 다른 프로세스가 동시에 사용할 수 없는 상태다.

이 조건을 제거하려면 모든 자원을 여러 프로세스가 동시에 공유할 수 있게 만들면 된다

 

하지만 현실적으로 모든 자원을 공유 가능하게 만드는 것은 어렵다.

예를 들어 프린터 한 대에 여러 프로세스가 동시에 출력 데이터를 보내면 결과가 뒤섞일 수 있다. 파일이나 공유 변수 역시 동시에 수정하면 데이터의 일관성이 깨질 수 있다.

따라서 상호 배제 조건을 완전히 제거하는 방법은 이론적으로는 가능하지만, 대부분의 실제 시스템에서는 적용하기 어렵다.

 

---

[2] 점유와 대기 조건 제거

점유와 대기(Hold and Wait)란 프로세스가 이미 자원을 하나 이상 점유한 상태에서 다른 자원을 추가로 기다리는 것이다.

이를 제거하는 대표적인 방법은 다음과 같다.

프로세스에 필요한 자원을 한꺼번에 모두 할당하거나, 하나도 할당하지 않는다.

 

예를 들어 프로세스가 R1, R2, R3을 모두 필요로 한다면 세 자원을 한 번에 얻을 수 있을 때만 실행한다.

하나라도 사용할 수 없다면 어떤 자원도 점유하지 않은 채 기다린다.

 

식사하는 철학자 문제에 비유하면 다음과 같다.

포크 두 개를 모두 집을 수 없다면, 이미 집은 포크도 내려놓고 기다린다.

 

이렇게 하면 포크 하나를 점유한 채 다른 포크를 기다리는 상황을 막을 수 있다.

 

다만 단점도 있다.

• 필요한 자원을 모두 모을 때까지 오래 기다릴 수 있다.
• 이미 사용할 수 있는 자원도 놀게 된다.
• 전체적인 자원 활용률이 낮아질 수 있다.

 

---

[3] 비선점 조건 제거

비선점(Nonpreemption)이란 다른 프로세스가 사용 중인 자원을 강제로 빼앗을 수 없는 상태다.

이 조건을 제거하려면 필요할 때 운영체제가 자원을 강제로 회수할 수 있도록 하면 된다.

대표적으로 CPU는 선점 가능한 자원이다.

프로세스 A가 CPU 사용 중
        ↓
운영체제가 CPU 회수
        ↓
프로세스 B에 CPU 할당

 

운영체제는 타이머 인터럽트 등을 통해 실행 중인 프로세스에서 CPU를 회수하고 다른 프로세스에 할당할 수 있다.

그러나 모든 자원이 선점 가능한 것은 아니다.

예를 들어 프린터가 문서를 출력하는 중간에 강제로 회수되면 출력 결과가 망가질 수 있다. 파일 쓰기나 장치 제어 역시 중간 상태에서 자원을 빼앗기 어려울 수 있다.

따라서 비선점 조건 제거는 상태를 저장하고 나중에 안전하게 다시 시작할 수 있는 자원에 주로 적용할 수 있다.

 

 

---

[4] 원형 대기 조건 제거

원형 대기(Circular Wait)란 프로세스들이 원형으로 서로의 자원을 기다리는 상태다.

P1 → P2의 자원 대기
P2 → P3의 자원 대기
P3 → P1의 자원 대기

 

이를 제거하는 대표적인 방법은 모든 자원에 번호를 붙이고, 항상 정해진 순서대로만 요청하게 만드는 것이다.

 

예를 들어 다음과 같이 번호를 부여한다.

R1 < R2 < R3 < R4

 

모든 프로세스는 반드시 낮은 번호의 자원부터 높은 번호의 자원 순서로 요청해야 한다.

가능
R1 획득 → R3 요청

불가능
R3 획득 → R1 요청

 

 

모든 프로세스가 동일한 방향으로만 자원을 요청하므로 원형 대기가 만들어지지 않는다.

식사하는 철학자 문제에서는 모든 포크에 번호를 붙이고, 각 철학자가 항상 낮은 번호의 포크부터 집도록 만들 수 있다.

그럼 첫 철학자와 마지막 철학자가 같은 포크를 먼저 필요로 하게 되면서 획득하지 못한 한 명의 철학자는 기다리게 된다.

 

다만 다음과 같은 단점이 있다.

• 모든 자원에 적절한 순서를 부여하기 어렵다.
• 시스템에 자원이 추가되거나 관계가 바뀌면 순서를 다시 설계해야 할 수 있다.
• 번호를 어떻게 정하느냐에 따라 병렬성과 자원 활용률이 달라질 수 있다.

 

---

교착 상태 예방의 특징

교착 상태 예방은 발생 조건을 사전에 제거하므로 교착 상태를 확실히 막을 수 있다.

하지만 조건을 강하게 제한하는 만큼 다음과 같은 부작용이 생길 수 있다.

장점
└─ 교착 상태 발생을 구조적으로 차단

단점
├─ 자원 활용률 감소
├─ 불필요한 대기 증가
└─ 시스템의 동시성 저하

 

---

2. 교착 상태 회피

교착 상태 회피(Deadlock Avoidance)는 자원을 무조건 할당하지 않고, 할당 이후에도 시스템이 안전한지를 계산한 뒤 조심조심 자원을 배분하는 방식이다.

지금 이 자원을 할당해도 모든 프로세스가 언젠가 종료할 수 있는가?

 

안전 순서열

안전 순서열(Safe Sequence)은 모든 프로세스가 교착 상태 없이 자원을 할당받고 종료할 수 있는 실행 순서다.

예를 들어 다음과 같은 순서로 프로세스가 종료될 수 있다면:

P2 → P1 → P3

 

이 순서가 안전 순서열이다.

먼저 종료한 프로세스는 사용하던 자원을 반납하고, 그 자원을 다음 프로세스가 사용할 수 있다.

 

---

안전 상태

안전 상태(Safe State)란 하나 이상의 안전 순서열이 존재하는 상태다.

현재 남은 자원으로 어떤 프로세스가 종료 가능
        ↓
종료 후 자원 반납
        ↓
다음 프로세스 종료 가능
        ↓
결국 모든 프로세스 종료 가능

 

안전 상태에서는 적절한 순서로 자원을 할당하면 모든 프로세스가 교착 상태 없이 종료될 수 있다.

 

---

불안전 상태

불안전 상태(Unsafe State)란 안전 순서열을 찾을 수 없는 상태다.

불안전 상태가 곧바로 교착 상태라는 뜻은 아니다.

안전 상태 → 교착 상태 없이 종료 가능

불안전 상태 → 교착 상태가 발생할 가능성이 있음

교착 상태 → 이미 서로 기다리며 진행 불가능

 

불안전 상태에서는 이후 프로세스의 자원 요청에 따라 교착 상태로 이어질 수 있다.

따라서 운영체제는 안전 상태에서 불안전 상태로 이동하게 만드는 자원 할당을 거부하거나 미룬다.

 

---

예시 1: 안전 상태

전체 자원이 12개이고, 현재 프로세스들이 9개를 사용 중이라고 가정하자.

전체 자원: 12
현재 할당된 자원: 9
남은 자원: 3

 

프로세스	최대 요구량	현재 사용량	추가 필요량
P1	10	5	5
P2	4	2	2
P3	9	2	7

P2는 추가로 2개만 있으면 작업을 끝낼 수 있다.

P2가 종료하면 시스템이 사용할 수 있는 자원은 총 5개가 된다.

기존 남은 자원 3
- P2에 추가 할당 2
+ P2의 전체 사용량 4 반납
= 사용 가능 자원 5

 

이제 P1은 추가로 필요한 5개를 받을 수 있다.

P1이 종료하면 사용하던 자원 10개를 반납하고, 마지막으로 P3도 필요한 자원을 받을 수 있다.

P2 → P1 → P3

 

따라서 안전 순서열이 존재하며, 현재 상태는 안전 상태다.

 

---

예시 2: 불안전 상태

이번에는 현재 프로세스들이 자원 10개를 사용 중이라고 가정하자.

전체 자원: 12
현재 할당된 자원: 10
남은 자원: 2

 

프로세스	최대 요구량	현재 사용량	추가 필요량
P1	10	5	5
P2	4	2	2
P3	9	3	6

현재 남은 자원 2개로는 P2를 먼저 완료할 수 있다.

P2가 종료하고 자원을 반납하면 사용 가능한 자원은 4개가 된다.

기존 남은 자원 2
- P2에 추가 할당 2
+ P2의 전체 사용량 4 반납
= 사용 가능 자원 4

 

하지만 이후에는:

• P1이 추가로 5개 필요하다.
• P3가 추가로 6개 필요하다.
• 사용할 수 있는 자원은 4개뿐이다.

따라서 P1과 P3 중 어떤 프로세스도 완료할 수 없다.

안전 순서열을 만들 수 없으므로 이 상태는 불안전 상태다.

아직 반드시 교착 상태가 발생했다고 단정할 수는 없지만, 이후 요청에 따라 교착 상태가 발생할 가능성이 있다.

 

---

은행원 알고리즘

교착 상태 회피의 대표적인 방법이 은행원 알고리즘(Banker’s Algorithm)이다.

은행이 모든 고객에게 무조건 대출해 주지 않고, 남은 자금으로 모든 고객의 최대 요구를 감당할 수 있는지 확인한 뒤 대출하는 모습과 비슷해 붙은 이름이다.

운영체제는 자원을 할당하기 전에 가상으로 계산한다.

자원 할당 요청
        ↓
일단 할당했다고 가정
        ↓
안전 순서열이 존재하는가?
        ├─ 존재함 → 실제로 할당
        └─ 없음   → 할당 보류

 

즉, 시스템이 계속 안전 상태에서 안전 상태로 이동하는 경우에만 자원을 할당한다.

 

다만 은행원 알고리즘을 사용하려면 각 프로세스가 앞으로 요구할 수 있는 최대 자원량을 미리 알아야 한다.

실제 프로그램에서는 미래의 자원 요구량을 정확히 알기 어려운 경우가 많아 모든 환경에 적용하기는 어렵다.

 

---

3. 교착 상태 검출 후 회복

교착 상태 검출 후 회복(Deadlock Detection and Recovery)은 교착 상태의 발생 가능성을 처음부터 제한하지 않는다.

프로세스가 자원을 요청하면 우선 할당하고, 주기적으로 시스템 상태를 검사해 교착 상태가 발견되면 이를 해소한다.

자원 요청
    ↓
일단 할당
    ↓
시스템 상태 검사
    ↓
교착 상태 발견
    ↓
회복 작업 수행

 

예방이나 회피보다 자원을 자유롭게 사용할 수 있지만, 교착 상태가 실제로 발생하면 작업 손실이나 복구 비용이 발생할 수 있다.

 

[1] 자원 선점을 통한 회복

교착 상태에 포함된 프로세스 중 하나로부터 자원을 강제로 회수해 다른 프로세스에 할당하는 방식이다.

P1과 P2가 교착 상태
        ↓
P2의 자원 일부를 강제로 회수
        ↓
P1에 자원 할당
        ↓
P1 작업 완료 및 자원 반납
        ↓
P2 작업 재개

 

한 프로세스에 자원을 몰아주어 먼저 종료시킨 뒤, 반납된 자원을 다른 프로세스가 사용하게 만드는 방식이라고 볼 수 있다.

 

다만 자원을 빼앗긴 프로세스는 이전 상태로 되돌아가 다시 실행해야 할 수 있다.

또한 어떤 프로세스의 자원을 회수할지 결정하는 과정도 필요하다.

• 지금까지 수행한 작업량
• 보유한 자원의 개수
• 프로세스 우선순위
• 다시 실행하는 데 필요한 비용

등을 고려해야 한다.

 

[2] 프로세스 강제 종료를 통한 회복

교착 상태에 포함된 프로세스를 종료해 해당 프로세스가 사용하던 자원을 회수하는 방식이다.

 

[2-1] 관련 프로세스를 모두 종료

교착 상태에 포함된 모든 프로세스를 한꺼번에 종료한다.

교착 상태를 확실하게 해결할 수 있지만, 진행 중이던 작업 결과를 모두 잃을 수 있다.

 

[2-2] 한 프로세스씩 종료

교착 상태가 해결될 때까지 프로세스를 하나씩 종료한다.

불필요한 프로세스 종료를 줄일 수 있지만, 프로세스를 하나 종료할 때마다 교착 상태를 다시 검사해야 하므로 오버헤드가 발생한다.

프로세스 하나 종료
        ↓
교착 상태가 해결되었는지 검사
        ├─ 해결됨 → 종료
        └─ 유지됨 → 다른 프로세스 추가 종료

 

---

검출 후 회복 방식의 특징

장점
├─ 평상시 자원 할당 제한이 적음
└─ 자원 활용률을 높일 수 있음

단점
├─ 교착 상태 검출 비용
├─ 작업 결과 손실 가능
├─ 강제 종료 및 롤백 비용
└─ 회복 대상 선택 필요

 

교착 상태가 자주 발생하지 않고, 발생하더라도 복구 비용을 감당할 수 있는 시스템에서 고려할 수 있다.

 

---

교착 상태를 무시하는 방법

모든 운영체제가 항상 교착 상태를 적극적으로 예방하거나 회피하는 것은 아니다.

교착 상태가 매우 드물게 발생하고, 이를 완벽하게 방지하는 비용이 더 크다고 판단되면 교착 상태를 특별히 처리하지 않을 수도 있다.

이를 흔히 타조 알고리즘(Ostrich Algorithm)이라고 부른다.

위험이 다가왔을 때 타조가 모래에 머리를 묻고 모르는 척한다는 비유에서 나온 표현이다.

교착 상태가 드물게 발생함
        ↓
예방·회피 비용이 더 큼
        ↓
특별한 처리 없이 무시
        ↓
문제가 발생하면 재시작 등으로 대응

 

 

 

---

세 가지 방법 비교

	교착 상태 예방	교착 상태 회피	검출 후 회복
기본 관점	발생 조건을 없앤다	안전할 때만 할당한다	발생을 허용하고 나중에 처리한다
처리 시점	자원 요청 이전	자원 할당 시점	교착 상태 발생 이후
필요한 정보	교착 상태 발생 조건	최대 요구량과 현재 자원 상태	현재 할당 및 대기 상태
자원 활용률	비교적 낮을 수 있음	예방보다 유연함	비교적 높을 수 있음
주요 비용	동시성 제한	안전 상태 계산	검출 및 복구 비용
대표 방법	자원 순서 부여	은행원 알고리즘	자원 선점, 프로세스 종료