Deadlock 이란 무엇인가

 Deadlock 두 줄 설명

 우리 컴퓨터 안에 있는 exe 파일들을 운영체제에서는 JOB이라고 부릅니다. 이러한 JOB이 일을 처리하기 위해 메모리를 할당받으면 프로세스(Process)가 되는 겁니다. 그리고 이러한 프로세스는 다시 프로세서(CPU)를 할당받으면서 비로소 작업을 처리하기 시작합니다.

 

 일을 처리하는 과정에서 프로세스는 수많은 자원을 필요로 합니다. 그중에서도 데드락은 공유자원을 필요로 할 때 발생합니다. 예를 들어, P1(프로세스 1) 이 R1(공유자원 1)을 선점한 상태에서 R2(공유자원 2)를 필요로 하고 P2 가 R2를 선점한 상태에서 R1을 필요로 할 때 우리는 데드락 상태라고 합니다.

 

따라서 데드락은 자원(Resource)에 큰 영향을 받고 멀티프로세스인 경우에 발생합니다. 

 

 

 

 

 Deadlock 발생 필요 조건

• Exclusive use of resources : 한 자원을 여러 프로세스가 동시에 처리할 수 없다. (자원의 특성)

• Non-preemptible resources : 이미 사용하고 있는 자원을 선점할 수 없다. (자원의 특성)

• Hold and wait (Partial allocation) : 자원을 하나 hold 한 상태에서 다른 자원을 요청. (프로세스의 특성)

• Circular wait : 순환 대기 구조 (프로세스의 특성)

 

 

 

 Deadlock 해결 방법 1 : Prevention

 말 그대로 데드락이 발생하기 전에 예방하는 방법입니다. 위에서 알아본 4가지의 조건 중 하나라도 일어나지 않게 한다면 데드락이 절대 발생하지 않는다는 거죠. 이론적으로는 분명 가능하지만 이 방법은 비현실적 요소가 많습니다.

 

• 모든 자원을 공유 허용

  1. Exclusive use of resources의 조건 제거 -> 현실적으로 불가능

• 모든 자원에 대해 선점 허용

  1. Non-preemptible resources 조건 제거 - > 심각한 자원낭비 발생 ( 불가능 )

• 필요자원을 한 번에 모두 할당하는 방법

  1. Hold and wait 조건 제거

  2. 필요하지도 않은 순간에도 자원을 가지고 있음 - > 자원낭비

  3. 무한 대기 현상 발생 가능

• Circular wait 조건 제거

  1. Totally allocation을 일반화 한 방법

  2. 자원들에 순서를 부여 - > 프로세스 순서의 증가 방향으로만 자원 요청

  3. 자원 낭비 발생

 

 Deadlock 해결 방법 2 : Avoidance 

 

 작업이 처리되는 모든 자원을 실시간으로 감시하다가 데드락이 발생할 위험이 있는 자원이 생기면 자원 할당 요청을 보류하여 시스템을 항상 안전하게 유지하는 방법입니다. 이 방법으로 데드락을 막는 것은 가능하지만 오버헤드가 많이 발생합니다.

 

• High overhead : 항상 시스템을 감시하기 때문에 많은 메모리가 필요

• Low resource utillization : safe state를 유지하기 위해, 사용되지 않는 자원이 존재

• Not practical : 프로세스와 자원의 수가 고정돼야 하는 등 비현실적인 조건이 필요하다.

 

 Deadlock 해결방법 3 : Detection

 검출(Detection) 방법은 말 그대로 데드락이 발생하면 빠르게 발견하여 문제를 해결하는 방법입니다. 데드락의 발생 여부는 RAG(Resource Allocation Graph)라는 그래프의 Graph reduction 방법을 사용해서 알 수 있습니다.

 

 RAG는 방향이 있는 이분 그래프로 아래의 그림과 같습니다. 간략하게 설명하자면 Process에서 Resource 방향의 간선은 자원 할당 요청을 의미하고 그 반대 방향의 간선은 자원 선점을 의미합니다. 그리고 Graph reduction 은 필요로 하는 모든 자원을 얻을 수 있는 노드의 간선을 지우는 것을 의미합니다. 

 

결과적으로 RAG의 간선을 모두 지울 수 없다면 Deadlock, 모두 지울수 있다면 정상이라고 보시면 됩니다. 현재는 RAG를 이용한 검출법의 오버헤드를 줄이기 위해 Cycle detection, Knot detection 등의 방법이 나왔지만 대부분 제약이 따른다고 합니다.

 

RAG

 

 Recorvery

 

방법 1, 2와 Detection 방법의 큰 차이점은 회복(Recovery)이 필요하다는 겁니다. 어쩃거나 데드락이 일어나기 때문이죠. 회복하는 방법에는 크게 두 가지 방법이 있습니다.  그런데 두가지 방법 모두 데드락을 해결하기 위해 진행 중인 프로세스를 강제 종료하게 됩니다. 강제 종료에서 발생하는 오버헤드를 방지하기 위해 Checkpoint라는 방법을 사용합니다. 이 방법을 사용하면 프로세스 작업이 진행되는 동안에 중간중간 체크포인트에 Context를 저장해서 ,강제 종료가 되면 가장 최근의 체크포인트 지점에서 다시 재실행을 하게 됩니다.

 

1. Process termination

   • Deadlock 상태에 빠진 프로세스를 종료 - > 강제종료 이후 재시작

2. Resource preemption

   • Deadlock 상태에 빠진 프로세스가 필요로 하는 자원을 강제로 가져옴

   • 자원을 빼앗긴 프로세스는 강제종료 이후 재시작