[Programming Language] 7. 부프로그램 구현 (1)

직전글

2023.07.31 - [Language] - [Programming Language] 6. 부프로그램(Subprogram) (4)

 

● 호출과 복귀의 일반적인 의미

- 부프로그램 연결

부프로그램 호출과 복귀 연산을 통틀어 부르는 용어

호출과 복귀의 시각화

 

- 부프로그램 호출 과정

호출 과정은 사용되고 있는 매개변수 전달 방법의 구현을 포함해야 함.
지역 변수가 정적 변수가 아니라면, 호출 과정은 피호출 부프로그램에서 선언된 지역 변수를 위한 기억 장소를 할당하고, 그 기억장소에 지역 변수를 바인딩하여야 하며, 호출 프로그램 단위의 실행 상태를 저장해야 함.

이후, 제어를 부프로그램 코드에 전달하고, 부프로그램이 끝났을때 제어가 반환될 수 있도록 해야 함.

언어가 중첩 부프로그램을 지원한다면, 호출과정은 피호출 부프로그램이 가시적인 비지역 변수(ex. 정적·동적 조상의 지역변수, 클로저)를 접근할 수 있는 동작 구조를 생성해야 함.

※실행 상태: 호출 프로그램 단위의 실행을 재개하기 위해 필요한 정보들. 레지스터 값, CPU 상태 비트, 환경 포인터 (EP: Environment Pointer)가 포함됨.

 

- 부프로그램 복귀 과정

부프로그램이 출력 모드 또는 입출력 모드이면서 복사 전달로 구현되는 매개변수를 가진다면, 관련된 형식 매개변수의 지역 값을 실 매개변수로 옮겨야 함.
다음으로, 지역 변수에 사용된 기억 장소를 해제하고 호출 프로그램 단위의 실행 상태를 복원함.
마지막으로, 제어를 호출 프로그램에 반환함.

 

● 단순 부프로그램의 구현

- "단순" 의 의미

부프로그램이 중첩될 수 없고, 모든 지역 변수가 정적임을 의미함.

 

- 호출 과정

(1) 호출 프로그램 단위의 실행 상태를 저장

(2) 매개변수를 계산하고 전달

(3) 복귀 주소를 피호출 프로그램에 전달

(4) 제어를 피호출 프로그램에 전달

 

- 복귀 과정

(1) 값-결과-전달 매개변수나 출력-모드 매개변수가 사용된다면, 그러한 매개변수의 값을 대응되는 실 매개변수로 복사
(2) 부프로그램이 함수라면, 호출 프로그램이 접근 가능한 장소로 함수 값(반환 값)을 이동
(3) 호출자의 실행 상태 복원
(4) 제어를 호출자에게 전달

 

- 호출과 복귀를 위해서 저장되어야 하는 정보들

== 별도의 기억 장소를 요구하는 정보들

(1) 호출자의 실행 상태 정보
(2) 매개변수
(3) 복귀 주소
(4) 함수의 반환 값
(5) 부프로그램에서 사용하는 임시 기억 장소 (언어마다 존재할 수 있음)
이상의 정보들은 지역 변수 및 부프로그램 코드와 함께 단순 부프로그램의 호출과 복귀에 필요한 완전한 정보 집합을 이룸.

 

- 단순 부프로그램의 구성

(1) 변하지 않는 부프로그램 코드

(2) 실행 중 변할 수 있는 지역 변수 + 위에서 살펴본 정보들 (호출과 복귀를 위해서 저장되어야 하는 5가지 정보)
단순 부프로그램인 경우, 이 두 부분은 모두 고정 크기임.

 

- 활성화 레코드 (Activation Record)

부프로그램의 코드가 아닌 부분의 형식을 활성화 레코드라 부름.
즉, 앞서 나온 단순 부프로그램을 구성하는 두 가지 부분 중, 코드를 제외한 부분의 형식을 부르는 용어.
왜냐하면, 이 부분에 속하는 데이타들이 부프로그램의 활성화(또는 실행)과 관련 있기 때문임.
활성화 레코드의 형식은 정적임. (바뀌지 않음)
활성화 레코드 인스턴스: 활성화 레코드의 구체적인 예이며, 활성화 레코드의 형식에 따라 저장된 데이터의 모음.

 

단순 부프로그램을 갖는 언어(ex. Fortran)는 재귀 부프로그램을 지원하지 않기 때문에, 한 시점에 활성화된 부프로그램은 오직 하나만 존재함. 따라서, 부프로그램의 활성화 레코드 인스턴스는 오직 하나만 존재하게 됨.
이상과 같은 경우, 활성화 레코드의 가능한 형식

활성화 레코드 인스턴스 예시

앞서 얘기한 정보들(지역변수 + 5가지 정보) 중에서, 이 활성화 레코드에서는 호출자의 실행 상태가 생략되었고, 함수의 반환 값이 없는 경우이기 때문에 생략되었음.

 

