교착상태 처리

교착상태를 처리하는 방법에는 4가지가 있다.

1. 교착상태 방지(Deadlock Prevention)

2. 교착상태 회피(Deadlock Avoidance)

3. 교착상태 검출 및 복구(Deadlock Detection )

4. 교착 상태 무시 (Don't Care)

 

1. 교착상태 방지

교착상태의 4가지 필요조건 중 한 가지 이상 불만족하게 만들어 교착상태를 방지한다.

1) 상호배타조건을 불만족

프로세스끼리 자원을 공유가능하도록 만든다. 그러나 이 방법은 원천적으로 불가능할 수도 있다.

2) 보유 및 대기 조건을 불만족

자원을 가지고 있으면서 다른 자원을 기다리지 않게 만든다. 예를 들어 자원이 없는 상태에선 모든 자원을 대기하게 만들 수 있다. 그래서 일부 자원만 접근가능하다면 프로세스가 보유하고 있는 자원을 모두 놓아주도록 만든다.

 

단점 : 자원 활용률 저하, 기아(starvation)

- 자원을 보유하지 못한채 계속 기다리다 굶어죽을 수 있다.(=무한대기)

3) 비선점 조건을 불만족

자원을 선점가능하도록 만든다. 즉, 다른 프로세스의 자원을 뺏어올수 있도록 만든다. 그러나 이 방법 역시 원천적으로 불가능할 수도 있다.(예: 프린터)

4) 환형대기 조건을 불만족

환형대기 조건을 불만족하게 만든다. 한 가지 방법으로 자원에 번호를 부여한다음 번호 오름차순으로 자원을 요청하는 구현한다.

단점 : 자원 활용률 저하

식사하는 철학자 예시

식사하는 철학자 문제의 경우 P0, P1, P2, P3의 경우 자원오름차순인 왼쪽 젓가락 → 오른쪽 젓가락 으로 진행한지만,

P4의 경우 오른쪽 젓가락이 0, 왼쪽 젓가락이 4이므로 오른쪽 젓가락 → 왼쪽 젓가락 순으로 진행하게 된다.

이를 통해 환형대기가 발생하는 걸 방지할 수 있다.

---

2. 교착상태 회피

이 방법에선 교착상태를 자원 요청에 대한 잘못된 승인으로 본다.(= 은행 파산)

1) 예제

12개의 Magnetic tape 및 3개의 process가 있다고 가정해보자.

안전한 할당(Safe allocation) - 자원이 필요한 모든 프로세스에게 바로바로 자원을 할당해줘도 정상적으로 동작하게 된다.

안전한 할당 예시

2) 또 다른 예제

또 다른 경우를 예로 들어보자. 12개의 자원을 3개의 프로세스에게 분배한다고 가정한다.

  - 1. 처음에 Current needs에 표시된대로 5+2+3=10개의 자원을 분배한다. 이제 남은 자원은 2개이다.

  - 2. P0은 추가로 5개의 자원을, P1은 추가로 2개의 자원을, P2는 추가로 6개의 자원을 요구할 것이다.

  - 3. 남은 자원은 2개밖에 없기 때문에 P1에게만 추가자원을 분배할 수 밖에 없다.

  - 4. P1의 프로세스가 모두 끝나 4개의 자원이 반환되더라도 P0과 P2는 자원이 부족하여 프로세스를 끝낼 수 없다.

=> 불안전한 할당(Unsafe allocation)

불안전한 할당 예시

운영체제는 자원을 할당할 때 불안전할당이 되지 않도록 해야한다. 불안전할당은 곧 교착상태로 이어지게 되기 때문이다. 이 예는 대출전문은행과 유사하다. (Banker's Algorithm)

 

---

3. 교착상태 검출 및 복구

교착 상태가 일어나는 것을 허용하되, 주기적으로 검사하여 교착상태 발생이 확인되면 이를 복구한다.

그러나 검출시 계산, 메모리와 같이 추가부담이 발생한다.(overhead)

검출이 끝난 뒤 교착상태를 복구할 경우 1)프로세스의 일부를 강제 종료하거나, 2)자원을 선점하여 일부 프로세스에게 할당하는 방식으로 문제를 해결할 수 있다.

 

---

4. 교착상태 무시

교착 상태는 실제로 잘 일어나지 않으므로 교착상태 처리를 따로 하지 않는다.

만일 교착 상태가 발생하게 되면 재시동하는 방식으로 문제를 해결한다. (ex. PC 재부팅)