THE 다중프로그래밍 시스템의 구조

운영체제 설계의 고전. 'THE'는 아인트호벤 공과대학(Technische Hogeschool Eindhoven)의 약자다. 다익스트라가 이끈 6명의 작은 팀 — 대부분 반일 근무 — 이 만든 이 시스템은, 우리가 오늘날 모든 OS에서 보는 계층 구조를 처음으로 체계화했다.

이 논문의 정신은 "두려움"이다. 다익스트라는 솔직히 고백한다. 1958년부터의 경험에서 그는, 실시간 인터럽트의 비재현성 때문에 프로그램 오류가 기계 오작동처럼 위장될 수 있음을 알고 있었다 — 그래서 "디버깅 가능성에 대한 두려움"을 가지고, 가능한 한 조심하기로 결정했다. 그 결정의 표어가 "예방이 치료보다 낫다(prevention is better than cure)"이다. "먼저 코딩하고 나중에 디버깅한다"는 당시의 관행과 정반대였다.

이 두려움에서 영감을 받은 결정이 시스템 설계의 핵심 기여를 낳았다. 다익스트라의 팀은 다중프로그래밍 시스템을 — 그 논리적 건전성이 선험적으로(a priori) 증명될 수 있고, 그 구현이 철저한 테스트를 허용하는 방식으로 — 설계할 수 있음을 발견했다. 테스트에서 나타난 유일한 오류는 사소한 코딩 실수(500 명령어당 하나)였고, 각각 10분 안에 위치를 찾아 수정되었다.

그 비결은 두 가지다. 첫째, 순차 프로세스의 사회 — 전체 시스템을 정의되지 않은 속도 비율로 진행하는 순차 프로세스들의 집합으로 배열하고, 그들의 협력을 명시적 동기화로 규제한다. 이렇게 하면 조화로운 협력이 이산적 추론으로 확립될 수 있고, 시스템은 실제 프로세서의 수와 독립적이 된다. 둘째 — 그리고 가장 혁신적으로 — 엄격한 계층 구조다.

레벨 0은 프로세서 할당과 실시간 클럭을, 레벨 1은 세그먼트 컨트롤러(저장 공간)를, 레벨 2는 메시지 인터프리터(콘솔)를, 레벨 3은 입출력 버퍼링을, 레벨 4는 사용자 프로그램을 다룬다. 각 레벨에서 "추상화"가 일어난다 — 레벨 0 위에서 프로세서의 수는 무관해지고, 레벨 1 위에서 물리적 페이지는 사라지며, 레벨 3 위에서 실제 주변장치는 사라진다. 그리고 이 계층 구조는 검증에서 행복한 결과를 낳았다. 각 레벨을 그 아래 레벨이 철저히 테스트된 후에야 추가했기에, "관련 상태"의 수가 폭발하지 않고 철저한 테스트가 현실이 되었다. 다익스트라는 단언한다 — 10배 더 큰 작업일수록, 구조화가 더 본질적이다.

매우 제한된 자원(평균적으로 반일 근무가 가능한 6명 정도의 그룹)을 가지고 시스템 설계의 기술에 기여하고자 했기에, 우리는 세 가지 지침 원칙을 채택했다. (1) 정당화할 수 있는 한 가장 야심찬 프로젝트를 선택하되 일상적인 작업은 최소한으로 유지한다. (2) 건전한 기본 특성을 가진 기계를 선택한다. (3) 경험이 결코 자동적으로 지혜로 이어지지 않는다는 사실을 인식하고, 귀중한 경험으로부터 가능한 한 많이 배우려는 의식적인 노력을 기울인다.

이 시스템은 네덜란드 기계인 EL X8을 위해 설계되었다. 시스템의 주요 목표는 대학교에 서비스로서 사용자 프로그램들의 연속적인 흐름을 원활하게 처리하는 것이다. 다중프로그래밍 시스템은 짧은 프로그램들의 처리 시간 감소, 주변장치의 경제적 사용, 보조 저장장치의 자동 제어를 염두에 두고 선택되었다.

그룹의 구성원들 — 대부분 수학자들 — 은 이전에 5년에서 8년의 좋은 대학 교육을 받았고 석사 또는 박사 수준이었다. 원래 포함되었던 자격이 덜 갖춰진 한 젊은이는 우리의 활동이 그의 정신적 이해력을 넘어선다는 것을 알게 되어 그룹을 떠났다. 시스템 설계에 필요한 지적 수준은 일반적으로 크게 과소평가되어 있다. 나는 이러한 종류의 작업이 매우 어렵고, 최고의 인재가 아닌 다른 사람들과 함께 하면 막대한 비용을 들인 실패에 그칠 운명이라고 더욱 확신하게 되었다.

1958년까지 거슬러 올라가는 광범위한 경험을 가진 팀의 선장으로서, 나는 실시간 인터럽트를 다루는 기본 소프트웨어를 만드는 쓰라린 경험으로 인해, 인터럽트 순간의 비재현성의 결과로 프로그램 오류가 때때로 기계 오작동처럼 오해의 소지가 있게 자신을 드러낼 수 있다는 것을 알고 있었다. 결과적으로 나는 몹시 두려웠다.

