토니 호어

모니터

여기서 말하는 모니터는 컴퓨터 화면을 지칭하는 것이 아니다. 프로세스(혹은 쓰레드)의 동기화^{synchronization}를 위해 사용되는 기법을 가리킨다. 모니터^monitor는 1972년에 벨파스트에서 열린 학술대회 중에 토니 호어와 브린치 핸슨^{Per Brinch Hansen} 두 사람의 아이디어에서 시작되었다.

나는 동시성 – 병렬 프로그래밍 – 에 사용되는 아이디어들을 관심 있게 알아보고 있었습니다. 나는 ‘공리’의 관점에서 그것들을 알아보는 데 흥미가 있었지요. 일반적인 순차적 프로그램을 작성할 때와 같은 방식으로 병렬 프로그램을 안전하게 작성하게 하려면 어떤 공리를 만들어야 할지 궁금했습니다. 학술대회 중에 이 주제가 떠올랐고 우리는 오후 전체 시간을 이 문제에 할애하면서 ‘모니터’라는 아이디어를 만들어냈습니다. 나와 핸슨이 토론의 주요 기여자였습니다.^​4​

컴퓨터 시스템에서 말하는 동기화란, 실행 중인 능동적인 작업들 사이의 순서를 정하는 것을 의미한다. ‘능동적인 작업’이란 결국 실행되고 있는 프로그램을 의미하는데, 한 프로그램이 종료한 후에 다른 프로그램이 실행되는 형태의 일괄작업^batch 시스템에서는 원칙적으로 동기화가 발생할 수가 없다. 하지만 여러 대의 컴퓨터가 자원을 공유한다면 컴퓨터 사이의 동기화가 필요할 것이다.

한 대의 컴퓨터 내에서 동기화 문제가 발생하는 경우는, 어떤 프로그램이 종료되지 않은 상태에서 다른 프로그램이 실행될 수 있는 상황이 존재할 때이다. 다중 처리^{multiprocessing} 시스템이나 다중 쓰레드^multi-thread 시스템에서는 발생할 수 있다.

동기화에 관한 가장 유명한 사례는 ‘식사하는 철학자들’ 문제이다.^​10​ 원래 다익스트라가 1965년에 학부생 시험 문제로 냈던 것에서 출발했는데 후에 토니 호어가 지금 알려진 형태로 정리했다. 다익스트라가 당시에 고민했던 것은 여러 대의 컴퓨터가 테이프 드라이브 장치를 어떻게 공유할지였다. 왜냐하면 어떤 컴퓨터가 테이프에 데이터를 쓰고 있는 중간에 다른 컴퓨터가 끼어들어서 다른 데이터를 써버리면 곤란하기 때문이다. 이 문제는 공용 자원에 대한 복수 개의 동시 접근을 어떻게 순서화하느냐로 해석할 수 있다. 이를 해결하기 위해 다익스트라는 세마포어^semaphore라는 개념을 제시했다. 이것은 공용 자원에 대한 접근 권한을 결정하는 특수한 변수이다. 이 변수를 통해서 한 번에 한 개의 컴퓨터만 테이프 드라이브에 접근할 수 있으며, 이 컴퓨터가 사용을 마칠 때까지는 다른 컴퓨터가 테이프 드라이브에 접근할 수 없다.

그런데 세마포어는 자원에 대한 접근 여부만 통제할 뿐, 일단 접근 권한을 얻은 후에 그 자원에 대해 무슨 작업을 할지는 관여하지 않는다. 위의 예에서 테이프 드라이브에 대한 접근 권한을 얻은 프로그램은, 테이프에 쓰기 작업을 할 수도 있고 읽기 작업을 할 수도 있다. 무슨 작업을 할지는 각 프로그램에 구현된 코드에 의해 결정된다.

모니터^monitor는 공유 자원에 대한 배타적 접근권만 통제하는 것이 아니라 그 공유 자원에서 벌어지는 작업까지도 통제하는 방식이다. 위의 예를 들자면, 테이프 드라이브의 읽기 동작에 대한 배타적 실행권을 통제하는 식이다. 따라서 프로그램에서는 테이프 드라이브 자체가 아닌, 테이프 드라이브 읽기 동작에 대해 실행 권한을 요청해야 하며 한 번에 한 개의 프로그램(혹은 프로세서, 혹은 쓰레드)만 그 읽기 동작을 실행할 수 있다.

