혼공 컴+운 chapter13. 교착 상태

13-1. 교착 상태란

식사하는 철학자 문제

- 동그란 원탁에 다섯 명의 철학자가 앉아 있다. 이 철학자들 앞에는 맛있는 식사가 있고, 철학자들 사이 사이에는 식사에 필요한 포크가 있다. 그리고 철학자들 앞에 있는 식사는 두 개의 포크로 먹을 수 있는 음식이라 가정.

이 철학자들은 아래와 같은 순서로 식사를 한다.

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

모든 철학자가 동시에 포크를 집어 식사를 하면 어떤 철학자도 식사를 할 수 없고 영원히 생각만 하는 상황이 발생할 수 있다. 모든 철학자가 왼쪽 포크를 집어들면 모두가 오른쪽 포크를 집어들 수 없다. 모든 철학자는 다른 철학자가 포크를 내려놓을 때까지 기다린다.

• 교착상태 : 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상
• 교착 상태 해결
  
  • 교착 상태가 발생했을 때의 상황을 정확히 표현
  • 교착 상태가 일어나느 근본적인 이유에 대해 알아야 한다.

자원 할당 그래프

• 어떤 프로세스가 어떤 자원을 사용하고 있고, 또 어떤 프로세스가 어떤 자원을 기다리고 있는지를 표현하는 간단한 그래프.
• 규칙
  • 프로세스는 원으로, 자원의 종류는 사각형으로 표현
  • 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현
  • 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시.
  • 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시
• 교착 상태가 발생한 상황은 자원 할당 그래프가 원의 형태를 띄고 있다.

교착 상태 발생 조건

• 상호배제 : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상황
• 점유 대기 : 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
• 비선점 : 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태
• 원형대기 : 프로세스들이 원의 형태로 자원을 대기하는 것. 

13-2. 교착 상태 해결 방법

교착 상태 예방

• 자원의 상호 배제를 없앤다. = 모든 자원을 공유가능하게 만든다. 하지만, 이론적으로는 교착상태를 없앨 수 있지만, 현실적으로 모든 자원의 상호 배제를 없애기는 어렵다.
• 점유와 대기를 없앤다.  : 운영체제는 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분. 
  • 단점 : 우선 자원의 활용률이 낮아질 우려가 있다. 점유와 대기를 금지하면 한 프로세스에 필요한 자원들을 몰아주고, 그 다음에 다른 프로세스에 필요한 자원들을 몰아줘야 한다. 당장 자원이 필요해도 기다릴 수밖에 없는 프로세스와 사용되지 않으면서 오랫동안 할당되는 자원을 다수 양산하기 때문에 자원의 활용률이 낮아진다. 
  • 많은 자원을 사용하는 프로세스가 불리해진다.자원을 많이 사용하는 프로세스는 자원을 적게 사용하는 프로세스에 비해 동시에 자원을 사용할 타이밍을 확보하기가 어렵기 때문이다. 기아현상을 야기할 우려가 있다.
• 비선점 조건을 없앤다. : 자원을 이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있다. 
  • 선점하여 사용할 수 있는 일부 자원에 대해서는 효과적이다. 
  • 단점 : 모든 자원이 이렇게 선점 가능한 것은 아니다. 비선점 조건을 없애 모든 자원을 빼앗을 수 있도록 하여 교착상태를 예방하는 방법은 범용성이 떨어지는 방안이다. 
• 원형 대기 조건을 없앤다. 
  • 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당한다. 
  • 현실적이고 실용적인 방식
  • 단점 : 모든 컴퓨터 시스템 내에 존재하는 수많은 자원에 번호를 붙이는 일이 간단한 작업이 아니고, 각 자원에 어떤 번호를 붙이는지에 따라 특정 자원의 활용률이 떨어질 수 있다. 

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

교착 상태 회피

• 교착 상태가 발생하지 않을 정도로만 조심 조심 자원을 할당하는 방식. 교착 상태를 한정된 자원의 무분별한 할당으로 인해 발생하는 문제로 간주. 프로세스들에 할당할 수 있는 자원이 한정된 상황에서 모든 프로세스들이 한 번에 많은 자원을 요구함녀 교착 상태가 발생할 위험이 증가. 
• 프로세스들에 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 정도의 양만큼만 자원을 배분하는 방법. 
• 안전 상태 : 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당 받고 종료될 수 있는 상태. 안전 순서열대로 프로세스들에 자원을 배분하여 교착 상태가 발생하지 않는 상태.
• 불안전 상태 : 교착 상태가 발생할 수도 있는 상황. 안전 순서열이 없는 상황. 
• 안전 순서열 : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 의미.
• EX)

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

• 할당 가능 자원 : 12
• 할당한 자원(P1, P2, P2 현재 사용량의 총합) : 9
• 남은 자원(할당 가능 자원 - 할당한 자원) : 12- 9 = 3
• 이 상태는 안전상태. P2->P1->P3이라는 안전 순서열이 있다.

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

• 할당 가능 자원 : 12
• 할당한 자원(P1,P2,P3 현재 사용량의 총합): 9+2=11
• 남은 자원 : (할당 가능 자원 - 할당한 자원) : 3 - 2 = 1

=> 요구한 네 개의 자원을 할당받은 P2는 정상적으로 작업을 끝내고 가지고 있던 자원을 반환. 그러면 남은 자원은 4+1=5개가 된다. 

• 할당 가능 자원 : 12
• 할당한 자원(P1,P2,P3 현재 사용량의 총합): 11 - 4 = 7
• 남은 자원 (할당 가능 자원 - 할당한 자원) : 1+4 = 5

=> P1에 남은 자원 다섯 개를 할당하면 P1 또한 작업을 정상적으로 완료 할 수 있다.

• 할당 가능 자원 : 12
• 할당한 자원(P1, P2, P3 현재 사용량의 총합): 7+5 = 12
• 남은 자원(할당 가능 자원 - 할당한 자원) : 5 - 5 = 0

=> P1이 작업을 정상적으로 마치고 자원을 반환하면 이제 P3에 자원을 할당하면 된다. 

• 할당 가능 자원 : 12
• 할당한 자원(P1, P2, P3 현재 사용량의 총합):12 - 10 = 2
• 남은 자원(할당 가능 자원 - 할당한 자원) : 0 + 10 = 10

- 운영체자가 P3에 만저 선뜻 자원을 하나 내주었다고 생각. 

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

• 할당 가능 자원 : 12
• 할당한 자원 : 10
• 남은 자원 : 2

=> 이 상황은 불안전 상태이다. 교착 상태가 발생할 위험이 있다. 

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

• 할당 가능 자원 : 12
• 할당한 자원 : 10 + 2 = 12
• 남은 자원 : 0

=======================================================================================

• 할당 가능 자원 : 12
• 할당한 자원 : 12 - 4 = 8
• 남은 자원 : 0 + 4 = 4

교착 상태 검출 후 회복

• 선점을 통한 회복 : 교착 상태가 해결 될 때까지 한 프로세스씩 자원을 몰아주는 방식. 교착 상태가 해결될 때까지 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에 할당하는 방식.
• 프로세스 강제 종료를 통한 회복 
• 잠재적 문제를 무시로 대처(타조 알고리즘)