Chapter 9 – 기억 장소 배당 Outline 9.1 정적 및 동적 기억 장소 배당 9.2 단위 프로그램

Presentation on theme: "Chapter 9 – 기억 장소 배당 Outline 9.1 정적 및 동적 기억 장소 배당 9.2 단위 프로그램"— Presentation transcript:

1 Chapter 9 – 기억 장소 배당 Outline 9.1 정적 및 동적 기억 장소 배당 9.2 단위 프로그램
9.1 정적 및 동적 기억 장소 배당 9.2 단위 프로그램 9.3 정적 기억 장소 배당 9.4 스택 기반 기억 장소 배당 9.5 힙 기억 장소 배당

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

3 9.1 정적 및 동적 기억 장소 배당 정적 기억 장소 할당 동적 기억 장소 할당 번역 시간 할당 (적재 시간)
기억장소 크기와 위치가 정적으로 고정 배열 접근코드가 효율적 (크기 고정) 기본조건 사용된 모든 배열은 확정된 고정 크기로 선언 부프로그램은 되부름(recursion) 불가 Fortran, Cobol, Basic 등에서 사용 동적 기억 장소 할당 실행 시간 할당 변수 제한 완화 (자료형, 크기 등) 인터프리터 언어 - LISP, SNOBOL4, APL Algol 형태 언어 - recursion 허용

4 9.1 정적 및 동적 기억 장소 배당 ALGOL PL/I C, C++, (Java?)
정적, 동적 기억 장소 할당을 함께 수행하는 언어 예 ALGOL own 변수 : 정적 할당 own 이외의 변수 : 동적 할당 (recursion 허용) 변수 크기가 실행 시, 할당 후 고정(stack based) PL/I STATIC : 정적 할당 AUTOMATIC : 동적 할당 (스택 기반) CONTROLLED, BASED : 동적 할당 (힙 기억 장소 할당) C, C++, (Java?) static : 정적 할당 auto : 동적 할당 (스택 기반), default임 힙 기억장소 할당 – C(malloc,free), C++(new, delete),Java(new)

5 9.2 단위 프로그램 모듈 (module) [단위 프로그램 (program unit)]
새로운 환경 설정(new environment) 선언가능 - 지역 식별자 도입 지역 변수 (local variable) 단위 프로그램에서 선언하여 사용하는 변수 활성화 상태(activated state) 한 단위 프로그램의 실행 시작부터 종료까지 블록도 단위 프로그램 임

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

7 9.2 단위 프로그램 오프셋(Offset) 참조 환경(referencing environment) 활성 레코드 바인딩
활성레코드에서의 상대위치 참조 시 주소 대신 사용 참조 환경(referencing environment) 단위 프로그램의 지역 변수 및 사용 가능한 비 지역변수 지역변수 : 현 단위 프로그램 활성 레코드에 할당 비지역 변수 : 다른 단위 프로그램 활성 레코드에 할당 활성 레코드 바인딩 코드부와 활성 레코드의 바인딩 재귀 호출(되부름) : 활성레코드 재귀적으로 발생 => 동적 바인딩 재귀 호출 불허용 : 활성 레코드 하나만 존재 => 정적 바인딩 가능

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

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

10 장점 단점 9.3 정적 기억 장소 할당 구현용이, 간결함 효율적인 프로그램 실행 유연성(flexibility) 적음
배열 크기 불변 recursion 불가 활성화되지 않은 활성레코드 상주 (오류 처리 루틴 등) 정적 변수(static variable) 번역 시간에 크기 고정( 크기- 정적 바인딩) 번역 시간 할당( 정적 할당)

11 9.4 스택 기반 기억 장소 할당 동적 기억 장소 할당 기법 스택 할당( for automatic allocation)
힙 할당(for dynamic alloc) 대부분의 컴파일러언어에서 사용 (블록 중심 언어) Algol 60, Pascal, Algol 68, PL/I, Ada, C, C++, Java등 인터프리터 언어 모두 사용 APL, Lisp, SNOBOL4, PROLOG, Smalltalk

12 9.4 스택 기반 기억 장소 할당 ALGOL 유사 언어(Algol-like language)
블록 개념을 도입(영역 단위) - 선언으로 새로운 환경 정의 단위 프로그램 : 블록, 부 프로그램 블록 : 정상적인 프로그램 실행 과정에서 차례가 되었을 때 활성화 부프로그램 :호출문에 의하여 호출되었을 때 활성화 기억장소 할당 시 고려 사항 변수수명 단위 프로그램 활성시간 참조 환경, 생성에 관한 규칙들 활성 레코드 크기 바인딩시간 - 번역 시간, 활성화 시점, 동적변화

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

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

15 9.4 스택 기반 기억 장소 할당 단위 엑티베이션 구조 활성레코드 크기 : 정적 바인딩 활성 레코드 코드부
(code segment) 반환 주소 나머지 내용 활성 레코드 (지역변수, 매개변수, 정적링크등) 동적 링크 활성레코드 크기 : 정적 바인딩 단위 엑티베이션 구조 코드부 : 기계어 명령어 활성 레코드 지역 변수, 형식 매개 변수 정적 링크 동적 링크 동적링크 반환주소 호출한 단위프로그램의 활성 레코드 주소 동적 체인 구성 => 동적 내포관계 표현 반환 시 실행 주소 호출자의 코드

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

