[운영체제] 교착 상태

‘혼자 공부하는 컴퓨터구조+운영체제 - 강민철’ 책을 참고하여 작성한 포스트입니다.

---

교착상태

교착 상태란, 두 개 이상의 작업이 서로 상대방의 작업이 끝나기를 기다리고 있는 상태로, 결과적으로 아무것도 완료되지 못하는 상태이다.

• 교착 상태를 해결하기 위해,
  • 교착 상태 발생 시의 상황을 정확히 표현해 보고,
  • 교착 상태가 일어나는 근본적인 이유를 알야아 한다.

자원 할당 그래프

• 자원 할당 그래프(resource-allocation graph)는 어떤 프로세스가 어떤 자원을 사용할 수 있고, 또 어떤 프로세스가 어떤 자원을 기다리고 있는지를 표현하는 간단한 그래프이다.
• 결론으로, 교착 상태가 발생한 상황은 자원 할당 그래프가 원의 형태를 띄고 있다.

교착 상태 발생 조건

교착 발생 조건에는 상호 배제, 점유와 대기, 비선점, 원형 대기 가 있다. 하나라도 만족하지 않는다면 교착 상태가 발생하지 않는다.

상호 배제

• 상호 배제 상황에서 교착 상태 발생이 가능하다

점유와 대기(hold and wait)

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

비선점

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

원형 대기(circular wait)

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

교착 상태 해결 방법

해결 방법에는 크게 1. 예방, 2. 회피, 3. 검출 후 회복 이 있다.

교착 상태 예방

교착 상태 발생 조건에 부합하지 않게 자원을 분배하여 교착 상태를 예방한다.

1. 자원의 상호 배제 제거
   • 모든 자원을 공유 가능하게 만든 말이다.
   • 현실적으로 모든 자원의 상호 배제를 없애기는 어렵기에 불가능하다
2. 점유와 대기 제거
   • 특정 프로세스에 자원을 모두 할당하거나, 아예 안하는 방법이다.
   • 당장 자원이 필요해도 기다릴 수밖에 없는 프로세스가 생기고,
   • 사용되지 않으면서 오랫동안 할당되는 자원을 다수 양산하여 자원의 활용률이 낮아진다.
   • 자원을 많이 사용하는 프로세스에 기아 현상이 나타날 수 있다.
3. 비선점 조건 제거
   • 일부 자원에는 효과적일 수 있으나,
   • 특정 자원은 선점 조건 시 문제가 생길 수 있다.
4. 원형 대기 조건 제거
   • 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하는 방법이 있다
   • 하지만 수많은 자원에 번호를 붙이는 것은 어려운 작업이며,
   • 번호 부여에 따라 자원의 활용률이 떨어질 수 있다.

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

교착 상태 회피

교착 상태가 발생하지 않을 정도로 조금식 자원을 할당하다가 위험하면 자원을 할당하지 않는 방식

• 안전 상태(safe state)
  • 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태
• 불안전 상태(unsafe state)
  • 교착 상태가 발생할 수도 있는 상황
• 안전 순서열(safe sequence)
  • 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
  • 이 순서에 따라 프로세스들에 자원 배분된 상태가 안전 상태
  • 그렇지 않고 안전 순서열이 없는 상태가 불안전 상태

설명

• 프로세스와 스레드는 자원을 사용하기 위해 1. 우선 자원을 운영체제에 요청하고, 2. 운영체제로부터 자원을 할당받고, 3. 자원의 사용이 끝나면 자원을 반환한다.

프로세스	요구량	현재 사용량
P1	10	5
P2	4	2
P3	9	2

• 위의 경우 할당 가능 자원이 12면 안전 상태이다. P2 -> P1 -> P3 이라는 안전 순서열이 있기 때문이다.

프로세스	요구량	현재 사용량
P1	10	5
P2	4	2
P3	9	3

• 이 경우는 불안전 상태죠

교착 상태를 회피하기 위해서는 시스템 상태가 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하면 된다.

교착 상태 검출 후 회복

교착 상태 발생하면 조치하는 방식
자원 할당할 때마다 교착 상태 발생 여부를 주기적으로 검사하며, 검출되면 다음과 같은 방식으로 해결한다.

선점을 통한 회복

• 다른 프로세스로부터 자원을 가져와 몰아주는 방식이다.

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

• 운영체제는 교착 상태에 놓인 프로세스를 모두 강제 종료할 수도 있고,
  • 확실하지만 많은 프로세스가 작업 내역을 잃을 수 있다.
• 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료할 수도 있다.
  • 교착 상태가 없어졌는지 여부를 확인하는 과정에서 오버헤드 발생

정리

• 교착 상태는 일어나지 않을 사건을 기다리며 무한히 대기하는 현상
• 식사하는 철학자 문제는 교착 상태의 발생을 보여 주는 예시
• 자원 할당 그래프를 이용해 교착 상태 표현 가능
• 교착 상태 발생 조건은 상호 배제, 점유와 대기, 비선점, 원형 대기
• 교착 상태 예방은 교착 상태의 발생 조건 중 하나를 충족하지 못하게 하는 방법
• 교착 상태 회피는 안전 상태를 유지하는 경우에만 자원 할당하는 방법
• 교착 상태 검출 후 회복은 교착 상태 발생 여부를 주기적으로 확인하고, 발생 시 회복하는 방식