[OS] 교착상태 (Dead Lock)

교착상태(Dead Lock)란,

: 여러 프로세스가 서로의 작업이 끝나기만을 기다리며 작업을 진행하지 못하게 되는 상태

 

ex) 식사하는 철학자 문제

: 왼쪽->오른쪽 순으로 포크를 집어야 식사를 시작할 수 있다는 조건이 있을 때, 5명의 철학자는 각자 왼쪽의 포크를 집은 뒤 오른쪽 포크를 무한정 기다리게 되어 굶어 죽을것이다. =>교착상태 

---

교착상태 필요조건

: 4가지를 모두 충족할 때 교착상태가 발생한다.

 

o 상호배제

: A가 사용중인 자원을 B가 동시에 사용할 수 없다.

o 비선점

: A가 사용중인 자원을 B가 뺏을 수 없다.

o 점유와 대기

: 자원1을 사용(점유)하면서 자원2를 필요(대기)로 하는 상황이다.

o 원형대기

: 점유와 대기상태의 프로세스들의 요청이 원형을 이룬다.

---

교착상태 해결방법

 

o 교착상태 예방

: 필요조건 4가지 중 하나를 무력화 하여 교착상태 발생을 예방한다.

but 상호배제나 비선점의 특징을 변경하거나, 대기가 발생하지 않도록 모든 필요자원을 미리 점유하거나, 원형 대기를 예방하기 위해 한 방향으로만 자원에 접근하도록 하는것은 문제가 많아 현실적으로 불가능하다.

 

o 교착상태 회피

: 자원 할당을 조절해서 교착상태를 피한다.

ex) 은행원 알고리즘 ( 은행원이 고객의 대출금액을 미리 확인하여 대출이 가능여부를 판단한다)

but 각 프로세스가 자원을 얼마나 사용할지 미리 아는 것이 어려워 실효성이 떨어진다.

 

o 교착상태 검출과 회복

: Timeout을 설정하거나 자원할당그래프를 확인하여 교착상태가 발생했는지 검출한다.

교착상태의 모든 프로세스 or 우선순위가 낮고, 작업시간이 짧고, 사용 자원수가 적은 순으로 프로세스를 종료하여 교착상태를 회복한다.

but Timeout이 꼭 교착상태 때문에 발생한 것이 아닐 수도 있다. (ex- 분산시스템의 경우 Timeout의 사유파악이 더 어려움)

but 자원할당그래프를 업데이트하는 추가작업으로 오버헤드 발생 가능성이 있다.