교착 상태(Dead lock)
무엇인가?
2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기를 기다리며 더 이상 진행하지 못하는 상태이다.
기아현상(Starvation)과 차이는?
기아 현상은 운영체제가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제이고, 교착 상태는 여러 프로세스가 작업하며 자연적으로 일어나는 문제이다.
언제 발생하나?
상호 배제, 비선점, 점유와 대기, 원형 대기를 모두 충족해야 발생한다(필요 조건).
상호 배제(Mutual exclusion)
한 프로세스가 사용하는 자원이 다른 프로세스와 공유할 수 없는 배타적인 자원이다.
비선점(non-preemption)
한 프로세스가 사용 중인 자원은 다른 프로세스가 빼앗을 수 없는 비선점 자원이다.
점유와 대기(hold and wait)
프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태이다.
원형 대기(circular wait)
점유와 대기를 하는 프로세스 간의 관계가 원을 이룬다.
어떻게 해결하나?
예방
교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화한다. 실효성이 적어 잘 사용되지 않는다.
상호 배제 예방
독점적으로 사용할 수 있는 자원을 없앤다. 현실적이지 어렵다.
비선점 예방
모든 자원을 빼앗을 수 있도록 만든다. 아사 현상이 발생하며, 이를 해결하기 위해 에이징을 도입하여도 현실적으로 기준을 정하기 어렵다.
점유와 대기 예방
프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방식이다. 프로세스는 시작 초기에 모든 자원을 한꺼번에 점유하거나 그렇지 못할 경우 자원을 모두 반납한다.
단점- 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어렵다.
- 자원의 활용성이 떨어진다.
- 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리하다.
- 결국 일괄 작업 방식으로 동작한다.
원형 대기 예방
점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는다.
단점- 프로세스 작업 진행 유연성이 떨어진다.
- 자원의 번호를 어떻게 부여할 것인지 문제이다.
회피
자원 할당량을 조절하여 교착 상태를 해결한다. 자원을 얼마만큼 할당해야 교착 상태가 발생하지 않는다는 보장이 없기 때문에 실효성이 적다.
은행원 알고리즘
교착 상태 회피를 구현하는 방법으로, 자원의 총 수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당한다.
검출
자원 할당 그래프를 모니터링하며 교착 상태가 발생하는지 살펴본다. 검출 - 회복은 교착 상태를 해결하는 현실적인 접근이다.
타임 아웃
자원 할당 그래프(Resource allocation graph)
프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표한한 것이다. 어떤 프로세스에 자원이 할당되어 있는지 혹은 어떤 프로세스가 자원을 기다리고 있는지를 한눈에 파악할 수 있다.
회복
교착 상태가 검출되면 교착 상태를 푸는 후속작업이다.
교착 상태 프로세스 동시 종료
종료된 프로세스들이 동시에 작업 시작하면 다시 교착 상태 일으킬 가능성이 존재한다.
교착 상태 프로세스 순차 종료
어떤 프로세스부터 종료할지 기준이 필요하다.
- 우선순위 낮은 프로세스 먼저 종료
- 우선순위 같은 경우 작업 시간 짧은 프로세스 먼저 종료
- 위 두 조건 같은 경우 자원 많이 사용하는 프로세스 먼저 종료
경쟁 조건(Race Condition)
무엇인가?
2개 이상의 프로세스가 공유 자원을 병행적으로 읽거나 쓰는 상황이다. 공유 자원 접근 순서에 따라 실행 결과가 달라질 수 있다.
어떻게 해결하나?
프로세스 동기화와 조정이 필요하다.
발생 상황
커널 작업 수행 도중 인터럽트 발생
커널 모드에서 데이터를 로드하여 작업 수행 중 인터럽트가 발생하여 같은 데이터를 조작하는 경우이다.
해결법
커널 모드에서 작업을 수행하는 동안, 인터럽트를 발생하지 못하게 하고 시간이 초과되어도 CPU 제어권을 가져가지 못하게 한다.
멀티 프로세서 환경에서 공유 메모리 내의 커널 데이터에 접근할 때
멀티 프로세서 환경에서 2개의 CPU가 동시에 커널 내부의 공유 데이터에 접근하여 조작하는 경우이다.
해결법
커널 내부에 있는 각 공유 데이터에 접근할 때 lock을 한다.
참고
