프로그래밍 언어론 제 4-1 장(보충 자료) 기억 장소 할당 정적 및 동적 기억 장소 할당 단위 프로그램 정적 기억 장소 할당 스택 기반 기억 장소 할당

8.1 기억장소 할당(Storage Allocation) 기억 장소 할당 기법 프로그래밍 언어의 일부 특징들과 매우 밀접하게 관련 프로그래밍 언어를 설계하고 구현하고자 할 때, 우선 고려할 사항 중 하나 예 ) recursion 허용(반환 주소들을 위한 실행 시간 스택, 지역 변수들에 대한 동적 기억 장소 할당) 배열 크기 변화 등 방식 정적 기억장소 할당 번역 시간 동적 기억장소 할당 실행 시간

8.1 정적 및 동적 기억 장소 할당(1) 정적 기억 장소 할당 동적 기억 장소 할당 번역 시간 할당 (적재 시간) 기억장소 크기와 위치가 정적으로 고정 배열 접근코드가 효율적 (크기 고정) 기본조건 사용된 모든 배열은 확정된 고정 크기로 선언 서브프로그램(한번 실행에 필요한 크기의 기억장소)은 recursion 불가 FORTRAN, COBOL 등 동적 기억 장소 할당 실행 시간 할당 변수 제한 완화 (자료형, 크기 등) 인터프리터 언어 - LISP, SNOBOL4, APL Algol 類 언어(스택 기반 할당) - recursion 허용

8.1 정적 및 동적 기억 장소 할당(2) 정적 + 동적 기억 장소 할당 1) ALGOL 2) PL/I own 변수 : 정적 할당 own 이외의 변수 : 동적 할당 (recursion 허용) 변수 크기가 실행시, 할당 후 고정(stack based) 2) PL/I STATIC : 정적 할당, AUTOMATIC : 동적 할당 (스택 기반) CONTROLLED, BASED : 동적 할당 (heap 기억 장소 할당)

8.2 단위 프로그램(1) 지역변수(local variable) 활성화 상태(activated state) 단위 프로그램에서 선언하여 사용하는 변수 활성화 상태(activated state) 한 단위 프로그램의 실행 시작부터 종료까지

8.2 단위 프로그램(2) 단위 활성화(Unit activation) - 실행 시간에 한 단위 프로그램이 표현된 상태 구성 1) 코드부(code segment) 명령어들로 구성 고정 크기 내용 불변 2) 활성 레코드(activation record) 지역변수 등 프로그램 실행시 요구되는 정보들 가변적(크기, 내용) 코드부 활성레코드 <단위 활성화>

8.2 단위 프로그램(3) 오프셋(Offset) 참조 환경(referencing environment) 활성 레코드 바인딩 활성레코드에서의 상대위치 자료 참조시 주소 대신 사용 참조 환경(referencing environment) 단위 프로그램의 지역 변수 및 사용 가능한 비 지역변수 - 지역변수 : 현재 단위 프로그램 활성 레코드에 할당 - 비지역 변수 : 다른 단위 프로그램 활성 레코드 할당 활성 레코드 바인딩 - 코드부와 해당 활성 레코드의 바인딩(코드부는 실행 시간 내내 하나만 존재) - recursion : 활성레코드가 재귀적으로 여러 개 발생 => 동적 바인딩 - recursion 불허용 : 활성 레코드가 1개만 존재 => 정적 바인딩

8.3 정적 기억 장소 할당(Static Storage Allocation) 대표적 언어 Cobol, Fortran, Basic 등 정적 할당 (예: Fortran 77) 하나의 주프로그램과 몇 개의 서브프로그램으로 구성 기억장소 총 용량 – 번역시간에 계산(실행시간에 변하지 않음) 서브프로그램 - 분리 컴파일 가능 활성 레코드 - 실행 전에 할당하여 실행 종료시까지 유지 정적 변수(static variable) : 번역 시간에 크기 고정, 번역 시간 할당 변수의 수명 = 프로그램 실행 시간 전체 Fortran 77에서의 변수의 영역 – 변수가 선언된 단위 프로그램에 국한 전역 변수 - COMMON 제공 (시스템 제공 활성 레코드에 속함) 지역 변수 - COMMON 이외의 모든 변수 모든 변수 - 오프셋 고정 (주소 대용) 링크시 - 유효(effective) 주소 고정 프로그램 실행 전에 지역 변수들에 대한 초기값 한정 가능 – DATA문 사용

