[운영체제] 교착 상태

이 글은 혼자 공부하는 컴퓨터 구조+운영체제 교재와 강의를 참고하여 정리한 글입니다. 오타나, 잘못된 내용이 있으면 언제든지 알려주세요! 감사합니다.😊

 

교착 상태 

교착 상태란 (deadlock)

프로세스를 실행하기 위해서는 자원이 필요한데, 두 개 이상의 프로세스가 각자 가지고 있는 자원을 무작정 기다린다면 그 어떤 프로세스도 더 이상 진행할 수 없는 상태가 된다. 이런 상태를 교착 상태(dead lock)라고 한다.

이러한 교착 상태는 언제 어떻게 발생할까?

 

식사하는 철학자 문제  (dining philosophers problem)

식사하는 철학자 문제

• 식사하는 철학자 문제는 교착 상태를 잘 설명할 수 있는 가상의 문제 시나리오이다. 
  • 동그란 원탁에 다섯 명의 철학자가 앉아 있다.
  • 철학자들 앞에는 맛있는 식사가 있고, 철학자들 사이사이에는 식사에 필요한 포크가 있다.
  • 그리고 철학자들 앞에 있는 식사는 두 개의 포크로 먹을 수 있는 음식이라 가정한다.
  • 철학자들은 다음과 같은 순서로 식사를 한다.
    1. 계속 생각을 하다가 왼쪽 포크가 사용 가능하면 집어든다.
    2. 계속 생각을 하다가 오른쪽 포크가 사용 가능하면 집어든다.
    3. 왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간 동안 식사를 한다.
    4. 식사 시간이 끝나면 오른쪽 포크를 내려놓는다.
    5. 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓는다.
    6. 다시 1번부터 반복한다.

 

모든 철학자들이 동시에 위와 같은 순서로 식사를 한다고 가정해 보자. 철학자들은 무사히 식사를 마칠 수 있을까? 그렇지 않다.

• 한두 명의 철학자가 식사할 때는 아무 문제가 없지만 모든 철학자가 동시에 집어 식사를 하면 어떤 철학자도 식사를 할 수 없고 영원히 생각만 하는 상황이 발생할 수 있다.
• 왜냐하면 모든 철학자가 왼쪽 포크를 집어들면 모두가 오른쪽 포크를 집어 들 수 없기 때문이다.
• 즉, 모든 철학자는 다른 철학자가 포크를 내려놓을 때까지 기다린다.
• 이처럼 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상을 교착 상태(deadlock)이라 한다.
• 철학자는 프로세스 혹은 스레드, 포크는 자원, 생각하는 행위는 자원을 기다리는 것에 빗대어 볼 수 있다.
  • 포크는 한 번에 하나의 프로세스 혹은 스레드만 접근할 수 있으니 임계 구역이라고 볼 수 있다.

 

• 게임 프로세스는 자원 A를 점유한 채 웹 브라우저 프로세스가 점유하고 있는 자원 B의 사용이 끝나길 기다린다.
• 웹 브라우저 프로세스는 자원 B를 점유한 채 게임 프로세스가 점유하고 있는 자원 A의 사용이 끝나길 기다린다.
• 이 경우 자원을 기다리기만 하다가 결국 실행을 하지 못하는 상황이 벌어지는데 이를 교착 상태라 한다.

 

교착 상태를 해결하기 위해서는 어떻게 해야할까?

1. 교착 상태가 발생했을 때의 상황을 정확히 표현해 보기
2. 교착 상태가 일어나는 근본적인 이유를 이해하기

 

자원 할당 그래프

교착 상태가 발생했을 때의 상황을 한눈에 보기 쉽게 그래프로 표현하는 방법이 있다. 교착 상태는 자원 할당 그래프(resource-allocation graph)를 통해 단순하게 표현할 수 있다. 자원 할당 그래프를 통해 교착 상태 발생 조건을 파악할 수 있다.

• 어떤 프로세스가 어떤 자원을 할당받아 사용 중인지 확인 가능하다.
• 어떤 프로세스가 어떤 자원을 기다리고 있는지 확인 가능하다.

 

자원 할당 그래프는 다음과 같은 규칙으로 그린다.

• 첫째, 프로세스는 원으로, 자원의 종류는 사각형으로 표현한다.
• 둘째, 사용할 수 있는 자원의 개수는 자원 사각형 내 점으로 표현한다.
  • 같은 자원이라 해도 사용 가능한 자원의 개수는 여러 개 있을 수 있다.

• 셋째, 프로세스가 어떤 자원을 할당 받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시한다.
  • 프로세스가 자원 이용을 끝내고 운영체제에 자원을 반납하면 화살표는 삭제된다.

하드 디스크 자원 하나는 프로세스 A에 할당되었다.

• 넷째, 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시한다.

