[운영체제] 교착 상태(Deadlock) 해결 방법

이 글은 혼자 공부하는 컴퓨터 구조 + 운영체제 (저자 : 강민철)의 책과 유튜브 영상을 참고하여 개인적으로 정리하는 글임을 알립니다.

---

아래는 모두 프로세스를 예로 들었지만 스레드에서도 똑같이 적용된다.

 

교착 상태가 발생할 조건에는 아래와 같이 네 가지가 있다.

아래의 조건 중 하나라도 만족하지 않는다면 교착 상태가 발생하지 않지만, 아래 조건이 모두 만족될 때 교착 상태가 발생할 가능성이 생긴다.

• 상호 배제(mutual exclusion) : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
• 점유와 대기(hold and wait) : 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
• 비선점(nonpreemptive) : 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태
• 원형 대기(circular wait) : 자원 할당 그래프를 그렸을 때, 프로세스들이 원의 형태로 자원을 대기하는 상태

 

운영체제는 아래의 방법으로 교착 상태를 해결한다.

• 예방 : 애초에 교착 상태가 일어나지 않도록 교착 상태 발생 조건에 부합하지 않게 자원을 분배
• 회피 : 교착 상태가 발생하지 않을 정도로 조금씩 자원을 할당하다가 교착 상태의 위험이 있으면 자원을 할당을 멈춤
• 검출 후 회복 : 자원을 제약 없이 할당하다가 교착 상태가 검출되면, 교착 상태를 회복

 

---

 

교착 상태 예방

애초에 교착 상태가 발생하지 않도록, 교착 상태 발생조건(상호배제, 점유와 대기, 비선점, 원형 대기) 중 하나를 없애는 것이다.

 

상호 배제를 없애기

• 모든 자원을 공유 가능하게 만든다
• 상호 배제를 없애면 동기화를 할 때 큰 문제가 될 수 있다.
• 현실적으로 불가능

 

점유와 대기를 없애기

• 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분
• 당장 자원이 필요해도 기다릴 수밖에 없는 프로세스와 사용되지 않으면서 오랫동안 할당되는 자원을 다수 양산하기 때문에 자원의 활용률이 낮아진다.
• 자원을 많이 필요로 하는 프로세스가 무한정 기다리게 되므로 기아 현상을 야기할 우려가 있다.

 

비선점 조건을 없애기(선점형으로 변환)

• 선점이 가능한 자원(CPU 등)에 한에 효과적
• 선점이 불가능한 자원(프린터 등)은 불가능
• 범용성이 떨어지는 방법

 

원형 대기 조건을 없애기

모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하면 원형 대기는 발생하지 않는다.

• 앞선 세 방식에 비해서 비교적 현실적이다.
• 컴퓨터 시스템 내에 존재하는 수많은 자원에 번호를 붙이는 것이 쉽지 않다.
• 각 자원에 어떤 번호를 붙이는지에 따라 특정 자원의 활용률이 달라진다.

 

식사하는 철학자 문제

위 그림은 교착 상태의 대표적인 예시인 식사하는 철학자 문제이다.

식사하는 철학자 문제에서 모든 포크에 1번부터 5번까지 번호를 붙이고, 철학자들로 하여금 번호가 낮은 포크에서 높은 포크 순으로 집어 들게 한다면 원형 대기는 발생하지 않는다.

왜냐하면 5번 포크를 집어들고 1번 포크를 집어들 수 없기 때문이다.

 

이는 마치 철학자들이 원형 식탁이 아닌 사각형 식탁에서 일렬로 앉아 식사를 하는 상황과 유사하다.

 

---

 

교착 상태 회피

• 교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주
• 교착 상태가 발생하지 않을 만큼만 자원을 할당

 

교착 상태 회피에 대해 깊이 알려면 아래의 용어를 알아야 한다.

• 안전 순서열(safe seqnence) : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
• 안전 상태(safe state) : 교착 상태 없이 프로세스가 자원을 할당받고 종료될 수 있는 상태, 안전 순서열이 있는 상태
• 불안전 상태(unsafe state) : 교착 상태가 발생할 수도 있는 상태, 안전 순서열이 없는 상태

 

