[운영체제(OS)] 8-3) 교착상태(Deadlock) 탐지, 회복

---

앞서서 배운 교착상태 방지, 회피 알고리즘을 사용하지 않을 경우에는 교착상태가 발생할 수 있으므로 탐지, 회복 알고리즘이 필요합니다.

---

1. 교착상태(Deadlock) 탐지

: 탐지 알고리즘은 교착상태가 얼마나 자주 일어나는지, 교착상태가 발생하면 몇 개의 프로세스가 연루되는지를 고려해야 합니다.

교착상태가 자주 일어난다면 탐지 알고리즘도 자주 돌려야하는데, 시간이 오래 지나면 못 쓰는 리소스가 묶이고 연루되는 스레드의 수가 늘어날 수 있기 때문입니다.

교착상태가 일어나는 시점 = 어떤 스레드의 자원 요청이 만족되지 못하는 시점 입니다. 극단적으로 스레드의 요청이 만족되지 못할 때마다 탐지 알고리즘을 돌리는 방법도 있습니다.

 

1) 각 Resource type이 한 개씩만 있는 경우

: 대기 그래프(wait-for graph)를 이용. 시스템은 대기 그래프를 유지할 필요가 있고, 주기적으로 사이클 탐지 알고리즘을 호출합니다.

(a)는 자원 할당 그래프, (b)는 a에 대응되는 대기 그래프

 

2) 각 Resource type이 여러개인 경우

: 은행원 알고리즘과 유사한 자료구조를 사용해야 합니다.

• Available : 리소스가 종류별로 몇 개 가용한지 [m]
• Allocation : 각 스레드에 할당되어 있는 리소스의 수 [n][m]
• Request : 각 스레드가 요청 중인 리소스의 수 [n][m]

---

2. 교착상태(Deadlock) 회복

: 교착상태 회복에는 수동적인 방법과 자동적인 방법이 있습니다. 수동적인 방법은 운영자가 수작업으로 처리하는 것이고, 자동적인 방법은 프로세스를 종료시키거나 리소스를 선점하는 것입니다.

 

1) 프로세스 종료(Process Termination) : 종료된 프로세스에게서 리소스를 모두 회수합니다. 교착상태의 프로세스를 모두 종료시키는 방법과 교착상태가 제거될 때까지 한 프로세스씩 종료시키는 방법이 있습니다.

- 모두 종료 : 진행중인 모든 프로세스를 종료시키므로 비용이 커집니다.

- 한 프로세스씩 종료 : 프로세스를 하나 종료시킬 때마다 탐지 알고리즘으로 확인하기 때문에 상당한 오버헤드를 유발할 수 있습니다. 어떤 프로세스를 먼저 종료시킬지에 대한 기준은 다음과 같습니다.

• 프로세스의 우선순위
• 프로세스가 지금까지 수행된 시간, 종료할 때까지 더 필요한 시간
• 프로세스를 종료하기 위해 필요한 추가 리소스의 수
• 프로세스가 사용한 리소스 타입과 수

2) 리소스 선점(Resource Preemption) : 교착상태가 깨질 때까지 프로세스로부터 리소스를 선점해 다른 프로세스에게 넘겨줍니다. 이를 위해 다음과 같은 사항을 고려해야 합니다.

• 희생자 선택(Selection of a victim) : 어떤 프로세스의 리소스를 줄 것인가
• 후퇴(Rollback) : 리소스를 줄 프로세스를 어떻게 할 것인가
• 기아 상태(Starvation) : 기아 상태가 발생하지 않는 것을 어떻게 보장할 것인가