교착 상태

 

★ 식사하는 철학자 문제 : 교착 상태를 설명하기 위한 아주 고전적인 문제 상황

• 5명의 철학자(프로세스 혹은 스레드)가 앞에는 맛있는 식사가 있고, 철학자들 사이사이에 포크(자원이자 임계 구역)가 놓여져 있으며, 식사는 두 개의 포크로 먹을 수 있는 음식이라고 가정
• 아래의 순서로 식사를 함
  1. 생각(자원을 기다리는 것)을 하다가 왼쪽 포크가 사용 가능하면 집어듬
  2. 생각을 하다가 오른쪽 포크가 사용 가능하면 집어듬
  3. 왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간동안 식사를 함
  4. 식사 시간이 끝나면 오른쪽 포크를 내려놓음
  5. 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓음
• 만약 모든 철학자가 동시에 포크를 집어 식사를 하면 어떤 철학자도 식사를 할 수 없고, 영원히 생각만 하는 상황이 발생할 수 있음
  => 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상을 교착 상태라고 함

 

 

★ 자원 할당 그래프

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

⭐︎ 자원 할당 그래프 규칙

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

2. 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현

3. 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시

 * 하드 디스크 자원 하나는 프로세스 A에 할당되었고, CPU는 프로세스 B, C에 할당되었음

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

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

• 이러한 방법으로 교착 상태의 자원 할당 그래프도 그릴 수 있음
• 교착 상태가 발생한 상황은 자원 할당 그래프가 원의 형태를 띔!!

 

 

★ 교착 상태 발생 조건
 * 네 가지 조건 중 하나라도 만족하지 않는다면 교착 상태가 발생하지 않지만, 조건이 모두 만족될 때 교착 상태가 발생할 가능성이 생김

1. 상호 배제 : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상황
2. 점유와 대기 : 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
3. 비선점 : 자원을 이용하는 프로세스의 작업이 끝나야만 비로소 이용할 수 있음
4. 원형 대기 : 자원 할당 그래프가 원의 형태로 그려지면 교착 상태가 발생할 수 있음
   (원의 형태를 띈다고 해서 반드시 교착 상태가 발생하는 것은 아님)

 

 

★ 교착 상태 예방

• 교착 상태 발생 필요 조건 네 가지 중 하나를 충족하지 못하게 하는 방법
• 상호 배제
  -> 모든 자원을 공유 가능하게 만든다
  -> 이론적으로는 가능하나, 현실적으로 모든 자원의 상호 배제를 없애기는 어려우므로 현실에서 사용하기에는 무리가 있음
• 점유와 대기
  -> 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식
  -> 자원의 활용률이 낮아질 수 있고, 많은 자원을 사용하는 프로세스는 기아 현상을 야기할 수 있음
• 비선점
  -> 자원을 이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있도록 하는 방법
  -> 일부 자원에 대해서는 효과적이나, 프로세스 순서가 중요한 작업도 있으므로 범용성이 떨어질 수 있음
• 원형 대기 조건
  -> 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하는 방법
  -> 제일 현실적이고 실용적인 방식이지만, 모든 자원에 번호를 붙이는 일은 간단한 작업이 아니며 어떤 번호를 붙이는지에 따라 특정 자원의 활용률이 떨어질 수 있음

 

 

★ 교착 상태 회피

• 교착 상태가 발생하지 않을 정도로만 조심조심 자원을 할당하는 방식
• 할당할 수 있는 자원이 충분한 상황에서 프로세스들이 한두 개의 적은 자원만을 요구한다면 교착 상태는 발생하지 않음
• 운영체제가 교착 상태를 회피하기 위해서는 시스템 상태가 안정 상태에서 안정 상태로 움직이는 경우에만 자원을 할당하면 됨!

⭐︎ 안정 상태 : 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태

⭐︎ 불안정 상태 : 교착 상태가 발생할 수도 있는 상황

⭐︎ 안전 순서열 : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서

