🖥 교착상태

프로세서는 필요한 자원을 얻기 위해 Blocked 상태로 전이될 수 있다고 알고 있다. 하지만 필요한 자원이 영원히 얻을 수 없는 상태가 된다면 이를 Deadlock 상태라고 하며, 이런 Deadlock된 프로세스가 시스템내에 존재한다면 시스템이 deadlock 상태에 있다라고 말하게 된다.

Deadlock vs. Starvation

일을 할 수 없는 상태를 두고 본다면, Starvation(이하 기아 현상)과 Deadlock(이하 교착 상태)은 비슷하다고 생각될 수 있다. 하지만 기아 현상의 경우는 운이 없어서 내 차례가 계속 밀리게 되는 현상이고, Deadlock의 경우 가능성이 0%인 상황이다. 또 기아 현상은 _Ready queue_에서 발생하는 반면, Deadlock은 _Wait queue_(사진에서의 asleep)에서 발생하게 된다. 추가적으로 어떤 자원을 기다리는지도 다르다.

자원의 분류

교착 상태를 설명하면 자원이라는 단어가 자주 언급된다. 이 장에서 언급되는 자원은 Hardware vs. Software 자원으로 구분되며 다음과 같은 분류법에 따라 분류될 수 있다.

• 선점 가능 여부에 따른 분류
  • 선점 가능한 자원
    • 선점 당한 후, 돌아와도 문제가 발생하지 않는 자원
      • Processor (Context switching)
      • Memory (Swap device)
  • 비선점 자원
    • 선점 당하면, 이후 진행에 문제가 발생하는 자원 (rollback, restart등의 작업이 필요함)
      • disk drive
• 할당 단위에 따른 분류
  • 전체 할당 자원
    • 자원 전체를 프로세스에 할당
      • Processor, disk drive 등
  • 분할 할당 자원
    • 하나의 자원을 여러 조각으로 나누어, 여러 프로세스들에게 할당
      • Memory 등
• 동시 사용 가능 여부에 따른 분류
  • Exclusive allocation resource
    • 한 순간에 한 프로세스만 사용 가능한 자원
      • Processor, memory, disk drive 등
        • Memory는 여러 구역으로 나뉘어 할당될 수 있지만 할당 받은 영역은 해당 프로세스만 사용이 가능하다.
  • Shared allocation resource
    • 여러 프로세스가 동시에 사용 가능한 자원
      • Program(S/W), Shared data 등
• 재사용 가능 여부에 따른 분류
  • 지속적 재활용 가능한 자원
    • 시스템 내에 항상 존재하는 자원, 사용이 끝나면 다른 프로세스가 사용 가능
      • Processor, memory, disk drive, program 등
  • 소비성 자원
    • 한 프로세스가 사용한 후에 사라지는 자원
      • Signal, message 등

교착 상태(Deadlock)과 자원의 종류

그렇다면 교착 상태를 발생 시키는 자원은 어떤게 있을까?

• Non-preemptible resources
• Exclusive allocation resources
• Serially reusable resources

여기서 CR(소비성 자원) 또한 교착 상태를 유발할 수 있지만, 강의에서 이 내용까지 고려하게 되면 Deadlock model이 너무 복잡해져 제외한다고 설명한다.

교착 상태는 기본적으로 Non-preemptible한 자원에서 발생하게 된다. 한번 할당 받으면 끝날때까지 사용하며 이 자원이 필요한 프로세스는 영원히 기다려야 하기 때문이다. 같은 맥락으로 Exclusive allocation resources 또한 내 영역은 나 이외는 사용할 수 없으며, Serially reusable resources도 같은 내용이다. 요약하자면 먼저 선점된 프로세스 외엔 사용이 불가능한 자원은 교착 상태를 유발할 수 있다.

교착 상태 발생 필요 조건

Non-preemptible한 자원이 교착 상태를 발생하는이긴 하지만 요청과 반환을 적절히 이뤄진다면 Non-preemptible한 자원을 사용하더라도 교착 상태는 발생하지 않는다. 이런 자원의 특성과 함께 프로세스의 특성이 겹쳐지면 교착 상태가 발생하게 된다.