프로세스 D가 CPU의 할당을 기다리고 있다.

 

식사하는 철학자 문제를 자원 할당 그래프로 표현해 보자.

포크는 자원, 철학자는 프로세스와 같다.

 

교착 상태를 자원 할당 그래프로 표현해 보자.

게임과 웹 브라우저 교착 상태 예시를 자원 할당 그래프로 표현한 것이다.

 

여기서 자세히 살펴보면 교착 상태가 일어난 그래프의 특징을 찾을 수 있다. 교착 상태가 발생한 상황은 자원할당 그래프가 원의 형태를 띠고 있다. 교착 상태가 일어나는 근본적인 이유에 대해서 이해해 보자.

 

교착 상태 발생 조건

• 교착 상태가 발생할 조건에는 네 가지가 있다.
  1. 상호 배제 (mutual exclusion)
  2. 점유와 대기 (hold and wait)
  3. 비선점 (nonpreemptive)
  4. 원형 대기 (circular wait)
• 만약 위 네 가지 조건 중 하나라도 만족하지 않으면 교착 상태가 발생하지 않는다.
• 만약 위 네 가지 조건을 모두 만족하면 교착 상태가 발생할 수 있다. (발생할 가능성이 생김)

 

상호 배제

• 교착 상태가 발생한 근본적인 원인은 해당 자원을 한 번에 하나의 프로세스만 이용 가능했기 때문이다.
  • 하나의 포크를 여러 명이 동시에 사용할 수 없었기 때문에 문제가 발생했다.
• 상호 배제는 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 상태를 말한다.

 

점유와 대기

• 자원을 보유한 채 다른 자원을 기다렸기 때문에 문제가 발생했다.
  • 왼쪽 포크를 들고 다른 철학자의 포크를 기다렸기 때문에 문제가 발생했다.
• 점유와 대기는 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태를 말한다.

 

비선점

• 비선점 자원은 그 자원을 이용하는 프로세스의 작업이 끝나야만 이용할 수 있다.
  • 철학자들은 포크를 기다리기만 했기 때문에 문제가 발생했다.
  • 다른 철학자의 포크를 강제로 빼앗을 수 있었다면 교착 상태는 발생하지 않았다.
• 비선점은 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태를 말한다. 

 

원형 대기

• 자원 할당 그래프가 원의 형태로 그려지면 교착 상태가 발생할 수 있다.
• 원형 대기는 프로세스들이 원의 형태로 자원을 대기하는 상태를 말한다.

참고: 자원 할당 그래프가 원의 형태를 띠지 않는다면 교착 상태는 발생하지 않지만, 원의 형태를 띤다고 해서 반드시 교착 상태가 발생하는 것은 아니다.

그렇다면 교착 상태를 어떻게 해결할까?

 

교착 상태 해결 방법

• 교착 상태를 해결하는 방법에는 크게 세 가지가 존재한다.
  1. 예방: 운영체제는 애초에 교착 상태가 일어나지 않도록 교착 상태 발생 조건에 부합하지 않게 자원을 분배한다.
  2. 회피: 교착 상태가 발생하지 않을 정도로 조금씩 자원을 할당하다가 교착 상태의 위험이 있다면 자원을 할당하지 않는다.
  3. 검출 후 회복: 자원을 제약 없이 할당하다가 교착 상태가 검출되면 교착 상태를 회복한다.

 

교착 상태 예방

• 교착 상태 예방은 애초에 교착 상태가 발생하지 않도록 하는 방법이다.
• 교착 상태 발생 조건인 상호 배제, 점유와 대기, 비선점, 원형 대기 중 하나를 없애버리면 된다.

 

상호 배제를 없애기

• 자원의 상호 배제를 없앤다는 말은 모든 자원을 공유 가능하게 만든다는 말과 같다.
• 현실적으로 모든 자원의 상호 배제를 없애기는 어려워 사용하기에는 어렵다.

 

점유와 대기를 없애기

• 점유와 대기를 없애면 운영체제는 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분한다.
  • 철학자들로 하여금 한 손에 포크를 들고 다른 포크를 기다리지 못하게 금지하는 것과 같다.
• 이론적으로 교착 상태를 해결할 수 있지만 자원의 활용률이 낮아진다는 우려가 있다.
  • 한 프로세스에 필요한 자원들을 몰아주고, 그다음에 다른 프로세스에 필요한 자원들을 몰아줘야 한다.
  • 이는 당장 자원이 필요해도 기다릴 수밖에 없는 프로세스와 사용되지 않으면서 오랫동안 할당되는 자원을 다수 양산 하기 때문에 자원의 활용률이 낮아진다.
