[PLT/프로그래밍언어론] 05. Memory Management

Memory Management

인터프리터의 주요 기능. 프로그램이 실행되는 동안 다양한 정보(지역변수, 임시값..)가 생성/로드/저장
PL에서는 메모리 접근 처리 방법을 결정해야 한다.

Subprogram(a.k.a procedure, routine, function)

함수, 루틴, 프로시저 다 같은 의미로 사용하겠다. 이론적으로는 반환 값이 있는 것을 subprogram이라고 함.

Stack

데이터를 쌓는 자료구조. LIFO 구조. 데이터 push/pop

Stack and Procedure

스택은 프로시저에 적합하다. 프로시저 또한 LIFO 구조로 호출/종료되기 때문. Env도 이 방식으로 처리 가능

Heap(자료구조 아님)

힙은 pq나 힙 정렬과 관련된 자료구조이지만, PL에서는 프로그램이 allocated 될 수 있는 특정 메모리 공간

Static Management

• 프로그램 실행 전에 compiler에 의해 performed된다.
• Statically allocate objects는 고정된 메모리 영역에 위치하고, 프로그램 실행 동안 그자리에 머무름.

Which can be allocated statically?

• Global Variable: 프로그램 전체에서 사용 가능.
• Object Code: 컴파일러에 의해 생성된 machine instruction
• Constants: 컴파일 시점에서 그 값이 결정될 수 있을 때만
• Compiler-generated Tables: 런타임중 프로그램의 support를 위해 사용됨.

Without Recursion(재귀가 없는 경우)

재귀가 없으면 두 개 이상의 프로시저가 동시에 활성화될 수 없음 -> PL의 다른 components를 정적으로 처리
ex) local variable(동일한 지역 변수는 스택에서 한 번만 나타남), argument, 임시 값, r.v, return address…

Dynamic Management

Static Management 만으론 충분하지 않다. 런타임 이전에 모든 component를 결정할 수 없음.
스택과 힙을 사용해서 Dynamic memory management를 할 수 있다.

Dynamic Management - Stack

• procedure activation or inline block에 할당된 각 메모리 공간을 activation record or _frame_이라 한다.
  • activation : 프로시저나 인라인 블록을 실행하는 것
• activation records를 담고 있는 스택을 runtime stack이라고 한다.

Activation Record

Inline block의 activation records는 procecure activation records의 부분집합. 빨간색이 공통인 것들.
(적어도 빨간색은 외워둬야 하지 않을까)

Activation Record - Dynamic Link

• activation record에는 local variable이랑 intermediate result가 들어간다.
• Dynamic Link는 스택에서 이전 activation record의 시작부분을 가리킨다.
  • activation record 크기가 각각 다르기 때문에 필요함
• 시작부분부터 특정 local variable을 찾으려고 local offset을 사용할 수 있다.

Activation Record - 나머지

• Return Address : 프로시저 호출이 끝난 후 실행될 다음 명령어 주소
• Address for Return Value : Return value는 caller의 frame에 저장된다
  • a가 b를 호출한다면, 리턴 값이 저장될 주소를 b에게 알려주고, a에 리턴 값이 저장된다.
• Parameter : Caller 로 부터 전달된 값

Stack Management

A(caller)와 B(callee)는 runtime stack에서 Activation Record를 저장/삭제한다.

• Activation Record Pointer: frame pointer 또는 _current environment pointer_라고 불림
• Stack Top Pointer: 스택에서 “free space”의 시작 지점을 가리킨다.

Procedure Call

• Calling Sequence는 컴파일러에 의해 프로시저 호출 직전과 직후(immdediately before and after)에 삽입된다.
• Prologue와 Epilogue는 프로시저 실행 전 후(before and after)에 삽입된다.
• 위에서 말한 3가지의 코드 fragment는 컴파일러와 implementation마다 다르다.
• 코드 크기의 최적화를 위해서 callee에게 대부분 코드가 할당된다.
  • calling sequence는 컴파일 시간에 여러 번 추가되지만, Prologue, Epilogue는 definition할 때 한 번만 삽입되므로, call마다 여러 번 추가할 필요가 없다.