8.3 정적 기억 장소 할당(2) . . . 그림8.1 한 Fortran 프로그램의 실행 상태 단위 프로그램 (주 프로그램) 전역 변수 (COMMON ) 코드부 1 활성 레코드 단위 프로그램 2 K . . . (주 프로그램)

8.3 정적 기억 장소 할당(3) 장점 단점 단순, 구현용이 실행 속도의 효율성 flexibility 적음 배열 크기 불변 recursion 불가 활성화되지 않을 수도 있는 활성레코드가 항상 주기억장치에 상주

8.4 스택 기반 기억 장소 할당 동적 기억 장소 할당 기법을 사용하는 언어들 1) 컴파일러를 사용하여 구현되는 언어들(블록 중심 언어) ALGOL 60, Pascal, ALGOL 68, PL/I, Ada, C, Java등 2) 인터프리터 기법을 사용하여 구현되는 언어들 APL, Lisp, SNOBOL4, PROLOG, Smalltalk ALGOL 類 언어(Algol-like language) Algol 60의 영향을 크게 받아 설계된 언어 블록 개념을 도입한 언어들 (영역 단위) - 선언문으로 새로운 환경 정의 단위 프로그램 : 블록, 서브프로그램 - 블록 : 정상적인 프로그램 실행 과정에서 차례가 되었을 때 활성화 - 서브프로그램 :호출문에 의하여 호출되었을 때 활성화 동적 기억 장소 할당을 논할 때 고려 사항 변수수명, 단위 프로그램 활성, 참조 환경, 생성에 관한 규칙들 활성화 레코드(변수)크기 결정 시점 다양 - 번역 시간, 활성화 시점, 동적변화

A B C D E F G A B C D E F G 그림 8.2 Algol 類 언어의 정적 내포 관계 예 단위 프로그램 구조 정적 내포 관계 트리 unit A A B C D E F G end A unit B unit C unit D end D end C end B unit G unit F unit E end E end G end F A B C D E F G 그림 8.2 Algol 類 언어의 정적 내포 관계 예

8.4 스택 기반 기억 장소 할당(2) 활성 레코드 크기의 크기가 정적으로 확정되는 경우 : 정적 바인딩 활성 레코드 크기의 크기가 정적으로 확정되는 경우 : 정적 바인딩 지역 변수 생성 : 단위프로그램의 활성화 시점 기억 장소 용량 : 번역시간에 확정 변수 오프셋 : 정적 바인딩 활성 레코드 : 매 호출시 할당 => recursion 허용 준정적(semi-static) 변수 : 크기 (오프셋) 번역 시간 고정, 실행 시간 할당(실제 주소 실행 시간 바인딩) 예) Pascal, C(포인터 개념 제외)의 활성 레코드 a : array[0..10] of integer; [C의 경우, int a[11];] => 크기는 정적 바인딩 활성레코드 위치(x)는 실행 시점에 결정 (유효 주소 - 동적 바인딩) 즉, loc a[i] = x + a의 offset + i * s (S는 정수에 대한 기억 장소의 크기)

8.4 스택 기반 기억 장소 할당(3) 활성레코드 크기 : 정적 바인딩 (계속) 단위 엑티베이션 구조 - 코드부 : 기계어 명령어 - 활성(엑티베이션) 레코드 (동적 링크 , 반환주소 포함) 동적링크 : 호출한 단위프로그램의 활성 레코드 주소 현재 활성화된 활성 레코드부터의 동적 체인 구성 => 동적 내포관계 표현 (현 활성화까지 계속 호출된 활성 레코드 체인) 나를 호출한 것이 누군가? 반환주소 : 반환시 실행 주소 (호출자의 코드부 內) 그림 8.2의 단위 프로그램 F와 G가 서로 반복하여 A -> E -> F ->G ->F -> G ->F 순서로 호출할 때의 활성 레코드들의 상태는 그림 8.4

코드부 (code segment) 반환 주소 나머지 활성 레코드 활성 레코드 동적 링크 (지역변수,매개변수,정적링크등) 그림 8.3 단위 프로그램의 전형적인 활성화

