운영체제 7 - (Deadlock Resolution)

해당 정리는 youtube HPC Lab. KOREATECH의 OS 강의를 듣고 정리한 내용입니다.

강의 자료는 https://hpclab.tistory.com/1?category=887083 해당 링크에 있습니다.

 

목차

• Deadlock의 개념
  • Deadlock
  • Resource(자원)
    • 선점 가능 여부에 따른 분류
    • 할당 단위에 따른 분류
    • 동시사용 가능 여부에 따른 분류
    • 재사용 가능 여부에 따른 분류
  • Deadlock 발생 예
  • Deadlock 발생 필요조건
• Deadlock 해결방법
  • Deadlock prevention
    • Exclusive use of resource 조건 제거
    • Non-preemptible resource 조건 제거
    • Hold and wait 조건 제거(Total allocation)
    • Circular wawit 조건 제거
  • Deadlock Avoidance
    • Dijkstra’s banker’s algorithm
    • Habermann’s alogrithm
    • Deadlock Avoidance 정리
  • Deadlock Detection and recovery
    • Deadlock Detection
    • Deadlock Recovery
    • Deadlock Detection and recovery 정리

Deadlock의 개념

Deadlock

Deadlock은 프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우를 말한다. 즉 필요한 자원을 기다리는 상태를 의미하는데 이는 Blocked/Asleep state에서 절대 받을 수 없는 자원을 기다리는 것을 의미한다.

Deadlock의 개념을 보면 기존에 살펴봤던 Stavation과 유사하다는 점을 알 수 있다.

이 둘의 차이점으로는 우선, Stavation은 Ready state에서 발생하는 현상이며, 프로세스의 자원을 운이 없어서 받지 못하는 상태를 의미한다.

즉 Stavation은 받을 수 있는데 우선순위에 밀려서 계속 기다리는 현상이다(가능성이 0%는 아니다) 반면 Deadlock은 필요한 자원을 받을 수 있는 확률이 0%이다.

 

이처럼 Deadlock은 자원과 밀접한 관계가 있다. 이번에는 자원들에 대해서 알아보자

Resource(자원)

자원을 일반적으로 HW resource와 SW resource로 구분을 할 수 있으며 여러 관점에 따라 분류가 가능하다.

1. 선점 가능 여부에 따른 분류

Preemptible resource와 Non-preemptible resource로 구분이 가능하다.

Preemptible resource는 빼앗을 수 있는 자원을 말한다. ex) Processor, memory 등

Non-Preemptible resource는 빼앗을 수 없는 자원을 말한다 ex) disk drive 등

2. 할당 단위에 따른 분류

Total allocation resource와 Partitioned allocation resource로 구분할 수 있다.

Total allocation resource는 자원 전체를 프로세스에게 할당하는 자원을 의미한다 ex) Processor, disk drive 등

Partitioned allocation resource는 하나의 자원을 여러 조각으로 쪼개서 여러 프로세스들에게 할당 가능한 것을 의미한다. ex) Memory 등

3. 동시 사용 가능 여부에 따른 분류

Exclusive allocation resource와 Shared allocation resource로 구분이 가능하다.

Exclusive allocation resource는 한 프로세스만 사용 가능한 자원을 의미한다. ex) Processor, memory, disk dirve 등등, 여기서 memory가 해당 분류에 포함이 되는 이유는 메모리는 여러 조각으로 나눠서 사용하는데 그 나눠서 쓴 할당된 영역에서 하나의 프로세스만 사용이 가능하기 때문이다.

4. 재사용 가능 여부에 따른 분류

SR(Serially-reusable Resource)와 CR(Consumable Resource)로 분류할 수 있다.

SR은 시스템 내 항상 존재하는 자원을 의미한다. 사용이 끝나면 다른 프로세스가 사용 가능한 것을 의미한다.

ex) Processor, memory, disk drive, program

CR(Consumable Resource)는 한 프로세스가 사용 후에 사라지는 자원을 말한다.

Deadlock 발생 예

위 그림은 2개의 프로세스와 2개의 자원이 있다고 가정했을 때 Deadlock이 발생하는 예다.

P1이 R2를 할당받고, 이후 P2은 R1을 할당받는다. → P1이 R1이 필요해 할당받으려고 하고 그 후 P2가 R2를 할당받으려고 하면 이때 Deadlock이 발생한다.

즉 서로 가진 것을 요청하는 상태이고 이는 P1, P2 둘 다 자원을 받을 수 있는 확률이 0%가 되기 때문에 Deadlock이 발생하는 것이다.

 

Deadlock 모델 표현법은 Graph Model과 State Transition Model 2가지가 존재한다. (우선 있다고만 알아만 두자)

Deadlock 발생 필요조건

Deadlock 발생 필요조건은 자원의 특성 2가지와 프로세스 특성 2가지가 존재한다. 이 4가지 모두 성립해야 발생한다.