모니터 개념이 처음 적용된 언어는 핸슨이 개발한 컨커런트 파스칼^{Concurrent Pascal}이다.^​11​ 모니터는 형태적으로 보면 클래스와 유사하다. 모니터를 사용하여 디스크 버퍼를 구현한 예가 다음과 같다.^​**​

type diskbuffer = monitor

    var head, tail, length: interger;

    procedure entry send(block: string);
      begin
       // doing someting here 
      end;

    procedure entry receive(block: string);
      begin
       // doing something here
      end;

위의 예를 보면 diskbuffer는 모니터 타입으로 선언되었고 그 안에는 head, tail, length 같은 공유변수와 send(), receive()라는 멤버 함수가 있다.

만약 어떤 프로그램(혹은 프로세스, 혹은 스레드)이 diskbuffer에 뭔가를 쓰고 싶다면 다음과 같이 할 수 있다.

var buffer: diskbuffer;

buffer.send("test string");

프로그래머는 diskbuffer가 모니터임을 이미 알고 있다. 그래서 buffer.send를 호출하게 되면 안전하게 “test string“이 buffer에 쓰여지리라는 것을 확신한다. diskbuffer를 접근하는 send(), receive()가 동시다발적으로 발생했을 때 이들이 뒤섞이지 않고 차례로 수행되도록 보장하는 것은 컨커런트 파스칼^{Concurrent Pascal} 컴파일러가 해야 할 일이다. 내부적으로 어떻게 구현되어 있는지를 응용 프로그래머는 신경쓸 필요가 없다.

그렇다면 모니터의 내부는 어떻게 구현되어 있을까? 두 가지 중요한 구성 요소가 있다. 하나는 자원에 대한 독점적 접근을 보장하기 위한 mutex이고 다른 하나는 특정 동작의 수행 가능 여부를 알려주는 조건 변수^{condition variable}이다. 위의 diskbuffer 예를 보면, diskbuffer라는 자원(혹은 객체)을 단 하나의 프로그램(프로세스/쓰레드)만이 접근할 수 있도록 보장해야 한다. 이를 위해 mutex라는 잠금 변수를 사용한다. 어떤 프로그램(프로세스/쓰레드)이 diskbuffer에 대한 독점적 접근을 확보했다고 하자. 그런데 send()라는 함수가 수행될 수 있다는 보장은 없다. 왜냐하면 모니터 내부에서 데이터를 저장하는 공간이 꽉 차 있어서 더 이상 저장할 수 없을 수도 있기 때문이다. 따라서 이를 알려주는 조건 변수라는 별도의 구조가 필요하다. 만약 저장공간이 꽉 차 있다면 send()를 호출한 프로그램은 diskbuffer에 대한 mutex 잠금변수를 포기하고 대기상태에 들어간다. 그러다가 다른 프로그램이 receive()를 호출해서 저장공간에 있는 값을 읽어가고 그로 인해 저장공간에 여유가 생기면 모니터는 해당 조건 변수에 대기 중인 프로그램들을 모두 깨운다. 그러면 깨어난 프로그램들이 다시 동작을 시도한다.

CSP

CSP(Commuinicating Sequential Processes)^​12​는 하드웨어의 발전에 자극받아 제안된 개념이다.

그 이유는 하드웨어의 기술적 발전, 다름 아닌 마이크로프로세서의 등장 때문이었습니다. 당시에 마이크로프로세서는 작고 값이 쌌습니다… 내 생각에 크고 빠른 컴퓨터를 저렴하게 만드는 방법은 아주 값이 싼 마이크로프로세서들을 많이 묶는 것이었습니다. 그리고 마이크로프로세서들끼리는 전선으로 연결해서 서로 협력하여 작업을 처리하도록 하자는 것이었죠. 그것을 위해서는 새로운 방법, 그러니까 프로그램을 위한 새로운 패러다임, 새로운 구조가 있어야 했습니다… 그래서 Communication sequential processes가 내 연구에서 주요한 역할을 하게 되었습니다.^​4​

프로그래머의 입장에서 모니터와 CSP의 차이점을 든다면, 모니터는 공유 자원을 사용하기 위한 서브루틴을 호출하는 식이지만, CSP는 입력과 출력을 위한 별개의 명령어를 사용해서 프로세서(혹은 프로그램) 사이에 통신하는 방식이라는 점이다.

