교착 상태란

식사하는 철학자 문제

동그란 원탁에 다섯명의 철학자가 앉아 있습니다. 철학자들 앞에는 식사가 있고, 철학자들 사이 사이에는 포크가 있습니다. 식사는 두개의 포크로 먹을 수 있는 음식입니다.

철학자들은 다음과 같은 순서로 식사를 합니다.

1. 생각을 하다가 왼쪽 포크가 사용 가능하면 잡는다.
2. 생각을 하다가 오른쪽 포크가 사용 가능하면 잡는다.
3. 왼쪽과 오른쪽 포크를 모두 잡으면 정해진 시간 동안 밥을 먹는다.
4. 식사 시간이 끝나면 오른쪽 포크를 내려놓는다.
5. 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓는다.
6. 다시 1번 부터 반복하다.

여기서, 모든 철학자들이 동시에 포크를 집게 되면 영원이 식사를 못 할 수 있어요!
모든 철학자가 왼쪽 포크를 잡으면 남은 포크가 없어서 오른쪽 포크를 잡을 수 없습니다.
모든 철학자는 다른 철학자가 포크를 내려놓을 때까지 기다려야 합니다.
➡️ 이렇게 일어나지 않을 사건을 기다리면서 진행이 멈춰 버리는 것을 교착 상태라 합니다.

🤩 철학자 = 프로세스 / 스레드
포크 = 자원(임계 구역)
생각하는 행위 = 자원을 기다리는 것

프로세스들이 서로 상대방이 가진 자원을 기다리기만 하다가 실행을 못하는 상황

자원 할당 그래프

: 어떤 프로세스가 어떤 자원을 사용하고 있고, 어떤 프로세스가 어떤 자원을 기다리고 있는지를 표현하는 그래프

자원 할당 그래프를 그리는 규칙

• 프로세스는 원으로, 자원의 종류는 사각형으로 표현

• 사용할 수 있는 자원의 개수는 자원 사각형 안에 점으로 표현

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

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

교착 상태를 그림으로 표현해보자

• 식사하는 철학자 문제
  
  ➡️ 교착 상태가 발생한 상황은 자원 할당 그래프가 원의 형태를 띄게 됩니다.

교착 상태 발생 조건

아래의 조건이 모두 만족 되어야만 교착 상태가 발생할 가능성이 생깁니다.

• 상호 배제
  : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 경우

• 점유와 대기
  : 자원을 할당받은 상태에서 다른 자원을 할당받기 위해 기다리는 상태
  

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

• 원형 대기
  : 프로세스들이 원의 형태로 자원을 대기하는 상태
  자원 할당 그래프가 원의 형태라고 반드시 교착 상태가 발생하는 것은 아님!!

교착 상태 해결 방법

🧐 운영체제는 교착 상태를 어떻게 해결할까?

교착 상태가 일어나지 않도록 자원을 분배하여 교착 상태를 예방하거나
교착 상태의 위험이 있다면 자원을 할당하지 않는 방식으로 교착 상태를 회피하거나
교창 상태가 검출되면 교착 상태를 회복하는 방법을 취할 수 있다.

교착 상태 예방

: 교착 상태 발생 필요 조건 네 가지 중 하나를 충족하지 못하게 한다.

• 자원의 상호 배제를 없애 볼까요?
  : 모든 자원을 공유 가능하게 만든다.
  현실적으로 모든 자원의 상호 배제를 없애기는 어려워요 🥲

• 그렇다면 점유와 대기를 없애 봅시다.
  운영체제는 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분
  식사하는 철학자 문제에서 포크를 두개 동시에 들게 하거나, 아예 들지 못하게 하는 겁니다.
  ➡️ 자원의 활용률이 낮아질 수 있어요.
  ➡️ 기아 현상이 발생할 수 있어요.
  

• 이번에는 비선점 조건을 없애 봅시다.
  : 자원을 이용 중인 프로세스로부터 해당 자원을 뺏는다.
  CPU 경우는 선점할 수 있지만, 프린터와 같은 자원은 선점할 수 없어요🥲
  

• 마지막으로 원형 대기 조건을 없애 봅시다.
  : 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당한다.
  자원에 어떻게 번호를 붙이는지에 따라 특정 자원의 활용률이 떨어질 수 있다.
  

예방 방식은 교착 상태가 발생하지 않음을 보장할 수는 있지만 부작용이 따릅니다

교착 상태 회피

: 교착 상태가 발생하지 않을 정도로만 조심 조심 자원을 할당한다.

프로세스들에 배분할 수 있는 자원의 양을 고려해서 교착 상태가 발생하지 않을 정도의 양만큼만 자원을 배분한다.

안전 상태
: 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태
안전 순서열대로 프로세스들에 자원을 배분하여 교착상태가 발생하지 않는 상태

불안전 상태
: 교착 상태가 발생할 수도 있는 상황. 안전 순서열이 없는 상황

안전 순서열
: 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
안전 순서열이 있는 상태를 안전 상태라고 볼 수 있어요.

➡️ 안전 순서열대로 자원을 배분하면 교착 상태 없이 올바르게 작업을 마칠 수 있어요!

교착 상태 검출 후 회복

: 교착 상태 발생을 인정하고 사후에 조치하는 방식

• 선점을 통한 회복
  : 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식이다.

• 프로세스 강제 종료를 통한 회복
  : 교착 상태에 놓인 프로세스를 모두 강제 종료하거나, 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료한다.
  프로세스들이 작업 내역을 잃을 수 있고, 교착 상태가 없어졌는지 확인하는 과정에서 오버헤드를 야기할 수 있다.
  

😎 타조 알고리즘
: 교착 상태를 아예 무시하는 방법