교착 상태(Deadlock)

5 분 소요


교착 상태(Deadlock)에 대한 이론적인 내용을 다뤄보고자 합니다. 수행한 프로젝트의 시스템 최초 가동 당시에 교착 상태 때문에 많은 어려움을 겪었습니다. 다양한 이벤트에 의해 비즈니스 로직들이 수행되었고 각 스레드 별로 자신들이 필요한 리소스(데이터베이스)를 점유하다보니 시스템은 자주 교착 상태에 빠지게 되었습니다. 다행히 오라클이 교착 상태를 감지하여 exception을 던져주기는 했지만 쉽사리 장애가 해소되지 않았고 다른 서비스들로 장애가 전파되기도 하였습니다.

당시에 시스템 장애를 폭탄처럼 투하하는 이 교착 상태를 모르는 팀원분들이 있다는 사실을 알았을 땐 놀랐습니다. IT 경력 10년이 가까운 분들이 경력 2년차 주니어 개발자인 저에게 '데드락이 무엇이니?' 라고 질문 한다니요…? 어찌됬든 눈 앞에 놓여진 시스템 장애의 원인을 해결하라는 특명을 받고 이틀을 뜬 눈으로 지새우며 현장 장애 대응, 테스트, 시스템 배포까지 했던 기억이 납니다. 저를 괴롭혔던 교착 상태에 대한 이론적인 내용을 한번 정리해보도록 하겠습니다.

교착 상태(Deadlock)란?

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

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

한정된 자원들을 나눠 사용하는 상태에서 두 프로세스가 서로 동일한 자원을 다른 순서로 먼저 점유하게 된다면 어떻게 될까요? 아래 그림과 간단한 시나리오를 통해 교착 상태를 조금 더 쉽게 이해해보도록 하겠습니다.

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

이미지 출처, https://includestdio.tistory.com/12


교착 상태를 발생시킬 수 있는 조건

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

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

교착 상태 문제 해결 방법

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

교착 상태 예방(prevention)

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

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

교착 상태 회피(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


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

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

교착 상태 탐지 방법

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

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

이미지 출처, Operating System Concepts 9th


교착 상태 회복 방법

탐지한 교착 상태를 회복하는 방법입니다.

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

OPINION

최근 바쁜 일정과 맞물려 교착 상태에 대한 글을 작성하는데 6일이라는 긴 시간이 걸렸습니다. 이 글을 정리하면서 대학 시절에 공부한 공룡 책(Operating System Concepts 9th)의 교착 상태에 대한 부분만 다시 읽어 보았습니다. 대학 생활 중 재밌게 들었던 수업이어서 그런지 포기한 대학원 진학이 다시 생각나는 하루입니다.

REFERENCE

댓글남기기