DeadLock, 교착상태

DeadLock, 교착 상태

두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태로, 무한히 다음 자원을 기다리게 되는 상태를 말한다.

 

이는 시스템적으로 한정된 자원을 여러 군데에서 사용하려고 할 때 발생한다. 마치 외나무 다리의 양 끝에서 서로가 비켜주기를 기다리고 있는 것과 같다.

Deadlock이 일어나는 경우

프로세스 1과 2가 자원 1, 2를 모두 얻어야 한다고 가정해보자.

 

t1 : 프로세스1이 자원 1을 얻음, 프로세스 2가 자원 2를 얻음

t2 : 프로세스1은 자원 2를 기다림, 프로세스 2는 자원 1을 기다림

 

현재 서로 원하는 자원이 상대방에게 할당되어 있어서, 두 프로세스는 무한정 wait 상태에 빠진다. 이것이 바로 Deadlock!

주로 발생하는 경우 : 멀티 프로그래밍 환경

멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황이 발생한다.

 

한 프로세스가 자원을 요청했을 때, 동시에 그 자원을 사용할 수 없는 상황이 발생할 수 있는데, 이때 프로세스는 ‘대기’ 상태로 들어간다. 대기 상태로 들어간 프로세스들이 실행 상태로 변경될 수 없을 때 ‘교착 상태’가 발생한다.

---

Deadlock 발생 조건

네 가지 모두 성립해야 데드락이 발생한다. 하나라도 성립하지 않으면 발생하지 않는다.

상호 배제 Mutual exclusion

 

자원은 한 번에 한 프로세스만 사용할 수 있다.

점유 대기 Hold and wait

 

최소한 하나의 자원을 점유하고 있으면서, 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 한다.

선점 불가 No preemption

 

다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없다.

자원을 획득 할 수 있는 유일한 방법은 다른 어떤 프로세스도 해당 자원을 점유하고 있지 않을 때 뿐이다.

순환 대기 Circular wait

 

프로세스 집합에서 순환 형태로 자원을 대기하고 있어야 한다. 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.

---

Deadlock 처리

Deadlock을 처리하는 방법으로는 Deadlock이 발생하기 전 예방, 회피하거나, Deadlock이 발생했을 경우 탐지하고 회복하는 네 가지 방식이 존재한다.

---

예방 prevention

데드락 발생 조건 중의 하나를 제거하여 데드락이 발생하는 상황 자체를 막아 버린다.

상호 배제 방지

 

여러 프로세스가 공유 자원을 사용하게 한다.

점유 대기 방지

• 프로세스 실행 전 모든 자원을 할당하여 대기를 발생시키지 않는다.?
• ⇒ 자원 낭비 발생
• 자원을 점유하지 않고 있을 때에만 다른 자원을 요청할 수 있도록 한다.
• ⇒ 기아 상태 발생

비선점 방지

• 모든 자원에 대한 선점을 허용한다.
• 자원을 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원을 반납한다.

순환 대기 방지

 

자원에 고유번호를 할당하여 번호 순서대로 자원을 요구하도록 한다.

⇒ 자원 낭비

 

하지만 이 방식을 사용하면, 프로세스는 당장 사용하지 않는 자원을 점유하고 있어야 하거나, 이미 할당 되었던 자원을 반납해야 하는 등의 전체 성능을 낮추어야 하는 단점이 있다.

---

회피 avoidance

자원 요청 시 자원이 어떻게 요청될 지에 대한 추가 정보(알고리즘마다 다름)를 제공하도록 요구하는 것으로, 시스템에 순환 대기가 발생하지 않도록 자원 할당 상태를 검사한다.

 

회피 방식에는 두 가지 방식이 있다.

은행원 알고리즘, Banker’s Algorithm

 

은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 데서 유래한 알고리즘이다.

📝 은행원 알고리즘 Banker’s Algorithm

프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안전 상태로 남아있게 되는지 사전에 검사하여 교착 상태를 회피할 수 있다.

사전 검사에서 안 상태면 자원을 할당하고, 아니면 다른 프로세스들이 자원을 해지할 때까지 대기한다.

 

그럼 위에서 안정 상태라는 게 무엇일까? 일단 한 줄로 정리하면 다음과 같다.

❓ 안전 상태란?

시스템이 각 프로세스들에게 
데드락을 피할 수 있는 안전한 순서(saf sequence)로 자원을 배분 할 수 있는 상태이다.

 

알고리즘 예시를 보며 좀 더 쉽게 이해해보자.

 

예를 들어 시스템에 12개의 자원과 프로세스 P0, P1, P2 이렇게 3개가 있다고 가정하자. 프로세스는 자기가 맡은 작업을 처리하기 위해 아래와 같은 개수의 자원을 필요로 한다.

• P0은 작업을 마치기 위해 10개의 자원이 필요하다고 시스템에 요청했다.
• P1은 작업을 마치기 위해 4개의 자원이 필요하다고 시스템에 요청했다.
• P2는 작업을 마치기 위해 9개의 자원이 필요하다고 시스템에 요청했다.