두려움에서 영감을 받은 이 결정은, 내가 그룹의 주요 기여라고 여기는 것의 밑바탕에 있다. 우리는 정제된 다중프로그래밍 시스템을, 그 논리적 건전성이 선험적으로(a priori) 증명될 수 있고 그 구현이 철저한 테스트를 허용하는 방식으로 설계하는 것이 가능하다는 것을 발견했다.

테스트 중에 나타난 유일한 오류들은 사소한 코딩 오류들(500 명령어당 단 하나의 오류 밀도)이었고, 각각은 10분 이내에 위치를 찾아 쉽게 수정되었다. 우리는 두 개 이상의 위험 요소의 불행한 "우연의 일치"와 같은 상황에서 시스템 탈선이 발생할 수 있다는 영구적인 두려움 속에 살지 않을 것이다 — 우리는 수학적 증명의 대다수에서는 드문 엄밀함과 명시성으로 시스템의 정확성을 증명했기 때문이다.

우리는 순차적 프로세스에서 다양한 상태들의 시간적 연속만이 논리적 의미를 가지며, 순차적 프로세스가 수행되는 실제 속도는 그렇지 않다는 사실을 완전히 인식했다. 따라서 우리는 전체 시스템을 정의되지 않은 속도 비율로 진행하는 순차적 프로세스들의 사회로 배열했다. 그들의 조화로운 협력은 명시적인 상호 동기화 문장에 의해 규제된다.

이 접근법의 근본적인 결과는, 그러한 순차적 프로세스들의 조화로운 협력이 이산적 추론에 의해 확립될 수 있다는 것이다. 추가적인 결과로, 협력하는 순차적 프로세스들의 전체 사회는, 이 프로세스들을 수행하는 데 사용할 수 있는 실제 프로세서의 수와 독립적이다.

전체 시스템은 엄격한 계층적 구조를 허용한다.

레벨 0에서 우리의 첫 번째 추상화가 달성되었고, 레벨 0 위에서 실제로 공유되는 프로세서의 수는 더 이상 관련이 없다. 레벨 1에서 정보의 식별은 세그먼트의 관점에서 이루어지며, 실제 저장 페이지들은 정체성을 잃고 그림에서 사라졌다. 각 레벨은 그 아래 레벨이 제공하는 추상화 위에 구축되며, 상위 레벨은 하위 레벨의 구현 세부사항을 알 필요가 없다.

개념 정립 단계에는 오랜 시간이 걸렸다. 우리는 프로세스들이 상호 동기화와 관련하여 서로에게 어떻게 영향을 미쳐야 하는지를 요구사항으로부터 추론하는 기술을 배웠고, 서로에 의해 동기화된 프로세스들의 사회가 모든 요구사항을 만족한다는 것을 증명할 수 있는 추론의 기술을 배웠다.

검증 단계에서 우리는 소프트웨어 디버깅 도구 없이 처녀 기계로 작업했다. 레벨 0에서 시작하여, 이전 레벨이 철저히 테스트된 후에야 매번 다음 레벨을 추가했다. 각 테스트 샷에는 테스트 프로세스가 이중 기능으로 포함되었다 — 첫째 시스템을 모든 관련 상태로 강제하고, 둘째 시스템이 사양에 따라 반응하는지 검증한다.

레벨 0(실시간 클럭과 프로세서 할당)의 테스트는 그 위에 여러 테스트 순차 프로세스를 두고 프로세서 시간이 규칙에 따라 분할되는지 검사하는 것이었다. 이것이 확립되자, 레벨 1에서 세그먼트 컨트롤러를 테스트했다. 그 단계에서 실시간 클럭의 존재는 너무 비물질적이어서 테스터 중 한 명이 실제로 그 존재를 잊어버렸다.

범용 객체를 테스트할 때 그것을 모든 가능한 경우에 노출시킬 수는 없다. 따라서 관련 테스트 케이스의 집합으로 테스트해야 한다. 무엇이 관련 있는지는 메커니즘을 블랙박스로 보는 한 결정될 수 없고, 테스트될 메커니즘의 내부 구조로부터 따라가야 한다.

관련 테스트 케이스의 수가 너무 작아서 그가 그들 모두를 시도할 수 있고, 무엇이 테스트되고 있는지가 너무 명료해서 그가 놓친 것이 없음이 분명하도록 — 즉, 매우 고도로 구조화된 — 메커니즘을 구축하는 것이 설계자의 책임이다.

산업용 소프트웨어 제작자들은 우리가 일종의 모델 작업을 했다고 판단하며, 사용된 기법들이 대학 부서 밖에서 적용 가능한지 의문을 표한다. 우리가 겸손한 범위에서만 그것을 할 수 있었다는 의견을 과소평가하는 것은 나의 의도가 아니다. 그러나 10배 또는 그 이상의 사람들이 있는 훨씬 더 큰 작업일수록, 구조화가 더 본질적이라는 의견을 감히 말하고 싶다.

THE 시스템의 6레벨을 쌓아 올린다. 각 레벨이 추가될 때마다 그 아래의 무언가가 "정체성을 잃고 그림에서 사라진다" — 레벨 0 위에서 프로세서의 수가, 레벨 1 위에서 물리적 페이지가, 레벨 3 위에서 실제 주변장치가. 위 레벨은 아래 레벨이 제공하는 깨끗한 추상화만 보면 된다. 아래 모션은 계층이 어떻게 한 층씩 쌓이고 검증되는지를 보여준다.