[혼공학습단 9기] 혼.공.컴.운. - 13. 교착상태

13-1 교착상태란

교착 상태란 무엇이며, 그를 표현하는 자원 할당 그래프와 교착 상태의 발생 원인을 예시를 통해 알아보겠습니다.

프로세스를 실행하기 위해 자원이 필요한데, 두 개 이상의 프로세스가 각자 가지고 있는 자원을 무작정 기다린다면 그 어떤 프로세스도 더 이상 진행할 수 없는 교착 상태가 된다.

 

식사하는 철학자 문제

 

식사하는 철학자 문제: 교착 상태를 설명하기 위한 아주 고전적이고 재미있는 문제 상황. 만약 원탁에 다섯 명의 철학자가 앉아 있고 서로의 사이사이에 총 다섯 개의 포크가 있고, 모두가 동시에 빈 포크가 어떤 것인지 생각하고 동시에 포크를 집어 식사를 해야 한다면, 영원히 아무도 식사할 수 없는 상황이 벌어질 수 있다.

 

교착 상태: 이렇게 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상

 

자원 할당 그래프

 

어떤 프로세스가 어떤 자원을 사용하고 있고, 또 어떤 프로세스가 어떤 자원을 기다리고 있는지를 표현하는 간단한 그래프로, 교착 상태를 단순하게 표현해 준다.

 

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

첫째, 프로세스는 원으로, 자원의 종류는 사각형으로 표현합니다.

둘째, 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현합니다.

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

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

 

교착 상태 발생 조건

 

상호 배제, 점유와 대기, 비선점, 원형 대기

 

상호 배제

 

한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 경우

 

점유와 대기

 

자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태

 

비선점

 

어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 경우

 

원형 대기

 

프로세스들이 원의 형태로 자원을 대기하는 것

 

13-2 교착 상태 해결 방법

운영체제는 교착 상태를 회피할 수도, 예방할 수도, 검출 후 회복할 수도 있다.

 

교착 상태 예방

 

교착상태를 예방하는 방법은 13-1절에서 설명한 교착 상태 발생 필요 조건 네 가지 중 하나를 충족하지 못하게 하는 방법과 같다.

 

자원의 상호 배제를 없애는 법

 

모든 자원을 공유 가능하게 만든다 -> 현실에서 사용하기에는 다소 무리가 있다.

 

점유와 대기를 없애는 법

 

특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분한다. -> 자원의 활용률이 낮아지거나 많은 자원을 사용하는 프로세스가 불리해진다. 많은 자원을 필요로 하는 프로세스가 무한정 기다리게 되는 기아 현상이 야기될 수 있다.

 

비선점 조건을 없애는 법

 

자원을 이용 중인 프로세스로부터 해당 자원을 뺏을 수 있도록 한다. -> 선점하여 사용할 수 있는 일부 자원(예: CPU)에 대해서는 효과적이나, 범용성이 떨어진다.

 

원형 대기 조건을 없애는 법

 

모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당한다. 앞선 세 방식에 비하면 비교적 현실적이고 실용적이지만, 번호를 붙일 자원이 너무 많고 각 자원에 어떤 번호를 붙이는지에 따라 특정 자원의 활용률이 떨어질 수 있다는 단점이 있다.

 

 

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

 

교착 상태 회피

 

교착 상태 회피: 교착 상태가 발생하지 않을 정도로만 조심해서 자원을 할당하는 방식. 교착 상태를 한정된 자원의 무분별한 할당으로 인해 발생하는 문제로 간주한다. 프로세스들에 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 정도의 양만큼만 자원을 배분한다.

 

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

 

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

 

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

 

교착 상태 검출 후 회복

 

교착 상태 검출 후 회복: 교착 상태 발생을 인정하고 사후에 조치하는 방식. 프로세스들이 자원을 요구할 때마다 그때그때 모두 할당하며, 교착 상태 발생 여부를 주기적으로 검사한다. 그리고 교착 상태가 검출되면 그 때 비로소 다음과 같은 방식으로 회복한다.

 

선점을 통한 회복

교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식

 

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

 

가장 단순하면서 확실한 방식. 교착 상태에 놓인 프로세스를 모두 강제 종료하거나 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료한다.

 

 

타조 알고리즘: 교착 상태를 아예 무시하는 방법. 때때로 이 방식이 적합할 때도 많다. (문제 발생의 빈도에 따라)