* 은행가 알고리즘

- 자원의 할당 허용 여부를 결정하기 전에 미리 결정된 모든 자원의 최대 가능한 할당량을 시물레이션하여 안정 여부를 검사하고 대기 중인 다른 모든 활동의 교착상태 가능성을 조사하여 안정 상태 여부를 검사 확인함

- 프로세스가 자원을 요청할 때마다 운영체제로 실행하며, 자원 요청을 승낙하는 것이 불안정한 상태에서 시스템을 배치할 수 있다고 판단하면 이 요청을 연기하거나 거부하여 교착상태를 예방

 

* 안정 상태

3개의 프로세스, 총자원이 12개, 현재 할당량은 10개, 잔여량은 2개

프로세스	현재 할당량	최대 요구량	추가 요구량
A	2	9	7
B	4	6	2
C	4	8	4

프로세스 B -> 프로세스 C -> 프로세스 A 순으로 자원을 할당하면 모든 프로세스의 수행을 마칠 수 있다.

 

* 불안정 상태

3개의 프로세스, 총자원이 12개, 현재 할당량은 11개, 잔여량은 1개

프로세스	현재 할당량	최대 요구량	추가 요구량
A	6	9	3
B	3	9	6
C	2	4	2

남은 자원 1개로 할당받아 완료될 수 있는 프로세스가 존재하지 않는다.

 

★ 교착상태 탐지

• 시스템이 교착상태 예방 알고리즘을 사용하지 않는다면, 교착상태가 발생할 수 있음
• 교착상태가 발생했는지를 파악하기 위해 시스템의 상태를 검사하는 교착상태 탐지 알고리즘을 수행
• 교착상태를 파악하기 위한 교착상태 탐지 알고리즘의 수행 시기를 결정하기는 어려움
• 교착상태 탐지 알고리즘을 자주 실행하면 시스템의 성능은 떨어짐

 

★ 교착 상태 검출 후 회복

⭐︎ 선점을 통한 회복

• 교착 상태가 해결될 때까지 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스씩 자원을 몰아주는 방식
• 희생자의 선택 : 비용을 최소화하기 위해 선점의 순서를 결정
• 복귀 : 프로세스를 중지하여 완전히 복귀시키고 재시작
• 기아 : 동일한 프로세스가 항상 희생자로 선택되기 쉬움

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

• 교착 상태에 놓인 프로세스를 모두 강제 종료할 수도 있고, 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료할 수도 있음
• 전자는 가장 확실한 방식이지만 그만큼 많은 프로세스 작업 내역을 잃을 수 있고, 후자는 손실은 적을 수 있지만 교착 상태가 없어졌는지 여부를 확인하는 과정에서 오버헤드를 야기

cf. 교착 상태를 아예 무시하는 타조 알고리즘 방식도 존재함

 

Q. 컴퓨터 시스템에서 교착상태의 해결 방안에 대한 설명으로 옳지 않은 것은?

1. 교착상태가 발생할 가능성을 사전에 없앤다. -> 교착상태 예방

2. 하나의 프로세스만이 한 시점에서 하나의 자원을 사용할 수 있게 한다. -> 상호 배제

3. 교착상태가 탐지되면, 교착상태와 관련된 프로세스와 자원을 시스템으로부터 제거한다. -> 교착상태 회복

4. 교착상태가 발생할 가능성을 인정하고, 교착상태가 발생하려고 할 때 이를 회피하도록 한다. -> 교착상태 회피

 

Q. 교착상태의 해결 기법 중 일반적으로 자원의 낭비가 가장 심한 것으로 알려진 기법은?

1. 교착상태 예방

2. 교착상태 회피

3. 교착상태 탐지

4. 교착상태 회복

 

-> 교착상태가 발생하는 네가지 조건 중 어느 하나를 제거함으로써 교착상태가 발생할 가능성을 배제하는 방법으로 자원의 낭비가 가장 심한 기법이다.