#15. 교착상태(Deadlocks)

- 프로세스는 실행을 위해 여러 자원을 필요로 한다.

  * CPU, 메모리, 파일, 프린터, ......

  * 어떤 자원은 갖고 있으나 다른 자원은 갖지 못할 때 (e.g .. 다른 프로세스가 사용 중) 대기해야

  * 다른 프로세스 역시 다른 자원을 가지려고 대기할 때 교착상태 가능성!

 

- 교착상태 필요조건 (Necessary Conditions)

  * Mutual Exclusion (상호배타)

  * Hold and wait (보유 및 대기)

  * No Preemption (비선점)

  * Circular wait (환형대기)

 

 자원(Resources)

- 동일 자원

  * 동일 형식 (type) 자원이 여러 개 있을 수 있다. (instance)

  * 예: 동일 CPU 2개, 동일 프린터 3개 등

- 자원의 사용

  * 요청 (request) -> 사용 (use) -> 반환 (release)

- 자원 할당도 (Resource Allocation Graph)

  * 어떤 자원이 어떤 프로세스에게 할당되었는가?

  * 어떤 프로세스가 어떤 자원을 할당 받으려고 기다리고 있는가?

  * 자원: 사각형, 프로세스: 원, 할당: 화살표

 

- 교착상태 필요조건

  * 자원 할당도 상에 원이 만들어져야 (환형태기)

  * 충분조건은 아님!

- 예제 : 식사하는 철학자 문제

 

교착상태 처리

- 교착상태 방지

  * Deadlocks Prevention

- 교착상태 회피

  * Deadlock Avoidance

- 교착상태 검출 및 복구

  * Deadlock Detection & Recovery

- 교착상태 무시

  * Don`t Care

 

 

교착상태 방지

- Deadlock Prevention

- 교착상태 4가지 필요조건 중 한 가지 이상 불만족

  * 상호배타 (Mutual exclusion)

  * 보유 및 대기 (Hold and wait)

  * 비선점 (No Preemption)

  * 환형 대기 (Circular wait)

 

 

(1) 교착상태 방지

- 상호배타 (Mutual exclusion)

  * 자원을 공유 가능하게; 원천적으로 불가능하다. (자원을 공유하는 것이 가능한가? CPU 서비스 역시 시간을 두고 switching을 할 뿐, 어느 한 순간에 동시에 사용하지 못한다.)

- 보유 및 대기 (Hold & Wait)

  * 자원을 가지고 있으면서 다른 자원을 기다리지 않게

  * 예: 자원이 없는 상태에서 모든 자원 대기, 일부 자원만 가용하면 보유 자원을 모두 놓아주기 (식사하는 철학자 문제 개선한 방식, 1명의 철학자가 왼쪽 젓가락을 잡고 오른쪽 젓가락을 잡으려 했는데, 오른쪽 젓가락을 누군가 이미 잡고있어서 왼쪽 젓가락을 놓아버린다. 근대 이러면 특정 철학자가 굶어 죽을 수 있다. )

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

- 비선점 (No preemptive)

  * 자원을 선점 가능하게, 원천적 불가할 수도 (예: 프린터)

- 환형대기 (Circular wait)

  * 예: 자원에 번호부여; 번호 오름차순으로 자원 요청 (식사하는 철학자 문제를 생각해보면 모든 철학자는 왼쪽, 오른쪽 젓가락 순으로 들지만, 한 철학자만 오른쪽, 왼쪽으로 들게 되므로 원형이 만들어지지 않는다.)

  * 단점: 자원 활용을 저하

 

 

(2) 교착상태 회피

- Deadlock Avoidance

  * 교착상태 = 자원 요청에 대한 잘못된 승인 (= 은행파산 : 은행에서 돈을 빌려주는데 액수를 잘못 빌려주게 되면 잘못하면 부도가 날 수 있다. (교착상태))

(방지(prevention)와 달리 교착상태를 다른 관점으로 봄.) 

- 예제

  * 12개의 magnetic tape 및 3개의 process

  * 안전한 할당 (Safe allocation)

Process	Max needs	Current needs
P0	10	5
P1	4	2
P2	9	2

(표대로 mt를 9개를 나눠줘도 3개가 남으므로 부도가 나지 않는다. 이 요청에 대해서는 safe allocation이라고 볼 수 있을까? 그냥 보기에는 안전해 보인다. 왜? mt를 9개를 할당하고 아직 남아있기 때문에 생각해보자. 5개 2개 2개 할당한 것이 진짜 safe allocation이 맞는지!! 

우선 P1의 경우 2개만 더 할당해주면 처리가 끝날 수 있다. 그리고 OS는 2개 할당할 여력이 있다. 2개를 할당하여 최대 할당을 맞춰주고 P1이 끝나면 사용중이던 리소스(magnatic tape)을 반환한다. 이러면 OS가 가지고 있는 tape는 5개가 된다. 이제 P0에게 해당 tape를 전부 할당해주고 P0가 끝나고 나면 10개가 된다. 마지막으로 P2에게 할당해주면 정상적으로 P0, P1, P2의 처리가 종료된다.

이러한 관점에서 볼 때 지금 5, 2, 2 로 자원 할당을 한 것은 Safe allocation이라고 볼 수 있다.)

 

- 예제

  * 12개의 magnetic tape 및 3개의 process

  * 불안전한 할당 (Unsafe allocation)

Process	Max needs	Current needs
P0	10	5
P1	4	2
P2	9	3

(이렇게 할당되면, 현재 OS가 가지고있는 tape은 2개이다. P1에게 최대치를 맞춰서 P1 프로세스가 종료되면

가지고 있던 tape를 반환하는데, 이제 OS가 가지고 있는 tape는 4개가 된다. 문제는 여기서부터이다.

P0에서 5개가 더 필요한데 현재 OS가 가지고 있는 tape은 4개뿐이므로 교착상태에 빠진다. (P2는 당연히 처리 안됨.) 즉, OS에서 지금 P2로 tape를 3개 주면 안됬었다....) 

- 운영체제는 자원을 할당할 때 불안전 할당 되지 않도록 해야 한다.

  * 불안전 할당 -> 교착상태

  * 대출전문 은행과 유사한 문제 해결 방식: Banker`s Algorithm

 

 

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

 - Deadloc Detection & Recovery

  * 교착상태가 일어나는 것을 허용

  * 주기적 검사

  * 교착상태 발생 시 복구

- 검출

  * 검사에 따른 추가 부담 (overhead): 계산, 메모리

- 복구

  * 프로세스 일부 강제 종료

  * 자원 선점하여 일부 프로세스에게 해당

(단점 : deadlock을 검출하기 위한 overhead가 크고, Recovery를 하려면 주기적으로 Deadlock상태가 발생하기 전 상태를 기억을 해놔야 한다. 따라서 비용이 많이 드는 방식이다. 그런데 이런 복구하는 작업도 불가능할 때도 있다. 이럴때는 하는 수 없이 한 프로세스를 강제종료 시키거나, 선점방식으로 자원을 강제로 뺏는 방법도 될 수 있다. )

 

 

(4) 교착상태 무시

- 교착상태가 실제로 잘 일어나지 않는다.

  * 4가지 필요조건이 모두 만족해야 하며, 반드시 일어나는 것도 아니므로.

  * 따라서 그냥 교착상태를 무시하자. 이것 역시 하나의 방법이다.

  * 교착상태 발생 시 재시동 (PC 등 가능)