• 많은 자원을 사용하는 프로세스가 불리해진다.
  • 자원을 많이 사용하는 프로세스는 자원을 적게 사용하는 프로세스에 비해 동시에 자원을 사용할 타이밍을 확보하기가 어렵기 때문이다.
  • 이는 결국 많은 자원을 필요로 하는 프로세스가 무한정 기다리게 되는 기아 현상을 야기하는 우려가 있다.

 

비선점을 없애기

• 비선점 조건을 없애면 자원을 이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있다.
  • 철학자의 포크를 빼앗을 수만 있다면 교착 상태는 발생하지 않는다.
• 비선점 조건을 없애는 방식은 선점하여 사용할 수 있는, 선점이 가능한 자원에 한해 효과적이다. 
  • CPU는 프로세스들이 선점할 수 있는 대표적인 자원이다.
  • 한 프로세스가 CPU를 이용하다가 일정 시간이 지나면 아직 작업이 모두 끝나지 않았더라도 다른 프로세스가 CPU를 할당받아 사용할 수 있기 때문이다.
• 하지만 모든 자원이 선점 가능한 것은 아니다.
  • 한 프로세스의 작업이 끝날 때까지 다른 프로세스가 기다려야 하는 자원도 얼마든지 있다.
  • 따라서 비선점 조건을 없애 모든 자원을 빼앗을 수 있도록 하여 교착 상태를 예방하는 것은 다소 범용성이 떨어진다.

 

원형 대기를 없애기

• 원형 대기를 없애는 방법은 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하면 원형대기는 발생하지 않는다.
  • 모든 포크에 1번부터 5번까지 번호를 붙이고, 철학자들로 하여금 번호가 낮은 포크에서 높은 포크 순으로 집어 들게 하면 원형 대기는 발생하지 않는다.
  • 왜냐하면 5번 포크를 집어 들고 1번 포크를 집어들 수 없기 때문이다.

• 이는 마치 원형 식탁이 아닌 사각형 식탁에서 일렬로 앉아 식사하는 것과 유사하다.
  • 동시에 포크를 들어도 문제 될 것이 없다.
• 하지만 단점이 존재한다.
  • 모든 컴퓨터 시스템 내에서 존재하는 수많은 자원에 번호를 붙이는 것은 어려운 작업이다.
  • 어떤 자원에 어떤 번호를 붙이느냐에 따라 자원의 활용률이 달라진다.
  • 예) 많이 활용되는 자원이 붙어있는 번호가 낮으면 많이 활용되지 못할 수 있다.

 

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

 

교착 상태 회피

• 교착 상태 회피는 교착 상태가 발생하지 않을 정도로만 조금씩 자원을 할당하는 방식이다.
• 교착 상태를 한정된 자원의 무분별한 할당으로 인해 발생하는 문제로 간주한다.
• 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 만큼만 자원을 배분한다.  

 

안전 순서열

• 안전 순서열은 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 말한다.
  • 웹 브라우저, 메모장, 게임 프로세스가 동시에 운영체제에 자원을 요청한 상황에서 웹 브라우저-메모장-게임 프로세스 순서대로 자원을 할당하면 교착 상태가 발생하지 않는다고 가정하자.
  • 이 경우 안전 순서열은 웹 브라우저 -> 메모장 -> 게임이다.

 

안전 상태

• 안전 상태는 교착 상태 없이, 교착 상태가 발생하지 않고 모든 프로세스가 자원을 할당받고 종료될 수 있는 상태를 말한다.
• 안전 순서열이 있는 상태를 안전 상태라고 볼 수 있다.

 

불안전 상태

• 불안전 상태는 교착 상태가 발생할 수도 있는 상황을 말한다.
• 안전 순서열이 없는 상태를 불안전 상태라고 볼 수 있다.

 

다음 예시를 통해 이해해 보자.

• 컴퓨터 시스템에 총 열 두 개의 자원이 있다.
• P1, P2, P3 세 개의 프로세스가 실행 중이며, 각각 5개, 2개, 2개의 자원을 할당받아 실행 중이다.
  • 운영체제가 배분할 수 있는 자원은 3개 남았다.
• 프로세스 P1, P2, P3는 각각 최대 10개, 4개, 9개 자원을 요구할 수 있다고 가정하자.

참고: 프로세스와 스레드는 자원을 사용하기 위해 첫째, 우선 자원을 운영체제에 요청한다. 둘째, 운영체제로부터 자원을 할당받아 사용한다. 셋째, 자원의 사용이 끝났다면 자원을 반환한다.

 

표로 나타내면 다음과 같다.

• 할당 가능 자원은 12개이다.
• 할당한 자원은 P1, P2, P3 현재 사용량의 총합인 9이다.
• 남은 자원은 (할당 가능 자원 - 할당한 자원)이므로 3이다.
• 안전 순서열이 존재한다. P2 -> P1 -> P3

 

프로세스 P1, P2, P3 각각 5개, 2개, 7개로 모두 최대로 추가로 자원을 요구한 상황을 가정해 보자. (최악의 상황)