자원의 특성

• Exclusive use of resource → 혼자 쓰는
• Non-preemptible resource → 선점당하지 않는

프로세스의 특성

• Hold and wait(Partial allocation)
• Circular wait

Deadlock 해결방법

deadlock 해결방법은 Deadlock prevention method, Deadlock avoidance method, Deadlock detection and recovery method 이렇게 3가지가 있다. 하나씩 알아보자

Deadlock prevention

이름 그대로 Deadlock 상황을 예방하는 것이다.

위에서 봤듯이 Deadlock 상황이 발생하려면 위에서 언급한 발생 필요조건 4가지 모두 성립을 해야 하는데 이 중에서 하나를 제거하는 것이다. 그래서 Deadlock Prevention을 하게 되면 Deadlock은 절대 발생하지 않는다.

4가지 조건을 하나씩 제거해 보자

Exclusive use of resource 조건 제거

즉 모든 자원의 공유를 허용한다는 것인데, 이는 현실적으로 불가능하다.

Non-preemptible resource 조건 제거

즉 모든 자원에 대한 선점을 허용하는 방법이다. 그러나 이는 현실적으로 불가능하다.

그래서 위와 같은 유사한 방법이 있는데 프로세스가 할당받을 수 없는 자원을 요청할 경우 모든 프로세스가 기존에 가지고 있던 자원을 모두 반납하고 작업을 취소하는 방법이 있다.

그러나 위 방식은 글에서도 알 수 있지만, 심각한 자원 낭비가 발생한다.

Hold and wait 조건 제거(Total allocation)

즉 필요한 자원을 모두 한 번에 할당하는 방식이다. 이는 현실적으로는 가능하다. 그러나 필요하지 않은 자원도 프로세스가 가지고 있기 때문에 자원 낭비가 발생한다. 또한 모든 자원을 할당받아야 하기 때문에 자원을 받을 때까지 기다리고 이는 곧 무한 대기 현상이 발생할 가능성이 생긴다.

Circular wait 조건 제거

Total allocation을 일반화하는 방법이라고 볼 수 있다.

자원들에게 순서를 부여하는 방식을 의미한다. 그래서 프로세스는 순서의 증가 방향으로만 자원 요청이 가능하다.

(증가 방향으로 자원 요청은 한쪽 방향으로만 가기 때문에 Circular 발생 x)

 

Deadlock Prevention을 정리하자면,

4개의 Deadlock 발생 필요조건 중 하나를 제거하는 방식이다. 즉, Deadlock이 절대 발생하지 않는다. 그러나 이는 심각한 자원낭비가 발생하고 비현실적이다.

Deadlock Avoidance

Deadlock 상황이 만들어지는 4가지 조건을 일단 둔 상태에서 감시를 하는 방법이다.

Deadlock 상태가 될 가능성이 있는 자원을 할당 요청을 보류하는 것이다.

이때 System을 항상 safe state로 유지하는 방법을 이용한다.

위에서 언급한 safe state와 unsafe state에 대해서 알아보자

 

Safe state

모든 프로세스가 정상적 종료 가능한 상태를 의미한다. 이때 Safe sequence가 존재하는데 Deadlock 상태가 되지 않을 수 있음을 보장한다.

Unsafe state

Deadlock 상태가 될 가능성이 있는 것을 말한다. 이때 무조건 발생되는 것이 아닌 가능성을 의미하는 것이다. 즉, 발생을 안 할 수도 있다.

 

Deadlock Avoidance를 알아보기 전에 몇 가지 가정을 해야 한다

• 프로세스의 수가 고정되어 있다.
• 자원의 종류와 수가 고정되어 있다.
• 프로세스가 요구하는 자원 및 최대 수량을 알고 있다.
• 프로세스는 자원을 사용 후 반드시 반납한다.

위 4가지 조건을 가정한 상태로 Deadlock Avoidance 방법에 대해서 하나씩 알아보자

Dijkstra’s banker’s algorithm

Deadlock avoidance를 위한 간단한 이론적 방식으로 한 종류의 자원이 여러 개 있다는 가정하에 적용된다. 위 알고리즘은 시스템이 safe state가 되는지 찾아보는 기법이다.

예를 들어 R이라는 자원이 10개 있고 3개의 프로세스가 있다고 가정해 보자

P1에 1개 P2에 5개 P3에 2개의 자원이 현재할당 되어있고, 남은 자원은 2개이다.

이 상태에서 safte sequence가 되는지 찾아보자

P1에게 2개의 자원을 할당하면, P1은 프로세스가 종료되고 3개의 자원을 반납하게 된다. 이후 P3에게 3개의 자원을 할당하면, P3는 프로세스가 종료되고, 5개의 자원을 반납하게 된다. 이후 P2에게 4개의 자원을 할당하게 되면 P2는 종료되면서 모든 프로세스가 할 일을 마치고 종료하게 된다 → safe sequence가 있다 → safe state이다.

