DeadLock(교착 상태)

DeadLock(교착 상태) 이란?

두 개 이상의 프로세스나 스레드가 상대방의 작업이 끝나기 만을 무한히 기다리고 있다가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태를 말한다. (시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생하게 된다.)

자원 - (하드웨어, 소프트웨어 등을 포함하는 개념)

• I/O 디바이스, CPU cycle, memory space, semaphore 등

Process1 과 Process2가 동시에 Resource1과 Resource2를 모두 얻어야 하는 상황이라고 생각하면

• Process1이 Resource1을 얻은 경우 Process2는 Resource1을 얻을 수 없고 Process2가 Resource2를 가지고 있어서 Process1은 Resource2를 얻을 수 없다.
• Process1 과 Process2는 서로 자원을 얻기 위해서 조금의 양보도 없고 조금 착해서 뺏지도 못하는 애들🥹
• 누가 양보할 때 까지 wait 상태에 계속 빠지게 되는데 이것을 DeadLock이라고 한다.

---

DeadLock 발생의 4가지 조건

상호배제(Mutual Exclusion)

• 매 순간 하나의 프로세스만이 자원을 사용할 수 있다.

비선점(Non-Preemption)

• Process는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않는다.

보유대기(Hold and Wait)

• 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있다.

순환대기(Circular Wait)

• 자원을 기다리는 프로세스간에 사이클이 형성 되어야 한다.

---

DeadLock 처리 방법 (숫자가 낮을 수록 강한 방법)

강한 방법이라는 뜻은 자원이 있어도 DeadLock이 발생하지 않을 수 있지만 자원을 사용하는 입장에서 상당히 비효율적으로 처리

1. DeadLock Prevention (예방)

• 자원 할당 시 DeadLock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것 

2. DeadLock Avoidance(회피)

자원 요청에 대한 부가적인 정보를 이용해서 DeadLock의 가능성이 없는 경우에만 자원을 할당 한다.

• 프로세스가 시작될 때 이 프로세스가 평생 쓸 자원의 최대량을 알고 있어 DeadLock을 피할 수 있다.

프로세스가 자원을 사용하는 절차

• Reqeust(자원을 요청하는 단계)
• Allocate (자원을 획득하는 단계)
• Use (자원을 사용하는 단계)
• Release (자원을 반납하는 단계)

Single instance인 경우 - Resource Allocation Graph Algorithm 사용

자원 ➡️ 프로세스: 자원이 프로세스에게 할당

프로세스 ➡️ 자원: 자원을 프로세스가 요청을 했는데 아직 할당받지 못한 상태

점선 화살표: 항상 프로세스에서 자원으로가는 화살표만 존재한다.

• 이 프로세스가 평생의 한번은 이 자원을 사용할 일이 있다는 의미

http://www.kocw.net/home/search/kemView.do?kemId=1046323

왼쪽 그림

• P1은 R1을 할당 받았고 P2는 R1에게 자원을 요청하고 P1이 끝날 때까지 대기 중인 상태

중간 그림

• P2가 R2에게 자원을 요청하면 화살표가 실선으로 바뀐다. (2번 자원은 아무도 가지고 있지 않기 때문에 요청한 프로세스한테 줄 수 있다.)

오른쪽 그림

• 자원을 할당해주면 P2 ➡️ R2에 화살표 방향이 R2 ➡️ P2로 바뀌게 되었다.
• P1이 여기서 R2에게 요청을 할 때 순환이 되면서 DeadLock이 발생하게 되고 요청하지 않으면 DeadLock이 발생하지 않는다. (이 정보를 알고 있음)
• DeadLock 발생할 수 있는 상황에는 사용가능한 자원이 있다고 전부 내어주는게 아니고 DeadLock 위험성이 있다고 하면 자원을 주지않는 방식이다.
  • 언젠가는 P1이 자원을 반납하면서 P2가 R1, R2에 자원을 다 받을 수 있고 P2가 자원을 다 반환하면 P1도 R1, R2를 전부 사용하는 날이 오니까🥹

Multiple instance인 경우 - Banker's Algorithm 사용

http://www.kocw.net/home/search/kemView.do?kemId=1046323

Allocation: 현재 프로세스에 할당한 자원 수

Max: 각 프로세스의 평생 사용할 자원 수

Available: 전체 자원 (10, 5, 7)에서 프로세스의 Allocation 정보를 뺀 가용자원

