질문의 핵심
- 교착상태(데드락)란?
- 교착상태가 발생할 필요조건은?
- 교착상태가 일어나는 원인은?
- 교착상태를 해결하는 방법은?
1. 데드락(Deadlock)
데드락이란?
- 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때, 무한 대기에 빠지는 상황.
- 교착 상태.
데드락은 프로세스가 자원을 사용하는 절차인 Request, Allocate, Use, Release 중 모든 프로세스가 Request 상태가 되어있는 상황이다.
데드락의 발생조건
데드락이 발생하기 위해 다음 4가지 조건이 모두 만족해야 된다.
- 상호 배재(Mutual Exclusion): 한 번에 프로레스 하나만 해당 자원을 사용할 수 있다.
- 점유 대기(Hold and Wait): 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.
- 비선점(No Preemption): 이미 할당된 자원을 강제로 빼앗을 수 없다.
- 순환 대기(Circular Wait): 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.
데드락의 해결법
- 예방(Prevention)
- 회피(Avoidance)
- 탐지(Detection)
- 무시(Ignoration)
데드락의 예방법
- 자원의 상호 배재 조건 방지: 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다. 추후, 동기화 문제가 발생할 수 있다.
- 점유 대기 조건 방지: 프로세스 실행에 필요한 모든 자원을 한꺼번에 할당받게 하거나, 자원이 필요한 경우 보유하고 있던 자원을 모두 반납하고 다시 요청하게 한다. 따라서, 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않도록 한다.
- 비선점 조건 방지: 이미 다른 프로세스에게 할당된 자원이 높은 우선 순위의 프로세스에게 선점될 수 있도록 한다.
- 순환 대기 조건 방지: 자원을 순환 형태로 대기하지 않도록 일정한 한 쪽 방향으로만 자원을 요구할 수 있도록 한다.
데드락을 예방하는 방법들은 시스템의 처리량이나 효율성을 떨어뜨리는 단점 혹은 기아 문제가 발생할 수 있다. 데드락 회피법으로 데드락 예방법의 단점 일부를 해결할 수 있다.
데드락의 회피법
안전 순서(Safe sequence)
특정한 순서로 프로세스들에게 자원을 할당할 때 데드락이 발생하지 않는 순서.
안정 상태(Safe State)
- 시스템의 프로세스들이 요청하는 모든 자원을 데드락을 발생시키지 않으면서도 차례로 모두에게 할당해 줄 수 있는 상태.
- 시스템의 프로세스들에 대한 안전 순서가 존재하는 상태.
안정 상태와 반대로 불안정 상태(Unsafe State) 는 데드락 발생 가능성이 있는 상황을 말한다. 데드락은 불안정 상태에서 발생할 수 있다. 따라서, 불안정 상태가 되지 않도록 자원을 할당하여 데드락을 회피한다.
자원을 할당한 후에도 시스템에 항상 안정 상태에 있을 수 있도록 하여 데드락을 회피할 수 있다. 이를 위한 알고리즘 중 유명한 것이 자원 할당 그래프 알고리즘 과 은행원 알고리즘 이다.
자원 할당 그래프 알고리즘(Resource Allocation Graph Algorithm)
자원을 요청하는 선이 자원을 할당받는 선으로 변경될 때, 점선(미래에 자원을 요청할 수 있음)을 포함하여 사이클이 생기지 않는 경우에만 요청된 자원을 할당한다.
각 자원 타입마다 하나의 인스턴스가 존재하는 경우 사용한다.
은행원 알고리즘(Banker's Algorithm)
- 어떤 자원의 할당을 허용하는지에 관한 여부를 결정하기 전에, 미리 결정된 모든 자원들의 최대 가능한 할당량을 가지고 시뮬레이션해서 안정 상태에 들 수 있는지 여부를 검사한다.
- 총 요청 자원의 수가 남은 자원의 수보다 적은 프로세스만 선택하여 수행한다.
은행원 알고리즘의 경우, 여러 인스턴스가 존재하는 경우에 사용한다. 또, 미리 최대 자원 요구량을 알아야 하고, 할당할 수 있는 자원 수가 일정해야 하는 등의 제약조건이 있다.
데드락 탐지 및 회복
데드락이 발생했을 때, 데드락을 탐지하고 회복하는 알고리즘을 사용한다.
데드락 탐지(Detection)
- 총 요청 자원의 수가 남은 자원의 수보다 적은 프로세스가 존재하지 않는지 탐지.
- 이 외에 자원 할당 그래프를 통해 탐지.
데드락 회복(Recovery)
- 단순히 프로세스를 1개 이상 중단시키기.
- 데드락에 빠진 모든 프로세스를 중단시키기.
- 데드락이 해결될 때까지 한 번에 한 프로세스씩 종료시키기.
- 자원 선점하기.
- 어떤 프로세스를 종료시킬지 결정하고, 데드락이 발생하기 전 상태로 돌아가(Rollback) 프로세스를 재시작한다.
데드락 무시(Deadlock Ignorance)
데드락이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않는 방식.
데드락에 대한 조치 자체가 더 큰 오버헤드일 수 있기 때문에, 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 프로세스를 죽이는 등의 방법으로 대처한다. 대부분의 범용 운영체제가 채택하는 방식이다.
참조
