9. 기억장소 배당

기억장소 할당 기법 : 프로그래밍 언어를 설계하고 구현하고자 할 때 우선 고려 사항

-> recursion 허용 , 배열 크기 변화 등

 

정적 기억 장소 할당 : 번역 시간 (적재 시간) (컴파일 타임, 로딩 타임)

                                   기억장소 크기와 위치가 정적으로 고정

                                   배열 접근 코드가 효율적 (크기 고정)

                                   조건 : 사용된 모든 배열은 확정된 고정 크기로 선언

                                             부프로그램은 되부름(recursion) 불가

                                   Fortran, Cobol, Basic 등에서 사용

 

 

 

 

동적 기억 장소 할당 : 실행 시간

                                   변수 제한 완화(자료형, 크기 등)

                                   인터프리터 언어 - Lisp, Snobol4, APL

                                   Algol 형태 언어 - recursion 허용

 

 

 

정적, 동적 기억 장소 할당을 함께 수행하는 언어

1) ALGOL 

own 변수 : 정적할당

own 이외의 변수 : 동적 할당 (recursion 허용)

변수 크기가 실행 시, 할당 후 고정 (stack based)

 

2) PL/I

STATIC : 정적 할당

AUTOMATIC: 동적 할당 (스택 기반)

CONTROLLED, BASED : 동적 할당 (힙 기억 장소 할당)

 

3) C,C++,Java

static : 정적 할당

auto: 동적 할당(스택 기반) (default)

힙 기억장소 할당 : C(malloc, free) , C++(new, delete) , Java(new)

 

 

모듈(module) : 단위 프로그램 (program unit)

-> 프로그램을 실행하는 단위

-> 컴파일, 바인딩, 또는 실행과 같은 행위와 관련해서 분리되거나 식별이 가능하도록 개발된 프로그램의 일부분

-> 다른 프로그램이나 그 프로그램의 부분과 상호작용할 수 있음

 

새로운 환경 설정 (new environment)

- 지역변수(local variable) 선언 가능 -> 지역 식별자 도입

- 단위 프로그램에서 선언하여 사용하는 변수 , 모듈이 실행될 때마다 실행 환경은 다름

- 상대 주소 지정 : base + offset

 

활성화 상태 (activated state)

- 한 단위 프로그램의 실행시작 부터 종료까지

- 활성 여부 = 호출 여부

 

블록 = 실행 단위 = 단위 프로그램

- 함수는 이름이 있는 블록

- 일반 중괄호({})는 이름이 없는 블록

 

 

단위 활성화(Unit activation)

- 실행 시간에 한 단위 프로그램이 표현된 상태

 

구성

1) 코드부(code segment)

- 명령어들로 구성 , 고정 크기 , 내용 불변

 

2) 활성 레코드(activation record)

- 지역 변수 등 프로그램 실행 시 요구되는 정보들

- 가변적이다 (크기 내용 측면에서)

 

 

메모리

코드영역

데이터영역

힙 영역 (런 타임에 크기가 결정된다)

스택 영역 (컴파일 타임에 크기가 결정된다)

 

오프셋(Offset)

- 활성레코드에서의 상대위치

- 참조 시 주소 대신 사용

- 할당 시작 위치인 base + 자신의 위치가 얼마나 이동하였는지 offset

 

오프셋을 쓰는 이유는

1) 특정 위치를 직접 나타내는 절대 주소 방식을 사용하면 변경에 취약해지기 때문

2) 한번 분기해서 가는 게 자릿 수가 줄어들어 계산이 상대적으로 빨라짐

 

참조 환경(referencing environment)

- 단위 프로그램의 지역 변수 및 사용 가능한 비 지역변수

- 지역변수 : 현 단위 프로그램 활성 레코드에 할당

- 비지역 변수 : 다른 단위프로그램 활성 레코드에 할당

 

활성 레코드 바인딩 

- 코드부와 활성 레코드의 바인딩

- 재귀 호출 허용 : 동적바인딩이라고 하며, 활성 레코드를 재귀적으로 발생시킨다.

- 재귀 호출 비허용:  정적바인딩이라고 하며, 활성 레코드가 하나만 존재한다.

 

 

정적 기억 장소 배당

- 대표적인 언어로는 Fortran, Basic, Cobol언어가 있다.

 

Fortran77

- 하나의 주 프로그램과 몇개의 부 프로그램으로 구성

- 기억장소의 총 크기는 번역시간에 계산되며 실행시간에는 변하지 않는다.

- 부 프로그램은 분리 컴파일이 가능하다.

- 활성 레코드는 실행 전에 할당되며, 실행 종료 시까지 유지된다.

- 정적변수(static variable)은 번역 시간에 크기가 고정되며, 번역 시간에 할당된다.

- 변수의 수명은 프로그램 실행시간 전체 (접근 가능 시간에서 차이를 보인다.)

- 전역변수 COMMON (시스템 제공 활성 레코드)

- 지역변수 COMMON 이외의 모든 변수

- 모든 변수는 오프셋이 고정되어 있다. 이는 주소를 대용하여 사용된다.

- 링크를 할 경우에 유효주소로써 확정이 된다.

- 프로그램 실행 전에 지역 변수들에 대한 초기값의 한정이 가능하며 이는 DATA문을 사용한다.

 

 

 

정적 기억 장소 배당의 장점

1) 구현이 쉽고 간결하다

2) 효율적인 프로그램 실행이 가능하다.

 

정적 기억 장소 배당의 단점

1) 유연성(flexibility)가 적다

2) 배열 크기가 불변이다.

3) recursion이 불가능하다.

