9장 기억 장소 배당 (Storage Allocation)
기억 장소 할당 기법
- 번역 시간에 수행되는 정적 기억장소 할당기법, 실행 시간에 수행되는 동적 기억장소 할당 기법이 있다.
- PL의 일부 특징들과 매우 밀접하게 관련된다.
- PL 설계 및 구현에서 우선적으로 고려할 사항 중 하나이다.
ex) Recursion 허용 여부, 배열 크기 변화 허용 여부 등
9.1 정적 및 동적 기억 장소 배당
정적 기억 장소 할당
- 번역 시간에 할당 (적재 시간)
- 기억장소 크기와 위치가 정적으로 고정
- 배열 접근코드가 효율적 (크기가 고정되어 있으므로)
- 사용된 모든 배열은 확정된 고정 크기로 선언되어야 함
- 서브프로그램은 Recursion을 수행할 수 없음
ex) Fortran, Cobol, Basic에서 정적 기억 장소 할당 기법을 채택함
동적 기억 장소 할당
- 실행 시간에 할당
- 변수 제한 완화 (데이터 형, 크기 등)
- Algol-like 언어들에서는 Recursion을 허용함
ex) 인터프리터 언어들(LISP, SNOBOL4, APL)에서 동적 기억 장소 할당 기법을 채택함
Algol
- own 변수: 정적 할당
- own 이외의 변수: 동적 할당 (Recursion이 허용됨)
- 변수 크기가 실행 시, 할당 후 고정됨 (stack based)
PL/I
- STATIC: 정적 할당
- AUTOMATIC: 동적 할당 (stack based)
- CONTROLLED, BASED: 동적 할당 (heap 기억 장소 할당)
C/C++, Java
- static: 정적 할당
- auto: 동적 할당 (stack based, default)
- heap 기억장소 할당: C(malloc, free), C++(new, delete), Java(new)
* Java에서는 Garbage Collection 기능이 있어, free, delete에 해당되는 개념이 필요하지 않음
9.2 단위 프로그램(Program Unit) = 모듈(Module)
- 새로운 환경 설정 (new environment)
- 선언 가능: 지역 식별자 도입
- 지역 변수(Local Variable): 단위 프로그램에서 선언하여 사용하는 변수
(즉, 해당 모듈에 없는 변수는 Non-Local 혹은 Global 변수이다.)
- 활성화 상태 (Activated State): 한 단위 프로그램의 실행 시작부터 종료까지
- 블록도 단위 프로그램에 속함
단위 활성화 (Unit Activation)
- 실행 시간에 한 단위 프로그램이 표현된 상태
- 구성: 코드부, 활성 레코드
1. 코드부 (code Segment)
- 명령어들로 구성되어 있음
- 고정된 크기
- 불변하는 내용
2. 활성 레코드 (Activation Record)
- 지역변수 등 프로그램 실행 시 요구되는 정보들
- 가변적인 내용과 크기
* 오프셋 (Offset)
- 활성 레코드에서의 상대적 위치
- 참조 시 주소 대신 사용됨
* 참조 환경 (Referencing Environment)
- 단위 프로그램의 지역 변수 및 사용 가능한 비 지역변수
- 지역 변수: 현 단위 프로그램 활성 레코드에 할당
- 비지역 변수: 다른 단위 프로그램 활성 레코드에 할당
* 활성 레코드 바인딩
- 코드부와 활성 레코드의 바인딩
- 재귀 호출 허용: 활성 레코드가 재귀적으로 계속 발생 -> 동적 바인딩 필요
- 재귀 호출 불허: 활성 레코드가 하나만 존재 -> 정적 바인딩 가능
9.3 정적 기억 장소 배당 (Static Storage Allocation)
ex) 정적 할당 기법을 채택한 대표적 PL로 Cobol, Fortran, Basic 등이 있음
Fortran77 (정적 할당)
- 하나의 메인 프로그램과 다수의 서브 프로그램으로 구성
- 기억장소의 총 용량: 번역시간에 계산되며, 실행시간에 변하지 않음
- 서브 프로그램의 분리 컴파일이 가능
- 활성 레코드는 실행 전에 할당되어 실행 종료 시까지 유지됨
- 정적 변수(static variable)은 번역 시간에 크기가 고정되어 번역 시간에 할당되어 수명은 프로그램 실행 시간과 동일시 됨
- 일반적인 Fortran77의 변수들은 변수가 선언된 단위 프로그램을 Scope로 함
- COMMON을 통해 전역 변수 선언 (시스템 제공 활성 레코드로 간주)
- 지역 변수는 COMMON 이외의 모든 변수가 해당
- 모든 변수는 오프셋이 고정되어 있어 주소에 대응될 수 있음
- 모듈 간 링크 시, 유효(effective)주소가 확정됨
- 프로그램 실행전에 DATA문을 통해 지역 변수들에 대한 초기값 한정이 가능함
정적 기억 장소 할당 기법의 장점
- 구현이 용이하며 간결함
- 효율적인 프로그램 실행이 가능함
정적 기억 장소 할당 기법의 단점
- 부족한 유연성(Flexibility)
- Recursion 불가능
- 활성화되지 않은 활성 레코드가 상주함 (오류 처리 루틴 등)
※ 정적 변수 (Static Variable)
- 번역 시간에 크기가 고정됨
- 번역 시간에 메모리가 할당됨 (정적 할당)
9.4 스택 기반 기억 장소 배당
동적 기억 장소 할당 기법
- 스택 할당과 힙 할당으로 구분됨
- 대부분의 컴파일러 언어에서 사용하는 형태임
ex) 블록 중심 언어: Algol 60, Pascal, Algol 68, PL/I, Ada, C/C++, Jave 등
ex) 인터프리터 언어: APL, Lisp, SNOBOL4, PROLOG, Smalltalk
Algol 유사 언어 (Algol-like Language)
- Algol 60의 영향을 받아 설계된 PL
- 블록 개념을 도입(영역 단위), 선언으로 새로운 환경을 정의함
- 단위 프로그램: 블록, 서브 프로그램
* 블록: 정상적인 프로그램 실행 과정에서 차례가 되었을 때 활성화 됨
* 서브 프로그램: 호출문에 의해 호출되었을 때 활성화 됨
기억장소 할당 시 고려 사항
1. 변수의 수명 (Extent)
2. 단위 프로그램의 활성 시간
3. 참조 환경, 생성에 관한 규칙들
※ 활성 레코드 크기의 바인딩 시간: 번역 시간, 활성화 시점, 동적 변화
활성 레코드의 크기
- 활성 레코드의 크기는 정적 바인딩됨
- 지역 변수는 단위 프로그램 활성화 시점에 생성 (automatic)
- 기억 장소 크기는 번역 시간에 확정
- 변수 오프셋도 정적 바인딩 됨
- 활성 레코드는 매 호출 시 할당됨 (Recursion 허용)
* 준정적 변수 (Semi-Static Variable)
- 크기(오프셋)는 번역 시간에 고정됨 (크기는 정적 바인딩)
- 실행 시간에 할당(실제 주소 실행 시간 바인딩): 기억장소 동적 할당
ex) Pascal(포인터 개념 제외), C(heap할당 제외)의 활성 레코드
a : array[0..10] of integer; (C의 경우, int a[11];)
- 크기는 정적 바인딩 됨
- 활성 레코드의 위치(x)는 실행 시점에 결정됨 (유효 주소, 동적 바인딩)
- 즉, loc a[i] = x + (a의 offset) + (i * s)
단위 엑티베이션의 구조
코드부
- 기계어 명령어가 위치함
활성 레코드
- 지역 변수, 형식 매개 변수 정적 링크 등이 위치함
* 반환 주소
- 반환 시 실행할 주소를 의미
- 호출자의 코드
* 동적 링크
- Dynamic Scope Rule에서 해당 함수를 호출한 주체와 연결된 링크
- 호출한 단위 프로그램의 활성 레코드 주소를 의미
- 동적 체인 구성 -> 동적 내포관계 표현
- 컴파일러가 해당 Scope에서 발견하지 못한 Non-Local Variable들을
동적 링크를 타고 가며 탐색함
* 정적 링크
- 컴파일러가 만든 정적 내포 관계 트리에서의 링크
- 그림에서의 정적 내포 관계 트리에서, 함수가 A -> E -> F -> G -> F -> G -> F 순서로 호출되었다 가정함
- 함수 F와 G를 Recursive하게 호출함
- 함수 A의 Return Address는 시스템이 됨
- 함수 E의 Activation Record에서 반환 주소는 함수 A내에서 E를 호출한 부분의 다음 주솟값임
- 함수 E의 Activation Record에서 동적 링크는 함수 A의 Activation Record와 연결됨
- 함수 F의 Activation Record에서 반환 주소는 함수 E내에서 F를 호출한 부분의 다음 주솟값임
- 함수 F의 Activation Record에서 동적 링크는 함수 E의 Activation Record와 연결됨
- 함수 G의 Activation Record에서 반환 주소는 함수 F내에서 G를 호출한 부분의 다음 주솟값임
- 함수 G의 Activation Record에서 동적 링크는 함수 F의 Activation Record와 연결됨
- 위와 같은 방식으로 호출된 함수에 대한 Activation Record를 Set-up해 나아가다가,
함수가 리턴을 시작하면, 생성된 순서의 반대로 Activation Record가 폐기되며 링크를 타고 올라간다.
- 활성 레코드들은 시스템이 제공한 stack에 생성된 순서대로 저장됨
- 새로 생긴 활성 레코드의 동적 링크는 먼저 stack에 push된 활성 레코드를 지칭하게 됨
- 이러한 방식으로 동적 체인을 구축함
활성 레코드의 크기는 활성화 시점에 바인딩 됨 (즉, 크기가 그 때 그 때 다르다)
- 단위 프로그램의 활성화 시점에서 지역변수 생성
- 이 때, 지역 변수의 기억 장소 크기가 확정됨
(지역 변수의 오프셋은 실행 시간에 확정되기 때문임)
※ 준동적 변수 (Semidynamic Variable)
- 기억 장소 크기는 활성화 시점에 바인딩 됨 (동적 바인딩)
- 기억 장소 할당도 동적으로 할당됨 (stack 할당)
* 동적 배열 (Dynamic Array)
- 준동적 변수의 한 종류임
- 활성화 시점에 크기가 확정되는 배열
- 사용자에게 유연성(Flexibility) 제공
ex) Ada에서의 준동적 변수 사용 예시
- 동적 배열에서 배열의 크기를 실행 시간에 확정지음 (활성화 됨)
준동적 변수(동적 배열)의 기억 장소 할당 방식
1. 번역 시간
- 준동적 변수의 명세표를 활성 레코드에 삽입
- 모든 오프셋은 상수로 취급이 가능함 (번역 시간동안에는 명세표의 크기만 알고있음)
* 명세표: 차원 수 등 정적으로 알려진 정보만을 저장하며, 명세표의 크기는 고정적임
2. 실행 시간
- 활성 레코드(준정적 변수, 준동적 변수 명세표) 기억장소 할당
- 확정 시, 준동적 변수 기억장소 할당
- 준동적 변수 기억장소 주소를 명세표에 배정
(준동적 변수의 오프셋도 상수화 됨)
- 배열의 명세표가 활성 레코드에 위치해 있다가, M, N(배열의 크기)이 확정(바인딩)되는 순간,
배열 A, B가 stack에 push됨
활성 레코드의 크기가 동적 바인딩되는 경우 (실행 시 활성 레코드의 크기가 변화)
- 프로그램 실행 중에 데이터가 생성/회수되어 활성 레코드의 크기가 변하는 경우
※ 동적 변수 (Dynamic Variable)
- 실행 시 변수 크기가 수시로 변할 수 있는 변수임
- 프로그램 실행 중 생성/해제가 가능
- 동적 변수 생성 후, 프로그램 종료 후에도 기억장소를 유지함 (메모리 공간 해제가 필수적)
- 스택의 활성 레코드에 할당이 불가능함
- Heap 기억 장소에 할당함 (명세표는 스택의 활성 레코드에 할당함)
ex) Algol 68, Ada, Fortran 90, C/C++, Java 등에서 제공
* 힙 동적 배열 (Heap-Dynamic Array), 유연성 배열 (Flexible Array)
- 프로그램 실행 중에 할당되는 데이터들에 맞춰서 크기를 조절할 수 있는 배열
ex) Pascal, C++, Ada, Algol 68, Java의 new
ex) C의 malloc
* Stack Variable: 준정적, 준동적 변수
* Heap Varialbe: 동적 변수
ex) PL/I(controlled based), Pascal(pointer), Algol 68, Ada(access)
동적 메모리 할당 예시 (Pascal, Ada)
- stack에는 명세표만 저장하고, 실제 데이터는 heap에 저장하여 서로를 포인터로 연결함
- 동적 변수를 stack에 저장하고, 그 위에 활성 레코드에 저장되고 나면, 동적 변수의 크기를 변경시키지 못하기 때문
Non-Local Variable의 참조 방법
- 다른 활성 레코드의 변수 참조
- Local Variable은 자신의 지역 환경(Local Environment)에 위치할 것임
- Non_local Variable은 비지역 환경 (Non-Local Environment) 어딘가에 위치할 것임
ex) Fortran의 지역 변수는 현재 단위 프로그램 활성 레코드에 위치함
ex) Fortran의 전역 변수는 시스템 제공 활성 레코드
ex) Algol-like 언어의 지역 변수는 현재 단위 프로그램 활성 레코드에 위치함
ex) Algol-like 언어의 비지역 변수는 정적 내포 관계를 따라 검색해 감
9.5 힙 기억 장소 배당 (Heap Storage Allocation)
- 정적 영역 규칙은 주로 번역 기법에서 사용하며, 동적 영역 규칙은 주로 인터프리터 기법에서 사용함
- 동적 기억 장소 할당은 Heap 기법을 이용함
ex) 인터프리터 언어 APL은 메인 프로그램의 변수가 전역 변수인 동적 영역 규칙을 사용함
- APL의 비지역 변수는 동적 링크를 이용하여 찾음
- APL 변수의 데이터 형과 크기는 실행 중 수시로 변화하며, 스택 기반 할당이 불가능 함
- 실제 데이터 값은 Heap 기억장소 할당 후 포인터로 연결됨
- APL에서 활성 레코드들은 모두 동적 링크로 연결됨
- APL의 모든 변수들은 Heap에 저장됨
