유한한 자원을 갖는 마이크로프로세서를 위한 프로세스 언어 document_id A220517004659

〈관련 출원〉 본 출원은 2004년 2월 12일자로 출원된 미국 가출원 제60/544,144호의 우선권을 주장하며, 상기 가출원의 전체 내용은 본 명세서에 참조로서 포함된다. 본 발명은 일반적으로 프로그래밍 언어에 관한 것으로, 더 상세하게는 최종적으로 유한한 자원을 갖는 마이크로프로세서에 의해 실행될 수 있는 프로세스들, 및 그 프로세스들의 상호작용을 표현하는 인공 언어에 관한 것이다. CISC 기반 마이크로프로세서(102)와 같은 마이크로프로세서들은 모든 퍼스널 컴퓨터의 핵심이다. 도 1을 참조하여 설명한다. 전원(104)과 메모리(106)가 CISC 기반 마이크로프로세서(102)에 추가되면, 컴퓨터를 구성하는 데에 필요한 모든 부분이 제공되게 된다. CISC 기반 마이크로프로세서(102)는 자신에게 주어진 명령들에 따라 행동함으로써 태스크를 수행한다. ''명령(instruction)''이란 프로그래밍 언어와 같은 인공 언어로 쓰여진 표현식이다. 과거에는 복잡한 명령을 수행할 수 있는 마이크로일렉트로닉 하드웨어의 단가가 매우 높았기 때문에, 초기의 마이크로프로세서는 단순한 명령들만을 사용했었다. 시간이 흘러 이러한 단가가 낮아짐에 따라, 보다 더 복잡한 명령들을 사용할 수 있게 되었다. 복잡한 명령(복수의 마이크로프로세서 동작을 지정하는 단일 명령)을 사용하면, 컴퓨터는 추가의 명령을 검색하지 않아도 되므로, 시간을 절약할 수 있다. 예를 들어, 7개의 동작이 하나의 명령으로 결합된 경우, 명령을 인출하는 단계들 중 6개가 제거되고, 마이크로프로세서가 해당 동작을 프로세스하는 데에 소비되는 시간이 감소된다. 7개의 명령을 단일 동작으로 결합하는 마이크로프로세서는, 복잡한 명령 집합 컴퓨터(complex instruction set computers, CISC)로 칭해진다. CISC 기반 마이크로프로세서(102)는 명령들의 실행 결과를 저장하기 위하여 레지스터를 사용한다. 각각의 레지스터는 CISC 기반 마이크로프로세서(102) 내에서 특정 목적의 데이터를 보유하는 데에 사용되는 고속 메모리의 비트들의 집합이다. 각각의 레지스터는 어셈블리 언어 프로그램에서 AX(인텔 80X86 프로세서에서 산술 연산의 결과를 보관하는 레지스터) 또는 SP(다양한 CISC 기반 마이크로프로세서 내의 스택의 최상위에서의 메모리 어드레스를 보관하는 레지스터)와 같은 이름으로 참조된다. 각각의 레지스터는 근본적으로는 CISC 기반 마이크로프로세서(102)의 컴포넌트들 간에서의 공유 메모리이다. 레지스터를 공유 메모리로서 사용하면, 하나의 컴퓨터는 특정 동작을 수행하고, 그 특정 동작의 결과를 레지스터에 저장한다. 순차적인 방식으로, 다른 컴포넌트가 동일 레지스터에 액세스하여, 다른 동작의 수행에 의한 결과를 얻을 수 있다. 이와 같이 동작들을 순차적으로 실행하면, CISC 기반 마이크로프로세서(102)의 컴포넌트들은 그들 간의 통신에서 동시성(synchrony)을 갖는 것처럼 보일 수 있게 된다. CISC 기반 미들웨어(108) 등에서, 프로그램 내의 거의 모든 명령은 순차적으로 실행되도록 설계된다. CISC 기반 마이크로프로세서(102)에서 이용될 수 있는 하드웨어 인터럽트는, 비동시성(asynchrony) 및 그에 의한 동작들의 병행(concurrent) 실행을 부가하기 위한 한 방법으로서 사용될 수 있다. 하드웨어 인터럽트는 CISC 기반 마이크로프로세서로부터의 서비스 리퀘스트로서, 디스크 드라이브 또는 입출력 포트와 같은 하드웨어 장치에 의해 외부적으로 생성되거나 CISC 기반 마이크로프로세서 자체에 의하여 내부적으로 생성될 수 있다. 외부 하드웨어 인터럽트는 포트로부터 수신되어 프로세스될 필요가 있는 캐릭터, 데이터의 블럭을 전송하기 위한 디스크 기입 준비, 또는 시스템 타이머의 틱(tick)과 같은 상황을 위해 사용된다. 내부 하드웨어 인터럽트는, 프로그램이 이용할 수 없는 어드레스에 액세스하거나 0으로 나누는 것과 같은 불가능한 액션을 시도할 때에 발생한다. 발산성 아키텍쳐(divergent architecture)(마이크로프로세서의 동시성 특성과 하드웨어 인터럽트의 비동시성 특성)로 인해, 인터럽트 핸들러 내의 단 하나의 프로그래밍 에러만으로도, CISC 기반 마이크로프로세서(102)가 교착되거나, 데이터가 복원불가능할 정도로 크게 손상될 수 있다. π계산법 프로그램(πcalculus program)(110)은 CISC 기반 미들웨어(108) 및 CISC 기반 마이크로프로세서(102)의 동시적이고 순차적인 실행 설계에 대해 원하는 비동시성 및 병렬성을 부여할 수 있다. π계산법은 대화형의 병행 시스템(interactive concurrent system)들에서의 프로세스를 기술하기 위한 수학적 언어이다. π계산법의 핵심은 링크를 통하여 통신하는 독립적인 병렬 프로세스들의 시스템으로 이루어진다. 한 프로세스가 다른 프로세스와 통신할 가능성은 다양한 링크들에 대한 지식에 따라 달라진다. 링크는 특정 프로세스만의 통신을 허용하도록 제한될 수 있다. π계산법은 컴퓨팅에 요구되는 많은 비동시성 및 병렬성을 부여하지만, 중대한 단점을 갖고 있다. π계산법은 구조화된 정보가 아닌 비트 패턴만으로 정의된 순수 이름에 크게 중점을 둔다. π계산법과 그 변형들은 명명된 링크 상에서 구조화된 데이터가 통과하는 것을 거의 허용하지 않는다. π계산법에서는, 이름 X와 같은 새로운 이름을 생성하기 위하여 ν연산자가 사용된다. 예를 들어, 수학적 항 (νX)P는 이름 X의 생성을 나타내며, 그 범위는 프로세스 P로 제한된다. 프로세스 P의 컴포넌트들은 X를 사용하여 서로 상호작용할 수 있지만, 다른 프로세스들과는 상호작용할 수 없다. 구조적으로 일치하는 수학적 규칙 (νX)(νX)P≡(νX)P에 대해 고찰한다. (νX)항은, malloc()과 같은 함수를 사용하는 메모리 할당을 요구하는 연산으로서 정의된다. 컴퓨팅 시스템 내에는 (νX)항을 1회 호출할 수 있을 만큼의 메모리만이 남아있다고 가정한다. 이러한 경우, 구조적으로 일치하는 규칙의 우변에 있는 (νX)항은 실패없이 프로세스된다. 그러나, 2번째의 (νX) 호출은 메모리 폴트를 유발하므로, 구조적으로 일치하는 규칙의 좌변에 있는 (νX)(νX)항은 프로세스되지 못할 것이다. π계산법의 또다른 문제점은 복제(replication) !P의 수학적 개념이다. π계산법은 언어의 프리미티브로서 복제 !P를 제공한다. !P항은 서로 병렬로 실행되고 있는 프로세스들 P의 무한 합성(infinite composition)을 의미하는 것으로 해석될 수 있다. !P는 이론적으로는 초월적이지만, 실제의 구체화에서는 문제를 유발한다. 마이크로프로세서는 메모리 및 대역폭과 같이 유한한 자원을 갖는 것이다. π계산법 프로그램은 원하는 비동기성을 부여하긴 하지만, 자신이 실행되고 있는 마이크로프로세서가 자원의 한계를 갖는다는 것은 인식하지 못한다.