• 프로세스 P2는 이미 자원 2개를 가지고 있으므로 남은 자원에서 2개를 배분하면 된다.
• 할당 가능 자원은 12개이다.
• 할당한 자원은 P1, P2, P3 현재 사용량의 총합인 9 + 2 = 11이다.
• 남은 자원은 (할당 가능 자원 - 할당한 자원)이므로 3 - 2 = 1이다.

 

• 4개의 자원을 할당받은 프로세스 P2는 정상적으로 작업을 끝내고 가지고 있던 자원을 반환한다.
• 할당 가능 자원은 12개이다.
• 할당한 자원은 P1, P2, P3 현재 사용량의 총합인 11 - 4 = 7이다.
• 남은 자원은 (할당 가능 자원 - 할당한 자원)이므로 1 + 4 = 5이다.

 

• P1에 남은 자원 5개를 할당하면 P1 또한 정상적으로 작업을 완료할 수 있다.
• 할당 가능 자원은 12개이다.
• 할당한 자원은 P1, P2, P3 현재 사용량의 총합인 7 + 5 = 12이다.
• 남은 자원은 (할당 가능 자원 - 할당한 자원)이므로 5 - 5  = 0이다.

 

• 프로세스 P1은 정상적으로 작업을 끝내고 가지고 있던 자원을 반환한다. P3에 자원을 할당하면 된다.
• 할당 가능 자원은 12개이다.
• 할당한 자원은 P1, P2, P3 현재 사용량의 총합인 12 - 10 = 2이다.
• 남은 자원은 (할당 가능 자원 - 할당한 자원)이므로 0 + 10 = 10이다.
• P2 -> P1 -> P3 안전 순서열 대로 자원을 배분하면 모든 프로세스가 자원을 할당받고 교착 상태 없이 올바르게 작업을 마칠 수 있다.

 

만약 동일한 상황에서 운영체제가 P3에게 먼저 선뜻 자원을 하나 내주었다고 가정해 보자.

• 할당 가능 자원은 12개이다.
• 할당한 자원은 P1, P2, P3 현재 사용량의 총합인 10이다.
• 남은 자원은 (할당 가능 자원 - 할당한 자원)이므로 2이다.
• 이런 상황은 불안전 상태이다. 즉, 안전 순서열이 존재하지 않고 교착 상태가 발생할 위험이 있다.

 

프로세스 P1, P2, P3 각각 5개, 2개, 6개로 모두 최대로 추가로 자원을 요구한 상황을 가정해 보자. (최악의 상황)

• 할당 가능 자원은 12개이다.
• 할당한 자원은 P1, P2, P3 현재 사용량의 총합인 10 + 2 = 12이다.
• 남은 자원은 (할당 가능 자원 - 할당한 자원)이므로 2 - 2 = 0이다.

 

• 할당 가능 자원은 12개이다.
• 할당한 자원은 P1, P2, P3 현재 사용량의 총합인 12 - 4 = 8이다.
• 남은 자원은 (할당 가능 자원 - 할당한 자원)이므로 0 + 4 = 4이다.
• 프로세스 P2에게 2개의 자원을 배분하여 P2 작업을 끝내도, 남은 자원으로는 P1, P3의 요구를 들어줄 수 없다. 즉, 불안전 상태로 교착 상태가 발생한 것이다.
• 즉, 운영체제가 교착 상태를 회피하기 위해서는 시스템 상태가 안전상태에서 안정 상태로 움직이는 경우에만 자원을 할당하면 된다.
  • 항시 안전 상태를 유지하도록 자원을 할당하는 방식이다.
  • c.f. 은행원 알고리즘

 

교착 상태 검출 후 회복

• 교착 상태 검출 후 회복은 교착 상태의 발생을 인정하고 사후에 조치하는 방식이다.
• 운영체제는 프로세스가 자원을 요구할 때마다 그때그때 모두 할당하고, 교착 상태 발생 여부를 주기적으로 검사한다. 교착 상태가 검출되면 회복한다.
• 교착 상태 검출 후 회복에는 다음과 같은 방식이 있다.
  • 선점을 통한 회복
  • 프로세스 강제 종료를 통한 회복

 

선점을 통한 회복

• 선점을 통한 회복은 교착 상태가 해결될 때까지 한 프로세스의 자원을 몰아주는 방식이다.
• 즉, 교착 상태가 해결될 때까지 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에 할당하는 방식이다.

 

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

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

 

타조 알고리즘

• 타조 알고리즘은 교착 상태를 무시하는 방법이다.
• 드물게 발생하는 잠재적 문제를 무시로 대처하는 방식이다.
• 문제 발생의 빈도나 심각성에 따라 최대 효율을 추구하는 엔지니어 입장에서는 이 방식이 적합할 때도 많다.