[운영체제] 교착 상태 해결 방법: 예방, 회피, 검출 후 회복

교착 상태 해결 방법

이전 글에서 교착 상태가 발생하는 조건을 살펴보았다.

교착 상태가 발생하려면 다음 네 가지 조건이 모두 만족되어야 한다.

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

 

따라서 교착 상태를 해결하는 방법은 크게 네 가지로 나눌 수 있다.

교착 상태 예방
교착 상태 회피
교착 상태 검출 후 회복
교착 상태 무시

 

교착 상태 예방

교착 상태 예방은 애초에 교착 상태가 발생하지 않도록 만드는 방식이다.

교착 상태는 네 가지 조건이 모두 만족될 때 발생한다.
따라서 이 중 하나라도 만족하지 않게 만들면 교착 상태를 막을 수 있다.

 

다만 교착 상태 예방은 교착 상태가 발생하지 않음을 보장할 수 있지만, 그만큼 부작용이 따를 수 있다.

1. 상호 배제 없애기

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

이 조건을 없애려면 모든 자원을 여러 프로세스가 동시에 공유할 수 있게 만들어야 한다.

이론적으로는 가능해 보이지만, 현실적으로는 어렵다.

 

예를 들어 프린터 같은 자원을 생각해보자.
여러 프로세스가 동시에 하나의 프린터를 사용하면 출력 결과가 뒤섞일 수 있다.

또한 어떤 파일에 여러 프로세스가 동시에 쓰기를 수행하면 데이터가 깨질 수 있다.

 

즉, 현실의 많은 자원은 한 번에 하나의 프로세스만 사용해야 한다.
그래서 상호 배제를 없애는 방식은 현실적으로 적용하기 어렵다.

2. 점유와 대기 없애기

점유와 대기는 프로세스가 어떤 자원을 이미 가지고 있으면서, 다른 자원을 기다리는 상태이다.

이 조건을 없애려면 프로세스가 자원을 가진 채로 다른 자원을 기다리지 못하게 하면 된다.

대표적인 방식은 다음과 같다.

프로세스가 실행 전에 필요한 자원을 모두 할당받게 한다.
필요한 자원을 모두 받을 수 없다면 아예 아무 자원도 할당하지 않는다.

 

특정 프로세스에 필요한 자원을 한 번에 모두 주거나, 하나도 주지 않는 방식이다.

이렇게 하면 자원을 가진 상태에서 다른 자원을 기다리는 상황이 생기지 않는다.

 

하지만 단점이 있다.

프로세스가 당장 사용하지 않는 자원까지 미리 할당받을 수 있기 때문에 자원의 활용률이 낮아질 수 있다.

 

예를 들어 어떤 프로세스가 나중에 프린터를 사용할 예정이라고 해서 처음부터 프린터를 점유하고 있으면, 그동안 다른 프로세스는 프린터를 사용하지 못한다.

 

따라서 교착 상태는 막을 수 있지만 자원이 비효율적으로 사용될 수 있다.

3. 비선점 없애기

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

이 조건을 없애려면 자원을 선점할 수 있게 만들면 된다.

이 방식은 CPU처럼 선점이 가능한 자원에는 효과적이다.

 

예를 들어 CPU는 운영체제가 타이머 인터럽트를 통해 실행 중인 프로세스에게서 회수할 수 있다.

 

하지만 모든 자원이 선점 가능한 것은 아니다.

예를 들어 프린터가 어떤 문서를 출력하는 중인데, 중간에 강제로 빼앗아 다른 프로세스에게 넘기면 출력 결과가 망가질 수 있다.

파일 쓰기 작업이나 입출력 장치 작업도 중간에 강제로 빼앗기 어려운 경우가 많다.

 

따라서 비선점을 없애는 방식은 일부 자원에는 적용할 수 있지만, 모든 자원에 적용하기는 어렵다.

4. 원형 대기 없애기

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

이 조건을 없애려면 자원에 순서를 부여하고, 모든 프로세스가 그 순서대로만 자원을 요청하게 만들 수 있다.

 

예를 들어 모든 자원에 번호를 붙인다고 하자.

R1, R2, R3, R4

 

그리고 프로세스는 항상 번호가 작은 자원부터 큰 자원 순서로만 요청해야 한다.

R1 → R2 → R3 → R4

 

이렇게 하면 원형으로 기다리는 구조가 생기기 어렵다.

왜냐하면 모든 프로세스가 같은 방향으로만 자원을 요청하기 때문이다.

