Dynamic Memory Allocation
프로그래머들은 일반적으로 런타임에 추가적인 가상 메모리를 획득해야 할 때 Dynamic Memory Allocator를 사용 하는 것이 더 편리하다고 생각한다.
Dynamic Memory Allocator(mallc)는 Heap이라는 가상 메모리 영역을 관리한다. 세부 정보는 시스템마다 다르지만 일반성의 손실 없이 Heap은 초기화되지 않은 Data 영역 전후에서 시작되어 위로 확장되는 demand-zero memory라고 가정한다. 각 프로세스에 대해 Kernel은 Heap의 상단을 가리키는 변수 brk("break")를 유지한다.
Allocator는 Heap을 다양한 크기의 Block들의 모음으로 유지한다. 각 Blcok은 할당되거나 사용 가능한 가상 메모리의 연속적인 Chunk이다. 할당 된 Block이 프로그램에서 사용하도록 명시적으로 예약되어있다. Free Block은 사용 가능한 Block이다. 사용 가능한 Block은 응용 프로그램에 의해 명시적으로 할당될 때까지 사용 가능한 상태로 유지된다. 할당된 Block은 프로그램에 의해 명시적으로 또는 Memory Allocator 자체에 의해 암묵적으로 해제될 때까지 할당된 상태로 유지된다.
sbkr 명령어를 통해서 brk 포인터를 증가시킬 수 있다. => Heap 메모리 크기가 커진다.
- Allocator는 두 가지 기본 스타일로 제공된다.
- 두 스타일 모두 프로그램에서 Block을 명시적으로 할당해야 한다.
- 할당된 Block을 해제하는 Entitiy에 대해서 서로 다르다.
Explicit allocator
- 프로그램이 명시적으로 Block을 할당하고 Free하도록 한다.
ex) malloc, free, new, delete
Implicit allocator
- 할당된 Block이 프로그램에 의해 더 이상 사용되지 않을 때를 감지하고 Block을 해제한다.
- Garbage Collector라고도 하며, 사용되지 않은 할당된 Block을 자동으로 해제하는 프로세스를 Grabage Collection이라고 한다.
ex) Lisp, ML 및 Java
The malloc Pcakage
#include <stdlib.h>
void *malloc(size_t size)- 메모리 할당 성공
- 메모리의 시작 주소 (가상 메모리 주소) 반환
- 메모리 할당 실패
- 할당 할 공간이 없을 때
- NULL을 반환하고 errno을 set 한다.
void free(void *p)- 사용 가능한 메모리 풀에서 가리키는 block을 반환
- calloc: Version of malloc that initializes allocated block to zero.
- realloc: Changes the size of a previously allocated block.
- sbrk: Used internally by allocators to grow or shrink the heap
malloc Example
#include <stdio.h>
#include <stdlib.h>
void foo(int n) {
int i, *p;
/* Allocate a block of n ints */
p = (int *)malloc(n * sizeof(int));
if (p == NULL) {
perror("malloc");
exit(0);
}
/* Initialize allocated block */
for (i = 0; i < n; i++)
p[i] = i;
/* Return allocated block to the heap */
free(p);
}Assumption
- 메모리는 워드 단위로 저장되는 것을 가정한다.
- 워드는 정수단위 크기이다.
Allocation Example
Constraints
- Applications
- malloc 및 free 요청의 임의의 Sequence를 실행할 수 있다.
- free는 malloc된 block에 요청되어야 한다.
- Aloocators
- 할당된 block의 크기의 수를 바꿀 수 없다.
- malloc 요청하면 즉시 응답해야 한다.
reorder, buffer 요청되면 안 된다. - free된 메모리에서부터 할당되어야 한다.
- alignment를 만족해야 한다.
- 오직 free 메모리만 조작하고 수정할 수 있다.
- malloc되면 움직일 수 없다.
Performance Goal
malloc, free 요청의 Sequence가 주어진다고 가정한다.
- 목표: 처리량 및 최대 memory 활용률 극대화
Throughput
- request per unit time에 완료된 수
- ex) 5,000 malloc과 5,000 free 가 10초 내에 처리됨
=> Throughput은 1,000 operations/second
Peak Memory Utilization
- 1. Aggregate payload Pk
- malloc(p) p byte 만큼의 payload를 갖는 block을 할당받는다.
payload: 실제 요청한 데이터가 저장되는 크기
ex) 10바이트를 요청하면 block은 alignment에 의해 16바이트 할당받는다. - k번째까지 malloc이 성공한다면, aggregate payload는 현재 할당된 payload의 합이다.
- malloc(p) p byte 만큼의 payload를 갖는 block을 할당받는다.
- 2. Current Heap size Hk
- k번째까지 malloc했을 때 Heap의 크기. Pk 시점의 Hk
- Heap 공간이 부족하면 brk를 증가시킨다.
- 실제 물리 메모리는 가상 메모리보다 작을 수 있다.
ex) 가상 메모리가 4GB라면, 프로그래머 관점에서 프로세스를 어드레싱할 수 있다고 생각하지만, 실제 물리 메모리는 1GB밖에 안된다. 그다음 1GB까지 가상 메모리를 사용하여 메모리를 할당하게 되면 OS의 가상 메모리 시스템에 의해서 Paging에 의해서 가상 메모리는 1GB에 매핑하고 물리 메모리를 넘어서면 나머지 3GB는 디스크의 일부 영역을 Swap Space를 잡아서 매핑한다. 그러다 보면 어떤 가상 메모리 Page는 물리 메모리에 매핑되어 있을 수도 있고, 디스크에 있는 Swap Space에 매핑되어 있을 수 있다. 이 예가 의미하는 바는 가상 메모리는 무한대로 큰 것처럼 보이지만, 어느 일정 크기를 넘어가게 되면 물리적인 메모리가 아닌 디스크 공간에 매핑되는 경우가 생긴다. 디스크 공간에 접근할 때 Disk Swap을 해야 하는데 이 Swap 할 때 Memory Access가 매우 느려진다. 이러한 관점에서 보면 Heap 공간을 최대한 활용해서 Utilization을 높이는 것이 좋다. 가급적 물리 메모리에 Peak 할 수 있을 정도로 쓸 수 있고 넘어가는 확률을 최대한 줄일 수 있다. - 3. Peak Memory Utilization after k + 1 requests
- Uk = (max(i <=k) Pi) / Hk
- brk를 움직이지 않고 현재 Heap 공간을 최대한 사용할 수 있게 하는 것이 좋다.
Throughput을 높이려 하면 Utilization이 떨어지고 그 반대도 마찬가지 현상이 일어난다.
적정하게 조절해서 만들어야 한다.
Fragmentation
Fragmentation에 의해서 Memory Utilization이 떨어진다.
- internal fragmentation
- external fragmentation
Internal Fragmentation
Block을 할당받았을 때 payload가 할당받은 Block Size보다 작으면 Internal Fragmentation이 발생한다.
- Caused by
- Heap 자료 구조의 Overhead
구현에 따라 줄일 수 있다. Utilization을 높이기 위해 매우 중요하다. - Alignment를 위해 Padding 발생
- Explicit policy decision
작은 크기를 만족하기 위해 큰 block을 반환하는 경우
- Heap 자료 구조의 Overhead
Internal Fragmentation은 이전의 어떤 Request가 왔는지 Pattern에 따라서 생길 수 있다.
External Fragmentation
충분한 Aggregate Heap Memory가 있지만 할당할 만큼 큰 Block이 남아있지 않을 때 발생한다.
External Fragmentation은 다음 request에 따라 발생하므로 예측하기 어렵다.
Implementation Issues
- Pointer만 있으면 얼마나 많은 메모리를 Free 해야 하는지 어떻게 알 수 있을까?
- Free Block을 어떻게 추적할 수 있을까?
- Free Block보다 더 작은 구조를 할당할 때 Extra Space를 어떻게 해야 할까?
- 할당에 사용할 Block을 어떻게 선택할까?
- Free 된 Block을 어떻게 Heap에 다시 넣을까?
Knowking How Much To Free
- 가장 일반적인 방법
- block 가장 앞의 word에 Block의 길이를 유지한다.
- Block의 길이를 유지하는 가장 앞에 있는 word를 header field, header라고 부른다.
- 모든 할당된 blcok에 여분의 word가 필요하다.
- block 가장 앞의 word에 Block의 길이를 유지한다.
Keeping Track of Free Blocks
- Implicit list: Block의 크기를 이용하여 모든 Block을 Link
- 단점: 모든 Block을 연결하고 있기 때문에 이미 할당된 Block까지 확인해야 하는 Overhead
- Explicit list: Block에 다음 free block을 가리키는 Pointer(Word Address)를 저장한다.
- 장점: 바로 free block으로 이동할 수 있다.
- 단점: free blcok을 가리키는 extra memory가 필요하다. -> 공간 효율이 떨어진다.
- Segregated free list: 크기가 다른 클래스에 서로 다른 free list를 저장한다.
- Blocks sorted by size: 각 free block 내에 Pointer가 있는 Balanced tree와 Key로 길이를 사용한다.
Implicit List
- 각 Block은 크기와 Allocation 상태를 가지고 있어야 한다.
- 2 word로 저장하는 것은 비효율적이다.
- 방법
- Block이 alignment 되어 있으면 몇 하위 bit들은 0이다.
- 0으로 된 부분을 Allocated/free flag로 사용한다.
- 크기를 저장하는 word를 읽을 때 bit는 mask 한다.
Detailed Implicit Free List Example
- 장점
- 단순하다.
- 단점
- free block을 찾기 위해 처음부터 탐색해야 하기 때문에 시간적인 Overhead가 있다.
Implicit List: Finding a Free Block
Free Block 찾는 방법
First fit
- 처음부터 탐색을 시작하며, 탐색하면서 첫 free block을 선택한다.
p = start;
while ((p < end) && \\ not passed end
((*p & 1) || \\ already allocated
(*p <= len))) \\ too small
p = p + (*p & -2); \\ goto next block (word addressed)- 전체 blcok(allocated, free)을 탐색하는 데 linear time이 걸릴 수 있다.
- 실제로는 list의 시작 부분에 'splinter'가 발생할 수 있다.
- 항상 list의 가장 앞에서 시작하기 때문에 느리다.
Next fit
- First fit과 비슷하지만, 이전에 탐색했던 부분부터 탐색을 시작한다.
- 앞에서부터 시작하지 않기 때문에, 일반적으로 First fit보다 빠르다.
- 그렇지 않을 경우는 이미 할당한 공간들이 free 되었다면 앞에서부터 찾는 게 빠를 수 있다.
- 그래서 어떤 탐색은 Fragmentation이 더 안 좋을 수 있다.
Best fit
- 공간적으로 가장 Memory 효율을 높이기 위한 방법.
- 처음부터 찾되, 요구하는 Memory를 가장 근접하게, Internal Fragmentation이 최소화되는 Block을 찾는 방법.
- leftover되는 byte가 적은 block을 찾는다.
- fragmentation을 최소화하여 Memory 효율을 높인다.
- 처음부터 끝까지 탐색한다. -> 대부분 first fit보다 느리다.
Implicit List: Allocating in Free Block
Splitting
- 할당된 공간이 사용 가능한 공간보다 작을 수 있으므로 Block을 분할한다.
void addblock(ptr p, int len) {
int newsize = ((len + 1) >> 1) << 1; // round up to even
int oldsize = *p & -2; // mask out low bit
*p = newsize | 1; // set new length
if (newsize < oldsize)
*(p+newsize) = oldsize - newsize; // set length in remaining
}Implicit List: Freeing a Block
구현 방법은 'allocated' flag를 clear 하면 된다.
void free_block(ptr p) { *p = *p & -2 }clear는 제대로 되지만, 'false fragmentation' 문제가 발생할 수 있다.
free를 실행하면 Block이 4개, 2개로 나뉘어있다.
5 Block을 할당하려 하면 연속적으로 5개 이상인 free block이 없기 때문에 할당할 수 없다.
이것을 false segmentation이라고 한다.
free space가 있음에도 allocater가 free space를 제대로 찾을 수 없다.
이 문제를 해결하기 위해 Coalescing를 사용한다.
Implicit List: Coalescing
free 할 때 앞, 뒤에 있는 Block이 Free Block이면 두 Block을 붙여준다.
뒤에 있는 Block과 Coalescing
void free_block(ptr p) {
*p = *p & -2; // clear allocated flag
next = p + *p; // find next block
if ((*next & 1) == 0)
*p = *p + *next; // add to this block if
} // not allocated앞의 Block과 어떻게 Join 할까?
Implicit List: Bidirectional Coalescing
- Boundary tags
- 사용 가능한 Block의 "Bottom"(끝)에 Size/allocated flagg word를 복사
- list의 뒤로도 traverse 할 수 있게 하지만, extra space가 필요하다.
-> payload의 크기는 줄어든다.
Constant Time Coalescing
Disadvantages of Boundary Tags
- Internal fragmentation
Can it be optimized?
- free 할 때 관심 있는 것은 이전 Block이 Free인지 Allocated인지 여부이다.
- 만약 Allocated라고 하면 합칠 필요가 없기 때문에 footer가 필요 없다.
Summary of Key Allocator Policies
- Placement policy:
- First-fit, Next-fit, Best-fit, etc...
- Throughput이 커지면 Fragmentation이 커진다. 반대도 마찬가지다. Trade off가 있다.
- segregated free list는 Best-fit과 비슷하지만 전체 list를 탐색할 필요 없다.
- Splitting policy:
- 언제 Free Block을 Split 해야 할까?
- 얼마나 많은 Internal Fragmentation을 납득할 수 있는가?
- Coalescing policy:
- Immediate coalescing: free가 호출될 때마다 coalesce.
- Deferred coalescing: 필요할 때까지 coalescing을 지연시킴으로써 free의 성능을 향상한다.
- malloc을 호출하여 free list를 탐색할 때 coalescing
- External Fragmentation의 양이 특점 Threshold에 도달하면 coalescing
Implicit Lists: Summary
- 구현: 매우 단순함.
- Allocate cost:
- worst case에 linear time
- Memory usage:
- placement policy에 따라 다르다.
- First-fit, Next-fit, Best-fit
- linear-time에 할당되기 때문에 실제로 쓰이지 않는다.
- 특별한 목적이 있는 프로그램에서 사용된다.
- Splitting과 Boundary tag coalescing은 모든 Allocator에 일반적인 개념이다.
Explicit List
공간적인 비용은 Implicit free list가 더 좋다.
그러나, allocated block을 skip 하여 탐색하기 때문에 Implicit free list보다 빠르다.
- free block만 관리한다.
- 다음 free block이 어디에 있든 바로 탐색할 수 있다.
- 여전히 coalescing 하기 위한 Boundary tag가 필요하다.
- free block만 탐색하는 장점이 있지만, pointer를 만들기 위한 payload 영역을 사용해야 하는 단점이 있다.
Allocating From Explicit Free Lists
free block들이 Double Linked List로 연결되어있다고 가정한다.
두 번째 block에 어떤 block이 allocation 되었다면 split 하고 남은 block에 각 pointer들이 앞 뒤로 연결된다.
Freeing With Explicit Free Lists
Insertion policy: 새로운 free block을 free list의 어디에 넣을 것인가?
- LIFO(last-in-first-out) policy
- free list의 시작하는 곳에 freed block을 삽입한다.
- 장점: 단순하고 Constant time에 실행한다.
- 단점: Address-ordered policy보다 Fragmentation이 많다.
- Address-ordered policy
- free list block이 항상 Address-order로 정렬되도록 free block을 삽입한다.
addr(prev) < addr(curr) < addr(next) - 장점: LIFO보다 Fragmenation이 적다.
- 단점: 탐색해야 한다.
- free list block이 항상 Address-order로 정렬되도록 free block을 삽입한다.
Freeing With a LIFO Policy (Case 1)
앞 뒤로 Allocated 인 경우
Freeing With a LIFO Policy (Case 2)
앞에 free인 경우
Freeing With a LIFO Policy (Case 3)
뒤가 free인 경우
Explicit List Summary
- Implicit List와 비교
- Allocation time은 모든 block 대신 free block의 수의 linear time이다.
- memory가 full일 때 더 빠르다.
- Block을 list 안팎으로 분할해야 하므로 Allocation 및 Free 작업이 약간 더 복잡하다.
- Link를 위한 추가 공간이 필요하다. (각 Block에 2 word 필요)
- Allocation time은 모든 block 대신 free block의 수의 linear time이다.
- fragmentation이 최소화되는 block을 찾으려면 best-fit policy에 따라 처음부터 탐색해야 한다.
=> 처음부터 탐색하기 때문에 fragmentation을 찾는데 비용이 많이 든다.
Segregated free lists
Segregated List (Seglist) Allocators
- Block의 각 Size Class에 자신만의 free list가 있다.
Explicit list는 단일 queue이기 때문에 처음부터 끝까지 탐색해야 best-fit 한, fragmentation을 최소화하는 block을 찾을 수 있었다면, seglist는 크기별로 클래스를 나눴기 때문에 크기에 맞는 class만 찾으면 되기 때문에 fregmenation을 최소화할 수 있다.
Seglist Allocator
- 특정 크기 Class에 대해 각각에 free list 배열을 지정한다.
- 크기 n인 block을 할당하는 방법:
- m > n의 block 크기를 만족하는 free list를 탐색한다.
- block이 있다면 그 block을 split 하고 남은 부분을 적절한 Class로 이동시킨다.
- block이 없다면 다음 Class에서 탐색한다.
- 이 과정을 반복한다.
- block이 없을 경우:
- OS한테 Heap Memory를 늘려달라고 요청한다.
- 새로운 Memory에서 n byte block을 할당한다.
- 남은 free block을 적절한 Class로 이동시킨다.
- m > n의 block 크기를 만족하는 free list를 탐색한다.
- block을 free 하는 방법:
- Coalesce 하고 적절한 Class로 이동시킨다.
- seglist의 장점:
- Higher throughput
- log time for power-of-two size classes
- Better Memory utilization
- First-fit 탐색을 seglist에 해도 best-fit 탐색에 근접하다.
- 극단적인 예: 각 Block에 자신의 크기 Class를 지정하는 것은 best-fit과 같다.
- Higher throughput
