목차
- 교착 상태이란?
- 교착 상태 발생 조건
- 교착 상태 해결 방법
- 현대 컴퓨터는 교착 상태를 어떻게 처리할까?
- 기아 상태란?
- 기아 상태 해결 방법
1. 교착 상태(데드락, Deadlock)이란?
공유 자원에 대한 동기화 문제를 해결하기 위해 성립해야 하는 세 가지 조건이 있다. 공유 자원을 사용하고 있는 프로세스가 존재한다면 다른 프로세스는 임계영역에 진입할 수 없는 상호 배제, 공유 자원을 사용하는 프로세스가 없다면 임계 영역에 진입할 수 있는 진행, 무한 대기를 발생시키지 않게 하기 위해 임계 영역 진입 횟수에 제한을 두는 한정 대기를 충족해야 한다.
하지만 위의 조건을 충족해 동기화 문제를 해결했을 때 발생하는 문제점이 있는데, 그것이 교착 상태이다. 교착 상태는 자원을 점유하고 있는 2개 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 요구하며, 서로의 작업이 끝나기를 기다리는 상태를 말한다.
2. 교착 상태 발생 조건
- 상호 배제 (Mutual Exclusion) : 한 번에 하나의 프로세스만 공유 자원을 사용할 수 있다.
- 점유 대기 (Hold And Wait) : 자원을 점유하고 있는 상태에서 다른 프로세스가 점유하는 자원을 기다린다.
- 비선점 (No Preemption) : 다른 프로세스가 점유 중인 자원을 뺏을 수 없다.
- 순환 대기 (Circular Wait) : 2개 이상의 프로세스에서 자원 점유와 자원 요구의 관계가 순환 구조를 띤다.
교착 상태는 네 가지 조건을 모두 만족해야 발생한다. 아래 사진에서 R은 자원, P는 프로세스를 칭할 때, 왼쪽은 교착 상태를 나타내지만, 오른쪽은 교착 상태가 아니다. 우선 왼쪽 사진을 설명하면 P1은 P2에게, P2는 P3에게, P3는 P1과 P2에게 할당된 자원을 요구하고 있기 때문에 교착 상태가 발생했다. 하지만 오른쪽 사진의 경우에는 P2와 P4의 실행을 마치면 P1과 P3가 자원을 할당받을 수 있기 때문에 교착 상태가 아닌 것이다.
3. 교착 상태 해결 방법
교착 상태를 해결하는 방법은 크게 세 가지로 분류한다. 교착 상태가 발생하지 않도록 "예방"하는 것, 교착 상태가 발생할 가능성을 배제하지 않고 적절히 "회피"하는 것, 교착 상태를 허용하면서 이를 "탐지"해 다시 회복하는 것으로 나뉜다.
1) 예방
앞서 네 가지 조건을 모두 만족해야 교착 상태가 발생한다고 언급했다. 따라서 교착 상태 발생 조건 중 하나를 부정함으로써 교착상태를 예방할 수 있다. 하지만 한 번에 하나의 프로세스만 공유 자원을 사용할 수 있기에 교착 상태가 발생하는데, 상호 배제 조건을 부정해 버리면 교착 상태 발생과 모순이 일어나므로 사실상 무의미하다.
- 점유 대기(Hold And Wait) 조건 방지
: 프로세스가 자원을 요청할 때 다른 자원을 점유하고 있으면 안 된다. 프로세스 생성 시 모든 자원을 할당받게 하거나, 점유하고 있던 자원을 모두 반환한 후에 다시 요청할 수 있도록 한다. 하지만 현재 명령에 필요하지 않은 자원도 점유하고 있기 때문에 효율이 좋지 않다.
- 비선점(No Preemption) 조건 방지
: 특정 자원을 할당받기를 기다리는 프로세스는 갖고 있던 자원을 모두 해제한다. 레지스터와 같이 상태를 저장하고 복구할 수 있는 자원에 사용할 수 있지만, 프린트나 드라이브 등과 같은 자원에는 적용하기 어렵다.
- 순환 대기(Circular Wait) 조건 방지
: 모든 자원에 번호를 부여하고, 현재 할당받은 우선순위보다 낮은 우선순위의 자원을 요청하기 위해서 현재 자원을 해제한 다음에 요청할 수 있다. 순서에 따라 자원을 할당받을 수 있기 때문에 효율이 좋지 않다.
2) 회피
교착 상태 회피는 교착 상태 예방보다 덜 엄격하면서 자원을 좀 더 효율적으로 사용할 수 있다. 교착 상태가 발생할 가능성이 있는 상태와 아닌 상태를 파악해야 하며, 이를 위해 아래와 같은 가정이 필요하다.
- 프로세스 수 고정
- 자원의 종류와 수 고정
- 프로세스가 사용할 최대 자원의 수
- 프로세스는 자원 사용 후 반납
교착 상태를 회피하기 위한 알고리즘에는 대표적으로 두 가지가 있다.
- 자원 할당 그래프 알고리즘(Resource Allocation Graph Algorithm)
: 프로세스는 나중에 필요한 자원을 미리 알려야 한다. 점선은 나중에 필요한 자원을 의미하는데, 점선을 포함해 사이클이 생기지 않을 경우에만 요청된 자원을 할당받을 수 있다. 사이클이 없다면 교착 상태가 발생하지 않아 자원을 할당받는다. 하지만 사이클이 있다면 교착 상태가 발생할 '가능성'이 있는 것임을 명심해야 한다.
- 은행원 알고리즘(Banker's Algorithm)
: 다익스트라가 고안한 알고리즘이며, 프로세스가 자원을 요청할 때마다 수행되어 시스템 부하가 심하다. 대기 중인 프로세스에서 총 요청한 자원의 수가 남아있는 자원의 수보다 작을 경우에만 자원을 할당한다. 교착 상태로부터 안전하다고 판단될 경우에만 자원을 할당해 주기 때문에, 교착 상태가 발생하지는 않지만 굉장히 비효율적이어서 이론적으로만 완벽한 알고리즘이다.
3) 탐지
교착 상태가 발생했는지 탐지하고, 다시 회복하기 위해 탐지 알고리즘, 회복 알고리즘이 필요하다. 하지만 언제 탐지 알고리즘을 수행할지에 대한 결정이 쉽지 않으며, 회복 알고리즘은 특정 프로세스를 강제 중지시키거나 자원 반납을 요구하므로 기존에 수행 중이던 작업을 다시 수행해야 한다.
4. 현대 컴퓨터는 교착 상태를 어떻게 처리할까?
정답은 현대 컴퓨터는 교착 상태를 처리하지 않는다. 리눅스나 윈도우의 OS는 교착 상태가 일어나지 않는다고 가정하기 때문에, 교착 상태를 처리할 수 있도록 설계되지 않았다.
따라서 교착 상태가 발생했을 때 두 개 이상의 프로세스가 동작하지 않아, 데이터에 손실이 발생하고 컴퓨터가 응답하지 않는 결과를 마주한다. 만약 교착 상태가 발생했다면 수동으로 프로세스를 종료시키거나 컴퓨터를 재부팅함으로써 사용자가 직접 데드락 발생을 해결해야 한다.
5. 기아 상태(Starvation)란?
프로세스의 우선순위가 낮아 필요한 자원을 할당받지 못하고 계속 기다리고 있는 상태를 의미한다. 교착 상태는 자원을 점유 중인 2개 이상의 프로세스가 서로에게 할당된 자원을 요구할 때 발생하고, 기아 상태는 여러 프로세스가 하나의 자원을 점유하기 위해 경쟁할 때 특정 프로세스는 영원히 자원을 할당받지 못할 때 발생한다.
6. 기아 상태 해결 방법
특정 자원의 대기가 길어질수록 우선순위를 높여주는 에이징 기법을 통해 기아 상태를 해결할 수 있다. 그 외에도 FIFO 방식으로 기아 상태를 해결할 수 있다.
댓글