교착 상태(DeadLock)

도서 쉽게 배우는 운영체제와 강의 운영체제-반효경 를 보고 정리한 글입니다.

 

📌 교착 상태란?

프로세스들이 서로가 가진 자원을 기다리며 대기중인 상태이다.

 

CPU 스케줄링 파트에 나왔던 아사 현상과는 다른데, 아사 현상의 경우 특정 프로세스의 우선순위가 계속 밀려 장기간 CPU를 할당받지 못하는 것이고 

 

교착상태는 여러 프로세스가 작업을 하다보니 서로의 자원을 할당받기 위해 무한정 대기하는 상태인 것이다.

 

교착 상태는 다음 4가지 조건을 💡 모두 만족했을 때, 발생한다.

 

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

 

 

상호 배제

프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다.

 

즉, 자원이 임계구역으로서 보호되기 때문에 여러 프로세스가 동시에 자원을 사용할 수 없다.

 

🚨 독점적으로 사용하는 자원을 두지 않는 방법으로 예방할 수 있지만, 임계 구역을 보호하지 않으면 생기는 경쟁 조건이나 동기화 문제 때문에 현실적으로 가능하지 않다.

 

비선점

프로세스는 다른 프로세스가 사용하고 있는 자원을 강제로 빼앗을 수 없어야 한다.

 

만약, 자원을 빼앗을 수 있다면 대기할 필요 없이 가져오면 되기 때문에 교착 상태는 발생하지 않을 것이다.

 

🚨 모든 자원을 빼앗을 수 있도록 만드는 방법으로 예방할 수 있지만, 이 방법 역시 임계 구역을 보호하지 않으면 생기는 문제들도 있고 빼앗을 수 있는 우선 순위나 시간에 대한 기준을 세우기 어렵다.

 

점유와 대기

프로세스는 자원을 할당받은 상태에서 다른 프로세스가 점유하고 있는 자원을 할당받기 위해 대기중인 상태여야 한다.

 

🚨 프로세스가 어떤 자원을 할당받을 때 필요한 자원을 전부 할당받아, 다른 자원을 기다리는 상황을 없에는 것으로 예방할 수 있다.

하지만, 추가로 필요한 자원이 생기는 경우가 있을 수 있다.

또한, 당장 사용하지 않은 자원을 선점하는 것은 비효율적이고 자원이 많이 필요한 경우 초기에 확보하기 어렵다.

 

원형대기

점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다.

 

원을 이루기 때문에 서로 양보하지 않게 되고 교착 상태에 빠진다.

 

🚨 자원에 우선순위를 부여하고 우선순위 별로 처리하여 원형으로 교착상태가 발생하는 것을 막을 수 있지만,

작업 진행에 유연성이 떨어지고 우선순위를 어떻게 부여할지 결정하기 어렵다.

 

 

📌 교착 상태 회피

교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고, 교착 상태가 발생하는 범위에 있으면 프로세스를 대기시킨다.

 

은행원 알고리즘

은행원 알고리즘은 최악의 경우를 기준으로 문제 상황을 철저히 피하여 교착 상태를 막는다.

 

각 프로세스는 자신이 사용할 자원의 최대 수를 운영체제에게 알려준다.

 

1. 전체 자원 : 시스템 내 전체 자원의 수
2. 가용 자원 : 시스템 내 현재 사용할 수 있는 자원의 수
3. 최대 자원 : 각 프로세스가 선언한 최대 자원의 수
4. 할당 자원 : 각 프로세스에 할당되어 있는 자원의 수
5. 기대 자원 : 각 프로세스가 앞으로 사용할 자원의 수

 

 

위 상황을 보면, 전체 자원이 A:10 B:5 C:7 인 상황이다.

 

프로세스의 기대 자원 수(Need)가 가용 자원 수(Available) 이하라면, 자원을 할당하여 작업을 끝낼 수 있으므로 안정 상태이다.

 

따라서, P1, P3는 안정상태로 볼 수 있다.

 

반면에, P0 의 경우 현재 가용 자원으로 최대 자원을 만족시켜줄 수 없기 때문에 안정 상태가 아니다.

 

위 예시의 경우, 안정 상태에 있는 프로세스에 먼저 자원을 할당해서 작업을 마치고 자원을 회수하면

 

가용 가능한 자원의 수가 늘어나기 때문에 안정 상태의 프로세스가 추가적으로 생긴다.

 

따라서, 모든 프로세스를 데드락 없이 작업을 완료시킬 수 있다.

 

 

 

기대 자원 수가 가용 자원 수보다 큰 프로세스에 자원을 할당하면 절대 안되고

 

현재 가용 자원으로 끝낼 수 있는 기대 자원이 있는 경우에만 자원을 할당해야 한다.

 

 

교착 상태 회피 방식의 문제점

모든 프로세스가 자신이 사용할 자원을 미리 선언해야 하는데, 쉬운 일이 아니다.

 

또한, 시스템 자원 수가 고정적이어야 하는데, 일시적인 고장이나 새로운 자원이 추가되는 일이 빈번하다.

 

그리고 프로세스에 따라 최대 자원 만큼 할당받지 않고도 작업을 끝낼 수 있는 경우가 있는데, 무작정 대기하는 것은 비효율적이다.

 

 

📌 교착 상태 검출

 

교착 상태 예방의 경우 현실적으로 구현하기 어렵고

 

교착 상태 회피의 경우 역시, 구현하기 어려우며 비효율적이다.

 

따라서, 교착 상태가 발견 됐을 때 회복하는 방법이 가장 현실적인 방법이다.

 

 

1. 타임 아웃을 이용한 교착 상태 검출

일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태로 판단하여 처리한다.

 

데이터 베이스의 경우, 데이터의 일관성이 중요하기 때문에 롤백 방식을 적용한다.

 

2. 자원 할당 그래프를 이용한다.

자원 할당 그래프를 확인해서 교착 상태가 있는지 확인한다.

 

 

프로세스(P) 가 자원(R)을 가리키면 할당 받기 위해 대기중인 것이고, 자원이 프로세스를 가리키면 점유하고 있는 상태임을 의미한다.

 

모든 자원이 상호 배제와 비선점 자원일 때,

 

왼쪽 그래프의 경우, 모든 프로세스가 점유와 대기 상태이고 원형대기 상태이다. 따라서 교착 상태임을 알 수 있다.

 

오른쪽 그래프의 경우, 점유와 대기 상태가 아니며 원형대기 상태가 아니므로 교착상태가 발생하지 않음을 알 수 있다.

 

 

교착 상태를 정확하게 파악할 수 있지만, 자원 할당 그래프를 유지 · 갱신 · 검사하는 작업이 필요하다.

 

 

📌 교착 상태 회복

교착 상태로 판단되는 경우, 교착 상태를 푸는 후속 작업이 필요하다.

 

1. 교착 상태를 일으킨 모든 프로세스를 동시에 종료

종료된 프로세스들이 다시 동시에 작업을 시작하면, 다시 교착 상태를 일으킬 가능성이 크므로

 

다시 실행할 때는 어떤 프로세스를 먼저 실행할 것인지 기준이 필요하다.

 

2. 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료

우선 순위가 낮은 프로세스를 먼저 종료하고, 우선 순위가 같은 경우 작업 시간이 짧은 프로세스를 먼저 종료한다.

 

우선 순위와 작업 시간이 동일한 경우, 자원을 많이 사용하는 프로세스를 먼저 종료한다.