동적 관리
- 정적 관리로는 충분하지 않다.
- 모든 프로그램 구성 요소가 런타임 전에 결정될 수는 없기 때문이다.
- 동적 메모리 관리를 위해 스택과 힙을 사용할 수 있다.
스택을 통한 동적 관리
- 활성화 레코드(activation record)=프레임(Frame) : 활성화된 프로시저(or 인라인 블록)에 할당된 각 메모리 공간
- 활성화 레코드는 컨텍스트 스위칭을 하기 전에 함수 상태를 기록하고 복원하기 위한 것이다.
- 메인 함수를 호출하는 순간 메인 함수의 활성화 레코드가 생성된다.
- 런타임 스택(runtime stack) : 활성화 레코드가 포함된 스택

활성화 레코드에는 무엇이 있을까?
- 인라인 블록의 활성화 레코드는 프로시저에 비해 훨씬 간단하다.
- 대부분 프로시저를 고려한다.
- 인라인 블록의 활성화 레코드에 대한 정보는 프로시저의 활성화 레코드에 있는 정보의 하위 집합
- 빨간색은 인라인 블록 및 프로시저에 일반적이라는 의미이다.
동적 링크(Dynamic Link) |
정적 링크(Static Link) |
리턴 주소(Return Address) |
리턴값 주소(Address for Return Value) |
매개변수(Parameters) |
지역 변수(Local Variables) |
중간 결과(Intermediate Results) |
동적 링크(Dynamic Link)
- 지역 변수와 중간 결과가 포함된 활성화 레코드.
- 동적 링크는 스택에 있는 이전 활성화 레코드의 시작을 가리킨다.
- 일반적으로 활성화 레코드의 크기가 다르기 때문에 이 링크가 필요
- 활성화 기록의 시작부터 로컬 오프셋을 사용하여 특정 로컬 변수를 찾을 수 있다.

기타
- 리턴 주소(Return Address) : 프로시저 호출이 완료된 후 다음 명령
- 리턴값 주소(Address for Return Value) : 반환 값은 호출자(caller)의 프레임에 저장
- 매개변수(Parameters) : 호출자(caller)로부터 전달됨
스택 관리
- 활성화 레코드는 런타임 시 스택에서 저장되거나 제거된다.
- 프로시저 B가 프로시저 A에 의해 호출되면 A(caller)와 B(callee) 모두 스택에서 해당 작업을 관리

- 활성화 레코드 포인터(Activation Record Pointer) : 프레임 포인터 or 현재 환경 포인터
- 스택 탑 포인터(Stack Top Pointer) : "여유 공간"의 시작 위치
프로시저 호출
- 콜링 시퀀스(Calling Sequence) : 컴파일러의 프로시저(caller) 호출 전후에 삽입
- 프롤로그(prologue) : 프로시저(callee) 실행 전에 삽입
- 에필로그(epilogue) : 프로시저(callee) 실행 후에 삽입

- 컴파일러와 구현에 따라 다르다.
- 코드 크기를 최적화하기 위해 해당 코드의 상당 부분이 callee에게 제공
- 정의를 위해 한 번만 삽입되기 때문
- 그렇지 않으면 호출할 때마다 여러 번 추가해야 한다.
프로시저 호출 전 작업
- 콜링 시퀀스와 프롤로그를 호출하여 다음 작업 수행
- 프로그램 카운터 수정
- 스택 공간 할당
- 활성화 레코드 포인터 수정
- 매개변수 전달
- 레지스터 저장
- 코드 실행 초기화
프로시저 호출 후 작업
- 에필로그와 콜링 시퀀스를 호출하여 다음 작업 수행
- 프로그램 카운터 업데이트
- 값 리턴
- 레지스터 리턴
- 코드 실행 마무리
- 스택 공간 할당 해제
힙을 사용한 동적 관리
힙(Heap)
- 메모리 관리를 위해 힙이 필요한 이유는?
- 우리에겐 이미 스택이 있고, 스택을 통한 프로시저의 메모리 관리는 당연해 보인다.
- 그러나 일부 언어에는 명시적인 메모리 할당을 허용하는 명령문이 있다.
명시적 메모리 할당
- 명시적인 메모리 할당을 사용하면 LIFO가 보장되지 않는다.
- 예제에서 포인터 변수 p는 첫 번째로 할당된 변수이고 첫 번째로 할당 해제된 변수이다.
- 스택을 사용하는 경우 q가 맨 위에 있으므로 q보다 먼저 p를 할당 해제할 수 없다.
int *p, *q; // 할당(Alloction) p = malloc(sizeof(int)); q = malloc(sizeof(int)); *p = 1; *q = 2; free(p); // 할당 해제(Deallocation) free(q); |
힙 관리
- 힙 관리 방법은 두 가지가 있다.
- 메모리 블록이 고려되는 방식에 따라
- 고정 길이 블록(Fixed Length Blocks)
- 가변 길이 블록(Variable Length Blocks)
고정 길이 블록(Fixed Length Blocks)
- 힙을 여러 개의 고정 길이 블록으로 나눈다.
- 사용 가능한 블록 목록(list of free blocks)을 유지하기 위해 사용 가능한 목록(free list)을 사용한다.
- 각 요청에 대해 첫 번째 여유 블록(free block)이 할당된다.
- 사용 가능한 목록의 포인터는 목록의 첫 번째 블록을 가리킨다.

