[프로그래밍언어론] 16. 동적 관리(Dynamic Management)

동적 관리

• 정적 관리로는 충분하지 않다.
  
  • 모든 프로그램 구성 요소가 런타임 전에 결정될 수는 없기 때문이다.
• 동적 메모리 관리를 위해 스택과 힙을 사용할 수 있다.

 

---

 

스택을 통한 동적 관리

 

• 활성화 레코드(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)의 블록 크기로 사용