대 구 가 톨 릭 대 학 교 I T 공 학 부
Ⓒ2014 소프트웨어공학연구실
8. 프로그래밍 기억장소 관리
목 차
2
8.1 개요
8.3 동적 기억장소 할당
8.5 힙 기반 기억장소 할당
8.4 스택 기반 기억장소 할당
8.2 정적 기억장소 할당
3
8.1 개요(1)
기억장소 관리 방법
①
시스템이 제어하는 방법 -> 일반적
일반적으로 프로그램 실행에 필요한 기억장소는 시스템에 의해 할당되고 해제됨
②
프로그래머가 제어하는 방법
허용 이유
시스템이 기억 장소를 효과적으로 할당하고 해제하는 시기를 결정하는 것이 매 우 어렵기 때문
프로그래머만이 프로그램의 특정 실행 부분에서 필요한 자료구조와 더 이상 필 요 없게 되어 기억장소를 해제해야만 하는 시기를 정확하게 알 수 있기 때문 ->
기억장소를 효율적으로 사용
문제점 : 기억장소 쓰레기(garbage), 허상참조(dangling reference) 등 발생
프로그래머가 모든 기억 장소 관리를 할 수 없음
임시 기억장소, 서브 프로그램을 위한 데이터 공간, 다른 시스템 데이터
8.2 개요(2)
기억장소 할당(Storage Allocation) 기법
프로그래밍 언어의 일부 특징들과 매우 밀접하게 관련
프로그래밍 언어를 설계하고 구현하고자 할 때, 우선 고려할 사항 중 하 나
예 : 되부름(recursion) 허용, 배열 크기 변화 등
방법 : 기억장소 할당 시기에 따라
정적 기억장소 관리 번역 시간 할당 (적재 시간)
동적 기억장소 관리 실행 시간 할당
스택 기반 기억장소 관리
힙 기반 기억장소 관리
정적 + 동적 기억장소 관리 변수의 종류에 따라 다른 시간에 할당
ALGOL(own 변수 : 정적 할당, own 이외의 변수 : 동적 할당-recursion 허용)
변수 크기가 실행 시간에 할당된 후 고정(스택 기반)
PL/I
STATIC : 정적 할당, AUTOMATIC : 동적 할당 (스택 기반)
CONTROLLED, BASED : 동적 할당 (heap 기억 장소 할당) 4
8.1 개요(3) – 단위 프로그램
단위 프로그램(Program Unit)
컴파일, 바인딩 또는 실행과 같은 행위와 관련해서 분리되거나 식별이 가능하도 록 개발된 프로그램의 일부분
지역변수(local variable) :
단위 프로그램에서 선언하여 사용하는 변수
활성화 상태(activated state) :
한 단위 프로그램의 실행 시작부터 종료까지
단위 활성화(Unit activation)
실행 시간에 한 단위 프로그램이 표현된 상태
1) 코드부(code segment)
프로그램의 명령어들로 구성
고정 크기, 내용 불변
2) 활성 레코드(activation record)
지역변수, 매개변수 등 단위 프로그램 실행에 필요한 정보들
가변적(크기, 내용) 5
코드부 활성레코드
8.1 개요(4) – 단위 프로그램
오프셋(Offset)
활성 레코드에서의 상대 위치
자료 참조 시 주소 대신 사용
(한 단위 활성화의) 참조 환경(referencing environment)
단위 프로그램의 지역 변수 및 사용 가능한 비지역 변수로 구성
지역변수 : 현재 단위 프로그램 활성 레코드에 할당
비지역 변수 : 다른 단위 프로그램 활성 레코드 할당
활성 레코드 바인딩
코드부와 해당 활성 레코드의 바인딩
재귀 호출(recursion) 불허용 언어
활성 레코드가 1개만 존재 => 정적 바인딩
재귀 호출(recursion) 허용 언어
활성레코드가 재귀적으로 발생 => 동적 바인딩
6
8.2 정적 기억장소 관리 (1)
정적 기억장소 할당 : FORTRAN 77
메모리 할당이 적재 시간에 이루어지며 모든 변수들의 위치가 고정
부프로그램은 중첩될 수 없고 재귀 호출도 허용되지 않음
COMMON 문을 이용해서 전역 변수를 선언할 수 있고, 그 외 변수들은 지역 변수
예) 주프로그램과 2개의 부프로그램 A, B로 이루어진 프로그램의 메모리 구조를 나타낸 구조
활성 레코드
지역 변수 : 해당 주프로그램 또는 부프로그램에서 선언된 지역 변수를 의미
매개변수 : 해당 부프로그램의 매개변수를 의미
복귀 주소 : 부프로그램 실행이 종료되고 복귀해야 할 메모리 주소를 의미
함수 값 : 부프로그램이 함수인 경우 함수의 반환 값을 의미
7
8
8.2 정적 기억장소 관리 (2)
FORTRAN 77 program의 실행 상태
전역 변수 (COMMON ) 변수 코드부 1
활성 레코드 1 단위 프로그램 1
코드부 2
활성 레코드 2 단위 프로그램 2
코드부 K
활성 레코드 K 단위 프로그램 K
. . .
. . .
. . .
(주 프로그램)
9
8.2 정적 기억장소 관리 (3)
특징
컴파일 또는 번역시에 기억 장소 할당이 이루어짐
프로그램 실행이 끝날 때까지 유지되며 실행이 끝나면 해제
기억장소 크기와 위치가 정적으로 고정
배열 접근코드가 효율적(크기 고정)
장점
기억 장소 관리 간단, 구현 용이
실행속도의 효율성
단점 : 융통성(flexibility) 적음
모든 프로그램의 활성 레코드 할당 (오류 처리 루틴 등)
활성화되지 않은 활성 레코드도 메모리를 항상 차지함
재귀 호출을 허용하지 않음
배열 크기 불변
대표적 언어 : FORTRAN, COBOL 등
10
8.3 동적 기억장소 관리 (1)
특징
실행 시에 기억장소 할당
변수 제한 완화(자료형, 크기 등)
인터프리터 언어 : LISP, SNOBOL4, APL, …
Algol 계통 언어 : PASCAL, C, Java…
재귀 호출을 지원하기 위하여 스택 기반 할당을 하는 동적 기억장소 관리를 이용
장점
실행에서의 융통성 제공
단점
실행 시 잘못된 기억장소 접근에 의한 오류를 유발할 위험
종류
스택 기반 기억장소 관리 / 힙 기반 기억장소 관리
8.4 스택 기반 (1)
스택 기반 기억장소 관리
부프로그램(단위 프로그램)이 활성화될 때 활성 레코드가 스택에 동적으로 생성되는 언어
대표적 언어 : C, Pascal, Ada 등 (재귀 호출 허용)
C : 부프로그램의 중첩을 허용하지 않음
Pascal, Ada : 부프로그램의 중첩을 허용
스택 기반 구조의 활성 레코드
동적 링크
임의의 활성 레코드를 스택에서 제거할 때, 제거 범위에 대한 정보 필요
호출자의 활성 레코드의 시작부를 가리킴
11
8.4 스택 기반 (2)
예) C 예제
3) p에서 q를 호출하여 q가 활성화되면 스택에 q의 활성 레코드가 생성됨 4) q의 실행 종료 : q의 활성 레코드는 스택에서 삭제됨
5) p의 실행 종료 : p의 활성 레코드가 스택에서 삭제됨
01 void q(void) 02 {
03 ⋮ 04 }
05 void p(void) 06 {
07 q();
08 ⋮ 09 }
10 int main(void) 11 {
12 p();
13 ⋮ 14 }
12
1) 프로그램 실행 : 스택에 main 활성
레코드가 생성됨
2) main에서 p를 호출하여 p가 활성화
되면 스택에 p의 활성 레코드가 생성됨
8.4 스택 기반 기억장소 관리 (3)
단위 활성화 구조 : 코드부 + 활성 레코드
코드부 : 기계어 명령어
활성 레코드
동적링크
호출한 단위프로그램의 활성 레코드 주소
동적 체인 구성 => 동적 내포관계 표현
반환주소(복귀주소)
반환 시 실행 주소 (호출자의 코드부 내)
정적 링크
단위 프로그램의 전형적인 활성화 13
8.4 스택 기반 기억장소 관리 (4)
예) 재귀 호출이 있는 C 예제
14
01 int factorial(int n) 02 {
03 if(n<=1) 04 return 1;
05 else
06 return n*factorial(n-1);
07 }
08 int main(void) 09 {
10 int result;
11 result = factorial(3);
12 return 0;
13 }
프로그램 실행 : 스택에 main 활성 레코드가 생성됨
11행에서 factorial(3)을 호출하면 스택에 factorial 의 활성 레코드가 생성됨
매개변수 n=3, 동적링크는 호출자 의 main 의 활성 레코드를 가리킴
함수의 반환값은 정해지지 않음
8.4 스택 기반 기억장소 관리 (5)
6행에서 factorial(2)를 재귀호출하면, 스택에 또 다른 factorial의 활성 레코 드가 생성됨
매개변수 n=2, 동적 링크는 호출자인 factorial의 활성 레코드를 가리킴
함수의 반환값은 정해지지 않음
6행에서 factorial(1)을 재귀호출하면, 스 택에 또 다른 factorial의 활성 레코드가 생성됨
매개변수 n=1, 동적 링크는 호출자인 factorial의 활성 레코드를 가리킴
함수의 반환값은 정해지지 않음
15
8.4 스택 기반 기억장소 관리 (6)
4행에서 함수의 반환값이 1로 정해지므
로 활성 레코드의 함수 값이 1이 됨 함수값 1을 factorial의 두번째 활성 레 코드로 반환
factorial(1)의 실행이 종료되면 동적 링 크가 가리키는 부분까지 스택에서 삭 제됨
factorial 두번째 활성 레코드의 n인 2 와 반환받은 1을 곱한 2가 함수값이 됨
16
8.4 스택 기반 기억장소 관리 (7)
함수값 2를 factorial의 첫번째 활성 레코드로 반환
factorial(2)의 실행이 종료되면 동적 링크가 가리키는 부분까지 스택 에서 삭제
factorial 첫번째 활성 레코드의 n인 3과 반환받은 2를 곱한 결과인 6 이 함수값
함수값 6을 main의 활성 레코드로 반환
factorial(3)의 실행이 종료되면 동적 링크가 가리키는 부분까지 스택 에서 삭제됨
main 활성 레코드의 지역변수 result가 6이 됨
17
8.4 스택 기반 기억장소 관리 (8)
예) 부프로그램 중첩을 하는 Ada 예제
01 procedure p is 02 x, y: integer;
03 procedure q is 04 x: float;
05 procedure r is 06 begin
07 ⋮ 08 end r;
09 begin 10 s;
11 end q;
12 procedure s is 13 y: float;
14 begin 15 r;
16 end s;
17 begin 18 q;
19 end p;
r이 활성화될 때의 스택 내용
5행~8행: 비지역 변수인 x와 y에 대한 참조가 이루어짐
x는 q에서 선언된 4행의 x가 되고, y는 p에서 선언된 2행의 y가 됨
p가 q를 포함하고, q가 r을 포함 하고 있음
18
8.4 스택 기반 기억장소 관리 (9)
q가 r을 포함 : r 활성 레코드의 정적 링크는 q의 활성 레코드를 가리킴
p가 q를 포함 : q 활성 레코드의 정적 링크는 p의 활성 레코드를 가리킴
p가 s를 포함 : s 활성 레코드의 정적 링크는 p의 활성 레코드를 가리킴
정적 링크의 연결
정적 체인(static chain)
19
20
8.4 스택 기반 기억장소 관리 - 비지역 변수의 참조(10)
비지역 변수의 참조
다른 활성 레코드에 정의된 변수 값 참조
FORTRAN
지역 변수: 현재 단위 프로그램의 활성 레코드
전역 변수: 시스템 제공 활성 레코드
ALGOL 계통 언어
지역 변수: 현재 단위 프로그램의 활성 레코드
비지역 변수: 정적 내포 관계
21
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
<단위 프로그램 구조>
• F의 “y := x”
y : CURRENT + y의 옵셋 (지역변수)
x : E 활성레코드 시작 + x의 옵셋 (비지역변수)
•정적링크
- 단위프로그램 내포구조 표현
• 동적링크
- 단위프로그램 호출 순서 표현
호출순서 : A →E →F →G →F →G →F
<활성레코드 실행 상태>
F 의 활성 레코드
G 의 활성 레코드
F 의 활성 레코드
G 의 활성 레코드
F 의 활성 레코드
E 의 활성 레코드
A 의 활성 레코드
스택이 증가하는 방향 동적 링크
정적링크
CURRENT
F 의 활성 레코드 G 의 활성 레코드 F 의 활성 레코드 G 의 활성 레코드 F 의 활성 레코드 E 의 활성 레코드 A 의 활성 레코드 스택이 증가하는 방향 동적 링크 정적링크 CURRENT F 의 활성 레코드 G 의 활성 레코드 F 의 활성 레코드 G 의 활성 레코드 F 의 활성 레코드 E 의 활성 레코드 A 의 활성 레코드 동적 링크 스택이 증가하는 방향 정적링크 CURRENT
8.4 스택 기반 기억장소 관리 - 비지역 변수의 참조(11)
ALGOL68의 지역/비지역 변수 참조
22
8.4 스택 기반 기억장소 관리 (12)
A 에 대한 활성 레코드
A
F 에 대한 활성 레코드
F 에 대한 활성 레코드 F 에 대한
활성 레코드
E 에 대한 활성 레코드
단위 프로그램 A 단위 프로그램 E 단위 프로그램 F 단위 프로그램 G
시스템으로 반환
G 에 대한 활성 레코드
G 에 대한 활성 레코드 A 코드부
. . . E 호출
. . .
E 코드부 . . . F 호출
. . .
G 코드부 . . . F 호출
. . . F 코드부
. . . G 호출
. . .
• • •
• •
•
•
• •
•
• •
• •
•
AEFGFGF 호출시 의 활성화 상태
23
8.4 스택 기반 기억장소 관리 (13)
비지역 변수의 참조 방법
1) 정적 체인(Static Chain)
정적 체인을 이용하여 다른 활성 레코드에 정의되어 있는 비지역 변수를 찾아서 참조하는 방법
비지역 변수 검색 방법
① 정적 체인을 따라 비지역 변수를 참조하는 방법
단점 : 블록들의 포함관계가 깊어질수록 많은 수의 활성 레코드를 추적 실행시간 낭비
② 간격(distance)을 사용하는 방법
간격 : 정적 내포 구조의 단계 수
D에서의 간격 : 지역변수(D선언)–0, 비지역변수(C선언)–1, 비지역변수(B선언)–2, 비지역변수(A선언)-3
변수 주소 : (distance, offset)
단점 : 간격 만큼 정적 링크를 따라가야 함 간격이 큰 경우 실행시간 낭비 2) 디스플레이(Display)
정적 체인 관계를 가변 배열 형태로 표현하는 방법
정적 링크는 활성화 레코드에 저장되기보다는 디스플레이라고 불리는 하나의 배열에 저장
변수 주소 : (display offset, local offset)
(d, o) 개념 사용
유효주소(d, o) = DISPLAY(m-d) + o m : DISPLAY 사용 활성레코드 수 d : 간격, o : 오프셋
장점 : 모든 비지역 변수들에 대한 참조 시간이 동일
단점 : 활성 레코드의 생성, 소멸할 때마다 디스플레이의 내용을 변경해야 함
1 3 m DISPLAY current
2 ...
24
8.4 스택 기반 기억장소 관리 (14)
ㅈ
8.5 힙 기반 기억장소 관리 (1)
힙 기반 기억장소 할당
APL과 같은 인터프리터 언어
활성 레코드는 스택에 생성하여 동적 링크로 연결
이때 활성 레코드에서 지역 변수와 같은 각 항목은 이름과 포인터로 구성
포인터는 항목의 값을 저장하는 힙 영역을 가리키는 주소임
비지역 변수의 참조
호출 순서에 기반하는 동적 영역 규칙을 따르므로 동적 링크를 따라가며 해당 이름에 대한 선언을 찾음
정적 영역 규칙에 필요한 정적 링크는 불필요하므로 활성 레코드에 정적 링크 항목은 없음
활성 레코드의 크기가 동적 바인딩
활성 레코드 크기 : 동적 바인딩 (실행 시 변화)
프로그램 실행 중에 새로운 자료값이 생성되고 회수되어 활성 레코드의 크기가 변함
25
26
8.5 힙 기반 기억장소 관리 (2)
APL 예
호출순서 : 주프로그램->SUB->FUN
Z ←0 X ←5 Y ←7 SUB 2 Z ←FUN Y ...
▽ SUB I : Y ...
...X...
...Y...
Z ← FUN I
▽
▽ R ← FUN N : X ...
...X...
...Y...
▽
주프로그램
부프로그램 SUB
함수 FUN
Heap X
N R
Y I
Y X Z FUN 의
활성 레코드
SUB 의 활성 레코드
주프로그램의 활성 레코드 CURRENT
한 실행 순간의 실행 스택
