교착 상태 1 - 교착 상태란

13장 교착상태에 대해서 공부해보려고 한다. 벌써 새벽 4시가 조금 넘었다. 이 단원만 마치고 오늘 새벽에는 어제 못한 수학 공부도 하고 아침 운동도 하려고 한다. 그러러면 2시간 안에 이 공부를 다 마쳐야 한다.

동시에 실행되는 여러 프로세스는 각자가 필요한 자원을 할당받아 실행된다. 그 과정에서 때로는 프로세스들이 꼼짝도 못하고 정지해 버리는 교착 상태가 발생할 수 있다. 이번 장에서는 교착 상태란 무엇인지, 운영체제는 교착 상태를 어떻게 해결하는지에 대해 알아보겠다.

 

교착 상태를 해결하는 것 또한 운영체제가 맡는 중요한 임무 중 하나이다. 교착 상태란 무엇이며, 그를 표현하는 자원 할당 그래프와 교착 상태의 발생 원인을 예시를 통해 학습해볼 것이다.

 

 

이렇게 교통이 마비되어 버리면 복구되기까지 오랜 시간이 걸릴 뿐더라, 심한 경우 교통 경찰이 직접 와서 마비를 해결해야 한다. 프로세스 실행 과정에도 이와 비슷한 문제가 있다.

프로세스를 실행하기 위해서는 자원이 필요한데, 두 개 이상의 프로세스가 각자 가지고 있는 자원을 무작정 기다린다면 그 어떤 프로세스도 더 이상 진행할 수 없는 교착 상태가 된다. 교착 상태는 정확히 무엇이며, 언제 어떻게 발생하는지 알아보겠다.

---

 

 

 

식사하는 철학자 문제

식사하는 철학자 문제는 교착 상태를 설명하기 위한 아주 고전적이고 재미있는 문제 상황이다. 이 유며한 문제는 교착 상태가 어떤 상황에서 왜 발생하는지, 나아가 교착 상태를 어떻게 해결할 수 있는지를 엿볼 수 있는 가상의 문제 시나리오이다.

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

 

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

 

 

언뜻 보면 위 순서에는 아무런 문제가 없어 보인다. 하지만 모든 철학자가 동시에 포크를 집어 식사를 하면 어떤 철학자도 식사를 할 수 없고 영원히 생각만 하는 상황이 발생할 수 있다. 모든 철학자가 왼쪽 포크를 집어들면 모두가 오른쪽 포크를 들 수 없기 때문이다. 다시 말해 모든 철학자는 다른 철학자가 포크를 내려놓을 때까지 기다린다.

 

식사하는 철학자 문제에서 철학자는 프로세스 혹은 스레드, 포크는 자원, 생각하는 행위는 자원을 기다는 것에 빗대어 볼 수 있다. 그리고 포크는 한 번에 하나의 프로세스 혹은 스레드만 접근 할 수 있으니 임계 구역이라고 볼 수 있다.

 

이는 마치 게임 프로세스는 자원 A를 점유한 채 웹 브라우저 프로세스가 점유하고 있는 자원 B의 사용이 끝나길 기다리고, 웹 브라우저 프로세스는 자원 B를 점유한 채 게임 프로세스의 자원 A사용이 끝나길 기다리는 상황과 같다. 이 경우 게임과 웹 브라우저 프로세스는 상대방이 가진 자원을 기다리기만 하다가 결국 실행 한 번 못하는 상황이 벌어진다. 이를 교착 상태라고 한다.

 

---

 

 

 

자원 할당 그래프

교착 상태는 자원 할당 그래프를 통해 단순하게 표현할 수 있다.

 

 

 

 

같은 자원이라 할지라도 사용 가능한 자원의 개수는 여러 개 있을 수 있다. 

 

 

 

프로세스가 자원 이용을 끝내고 운영체제에 자원을 반납하면 화살표는 삭제된다.

 

 

이 그림은 프로세스 D가 CPU의 할당을 기다리고 있음을 나타낸 그래프이다. 

 

 

아래 그래프는 무엇을 나타내고 있을까?

현자 사용 가능한 SSD 자원은 3개, CPU 자원은 2개, 프린트는 1개가 있다. 프로세스 A는 SSD를 할당받아 사용 중이고, 프로세스 B와 C는 CPU를 할당받아 사용 중이며, 프로세스 D는 프린터를 사용 중이다. 프로세스 E는 프린터 자원을, 프로세스 F는 CPU의 할당을 기다리고 있고 볼 수 있다.

 

 

 

앞서 설명한 식사하는 철한자 문제도 자원 할당 그래프로 표현한 것이다. 식사하는 철학자 문제에서 포크는 자원, 철학자는 프로세스와 같다고 했다. 모든 철학자가 왼쪽 포크를 든 채 오른쪽 포크를 기다리고 있는 상황이니 이와 같이 표현할 수 있다.

 

 

게임 프로세스는 자원 A를 할당받은 채 웹 브라우저 프로세스가 할당받은 자원 B의 사용이 끝나길 기다리고 있고, 웹 브라우저 프로세스는 자원 B를 할당 받은 채 게임 프로세스가 할당받은 자원 A의 사용이 끝나길 기다리는 상황이다.

 

 

---

 

 

 

교착 상태 발생 조건

이러한 교착 상태는 왜 발생했을까? 교착 상태가 발생할 조건에는 네 가지가 있다.

 

 

 

교착 상태가 발생한 근복적인 원인은 해당 자원을 한 번에 하나의 프로세스만 이용 가능했기 때문이다. 만일 식사하는 철학자 문제에서 하나의 포크르 여러 명이 동시에 사용할 수 있었다면 교착 상태는 발생하지 않았을 것이다.

 

식사하는 철학자 문제에서 누구도 식사를 이어갈 수 없었던 이유는 '왼쪽 포크를 들고' 다른 철학자의 포크를 기다렸기 때문이다. 

만일 철학자들 중 누군가 다른 철학자의 포크를 강제로 빼앗을 수 있었다면 교착 상태는 발생하지 않았을 것이다. 하지만 식사하는 철학자 문제에서 철학자들은 모두 점잖게 그저 포크를 기다리기만 했다. 비선점 자원은 그 자월을 이용하는 프로세스의 작업이 끝나야만 비로소 이용할 수 있다.

 

교착 상태가 발생한 마지막 이유는 프로세스들과 프로세스가 요청 및 할당받은 자원이 원의 형태를 이루었기 때문이다. 다시 말해 자원 할당 그래프가 원의 형태로 그려지면 교착 상태가 발생할 수 있다.

---

 

 

 

단원 마무리하기

 

 

식사하는 철학자 문제에서 모든 철학자가 동시에 식사를 하려고 하면 교착 상태가 발생한다.

 

 

 

 

문제를 모두 잘 풀었다.

 

---

 

 

 

학습을 마치고

이로써 어젯밤에 미리 발행했던 모든 포스트에 학습일지를 모두 써서 완료했다. 교착상태가 발생하는 식사하는 철학자 문제는 정말 재미있는 예시였다. 

교착 상태에 관한 한 단원만 학습을 마치면 이제 새벽 공부도 끝이 난다. 조금만 더 힘을 내서 공부를 마무리해보자.