✅ 교착 상태란
프로세스를 실행하기 위해서는 자원이 필요한데, 두 개 이상의 프로세스가 각자 자기가 가지고 있는 자원을 무작정 기다린다면 그 어떤 프로세스도 더 이상 진행할 수 없는 교착상태가 된다.
식사하는 철학자 문제
식사하는 철학자 문제 dining philosphers problem 는 교착 상태를 설명하기 위한 아주 고전적이고 재밌는 문제 상황이다. 동그란 원탁에 다섯 명의 철학자가 앉아 있다. 이 철학자들 앞에는 맛있는 식사가 있고, 철학자들 사이 사이에는 식사에 필요한 포크가 있다. 그리고 철학자들 앞에 있는 식사는 두 개의 포크로 먹을 수 있는 음식이라고 가정한다. 해당 철학자들은 아래와 같은 순서로 식사를 한다.
- 계속 생각을 하다가 왼쪽 포크가 사용 가능하면 집어든다.
- 계속 생각을 하다가 오른쪽 포크가 사용 가능하면 집어든다.
- 왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간동안 식사를 한다.
- 식사 시간이 끝나면 오른쪽 포크를 내려놓는다.
- 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓는다.
- 다시 처음부터 반복한다.
모든 철학자가 동시에 포크를 집어들어 식사를 하면 어떤 철학자도 식사를 할 수 없고 영원히 생각만 해야하는 상황이 발생할 수 있다. 모든 철학자가 왼쪽 포크를 집어들면 모두가 오른쪽 포크를 집어 들 수 없기 때문이다. ➡️ 모든 철학자는 다른 철학자가 포크를 내려놓을 때까지 기다린다.
이렇게 일어나지 않을 사건을 기다리며 진행이 멈춰버리는 현상을 교착 상태 deadlock라고 한다.
식사하는 철학자 문제에서 철학자는 프로세스 혹은 스레드, 포크는 자원, 생각하는 행위는 자원을 기다리는 것에 빗대어 볼 수 있다. 포크는 한 번에 하나의 프로세스만 접근할 수 있으므로 임계 구역이라고 볼 수 있다.
이러한 교착 상태를 해결하기 위해서는 교착 상태가 발생했을 때의 상황을 정확히 표현해 보고, 교착 상태가 일어나는 근본적인 이유에 대해 알아야 한다.
자원 할당 그래프
교착 상태는 자원 할당 그래프resource-allocation graph 를 통해 단순하게 표현할 수 있다. 자원 할당 그래프는 어떤 프로세스가 어떤 자원을 사용하고 있고, 또 어떤 프로세스가 어떤 자원을 기다리고 있는지를 표현하는 간단한 그래프이다.
🔎 프로세스는 원으로, 자원의 종류는 사각형으로 표현한다.
🔎 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현한다.
같은 자원이라고 할지라도 사용 가능한 자원의 개수는 여러 개 있을 수 있다. 
🔎 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시한다.
프로세스가 자원 이용을 끝내고 운영체제에 자원을 반납하면 화살표는 삭제된다.
🔎 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시한다.
교착 상태가 발생한 자원 할당 그래프는 원의 형태를 띄고 있다.
교착 상태 발생 조건
교착 상태가 발생할 조건에는 네 가지가 있다. 상호 배제, 점유와 대기, 비선점, 원형 대기이다. 아래의 조건 중 하나라도 만족하지 않는다면 교착 상태가 발생하지 않는다.
🔎 상호 배제 mutual execlusion
교착 상태가 발생하는 근본적인 원인은 하나의 자원을 한 번에 하나의 프로세스만 이용 가능하기 때문이다. 즉, 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때, 즉 상호배제 상황에서 교착 상태가 발생할 수 있다.
🔎 점유와 대기 hold and wait
어떠한 자원을 할당 받은 상태에서 다른 자원을 할당받기를 기다린다면 교착 상태가 발생할 수 있다. 이렇게 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태를 점유와 대기 이라고 한다.
🔎 비선점 nonpreemptive
비선점 자원은 그 자원을 이용하는 프로세스의 작업이 끝나야만 비로소 이용할 수 있다. 즉, 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하기 때문에 교착 상태가 발생한다.
🔎 원형 대기 circular wait
프로세스들과 프로세스가 요청 및 할당 받은 자원들이 원의 형태를 이룬것이다. 즉, 프로세스가 원의 형태로 자원을 대기하는 것을 원형 대기라고 한다.
원의 형태를 띈다고 해서 반드시 교착 상태가 발생하는 것은 아니다.
✅ 교착 상태 해결 방법
운영체제는 교착 상태를 회피할 수도, 예방할 수도, 검출 후 회복할 수도 있다.
- 교착 상태 발생 조건에 부합하지 않게 자원을 분배하여 교착상태를 예방
- 교착 상태가 발생하지 않을 정도로 조금씩 자원을 할당하다가 교착 상태의 위험이 있다면 자원을 할당하지 않는 방식으로 교착 상태를 회피
- 자원을 제약 없이 할당하다가 교착 상태가 검출되면 교착 상태를 회복
교착 상태 예방 (Prevention)
교착 상태 발생 필요 조건 네 가지 중 하나를 충족하지 못하게 하는 방법
즉, 프로세스들에 자원을 할당할 때 상호 배제, 점유와 대기, 원형대기, 비선점 중 하나의 조건이라도 만족하지 않게 할당하면 교착 상태는 발생하지 않는다.
🔎 상호배제
상호 배제를 없애기 위해 모든 자원을 공유 가능하게 만든다. 이론적으로는 교착 상태를 없앨 수 있지만, 현실적으로 모든 자원의 상호배제를 없애기는 어렵다. ➡️ 현실에서 사용하기엔 무리가 있다.
🔎 점유와 대기
점유와 대기를 없애면 운영체제는 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 못하게 하는 방식으로 배분한다.
이론적으로는 교착상태를 해결할 수 있지만, 단점도 있다.
-
자원의 활용률이 낮아진다. (필요한 자원들을 몰아주고, 그 다음 다른 프로세스에 자원을 몰아준다.) ➡️ 당장 자원이 필요해도 기다릴 수 밖에 없는 프로세스와 사용되지 않으면서 오랫동안 할당되는 자원을 다수 양산하기 때문
-
많은 자원을 사용하는 프로세스가 불리해진다. (자원을 적게 사용하는 프로세스에 비해 동시에 자원을 사용할 타이밍을 확보하기 어렵기 때문) ➡️ 기아 현상 야기
🔎 비선점
자원을 이용중인 프로세스로부터 해당 자원을 빼앗을 수 있다.
- 선점하여 사용할 수 있는 일부 자원에 대해서는 효과적이다. (예. CPU)
- 선점 가능하지 않은 자원이 존재한다. (예. 프린터)
🔎 원형 대기
모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하면 원형 대기는 발생하지 않는다. 비교적 현실적이고 실용적이지만 단점이 있다.
- 존재하는 수많은 자원에 번호를 붙이기 어렵다.
- 어떤 번호를 붙이는지에 따라 특정 자원의 활용률이 떨어진다.
교착 상태의 발생조건을 원천적으로 제거하여 교착 상태를 사전에 방지하는 예방 방식은 교착 상태가 발생하지 않음을 보장할 수 는 있지만 여러 부작용이 따른다.
교착 상태 회피 (Avoidance)
교착 상태가 발생하지 않을 정도로만 조심 조심 자원을 할당하는 방식이다.
교착 상태 회피 방식에서는 교착 상태를 자원의 무분별한 할당으로 인해 발생하는 문제로 간주한다. 프로세스들에 할당할 수 있는 자원이 충분한 상황에서 프로세스들이 한두 개의 적은 자원만을 요구한다면 교착 상태는 발생하지 않는다. 반면 프로세스들에 할당할 수 있는 자원이 한정된 상황에서 모든 프로세들이 한 번에 많은 자원을 요구하면 교착 상태가 발생할 위험이 증가한다.
프로세스들에 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 정도의 양만큰만 자원을 배분하는 방법이 교착 상태 회피이다.
- 안전 상태 (
safe state): 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태 - 불안전 상태 (
unsafe state): 교착 상태가 발생할 수도 있는 상황 - 안전 순서열(
safe sequence): 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서 (안전 순서열이 있는 상태를 안전 상태라고 한다. 안전 순서열이 없는 상황은 불안전 상태라고 한다.➡️ 교착 상태가 발생할 수 있다.)
운영체제가 교착 상태를 회피하기 위해서는 시스템 상태가 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하면 된다. => 교착 상태 회피는 항시 안전 상태를 유지하도록 자원을 할당하는 방식이다.
교착 상태 검출 후 회복 (Recovery)
교착 상태 발생을 인정하고 사후에 조치하는 방식이다.
프로세스들이 자원 요청 시마다 모두 할당하며, 교착 상태 발생 여부를 주기적으로 검사한다. 교착 상태가 검출되면 회복한다.
🔎 선점을 통한 회복
교착 상태가 해결될 때까지 한 프로세스 씩 자원을 몰아주는 방식이다. 다른 프로세스로부터 자원을 강제로 뺴앗고 한 프로세스에 할당하는 방식이다.
🔎 프로세스 강제 종료를 통한 회복
교착 상태에 놓인 프로세스를 모두 강제 종료하거나 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료한다.
교착 상태를 아예 무시하는 방법인 타조 알고리즘(
ostrich algorithm)도 존재한다.
