[운영체제] 데드락 (Deadlock)

데드락이란?

여러 프로세스들이 서로가 가진 자원을 기다리며 block된 상태입니다. 기본적으로 프로세스는 필요 자원 중 가능한 자원을 획득한 후, 나머지 자원을 획득할 때까지 기존 자원을 놓지 않고 기다리기 때문에 이러한 문제가 발생할 수 있습니다. 여기서 자원이란 I/O device, CPU와 같은 하드웨어 자원과 semaphore와 같은 소프트웨어 자원을 포함하는 개념입니다.

Deadlock 발생의 4가지 조건

• Mutual Exclusion
  • 하나의 자원은 한 시점에서 오직 하나의 프로세스만 사용할 수 있고, 동시에 두 개 이상의 프로세스가 사용할 수 없습니다.
• No Preemption
  • 프로세스는 자원을 스스로 내려놓을 뿐 뻇기지 않습니다.
• Hold and Wait
  • 프로세스는 필요한 모든 자원을 획득할 때까지, 기존에 획득해둔 자원을 스스로 반납하지 않습니다.
• Circular wait
  • 자원을 기다리는 프로세스 간세 사이클이 형성됩니다. 예를 들어, 프로세스i는 A자원이 필요한데 이 자원은 프로세스j가 가지고 있고, 동시에 프로세스j는 A와 함께 B자원이 필요한데 이는 프로세스i가 깆고 있는 경우입니다. 누군가 포기하기 전에는 데드락이 풀리지 않습니다.

Resource-Allocation Graph

자원을 기다리는 프로세스 간의 사이클이 있는지 확인하기 위해, 자원할당 그래프를 활용합니다. 이는 자원과 프로세스 간의 관계를 표시합니다.

원은 프로세스이고 네모는 자원이며, 네모 안의 점은 한 자원의 instance 개수입니다. 자원에서 시작하는 화살표는 가리키는 프로세스에게 할당되었다는 뜻이고, 프로세스에서 시작하는 화살표는 가리키는 자원이 필요하다는 뜻입니다.이 그래프의 화살표를 따라가다가 이미 지나온 자원이나 프로세스를 만나면 사이클이 있다는 것입니다.

Dead락을 확인하는 방법

1. 그래프에 cycle이 있으며 deadlock이 아니다.
2. 그래프에 cycle이 있고, 앞으로도 가용자원이 없으면 dedlock이다.

앞으로도 가용자원이 없다는 뜻은, 프로세스가 필요한 모든 자원을 할당 받은 경우 사용을 하고 반납할 것이기 때문에, 앞으로 가용 상태가 될 자원이다. 위의 오른쪽 그래프에서 R1과 R2는 각가 P2와 P4가 사용하고 반납할 자원이기 때문에, 이 그래프 deadlock이 아니다.

Deadlock을 처리하는 방법

Deadlock Prevention

자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것입니다.

• Mutual Exclusion
  이것은 어쩔 수 없이 반드시 성립해야합니다.
• Hold and Wait
  프로세스가 필요 자원 중 일부를 가지고 요청하지 않고, 모두 없는 상태로 요청하고 한번에 모두 할당받을 수 있는 경우에만 할당하는 것입니다.
  자원이 필요한 경우, 가지고 있는 자원을 모두 반납한 후 다시 요청하는 방법으로 구현할 수 있습니다.
• No Preemption
  어떤 자원을 기다려야하는 경우, 이미 보유한 자원을 뻇기게 합니다. CPU나 Memory처럼 뻇기는 당시의 상태를 쉽게 저장하고 다시 복구할 수 있는 자원에만 적용해야합니다.
• Circular Wait
  모든 자원의 할당 순서를 미리 정하는 방법으로 구현할 수 있습니다.단점이 방법들은 추가적인 일(확인하고, 자원을 반납하고 다시 획득하는 등) 등 오버헤드가 발생하기 때문에 비효율적입니다.

Deadlock Avoidance

매우 보수적인 방법으로 사전에 한 프로세스가 모든 라이프 사이클 동안 필요한 자원을 미리 조사한 후, 데드락의 가능성이 있으면 자원을 할당하지 않는 방법입니다. 데드락의 가능성을 판단하는 방법으로 Banker 알고리즘이 있습니다.

위의 그림에서 Allocation은 지금 할당된 자원이고, Max는 한 프로세스가 필요한 총 자원, Available은 현재 가용자원, Need는 앞으로 필요한 자원(어느 시점에 필요할지는 모른다.)입니다. 여기서 어떤 프로세스가 자원을 요청한다면, 요청한 만큼을 보는 것이 아니라 해당 프로세스의 Need와 Available를 비교하여, 현재 가용자원으로 앞으로 요청할지도 모르는 모든 요청까지 처리할 수 있을 때만 자원을 할당합니다.
이 방법은 매우 안전하지만, 자원이 남아있고 데드락이 발생하지 않을 수 있을지라도, 자원을 할당하지 않는 경우가 있기 때문에 상당히 비효율적입니다.

Deadlock Detection and Recovery

이 방법은 위의 두 방법과는 다르게 데드락을 허용하고, 발생했을 때 이를 감지하여 복구하는 방법입니다. 위와 비슷한 방법으로 deadlock을 감지할 수 있는데, 다만 낙관적인 방법을 적용합니다.

Detection

1. 가용자원으로 처리할 수 있는 리퀘스트는 처리한다. 그후 처리한 프로세스의 자원을 반납한다.
   P0과 P2의 요청을 처리할 수 있음으로, 처리하고, 반납한다. 그러면Allocation Request Available

   	Allocaton	Request	Availabe
   P0	0 0 0	0 0 0	3 1 3
   P1	2 0 0	2 0 2
   P2	0 0 0	0 0 0
   P3	2 1 1	1 0 0
   P4	0 0 2	0 0 2

2. 1번을 모든 요청을 처리하거나, 영원히 못처리하는 것이 확인 될 때까지 반복한다.

   	Allocaton	Request	Availabe
   P0	0 0 0	0 0 0	5 1 3
   P1	0 0 0	0 0 0
   P2	0 0 0	0 0 0
   P3	2 1 1	1 0 0
   P4	0 0 2	0 0 2

Recovery

• 모든 프로세스를 죽이거나
• 프로세스를 하나씩 죽여가면서 데드락이 풀리는지 확인하는 방법.
• 비용을 최소화는 프로세스를 선택하는 로직에서 Starvation이 발생할 수도 있음으로 선정된 횟수를 계산하는 등의 방법을 사용해야합니다.

Deadlock Ignorance

데드락을 방치하는 방법입니다. 제일 무책임하지만, 대부분의 범용 OS에서 선택하고 있는 방법입니다. 이 방법은 위의 오버헤드가 전혀없음으로 가장 효율적인 방법일 수 있습니다. 이 방법에서 데드락이 발생하면, 사용자가 이를 느끼고 직접 강제 종료하는 방법으로 데드락을 해결합니다.

 

참조

운영체제