[CS] Chapter 06 교착 상태

📌 교착 상태의 개요

1. 교착 상태의 정의

교통 체증이 심한 교차로에서 서로 비켜주기를 기다리며 꼼짝 못 하는 경우가 바로 교착 상태입니다.

교착상태 : 2개 이상의 작업이 동시에 이루어지는 경우, 다른 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태

교착 상태는 아사 현상(starvation)과 비슷해 보이지만 차이가 있습니다. 아사 현상은 잘못된 정책으로 특정 프로세스의 작업이 지연되는 문제인 반면, 교착 상태는 여러 프로세스가 작업을 진행하다 보니 발생하는 자연적인 현상입니다. 따라서 교착 상태가 발생하면 강압적으로 해결해야 합니다.

• 시스템 자원
  교착 상태는 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생합니다. 어떤 프로세스가 임계구역으로 보호되는 프린터, 스캐너 등 동시에 같이 사용할 수 없는 시스템 자원을 할당받은 후 양보하지 않는 경우를 예로 들 수 있습니다. 프로세스 P1은 프린터를 할당받은 후 스캐너를 기다리고 프로세스 P2는 스캐너를 할당받은 후 프린터를 기다리면 교착 상태가 발생합니다.

• 잠금

• 응용 프로그램

2. 자원 할당 그래프

자원 할당 그래프(resource allocation graph)는 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프(directional graph)로 표현한 것입니다.

자원 할당 그래프에서 프로세스는 원으로, 자원은 사각형으로 표현합니다. 자원을 사용하는 경우(할당된 경우)는 자원에서 프로세스로 향하는 화살표로 표시하고, 프로세스가 자원을 기다리는 경우(대기하는 경우)는 프로세스에서 자원으로 향하는 화살표로 표시합니다.

식사하는 철학자 문제를 살펴봅시다. 철학자 4명이 둥근 식탁에 둘러앉아 식사를 하는데 왼쪽에 있는 포크를 잡은 뒤 오른쪽에 있는 포크를 잡아야만 식사가 가능하다는 조건이 있습니다. 철학자들은 음식을 먹기 위해 왼쪽의 들고 있는 다른 철학자가 앉아 있습니다. 이 문제의 결과는 오른쪽 포크를 잡지 못해 철학자가 모두 굶어 죽는다는 것입니다. 현실에서는 이와 같은 일이 없겠지만, 식사하는 철학자 문제는 교착 상태를 설명하기 위한 예로 오랫동안 사용되었습니다.

식사하는 철학자 문제에서 교착 상태가 발생하는 조건은 다음과 같습니다.

1. 철학자들은 서로 포크를 공유할 수 없습니다.
   자원을 공유하지 못하면 교착 상태가 발생합니다.
2. 각 철학자는 다른 철학자의 포크를 빼앗을 수 없습니다.
   자원을 빼앗을 수 없으면 자원을 놓을 때까지 기다려야 하므로 교착 상태가 발생합니다.
3. 각 철학자는 왼쪽 포크를 잡은 채 오른쪽 포크를 기다립니다.
   자원 하나를 잡은 상태에서 다른 자원을 기다리면 교착 상태가 발생합니다.
4. 자원 할당 그래프가 원형입니다.
   자원을 요구하는 방향이 원을 이루면 양보를 하지 않기 때문에 교착 상태가 발생합니다.

📌 교착 상태 필요조건

1. 교착 상태 필요조건

상호 배제(mutual exclusion), 비선점(non-preemption), 점유와 대기(hold and wait), 원형 대기(circular wait)의 네 가지 조건을 동시에 만족해야만 교착 상태가 발생합니다.

• 상호 배제 :
  한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 합니다. 배타적인 자원은 임계구역으로 보호되기 때문에 다른 프로세스가 동시에 사용할 수 없습니다. 배타적인 자원을 사용하면 교착 상태가 발생합니다.
• 비선점 :
  한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 합니다. 어떤 자원을 빼앗을 수 있다면 시간 간격을 두고 자원을 공유할 수 있습니다. 하지만 빼앗을 수 없으면 공유할 수도 없으므로 교착 상태가 발생합니다.
• 점유와 대기 :
  프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 합니다. 다른 프로세스의 작업 진행을 방해하는 교착 상태가 발생하려면 다른 프로세스가 필요로 하는 자원을 점유하면서 또 다른 자원을 기다리는 상태가 되어야 합니다.
• 원형 대기 :
  점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 합니다. 프로세스가 특정 자원에 대해 점유와 대기를 한다고 해서 모두 교착 상태에 빠지는 것은 아닙니다. 점유와 대기를 하는 프로세스들이 서로 방해하는 방향이 원을 이루면 프로세스들이 서로 양보하지 않기 때문에 교착 상태에 빠집니다.

