교착상태와 교착상태 해결방법에 대해서 설명해주세요.
답변
- 교착상태란 두 개 이상의 프로세스가 자원을 점유한 상태에서 서로가 점유한 자원을 서로에게 요구하고 있어서 그 프로세스들이 무한정으로 기다리고 있는 상태입니다.
- 이에 대한 해결방법은
예방,회피,탐지및회복이 있습니다.
교착상태란 ?
Deadlock- 두 개 이상의 프로세스가 서로의 작업이 끝나기만을 기다리고 있어 둘 다 영원히 끝나지 않는 상황
교착상태의 4가지 필요 조건
아래 4가지 조건이 모두 만족되는 경우 데드락이 발생할 가능성이 있다.
→ 하나라도 만족하지 않으면 발생하지 X
- 상호 배제 (
Mutual exclusion)- 한 리소스는 한 번에 한 프로세스만이 사용할 수 있다.
- 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다.
- 점유와 대기(
Hold and wait)- 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.
- 비선점 (
No preemption)- 이미 할당된 자원을 강제로 빼앗을 수 없다.
- 프로세스가 task를 마친 후 리소스를 자발적으로 반환할 때까지 기다려야 한다.
- 환형 대기 (
Circular wait)
- 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.
- Hold and wait 관계의 프로세스들이 서로를 기다림
교착상태 해결방법
크게 3가지의 해결법이 존재한다.
- 데드락이 발생하지 않도록 예방(
prevention) 하기 - 데드락 발생 가능성을 인정하면서도 적절하게 회피(
avoidance) 하기 - 데드락 발생을 허용하지만 데드락을 탐지(
detection)하여, 데드락에서 회복(Recovery)하기
1️⃣ 예방 (Prevention)
- 교착상태가 발생할 수 있는 요구조건을 만족시키지 않게 함으로써 교착상태를 방지한다.
- 위에 있는 교착상태 발생의 네가지 조건 중에서 어느 하나를 제거함으로써 수행된다.
- 자원 낭비가 가장 심한 기법이다.
2️⃣ 회피 (Avoidance)
- 교착상태가 발생할 가능성을 배제하지 않고 교착상태가 발생하면 적절히 피해나가는 방법이다.
- 리소스 할당의 측면에서, 교착상태가 발생할 가능성이 있는 자원 할당(unsafe allocation)을 하지 않는다.
- 주로 은행원 알고리즘(Banker's Algorithm)이 사용된다.
은행원 알고리즘
- 은행원 알고리즘은 다익스트라가 제안한 기법으로, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래한 기법
- 각 프로세스에게 자원을 할당하여 교착상태가 발생하지 않으며 모든 프로세스가 완료될 수 있는 상태는
안전상태, 교착상태가 발생할 수 있는 상태는불안전 상태라고 한다.- 은행원 알고리즘을 적용하기 위해서는 자원의 양과 사용자(프로세스) 수가 일정해야 한다.
- 은행원 알고리즘은 프로세스의 모든 요구를 유한한 시간안에 할당하는 것을 보장한다.
3️⃣ 탐지 및 회복 (Detection and Recovery)
- 교착상태가 발생 할 수 있도록 놔 두고 교착상태가 발생 할 경우 찾아내어 고친다.
탐지
- 시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견한다.
- 교착상태 발견 알고리즘과 자원 할당 그래프 등을 사용한다.
자원 할당 그래프의 단점 : 자원을 요청할 때마다 탐지 알고리즘을 실행하면, 오버헤드가 발생한다.
회복
- 교착상태를 발견했다면 회복기법을 진행한다.
- 교착상태를 일으킨 프로세스를 종료하거나 교착상태의 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복한다.
1. 프로세스 종료 방법
- 교착 상태의 프로세스 모두 중지
- 교착 상태가 제거될 때까지 한 프로세스씩 중지
2. 자원 선점 방법
- 자원을 빼앗긴 프로세스는 강제 종류 이후 재시작
- 교착 상태에 빠진 프로세스가 필요로 하는 자원을 강제로 가져옴
참고 자료
데굴데굴 뚝딱뚝딱 개발기록