Need: Max에서 Allocation 정보를 뺀 추가 요청 가능량

 

아래 상황을 만족하는 프로세스들을 처리하면서 모든 프로세스가 처리가 가능하다면 DeadLock이 아니다.

• Available(가용자원) - Need(추가 요청 가능량)이 가능하면 Allocation(할당한 자원)을 반환할 수 있다.
• 반환한 자원 수 만큼 Available(가용자원)의 자원 수를 증가 시킨다.

Available(가용자원)이 존재 하더라도 Need(추가 요청 가능량)을 처리할 수 없으면 자원을 주지 않기 때문에 효율적이지 않다.

• 가용자원을 먼저 사용하고 반환하는걸 기다릴 수 도 있기 때문이다.

3.  DeadLock Detection and recovery (탐지 및 복구)

• DeadLock 발생은 허용하되 그에 대한 detection 루틴을 두어 DeadLock 발견시 recover 한다.

Detection

Resource type당 single instance인 경우 - 자원할당 그래프에서 cycle이 곧 DeadLock을 의미한다.

• Wait-for graph 알고리즘

https://woodforest.tistory.com/9

• 왼쪽 Resource-Allocation Graph에서 자원을 할당하고 요청하는 관계를 프로세스 입장에서만으로 그릴 수 있다.

 

 

Resource type당 multiple instance인 경우 - Banker's Algorithm과 유사한 방법 활용

뱅커스 알고리즘 보다 낙관적으로 DeadLock이 있는지 없는지 확인할 때 정말 DeadLock인 것만 찾아본다.

• Request는 추가 요청 가능량이 아니라 현재 실제로 요청한 자원량을 나타낸다.

http://www.kocw.net/home/search/kemView.do?kemId=1046323

 

1. 현재 가용자원이 (0, 0, 0)이므로 Request(실제 요청 자원량)으로 처리할 수 있는 프로세스는 P0와 P2가 있다.

2. P0와 P2가 자원을 반납하면 할당된 자원만큼 가용자원이 증가하니까 가용자원은 (3, 1, 3)이 된다.

3. 가용자원이 (3, 1, 3)일때 처리할 수 있는 프로세스는 P3, P1이 있고 똑같이 반납하면 가용자원은 (7, 2, 4)가 된다.

4. 이후 P4도 처리하면서 모든 프로세스를 처리할 수 있기 때문에 DeadLock이 아닌것을 확인할 수 있다.

 

모든 프로세스를 처리할 수 있는 sequence가 없다면 DeadLock이 발견되는데 이때 Recovery가 진행된다.

 

Recovery (복구)

Process Termination (자원을 죽이는 방법)

• DeadLock과 연류된 모든 프로세스를 죽인다.
• DeadLock에 연류된 프로세스를 하나씩 죽여보는 방식
  • DeadLock이 없어지면 통과되고 여전히 DeadLock이 존재하면 없어질 때 까지 확인하고 죽이기를 반복한다.

Resource Preemption (자원을 뺏는 방법)

비용을 최소화하기 위해서 누구에게 자원을 뺏을지 정한다.

• 그 프로세스로부터 자원을 뺏어서 자원을 없애고 안전한 상태로 rollback 하여 process를 재시작 한다.

프로세스 A한테 자원을 뺏었는데 프로세스 B가 갖기 전에 프로세스 A의 작업을 가져가 버리면 또 작업을 요청하고 가져가게 된다.

• DeadLock을 뺏어서 없앴는데 작업을 또 요청하고 가져가면서 똑같이 DeadLock이 발생할 수 있다.

 

이런 문제 때문에 똑같은 패턴으로 자원을 뺏 는게 아니라 조금씩 바꿔서 처리해야 DeadLock이 없어질 수 있고 Starvation 문제를 막아야 한다.

 

• 비용을 최소하기 때문에 동일한 프로세스가 계속해서 선정되면 비용을 최소하는데는 성공했지만 프로세스는 계속해서 rollback하기 때문에 문제가 발생한다.
  • 몇 번 rollback 당했는지도 고려해서 동일한 프로세스가 계속 선정되지 않게 조정을 해야 한다.

 

4. DeadLock ignorance (무시)

• DeadLock을 시스템이 책임지지 않는다.
• UNIX를 포함한 대부분의 OS가 채택한 방법 (사용자가 재부팅, 프로세스 강제 종료등으로 해결)

---

 

참고

운영체제