- 단순 부프로그램을 갖는 프로그램의 코드와 활성화 레코드 예제

단순 부프로그램의 활성화 레코드 인스턴스는 고정 크기이므로, 정적으로 할당가능함.
다음 그림은 주프로그램 MAIN과 세 개의 부프로그램 A, B, C으로 구성된 프로그램에서의 프로그램 코드와 활성화 레코드를 보여줌.

이 형태는 컴파일러에 의해 완성되는 것은 아님. 네 개의 프로그램 단위는 각기 다른 시기에 컴파일 되었을 수 있음.
각 프로그램 단위가 컴파일될 때, 외부 부프로그램의 참조 리스트와 더불어 기계어 코드가 파일로 작성됨.
그림과 같은 형태는 운영체제의 일부인 링커에 의해 통합됨. 링커는 로더, 링커/로더, 또는 링크 에디터라고도 불림.

 

ㄴ 링커의 일반적인 동작

(1) 주프로그램에서 참조된 번역된 부프로그램들을 포함한 파일을 찾고, 그 파일들을 메모리에 로드함.
(2) 주프로그램에 있는 부프로그램 호출의 목적지주소를 부프로그램의 진입 주소로 설정함
(3) 적재된 부프로그램에 있는 다른 부프로그램에 대한 모든 호출과 라이브러리 부프로그램에 대한 모든 호출에 대해서도 동일한 작업 수행

링커의 역할 시각화

● 스택 동적 지역변수를 갖는 부프로그램의 구현

스택 동적 지역 변수의 가장 중요한 장점 중 하나는 재귀 부프로그램을 지원한다는 점임.

 

- 복잡한 활성화 레코드

ㄴ 스택 동적 지역 변수를 사용하는 언어에서의 부프로그램 연결이 단순 부프로그램에서보다 더 복잡한 이유
(1) 컴파일러는 지역 변수의 묵시적인 할당과 해제를 수행하는 코드를 생성해야 함.
(2) 재귀는 부프로그램의 다중 동시 활성화 가능성을 증대하고, 각 활성화는 활성화 레코드 인스턴스를 요구함.
이는 주어진 시점에 한 개 이상의 부프로그램 인스턴스(종료되지 않은 실행)가 존재한다는 것을 의미.

 

대부분의 언어에서 주어진 부프로그램의 활성화 레코드 형식은 컴파일 시간에 알려짐. 또한, 많은 경우에, 모든 지역 데이터는 고정 크기이므로 활성화 레코드의 크기도 컴파일 시간에 알려짐.

예외) 지역 배열의 크기가 실 매개변수의 값에 종속되는 언어(Ada 등)에서는, 활성화 레코드 형식은 정적이지만, 활성화 레코드의 크기는 동적임.

 

ㄴ 스택 동적 지역 변수를 갖는 언어의 전형적인 활성화 레코드 형식

복귀 주소, 동적 링크, 매개변수는 호출자에 의해서 활성화 레코드 인스턴스에 놓여지기 때문에, 이 항목들이 먼저 나타나야 함. 지역 변수는 피호출 부프로그램에서 할당 및 초기화되기 때문에 활성화 레코드의 마지막에 나타남.

 

+ 복귀 주소

대개 호출 프로그램 단위의 코드 세그먼트에 있는 호출 다음 명령어에 대한 포인터로 구성됨.

(쉽게 말해 호출한 곳 직후를 가르키고 있다고 보면 됨.)

+ 동적 링크
호출자의 활성화 레코드 인스턴스의 기준점에 대한 포인터임.
정적 영역 언어에서, 이 링크는 실행-시간 오류가 발생할 때, 추적 정보를 제공하기 위하여 사용됨
동적 영역 언어에서, 동적 링크는 비지역 변수를 접근하기 위하여 사용됨. (이후 관련 내용 나올 예정)

 

+ 매개변수

호출자가 제공한 값 또는 주소

 

+ 지역 변수

지역 스칼라 변수는 활성화 레코드 인스턴스 안에 있는 기억 장소에 바인딩 됨.
데이터 구조(Data Structure) 형태인 지역 변수는 때때로 다른 곳(힙 또는 다른 활성화 레코드 인스턴스)에 할당되고, 데이터 구조의 서술자와 기억 장소에 대한 포인터만이 활성화 레코드의 일부가 됨.

 

+ C언어 예시

void sub(float total, int part) {
  int list[5];
  float sum;
  ...
}

함수 sub의 활성화 레코드

부프로그램을 활성화는 활성화 레코드 인스턴스의 동적 생성을 요구함
앞서 설명한 것처럼, 활성화 레코드 인스턴스의 크기는 실행 시간에 변경될 수 있어도, 형식은 컴파일 시간에 고정됨.
호출과 복귀 의미에 따르면, 마지막에 호출된 부프로그램이 먼저 끝나야 함. 이에 따라, 활성화 레코드 인스턴스를 스택에 생성하는 것이 타당함. 이 스택은 런타임 시스템의 일부이므로, 런타임 스택이라고 불림. (여기선 단순히 스택이라고 부를 예정)
재귀적이든 비재귀적이든, 모든 부프로그램 활성화는 새로운 활성화 레코드를 스택에 생성함.

 