사용하는 자원을 동시에 공유할 수 없고 중간에 빼앗을 수도 없다면 자원을 가진 프로세스가 자원을 내놓을 때까지 무작정 기다리는 교착 상태가 발생합니다.

2. 식사하는 철학자 문제와 교착 상태 필요조건

여기서 기억할 것은 교착 상태와 아사 현상이 다르다는 점입니다. 아사 현상은 정책상 잘못이나 오류로 인해 특정 프로세스의 작업이 이루어지지 않는 것입니다. 아사 현상은 프로세스가 양보할 수 있는 상한선을 정하는 에이징(나이 먹기)으로 해결할 수 있습니다.

아사 현상과 달리 교착 상태는 정책상 잘못이나 오류가 없어도 자연적으로 발생합니다. 따라서 교착 상태는 에이징으로 해결할 수 없고 정책을 바꾼다고 해서 막을 수도 없습니다. 교착 상태는 아사 현상보다 처리하기 복잡하기 때문에 이를 해결하기 위한 다양한 방법이 제시되었습니다.

📌 교착 상태 해결 방법

1. 교착 상태 해결

교착 상태를 해결하는 방법은 예방(prevention), 회피(avoidance), 검출(detection)이며, 추가적으로 교착 상태가 발견된 후에 자원을 회복하는 방법도 있습니다.

• 교착 상태 예방
  교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화하는 방식입니다. 이 방법은 실효성이 적어 잘 사용되지 않습니다.
• 교착 상태 회피
  자원 할당량을 조절하여 교착 상태를 해결하는 방식입니다. 자원을 얼마만큼 할당해야 교착 상태가 발생하지 않는다는 보장이 없기 때문에 실효성이 적습니다.
• 교착 상태 검출과 회복
  자원 할당 그래프를 모니터링하면서 교착 상태가 발생하는지 살펴보는 방식입니다. 교착 상태가 발생하면 교착 상태 회복 단계가 진행됩니다. 교착 상태를 검출한 후 회복하는 방식은 교착 상태를 해결하는 현실적인 접근 방법입니다.

2. 교착 상태 예방

교착 상태를 유발하는 네 가지 조건 중 하나라도 예방하여 교착 상태를 처리하는 방법으로 다음과 같은 네 가지 예방법이 있습니다.

상호 배제 예방

시스템 내에 있는 상호 배타적인 모든 자원, 즉 독점적으로 사용할 수 있는 자원을 없애버리는 방법입니다. 시스템 내의 모든 자원을 공유할 수 있다면 교착 상태가 발생하지 않습니다.

그러나 현실적으로는 모든 자원을 공유할 수 없으며 상호 배제를 적용하여 보호해야 하는 자원이 있습니다. 상호 배제를 없애버리는 것은 식사하는 철학자 문제에서 두 사람에게 하나의 포크를 같이 사용하라고 하는 것과 같습니다. 상호 배제를 무력화하기는 사실상 어렵습니다.

비선점 예방

모든 자원을 빼앗을 수 있도록 만드는 방법입니다. 사실상 시스템의 모든 자원을 빼앗기는 어렵습니다.

설사 어떤 자원을 뺴앗을 수 있도록 할지라도 어떤 기준으로 빼앗을지, 빼앗은 시간 중 얼마나 사용할지 결정하기가 어렵습니다. 게다가 이러한 방법은 아사 현상을 일으킵니다.

아사 현상을 해결하기 위해 에이징을 사용하는 것도 힘듭니다. 따라서 비선점 조건을 무력화하기가 어렵습니다.

점유와 대기 예방

프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법입니다. 다시 말해 '전부 할당하거나 아예 할당하지 않는(all or nothing)' 방식을 적용하는 것입니다. 이를 위해 프로세스는 작업 초기에 자신이 사용하려는 모든 자원을 한꺼번에 점유하거나, 그렇지 못할 경우 자원을 모두 반납해야 합니다.

상호 배제 예방과 비선점 예방은 자원에 대한 제약을 풀어버리는 것입니다. 그러나 임계구역으로 보호받는 자원에 대한 제약을 풀기는 어렵습니다. 점유와 대기 예방은 자원이 아닌 프로세스의 자원 사용 방식을 바꿔 교착 상태를 처리한다는 점에서 의미가 있습니다. 한편 점유와 대기 예방에는 다음과 같은 단점이 있습니다.

• 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어렵습니다.
• 자원의 활용성이 떨어집니다.
• 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리합니다.
• 결국 일괄 작업 방식으로 동작합니다.

원형 대기 예방

점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법입니다.

자원을 한 방향으로만 사용하도록 설정하면 원형 대기를 예방할 수 있습니다. 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당하는 것입니다.

원형 대기 예방은 모든 자원을 할당받아야 실행할 수 있는 점유와 대기 예방보다 완화된 방법입니다. 그러나 이 또한 다음과 같은 단점이 있습니다.