Tasks before Procedure Call : Calling sequence & Prologue

• Program Counter Modification
• Stack Space Allocation
• Activation Record Pointer Modification
• Parameter Passing
• Register Save
• Initialize Code Execution

Tasks after Procedure Call : Epilogue & Calling sequence

• Update Program Counter
• Value Return
• Return of Registers
• Finalize Code Execution
• Stack Space Deallocation

Heap - Dynamic Management

스택 말고도 힙이 필요하다. 일부 PL이 explicit memory allocation을 허용하는 stataement 때문

Explicit Memory Allocation

explicit memory allocation에는 LIFO가 적용되지 않는다.
위 예시만 봐도 p가 먼저 할당되고 먼저 해제됨. 스택이라면 p를 q보다 먼저 해제할 수 없음.

Heap Management

Heap management method는 memory block을 다루는 방법에 따라 두 가지로 나뉜다.

• Fixed Length Blocks
• Variable Length Blocks

Heap Management - Fixed Length Block

• Heap을 여러 개의 fixed length blocks으로 나눈다.
• free block list을 관리하기 위해 free list를 사용한다.
• request마다 first free block이 할당되고, 할당된 block은 free list에서 제거된다.
• free list의 pointer는 리스트에 있는 first block을 가리킨다.

• 블록이 해제되면 블록이 다시 free list에 추가됩니다.
• request를 충족하기 위해 여러 블럭이 할당될 수 있다.
  • ex) 만약 한 칸이 4KB이고, 15KB만큼 요청이 오면 16KB를 할당해야 한다

Heap Management - Variable Length Blocks

n > k 이고 n < m이라서, third free block에 할당된다.
애도 free list를 사용하지만, block의 크기가 다를 수 있다. 요청된 크기에 맞는 block을 할당해준다.

Variable Length Blocks -> Fragmentation

• 가변 길이 -> fragmentation을 유발할 수 있다.
• fragmentation 때문에 메모리 공간이 낭비될 수 있고, 프로그램 성능도 저하될 수 있다.

Internal Fragmentation

m > n이면, d = m - n 만큼 낭비된다.
할당된 블록 크기가 요청된 크기보다 큰 경우, 공간이 남아서 낭비된다.

 

External Fragmentation

m + k > n 이지만 consecutive(연속적)이지 않아 할당을 못하고 있다.
free block들이 흩어져 있어 요청된 메모리를 할당할 수 없는 경우를 말한다.

결론: fragmentation은 heap managemet method을 고려할 때 중요한 요소이다.

Solution1: Using Single Free List

크기 n의 메모리 할당 요청이 있을 때, free list를 직접 사용하자.

• First Fit: 크기 n보다 큰 첫 번째 블록을 할당
• Best Fit: 크기 n 이상이며, 가장 작은 차이(d=k-n)를 가진 블록을 할당
  • Internal Fragmentation 최소화하는데 사용되는 방법
• Free Memory Compaction(압축): 힙의 끝에 도달하면 모든 activation block을 힙의 끝으로 이동
  • 여전히 할당한 공간이 없다면, 런타임 에러가 발생한다(힙 공간 부족)
  • External Fragment을 해결하기 위한 방법

Solution2: Multiple Free Lists : Buddy System

• 2의 제곱 크기에 해당하는 free list 여러 개를 사용한다.
• 크기가 n인 요청이 오면, 먼저 2^k >= n인 블록을 2^k free list에서 찾는다.
  • 만약 available block이 없으면 2^(k+1) free list에서 찾는다.
• 2^(k+1) free list에서 찾으면 그 블럭을 두 개의 2^k로 split한다.
  • 2^k 하나는 할당되고, 나머지 하나는 2^k free list에 연결된다
