Deadlocks

Deadlock Problem

A Set of blocked process

- Each Member is holding a resource 

- Each Member is waiting to acquire a resource held by another process in set.

두 개 이상의 자원이 서로 끝나기만을 상대방의 작업이 끝나길 기다리고 있는 상태. 무한 교착상태라고 한다.

MultiProgramming 환경에서 자주 발생

Deadlock 발생 조건 

(4가지 모두 만족하면 발생할 가능성이 있다는 것임) 

(조건을 모두 만족한다고 Deadlock가 발생하는 것은 아님)

- Mutual Exclusion : 한 프로세스는 한 리소스만 사용할 수 있다.

- Hold and wait : 하나 이상의 리소스를 소유하고 있으면서 다른 프로세스가 가지고 있는 리소스를 기다린다.

- No preemption : 중간에 다른 프로세스로 순서가 바뀌지 않음

- Circular wait : Hold & wait 관계의 프로세스가 Circle을 이룬다.

1. Deadlock Prevention

- 4가지 조건 중 1가지만 막아도 Deadlock이 발생되지 않음

- Mutual Exclusion : 공유해야 하는 리소스가 아니면 리소스를 hold하지 않음.

불가능

- Hold and wait : 시작 하기 전, 모든 자원을 미리 할당 받는다. 리소스가 사용되지 않을때만, 프로세스가 요청하는 것을 허용

 starvation

- No preemption : 리소스를 확인해서 모두 얻을 수 있는 상태가 되면 프로세스를 다시 시작

- Circular wait : 접근 순서를 청해서 사용하게 한다.

2. Deadlock Avoidence (7장 PPT 32쪽 참고)

- 요청하는 자원의 갯수 > 사용 가능한 자원의 갯수             => Deadlock가 일어날 수 있으므로 잠시 멈춘다.

- 리소스의 Maximum number (최대 얼마큼 쓸 것이다) 라는 것을 알고 있어야함

- Resource-allocation graph - single instance

- banker's algorithm - multi instance

3. Deadlock Recovery

- process termination

- checkpoint & roll back