강준현

강준현

개발자

교착 상태(deadlock)

4 분 소요


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), 은행원 알고리즘 같은 교착 상태 회피 알고리즘이 존재한다. 교착 상태 회피 방법은 현재 자원의 가용 개수와 프로세스의 자원 요구량을 미리 알고 있어야 가능하다. 안전 상태에 대해 조금 자세히 살펴보자.

시스템이 안전 상태(safe state)라는 의미는 안전 순서(safe sequence)가 존재한다는 뜻이다. 안전 순서는 교착 상태를 만들지 않으면서 프로세스에 자원을 할당할 수 있는 순서이다. 간단한 예제 시나리오를 통해 이해도를 높여 보자. 시나리오를 살펴보기 전에 필요한 컨텍스트는 다음과 같다. 각 프로세스별 할당된 자원 및 가용 자원이다.

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


안전 상태 개념을 이해하기 위한 시나리오는 다음과 같다.

  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 순으로 자원을 할당하면 교착 상태가 발생하지 않는다.

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

Operating System Concepts 9th

2.3. Detection and Recovery

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

RAG(Resource Allocation Graph) 방식을 사용하면 교착 상태가 발생하고 있는지 확인할 수 있다. 자원 할당 그래프에서 자원을 모두 할당받은 프로세스(vertex)에 연결된 선(edge)을 제거해나가면 해당 상태가 교착 상태인지 아닌지 확인이 가능하다. RAG 방식을 자원 할당 그래프와 간단한 설명을 통해 이해해보자.

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


탐지한 교착 상태를 회복하는 방법은 다음과 같다.

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

REFERENCE

댓글남기기

참고