프로세스 교착상태

교착상태란?

프로세스는 실행되기 위해서 CPU,메모리 등등의 여러 자원을 사용한다. 

이때 각자 자원을 점유한 프로세스들이 다른 자원이 필요한데 이를 다른 프로세스가 사용하고 있어서 갖지 못하고 대기 상태에 들어가게되면서 발생하는 현상이다.

마치 교차로에 자동차들이 오도가도 못하는 상황을 그려보면 된다.

 

교착상태 발생의 필요 충분 조건

교착상태가 발생하기 위해서는 다음의 네가지 조건이 충족되어야 하는데, 이 네가지 조건중 하나라도 충족되지 않으면 교착상태가 발생하지 않는다

상호배제(Mutual Exclusion)  : 한번에 한개의 프로세스만이 공유 자원을 사용할 수 있어야 한다.

점유와 대기(Hold and Wait) : 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 이해 대기하는 프로세스가 있어야 한다.

비선점(Non-preemption): 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야한다.

환형 대기(Circular Wait): 공유자원과 공유자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 필요로 하는 상황이다.

 

식사하는 철학자가 대표적인 예시로 많이 이야기된다.

한 명의 철학자가 젓가락을 가지고 있으면 다른 철학자는 가질 수 없다. 보유 및 대기는 한 짝의 젓가락을 가지고 있는 상태에서 다른 젓가락을 기다리고 있는 경우와 같다. 철학자가 젓가락을 가지고 있으면 다른 철학자가 젓가락을 뺏을 수 없으므로 비선점도 만족된다. 또한 원형 테이블에서 이루어지는 형태로 환형대기도 만족되어 결국 식사하는 철학자들은 교착상태에 빠지게 되는 것이다.

출처 : https://copycode.tistory.com/72

 

교착상태의 근본적인 발생원인은 바로 자원이다. 프로세스가 메모리에서 동작할 때 자원에 대한 요청을 운영체제에 전달하게 되는데, 이때 운영체제는 누구도 자원을 사용하지 있지 않을 경우 할당하게 해준다. 

이 때 어떤 자원이 어떤 프로세스에게 할당되었는지 어떤 프로세스가 할당받으려고 기다리고 있는지에 대한 정보를 가르쳐주는 지표가 자원할당도이다. 프로세스가 어떠한 자원을 화살표로 가리키면 자원을 요청한 것이고, 자원이 프로세스를 화살표로 가리키면 프로세스에게 할당되어 사용 중이다. 교착 상태가 발생하면 자원 할당도 상에 원이 만들어진다. 

 

교착상태의 해결법

1. 예방하기

 

교착 상태의 네가지 조건 중 하나를 제거. 자원낭비가 심하다.

상호 배제(Mutual Exclusion)부정 : 한번에 여러개의 프로세스가 공유 자원을 사용할 수 있도록.

점유 및 대기(Hold and Wait) 부정 : 프로세스가 실행되기 전 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나 자원이 점유되지 않은 상태에서만 자원을 요구하도록 한다.

비선점(Non-preemption)부정 : 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 한다.

환형 대기(Circular Wait)부정 : 자원을 선형 순서로 분류하여 고유 번호를 할당하고, 각 프로세스는 현재 점유한 자원의 고유 번호보다 앞이나 뒤 어느 한쪽 방향으로만 자원을 요구하도록 하는것이다.

 

2. 발생 후 대처 

 

회피 기법(Avoidance)

교착상태 회피 기법은 교착상태가 발생할 가능성을 배제하지 않고 교착상태가 발생하면 적절히 피해나가는 방법으로, 주로 은행원 알고리즘(Banker's Algorithm)이 사용된다.

은행원 알고리즘
1. 은행원 알고리즘은 다익스트라가 제안한 기법으로, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래한 기법입니다.
2. 각 프로세스에게 자원을 할당하여 교착상태가 발생하지 않으며 모든 프로세스가 완료될 수 있는 상태를 안전상태, 교착상태가 발생할 수 있는 상태를 불안전 상태라고 합니다.
3. 은행원 알고리즘을 적용하기 위해서는 자원의 양과 사용자(프로세스) 수가 일정해야 합니다.
4. 은행원 알고리즘은 프로세스의 모든 요구를 유한한 시간안에 할당하는 것을 보장합니다.

 

발견기법(Detection)

교착상태 발견 기법은 시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견하는 것을 의미한다.

교착상태 발견 알고리즘과 자원 할당 그래프 등을 사용 할 수 있다.

 

회복기법(Recovery)

교착상태 회복 기법은 교착상태를 일으킨 프로세스를 종료하거나 교착상태의 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복하는 것을 의미한다.

 - 프로세스 종료

교착상태에 있는 프로세스를 종료하는 것으로, 교착상태에 있는 모든 프로세스를 종료하는 방법과 교착상태에 있는 프로세스들을 하나씩 종료해가며 교착상태를 해결하는 방법이 있다.

 - 자원선점

교착상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하며, 해당 프로세스를 일시 정지시키는 방법. 우선순위가 낮은 프로세스, 수행된 정도가 적은 프로세스, 사용되는 자원이 적은 프로세스 등을 위주로 해당 프로세스의 자원을 선점한다.

※ 자원 선점시 고려사항

1. 자원을 선점할 프로세스 선택 문제 : 최소의 피해를 줄 수 있는 프로세스를 선택.

2. 자원을 선점한 프로세스의 복귀 문제 : 자원이 부족한 상태이므로 대부분 일시 중지시키고 다시 시작하는 방법을 사용한다.

3. 기아 현상 문제 : 한 프로세스가 계속하여 자원 선점 대상이 되지 못하도록 고려해야 한다.