- 요청이 있는 경우,
- 첫 번째 블록이 할당
- 블록이 사용 가능 목록(list of free blocks)에서 제거
- 블록이 해제(또는 할당 해제)되면,
- 블록이 사용 가능 목록으로 돌아간다.
- 요청을 충족하기 위해 여러 블록을 할당할 수 있다.
가변 길이 블록(Variable Length Blocks)
- 고정 길이 블록과 유사하게 사용 가능한 블록(available blocks)에 대한 사용 가능한 목록(free list)을 사용한다.
- 블록의 크기는 다를 수 있다.
- n 크기의 메모리를 요청하면 이 크기에 맞는 여유 블록(free block)을 할당한다.

- 예) n > k 및 n < m.
- 세 번째 여유 블록이 할당된다.
조각화(Fragmentation)
- 가변 길이 방식은 조각화를 유발한다.
- 조각화로 인해 메모리 공간이 낭비될 수 있으며, 프로그램 성능이 저하될 수 있다.

- 내부 단편화(Internal Fragmentation)
- 할당된 블록 크기가 요청된 크기보다 크다.
- m > n이면 d = m - n은 낭비된다.

- 외부 단편화(External Fragmentation)
- 충분한 공간이 있지만 흩어져 있는 여유 블록(free block)으로 인해 요청한 메모리를 할당할 수 없다.
- m + k > n이지만 연속적이지 않다.
- 힙 관리 방법에서는 조각화를 고려해야 한다.
단일 사용 가능 목록(Single Free List)
- n 크기의 메모리 할당 요청이 있는 경우,
- 사용 가능한 목록(free list)을 직접 사용
- First Fit : 크기 n보다 큰 첫 번째 블록을 할당
- Best Fit : 최소 d = k – n을 갖는 크기 k >= n 블록을 할당
- 사용가능 메모리 압축
- 힙의 끝에 도달하면 모든 활성화 블록을 끝으로 이동시킨다.
다중 사용 가능 목록(Multiple Free Lists)
- 버디 시스템(Buddy System)
- 크기가 2의 n 제곱(2^n)인 여러 개의 사용 가능 목록(free list)이 있다.
- 크기 n 요청의 경우 2^k >= n 블록의 사용 가능 목록(free list)에서 블록을 찾는다.
- 사용 가능한 블록이 없으면 다음으로 2^(k+1) 사용 가능 목록(free list)을 검색한다.

- 2^(k+1) free list에서 free block이 발견되면,
- 이 블록을 두 개의 2^k 블록으로 분할
- 그 중 하나를 할당하고, 다른 하나를 2^k 사용 가능 목록(free list)에 연결한다.

- 다음에 할당된 블록이 해제되면
- 분할된 친구를 찾아 사용 가능(free)한지 확인
- 이들을 결합하여 2^(k+1) 사용 가능 목록(free list)에 다시 넣는다.

- 피보나치 힙
- 2n개의 사용 가능 목록(free list) 대신에 피보나치 수열(Fib(n) = Fib(n-1) + Fib(n-2))을 사용 가능 목록(free list)의 블록 크기로 사용
'프로그래밍언어론' 카테고리의 다른 글
[프로그래밍언어론] 18. 파이썬으로 CRT 구현 (0) | 2023.10.11 |
---|---|
[프로그래밍언어론] 17. 범위 규칙 구현(Scope Rule Implementation) (0) | 2023.10.11 |
[프로그래밍언어론] 15. 정적 관리(Static Management) (0) | 2023.10.11 |
[프로그래밍언어론] 14. 스택(Stack), 힙(Heap) (0) | 2023.10.11 |
[프로그래밍언어론] 13. 가시성 규칙(Visibility Rules), 범위 규칙(Scope Rules) (0) | 2023.10.10 |
동적 관리
- 정적 관리로는 충분하지 않다.
- 모든 프로그램 구성 요소가 런타임 전에 결정될 수는 없기 때문이다.
- 동적 메모리 관리를 위해 스택과 힙을 사용할 수 있다.
스택을 통한 동적 관리
- 활성화 레코드(activation record)=프레임(Frame) : 활성화된 프로시저(or 인라인 블록)에 할당된 각 메모리 공간
- 활성화 레코드는 컨텍스트 스위칭을 하기 전에 함수 상태를 기록하고 복원하기 위한 것이다.
- 메인 함수를 호출하는 순간 메인 함수의 활성화 레코드가 생성된다.
- 런타임 스택(runtime stack) : 활성화 레코드가 포함된 스택

