프로세스 동기화

컴퓨터에서 사용되는 동기화Synchronization가 의미하는 바는, 그 단어의 사전적인 의미와 잘 연결되지 않는다. 그렇다고 아주 동떨어진다는 이야기는 아니다. 하지만 실제 그것이 표현하고자 하는 내용을 알게 되면 그게 왜 ‘동기화’라고 불려야 하는지 선뜻 받아들여지지 않는다. 사실 컴퓨터에는 그런 용어들이 꽤 있다. 변수variable, 프로세스process라는 단어들이 컴퓨터 분야에서 표현하는 내용은, 그 단어만 들어서는 제대로 가늠하기 어렵다. ‘동기화’를 이해하려면 그 반댓말인 ‘비동기적asynchronous‘이라는 단어를 생각하는 편이 나을지도 모르겠다. 무엇인가가 ‘비동기적’이라고 말할 때는 그 대상이, 다른 어떤 것과도 순서적 연관관계를 가지지 않음을 의미한다. 예를 들어 내가 점심을 아무 때나 먹는다면 그것은 비동기적이다. 그런데 만약 12시가 지났을 때만 먹는다면 그때는 시간과 동기화되었다고 말할 수 있을 것이다.

따라서 컴퓨터에서 사용되는 ‘동기화’란, ‘뭔가가 어떤 다른 뭔가와 순서적 연관 관계없이 자유롭게 수행되지 못하는 상황’을 의미한다고 해석해도 좋지 않을까 싶다.

컴퓨터의 구조를 아는 이라면, 현대식 컴퓨터(폰 노이만식 컴퓨터)는 순차적으로 명령어를 수행하는 기계임을 알고 있을 것이다. 엄밀히 말해서 컴퓨터는 한 번에 하나의 일만 할 수 있으며, 메모리에 올라와 있는 명령어 덩어리(프로그램)에서 명령어를 순서대로 처리할 뿐이다. 그래서 동시에 여러 가지 일이 벌어질 수가 없다. 우리는 이런 방식을 일괄처리batch 방식이라고 불렀다.

그런데 두 가지 방향에서 예외가 발생하기 시작했다. 먼저, 여러 대의 컴퓨터를 운영하는 경우이다. 각 컴퓨터가 독자적인 입출력 장치를 가졌다면 서로 아무런 관련이 없겠으나, 뭔가를 공유하기 시작하면 이야기가 달라진다. 가령 컴퓨터는 여러 대인데 프린터는 한 대만 있는 경우에 여러 컴퓨터가 이 프린터에 접근하려고 하면 이때부터 순서를 따지기 시작해야 한다. 컴퓨터가 아무런 제약 없이 프린터에 출력하도록 내버려 둔다면 최악의 경우, 우리는 각 컴퓨터가 쏟아낸 출력이 뒤죽박죽 섞여 있는 종이를 쳐다봐야 할 것이다.

두 번째 예외는 시분할 시스템이었다. 하나의 컴퓨터에서 여러 개의 프로그램이 동시다발적으로 수행될 수 있게 된 것이다. 물론 세밀하게 파고들면 컴퓨터의 프로세서는 한순간에 하나의 일만 하지만, 인터럽트를 통해서 프로세서의 동작을 중간에 끊어버리고 다른 프로그램을 수행하도록 바꿔버리는 일이 가능해졌다. 다중 처리multiprocessing의 시대가 열리면서 한 대의 컴퓨터 내에서도 메모리, 디스크 등의 자원을 여러 프로세스​**​가 서로 접근하는 상황이 가능해졌고 따라서 순서를 따지는 일이 필요해졌다.

임계 구역

앞에 들었던 예에서 프린터, 디스크는 서로 다른 컴퓨터 혹은 프로세스가 접근하려는 공유 자원이었다. 이런 공유 자원을 다루는 프로그램 코드를 임계 구역critical section이라고 부른다. 임계 구역에 해당하는 코드는 항상 하나의 컴퓨터 혹은 프로세스만이 점유할 수 있다. 즉, 그 구역의 코드를 어떤 프로세스가 수행하고 있는 동안에 다른 프로세스가 그 구역의 코드를 수행해서는 안 된다. 그렇게 했다가는 프린터에 출력되는 내용이 뒤죽박죽될 수 있기 때문이다.

그렇다면 임계 구역에 해당하는 코드를 수행하고 싶은 컴퓨터/프로세스는 이 임계 구역을 다른 컴퓨터/프로세스가 이미 수행하고 있는지 확인하여야 한다. 그리고 자신이 해당 코드를 수행하게 되면 그 사실을 표시해서 다른 컴퓨터/프로세스가 접근하지 못하도록 막아야 한다. ‘컴퓨터/프로세스가 어떤 다른 컴퓨터/프로세스와 순서적 연관 관계없이 자유롭게 수행되지 못하는 상황’이므로 ‘동기화’의 문제이다.

