13장 교착 상태

13-1 교착 상태란

식사하는 철학자 문제

• 동그란 원탁에 다섯 명의 철학자가 앉아 있고, 철학자들 앞에는 맛있는 식사가 있고, 철학자들 사이 사이에는 식사에 필요한 포크가 있다. 그리고 철학자들 앞에 있는 식사는 두 개의 포크로 먹을 수 있는 음식이라 가정하자.

 

• 과연 철학자들은 무사히 식사를 마칠 수 있을까? 모든 철학자가 동시에 포크를 집어 식사를 한다면 어떤 철학자도 식사를 할 수 없고 영원히 생각만 하는 상황이 발생할 것이다.
• 이렇게 일어나지 않을 사건을 기다리며 진행을 멈춰 버리는 현상을 교착 상태라고 한다.
• 철학자는 프로세스 혹은 스레드, 포크는 자원, 생각하는 행위를 자원을 기다리는 것에 빗대어 볼 수 있다. 포크는 한 번에 하나의 프로세스 혹은 스레드만 접근할 수 있으니 임계 구역이라고 볼 수 있다.
• 교착 상태는 아주 다양한 상황에서 발생한다. 앞서 배운 뮤텍스 락에서도 교착 상태가 발생할 수 있다.
• 예를 들어 프로세스 A는 임계 구역 진입 전 lock1을 잠그고, 프로세스 B는 임계 구역 진입 전 lock2를 잠갔다고 가정한다면, 프로세스 A는 lock2가 풀리길 기다리고, B는 lock1이 풀리길 기다린다면 교착 상태가 발생한다.
• 이런 교착 상태를 해결하기 위해서는
  • 교착 상태가 발생했을 때의 상황을 정확히 표현하기
  • 교착 상태가 일어나는 근본적인 원인에 대해 알기

교착 상태 해결 방법

1. 교착 상태가 발생했을 때의 상황을 정확히 표현하기

자원 할당 그래프

• 어떤 프로세스가 어떤 자원을 사용하고 있고, 또 어떤 프로세스가 어떤 자원을 기다리고 있는지 표현하는 간단한 그래프이다.
• 아래와 같은 규칙으로 그려진다.
  1. 프로세스는 원으로, 자원의 종류는 사각형으로 표현한다.

     

  2. 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현한다.
     1. 같은 자원이라해도 사용 가능한 자원의 개수는 여러 개 있을 수 있다. 예를 들어, 하드 디스크가 세 개 있는 경우 자원의 종류는 하드 디스크 하나지만, 사용 가능한 하드 디스크 개수는 세 개 이다.
     2. 따라서 하드 디스크는 사각형 안에 세 개의 점으로 표현한다. 또한 CPU가 두 개 있는 경우 자원의 종류는 CPU 하나지만, 사용 가능한 CPU 개수는 두 개이므로 CPU 사각형 안에 두 개의 점으로 표현한다.

        

  3. 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시한다.
     1. 예를 들어, 아래 그림은 ‘하드 디스크 자원 하나는 프로세스 A에 할당되었고, CPU는 프로세스 B, C에 할당되었음’을 표현한 자원 할당 그래프이다. 프로세스가 자원 이용을 끝내고 운영체제에 자원을 반납하면 화살표는 삭제된다.

     

  4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시한다.
     1. 아래 그림은 ‘프로세스 D가 CPU의 할당을 기다리고 있음’을 나타낸 그래프라고 볼 수 있다.

     

• 교착 상태가 발생한 상황은 자원 할당 그래프가 원의 형태를 띄고 있다.

 

 

 

 

2. 교착 상태가 일어나는 근본적인 이유 이해하기

• 교착 상태가 발생할 조건이 있는데, 조건들 중 하나라도 만족하지 않는다면 교착 상태가 발생하지 않지만, 모두 만족한다면 교착 상태가 발생한다.
• 교착 상태가 발생할 조건 : 상호 배제, 점유와 대기, 비선점, 원형 대기

상호 배제

• 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태

점유와 대기

• 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태

비선점

• 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태

원형 대기

• 프로세스들이 원의 형태로 자원을 대기하는 상태

13-2 교착 상태 해결 방법

교착 상태 예방

교착 상태 발생 필요 조건 네 가지(상호 배제, 점유와 대기, 비선점, 원형 대기) 중 하나의 조건이라도 만족시키지 않게 하자

---

상호 배제 없애기

