협력하는 순차 프로세스

동시성 프로그래밍의 초석. 1965년 가을 학기 다익스트라의 강의 노트로 쓰인 이 글에서, 우리가 오늘날 운영체제 교과서에서 만나는 거의 모든 개념이 처음 모습을 드러낸다.

문제는 이렇다. 여러 순차 프로세스가 — 속도 비율이 알려지지 않고, 통신 가능성이 제한된 채 — 협력해야 한다. 공통 변수에 대한 분할 불가능한 접근만으로는 부족하다. 변수를 검사한 순간과 그에 반응하는 순간 사이에, 다른 프로세스가 그 값을 바꿔버릴 수 있기 때문이다. 다익스트라의 해법은 새로운 종류의 원시 연산이다 — 세마포어(semaphore)와, 그것에만 작용하는 P 연산·V 연산.

두 연산의 정의는 정밀하다. V(S)는 세마포어 S의 값을 1 증가시킨다 — 분할 불가능하게. P(S)는 결과 값이 음이 아닌 한 S를 1 감소시킨다 — 즉 S가 0이면 다른 프로세스가 V를 수행할 때까지 기다린다. 핵심은 "분할 불가능"이다. S := S+1은 두 프로세스가 동시에 실행하면 증가 하나를 잃을 수 있지만, V(S)는 그렇지 않다. 이것이 동시성 제어의 원자(atom)다.

이 두 연산만으로 다익스트라는 일련의 고전적 문제를 차례로 푼다. 단일 이진 세마포어 free로 상호 배제(mutual exclusion) — 임계 영역에 한 번에 한 프로세스만. 일반 세마포어로 생산자-소비자 문제 — 무한 버퍼를 통한 단방향 통신. 그리고 그는 일반 세마포어가 이진 세마포어만으로 흉내 낼 수 있음을 보이며, 그 과정에서 "잠자는 이발사(Sleeping Barber)"라는 우아한 비유를 소개한다.

