교착상태는 예방하거나, 회피하거나, 검출 후 회복해서 해결할 수 있다.
그냥 무시할 수도 있다. (대부분의 운영체제가 무시함)
예방
교착 상태 발생 조건 4가지에 해당하는 상호 배제, 점유와 대기, 비선점, 원형 대기 중 하나의 조건이라도 없애면 교착 상태는 발생하지 않는다.
- 상호 배제
- 모든 자원을 공유 가능하게 만든다
단점: 현실적으로 힘듦
- 점유와 대기
- 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분한다. (포크를 두개 동시에 들게 하거나, 아예 못들게 한다.)
단점: 자원의 활용률이 낮아지고, 프로세스가 모든 자원을 할당 받을 수 있는 타이밍을 확보하기가 어렵다.
- 비선점
- 자원을 이용 중인 프로세스로부터 자원을 빼앗는다.
- 대표적으로 CPU 를 각 프로세스가 일정 시간동안 선점해서 사용한다.
단점: 프린터와 같이 한 프로세스가 시작부터 끝까지 사용해야 하는 경우 사용이 불가능하다.
- 원형 대기
- 모든 자원에 번호를 부여해서 오름차순으로 자원을 할당한다.
- 철학자들에게 번호가 낮은 포크에서 높은 포크 순으로 집어들게 한다.
단점: 시스템에 존재하는 수많은 자원에 일일이 번호를 붙이기 힘들다.
원형 구조를 없애면 일자 테이블에서 식사하는 상황과 유사해진다.
회피
프로세스가 어떤 자원을 얼마나 사용할지 보고한다. 그러면 OS는 요청이 올 때마다 데드락 발생 가능성을 동적으로 판단하여 자원을 할당한다.
- 안전 순서열 : 교착 상태 없이 안전하게 프로세스들에게 자원을 할당할 수 있는 순서
- 안전 상태 : 안전 순서열대로 프로세스에 자원을 배분해 교착 상태가 발생하지 않는 상태
- 불안전 상태 : 안전 순서열이 없는 상황으로 교착 상태가 발생할 위험이 있다.
자원 할당 그래프 알고리즘
- 자원의 종류마다 한개의 인스턴스가 있는 경우 (사이클=데드락인 경우)
- 프로세스에서 자원 요청이 들어오면 요청 간선과 예약 간선을 추가한다.
- 할당 간선 (R→P) : 자원이 프로세스에 배정됨
- 요청 간선 (P→R) : 프로세스가 지금 자원을 요청함
- 예약 간선 (P⇢R) : 이 프로세스가 미래에 이 자원을 요청할 수도 있다
- 요청을 할당(R→P)으로 바꿨을 때 예약간선까지 포함해서 사이클이 형성된다면 데드락 위험이 있다고 판단해 요청을 거절한다.
은행원 알고리즘
자원의 종류마다 여러개의 인스턴스가 있는 경우
- 안전성 알고리즘 :
요청 자원 ≤ 은행 잔고인 (즉 남은 자원으로 완료 가능한) 프로세스를 찾아서 자원을 더 빌려주고, 작업을 완료시켜서 그 프로세스의 자원을 반납 받는다. - 자원 요청 알고리즘 : 매 요청마다 가상으로 할당을 해본 뒤, 3단계 안전성 검사를 돌려서 안전하면 승인하고 불안전하면 요청을 보류하여 대기시킨다
- 한도 심사 : 요청 금액이 대출 한도(처음 요청한 총 금액)를 초과하는지 심사
- 잔고 심사 : 빌려줄 돈이 있는지 심사
- 시뮬레이션 심사 : 이 요청을 승인했을 때 다음 요청들은 어떻게 될지 계산해봄
- 시간 복잡도가
O(N^2)로 운영체제에서 사용하지는 않는다.
탐지 후 회복
- 탐지
- 대기 그래프 (단일 인스턴스) : 자원할당 그래프에서 자원을 제거하고 프로세스 간 대기 관계를 연결해서 사이클을 판단한다.
- 탐지 알고리즘 (다중 인스턴스) : 은행원의 안전성 알고리즘과 유사하지만, 미래 최대 요구(Max)는 고려하지 않고 현재 요청만 판단한다.
- 회복
- 선점을 통한 회복 : 교착 상태가 해결될 때까지 자원을 강제로 한 프로세스에게 몰아주는 방식
- 강제 종료를 통한 회복 : 교착 상태에 놓인 프로세스를 모두 또는 하나씩 강제종료시켜 해결하는 방식
탐지 알고리즘으로 성능 오버헤드가 발생한다. 즉시 자원 할당이 안될 때에만 탐지하거나, 일정 시간 간격, CPU 이용률이 일정 수준 이하일때만 탐지하도록 하더라도 비효율적이기 때문에 실제로 사용되지는 않는다.
