강준현

강준현

개발자

Deadlock

5 분 소요


0. 들어가면서

처음 참여했던 프로젝트 시스템의 가동 초창기엔 교착 상태(deadlock) 때문에 많은 어려움을 겪었습니다. 너무 많은 이벤트들이 발생했고, 각 트랜잭션 스레드들이 자신이 필요한 리소스(resource)를 점유하다보니 시스템은 잦은 교착 상태에 빠졌습니다. 오라클(oracle) 데이터베이스에서 교착 상태를 감지 후 예외(exception)을 던져줬지만, 그 것만으로 부족했습니다. 트랜잭션이 길어지면서 다른 서비스들로 장애가 전파되는 일들도 많았습니다. 이번 포스트는 저의 첫 프로젝트를 고달프게 만들었던 교착 상태에 대해 정리하였습니다.

1. What is Deadlock?

Wikipedia
두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 가리킨다.

이런 현상이 발생하는 이유는 한정되는 자원을 여러 실행 흐름들이 나눠서 사용하기 때문입니다. 특정 자원을 한 프로세스가 사용하고 있다면 다른 프로세스는 기다릴 수 밖에 없습니다. 읽기 전용으로 사용할 때는 동시에 사용이 가능하지만, 쓰기 기능이 필요하다면 점유된 자원의 해제를 기다려야합니다.

1.1. Deadlock between Process1 and Process2

한정된 자원들을 나눠 사용하는 상태에서 두 프로세스가 서로 동일한 자원을 다른 순서로 먼저 점유하는 시나리오를 기준으로 설명을 이어가겠습니다. 아래 그림은 프로세스1, 프로세스2가 서로 교착 상태에 빠진 상황입니다.

  1. 프로세스1은 자원1을 먼저 점유합니다.
  2. 프로세스2는 자원2를 먼저 점유합니다.
  3. 프로세스1은 자원2를 사용할 수 있을 때까지 대기합니다.
  4. 프로세스2는 자원1을 사용할 수 있을 때까지 대기합니다.
  5. 프로세스1, 프로세스2는 서로 자원을 얻기 위해 대기하면서 교착 상태에 빠집니다.
  6. 외부의 개입이 없다면 두 프로세스는 서로 종료되지 못합니다.

https://includestdio.tistory.com/12

1.2. Conditions for Deadlock

교착 상태는 한 시스템 내에서 다음 네 가지 조건이 동시에 성립할 때 발생합니다. 아래 네 가지 조건 중 하나라도 성립하지 않는다면 교착 상태는 발생하지 않습니다.

  • 상호 배제(mutual exclusion)
    • 자원은 한번에 한 프로세스만 사용할 수 있어야 합니다.
  • 점유 대기(hold and wait)
    • 최소한 하나의 자원을 점유하고 다른 프로세스에게 할당된 자원을 대기하는 프로세스가 존재해야합니다.
  • 비선점(no preemption)
    • 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없습니다.
  • 순환 대기(circular wait)
    • 대기 중인 프로세스들이 순환 형태로 다른 프로세스가 점유한 자원의 해제를 기다리는 상태입니다.
    • 프로세스 집합 {p0, p1, .. pn}에서 p0은 p1의 자원, p1은 pn의 자원, pn은 p0의 자원을 점유하기 위해 대기합니다.

2. Solve the Deadlock Problem

교착 상태 예방(prevention), 회피(avoidance), 탐지(detection)와 회복(recovery) 같은 여러 가지 해결 방법들이 존재합니다.

2.1. Prevention

교착 상태를 발생시키는 4개의 조건 중 하나 이상을 만족시키지 않도록 만들어 해결하는 방법입니다.

  • 상호 배제(mutual exclusion) 부정
    • 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 합니다.
    • 이 조건을 부정한다면 여러 실행 흐름에 의해 자원이 동시에 사용되면서 매번 다른 실행 결과를 얻게되는 문제가 발생합니다.
  • 점유 대기(hold and wait) 부정
    • 프로세스가 실행되기 전에 필요한 모든 자원을 요청하고 허용되기까지 대기합니다.
    • 자원을 효율적으로 사용하지는 못하는 시스템이 됩니다.
    • 우선순위가 낮은 프로세스는 계속 자원을 할당받지 못하는 기아(starvation) 현상이 발생할 수 있습니다.
  • 비선점(no preemption) 부정
    • 높은 우선순위의 프로세스가 다른 프로세스가 사용 중인 자원을 점유합니다.
    • 자원을 빼앗긴 프로세스는 작업하던 내용을 잃을 수 있습니다.
  • 순환 대기(circular wait) 부정
    • 자원을 순환 형태로 대기하지 않도록 일정한 방향으로만 자원을 요구할 수 있도록 합니다.
    • 어플리케이션 개발자에 의해 적절한 순서로 실행될 수 있도록 프로그램되어야 합니다.

2.2. Avoidance

교착 상태 예방은 교착 상태를 막을 수 있지만 자원을 효율적으로 사용하지는 못 합니다. 교착 상태 회피는 덜 엄격한 제약 조건을 통해 자원을 조금 더 효율적으로 사용할 수 있게 합니다. 안전 상태(safe state), 은행원 알고리즘 같은 교착 상태 회피 알고리즘들이 존재합니다.

2.2.1. Limitations of Avoidance

교착 상태 회피 방법은 현재 자원의 가용 개수와 프로세스의 자원 요구량을 미리 알고 있어야 가능합니다.