마지막으로 교착 상태(deadly embrace) — 한 프로세스가 다른 것이 먼저 죽어야만 계속될 수 있는 상황. 다익스트라의 해법은 은행원 알고리즘(Banker's Algorithm)이다. 은행원은 고객에게 플로린을 빌려주되, 잠정적으로 빌려준 뒤 모든 거래가 완료될 수 있는지 — "안전한" 상태인지 — 검사하고, 안전하지 않으면 "기다리라"고 말한다. 그리고 이 노트의 마지막 통찰 — 동시 프로그래밍과 다중프로그래밍은 같은 논리적 구조의 다른 구현일 뿐이다. (참고로, 이 학기 말 시험 문제가 바로 "다섯 철학자의 만찬"이었다.)

복잡한 해결책으로 이끄는 문제의 근원은 공통 변수에 대한 분할 불가능한 접근이 항상 "단방향 정보 트래픽"이라는 사실에 있다. 검사 자체는 다른 프로세스에 어떤 흔적도 남기지 않으며, 그 결과 프로세스가 공통 변수의 현재 값에 반응하고자 할 때, 그 검사 순간과 반응의 수행 사이에 다른 프로세스들에 의해 값이 변경될 수 있다.

이러한 대안은 특수 목적 정수 — "세마포어(semaphores)" — 와 두 가지 새로운 기본 연산, "P-연산"과 "V-연산"을 도입함으로써 제공된다. P/V 연산은 항상 세마포어에 대해 작동하며, 병행 프로세스들이 세마포어에 접근할 수 있는 유일한 방법을 나타낸다.

시간적으로 서로를 배제해야 하는 임계 영역을 각각 가진 N개의 프로세스에 대한 해결책은 이제 간단해진다. 단일 이진 세마포어 "free"의 도움으로 이를 달성할 수 있다. "free = 1"은 어느 프로세스도 임계 영역에 관여하고 있지 않음을, "free = 0"은 하나가 관여하고 있음을 의미한다.

P(free)는 임계 영역 진입 전에 호출되어, 다른 프로세스가 임계 영역에 있으면 대기하게 한다. V(free)는 임계 영역을 떠날 때 호출되어, 대기 중인 다른 프로세스가 진입할 수 있게 한다.

우리는 각각 "생산자"와 "소비자"라고 불리는 두 프로세스를 고려한다. 생산자는 매 주기마다 소비자가 처리해야 할 정보 부분을 생산한다. 두 프로세스는 무한 용량의 버퍼를 통해 연결되어 있다. ("버퍼"라는 이름의 기원은 그것의 부재의 결과를 조사하면 이해할 수 있다 — 버퍼 없는 연결은 펀치가 유휴 상태인 기간과 컴퓨팅 프로세스가 유휴 상태인 기간을 번갈아 초래한다.)

이제 "큐잉 중인 부분의 수"라고 불리는 단일 일반 세마포어로 두 프로세스를 구성할 수 있다.

V-연산이 부분의 완전한 추가에 선행되어야 함이 절대적으로 필수적이다. 다익스트라는 일반 세마포어가 이진 세마포어만으로 흉내 낼 수 있음도 보인다. 그 과정에서 등장하는 한 프로그램은 "잠자는 이발사(The Sleeping Barber)"로 알려져 있다.

두 프로세스가 유한 크기 N의 버퍼를 통해 결합되면 관계는 대칭이 된다. "소비자는 버퍼에서 빈 위치를 생산하고, 생산자는 빈 위치를 소비한다." 두 개의 일반 세마포어 — 큐잉 중인 부분의 수, 빈 위치의 수 — 가 완전한 대칭성을 이룬다.

다양한 프로세스가 같은 시설을 공유해야 할 때 발생하는 논리적 문제가 있다. 저장 공간을 페이지 단위로 빌리는 프로세스들을 생각하자. 총 저장소가 100페이지일 때 — P1이 41페이지, P2가 21페이지를 빌려 사용 가능 저장소가 38페이지로 줄었다면, 이것은 안전하지 않은 상황이다. 두 프로세스 모두 각각 추가로 39페이지를 필요로 할 수 있는데 38만 사용 가능하기 때문이다.

이 상황 — 한 프로세스가 다른 것이 먼저 죽어야만 계속될 수 있을 때 — 을 "교착 상태(The Deadly Embrace)"라고 부른다. 풀어야 할 문제는 — 불필요하게 제한적이지 않으면서 교착 상태의 위험을 어떻게 피할 수 있는가.

은행원이 유한한 자본을 가지고 있다. 고객은 미리 최대 "필요(need)"를 명시하고, 그 필요를 초과하지 않는 한 대출을 늘리거나 줄일 수 있다. 요청된 플로린을 지불할 수 있는지 결정하기 위해, 은행원은 본질적으로 그가 지불한 것처럼 발생할 상황을 검사한다. 이 상황이 "안전"하면 지불하고, 안전하지 않으면 "기다려야 합니다"라고 말한다.

문헌에서 때때로 "동시 프로그래밍" — 같은 작업에서 하나 이상의 중앙 프로세서가 작동하는 것 — 과 "다중프로그래밍" — 단일 프로세서가 다른 작업들 사이에 시간을 나누는 것 — 사이에 날카로운 구별이 발견된다. 나는 항상 이 구별이 다소 인위적이고 따라서 혼란스럽다고 느꼈다.

두 경우 모두, 거시적으로 말해서, 다수의 순차 프로세스들이 서로 협력해야 하며, 이 협력에 대한 우리의 논의들은 어느 쪽에든 동등하게 잘 적용된다. 동시 프로그래밍에서 공간에 퍼져 있는 것(즉, 장비)은 다중프로그래밍에서 시간에 퍼져 있다. 두 경우 모두 같은 논리적 구조의 다른 구현들이다.

마지막으로 나는 프로그램들의 정확성에 대한 내 관심을 표현하고 싶다. 인간 정신이 시간에 따라 진화하는 처리를 생각하는 것이 끔찍하게 어렵고, 우리의 가장 큰 도움은 식별된 양들의 값에 의미들을 부여하는 것임을 느낀다. 우리는 어느 정도의 복잡성을 가진 각 프로세스에서 변수들이 계층적 순서를 인정한다는 것을 굳게 믿으며, 이러한 계층들이 프로그램 텍스트에서 명확하게 인식 가능할 때 명료성과 효율성의 이득이 상당할 것이다.

두 프로세스가 임계 영역에 들어가려 한다. 이진 세마포어 free가 그 문지기다. free가 1이면 자유, 0이면 점유 중. P(free)는 문을 통과하려는 시도이고, V(free)는 문을 다시 여는 행위다. 아래 모션은 한 프로세스가 임계 영역에 있는 동안 다른 프로세스가 P(free)에서 어떻게 멈추는지, 그리고 V(free)가 그를 어떻게 풀어주는지를 보여준다.