어떻게 서로 양보 안 하면, 교착

잡고, 그리고 기다린다

경쟁 상태 레슨에서 좋은 습관을 하나 익혔다. 무언가를 고치려면 먼저 그것을 잡고, 다 쓸 때까지 다른 사람은 기다리게 하는 것이다. 한 칸짜리 화장실에 줄을 서듯이 말이다. 덕분에 둘이 겹쳐 결과를 망치는 사고가 사라졌어요.
이번에는 일에 자원이 둘 필요하다고 하자. 도구 1번과 도구 2번이라 부르고, 일을 끝내려면 두 도구가 다 있어야 한다. A는 1번을 먼저 잡고 2번을 기다린다. B는 2번을 먼저 잡고 1번을 기다린다. 둘 다 규칙대로 하나씩 잡았을 뿐인데 나머지 하나는 끝내 손에 넣지 못해요.
잡은 것은 놓지 않고, 없는 것은 기다린다. 이 잡고 기다리기가 모든 문제의 시작이다.

두 버튼을 눌러 A와 B가 하나씩 잡게 한다. A는 1번을 잡고 2번을 기다리고, B는 2번을 잡고 1번을 기다린다. 둘 다 잡은 것은 놓지 않고 없는 것만 기다리니 더 나아가지 못해요(빨강).

이상한 일이다. 둘 다 잘못한 것이 없다. 경쟁 상태 레슨에서 안전하다고 배운 방법대로 차례로 하나를 잡았을 뿐이에요. 그런데도 둘 다 멈췄다.
문제는 잡는 것 자체가 아니라, 잡은 채로 서로를 기다리는 모양에 있다. 이 모양을 더 또렷이 보려면 익숙한 장면 하나를 떠올리면 좋아요.

좁은 다리에서 마주 선 두 사람

한 사람만 겨우 지나가는 좁은 다리가 있다. 한쪽 끝에서 한 사람이, 반대쪽 끝에서 또 한 사람이 동시에 다리에 오른다. 둘은 가운데로 걸어가다 딱 마주쳐요.
앞으로 가려면 상대가 비켜 줘야 한다. 그런데 둘 다 자기가 선 칸을 내주지 않아요. 내가 먼저 왔으니까, 내가 더 급하니까. 아무도 물러서지 않으니 둘은 가운데서 영영 멈춰 선다.
다리의 칸 하나하나가 앞의 도구 1번, 2번이고, 두 사람이 A와 B다. 저마다 자기 자리를 잡은 채 상대 자리를 기다리는, 앞에서 본 모양 그대로예요.

두 버튼으로 A와 B를 한 칸씩 가운데로 옮긴다. 다리 한가운데서 마주치면 둘 다 자리를 내주지 않아 더는 못 가고 멈춰요(빨강).

다리에서는 두 사람이 마주 보다 멈췄다. 그런데 막히는 쪽이 꼭 둘일 필요는 없다. 셋, 넷, 그보다 많은 사람이 한 줄이 아니라 둥글게 늘어서서 서로를 기다리면 같은 멈춤이 더 크게 일어나요.
이번에는 사람들을 식탁에 둥글게 앉히고 기다림의 고리가 닫히는 순간을 직접 만든다.

고리가 닫히면 모두 멈춘다

식탁에 다섯 사람이 둥글게 앉아 있고, 사람과 사람 사이마다 젓가락이 한 짝씩 놓여 있다. 먹으려면 양쪽 젓가락이 다 필요한데, 모두가 똑같이 왼쪽 것을 먼저 집고 오른쪽 것을 기다리기로 했다.
한두 명만 그러면 괜찮다. 누군가는 양쪽을 다 잡아 먹고, 다 먹으면 내려놓으니까. 그런데 모두가 동시에 왼쪽을 집으면 모두의 오른쪽 젓가락은 옆 사람 손에 있다. 모두가 옆 사람을 기다리고, 기다림이 한 바퀴를 돌아 자기 자신에게 돌아와요.
이렇게 기다림의 화살표가 동그란 고리를 이루면 고리 위의 누구도 영영 움직이지 못한다. 좁은 다리의 두 사람이 식탁을 둘러싼 여러 명으로 늘어난 셈이에요.