임계 구역을 누군가 수행하고 있음을 알려주는 표시는, 결국 컴퓨터의 메모리에 올라와 있는 변수이다. 변수값이 0이면 아무도 수행하고 있지 않고, 1이면 누군가 수행하고 있다는 의미로 해석하면 된다. 그런데 여기서 어처구니없는 상황이 생긴다. 이 변수를 복수 개의 컴퓨터/프로세스가 접근하게 되므로, 결국 이것도 공유 자원이 되며 이 변수를 다루는 코드도 임계 구역이 된다. 그렇다면 이 새로운 임계 구역을 위해 또 변수가 필요하고, 그 변수는 다시 공유 자원이므로 또 임계 구역이 필요하게 되어, 결국은 답이 없게 된다.

1959년에 다익스트라가 수학 센터에서 동료들에게 냈던 문제가 바로 이것이었다. 프로세스가 두 개 있다고 했을 때 임계구역을 완벽하게 구현할 방법을 찾는 것이었다. 여러 동료들이 각자 방법을 궁리해냈지만 그때마다 다익스트라는 허점을 짚어냈는데 결국 데커Dekker가 완벽한 방법을 찾아냈다.​11​

데커의 방법은 특별한 하드웨어 지원 없이도 임계 구역을 구현했다는 점에서 장점이 있었다. 하지만 두 개의 프로세스만 지원한다는 단점이 있다.

세마포어

1962년에 다익스트라는 세마포어Semaphore라는 개념을 제안했다. P, V라고 불리는 두 개의 명령문을 사용해서 공유 자원에 대한 접근을 제어했다. P와 V는 세마포어용 변수에 대해 동작한다. P 명령문은 변수의 값을 1만큼 감소시키며, 변수의 값이 0보다 작아지면 변수의 값이 0이 될 때까지 기다린다. V 명령문은 변수의 값을 1만큼 증가시키며 변수의 값이 0 이하이면 이 세마포어 변수의 값이 0이 되기를 기다리고 있는 프로세스 중 하나를 활성화시킨다. 세마포어 방식에서는 세마포어 변수의 값이 단순히 0, 1만 가능한 것이 아니라 -1, -2 등이 가능하므로 세 개 이상의 프로세스도 참여할 수 있다. 또한 공유 자원의 개수가 여러 개인 경우는 세마포어 변수의 값을 2 혹은 3과 같이 높은 값으로 설정함으로써 지원할 수 있다. 하지만 한 가지 중요한 단점이 있다. 데커의 방법은 일반 명령어로 구현할 수 있지만, 세마포어 방식에서는 세마포어 변수의 값을 변경하는 동작이 중간에 끊어져서는 안 된다. 예를 들어 세마포어 변수의 값이 1일 때, 두 개의 프로세스가 동시에 P 명령문을 실행했다고 가정해보자. 먼저 세마포어 변수에 접근한 프로세스가 값을 읽어서 1만큼 줄인 후에 메모리에 다시 저장하려고 할 때, 두 번째 프로세스가 중간에 끊고 들어와서 세마포어 변수에 접근해서 읽어간다면 아직 0으로 바뀌기 전의 1이라는 값을 가져가게 되므로 두 프로세스는 모두 임계구역에 접근하게 될 것이다. 이렇게 메모리의 특정 번지에 있는 값을 읽은 후 수정하고 다시 저장하는 과정이 ‘끊어지지 않고 처리되도록atomic operation‘하기 위해 프로세서는 특수한 명령어를 제공해야 한다.

식사하는 철학자들

‘식사하는 철학자들’은 다중 처리multiprocessing 시스템의 동기화와 관련된 유명한 문제이다. 원래는 여러 대의 컴퓨터가 테이프 드라이브 장치를 어떻게 공유할지에 관하여 다익스트라가 1965년에 학부생 시험 문제로 냈던 것에서 기원했다고 한다. 후에 토니 호어가 이를 변형해서 지금의 형태가 되었다. 호어가 묘사한 식사하는 철학자들 문제는 다음과 같다.