활성화 레코드에는 무엇이 있을까?
- 인라인 블록의 활성화 레코드는 프로시저에 비해 훨씬 간단하다.
- 대부분 프로시저를 고려한다.
- 인라인 블록의 활성화 레코드에 대한 정보는 프로시저의 활성화 레코드에 있는 정보의 하위 집합
- 빨간색은 인라인 블록 및 프로시저에 일반적이라는 의미이다.
동적 링크(Dynamic Link) |
정적 링크(Static Link) |
리턴 주소(Return Address) |
리턴값 주소(Address for Return Value) |
매개변수(Parameters) |
지역 변수(Local Variables) |
중간 결과(Intermediate Results) |
동적 링크(Dynamic Link)
- 지역 변수와 중간 결과가 포함된 활성화 레코드.
- 동적 링크는 스택에 있는 이전 활성화 레코드의 시작을 가리킨다.
- 일반적으로 활성화 레코드의 크기가 다르기 때문에 이 링크가 필요
- 활성화 기록의 시작부터 로컬 오프셋을 사용하여 특정 로컬 변수를 찾을 수 있다.

기타
- 리턴 주소(Return Address) : 프로시저 호출이 완료된 후 다음 명령
- 리턴값 주소(Address for Return Value) : 반환 값은 호출자(caller)의 프레임에 저장
- 매개변수(Parameters) : 호출자(caller)로부터 전달됨
스택 관리
- 활성화 레코드는 런타임 시 스택에서 저장되거나 제거된다.
- 프로시저 B가 프로시저 A에 의해 호출되면 A(caller)와 B(callee) 모두 스택에서 해당 작업을 관리

- 활성화 레코드 포인터(Activation Record Pointer) : 프레임 포인터 or 현재 환경 포인터
- 스택 탑 포인터(Stack Top Pointer) : "여유 공간"의 시작 위치
프로시저 호출
- 콜링 시퀀스(Calling Sequence) : 컴파일러의 프로시저(caller) 호출 전후에 삽입
- 프롤로그(prologue) : 프로시저(callee) 실행 전에 삽입
- 에필로그(epilogue) : 프로시저(callee) 실행 후에 삽입

- 컴파일러와 구현에 따라 다르다.
- 코드 크기를 최적화하기 위해 해당 코드의 상당 부분이 callee에게 제공
- 정의를 위해 한 번만 삽입되기 때문
- 그렇지 않으면 호출할 때마다 여러 번 추가해야 한다.
프로시저 호출 전 작업
- 콜링 시퀀스와 프롤로그를 호출하여 다음 작업 수행
- 프로그램 카운터 수정
- 스택 공간 할당
- 활성화 레코드 포인터 수정
- 매개변수 전달
- 레지스터 저장
- 코드 실행 초기화
프로시저 호출 후 작업
- 에필로그와 콜링 시퀀스를 호출하여 다음 작업 수행
- 프로그램 카운터 업데이트
- 값 리턴
- 레지스터 리턴
- 코드 실행 마무리
- 스택 공간 할당 해제
힙을 사용한 동적 관리
힙(Heap)
- 메모리 관리를 위해 힙이 필요한 이유는?
- 우리에겐 이미 스택이 있고, 스택을 통한 프로시저의 메모리 관리는 당연해 보인다.
- 그러나 일부 언어에는 명시적인 메모리 할당을 허용하는 명령문이 있다.
명시적 메모리 할당
- 명시적인 메모리 할당을 사용하면 LIFO가 보장되지 않는다.
- 예제에서 포인터 변수 p는 첫 번째로 할당된 변수이고 첫 번째로 할당 해제된 변수이다.
- 스택을 사용하는 경우 q가 맨 위에 있으므로 q보다 먼저 p를 할당 해제할 수 없다.
int *p, *q; // 할당(Alloction) p = malloc(sizeof(int)); q = malloc(sizeof(int)); *p = 1; *q = 2; free(p); // 할당 해제(Deallocation) free(q); |
힙 관리
- 힙 관리 방법은 두 가지가 있다.
- 메모리 블록이 고려되는 방식에 따라
- 고정 길이 블록(Fixed Length Blocks)
- 가변 길이 블록(Variable Length Blocks)
고정 길이 블록(Fixed Length Blocks)
- 힙을 여러 개의 고정 길이 블록으로 나눈다.
- 사용 가능한 블록 목록(list of free blocks)을 유지하기 위해 사용 가능한 목록(free list)을 사용한다.
- 각 요청에 대해 첫 번째 여유 블록(free block)이 할당된다.
- 사용 가능한 목록의 포인터는 목록의 첫 번째 블록을 가리킨다.

