알고리즘과 자료구조에 대한 열정을 이야기하면 사람들은 어리둥절한 표정을 짓는다. 대부분 ‘프로그래머가 하는 일’이 무엇인지는 알지만, 컴퓨터 과학이 어디에 쓰이는지는 잘 모른다. 안다고 해도 실생활과는 별 관련이 없다고 생각한다. 아주 간단한 예를 통해 응용 컴퓨터 과학이 사실 우리 주변 어디에나 있다는 걸 보여주겠다.

정리해야 할 양말 더미를 상상해보자. 그리 신나는 일은 아니다. 너무 오래 미뤄둔 탓에 정리하는 데 족히 한 시간은 걸릴 것이다.

고민 끝에 도움을 받기로 한다. 친구와 함께 작업에 나선다. 시간은 대략 절반으로 줄어든다.

컴퓨터 과학자라면 이 양말 더미를 자원이라고 부를 것이다. 당신과 친구는 가차 없이 워커로 격하된다. 두 사람이 동시에 하나의 문제를 다룬다 — 즉 병렬로 작업하는 것이다. 이것이 병렬 컴퓨팅의 핵심이다.

양말 정리를 병렬로 하기에 특히 적합하게 만드는 몇 가지 특성이 있다.

• 작업을 깔끔하게 나눌 수 있다. 짝을 찾는 데 걸리는 시간은 워커마다 거의 비슷하다.
• 다른 짝을 찾는 일은 완전히 독립된 작업이라 동시에 진행할 수 있다.

이 작업에 워커를 많이 투입할수록 더 빨리 끝난다.

• 워커 1명이면 60분이 걸린다.
• 워커 2명이면 30분이 걸린다.

그럼 워커가 3명이면 얼마나 걸릴까? 맞다! 약 20분이다. 이 관계를 간단한 수식으로 나타낼 수 있다:

사실 이건 그리 정확한 얘기가 아니다. 오버헤드를 빼먹었기 때문이다. 메리가 양말 하나를 집으려는 순간 스티븐도 같은 양말에 손을 뻗을 수 있다. 두 사람은 서로 웃으며 한 명이 다른 양말을 집는다. 컴퓨팅에서도 워커가 비슷하게 행동한다. 물론 웃지는 않고 다른 작업을 집을 뿐이지만. 많은 워커가 자원을 공유하면 이런 상황은 꽤 자주 발생한다. 그리고 상황을 해결하는 데는 항상 약간의 추가 시간이 든다. 그래서 최적의 정리 속도에서는 조금 벗어나게 된다.

하지만 상황은 더 나빠질 수도 있다! 양말 100개를 워커 100명이 정리한다고 해보자. 처음에 모든 워커가 양말을 하나씩 집어 들고 짝을 찾으려 할 것이다. 문제는 이렇다. 각자 양말을 하나씩 집는 순간 더 이상 남은 양말이 없어진다. 모든 워커가 대기 상태에 빠진다. 정리는 영원히 끝나지 않는다. 이것이 바로 데드락이며, 병렬 컴퓨팅에서 가장 두려운 시나리오 중 하나다.

이 경우 간단한 해결책은 양말을 다시 내려놓고 잠시 기다렸다가 새 양말을 집으려 시도하는 것이다. 또 다른 해결책은 정리를 위한 일종의 ‘프로토콜’을 강제하는 것이다. 프로토콜을 공동의 목표를 달성하기 위한 워커 간의 암묵적인 합의라고 생각하면 된다.

예를 들어 각 워커가 한 가지 색깔의 양말만 맡도록 하는 것이다. 워커 1은 초록색 양말을, 워커 2는 회색 양말을 맡는 식이다. 이 간단한 방법으로 데드락을 피할 수 있는데, 완전히 분리된 작업을 처리하기 때문이다.