• 할당된 block이 해제되면, 분할된 buddy를 찾아서 결합 -> 2^(k+1) free list에 attach 된다
  • Fibonacci Heap : 2^n 단위 사이즈 대신 피보나치 수열의 수를 block size로 사용

Scope Rule Implementation

Static Scope Rule Implementation

주의 ) A: B:는 프로시저가 아님!

• Static Scope Rule 구현은 스택 사용보다 많은 관리가 필요하다
• ex) 프로시저 foo에서 변수 x는 블록 B의 x를 참조하지만(선언 기준), dynamic link로 foo에 연결된 activation record는 블록 C입니다. (실행 기준이니까)
• block을 즉시 둘러싼 block에 대한 link가 필요하다. (선언 기준인 정적 스코프를 위해서)
  -> static link를 사용해서 둘러싼 block의 activation record를 가리킨다.
• static scope를 관리할 때는 dynamic link 대신 static link를 사용한다.

Static scope - static link - 선언 기준 : 값을 가져올 때 선언 기준
Dynamic scope - 값을 가져올 때 call stack 기준

Dynamic link - Stack, Heap - 실행 기준

Static Link

• Activation record가 stack에 추가될 때, static link의 주소를 결정해야 한다(내부에 포함되어 있으니)
  • 즉 static link로 어떤 활성화 레코드를 가리켜야 할 지 정해야 한다.
• 일반적으로는 caller가 link를 계산해서 callee에게 전달한다.
• 두 가지 케이스로 나뉜다.

Static Link Example: Case1 - Callee가 Caller 외부에 있을 때

Block B랑 C는 Block A 내부에서 선언되어 있다. D와 E는 C 내부에 있다.
A->B->C->D->E->C 순으로 호출한다고 해보자.

 

예시: E가 C를 호출하지만, C는 E의 외부에 있다

• callee(C)는 visibility rule에 따라 caller(E)의 block 외부에 있어야 한다.
  • callee(C)의 activation record는 이미 stack에 있다.
• C가 E랑 static link를 맺는게 아니라, C의 direct outside block인 A와 Static Link를 한다.
• static link를 backtrace하여 new block을 위한 new link를 찾을 수 있다.

결론 : Callee가 Caller 외부에 있으면 Callee는 direct outside block(선언기준)과 static link를 한다.

Static Link Example: Case2 - Callee가 Caller 내부에 있을 때

예시: C가 D를 호출하는데, D는 C 내부에 있다

• visibility rule에 따라 callee가 caller 블럭 내부에 선언되어 있다.
• 따라서 단순하게 Static link를 caller에게 해주면 된다.

Display

• Static Link는 프로시저 호출마다 여러 번 메모리 접근을 해야 한다.
• non-local이 k개 블록 떨어져있으면 static link를 k번 따라가야 한다.
• 보통은 중첩이 많지 않아 큰 문제가 발생하지는 않지만 Display를 쓰면 constant memory accesses (twice)만 필요하다

• Display라고 불리는 벡터를 사용하는 방법이다.
• Display의 k번째 요소는 k번째 중첩 레벨의 현재 activation record pointer를 담고 있다.
• non-local name이 레벨 n에서 선언된 경우에 Display n번째 element로 가서 offset을 이용해 name을 찾는다.
• 프로시저가 k 레벨에서 호출되면, Display의 k번째 요소는 callee의 activation record pointer로 업데이트 한다.
  (참고로 Static Link의 레벨을 다루는 거니까 호출 기준이 아니라 선언 기준임.)

• 만약 같은 레벨에서 프로시저가 호출된다면, 디스플레이의 이전 값을 저장해야 합니다.
• 블록 C가 2레벨에서 호출되었으므로, 블록 B의 이전 포인터는 C에서 B로 연결된 링크로 저장됩니다.
  • 기존에 있는 것을 새로 들어온 얘가 가리킨다.