즉 실행 종료 순서는 P1 → P3 → P2 되며 safe sequence가 하나라도 존재하기 때문에 위 예시는 safe state이다.

 

다른 예시를 한번 더 보자

위 예시와 동일하게 현재 프로세스에 할당된 자원의 개수와 남은 자원의 개수는 동일하다.

현재 남은 자원은 2개인데 P1 ~ P3중에서 2개 이하를 필요로 하는 프로세스가 없으므로, safe sequence가 존재하지 않는다. 따라서 위 예시는 unsafe state이고 Deadlock이 발생될 가능성이 있다.

이때 무조건적으로 Deadlock이 발생하지 않는 이유는 위 표의 Additional Need는 최대 필요한 자원의 개수이다. 즉, P1이 자원이 4개가 안필요했을 수도 있어서, P1이 정상적으로 종료될 수도 있기 때문이다.

 

Dijkstra banker’s algorithm은 위처럼 남은 자원을 프로세스에게 줬다고 가정했을 때, safe sequence를 찾는 알고리즘이다.

Habermann’s algorithm

Dijkstra’s algorithm의 확장 버전이다. 이 알고리즘은 여러 종류의 자원을 고려한 것이며, 알고리즘 방법은 동일하다.

5개 프로세스가 존재하고 Ra, Rb, Rc 4가지 자원이 존재한다. 총자원의 개수는 순서대로 10,5,7이다.

결론만 말하자면 P2 → P4 → P1 → P3 → P5 순서로 하게 됐을 때 safe sequence가 만들어진다.

Deadlock Avoidance 정리

Deadlock Avoidance는 Deadlock 발생 가능성을 아예 막을 수 있다.

그러나 항상 시스템을 감시하기 때문에 그만큼 overhead 가 증가한다. 또한 Safe state를 유지하기 위해 사용되지 않는 자원이 존재한다.

Deadlock Detection and recovery

Deadlock Detection

Deadlock 상황을 피하지 않고 발생하게 되면 그때 해결하는 방식이다.

해당 방식은 주기적으로 Deadlock이 발생했는지 상태확인을 해야 하는데, 이때 **Resource Allocation Graph(RAG)**를 사용해서 Deadlock이 발생했는지 체크한다.

 

Resource Allocation Graph

위에서 언급한 내용처럼 Deadlock 검출을 위해 사용되며 방향성이 있는 그래프이다. 또한 bipartite graph라고 2개의 파트를 나눈 그래프이다.( 프로세스와 지원 이렇게 2개의 파트로 나눈다.)

 

RAG를 사용해서 Deadlock 상태를 확인하는 방법은 edge를 하나씩 지원 가면 된다. 만약 모든 edge가 지워지면 Deadlock인 프로세스가 없는 것이다. 그러나 만약 지울 수 없는 edge가 존재하면 몇몇 프로세스가 Deadlock 상태라는 것이다. 예시를 보면서 하나씩 알아보자.

위 그림을 보면 a 상태에서 R2에 있는 자원을 P1에게 할당했을 때를 가정하면 P1은 원하는 모든 자원을 할당받았기 때문에 edge를 지우면 된다. 그럼 그림 b 상태로 되는데 P2에서 원하는 모든 자원을 할당이 가능하기 때문에 c그림으로 가게 된다. 즉 위 상황은 모든 edge를 지울 수 있기 때문에 Deadlock이 아님을 알 수 있다.

두 번째 예시로 a에서 P3에게 자원을 할당할 수 있기 때문에 P3에게 자원을 할당을 하게 되면 b그림과 같은 상태가 된다. 그러나 b상태에서 모든 edge를 지울 수 없다. 따라서 위 상태는 Deadlock 상태로 알 수 있다.

 

Deadlock인지 확인하는 방법에 대해서 알아봤고 이제 해결하는 과정에 대해서 알아보자

Deadlock Recovery

Deadlock Recovery를 하는 방법에는 Process termination, Resource preemption 2가지 방식이 존재한다.

Process termination : Deadlock 상태에 있는 프로세스를 종료시키는 방법

Resource preemption : Deadlock 상태 해결을 위해 자원을 빼앗는 방식

Deadlock Detection and recovery 정리

Deadlock에 대해서 현재 상태만 고려해 발생하게 되면 그때 해결하는 방식이다.

그렇기 때문에 Deadlock이 발생했는지 주기적으로 검사를 해야 하고, 그로 인해 overhead가 발생할 수 있다.

Deadlock을 해결하기 위한 방식에는 Deadlock 상태의 프로세스를 종료시키는 방법과, 자원을 빼앗는 방법 2가지가 있다.