• 그림 8.4 한 전형적인 활성화 상태 A 에 대한 활성 레코드 E F 단위 프로그램 G 시스템으로 반환 코드부 . . . 호출 • 그림 8.4 한 전형적인 활성화 상태

미사용 FREE CURRENT 그림 8.5 실행 중 스택에서 활성 레코드들의 동적 링크 관계 활성 레코드 (현재 실행중인 동적 체인(나를 호출한 것이 누군가?) CURRENT FREE (현재 실행중인 활성 레코드) 스택이 증가 하는 방향 활성 레코드

• 그림 8.6 그림 8.4에 대한 활성 레코드들의 스택 CURRENT F 의 활성 레코드 G E A 스택이 증가하는 방향 동적 링크 • 그림 8.6 그림 8.4에 대한 활성 레코드들의 스택

8.4 스택 기반 기억 장소 할당(5) 활성레코드의 크기 : 활성화 시점 바인딩 - 단위 프로그램의 활성화 시점에서 지역변수 생성 => 이때 지역변수의 기억장소 크기확정 ∴ 지역변수 오프셋 : 실행시간에 확정 준동적 변수(semidynamic variable) - 기억장소 크기가 활성화 시점에서 확정되는 변수 동적 배열(dynamic array) - 활성화 시점에 배열크기 확정 (준동적 변수) => 사용자의 flexibility 제공 ALGOL60, ALGOL68, Ada 등에서 허용

Ada에서 한 단위 프로그램 U에서의 선언문이 사용된 예 Get (M, N) declare A : array(1…N) of INTEGER; B : array(1…M) of FLOAT; begin … end

8.4 스택 기반 기억 장소 할당(6) 준 동적 변수(동적 배열)의 기억 장소 할당 순서 1) 번역시간에 ① 준동적 변수(동적 배열 A, B)의 명세표만을 활성레코드에 삽입 - 오프셋의 상수 개념 사용 가능 참고) 명세표 - 차원 수 등 정적으로 알려진 정보만 저장, 명세표 크기 고정 2) 실행시간 활성 레코드를 기억 장소에 할당하는 순서 ① 활성레코드(준 정적변수, 준 동적 변수 명세표)기억장소 할당–이미 확정 ② 계산된 준동적 변수 기억장소만큼 활성 레코드 할당 ③ 준동적 변수 기억장소 주소를 명세표에 배정(명세표의 포인터에 바인딩) 준동적 변수의 오프셋도 상수화(정적으로 확정)

• 그림 8.7 준동적 변수가 있는 전형적인 활성 레코드 U의 나머지 준정적 변수 단위 프로그램의 활성 레코드 B 배열 (M) 1 (N) U 의 일부 준정적 변수 동적 링크 반환 주소 B에 대한 명세표 스택이 증가하는 방향 A A에 대한 • U의 나머지 준정적 변수 그림 8.7 준동적 변수가 있는 전형적인 활성 레코드

활성레코드 크기 : 동적 바인딩 (실행시 변화) 8.4 스택 기반 기억 장소 할당(7) 활성레코드 크기 : 동적 바인딩 (실행시 변화) - 프로그램 실행 중에 새로운 자료값이 생성되고 회수되어 활성 레코드의 크기가 변하는 경우 동적(dynamic) 변수 실행시 변수 크기가 수시로 변할 수 있는 변수 예) Algol68, Ada, Fortran90, C, C++, Java등에서 제공하는 힙동적 배열 또는 flexible array 프로그램이 실행 중에 할당되는 자료들에 맞추어서 크기를 조절할 수 있는 배열 예) 프로그램에서 변수 생성 시점을 정해주는 변수들 동적 변수 특성 프로그램 실행 중에 생성/해제 가능 => 동적 변수 생성 프로그램 종료 후에도 기억장소 유지 => 스택의 활성레코드에 할당 불가 => 힙(heap) 기억장소에 할당 (명세표는 스택의 활성 레코드에 할당) ∴ 스택 변수 : 준정적, 준동적 변수 힙 변수 : 동적변수 예) PL/I(controlled, based), Pascal(pointer), Algol68, Ada(access)