2.2.2. Safe State

시스템이 안전 상태(safe state)라는 의미는 안전 순서(safe sequence)가 존재한다는 뜻입니다. 안전 순서는 교착 상태를 만들지 않으면서 프로세스들에게 자원을 할당할 수 있는 순서입니다. 간단한 예제 시나리오를 통해 이해도를 높여 보겠습니다.

Scenario Context for Safe State

안전 상태에 대한 개념 설명 이전에 시나리오에 필요한 상황을 짚고 가겠습니다. 다음은 각 프로세스 별 할당된 자원 및 가용 자원입니다.

  • P0, P1, P2, P3, P4 프로세스가 존재
  • Allocation - 각 프로세스 별로 A, B, C 자원을 할당받은 수
  • Max - 각 프로세스 별로 최대 필요한 A, B, C 자원 수
  • Available - 현재 가용 가능한 A, B, C 자원 수

Operating System Concepts 9th
Scenario for Safe State Concepts
  1. P1 프로세스가 필요한만큼 자원을 할당하여 일을 종료시킨다. 
     if (Current_Availble(3, 3, 2) > Need(1, 2, 2)) {
     Current_Availble(5, 3, 2) = Current_Availble(3, 3, 2) + Allocation(2, 0, 0)
 }
  2. P3 프로세스가 필요한만큼 자원을 할당하여 일을 종료시킨다. 
     if (Current_Availble(5, 3, 2) > Need(0, 1, 1)) {
     Current_Availble(7, 4, 3) = Current_Availble(5, 3, 2) + Allocation(2, 1, 1)
 }
  3. P4 프로세스가 필요한만큼 자원을 할당하여 일을 종료시킨다. 
     if (Current_Availble(7, 4, 3) > Need(4, 3, 1)) {
     Current_Availble(7, 4, 5) = Current_Availble(7, 4, 3) + Allocation(0, 0, 2)
 }
  4. P0 프로세스가 필요한만큼 자원을 할당하여 일을 종료시킨다. 
     if (Current_Availble(7, 4, 5) > Need(7, 4, 3)) {
     Current_Availble(7, 5, 5) = Current_Availble(7, 4, 5) + Allocation(0, 1, 0)
 }
  5. P2 프로세스가 필요한만큼 자원을 할당하여 일을 종료시킨다. 
     if (Current_Availble(7, 5, 5) > Need(6, 0, 0)) {
     Current_Availble(10, 5, 7) = Current_Availble(7, 5, 5) + Allocation(3, 0, 2)
 }
  6. P1 > P3 > P4 > P0 > P2 순으로 자원을 할당하면 교착 상태가 발생하지 않습니다.

2.2.3. Unsafe State

안전 순서가 존재하지 않는 상태를 불안전 상태(unsafe state)라고 합니다. 불안전 상태라고 해서 교착 상태가 반드시 발생하는 것은 아닙니다. 프로세스가 항상 필요한 자원을 최대한으로 사용하는 것은 아니기 때문입니다. 불안전 상태가 안전 상태보다 더 큰 영역이라고 볼 수 있습니다.

Operating System Concepts 9th

2.3. Detection and Recovery

교착 상태 탐지(detection)과 회복(recovery)

교착 상태를 만들지 않기 위한 작업을 수행하지 않습니다. 다만, 주기적으로 교착 상태가 발생하는지 검사하고 발생한 경우 이를 해결하는 방식입니다.

2.3.1. Method for Deadlock Detection

RAG(Resource Allocation Graph)를 사용하여 교착 상태가 발생하고 있는지 확인합니다. 자원 할당 그래프에서 자원을 모두 할당받은 프로세스(vertex)에 연결된 선(edge)을 제거해나가면 해당 상태가 교착 상태인지 아닌지 확인이 가능합니다.

RAG(Resource Allocation Graph)

다음은 자원 할당 그래프입니다. 간단한 설명을 통해 이해도를 높여보겠습니다.

  • (a) 이미지
    • 프로세스에서 자원으로 표시된 화살표(P->R)는 프로세스가 자원을 할당받기 위해 대기하고 있는 상태를 의미합니다.
    • 자원에서 프로세스로 표시된 화살표(R->P)는 자원이 프로세스에게 할당된 상태를 의미합니다.
  • (b) 이미지
    • 각 프로세스들 간의 대기 상태를 다시 표현한 이미지입니다.
  • 자원을 모두 할당받은 P5 프로세스에 연결된 선부터 제거해 나가더라도 모든 선을 제거할 수 없기 때문에 아래 그래프는 교착 상태입니다.

Operating System Concepts 9th

2.3.2. Recovery

교착 상태를 탐지한 트랜잭션이 회복하는 방법입니다.

  • 프로세스 종료
    • 교착 상태를 일으키는 프로세스를 종료시킵니다.
    • 종료되는 프로세스로 최소 비용을 발생시키는 프로세스를 선택해야 합니다.
    • 모든 프로세스를 동시에 종료하거나 교착 상태가 해결될 때까지 한 프로세스씩 종료하는 방법이 있습니다.
    • 종료된 프로세스는 재시작시킵니다.
  • 자원 선점
    • 교착 상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당합니다.
    • 자원을 빼앗긴 프로세스는 강제 종료된 후 재시작합니다.
    • 우선순위가 낮은 프로세스, 수행된 횟수가 적은 프로세스 등과 같은 기준을 통해 자원을 선점당할 프로세스를 선택합니다.

REFERENCE

댓글남기기

참고