🔴 데드락(교착상태)이란?
두 개 이상의 프로세스가 자원을 점유한 상태에서 서로가 점유한 자원을 서로에게 요구하고 있어서 그 프로세스들이 무한정으로 기다리고 있는 상태
이에 대한 해결 방법은 예방
, 회피
, 탐지 및 회복
이 있다.
📚 데드락 발생의 4가지 필요 조건
아래의 4가지 조건이 모두 만족되는 경우 데드락이 발생할 가능성이 있다.
→ 하나라도 만족하지 않으면 발생하지 않는다.
1. 상호 배제 (Mutual exclusion)
- 한 리소스는 한 번에 한 프로세스만이 사용할 수 있다.
- 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다.
2. 점유와 대기(Hold and wait)
- 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.
3. 비선점 (No preemption)
- 이미 할당된 자원을 강제로 빼앗을 수 없다.
- 프로세스가 task를 마친 후 리소스를 자발적으로 반환할 때까지 기다려야 한다.
4. 환형 대기 (Circular wait)
- 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.
- Hold and wait 관계의 프로세스들이 서로를 기다림
🟢 데드락(Deadlock)의 해결법
데드락의 해결법은 크게 3가지로 분류할 수 있다.
-
데드락이 발생하지 않도록 예방(prevention)
하기
-
데드락 발생 가능성을 인정하면서도 적절하게 회피(avoidance)
하기
-
데드락 발생을 허용하지만 데드락을 탐지(detection)하여, 데드락에서 회복하기
1. 예방 (Prevention)
데드락의 발생조건 4가지 중 하나라도 발생하지 않게 하는 것
즉, 각각의 조건을 방지하여 데드락 발생 가능성을 차단한다.
하지만 이 방법은 자원의 낭비가 가장 심한 방법이다.
- 자원의 상호 배제 조건 방지
- 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다.
- (그러나 추후 동기화 관련 문제가 발생할 수 있다)
- 점유 대기 조건 방지
- 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류해서, 나중에 또다른 자원을 점유하기 위한 대기 조건을 성립하지 않도록 한다.
- 비선점 조건 방지
- 이미 다른 프로세스에게 할당된 자원이 선점권이 없다고 가정할 때, 높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록 한다.
- 순환 대기 조건 방지
- 자원을 순환 형태로 대기하지 않도록 일정한 한 쪽 방향으로만 자원을 요구할 수 있도록 한다.
2. 회피 (Avoidance)
교착상태가 발생할 가능성을 배제하지 않고 교착상태를 적절히 피해나가는 방법
- 리소스 할당의 측면에서, 교착상태가 발생할 가능성이 있는 자원을 할당하지 않는다.
- 자원을 할당한 후에도 시스템이 항상
Safe state(데드락이 발생하지 않는 안정 상태)
에 있을 수 있도록 할당을 허용하자는 것이 기본 특징이다.
- 주로
은행원 알고리즘(Banker's Algorithm)
이 사용된다.
🔎 은행원 알고리즘(Banker's Algorithm)
다익스트라가 제안한 기법으로, 어떤 자원의 할당을 허용하는지에 관한 여부를 결정하기 전에, 미리 결정된 모든 자원들의 최대 가능한 할당량을 가지고 시뮬레이션 해서 Safe state에 들 수 있는지 여부를 검사한다.
즉, 대기중인 다른 프로세스들의 활동에 대한 교착 상태 가능성을 미리 조사하는 것이다.
- 자원 할당량을 사전에 파악하고 데드락을 회피할 수 있도록 한다.
- 그러나 은행원 알고리즘의 경우 미리 최대 자원 요구량을 알아야 하고, 할당할 수 있는 자원 수가 일정해야 하는 등 사용에 있어 제약 조건이 많고, 그에 따른 자원 이용도 하락 등 단점도 존재한다.
3. 탐지 및 회복 (Detection and Recovery)
교착상태가 발생 할 경우 탐지하여 회복한다
탐지
- 시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견한다.
교착상태 발견 알고리즘
과 자원 할당 그래프
등을 사용한다.
- 자원 할당 그래프의 단점 : 자원을 요청할 때마다 탐지 알고리즘을 실행하면, 오버헤드가 발생한다.
회복
- 교착상태를 발견했다면 회복을 진행한다.
- 교착상태를 일으킨 프로세스를 종료하거나 교착상태의 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복한다.
- 프로세스 종료 방법
- 교착 상태의 프로세스 모두 중지
- 교착 상태가 제거될 때까지 한 프로세스씩 중지
- 자원 선점 방법
- 자원을 빼앗긴 프로세스는 강제 종류 이후 재시작
- 교착 상태에 빠진 프로세스가 필요로 하는 자원을 강제로 가져옴