교착 상태(DeadLock)과 해결 방법
Table of contents
교착 상태란 (Dead Lock)
2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태를 교착 상태 라고 한다.
아사 현상은 운영체제가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제이고,
교착 상태는 여러 프로세스가 작업을 진행하다 보니 자연적으로 일어나는 문제이다.
교착 상태의 발생
- 프로세스 간, 공유할 수 없는 임계구역의 자원을 사용하면서, 서로의 작업 완료를 기다릴때 발생할 수 있다.
- 임계 구역을 해결하기 위해, 사용하는 공유 변수 때문에 무한 대기 현상이 일어나는 경우, 교착 상태가 발생할 수 있다.
- 데이터의 일관성을 유지하기 위해, 데이터베이스가 잠금을 사용할 때, 교착상태가 발생할 수 있다.
교착 상태 필요조건과 예방
교착 상태가 발생하는 4가지 필요조건이 있고, 하나라도 충족하지 않으면 발생하지 않는다.
1. 상호 배제
한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다. 배타적인 자원은 임계구역으로서, 다른 프로세스가 동시에 사용할 수 없기 때문이다.
-> 독점적으로 사용할 수 있는 자원을 두지 않는 방법으로 예방할 수 있지만, 임계구역을 보호하지 않으면 생기는 문제들 때문에 현실적으로 가능하지 않다.
2. 비선점
한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다.
-> 모든 자원을 빼앗을 수 있도록 만드는 방법이 있지만, 이 방법 역시 임계구역을 보호하지 않으면 생기는 문제들도 있고, 빼앗을 수 있는 우선순위나 시간에 대한 기준을 세우기 어렵다. 또한, 아사 현상을 일으킬 수 있다.
3. 점유와 대기
프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다.
-> 프로세스가 어떤 자원을 할당받은 상태라면, 다른 자원을 기다리지 못하게하는 방법이 있다. 하지만, 추가로 필요한 자원이 있는 경우가 있고, 당장 사용하지 않을 자원을 선점하는 경우 자원 활용성이 떨어지고, 자원 여러개가 많이 필요한 프로세스의 경우 자원 확보가 매우 어렵다.
4. 원형 대기
점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다.
-> 자원에 우선순위를 부여하고 우선순위별로 처리하여 원형으로 교착상태가 발생한는 것을 막을 수 있지만, 작업 진행에 유연성이 떨어지고 우선순위를 어떻게 부여해야 하는지 결정하기 어렵다.
교착 상태 회피
교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고, 교착 상태가 발생하는 범위에 있으면 프로세스를 대기시킨다.
자원을 많이 할당할 수록 교착 상태가 발생할 확률이 커지는 것은 당연하기 때문에, 자원의 총수와 할당된 자원의 수를 기준으로 시스템이 안정 상태를 유지하도록 자원을 할당한다.
은행원 알고리즘 (banker’s algorithm)
은행원 알고리즘은 최악의 경우를 기준으로 문제 상황을 철저히 피하여 교착 상태를 막는다.
각 프로세스는 자신이 사용할 자원의 최대 수를 운영체제에 알려준다. 운영체제가 자원을 할당할 때 시스템의 상태를 파악하는 데 꼭 필요한 정보이기 때문이다.
- 전체 자원 : 시스템 내 전체 자원의 수
- 가용 자원 : 시스템 내 현재 사용할 수 있는 자원의 수
- 최대 자원 : 각 프로세스가 선언한 최대 자원의 수
- 할당 자원 : 각 프로세스에 할당된 자원의 수
- 기대 자원 : 각 프로세스가 앞으로 사용할 자원의 수(최대 자원 - 할당 자원)
프로세스가 하나라도, 기대 자원 수가 가용 자원 수 이하라면, 자원을 할당하여 작업을 끝낼 수 있으므로 안정상태이다.
작업을 끝내면, 할당 받았던 자원 수까지 가용 자원수로 포함되기 때문에, 다른 프로세스를 무리없이 끝낼 수 있기 때문이다.
따라서, 기대 자원수가 가용 자원수보다 큰 프로세스에 자원을 할당하면 절대 안되고, 현재 가용 자원으로 끝낼 수 있는 기대 자원이 있는 경우에만 자원을 할당해야 한다.
교착 상태 회피 방식의 문제점
- 모든 프로세스가 자신이 사용할 자원을 미리 선언해야 하는데, 쉬운 일이 아니다.
- 시스템 자원 수가 고정적이어야 하는데, 일시적인 고장이나 새로운 자원이 추가되는 일이 빈번하다.
- 프로세스에 따라, 최대 자원을 할당받지 않아도 작업을 진행하거나 끝낼 수 있는 프로세스가 있는데, 무작정 대기하는 것은 자원 낭비일 수 있다.
교착 상태 검출
교착 상태 예방의 경우, 현실적으로 구현하기 어렵고 (임계구역 보호), 교착 상태 회피의 경우 자원이 낭비될 수 있다.
따라서, 교착 상태가 발견 되면, 회복하는 방법이 가장 현실적인 방법이다.
1. 타임아웃을 이용한 교착 상태 검출
일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태로 판단하여 처리한다.
-> 엉뚱한 프로세스가 강제 종료될 수 있고, 여러 시스템에 나뉘어 있는 분산 데이터베이스와 같은 경우에는 타임아웃 방법을 적용하기 어렵다.
따라서, 프로그램이 응답이 없어 종료합니다. 와 같은 메세지를 띄우고 강제 종료할 것인지 대기할것인지 묻는 경우가 있다.
데이터베이스의 경우, 데이터의 일관성이 중요하기 때문에 롤백 방식을 적용한다.
2. 자원 할당 그래프를 이용한다.
자원 할당 그래프를 확인해서 교착 상태가 있는지 확인한다.
교착 상태를 정확하게 파악할 수 있지만, 자원 할당 그래프를 유지 · 갱신 · 검사하는 작업이 필요하다.
교착 상태 회복
교착 상태로 판단되는 경우, 교착 상태를 푸는 후속 작업이 필요하다.
1. 교착 상태를 일으킨 모든 프로세스를 동시에 종료
종료된 프로세스들이 동시에 작업을 시작하면 다시 교착 상태를 일으킬 가능성이 크므로, 다시 실행할 때는 어떤 프로세스를 먼저 실행할 것인지 기준이 필요하다.
2. 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
우선 순위가 낮은 프로세스를 먼저 종료하고, 우선 순위가 같은 경우 작업 시간이 짧은 프로세스를 먼저 종료한다.
우선 순위와 작업 시간이 동일한 경우, 자원을 많이 사용하는 프로세스를 먼저 종료한다.