OS : 교착상태(dead lock)

교착상태란?

---

2개 이상의 작업이 서로 끝나기만을 기다리고 있기 때문에 어느것도 실행되지 않는 상태를 말한다.

다중 프로그래밍 환경에서 자주 발생하며, 이를 해결하기 위한 일반적인 해결방안은 아직 존재하지 않는다.

교착상태의 조건

• 상호배제(Mutual Exclusion) : 프로세스들이 원하는 자원에 대해 상호 배타적인 통제권을 요구한다.
• 점유대기(Hold and Wait) : 프로세스가 할당된 자원을 점유하고 있는 상태에서 다른 자원을 기다린다.
• 비선점(Non-Preemptive) : 프로세스가 점유권을 넘겨주기 전까지 점유권을 빼앗을 수 없다.
• 순환대기(Circular Wait) : 프로세스는 순환적으로 다음 프로세스가 원하는 자원을 가지고 있다.

위 4가지 조건을 모두 충족해야만 교착상태가 발생한다.(ex : 식사하는 철학자)

교착상태 해결 방법 :

예방

상호배제 조건 제거 : 비공유 자원

점유대기 조건 제거 : 프로세스가 자원을 요구할 때 자원을 점유하지 않도록 한다.

비선점 조건 제거 : 비선점 프로세스에 대해 선점 가능한 프로토콜을 만들어준다.

순환대기 조건 제거 : 자원 종류 순서대로 요청하게 한다.

예방의 단점 : 장치 사용율, 시스템 처리율이 떨어진다.

회피

동적으로 자원 할당 상태를 조사하여 교착상태를 피한다.

미래의 자원 할당 해지를 감지.

안전한 상태(safe state)^[각주:1]를 유지할 수 있는 자원 요구만 들어준다.(자원 이용율이 낮아지는 단점)

종류별 자원이 한개 : 자원 할당 그래프 알고리즘^[각주:2]

종류별 자원이 여러개 : 은행원 알고리즘

탐지

교착상태 탐지 알고리즘과 회복 알고리즘이 필요하다.

종류별 자원이 한개 : 대기 그래프^[각주:3]

종류별 자원이 여러개 : 은행원 알고리즘^[각주:4]

회복

수동 : operator가 처리

자동 : 교착상태에 있는 프로세스를 종료(전부 다 종료시키는 방법과 하나씩 종료시키는 방법이 있다.)

무시

unix/windows : 1년에 한번 사용자가 재부팅

jvm : 응용 개발자에게 맡김

1. 일련의 순서대로 자원을 할당해도 교착상태가 일어나지 않는 상태 [본문으로]
2. 자원 할당 그래프 + 예약 간선 프로세스가 자원을 요청하면 예약간선이 요청간선으로 바뀐다. [본문으로]
3. 교착상태인지 탐지할 수 있는 그래프 cycle이 있으면 교착상태에 있다. os는 대기그래프를 유지하며 주기적으로 cycle이 있는지 탐지하는 알고리즘을 수행한다. [본문으로]
4. 프로세스가 자원을 요구할 때 시스템은 자원을 요구해도 교착상태가 일어나지 않는지를 미리 검사한 후 자원을 할당하는 알고리즘 각 프로세스는 실행하기 전에 필요한 자원 형태의 최대수를 선언 시스템은 자원을 할당한 뒤에도 안전한 상태에 있는지를 검사하여 안전한 상태에 있으면 할당하고 아니면 대기시킨다. 은행원 알고리즘의 한계 할당할 수 있는 자원이 일정해야한다. 일정한 사용자수에서만 사용 가능 알고리즘을 유한시간 내에 수행해야 한다. 유한시간 내에 자원을 되돌려 받아야 한다. 최대 자원을 미리 등록해야 한다. -> 제한적인 상황에서만 사용할 수 있다. [본문으로]