- 요청이 있는 경우,
- 첫 번째 블록이 할당
- 블록이 사용 가능 목록(list of free blocks)에서 제거
- 블록이 해제(또는 할당 해제)되면,
- 블록이 사용 가능 목록으로 돌아간다.
- 요청을 충족하기 위해 여러 블록을 할당할 수 있다.
가변 길이 블록(Variable Length Blocks)
- 고정 길이 블록과 유사하게 사용 가능한 블록(available blocks)에 대한 사용 가능한 목록(free list)을 사용한다.
- 블록의 크기는 다를 수 있다.
- n 크기의 메모리를 요청하면 이 크기에 맞는 여유 블록(free block)을 할당한다.

- 예) n > k 및 n < m.
- 세 번째 여유 블록이 할당된다.
조각화(Fragmentation)
- 가변 길이 방식은 조각화를 유발한다.
- 조각화로 인해 메모리 공간이 낭비될 수 있으며, 프로그램 성능이 저하될 수 있다.

- 내부 단편화(Internal Fragmentation)
- 할당된 블록 크기가 요청된 크기보다 크다.
- m > n이면 d = m - n은 낭비된다.

- 외부 단편화(External Fragmentation)
- 충분한 공간이 있지만 흩어져 있는 여유 블록(free block)으로 인해 요청한 메모리를 할당할 수 없다.
- m + k > n이지만 연속적이지 않다.
- 힙 관리 방법에서는 조각화를 고려해야 한다.
단일 사용 가능 목록(Single Free List)
- n 크기의 메모리 할당 요청이 있는 경우,
- 사용 가능한 목록(free list)을 직접 사용
- First Fit : 크기 n보다 큰 첫 번째 블록을 할당
- Best Fit : 최소 d = k – n을 갖는 크기 k >= n 블록을 할당
- 사용가능 메모리 압축
- 힙의 끝에 도달하면 모든 활성화 블록을 끝으로 이동시킨다.
다중 사용 가능 목록(Multiple Free Lists)
- 버디 시스템(Buddy System)
- 크기가 2의 n 제곱(2^n)인 여러 개의 사용 가능 목록(free list)이 있다.
- 크기 n 요청의 경우 2^k >= n 블록의 사용 가능 목록(free list)에서 블록을 찾는다.
- 사용 가능한 블록이 없으면 다음으로 2^(k+1) 사용 가능 목록(free list)을 검색한다.

- 2^(k+1) free list에서 free block이 발견되면,
- 이 블록을 두 개의 2^k 블록으로 분할
- 그 중 하나를 할당하고, 다른 하나를 2^k 사용 가능 목록(free list)에 연결한다.

- 다음에 할당된 블록이 해제되면
- 분할된 친구를 찾아 사용 가능(free)한지 확인
- 이들을 결합하여 2^(k+1) 사용 가능 목록(free list)에 다시 넣는다.

- 피보나치 힙
- 2n개의 사용 가능 목록(free list) 대신에 피보나치 수열(Fib(n) = Fib(n-1) + Fib(n-2))을 사용 가능 목록(free list)의 블록 크기로 사용
'프로그래밍언어론' 카테고리의 다른 글
[프로그래밍언어론] 18. 파이썬으로 CRT 구현 (0) | 2023.10.11 |
---|---|
[프로그래밍언어론] 17. 범위 규칙 구현(Scope Rule Implementation) (0) | 2023.10.11 |
[프로그래밍언어론] 15. 정적 관리(Static Management) (0) | 2023.10.11 |
[프로그래밍언어론] 14. 스택(Stack), 힙(Heap) (0) | 2023.10.11 |
[프로그래밍언어론] 13. 가시성 규칙(Visibility Rules), 범위 규칙(Scope Rules) (0) | 2023.10.10 |