• Exclusive use of resources - 자원의 특성
• Non-preemptible resources - 자원의 특성
• Hold and wait (Partial allocation) - 프로세스의 특성
  • 자원을 하나 Hold하고 다른 자원 요청
• Circular wait - 프로세스의 특성

위 네 가지 조건이 만족하게 되면 교착 상태가 발생하며 이중 하나만 깨져도 교착 상태 문제는 해결된다.

교착 상태 예방

앞서 교착 상태는 필요 조건 네 가지 중 하나만 해결되어도 발생하지 않는다고 설명했다. 그렇다면 각 조건은 어떤 방법으로 해결할 수 있을까.

모든 자원을 공유 허용

Exclusive use of resources 조건을 제거하기 위해선 모든 자원을 독점할 수 없는 공유 자원으로 만드는 방법이다. 하지만 이 방법은 현실성이 없으므로 넘어가자.

모든 자원에 대해 선점 허용

Non-preemptible resources 조건 제거하기. 이 방법 또한 현실적으로 불가능하다. 유사한 방법으로 프로세스가 할당 받을 수 없는 자원을 요청한 경우 기존 작업을 취소하고 작원을 모두 반납한다. 이 작업을 성공할때 까지 계속 다시 시작한다. 매우 _비효율적_이며 _자원 낭비가 심각_할 것이다.

필요 자원 한번에 모두 할당 (Total allocation)

Hold and wait 조건 제거. 작업에 필요한 모든 자원을 받기 전까진 작업을 수행하지 않고 모든 자원을 할당 받으면 작업을 수행하는 방법이다. 언뜻 괜찮아 보이지만 이 방법은 _자원 낭비가 발생_하게 된다. 프로세스는 모든 자원을 항상 필요하지 않다. 어떤 자원은 매우 짧은 순간만 필요하지만 이 자원이 다른 프로세스에겐 매우 절실할 수 있으며 이를 위해 _무한정 대기_할 수 밖에 없게 된다. 따라서 자원을 효율적으로 사용할 수 없게 된다.

Circular wait 조건 제거

Totally allocation을 일반화한 방법으로, 자원에게 순서를 부여한다. 프로세스는 순서의 증가 방향으로만 자원 요청이 가능하기 때문에 Circular wait가 절대로 발생할 수 없지만, 많이 사용되는 자원에서 _병목 현상_이 발생할 수 있다. 따라서 단 하나의 자원만이 공통적으로 필요하고 그 다음(또는 자원이 둘 중 하나만 있어도 수행이 가능한 경우) 순서는 모두 각각의 자원이 필요한 프로세스들이라도 하나의 공통 자원에서 대기하기 때문에 _자원이 낭비_가 된다.

이 처럼 교착 상태 예방은 "조건 하나를 제거하면 교착 상태는 절대 발생하지 않는다." 라는 간단한 전제를 가지지만, 이를 위한 방법이 _비현실적_이고, _자원 낭비_가 너무 심하기 때문에 예방이 아닌 회피에 집중하게 된다.

교착 상태 회피

이전 단원의 교착 상태 예방의 경우 기반 시스템을 변경하여 많은 비용과 현실성이 없다는 문제점이 있었다. 이번 단원의 교착 상태 회피는 시스템의 상태를 계속 감시하며 교착 상태 가능성이 있는 자원 할당 요청을 보류하여 _시스템을 항상 안전한 상태(Safe state)로 유지_하는 방법이다. 도로를 예로 들어서 이전의 교착 상태 예방의 경우 모든 도로를 다시 깔아서 원천 봉쇄를 한다는 접근이라면 교착 상태 회피는 중간에 _교통 정리를 하는 감시자를 둬 조율_한다라는 접근이다.

시스템은 항상 안전 상태(Safe state)를 유지한다고 했다. 안전 상태는 Safe sequence(교착 상태가 되지 않을 수 있는 순서)가 존재하는 _프로세스가 정상적 종료 가능한 상태_이다. 반대로 안전하지 않은 상태(Unsafe state)는 교착 상태가 될 _가능성_이 있는 상태이다.