• C가 스택에서 빠져나간 후 이 값을 복원할 수 있습니다. 
  • C가 스택에서 나갈 때 C가 가리키는 걸 다시 Display에 넣어준다.
    
    • callee(블록 D)가 caller(블록 C) 내부에 있을 경우(= 레벨이 증가하는 경우), 디스플레이의 길이를 늘려 다음 요소(3번째 요소)에 포인터를 넣는다.

• 블록 E가 호출되면, 디스플레이 3번째 요소의 이전 값이 저장됩니다. (같은 레벨이니까)
• 그런 다음 Display 3에서 블록 E에 대한 포인터가 업데이트됩니다.
• 변수 x가 블록 C에서 선언되고, 블록 E에서 사용된다고 가정해봅시다.
  • 컴파일 시점에 우리는 x가 C에 선언된 것을 알고 있습니다(Static Scope를 통해서).
  • 블록 C는 2레벨에 있으므로 디스플레이의 2번째 요소를 확인하고, 로컬 오프셋을 사용해 x의 바인딩을 찾을 수 있습니다.

• 블록 E에서 블록 C가 호출된다. (더 낮은 레벨이 호출되는 경우)

• 블록 E에서 선언된 로컬 이름을 블록 C에서는 사용할 수 없다.
• 이거를 Display로 어떻게 구현할까?
• 일단 Display의 level2가 새로 호출된 C 활성화 레코드를 가리키도록 한다. 그리고 기존에 있던 C를 새로운 C가 가리킨다.
• level2 이후 요소(level3, …)들은 비활성화된다.

Dynamic Scope Rule Implementation

• Dynamic scope에서 non-local은 활성화된 순서대로 고려된다.
  • 따라서 스택을 backward하여 적절한 바인딩을 찾아야 합니다. (call stack)
• A, B, C, D 호출을 생각해봅시다. 회색으로 표시된 것은 deactivated된 바인딩을 나타낸다.

Association List

• Activation Record에 직접 바인딩을 저장하는 대신, 바인딩을 Association list(A-list)에 별도로 저장할 수 있습니다.
• 프로그램이 새로운 env에 진입하면, 바인딩이 A-list에 삽입되고, env에서 벗어날 때 제거됩니다.
  C end -> x:B

• 두 가지 단점

1. Name을 런타임 중 structures(구조체)에 저장해야 합니다.
2. Name의 위치를 compile time에 추적할 수 없습니다.

• 런타임에 이름을 검색하는 것은 inefficient일 수 있다. 리스트 전체를 확인해야 할 수도 있다.

Central Referencing Table를 쓰자

Central Referencing Table

이러한 단점을 해결하기 위해 Central Referencing Table, CRT을 사용한다.

• 프로그램에서 사용된 모든 name이 CRT에 저장됩니다.
• 각 name에는 activate 또는 inactivate를 나타내는 flag가 있습니다.
• name의 유효한 바인딩은 스택에 쌓여 있으며, 비활성화된 바인딩은 그 아래에 있습니다.

(왼쪽이랑 오른쪽이랑 다른 예시임)  
위를 개선한게 아래. 변수마다 스택 대신 하나의 hidden stack을 사용한다

• inactivate 바인딩은 hidden stack에 저장되며, 다시 activated될 때 복원된다.
• 세 번째 열은 이름에 해당하는 실제 denotable object 대한 참조를 담고 있다.

A열고 B열고 B닫고 C열고 D열고 D닫고 C닫고 A를 닫는 구조

• Enter
  • env에 있는 변수들이 활성화되어있으면 스택에 이름과 실제 denotable object 참조를 push한다.
  • 그게 아니면 flag 1로 바꿔주고 Reference를 넣어준다.
• Exit
  • 나가는 env의 변수 중에서 만약 스택에 존재하는게 있다면 스택에 있는 걸로 원복해준다.
    • a,b,c로 넣었다면 스택에는 top부터 c,b,a로 있으므로, c,b,a 순으로 검사해야 함.
  • 스택에 없다면 flag를 0으로 바꿔준다.

---