운영체제 - 7(교착상태)

 

교착상태

 

- Deadlock : 두개 이상의 프로세스가 필요한 자원을 기다리면서 무한정 중지된 상태

 

1. 발생원인 :

제한된 자원에서 프로세스의 이용률을 높이고, 시스템 효율성을 높이려는 과정에서 부작용으로 발생

 

* 프로세스의 자원이용 순서

1) 요청 : 자원요청 -> 자원할당

2) 사용 : 할당된 자원 사용

3) 해제 : 할당자원을 반납 후 종료

 

2. 필요충분조건 :

상호배제 + 점유와 대기 + 비선점 + 순환 대기

 

=> Deadlock이 왜 발생하고, 어디에서 발생하는지 알아야 할 필요가 있다

 

3. 자원할당 그래프

: 프로세스 집합과 자원들로 구성된 간선 집합을 통해 자원과 프로세스 간 관계를 그래프로 나타낸 것

- 이 그래프에서 사이클이 생기면 Deadlock이 발생한 것

P1이 R2를 요청 -> R2는 P2에 할당

P2는 R1를 요청 -> R1는 P1에 할당

사이클이 발생하여 교착상태가 일어났음을 알 수 있다.

 

<자원할당 그래프 Example1>

P1는 R1 요청 -> R1는 P2에 할당

P2는 R3 요청 -> R3는 P3에 할당

Deadlock은 발생하지 않는다

-> P3는 이미 모든 자원이 할당된 상태이므로 P3가 종료되면 P2, P1가 순차적으로 각각 자원을 할당받을 수 있음

-> Cycle 역시 발생하지 않음

 

<자원할당 그래프 Example2>

이 경우 P4가 자원 R2를 해제할 수 있으므로 이 자원이 P3에 할당되면 Deadlock이 발생하지 않음

 

---

교착상태 처리

- Deadlock 처리기법 : 예방, 회피, 탐지, 복구

 

1. Deadlock 예방

: Deadlock의 4가지 필요충분 조건이 발생하지 않도록 하여 Deadlock이 아예 발생하지 않게 한다

 

1) 상호 배제 : 상호 배제가 필요하지 않을 수 있는 상황에서는 가능하나, 자원에 따라 다르므로 상호배제는 무조건 유지

2) 점유와 대기 : 필요한 자원을 한꺼번에 요청하고 다 처리할 때 까지 다른 프로세스 보류

3) 비선점 방지 : 원래는 프로세스가 점유한 자원을 회수할 수 없지만, 회수를 허용하여 자원을 강제로 뺏어올 수 있게 한다.

4) 순환대기 방지 : 모든 자원에 순서를 부여하여 순서 순으로만 자원을 할당하여 Cycle이 발생하지 않게 한다

 

=> 4가지 조건중 3가지를 방지하면 Deadlock이 발생하지 않는다

 

 

2. Deadlock 회피

: 교착 상태가 일어날 확률이 낮은데도 무조건적으로 예방하는 것은 시스템 처리성능 저하의 문제가 발생함

-> Deadlock 발생 가능성을 인정하고 회피대책을 마련하는 것

 

1) 프로세스 시작거부 : 현재 프로세스와 새로 시작할 프로세스의 최대요구량 > 최대값 인 경우 시작거부

2) 자원할당 거부 : 자원 할당시 Deadlock 가능성이 높으면 할당을 거부한다.

(Unsafe/Safe Zone으로 나누어 놓고 Deadlock은 Unsafe Zone에서만 일어난다는것을 착안)

    (1) 자원할당 그래프

    (2) 은행가알고리즘

 

* Safe State

=> Safe한 상태 유지 (Deadlock 발생 x)

 

* Unsafe State

=> Unsafe State

 

 

3. Deadlock 탐지

: 교착상태가 발생하도록 허용하되, 교착상태 발생시 탐지하고 복구

- Deadlock Detection / Deadlock Recovery 알고리즘 두 가지가 필요

 

(1) Multiple instances of resource

- 은행가 알고리즘의 변형알고리즘 활용

- 교착상태 회피의 경우 들어가기전에 교착상태 여부를 판단했으나, 탐지 알고리즘은 우선 들어간 뒤

교착상태가 발생하면 이를 감지한다

 

(2) Single Instance of resource

- wait-for graph 활용 알고리즘

 

* 쇼사니와 포크만의 알고리즘

4. Deadlock 복구

 

1) 프로세스 중단

: 교착상태와 관련된 모든 프로세스를 중단 or 하나씩 선택하여 중단

 

2) 자원선점(강제회수)

: 자원을 강제로 회수하여 교착상태 해결