가정

교착 상태 회피 가정은 다음과 같다.

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

가정을 살펴보면 Not practical하다는 걸 알 수 있다. 하지만 현실적인 해결책은 이런 논리적인 고민에서 시작하기 때문에 즐겨보자 :facepunch:

Dijkstra's banker's algorithm

Banker's algorithm은 Dijkstra 선생님이 제안하신 교착 상태 회피를 위한 간단한 이론적 기법이다. 가정은 한 종류의 자원이 여러 개이며 시스템은 항상 safe state로 유지한다. 예는 영상을 참고하면 좋을 것 같다.

Habermann's algorithm

Dijkstra's algorithm의 확장으로 여러 종류의 자원을 고려하며 시스템을 항상 safe state로 유지하는 알고리즘이다.

이렇게 교착 상태를 해결하는 방법을 알아봤는데 이 역시 문제가 있다. 일단 자원을 항상 감시해야하기 때문에 Overhead가 높고, Safe state를 유지하기 당장 또는 꼭 필요하지 않은 자원을 미리 할당하여서 자원을 효율적으로 사용하지 못한다. 마지막으로 Practical하지 않다.

교착 상태 탐지 및 복구

이 단원은 이전의 교착 상태를 해결하기 위해서 방어적인 태도를 가졌다면 이 단원은 "교착 상태가 되면 해결하지 뭐~" 라는 느낌으로 접근한다. 그렇기 때문에 탐지가 중요하며 Resource Allocation Graph(RAG)를 사용하여 주기적으로 교착 상태 발생을 확인한다.

RAG(Resource Allocation Graph)

RAG는 교착 상태를 감지하기 위한 방향을 가진 이분 그래프이다.

Graph reduction

Graph reduction은 RAG를 보고 교착 상태를 탐지하는 방법으로 Completely reduced, 즉 모든 Edge가 제거되면 교착 상태에 빠진 프로세스가 없다고 판단하며, 반대로 Irreducible, 지울 수 없는 Edge가 존재하면 하나 이상의 프로세스가 교착 상태에 빠졌다고 판단하는 방법이다.

교착 상태 복구

앞서 교착 상태가 탐지되면 복구를 통해 교착 상태를 해결하려는 시도를 하게된다. 교착 상태를 해결하기 위해선 교착 상태를 일으킨 프로세스 또는 자원에 대해 조취를 취해야 하는데, 프로세스의 경우 _교착 상태인 프로세스 중 일부를 종료_시킨다. 종료시킬 프로세스를 선택하는 방법으론 두 가지가 있는데 각각의 특징은 다음과 같다.

• Lowest-termination cost process first
  • 정의된 비용 모델에서 가장 적은 비용을 종료하는 방식으로 간단하고 적은 Overhead를 가지지만, 불필요한 프로세스들이 종료 될 가능성이 높다.
• Minimum cost recovery
  • 모든 경우의 수를 고려해 최소 비용으로 교착 상태를 해결할 수 있는 프로세스를 선택한다. 하지만 모든 경우의 수를 고려해야 하기 때문에 복잡하고, 많은 Overhead가 발생한다.

다음은 자원에 대한 조취로 _자원 선점(Resource preemption)_을 통해 문제를 해결하는 방법이다. 앞서 설명한 선택 방법과 비슷하게 자원에 대한 비용 모델 또는 최소 비용으로 해결할 수 있는 자원을 선택해, 해당 프로세스 자원을 선점하고 해당 프로세스를 종료시킨 후 재시작하도록 한다. 이 방법도 앞서 프로세스 종료 문제와 같이 교착 상태가 아닌 프로세스가 종료될 수 있다.

Checkpoint-restart method

앞서 교착 상태 복구를 위해 프로세스 또는 자원을 통해 문제를 해결하려고 시도하면 프로세스가 종료된다는 걸 알 수 있다. 그렇다면 종료된 프로세스는 처음부터 다시 시작해야할까? 그렇다면 너무 비효율적이기 때문에 프로세스들은 특정 시점마다 Context를 저장하고 가장 최신 Context를 복구하는 롤백 과정을 거친다.