하지만 이 방식도 단점이 있다.

먼저 모든 자원에 번호를 붙이는 일이 쉽지 않다.
또한 어떤 자원에 어떤 번호를 붙이느냐에 따라 자원 활용률이 달라질 수 있다.

즉, 원형 대기를 없애는 방식은 이론적으로는 효과적이지만, 실제 시스템에서는 자원 번호 부여와 활용률 문제가 생길 수 있다.

 

교착 상태 회피

교착 상태 회피는 교착 상태가 발생하지 않을 만큼만 조심스럽게 자원을 할당하는 방식이다.

 

예방은 교착 상태 조건 자체를 없애는 방식이었다.
반면 회피는 조건을 무조건 없애기보다는, 자원을 할당할 때마다 교착 상태 가능성을 검사한다.

 

교착 상태 회피에서는 교착 상태를 무분별한 자원 할당으로 인해 발생하는 문제로 본다.

따라서 운영체제는 현재 남은 자원과 프로세스들이 앞으로 요구할 최대 자원량을 고려해서, 안전하다고 판단될 때만 자원을 할당한다.

안전 순서열

교착 상태 회피를 이해하려면 안전 순서열을 알아야 한다.

안전 순서열은 교착 상태 없이 프로세스들이 순서대로 자원을 할당받고 종료될 수 있는 순서이다.

예를 들어 어떤 순서로 프로세스를 실행했을 때 모든 프로세스가 필요한 자원을 받고 정상 종료될 수 있다면, 그 순서는 안전 순서열이다.

안전 상태와 불안전 상태

안전 상태는 안전 순서열이 존재하는 상태로, 교착 상태 없이 모든 프로세스가 종료될 수 있는 상태이다.

반대로 불안전 상태는 안전 순서열이 없는, 교착 상태가 발생할 수도 있는 상태이다.

안전 상태 예시

컴퓨터 시스템에 총 12개의 자원이 있다고 하자.

현재 프로세스는 P1, P2, P3가 있다.

각 프로세스가 현재 할당받은 자원과 최대 요구 자원은 다음과 같다.

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

 

현재 할당된 자원은 총 9개이다.

전체 자원이 12개이므로 현재 남은 자원은 3개이다.

 

이때 P2는 추가로 2개만 더 받으면 최대 요구량을 만족하고 실행을 끝낼 수 있다.

남은 자원 3개
P2 추가 필요 2개

→ P2 실행 가능

 

P2가 끝나면 P2가 사용하던 자원 4개를 반납한다고 볼 수 있다.
그러면 사용 가능한 자원은 7로 늘어난다.

이제 P1은 추가로 5개가 필요하므로 실행 가능하다.

남은 자원 7개
P1 추가 필요 5개

→ P1 실행 가능

 

P1이 끝나면 P1이 사용하던 자원 10개가 반납된다.

그러면 P3도 실행 가능해진다.

따라서 가능한 안전 순서열은 다음과 같다.

P2 → P1 → P3

 

이 순서대로라면 모든 프로세스가 교착 상태 없이 종료될 수 있다.

따라서 이 상태는 안전 상태이다.

 

참고로 네 메모에 적힌 P1 → P2 → P3은 현재 남은 자원이 3개일 때 P1이 추가로 5개를 필요로 하므로 바로 시작할 수 없다.
따라서 이 예시에서는 P2 → P1 → P3 또는 P2 → P3 → P1처럼 P2를 먼저 실행하는 순서가 자연스럽다.

불안전 상태 예시

이번에는 운영체제가 P3에게 자원 1개를 추가로 할당했다고 해보자.

그러면 현재 할당 상태는 다음과 같다.

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

 

현재 할당된 자원은 총 10개이다.

전체 자원이 12개이므로 남은 자원은 2개이다.

남은 자원 2개로 실행 가능한 프로세스를 찾아보자.

P1 추가 필요 5개 → 실행 불가
P2 추가 필요 2개 → 실행 가능
P3 추가 필요 6개 → 실행 불가

 

P2는 실행 가능하다.
P2가 끝나면 자원 4개를 반납하므로 사용 가능한 자원은 6이다.

이제 P1은 추가 필요 5개라 실행 가능하고, P3도 추가 필요 6개라 실행 가능하다.

 

따라서 이 경우도 사실 안전 순서열이 존재한다.

P2 → P1 → P3
또는
P2 → P3 → P1

 

“P3에게 자원 하나를 더 주면 무조건 안전 순서열이 없다”는 설명은 이 숫자만 놓고 보면 맞지 않는다.

 