8.4 스택 기반 기억 장소 할당(8) 동적메모리 할당 예 (Pascal, Ada) Pascal의 동적 할당 P Ada new(P); Ada type SEQ is array(INTEGER range <>) of FLOAT; type SEQREF is access SEQ; p : SEQREF ; ... p := new SEQ(1..50); heap new(P) : P는 레코드 t의 포인터 ① t형의 기억장소를 힙에 할당 ② 할당된 주소를 P에 배정 ③ dispose(P)를 만날 때까지 유지 P stack p := new SEQ(1..50); ① SEQ 형 메모리를 힙에 할당 ② 시작 주소를 p에 배정 ③ 명시적인 해제문장(free)까지 유지

CURRENT P A B (?) 그림 8.8 동적 변수를 스택에 할당 못하는 이유

8.4 스택 기반 기억 장소 할당(9) 비지역 변수의 참조 Fortran ALGOL 類 언어 - 다른 활성레코드에 정의된 변수값 참조 ① 지역변수 : 지역환경(local environment) ② 비지역변수 : 비지역환경(nonlocal environment) Fortran ① 지역 변수 - 현재 단위프로그램 활성레코드 ② 전역 변수 - 시스템 제공 활성레코드 ALGOL 類 언어 ② 비지역 변수 - 정적 내포관계

x 선언 A B C D E F G y선언 … y := x ; 그림 8.9 그림 8.2에서 변수 선언 예

8.4 스택 기반 기억 장소 할당(10) Algol68의 지역/비지역 변수 참조 <단위 프로그램 구조> <활성레코드 실행 상태> 호출순서 : A →E →F →G →F →G →F unit A x 선언 end A unit B end B 정적링크 - 단위프로그램 내포구조 표현 동적링크 - 단위프로그램 호출 순서 표현 unit C end C unit D end D F의 “y := x” y : CURRENT + y의 옵셋 (지역변수) x : E 활성레코드 시작 + x의 옵셋 (비지역변수) unit E x 선언 end E unit F y 선언 y := x end F unit G x 선언 end G

그림 8.10 정적 링크가 첨가된 그림 8.7의 예 CURRENT F G E A 의 활성 레코드 스택이 증가하는 방향 동적 정적링크 CURRENT 그림 8.10 정적 링크가 첨가된 그림 8.7의 예

8.4 스택 기반 기억 장소 할당(11) (1)정적 체인(Static Chain) 비지역 변수의 참조 방법 - 단위프로그램의 정적 내포관계 비지역 변수 검색방법 정적 체인을 따라 탐색 - 실행시간 낭비 간격(distance) 사용 - 간격 : 정적 내포 구조의 단계 수(현 단위 프로그램에서 선언된 지역 변수는 0) 예: (그림 8.11) D에서의 간격 : 지역 변수 z (D에서 선언) –0 비지역 변수 y (B에서 선언) - 1 비지역 변수 x (A에서 선언) - 2 => 변수 주소 : (d, o)로 표현 (번역 시간에 결정 가능) d : 간격, o : 옵셋 - 간격 만큼 정적 링크 추적 (간격이 클 때는 시간 소요)

• A B D C . . . 그림 8.11 프로그램 구조와 활성 레코드 상태 X선언 y선언 Z선언 정적 링크 . . . 실행중 A의 활성 레코드 B의 활성 레코드 C의 활성 레코드 D의 활성 레코드 • 정적 링크 CURRENT (b) (a)에서 ABCD 순으로 호출 실행 상태에서 있는 활성 레코드들의 스택 상태 (a) 한 프로그램 구조 예

8.4 스택 기반 기억 장소 할당(12) (2) 디스플레이 비지역 변수의 참조 방법 (계속) - 정적체인 관계를 가변배열 형태로 표현 방법 (d, o) 개념 사용 유효주소(d, o) = DISPLAY[m-d] + o 활성 레코드의 시작 주소는 DISPLAY[m-d] m : DISPLAY 사용 활성레코드 수 d : 간격, o : 오프셋 장단점 모든 비지역 변수 참조시간 동일 활성레코드의 발생, 소멸시 디스플레이 내용 변경 단위 프로그램의 호출과 반환 횟수에 비하여 비지역 변수들의 사용이 상대적으로 증가할 경우 효과적인 방법 DISPLAY current m ... 3 2 1

그림 8.12 그림 8.10의 예에 대한 디스플레이 사용 F 의 활성 G 레코드 E A 동적 링크 스택이 증가하는 방향 1 2 3 디스플레이 배 열 첨자값 그림 8.12 그림 8.10의 예에 대한 디스플레이 사용