• 프로세스 작업 진행에 유연성이 떨어집니다.
• 자원에 번호를 어떻게 부여할지가 문제입니다.
  자원을 보호해야 하므로 상호 배제 예방과 비선점 예방은 사용하기 어렵고 점유와 대기 예방, 원형 대기 예방은 프로세스 작업 방식을 제한하고 자원을 낭비하기 때문에 사용할 수 없습니다.

3. 교착 상태 회피

교착 상태 회피의 개념

교착 상태 회피는 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어주는 방법입니다. 교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고, 교착 상태가 발생하는 범위에 있으면 프로세스를 대기시킵니다.

교착 상태 예방은 프로세스의 작업 방식을 제약하기 때문에 사용할 수 없었는데, 교착 상태 회피는 시스템의 운영 방식에 변경을 가하지 않기 때문에 교착 상태 예방보다 좀 더 유연합니다.

교착 상태 회피에서는 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정상태(safe state)와 불안정 상태(unsafe state)로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당합니다. 할당된 자원이 적으면 안정 상태가 크고, 할당된 자원이 늘어나면 불안정 상태가 커집니다. 그렇다고 불안정 상태에서 항상 교착 상태가 발생하는 것은 아닙니다. 교착 상태는 불안정 상태의 일부분이며, 불안정 상태가 커질수록 교착 상태가 발생할 가능성이 높아질 뿐입니다. 교착 상태 회피에서는 안정 상태를 유지할 수 있는 범위 내에서 자원을 할당함으로써 교착 상태를 피합니다.

은행원 알고리즘

교착 상태 회피를 구현하는 방법은 에츠허르 테이크스트라가 제안한 은행원 알고리즘(banker's algorithm)입니다. 은행이 대출해 주는 방식, 즉 대출 금액이 가능한 범위 내이면(안정 상태이면) 대출이 허용되지만 그렇지 않으면 거부되는 것과 유사하기 때문에 이러한 명칭이 붙었습니다.

은행원 알고리즘에서는 최악의 경우를 기준으로 삼음으로써 문제 상황을 철저히 피하여 교착 상태를 막습니다.

교착 상태 회피의 문제점

교착 상태 회피의 원칙은 교착 상태가 발생하지 않을 수준까지만 자원을 나누어주는 것입니다. 하지만 여기에는 다음과 같은 문제가 있어서 실제 시스템에서는 교착 상태 회피를 사용하지 않습니다.

• 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 합니다.
• 시스템의 전체 자원 수가 고정적이어야 합니다.
• 자원이 낭비됩니다.
  교착 상태 회피에서는 실제로 교착 상태가 발생하지 않는데도 발생할 것이라고 예상하고 프로세스에 자원을 할당하는 데 제약을 둡니다.

4. 교착 상태 검출

타임아웃

타임아웃을 이용한 교착 상태 검출은 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법입니다.

윈도우에서 '프로그램이 응답이 없어 종료합니다'라는 메시지를 본 적이 있을 텐데 이것이 타임아웃을 이용하는 방법의 대표적인 예입니다. 타임아웃을 이용한 방식에는 다음과 같은 문제가 있습니다.

• 엉뚱한 프로세스가 강제 종료될 수 있습니다.
• 모든 시스템에 적용할 수 없습니다.

타임아웃으로 데이터의 일관성이 깨지는 문제를 해결하기 위해 데이터베이스에서는 체크포인트(check point)와 롤백(roll back)을 사용합니다. 체크포인트는 작업을 하다가 문제가 발생하면 저장된 상태로 되돌아오기 위한 표시입니다. 체크포인트를 설정하면 현재의 시스템 상태가 하드디스크에 저장되며 이러한 데이터를 스냅숏(snap shot)이라고 합니다. 롤백은 작업을 하다가 문제가 발생하여 과거의 체크포인트로 되돌아가는 것을 말합니다. 롤백이 일어나면 저장된 스냅숏을 복원하여 시스템을 체크포인트 시점으로 되돌립니다.

자원 할당 그래프를 이용한 교착 상태 검출

교착 상태를 검출하는 또 다른 방법은 자원 할당 그래프를 이용하는 것입니다.

5. 교착 상태 회복

교착 상태가 검출되면 교착 상태를 푸는 후속 작업을 하는데 이를 교착 상태 회복이라고 합니다. 교착 상태 회복 단계에서는 교착 상태를 유발한 프로세스를 강제로 종료합니다.

• 교착 상태를 일으킨 모든 프로세스를 동시에 종료합니다.
• 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료합니다.
  프로세스 종료 순서를 정할 때는 다음과 같은 기준이 필요합니다.
  1. 우선순위가 낮은 프로세스를 먼저 종료합니다.
  2. 우선순위가 같으면 작업 시간이 짧은 프로세스를 먼저 종료합니다.
  3. 위의 두 조건이 같으면 자원을 많이 사용하는 프로세스를 먼저 종료합니다.