불안전 상태 예시를 만들려면 P2도 실행할 수 없게 남은 자원이 2개보다 작거나, P2의 추가 필요량이 3개 이상이어야 한다.

예를 들어 P2의 최대 요구가 5개라면 다음과 같다.

프로세스   현재 할당   최대 요구   추가 필요
P1        5          10        5
P2        2          5         3
P3        3          9         6

 

현재 남은 자원은 2개이므로 이 경우 어떤 프로세스도 필요한 자원을 더 받을 수 없다.

따라서 안전 순서열이 없고, 불안전 상태임을 확인할 수 있다.

 

은행원 알고리즘

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

은행원 알고리즘은 은행이 돈을 빌려주는 상황에 비유한 알고리즘이다.

은행은 고객에게 돈을 빌려줄 때, 모든 고객이 언젠가 돈을 빌리고 갚을 수 있는 상태를 유지해야 한다.

운영체제도 마찬가지로 자원을 할당할 때, 모든 프로세스가 언젠가 필요한 자원을 할당받고 종료될 수 있는지 검사한다.

 

은행원 알고리즘은 자원을 할당한 뒤에도 시스템이 안전 상태로 남아 있는 경우에만 자원을 할당한다.

자원 요청 발생
→ 요청을 들어줬을 때 안전 상태인지 검사
→ 안전 상태라면 할당
→ 불안전 상태라면 할당하지 않고 대기

 

정리하면 교착 상태 회피는 항상 안전 상태를 유지하도록 자원을 할당하는 방식이다.

 

 

교착 상태 검출 후 회복

교착 상태 검출 후 회복은 교착 상태가 발생할 수 있음을 인정하고, 실제로 교착 상태가 발생하면 나중에 해결하는 방식이다. 예방이나 회피처럼 미리 막으려고 하지 않는다.

프로세스가 자원을 요구하면 일단 할당한다.
그러다가 교착 상태가 발생했는지 주기적으로 검사하고, 교착 상태가 발견되면 회복 절차를 수행한다.

회복 방법에는 대표적으로 두 가지가 있다.

1. 선점을 통한 회복

선점을 통한 회복은 교착 상태가 해결될 때까지 일부 프로세스에게서 자원을 빼앗아 다른 프로세스에게 할당하는 방식이다.

즉, 자원을 강제로 회수해서 교착 상태를 풀어낸다.

프로세스 A가 가진 자원 회수
→ 프로세스 B에게 할당
→ B 실행 완료
→ 자원 반납
→ 교착 상태 완화

 

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

CPU나 메모리 일부는 선점이 가능할 수 있지만, 프린터 출력 중간 결과처럼 강제로 회수하기 어려운 자원도 있다.

따라서 선점을 통한 회복은 적용 가능한 자원에 제한이 있다.

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

교착 상태를 해결하는 또 다른 방법은 프로세스를 강제 종료하는 것이다.

방법은 두 가지가 있다.

교착 상태에 놓인 프로세스를 모두 강제 종료
교착 상태가 해결될 때까지 하나씩 강제 종료

 

첫 번째 방식은 교착 상태에 관련된 프로세스를 모두 종료하는 방법이다.

이 방법은 확실하게 교착 상태를 해결할 수 있다.

하지만 작업 내역이 모두 사라질 수 있다는 큰 단점이 있다.

 

두 번째 방식은 교착 상태가 해결될 때까지 프로세스를 하나씩 종료하는 방법이다.

이 방식은 한 번에 모두 종료하는 것보다 피해가 적을 수 있다.
하지만 어떤 프로세스를 종료할지 판단해야 하고, 교착 상태가 풀렸는지 계속 확인해야 하므로 오버헤드가 발생한다.

 

 

교착 상태 무시

마지막으로 교착 상태를 아예 무시하는 방식도 있다.

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

타조가 위험을 보면 머리를 땅에 파묻는다는 비유에서 나온 표현이다.

 

즉, 교착 상태가 아주 드물게 발생한다면 이를 해결하기 위한 복잡한 비용을 들이지 않고, 문제가 발생했을 때 사용자가 직접 재부팅하거나 프로세스를 종료하게 두는 방식이다.

 

물론 중요한 시스템에서는 이런 방식이 적절하지 않을 수 있다.

하지만 교착 상태 발생 가능성이 매우 낮고, 예방이나 회피 비용이 너무 크다면 현실적으로 무시하는 전략을 택할 수도 있다.