DeadLock (교착 상태)

교착상태란?

둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하여 무한정 기다리게 되는 현상을 데드락(DeadLock). 즉, 교착 상태 라고 합니다.

여러 개의 작업이 동시에 실행되는 멀티 프로세스, 멀티 스레드 프로그래밍 환경에서 발생할 수 있는 이슈입니다.

 

교착 상태에 대해 알아볼 때면 자주 등장하는 예시가 있는데요.

바로, 식사하는 철학자들 입니다.

'식사하는 철학자들'은 운영체제의 교착 상태를 설명하기 위해 다익스크라가 만든 문제라고 합니다.

그 내용은 바로 이렇습니다.

 

5의 철학자들이 원형 식탁에 둘러앉아 식사를 하는데, 철학자들 사이에는 포크가 하나씩 놓여 있다.

철학자들이 식사를 하기위해서 지켜야 하는 규칙이 있는데, 바로 아래와 같다.

1. 왼쪽 포크가 사용가능해질 때까지 생각을 하다가, 사용이 가능해지면 바로 왼쪽 포크를 집어든다.
2. 오른쪽 포크가 사용가능해질 때까지 생각을 하다가, 사용이 가능해지면 바로 오른쪽 포크를 집어든다.
3. 양쪽의 포크를 잡으면 정해진 시간만큼 식사한다.
4. 오른쪽 포크를 내려놓는다.
5. 왼쪽 포크를 내려놓는다.
6. 다시 1번으로 돌아간다.

만약 모든 철학자들이 동시에 자신의 왼쪽 포크를 집어든다면, 모든 철학자들이 자기 오른쪽의 포크가 사용가능해질 때까지 기다리게 됩니다. 하지만 이렇게 되면 모든 철학자는 영원히 오른쪽 포크를 사용할 수 있을 때까지 기다리게 되는데, 이것이 바로 교착상태 입니다.

 

---

 

교착상태 발생 조건

그럼 어떤 조건에서 교착상태가 발생할까요?

교착상태는 아래 4가지 조건이 모두 만족하게 되면 발생합니다.

 

✔️상호 배제 (Mutual Exclusion)

프로세스 간의 공유 자원은 한 번에 한 개의 프로세스에만 할당됩니다.

즉, 여러 프로세스가 동시에 공유 자원을 사용할 수 없습니다.

 

✔️점유와 대기 (Hold and Wait)

최소한 하나의 자원을 점유하고 있으면서 다른  프로세스에게 할당되어 사용되고 있는 자원을 추가적으로 점유하기 위해 대기하는 상태입니다.예를 들어, 프로세스A가 자원 a를 점유하고 있고 b를 사용하기 위해 대기중입니다.이 때, 다른 프로세스C는 자원 a를 사용하기 위해 대기하고 있어서 프로세스A의 작업이 끝날 때까지 대기하게 됩니다.

 

✔️비선점 (Non-preemption)

프로세스가 어떤 자원을 점유하고 있을 때, 이 자원을 다른 프로세스가 강제로 빼앗을 수 없습니다.

 

✔️순환 대기 (Circular Wait)

공유자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어, 자신에게 할당된 자원을 점유하고 있으면서 앞이나 뒤에 있는 프로세스의 자원을 요구하는 상황입니다.

위에서 설명했던 식사하는 철학자들을 예시로 들자면, 그 상황처럼 왼쪽의 포크를 가지고 있는 상태에서 오른쪽 포크를 기다리고 있는 상황이 원형으로 이루어져 무한 대기가 이루어지는 상황입니다.

 

---

 

교착상태 해결하기

교착상태를 해결하는 방법에는 여러가지가 있습니다.

먼저, 교착상태가 발생하지 않도록 사전에 시스템을 제어하는 방법인 예방기법(Prevention)입니다.

위에서 설명했던 교착상태가 발생하는 4가지 조건 중 하나를 제거함으로써 교착상태의 발생을 막는 것인데, 자원 낭비가 가장 심한 기법이라고 할 수 있습니다.

 

✔️상호 배제 제거

👉여러 프로세스가 동시에 공유자원을 사용할 수 있도록 합니다.

👉하지만 이렇게 하면 당연히 공유자원 문제가 발생할 수밖에 없습니다.

✔️점유 및 대기 제거

👉프로세스가 실행되기 전에 필요한 모든 자원을 할당하여 프로세스 대기를 제거합니다.

👉또는, 어떠한 자원도 점유하고 있지 않은 상태에서만 자원을 요구하도록 합니다.

👉하지만 이렇게 하면 한 번에 모든 자원을 요구하고 할당받는 게 효율적이지 않을 뿐더러, starvation(기아 현상)이 발생할 수 있습니다.

✔️비선점 제거

👉다른 프로세스가 점유하고 있던 자원을 뺏어서 사용하는 것을 허용합니다.

👉딱 봐도 위험해보이는 방법입니다.

✔️순환 대기 제거

👉자원을 선형적인 순서로 분류하여 고유번호를 할당하고, 각 프로세스는 현재 점유한 자원의 고유번호보다 앞이나 뒤 어느 한쪽 방향으로만 자원을 요구하도록 하여 원형 꼬리물기를 방지하는 방법입니다.

👉그나마 실현해볼 수 있는 방법입니다.

 

 

 

교착상태를 해결하는 또 다른 방법으로는 회복기법(Recovery)이 있습니다.

교착상태를 일으킨 프로세스를 종료하거나, 교착 상태의 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복하는 것을 의미합니다.

• 프로세스 종료
  • 교착상태에 있는 프로세스를 종료하는 것으로, 교착상태에 있는 모든 프로세스를 종료하는 방법과 교착상태에 있는 프로세스들을 하나씩 종료해가며 해결하는 방법이 있습니다.
• 자원 선점
  • 교착상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하고, 해당 프로세스를 일시정지시키는 방법입니다.
  • 우선순위가 낮은 프로세스, 수행된 정도가 적은 프로세스, 사용되는 자원이 적은 프로세스 등을 위주로 해당 프로세스의 자원을 선점합니다.

  • 자원 선점시 고려해야할 사항

    • 자원을 선점할 프로세스 선택 : 최소의 피해를 줄 수 있는 프로세스 선택

    • 자원을 선점한 프로세스의 복귀 : 자원이 부족한 상태이므로 대부분 일시중시키고 다시 시작하는 방법 사용

    • 기아현상 : 한 프로세스가 계속하여 자원 선점 대상이 되지 못하도록 고려

 

 

마지막으로 회피기법(Avoidance)이 있습니다.

교착상태가 발생할 가능성을 배제하지 않고, 교착상태가 발생하면 적절히 피해나가는 방법입니다.

주로 은행원 알고리즘(Banker's Algorithm)이 사용됩니다.

 

은행원 알고리즘은 교착상태가 발생할 수 있는 상태를 불안전 상태, 그렇지 않은 상태를 안전 상태라 했을 때, 안전 상태가 될 것이 100% 보장되는 경우에만 요청을 받아들입니다.

 

예를 들어, 은행에 2,000원이 있고 고객 3명이 동시에 대출을 요청하는 상황이라고 가정해봅시다.

 

이 때, 현재 가지고 있는 자원인 2,000원으로 안전 상태를 만들 수 있는 고객은 A와 C가 됩니다.

이렇게 현재 가지고 있는 자원으로 안전 상태를 만들 수 있는 경우에만 자원을 할당해주는 것이 은행원 알고리즘 입니다.

 

 

 

 

 

 

Deadlock

[OS] 교착상태란 무엇인가?