아주 아주 오랜 옛날에 부유한 자선사업가가 다섯 명의 뛰어난 철학자를 모시기 위해 대학에 기부를 했다. 철학자 한 사람마다 그가 사색을 할 수 있는 방이 주어졌고 함께 쓰는 식사 공간이 만들어졌다. 여기에는 원형 식탁이 하나 놓였고 다섯 개의 의자와 함께, 철학자가 앉을 자리마다 이름표가 놓였다… 철학자의 자리에 앉으면 접시 왼쪽에는 순금 포크가 하나 놓여 있었고 식탁 중앙에는 항상 스파게티로 채워져 있는 커다란 그릇이 있었다.
철학자는 대부분의 시간을 사색하며 지냈다. 하지만 배가 출출해지면 식사 공간으로 나와서 자신의 자리에 앉아 왼쪽에 놓여 있는 포크를 들고 스파게티를 먹었다. 그런데 스파게티가 워낙 다루기에 까다로운지라 포크를 하나 더 써야 했다. 그래서 철학자는 접시 오른쪽에 놓여 있는 포크도 사용해야만 했다. 식사를 마치면 철학자는 포크 두 개를 제자리에 내려놓고 의자에서 일어나 자신의 방으로 돌아가 사색에 잠겼다. 당연히 포크는 한 번에 한 사람만 사용할 수 있다. 만약 자신의 양쪽에 놓여 있어야 할 포크를 누군가 쓰고 있다면 사용이 끝날 때까지 기다려야 한다.​12​​††​

By Benjamin D. Esham / Wikimedia Commons, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=56559

언뜻 보면 그저 지루한 철학자의 일상을 보는 듯하다. 그런데 이 이야기에는 심각한 문제가 도사리고 있다. 잘못하면 굶어 죽는 철학자가 생길 수 있다는 것이다. 일단 설명을 위해 다섯 명의 철학자에게 다음과 같이 번호를 붙여보자. 1번 철학자, 2번 철학자, 3번 철학자, 4번 철학자, 5번 철학자. 그리고 모두 이 순서대로 식탁에 앉는다고 가정한다. 철학자가 굶어 죽을 가능성은 두 가지가 있다. 예를 들어 3번 철학자가 스파게티를 먹으려고 앉았는데 왼쪽에 앉은 2번 철학자가 스파게티를 먹고 있었다고 하자. 그렇다면 3번 철학자는 자신의 왼쪽에 놓인 포크를 쓸 수 없기 때문에 기다려야 한다. 기다리는 사이에 4번 철학자가 오른편에 앉아서 스파게티를 먹기 시작했다. 이제 3번 철학자는 오른쪽에 놓인 포크도 쓸 수 없게 되었다. 그 사이에 2번 철학자가 식사를 마치고 방으로 돌아갔지만 여전히 4번 철학자는 식사를 마치지 않았다. 3번 철학자는 기다리는 수밖에 없다. 그런데 식사가 부족했는지 2번 철학자가 다시 나타났다. 그리고는 다시 식사를 시작했다. 이제 3번 철학자는 양쪽 포크를 다시 모두 잃었다. 4번 철학자가 식사를 끝내고 방으로 돌아갔다. 하지만 여전히 2번 철학자는 식사 중이다. 3번 철학자는 어쩔 방법이 없다. 기다리는 수밖에. 그런데 이게 웬일인가. 2번 철학자가 아직 식사를 끝내지 않았는데 4번 철학자가 다시 의자에 앉더니 스파게티를 먹기 시작했다. 이렇게 2번 철학자와 4번 철학자가 계속 번갈아 가며 나타나서 스파게티를 먹다 보니 3번 철학자는 배가 고파 정신을 잃고 말았다.

위의 시나리오는 극단적이기는 하지만, 완전히 배제할 수 없는 상황이다. (뭐, 세상일을 어떻게 알겠는가?) 그런데 더 극단적인 상황도 있다. 모든 철학자가 굶어 죽을 수도 있다. 하필이면 다섯 명의 철학자가 동시에 배가 고파졌다. 그래서 모두 동시에 방에서 나와 동시에 의자에 앉아서 동시에 왼쪽 포크를 집어 들었다. 아뿔싸! 이제 오른쪽 포크를 집어 들어야 하지만 식탁 위에는 남아 있는 포크가 없다. 누군가 그냥 집었던 포크를 내려놓고 일어나면 좋으련만 철학자들은 너무도 융통성이 없었다. 일단 포크를 들었으면 한술 뜨기 전에는 내려놓는 일이 절대 없었다. 결국 다섯 철학자는 모두 배가 고파 정신을 잃고 말았다.

위의 두 가지 사례는 동기화에서 발생할 수 있는 문제는 기아상태starvation과 교착상태deadlock을 각각 보여준다. 동기화는 시분할 시스템을 포함하여 현대의 분산 병렬 처리 시스템에서 매우 중요한 요소였고 다익스트라는 분산 병렬 처리의 선구자로 인정받고 있다.

1 2 3 4 5 6