하지만 여전히 함정이 있다. 만약 초록색 양말은 4개뿐이고 회색 양말은 4000개라면 어떻게 될까? 워커 1은 금방 할 일이 없어질 것이다. 양말 두 켤레를 순식간에 정리하고는 워커 2가 나머지를 정리하는 걸 구경만 하게 된다. 그게 과연 팀워크라고 할 수 있을까?

이런 식으로 작업을 나누는 게 가장 합리적인 경우는 색깔별로 양말 수가 비슷하다고 가정할 수 있을 때다. 그래야 모두가 비슷한 수준의 작업량을 맡게 된다.

다음 히스토그램을 보면 무슨 말인지 감이 올 것이다:

이 경우 색깔별로 더미 크기가 거의 비슷하다. 모든 워커에게 공평한 작업량이 주어진 셈이다.

두 번째 경우에는 분포가 고르지 않다. 이 예시에서 회색 양말 더미를 정리하고 싶은 사람은 없을 것이다. 조금 더 고민이 필요하다.

어떻게 하면 좋을까?

대부분의 경우 작업을 나누는 다른 방법을 고민하는 게 도움이 된다. 예를 들어 커다란 회색 더미를 워커 두 명이 함께 정리하도록 할 수 있다. 한 명은 큰 양말을, 다른 한 명은 작은 양말을 맡는 것이다. 하지만 여기서 또 다른 문제가 생긴다. 누가 ‘큼’과 ‘작음’의 기준을 정하느냐는 것이다.

그래서 더 영리한 방법을 깊게 고민하기보다는, 여기서는 실용적인 길을 택하기로 한다. 모두가 색깔이나 크기에 상관없이 그냥 비슷한 크기의 더미를 하나씩 집어 들고 작업을 시작하는 것이다.

대부분 각 더미에는 짝을 찾지 못한 양말이 조금 남게 될 것이다. 괜찮다. 그냥 그 양말들을 한데 모아 섞은 뒤 새로운 더미를 만들어 다시 정리하면 된다. 끝날 때까지 이 과정을 반복한다. 이를 작업 큐라고 부른다. 이 방식에는 두 가지 장점이 있다. 첫째, 워커 간의 추가적인 합의가 필요 없고, 둘째, 문제 영역에 대해 깊게 고민하지 않아도 워커 수에 따라 꽤 잘 확장된다.

분산 시스템의 까다로운 점은 얼핏 간단해 보이는 해결책이 실제로는 처참하게 실패할 수 있다는 데 있다.

만약 작은 더미들이 이렇게 생겼다면 어떨까?

각 더미에서 찾을 수 있는 짝의 수는… 기대에 한참 못 미친다. 우리가 할 수 있는 일은 아주 빠른 사전 정렬 단계를 거쳐 짝이 맞을 확률을 높이는 것이다. 혹은 당신이 더 좋은 아이디어를 떠올릴 수도 있다.
멋진 점은, 더 빠른 방법을 한 번 찾아내면 비슷한 유형의 다른 작업에도 적용할 수 있다는 것이다.

이런 문제들은 컴퓨터 과학에 뿌리를 두고 있으며, 어디에서나 찾아볼 수 있다. 개인적으로 나는 ‘Computer Science’라는 용어를 그다지 좋아하지 않는다. 나는 독일어인 ‘Informatik’이라는 말을 더 선호하는데, 대략 ‘정보과학’으로 옮길 수 있다. 우리가 여기서 하는 일의 진정한 본질은 문제 유형 전체를 해결하는 일반적인 방법을 찾는 것이기 때문이다. 우리는 객체의 본질과 그 속성에 대해 고민한다. 우리가 하는 일은 양말을 정리하는 것이 아니라 정보의 근본적인 질문에 답하려는 것이다. 이제 내가 왜 이 주제에 그토록 열정적인지 이해할 수 있을 것이다.

아, 그리고 왜 내가 프로그래밍을 사랑하는지에 대한 관련 글도 있다.