예를 들어 A, B, C 프로세스가 동시에 운영체제에 자원을 요청한 상황에서 B -> A -> C 순서로 자원을 할당하면 교착 상태가 발생하지 않는다고 가정하면 B -> A -> C가 안전 순서열이 된다.

안전 순서열이 있는 상태를 안전 상태이고, 없는 상태가 불완전 상태이다.

 

운영체제는 교착 상태를 회피하기 위해 시스템 상태가 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당한다.

즉, 교착 상태 회피 방식은 항시 안전 상태를 유지하도록 자원을 할당하는 방식이다.

 

교착 상태 회피 예제

• 컴퓨터 시스템에 총 12개의 자원이 있다고 가정
• 프로세스 P1, P2, P3가 각각 5개, 2개, 2개의 자원을 할당받아 실행 중이라 가정
• 프로세스 P1, P2, P3는 각각 최대 10개, 4개, 9개 자원을 요구할 수 있다고 가정

프로세스와 스레드는 우선 자원을 운영체제에게 요청하고, 운영체제로부터 자원을 할당받아 사용하고, 자원 사용이 끝나면 자원을 반환한다.

 

안전 상태

 

이 상태는 안전 상태이다. P2 -> P1 -> P3이라는 안전 순서열이 있기 때문이다.

 

왜냐하면 각 프로세스들이 최대로 자원을 요구한 최악의 상황이라면 시나리오는 아래와 같다.

1. 이미 자원 2개를 점유하고 있던 P2는 남은 자원에서 2개를 추가적으로 할당 받아 작업을 끝내고 쓰던 모든 자원을 반환한다.
2. 이미 자원을 5개 점유하고 있던 P1은 남은 자원에서 5개를 추가적으로 할당 받아 작업을 끝내고 쓰던 모든 자원을 반환한다.
3. 이미 자원을 2개 점유하고 있던 P3는 남은 자원에서 7개를 추가적으로 할당 받아 작업을 끝내고 쓰던 모든 자원을 반환한다.

---

불안전 상태

이번에는 P3가 2개의 자원을 쓰고있는 상태가 아니라 3개의 자원을 쓰고 있는 상태라 가정

이는 불안전 상태이다. 즉, 안전 순서열이 없으므로 교착 상태가 일어날 수 있다.

 

예를 들어, 최악의 상황인 각 프로세스가 최대로 자원을 요구하면 시나리오는 아래와 같다.

1. 이미 자원 2개를 점유하고 있던 P2는 남은 자원에서 2개를 추가적으로 할당받아 작업을 끝내고 쓰던 모든 자원을 반환한다.
2. 이미 자원을 5개 점유하고 있던 P1은 남은 자원에서 5개를 추가적으로 할당받고 싶지만, 남은 자원이 4개이므로 작업을 완료할 수 없게 된다.
3. 이미 자원을 3개 점유하고 있던 P3은 남은 자원에서 6개를 추가적으로 할당받고 싶지만, 남은 자원이 4개이므로 작업을 완료할 수 없게 된다.
4. 교착 상태에 빠진다.

 

---

 

교착 상태 검출 후 회복

• 교착 상태의 발생을 인정하고 사후에 조치하는 방식
• 프로세스가 자원을 요구하면 일단 할당, 교착 상태가 검출되면 회복
• 회복에는 선점을 통한 회복과 프로세스 강제 종료를 통한 회복이 있다.

 

선점을 통한 회복

• 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
• 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에 할당

 

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

프로세스 강제 종료를 통한 회복에는 아래의 두 가지 방법이 있다.

• 교착 상태에 놓인 프로세스를 모두 강제 종료하는 방법(작업 내역을 잃을 위험)
• 교착 상태가 해결될 때까지 한 프로세스씩 강제 종료(교착 상태가 해결되었는지 확인하는 과정에서 오버헤드 발생)