17 미사용 FREE CURRENT 그림 9.5 실행 중 스택에서 활성 레코드들의 동적 링크 관계 활성 레코드 (현재 실행중인
동적 체인 CURRENT FREE (현재 실행중인 활성 레코드) 스택이 증가 하는 방향 활성 레코드

18 • 현재 호출된 상태 A →E →F →G →F →G →F CURRENT F 의 활성 레코드 G E A 스택이 증가하는 방향
동적 링크 •

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

20 9.4 스택 기반 기억 장소 할당 준동적 변수(semidynamic variable) 사용 예 (Ada)
준동적 변수( 동적 배열) 선언 예 get (M, N) declare A : array(1..N) of INTEGER; B : array(1..M) of FLOAT; begin … end

21 ① 활성레코드(준정적변수, 준동적 변수 명세표) 기억장소 할당
9.4 스택 기반 기억 장소 할당(6) 준 동적 변수(동적 배열)의 기억 장소 할당 방식 1) 번역시간 ① 준동적 변수의 명세표 활성레코드에 삽입 모든 오프셋 : 상수 취급 가능(번역 시간) 참고) 명세표 차원수 등 정적으로 알려진 정보만 저장 명세표 크기 고정 2) 실행시간 ① 활성레코드(준정적변수, 준동적 변수 명세표) 기억장소 할당 ② 준동적 변수 기억장소 할당(확정시) ③ 준동적 변수 기억장소 주소를 명세표에 배정 준동적 변수의 오프셋도 상수화

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

23 9.4 스택 기반 기억 장소 할당 활성레코드 크기 : 동적 바인딩 (실행 시 변화) 동적(dynamic) 변수
프로그램 실행 중에자료가 생성되고 회수되어 활성 레코드의 크기가 변하는 경우 동적(dynamic) 변수 실행 시 변수 크기가 수시로 변할 수 있는 변수 예) Algol68, Ada, Fortran90, C, C++, Java등에서 제공 힙 동적 배열 (heap dynamic array) 유연성 배열 (flexible array) 프로그램이 실행 중에 할당되는 자료들에 맞추어서 크기를 조절할 수 있는 배열 예) 프로그램에서 변수 생성 시점을 정해주는 변수들 new – Pascal, C++, Ada, Algol68, Java 등 malloc - C

24 9.4 스택 기반 기억 장소 할당 활성레코드 크기 : 동적 바인딩 (실행 시 변화) 동적 변수 특성
프로그램 실행 중에 생성/해제 가능 => 동적 변수 생성 프로그램 종료 후에도 기억장소 유지 => 스택의 활성레코드에 할당 불가 => 힙(heap) 기억장소에 할당 명세표는 스택의 활성 레코드에 할당 스택 변수 : 준정적, 준동적 변수 힙 변수 : 동적변수 예) PL/I(controlled, based), Pascal(pointer), Algol68, Ada(access)

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

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

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

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

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

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

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

32 9.4 스택 기반 기억 장소 할당(12) 비지역 변수의 참조 방법 (2) 디스플레이 정적 체인 관계를 가변배열 형태로 표현
(d, o) 개념 사용 유효주소(d, o) = DISPLAY(m-d) + o m : DISPLAY 사용 활성레코드 수 d : 간격, o : 오프셋 장단점 모든 비지역 변수 참조시간 동일 활성레코드의 발생, 소멸 시 디스플레이 내용 변환 1 3 m DISPLAY current 2 ...

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

34 9.5 힙 기억 장소 할당(Heap Storage Allocation)
영역 규칙 1) 정적 영역 규칙 - 번역기법에서 사용 2) 동적 영역 규칙 - 인터프리터 기법에서 사용 동적 기억 장소 할당 => 힙기법 이용 APL 예 주프로그램의 변수 => 전역변수 인터프리터 언어 동적영역 규칙 사용 주프로그램 Z ←0 X ←5 Y ←7 SUB 2 Z ←FUN Y 부프로그램 ▽ SUB 1 : Y SUB ...X... ...Y... Z ← FUN 1 ... ▽ 함수 ▽ R ← FUN N:X FUN 호출순서 1) 주프로그램 →SUB →FUN Y는 SUB의 변수 2) 주프로그램 →FUN Y는 주프로그램의 변수

35 9.5 힙 기억 장소 할당 프로그램에서 실행 순간의 스택 APL - 비 지역변수 : 동적 링크 이용
스택기반 할당 불가 실제 자료값 : 힙 기억장소 할당 후 포인터로 연결

36 Heap 그림 9.14 한 실행 순간의 실행 스택 X N R Y I Z FUN 의 활성 레코드 SUB 주프로그램의 스택이
증가하는 방향 CURRENT 주프로그램 Z ←0 X ←5 Y ←7 SUB 2 Z ←FUN Y 부프로그램 ▽ SUB 1 : Y SUB ...X... ...Y... Z ← FUN 1 ... ▽ 함수 ▽ R ← FUN N:X FUN 그림 9.14 한 실행 순간의 실행 스택

37 슬라이드 쇼가 끝났습니다.

38 용 어 정리

39 모듈 (module) 용어 국제 표준 규격 15.06.01 module 모듈 program unit 단위 프로그램
A part of a program developed to be discrete or identifiable with respect to actions such as compilation, binding, or execution, and that may interact with other programs or parts of programs. <NOTE> The concept referred to by the term "module" may vary according to the different programming languages. 컴파일, 바인딩, 또는 실행과 같은 행위와 관련해서 분리되거나 식별이 가능하도록 개발된 프로그램의 일부분으로서 다른 프로그램이나 그 프로그램의 부분과 상호작용할 수 있다. <주> 모듈”이라는 용어로 언급된 개념은 다양한 프로그래밍 언어들에 따라 차이가 있을 수 있다.