버튼을 누를 때마다 다음 사람이 왼쪽 젓가락을 집는다. 다섯 번째 사람까지 집어 고리가 닫히는 순간, 모두의 오른쪽 젓가락이 옆 사람 손에 있어 전부 멈춰요(빨강).

고리가 닫히는 마지막 한 걸음에서 멀쩡히 돌아가던 식탁이 통째로 얼어붙었다. 무서운 점은 누구 한 명이 특별히 잘못한 게 아니라는 것이다. 모두가 똑같이, 그럴듯하게 왼쪽부터 집었을 뿐인데 전체가 멈췄어요.
그렇다면 얼어붙은 식탁은 어떻게 녹일까? 다행히 방법은 의외로 단순하고, 길은 두 가지다.

푸는 법: 양보하거나, 순서를 정하거나

첫 번째 길은 양보다. 고리 위의 누구 한 명이 잡고 있던 것을 잠깐 내려놓는다. 그러면 그 사람을 기다리던 옆 사람이 두 짝을 다 모아 먹고, 다 먹으면 내려놓는다. 한 곳이 풀리니 다음 사람이 풀리고, 막힘이 도미노처럼 차례로 풀려요. 고리에 끊긴 곳이 하나만 생겨도 더는 동그란 고리가 아니기 때문이다.
두 번째 길은 더 영리하다. 고리가 아예 닫히지 못하게 미리 막는 것이다. 모두에게 '누구든 항상 번호가 작은 것부터 잡는다'는 같은 규칙을 준다. 그러면 1번을 잡지 못한 사람은 2번도 잡지 않고 기다린다. 모두가 같은 순서로 잡으니 두 사람이 엇갈려 마주 보는 일이 생기지 않고, 고리가 만들어질 수 없어요.

먼저 고리를 닫아 모두 멈추게 한 뒤, 한 명에게 양보를 시킨다. 그 사람이 잡은 것을 내려놓으면 고리가 끊기고, 옆 사람부터 차례로 풀려 모두 다시 움직여요(초록).

양보는 이미 멈춘 고리를 푸는 길이고, 순서 정하기는 멈춤이 아예 생기지 않게 하는 길이다. 하나는 사고가 난 뒤의 응급 처치이고, 다른 하나는 사고를 미리 막는 예방인 셈이에요.
둘의 핵심은 같다. 동그란 기다림의 고리가 닫히지 못하게 하는 것이다. 어디 한 군데라도 끊기면 멈춤은 다시 흐름으로 바뀌어요.

한 장으로 정리

네 가지만 기억하면 된다.
첫째, 각자 하나씩 잡은 채 서로 상대 것을 기다리면 잡고 기다리기가 시작된다. 둘째, 좁은 다리의 두 사람처럼 마주 보고 양보하지 않으면 둘 다 멈춘다.
셋째, 그 멈춤이 둥글게 한 바퀴를 돌아 고리가 닫히면 고리 위의 모두가 멈춘다. 이것이 교착 상태예요. 넷째, 누군가 잡은 것을 내려놓고 양보하거나 모두가 같은 순서로 잡도록 정해 두면, 고리가 끊기거나 아예 생기지 않아 다시 흐를 수 있다.

네 단계를 차례로 누르면 잡고 기다리기, 다리 위의 마주 봄, 닫힌 고리, 양보와 순서로 푸는 길까지 교착 상태의 처음과 끝이 한 장에 정리돼요.

경쟁 상태 레슨에서는 한 명씩 차례로 하면 안전하다고 배웠는데, 이번에는 그 차례로 잡기가 도리어 모두를 멈추게 할 수 있다는 것을 보았다. 같은 도구도 어떻게 쓰느냐에 달린 셈이다.
안전한 줄서기와 영영 멈추는 교착 상태는 종이 한 장 차이예요. 잡는 순서를 모두 같게 맞추느냐, 누군가 양보할 줄 아느냐가 그 한 장을 가른다.
이제 운영체제 영역에는 마지막 레슨 하나가 남았다. 전원 버튼을 누른 순간부터 화면이 뜨기까지, 컴퓨터가 어떻게 스스로 깨어나는지를 다뤄요.