자원의 상호 배제를 없앤다는 의미는 모든 자원을 공유 가능하게 만든다는 말과 같은데, 이는 현실적으론 어렵다.

점유와 대기 없애기

이건 마치 식사하는 철학자 문제 속 철학자들에게 포크를 두 개 동시에 들게 하거나, 아예 들지 못하게 하는 것과 같다. 점유와 대기를 없애면 운영체제는 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분한다.

이론적으로는 해결할 수 있지만 자원의 활용률이 낮아질 수 있고, 많은 자원을 사용하는 프로세스가 불리해진다. 자원을 많이 사용하는 프로세스는 자원을 적게 사용하는 프로세스에 비해 동시에 자원을 사용할 타이밍을 확보하기 어렵기 때문이다. 결국 많은 자원을 필요로 하는 프로세스가 무한정 기다리게 되는 기아 현상을 야기할 우려가 있다.

비선점 조건 없애기

비선점 조건을 없애면 자원을 이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있다. 식사하는 철학자 문제에서 철학자의 포크를 빼앗을 수만 있다면 교착 상태는 발생하지 않듯 자원의 비선점 조건을 없애면 교착 상태는 발생하지 않는다.

이 방식은 CPU 같은 일부 자원에 대해서는 효과적이지만, 한 번에 하나의 프로세스만 이용 가능한 프린트 자원은 이 방식이 어렵다. 다소 범용성이 떨어지는 방안이다.

원형 대기 조건 없애기

모든 자원에 번호를 붙이고 오름차순으로 자원을 할당하면 원형 대기는 발생하지 않는다. 이는 마치 철학자들이 원형 식탁이 아닌 사각형 식탁에서 일렬로 앉아 식사하는 상황과 유사하다.

원형 대기를 없앰으로써 교착 상태를 예방하는 방식은 앞선 세 방식에 비하면 비교적 현실적이고 실용적인 방식이지만, 단점이 있다. 모든 컴퓨터 시스템 내에 존재하는 수많은 자원에 번호를 붙이는 것은 어렵고, 각 자원에 어떤 번호를 붙이는지에 따라 특정 자원의 활용률이 떨어질 수 있다.

이렇듯 교착 상태의 발생 조건을 원천적으로 제거하여 교착 상태를 사전에 방지하는 예방 방식은 교착 상태가 발생하지 않음을 보장할 수는 있지만 여러 부작용이 따른다.

교착 상태 회피

교착 상태 회피는 교착 상태가 발생하지 않을 정도로만 조심 조심 자원을 할당하는 방식이다. 교착 상태 회피 방식에서는 교착 상태를 무분별한 자원의 할당으로 인해 발생하는 문제로 간주한다.

식사하는 철학자 문제를 생각해보면, 포크가 100개 있는 상태에서 철학자들이 한 두개만 요구한다면 교착 상태는 발생하지 않는다. 반면 포크의 양이 충분하지 않은 상태에서 철학자들 모두가 자신이 요구할 수 있는 최대의 포크를 요구하면 교착 상태가 발생한다.

그렇기 때문에 프로세스들에 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 정도의 양만큼만 자원을 배분하는 방법이 교착 상태 회피이다.

• 안전 상태 : 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태
• 불안전 상태 : 교착 상태가 발생할 수도 있는 상황
• 안전 순서열 : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
  • 안전 상태 : 안전 순서열대로 프로세스들에 자원을 배분하여 교착 상태가 발생하지 않는 상태
  • 불안전 상태 : 안전 순서열이 없는 상황. 시스템이 불안전 상태에 놓이면 교착 상태가 발생할 수 있는 위험이 있다.

교착 상태 검출 후 회복

교착 상태 예방과 회피는 교착 상태 발생을 막기 위한 노력이었다면, 교착 상태 검출 후 회복은 교착 상태 발생을 인정하고 사후에 조치하는 방식이다.

선점을 통한 회복

교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식이다. 교착 상태가 해결될 때까지 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에 할당한다.

프로세스 강제 종료를 통한 회복

가장 단순하면서 확실한 방법이다. 교착 상태에 놓은 프로세스를 모두 강제 종료하거나 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료한다. 전자는 한 방에 해결할 수 있지만 그만큼 많은 프로세스들이 작업 내역을 잃을 가능성이 있고, 후자는 작업 내역을 잃는 프로세스는 최대한 줄일 수 있지만 교착 상태가 없어졌는지 여부를 확인하는 과정에서 오버헤드를 야기한다.