교착상태
설명에 앞서 다음 예시를 확인해보자.
식사하는 철학자 문제
동그란 테이블 위 5명의 철학자들이 앉아있고, 철학자들 사이에는 포크가 놓여있다. 식사를 하기위해서는 2개의 포크가 필요하고, 철학자들은 다음과 같은 과정으로 행동한다.
결과는 어떻게 될까?
그 누구도 식사를 할 수 없게된다. 예를 들어 모두가 왼쪽 포크를 집어든다면, 모든 철학자가 오른쪽 포크를 집어들 수 없고 기다리게 된다.
교착상태는 일어나지 않을 사건을 기다리며 진행이 멈춰버리는 현상이다.
철학자를 프로세스 또는 스레드, 포크를 자원이라고 볼 수 있다.
교착상태 해결을 위해
자원 할당 그래프 - 교착상태가 발생했을 때의 상황을 정확히 표현하기
자원할당 그래프를 통해 어떤 프로세스가 어떤 자원을 할당 받아 사용중인지, 어떤 프로세스가 어떤 자원을 기다리고 있는 지 확인할 수 있다.
자원 할당 그래프는 다음과 같이 제작할 수 있다.
- 프로세스를 원으로, 자원을 사각형으로 그린다.
- 사용할 수 있는 자원의 개수는 사각형 내부에 점으로 표현한다.
- 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원->프로세스 방향의 화살표를 표시한다.
- 프로세스가 어떤 자원을 기다리고 있다면 프로세스->자원 방향으로 화살표를 표시한다.
이 자원 할당 그래프에서 알 수 있는 점들은 다음과같다.
프로세스 A는 3개의 SSD를 할당받아 사용하고 있다
프로세스 B,C는 각각 하나의 CPU를 할당받아 사용하고 있다.
프로세스 D는 프린터를 사용하고 있다.
프로세스 E는 프린터의 사용을 기다리고 있다.
프로세스 F는 CPU의 할당을 기다리고 있다.
교착상태의 자원 할당 그래프는 아래와 같다.
4가지 발생 조건 - 교착상태가 일어나는 근본적인 이유 이해하기
교착상태가 발생할 네 가지 조건이 있다. 이중 하나라도 만족하지 않는다면 교착상태가 발생하지 않으며, 모든 조건을 만족하면 교착상태가 발생 할 수도 있다.
상호배제
한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
점유와 대기
자원을 할당받은 상태에서 다른 자원을 할당 받기를 기다리는 상태
비선점
어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태
원형 대기
프로세스들이 원의 형태로 자원을 대기하는 상태
교착상태 예방
교착상태 발생 조건 중 하나를 없애 버리는 방법이 있다.
상호 배제를 없앤다면?
모든 자원을 공유 가능하게 만든다. 현실적으로는 불가능
점유와 대기를 없앤다면?
특정 프로세스에 자원을 몰빵하거나, 아예 주지 않는 방식
but, 자원의 활용률이 낮아질 수 있다.
비선점을 없앤다면?
선점이 가능한 자원(CPU)에 한해 효과적!
but, 모든 자원이 선점 가능한 것은 아니다.
원형 대기를 없앤다면?
모든 자원에 번호를 붙이고, 오름차순으로 할당하는 방법. 가장 현실적이고 실용적!
but, 자원에 번호를 붙이는 것이 어렵고, 어떤 자원에 어떤 번호를 붙이느냐에 따라 활용률이 달라진다
교착상태 예방은 교착상태가 발생하지 않음은 보장할 수 있으나, 부작용이 따르는 방식이다.
교착상태 회피
교착상태를 무분별한 자원 할당으로 인해 발생했다고 간주한다.
교착상태가 일어나지 않도록 조심조심 할당하는 방법
은행원 알고리즘을 확인해보자.
안전 순서열
교착상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
안전상태
교착상태 없이 모든 프로세스가 자원을 할당받고 종료될 수 있는 상태
안전 순서열이 있는 상태
불안전상태
교착상태가 발생할 수도 있는 상태
안전 순서열이 없는 상태
예시를 보자.
표로 나타내면 아래와 같다.
운영체제는 남은 3개의 자원을 어떻게 배분해야 할까?
만약 세 프로세스에서 최대한의 자원을 요구한다고 한다면 아래의 표와 같아진다.
교착상태를 피하기 위한 안전 순서열이 존재한다. p2 -> p1 -> p3
위의 안전 순서열대로, 자원을 나누어보자.
p2에 분배하고 나서의 표이다. p2에는 최대 요구량의 자원이 들어가고, 실행이 종료되면 운영체제로 자원을 반환하게 된다.
이렇게 생긴 남은 자원 5개를 p1에 모두 제공하면, p1 역시 실행될 수 있다.
이를 안전상태라고 한다.
만약 안전 순서열과 다르게 자원을 분배한다면?
p3에게 먼저 자원 하나를 나누어 준 뒤의 표이다.
이 때도 최대의 자원을 요구한다면 p1,p2,p3가 각각 5개,2개,6개의 자원을 요구하는 셈이다.
이러한 상황에서는 남은 자원을 모두 분배해도 세 프로세스 중 어떤 프로세스도 먼저 끝낼 수 없는 교착상태에 빠지게 된다.
이를 불안전상태라고 한다.
교착상태 검출 후 회복
선점을 통한 회복
교착상태가 해결될 때까지 하나의 프로세스에 자원을 몰아준다.
프로세스 강제 종료를 위한 회복
교착상태에 놓인 프로세스를 모두 강제 종료하는 법 (확실하지만, 작업 내역을 잃을 위험이 있음)
or
교착상태가 해결될 때까지 프로세스를 하나씩 종료하는 법 (계속 확인해봐야해서 오버헤드)
출처 한빛미디어 혼자 공부하는 컴퓨터 구조+운영체제
