Orca는 loosely coupled 분산 시스템에서 돌아가는 병렬프로그램을 구현하기위한 언어로 네델란드의 Vrije 대학의 Henri E. Bal 이 주축이 되어 1986년부터 개발되고 있다. 

Orca가 개발된 동기는 분산 시스템기반에서 기존의 메세지 전달 방식으로 확장된 순차처리 기반의 언어를 가지고 병렬프로그램을 만드는데 발생하는 문제점들을  극복하기 위한 것이며, Orca는 시스템 프로그래밍을 위한 것이 아니라 분산 응용 프로그래밍을 위해 연구되고 개발되어 왔다.
 

1 분산 공유 메모리(Distributed Shared Memory)

대부분의 분산 프로그래밍은 메세지 전달 방식에 의존하고 있다. 기반 하드웨어가 메세지 전달을 이미 지원하기 때문에 이러한 선택은 매우 자연스러운 것이다. 그러나 모든 경우에 있어서 이 방법이 효과적일 수는 없다. 여러 프로세스가 광역의 상태 정보를 공유하여 통신을 하는 경우에는 메세지 전달 방법이 적절하지 않다. 
 

이러한 문제를 해결하기 위해서 서로 다른 시스템간에 따로 존재하는 물리적인  메모리를 프로그래머에게는 논리적으로  하나의 공유된 메모리로 보이게 하는 연구가 진행되어 왔으며 이를 분산 공유 메모리(Distributed shared memory)라 부른다. 

공유 메모리를 사용하는 다중 프로세서 시스템에서는 공유 데이터 구조가 공유 메모리에 저장되며 저장되어 있는 데이터를 사용하는 방법은 기본적으로 지역 메모리를 접근하는 것과 동일하다.  한 프로세스가 공유 데이터의 한 부분을 바꾸려고 하고 이 때 다른 프로세스가 이 공유 데이터 구조에 어떠한 접근도 하지 않게 하기 위해서 이러한 시스템의 경우에는 그 부분에 대하여 "잠금(lock)"을 하는 메커니즘을 가진다.  일반적으로  지역 메모리에 접근하는 것보다 이러한 공유 메모리에 접근하는 것이 더 많은 오버헤드를 발생시킨다.

분산 시스템에서는 각 시스템이 자신의 지역 메모리를 가지고 있기 때문에 공유 메모리 다중 프로세서 시스템에서와는 달리  메모리 접근에 대한 오버헤드가 필요한 데이터의 위치에 의존한다. 

분산 시스템에 공유 메모리를 구현하기 위해서 공유 메모리를 사용하는 다중 프로세서 시스템처럼 공유 데이터에 대하여 쓰고, 읽고, 잠금하는 저 수준의 명령어를 언어차원에서 지원할 수도 있을 것이다. 그러나 Orca에서는 이에 대한 해결책으로 공유 데이터 구조를 "데이터 객체(data-object)"라는 곳에 encapsulate한다. 

데이터 객체에 encapsulate된 공유 데이터는 사용자가 정의한 연산에 의해서 관리된다.  Orca에서 사용하는 데이터 객체는 추상화 데이터 형(abstract data type)의 인스턴스로 볼 수 있다.
 
 
 
 

2 프로세스
 

컴파일러가 병렬성을 효율적으로 만들어 줄 수 없기 때문에 Orca에서는 명시적으로 병렬성을 구현한다. 즉, Orca에서는 순차 프로세스를 명시적으로 생성함으로써 병렬성을 구현하고 있다. Orca 언어로 만들어진 프로그램이 처음 시작하면 하나의 프로세스만 실행이 된다.  그러나 새로운 프로세스를 fork statement를 사용해서 명시적으로 생성한다.

fork name(actual parameters) [ on (cpu-number)];

위의 문장은 새로운 anonymous 자식 프로세스를 생성시킨다. fork 문장은 on 예약어를 사용할 수 있는데, on 을 사용하여 cpu를 지정하면 자식 프로세스는 지정한 프로세서에 생성된다. on을 사용하지 않으면 자식 프로세스는 같은 프로세서에 생성이 된다. 사용가능한 cpu는 NCPUS standard function을 통해서 알수 있다.

프로세스는 input과 shared의  두 가지 종류의 파라미터를 가질 수 있다. input 파라미터로는 어떤 종류의 데이터 구조도 가질 수 있으며 프로세스는 이 파라미터의 복사본을 가지게 된다. 부모 프로세스는 자식 프로세스에게 공유 파라미터로써 데이터 객체를 넘겨 줄 수 있다. 이 경우에는 부모와 자식 프로세스가 데이터 객체를 공유하며 이 공유 객체를 통해서 서로 통신을 하게 된다. 예를 들어 child 라는 프로세스가 다음처럼 선언되었다고 가정하자.

