교착상태 (deadlock)

The Deadlock Problem

Deadlock 발생의 4가지 조건

Resource-Allocation Graph

여기에는 사이클이 없으니 deadlock이 아니다.

자원에서 프로세스로 화살표가 나가는 것은 그 프로세스가 자원을 가지고 있다는 뜻이고 프로세스에서 자원으로 화살표가 나가는 것은 그 프로세스가 자원을 기다리고 있다는 뜻이다.

왼쪽은 데드락이다. 자원이 두 개가 있지만 사이클도 두개다.
오른쪽은 사이클이 있지만, 자원이 두개씩 있기 때문이다. 여분의 자원이 있기 때문에 2번과 4번이 자원을 반납하면 available해진다.

Deadlock의 처리 방법

Deadlock Prevention

Deadlock의 조건 4가지중 하나 이상을 깨는 방법.

mutual exclusion은 막을 수 있는 조건이 아니다.

자원 이용률이 나빠지고, 생기지도 않을 데드락에 많은 제약 조건을 달아놓기 때문에 비효율적이다.

Deadlock Avoidance

프로세스가 평생 쓸 자원을 알고 있다고 가정하고, 문제가 안생기면 할당하는 것이다.

Resource Allocation Graph Algorithm

점선은 그 프로세스가 언젠가 한번은 그 자원을 쓴다는 얘기다.

자원의 인스턴스가 하나씩 있을 때 deadlock avoidance를 위해서 사용하는 알고리즘이다.

unsafe state에 있다고 무조건 deadlock이 발생하는 것이 아니라 가능성이 있는 것이다.

Bankers Algorithm

자원이 남아도 혹시 모를 상황에 대비하여 주지 않기 때문에 비효율적이다.

Deadlock Detection and Recovery

프로세스가 n개일 때 O(n^2)가 걸린다. 점이 n개니 화살표는 최대 n * (n-1)개가 있다.

자원당 인스턴스가 하나 이면 resource-allocation graph로 deadlock detection이 가능하다.

자원당 인스턴스가 여러 개인 경우에 테이블을 그려서 현재 상태가 데드락인지 파악 가능하다.

이전과 다르게 p2도 자원 요청을 했다. 가용자원으로 처리 가능한 있는걸 해결하고 반납받고 다른 것들을 해결하면 된다

Recovery

deadlock에 연루된 것들을 한꺼번에 다 죽일 수도 있고, 하나씩 즉이는 방법이 있다. 이것은 프로세스를 죽이는 방법이고, 또 다른 방법은 자원을 뺏는 방법이다. 자원을 뺏는 것은, 또 같은 패턴으로 문제가 생길 수도 있기 때문에 starvation이 발생할 수도 있다.

Deadlock Ignorance