CSP에서는 프로세서(혹은 프로그램/프로세스/쓰레드) 사이에 데이터를 주고받기 위해 명시적으로 입력과 출력을 표현한다. 입력을 위해서는 ? 기호를 사용하고 출력을 위해서는 ! 기호를 사용한다. 아래에 간단한 예가 있다.

X?(x, y) // X라는 이름의 프로세스에서 두 개의 입력값을 받아서 차례로 x와 y에 저장한다.
DIV!(3, a) // DIV라는 프로세스에게 3과 변수 a값을 차례로 전달한다.

위의 예에서 만약 X라는 프로세스가 아직 전달할 값을 준비하지 못했다면 기다려야 한다. 또한 DIV라는 프로세스가 새로운 값을 받을 준비가 되지 않았다면 역시 기다려야 한다.

모니터에서 사용했던 diskbuffer의 예를 CSP에 적용한다면 이제 diskbuffer는 객체가 아니라 별개의 프로세스로 구현되어야 한다. 그리고 send()라는 함수를 호출하는 것은 diskbuffer!"test string" 과 같은 명령어로 바뀔 것이다.

CSP에서 가장 독특한 명령어는 Alternative 명령어와 Repetitive 명령어이다. Alternative 명령어는 일종의 조건문으로서 ⫿ 기호가 사용된다. Repetitive 명령어는 일종의 반복문으로서 * 기호가 사용된다. 그 예는 다음과 같다.

[x ≥ y -> m := x ⫿ y ≥ x -> m := y] // 만약 x가 y보다 크거나 같다면 x를 m에 대입하고 y가 x보다 크거나 같다면 y를 m에 대입한다. 둘 다 만족된다면 둘 중 아무거나 하나를 진행한다.

*[(c: character; west?c) -> east!c ] // west라는 프로세스에서 문자를 받아서 east라는 프로세스에 전달한다.

CSP는 전선으로 연결된 다중 프로세서 시스템을 염두에 두고 만들어졌으나, 실제로는 다중 프로세스 시스템에도 적용이 가능하므로 매우 강력하다고 할 수 있다. 실제로 CSP는 세마포어나 모니터를 모두 대체할 수 있다.

CSP는 단순히 연구 차원에서 끝나지 않고 산업계와의 협업으로 이어졌다. 당시에 영국의 스타트업 기업 INMOS가 Transputer라는 마이크로프로세서를 개발하면서 토니의 연구팀과 협업하여 OCCAM이라는 프로그래밍 언어를 개발했다. 이 프로세서는 메모리를 내장하고 있었고 다른 프로세서와의 통신을 위한 직렬 링크를 제공했다.

자료 구조

컴퓨터가 다루는 데이터는 여러 유형으로 나뉜다. 정수, 실수, 불^bool, 문자와 같은 기본 유형과 행렬, 리스트, 그래프 등의 복잡 유형 등이 있다. 이런 유형들은 컴퓨터와 상관없이 종이 위에서 추상적으로 다룰 수 있다. 하지만 이것들을 컴퓨터 내에서 구현하게 되면 중요한 문제에 부딪히게 된다. 1차원의 구조를 가진 메모리에서 이 데이터를 어떻게 배치하고 사용할 것인가이다. 예를 들어 아래와 같은 2차원 행렬을 생각해보자.

1  2  3 
4  5  6 
7  8  9

종이 위에서는 위의 형태 그대로 사용할 수 있지만 컴퓨터에서 이를 메모리에 저장해야만 사용할 수 있다. 그런데 메모리는 1차원적인 주소를 가졌으므로 2차원 정보를 바로 저장할 수가 없다. 그래서 행 단위로 쪼개어 저장하는 식으로 변형을 가해야 한다. 그러면 다음과 같이 메모리에 저장된다.

메모리번지  데이터
   A      1
  A+1     2
  A+2     3
  A+3     4
  A+4     5
  A+5     6
  A+6     7
  A+7     8
  A+8     9

이렇듯 컴퓨터가 다루는 각종 데이터들은 메모리에 저장하기 위해 변형되어야 하는데 어떤 방식으로 할 것인가에 대한 고민이 ‘자료 구조^{data structuring}‘이다.

토니는 1972년에 다익스트라, 달^{O.-J. Dahl} 등과 함께 <구조적 프로그래밍>^​13​이라는 책을 발표하면서 자료 구조를 체계적으로 정리했다.^​††​

1 2 3 4 5 6