process child(Id: integer; X: shared AnObjectType); begin ... end;

그러면 새로운 child 프로세스는 다음과 같이 생성되어 질 수 있다.

MyObj: AnObjectType;   # 객체 선언
...
# 새로운 자식 프로세스를 생성하고 value 파라미터로는 12를 
#공유 파라미터로는 MyObj 객체를 전달한다.
fork child(12, MyObj);

자식 프로세스는 공유 객체를 이와 같은 방식으로 자신의 자식 프로세스에게 넘겨줄 수 있으며, 그 자식 프로세스는 또 다시 자신의 자식 프로세스에게 같은 공유 객체를 넘겨 줄 수 있다. 이런 식으로 데이터 객체가 공유 되는 것이다. 만약 공유 객체를 공유하고 있는 프로세스 중에 어느 한 프로세스가 이 공유 객체의 연산을 가하면 다른 모든 프로세스들도 같은 효과를 보게 된다. 이는 마치 그 객체가 하나의 공유 메모리에 있어서 잠김에 의해 보호 받는 듯이 보이게 되는 것이다. 
 
 

3 공유 데이터 객체와 추상화 데이터 형(Shared data-objects and abstract data types)

공유 데이터 객체는 추상화 데이터 객체(객체 형)의 인스턴스이다.  Orca에서 추상화 데이터 형의 정의는 상세(specification)부분과 구현(implementation)부분의 두 단계로 이루어진다.

상세 부분

object specification  IntObject;
  operation  Value(): integer;
  operation  Assign(val: integer);
  operation  Add(val: integer);
  operation  Min(val: integer);
end;
 

구현 부분

object  specification  IntObject;
   x: integer;

   operation  Value():  integer;
   begin
      return  x;
   end;

   operation  Assign(v: integer);
   begin
      x := v;
   end;
   …
begin
   x := 0;    # 객체의 초기화 부분
end;
 

일단 객체 형(object type)이 정의되면, 정의된 형의 인스턴스는 다음과 같이 생성되고 사용된다. 

X:  IntObject;
tmp:  integer;

X$Assign(3);             #  3을 X에 할당
X$Add(1);                 #  X 값을 증가
tmp := X$Value();      #  X의 현재 값 읽기
 

객체가 생성되면 그 객체의 지역 변수에 대한 메모리가 할당되고 초기화 코드가 실행된다. 

Orca는 하나의 추상화 데이터 형을 지원한다. 다시 말해서 똑 같은 추상화 형을 가지고  지역 객체(local object)와 공유 객체를 생성한다.  이 정보는 객체 선언 또는 객체 형 선언 시에 주어지지 않고, fork 문장을 이용해서 새로운 프로세스 생성시 공유 파라미터로 전달되는 객체는 공유 객체로 사용되고 그렇지 않은 객체는 지역 객체로 사용된다. 

물리적인 하드웨어 분산을 감추고 공유 데이터를 효과적으로 시뮬레이션하기 위해서 Orca에서는 복사(replication)와 안정된 브로드케스팅reliable broadcasting)에 기반한 구현을 하고 있다.  각 프로세서는 각 공유 객체의 복사본을 가진다.  이 공유 객체에 대해서 아무런 변화를 주지않는 연산(read 연산)은 지역에 복사되어 있는 공유 객체의 데이터를 직접 사용하고,  이 공유 객체에 변화를 가하는 연산(write 연산)은 변화된 새로운 값을 다른 모든 프로세서에게 브로드케스팅 하는 방법으로 공유 객체를 업데이트 한다. 
 

4 동기화(Synchronization)

Orca에서의 추상화 데이터 형은 지역 객체뿐만 아니라 공유 객체를 생성하는데 모두 사용될 수 있다.  공유 데이터 객체 생성의 경우는 동기화의 문제가 발생하며 두 가지 종류의 동기화가 있다.
 

4.1  상호 배타 동기화(Mutual exclusion synchronization)

상호 배타 동기화는 객체에 대한 모든 연산을 나누지 않고 실행함으로써 내포적으로 이루어 진다. 개념적으로 각 연산은 이 연산이 적용되는 모든 객체에 대하여 잠금(lock)을 하고, 그 후에 해당 일을 한다.  해당 일이 모두 끝난 후에는 잠금을 해제 한다. 또한 이 모델이 지원하는 상호 배타 동기화는 serializability을 보장한다. 즉, 두 개의 연산이 동시에 같은 공유 객체에 접근하면 결과적으로는 하나의 연산이 다른 연산의 다음에 적용되는 것과  같은 것이 된다. 그러나,  연산에 대한 순서는 사전에 결정되어지지 않는다
 