4) 활성화 되지 않은 활성레코드가 상주할 경우가 있어서 효율성이 저하된다.

 

 

 

동적 기억 장소 할당 기법

1) 스택 할당 (for automatic allocation)

2) 힙 할당 (for dynamic allocation)

 

대부분의 컴파일러 언어에서 사용합니다.

(Algol60, Pascal, Algol68, PL/I , Ada, C, C++ , Java 등)

 

인터프리터 언어에서 모두 사용합니다.

(APL, LISP, SNOBOL4, PROLOG, Smalltalk)

 

 

 

Algol 유사 언어

- 블록 개념 도입 (영역 단위)

- 단위 프로그램 : 블록(정상적인 프로그램 실행 과정에서 차례가 되었을때 활성화),

                            부 프로그램(호출문에 의하여 호출되었을 때 활성화)

 

- 기억장소 할당 시 고려 사항

   1) 변수 수명

   2) 단위 프로그램 활성 시간

   3) 참조 환경, 생성에 관한 규칙들

 

- 활성 레코드 크기 바인딩 시간 => 번역 시간, 활성화 시점, 동적 변화

 

 

**활성 레코드 크기는 정적 바인딩이다.

- 매개변수 + 지역 변수 + @

- 지역 변수 생성 : 단위 프로그램 활성화 시점 (automatic)

- 기억 장소의 크기 : 번역 시간에 확정

- 변수 오프셋 : 정적 바인딩

- 활성 레코드 : 매 호출 시마다 할당되며 recursion을 허용한다.

 

준정적 변수 (semi-static)

- 크기 (오프셋) 번역시간 고정으로 하며, 정적 바인딩이다.

- 실행시간에 기억장소가 동적 할당이 된다.

- Pascal(포인터 제외) , C(heap할당 제외)의 활성 레코드 

 

준동적 변수 (semi-dynamic)

- 기억장소 크기 : 활성화 시점 바인딩(동적)

- 실행시간에 기억장소가 동적 할당이 된다.

- 동적 배열

- 사용자에게 유연성을 제공

 

준 동적 변수(동적 배열)의 기억 장소 할당 방식

1) 번역 시간

- 준 동적 변수의 명세표(차원 수 등 정적으로 알려진 정보만 저장 , 크기 고정)를 활성 레코드에 삽입

- 모든 오프셋은 번역시간에 확정되며 상수 취급이 가능하다.

 

2) 실행 시간

- 활성레코드(준 정적 변수, 준 동적 변수 명세표) 기억장소에 할당

- 준 동적 변수 기억장소에 할당

- 준 동적 변수 기억장소 주소를 명세표에 배정하며, 준 동적 변수의 오프셋도 상수화 한다.

 

 

 

단위 activation 구조

코드부(code segment) : 기계어 명령어

활성레코드 : 지역변수, 형식 매개 변수

반환주소 : 반환시 실행 주소, 호출자의 코드

동적 링크 : 반환 주소 , 호출한 단위프로그램의 활성 레코드 주소 , 동적 체인 구성 => 동적 내포 관계 표현

나머지 내용(지역변수, 매개변수, 정적링크)

 

 

유연 배열(flexible array) : 동적 변수

- Algol60, Algol68, Ada 등에서 허용

 

 

동적 변수

- 활성 레코드 크기가 동적 바인딩으로 (실행 시 변화)

- 실행 시 변수 크기가 수시로 변할 수 있다.

- Algol 68, Ada, Fortran 90 , C, C++, Java 등에서 제공

- 힙 동적 배열, 유연성 배열

- new : Pascal, C++ , Ada, Algol68, Java 등

- malloc : C

- 프로그램 실행 중에 생성 / 해제 가능

 

스택 변수 : 준 정적, 준 동적 변수

힙 변수 : 동적 변수 (PL/I의 controlled, based / Pascal의 pointer / Algol68과 Ada의 access)

 

 

비 지역 변수의 참조

- 다른 활성 레코드의 변수 참조

지역변수는 지역 환경에

비지역 변수는 비지역 환경에

 

ex) Fortran : 지역 변수는 현재 단위프로그램 활성 레코드 / 전역 변수는 시스템 제공 활성 레코드

      ALGOL 유사 언어 : 지역 변수는 현재 단위 프로그램 활성 레코드 / 비 지역 변수는 정적 내포 관계

 

(1) 정적 체인(Static Chain)

- 단위 프로그램의 정적 내포 관계

- 비 지역 변수 검색 방법

- 정적 체인을 따라 탐색하면 실행시간이 낭비되는 단점이 있다.

- 간격(distance) 사용 : 정적 내포 구조의 단계수를 의미한다.

-> 변수 주소 (d,o) d : distance / o: offset    (간격 만큼 정적 링크 추적하므로 간격이 클 때는 실행 시간이 낭비된다.)

 

(2) 디스플레이

- 정적 체인 관계를 가변 배열 형태로 표현

- (d,o)개념을 사용

- 유효주소(d, o) = DISPLAY(m-d) + o

- m: DISPLAY 사용 활성 레코드 수 , d: 간격 , o : 오프셋

 

장점 : 모든 비지역 변수 참조시간이 동일하다

단점 : 활성 레코드의 발생 소멸시, 디스플레이 내용이 변환된다.

 

 

정적 영역 규칙 : 번역 기법

동적 영역 규칙 : 인터프리터 기법

 

APL : 비지역 변수를 동적 링크를 이용한다.

APL 변수의 자료형과 크기는 실행 중 수시로 변화하기 때문에 스택 기반 할당이 불가능하다.

실제 자료 값은 힙 기억 장소에 할당 후 포인터로 연결한다.