이렇게 프로세스가 작업을 마치기 위해 총 몇 개의 자원이 필요한 지가 위에서 언급한 '자원 요청시 요구 되는 추가 정보'의 일종이다. 아무튼 각 프로세스들이 작업을 마치기 위해 필요한 자원은 위와 같고, 특정 시점 'T0'에서 시스템이 파악한 자원 할당 상태는 아래와 같다.

• P0은 지금 5개의 자원을 가지고 있다. 작업을 마치기 위해 5개의 자원이 더 필요 하다.
• P1은 지금 2개의 자원을 가지고 있다. 작업을 마치기 위해 2개의 자원이 더 필요 하다.
• P2은 지금 2개의 자원을 가지고 있다. 작업을 마치기 위해 7개의 자원이 더 필요 하다.
• 시스템에는 현재 12개의 자원 중 3개의 자원이 남아 있다.

이 상태에서 시스템은 P1 -> P0 -> P2 순서로 자원을 할당하여 안전 상태를 유지 할 수 있다.

1. 시스템에는 3개의 여유 자원이 있다. P1이 필요 자원 2개를 할당 받아 작업을 처리하고 자신이 가진 자원 4개를 반납한다.
2. 시스템에는 5개의 여유 자원이 있다. P0이 필요 자원 5개를 할당 받아 작업을 처리하고 자신이 가진 자원 10개를 반납한다.
3. 시스템에는 10개의 여유 자원이 있다. P2이 필요 자원 7개를 할당 받아 작업을 처리하고 자신이 가진 자원 9개를 반납한다.

이로써 데드락 상황이 발생하지 않고 모든 프로세스들이 작업을 완료 했다.

 

이렇게 데드락 회피는 프로세스가 자원을 요청 할 때 마다 '안정 상태'를 유지 할 수 있을 경우에만 자원을 할당하고, 그렇지 않을 경우 프로세스를 기다리게 함으로써 데드락을 피해간다.

 

만일 시스템이 위와 다른 순서로 자원을 할당 한다고 하면 모든 프로세스들이 작업을 마치기 위한 자원을 제대로 할당 받지 못하는 경우가 발생할 수 있다. 이를 안전하지 않은 상태(Unsafe state)라고 하며 데드락이 발생할 가능성이 있는 상태다. 주의할 점은 안전하지 않은 상태라고 무조건 데드락이 발생하는 것은 아니다.

 

자원 할당 그래프 알고리즘, Resource-Allocation Graph Algorithm

 

알고리즘 설명에 들어가기 전 알아야 할 점은, 하나의 자원 유형에 대해 여러 개의 인스턴스가 존재할 수 있다는 것이다.

📝 자원 할당 그래프 알고리즘 Resource-Allocation Graph Algorithm

자원과 프로세스에 대해 요청 간선, 할당 간선, 예약 간선을 적용하여 교착 상태를 회피하는 알고리즘이다.

 

해당 알고리즘에서는 다음과 같은 간선이 필요하다. 즉, 이 알고리즘에서는 간선 정보가 위에서 언급한 '자원 요청시 요구 되는 추가 정보'의 일종이 된다. 각 간선은 다음과 같은 정보를 나타낸다.

• 요청 간선 : 프로세스가 자원의 인스턴스 하나를 요청했음을 나타낸다.
• 할당 간선 : 자원의 한 인스턴스가 프로세스에 할당되어 있음을 나타낸다.
• 예약 간선 : 미래에 언젠가 자원을 요청할 수도 있음을 나타낸다.

프로세스가 자원을 요구 시, 요청 간선을 할당 간선으로 변경했을 때 사이클이 생성되는지 확인한다.

• 사이클이 생성된다면 → 불안전 상태
  • 자원에 하나의 인스턴스만 존재 ⇒ 교착 상태 발생할 것!
  • 자원에 여러 인스턴스가 존재 ⇒ 교착 상태 가능성
• 사이클이 생성되지 않는다면 안전 상태로 교착 상태가 발생하지 않을 것임으로 자원을 할당한다.

---

탐지 Detection

자원 할당 그래프를 통해 교착 상태를 탐지한다.

 

자원 요청 시, 탐지 알고리즘을 실행시키기 때문에 그에 따른 오버헤드가 발생한다.

---

회복 Recovery

교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시킨다.

• 프로세스 종료 방법
  • 교착 상태의 프로세스를 모두 중지시킨다.
  • 교착 상태가 제거될 때까지 프로세스를 하나씩 중지시킨다.
• 자원 선점 방법
  • 교착 상태의 프로세스는 일시 정지시키고, 해당 프로세스가 점유하고 있던 자원을 선점해 다른 프로세스에게 할당한다.
  • 우선 순위가 낮은 프로세스나 수행 횟수가 적은 프로세스 위주로 프로세스 자원을 선점한다.

---

참고자료

https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer Science/Operating System/DeadLock.md

데드락(Deadlock) 개념 정리