4.2  조건 동기화(Conditional synchronization)

조건 동기화의 경우는 어떤 특정 조건이 만족될 때까지 모든 프로세스가 대기한다.  이 모델에서는 조건 동기화는 연산들에 잠금을 허용함으로써 연산의 수행과 결합되어 있다.

operation  op(formal parameters): ResultType;
begin
   guard  condition(1)  do  statement(1)  od;
   …
   guard  condition(n)  do  statement(n)  od;
end;

조건은 boolean 이며 guard로 불린다.  위의 연산은 guard 중에 하나가 참이 될 때까지 잠김된다.  하나가 선택되면 그 구문이 실행되는 것이다.
 
 
 

5  계층적 객체(Hierarchical objects)

추상화 데이터 형은 간단하게 언어가 새로운 형을 갖도록 확장할 수 있다.  새로운 형을 구축하는 방법은 새로운 데이터 형을 만드는데 기존의 추상화 데이터 형을 이용할 수 있기  때문에 계층적이다.  따라서,  한 객체의 내부 데이터는 그 자체가 객체라고 볼 수 있다.  하지만 이러한 계층구조가 객체지향 언어에서처럼 하나가 다른 하나를 상속한다는 것은 아니다.  새로운 데이터 객체와 예전의 데이터 객체 사이에는 상속의 관계가 아닌 “사용”의 관계를 가진다. 

이러한 객체의 nesting은 실재로 디자인을 어렵게 만드는 문제를 내포하고  있다. 아래와 같이 OldType이라는 기존의 객체가 있다고 하자.

object  specification  OldType;
   operation  OldOperation1() :  boolean;
   operation  OldOperation2();
end;

OldType은 다른 형을 구현하는데 사용되어 질 수 있다.

object  implementation  NewType;
  NestedObject: OldType;
  operation  NewOperation();
  begin
    guard  NestedObject$OldOperation1() do
     …
      NestedObject$OldOperation2();
    od;
  end;
end;

위의 코드에서 새로운 형의 객체는 OldType형의 NestedObject를 포함하고 있다.  후자의 객체를 nested 객체라 부르는 이유는 이 객체가 다른 객체의 일부분이기 때문이다. 
 
 
 

6. 성 능(Performance)*

Orca언어의 성능을 알아보기 위하여 병렬 branch-and-bound 알고리즘으로 구현된 traveling saleman problem(TSP)을 가지고 테스트해 보았다. [그림 1]은 사용된 알고리즘을 보여준다.  

프로그램이 시작되면 먼저 Manager 프로세스가 하나의 프로세서에서 구동된다. 그 후 Manager프로세스는 초기화를 위하여 JobQueue 공유 객체와 Minimum 공유 객체를 만들고, 일을 할 Worker 자식 프로세스를 다른 프로세서위에 하나씩 구동되도록 생성한다.  초기화가 끝나면 Manager프로세스는 JobQueue 공유 객체에 Job을 하나씩 집어 넣는다. JobQueue 공유 객체에 들어가는 Job은 각 도시를 이어주는 임의의 경로이다. 그러나 전체 도시가 다 연결되어 있지는 않고 일부의 도시만 이어져 있는 Job이다. 각 Worker 프로세스는 JobQueue 공유 객체에 들어있는 Job을 가져다가 이 Job을 기준으로 생성가능한 모든 경로를 만들어 Minimun 공유 객체에 들어 있는 현재까지의 최소 경로와 비교해본다. 비교 결과 더 짧은 경로면 Minimun 공유 객체에 들어 있는 경로를 업데이트 시키고 그렇지 않으면 다시 다른 Job을 JobQueue 공유 객체로 부터 꺼내와 같은 작업을 반복한다. 
 

이 실험이  시행된 환경은 10Mbit/s Ethernet으로 연결되어  16 개의 MC68030 cpu(16MHz) 로 이루어진 분산 시스템이며 그 결과는 다음 그림에 나타나 있는  그래프와 같다. 
 
 

*Bal. H.E., Kaashoek, M.F., and Tanenbaum A.S.: "Orca: A Language for Parallel Programming of Distributed Systems", IEEE Transactions on Software Engineering, vol. 18, No. 3, March 1992, pp. 190-205 (Copyright (c) 1992 by IEEE).