ㄴ 환경 포인터(EP: Environment Pointer)

앞서 실행 상태를 언급할 때 나왔던 용어로, 부프로그램의 실행을 제어하기 위해 요구되는 정보 요소임.

런타임 시스템은 EP가 항상 현재 실행 중인 프로그램 단위의 활성화 레코드 인스턴스의 기준 주소를 가르키도록 해야 함.

프로그램 시작 시점에, EP는 주프로그램의 활성화 레코드 인스턴스의 기준 주소, 즉 첫 주소를 가리킴.
부프로그램이 호출될 때, 현재의 EP는 동적 링크로서 새로운 활성화 인스턴스에 저장됨.
그 다음, EP는 새로운 활성화 레코드 인스턴스의 기준 주소를 가리키도록 설정됨.
부프로그램으로부터 복귀할 때, 스택 꼭대기를 재설정(스택 꼭대기에 있는 활성화 레코드 인스턴스를 제거)하고, 실행을 종료한 부프로그램의 활성화 레코드 인스턴스에 있는 동적 링크의 값으로 EP를 재설정.

EP는 활성화 레코드 인스턴스의 데이터 (매개변수, 지역 변수) 내용을 접근하는 오프셋 주소의 기준으로 사용됨.

현재 사용되고 있는 EP는 런타임 스택에 저장되지 않음.

 

ㄴ 활성화 레코드 인스턴스를 사용하는 부프로그램 호출 동작

(1) 활성화 레코드 인스턴스 생성
(2) 호출 프로그램 단위의 실행 상태를 저장
(3) 매개변수를 계산하고 전달
(4) 복귀 주소를 피호출 프로그램에 전달
(5) 제어를 피호출 프로그램에 전달

단순 부프로그램 호출 동작과 동일함.

 

ㄴ 피호출자의 프롤로그 동작

== 피호출 부프로그램 실행 시작 시점의 동작
(1) EP를 동적 링크로서 스택에 저장하고, EP에 새로운 값을 생성
(2) 지역 변수 할당

 

ㄴ 피호출자의 에필로그 동작

== 피호출 부프로그램 종료 시작 시점의 동작
(1) 값-결과 전달 매개변수나 출력 모드 매개변수가 사용된다면, 그러한 매개변수의 값을 대응되는 실 매개변수로 복사
(2) 부프로그램이 함수라면, 호출 프로그램이 접근 가능한 장소로 함수 값(반환 값)을 이동

(3) 스택 꼭대기를 재설정한 뒤, 삭제되는 활성화 레코드에 저장되어 있던 동적 링크의 값으로 EP를 재설정

(4) 호출자의 실행 상태 복원
(5) 제어를 호출자에게 전달

3번 빼고는 단순 부프로그램 복귀 동작과 동일함.

 

- 재귀 없는 부프로그램 예제

// C
void fun1(float r) {
   int s, t;
   ...        // 지점 1
   fun2(s);
   ...
}

void fun2(int x) {
   int y;
   ...        // 지점 2
   fun3(s);
   ...
}

void fun3(int q) {
   ...        // 지점 3
}

void main() {
   float p;
   ...
   fun1(p);
   ...
}

호출 순서: main이 fun1 호출 → fun1이 fun2 호출 → fun2가 fun3 호출

지점 1 에서 main과 fun1의 활성화 레코드 인스턴스(ARI, Activation Record Instance)만 존재 함.
각각 지점 2, 지점 3 에서 fun2, fun3의 ARI가 추가됨.
fun3가 종료되면 ARI가 삭제됨. 마찬가지로 fun2와 fun1이 종료되면, ARI들 삭제됨.
마지막에는 main의 ARI만 존재.

추가 그림 설명

ㄴ 동적 체인 (또는 호출 체인)
주어진 시점에서 스택에 있는 동적 링크의 집합을 의미.
동적 체인은 실행이 현 지점까지 도달한 동적 역사를 반영함.

 

ㄴ 지역 오프셋
지역 변수의 참조는 코드에서 활성화 레코드의 시작 지점(EP로 표시되는 주소)으로부터 지역 영역의 오프셋으로
나타냄. 그런 오프셋을 지역 오프셋이라고 함.
위 그림에서, 첫 지역 변수는 활성화 레코드의 시작 지점으로부터 (매개변수의 개수 + 2) 위치에 할당됨. "+2"는 복귀 주소와 동적 링크를 위한 장소가 각각 1개씩 필요하기 때문.

fun1에서 s의 지역 오프셋은 3 (= 1 + 2 + 0)이고, t의 지역 오프셋은 4 (=1 + 2 + 1)임.

지역 변수의 주소를 얻으려면, 변수의 지역 오프셋을 EP에 더하면 됨.