Dynamic Memory Allocation : Basic Concepts

Dynamic Memory Allocation

프로그래머들은 dynamic memory allocator을 사용해 run time 동안 사용될 가상메모리를 얻을 수 있습니다.

dynamic memory allocator은 heap이라고 불리는 가상메모리를 관리합니다.

 

allocator는 vairable한 size인 block을 allocated 또는 free한 상태로 heap을 관리합니다.

allocator는 두가지 type이 존재합니다.

• Explicit allocator

malloc이나 free를 통해 개발자가 직접 heap 메모리를 관리해 줍니다. c언어가 대표적입니다.

• Implicit allocator

malloc 같은 메모리 할당은 하지만 free는 자동적으로 해줍니다. free는 자동적으로 해주기 때문입니다.

JAVA, ML, Lisp 같은 경우입니다.

 

The 'malloc' Package

#include <stdlib.h>

void *malloc(size_t size)

성공 : 최소 size byte를 가리키는 메모리 pointer를 return 합니다. 

32 bit(8 byte) 또는 64 bit(16 byte) 를 할당합니다.

만약 size가 0이면 NULL을 return합니다. 

 

실패 : NULL을 return하고 errno을 셋팅합니다. (heap의 메모리 공간이 없을 경우)

 

void free(void *p)

pointer p를 가리키는 메모리 block을 free합니다.

p는 malloc이나 realloc을 통해 생성된 pointer입니다.

 

calloc는 malloc + malloc으로 할당된 메모리 공간 0으로 초기화

realloc은 이전에 할당된 block의 size를 바꿉니다.

sbrk는 allocator을 사용해 heap의 brk를 줄이거나 늘립니다.

 

malloc example

 

메모리는 block 단위로 할당이 됩니다.

 

allocation example

 

Constraints (제한 사항)

allocator는 할당된 block의 size를 control할 수 없습니다.

allocator는 malloc 요청에 즉각 반응해야 합니다. 

allocator는 free된 메모리로 부터 block을 할당합니다.

allocator는 모든 정렬 요구사항을 충족하도록 block을 정렬해야합니다.

allocator는 free된 메모리를 다룰 수 있습니다.

이미 malloc된 block은 움직일 수 없습니다.

 

Performance Goal : Throughput

5000개의 mallco 요청과 5000개의 free요청을 10초안에 처리한다고 하면

Throughput은 초당 1000개의 operation을 처리하게 됩니다.

즉 throughput을 빠르게 하는 것이 목표입니다.

 

Performance Goal : Peak Memory Utilization 

Aggregate payload (Pk)

malloc(p)를 실행하면 p byte를 지니고 있는 block을 할당받습니다.

block의 크기는 p보다 크거나 같습니다.

aggregate payload(Pk)는 k번 malloc과 free를 하는 동안 지금까지 얼마나 payload(실제 data를 요청한 크기)의

누적합을 의미합니다.

 

Current heap size (Hk)

말 그대로 k번 malloc과 free를 진행하고 현재 brk가 가리키고 있는 heap의 크기입니다.

heap은 오직 allocator가 sbrk를 사용할 때만 늘어납니다.

 

Peak memory utilization

가상메모리 공간은 무한하지 않으므로 공간을 효율적으로 사용해야합니다.

만약 메모리 공간이 over되면 disk로 넘어가 data의 접근이 오래걸리게 됩니다.

메모리 공간을 효율적으로 사용하게 되려면 사용하지 않은 메모리를 최대한 줄여야 합니다.

 

그렇게 되면 throughput과 peak memory utilization의 충돌이 발생하게 됩니다.

 

Fragmentation

나쁜 메모리 효율성은 fragmentation에 의해 발생합니다.

 

Internal Fragmentation

예를 들어 malloc을 통해 10 byte를 요청했지만 block의 크기는 16byte이므로 6 byte가 낭비됩니다.

 

원인

heap의 자료구조를 유지하는 Overhead

blcok을 정렬하는데 문제가 발생

작은 payload를 유지하는데 큰 block이 사용

 

하지만 이러한 internal fragmentation은 개선이 쉽습니다.

 

Extrenal Fragmentation

위를 보시면 heap의 크기가 여유가 있음에도 불구하고 malloc(6)를 할 수 없는 상황입니다.

이러한 경우 internal fragmentation과는 다르게 다루기 어렵습니다.

 

Implementation Issues

1. free(ptr)을 할 경우 ptr이 가리키는 메모리의 크기를 어떻게 알고 free를 할 수 있는가?

2. 어떻게 heap 메모리 구조에서 free인 부분만 찾아서 malloc을 수행하는가?

3. 할당된 block 보다 작은 payload에서 남는 메모리 공간으로 무엇을 할까?

4. heap 메모리 구조에서 여러 free block중 어떤것을 allocate할까?

5. 어떻게 free된 block을 다시 삽입할까?

 

Knowing How Much to Free

보통 free를 할 때 얼마나 free를 해야하는 가에 대한 문제는

기본 방법으로 첫번째 block 칸에 할당된 크기를 적어줌으로써 free할 때 그 크기를 일고 free 합니다.

malloc(4)를 하면 첫번째 block에 할당된 크기를 적고 payload는 4 block의 크기를 가져갑니다.

따라서 총 5 block을 가져갑니다.

 

Keeping Track of Free Blocks

free된 block만 찾는 방법입니다.

 

Method 1 : Implicit list

free된 block만 찾기 위해서는 이미 allocate 된 block을 볼 필요가없다.

하지만 계속 탐색해야하기 때문에 속도가 느려집니다.

 

Method 2 : Explicit list

맨 앞 block에는 할당된 크기를 나타내고 두 번째 block에는 free된 block의 위치를 나타냄으로써

free된 block만 탐색할 수 있습니다. 

하지만 공간비용이 떨어질 수 있습니다.

 

Method 3 : Segregated free list

서로 비슷한 size의 free된 block을 class 별로 묶어서 정렬합니다.

malloc의 요청된 크기에 따라 class에 접근해 할당합니다.

 

Method 4 : Blocks sorted by size

free된 block을 blanced-tree 형태(ex : Red-Black tree) 로 관리하면서 

tree를 탐색하면서 malloc된 크기에 알맞는 block을 찾습니다.

 

Method 1 : Implicit List

할당된 block 마다 block이 free인지 allocate인지 상태와 block의 size가 필요합니다.

이러한 두가지 정보를 저장하기 위해 2 word를 사용하는 것은 매우 비효율적 입니다.

이를 1 word를 사용해 저장하면 더 효율적입니다.

예를 들어 word = 4 byte라고 하면 

block이 늘어날 수 록 4 byte만큼 늘어가게 됩니다.

size에 대한 정보를 저장하므로 

4 =   0100

8 =   1000

16 = 10000

위와 같이 됩니다. 그런데 결국 마지막 LSB는 무조건 0이 됩니다. 이러한 0을 Free인지 Allocate인지 flag로

사용하면 효율적입니다. free이면 0, allocate이면 1로 flag를 사용하면 됩니다.

예를 들어 malloc(5)를 하게 되면 총 2 block을 할당받게 됩니다.(8 byte)

장점은 간단하다는 것입니다.

단점은 free된 block만을 탐색하는 것이 아닌 allocate된 block도 탐색하므로 시간이 오래걸립니다.

 

Implicit List : Finding a Free Block

First fit

처음부터 요청한 크기의 free block을 찾습니다. 제일 처음으로 찾은 block을 return합니다.

선형시간이 걸리고 다시 요청이 들어와도 처음부터 탐색합니다.

while 문이 참이면 알맞는 free인 block을 못찾은 상태이므로 계속 반복해줍니다.

*p & 1 는 LSB를 확인해 free인지 allocate인지 확인합니다.

*p <= len 은 size의 크기가 원하는 크기 len보다 작거나 같으면 할당할 수 없습니다.

 

p = p + (*p & -2) 는 다시 p의 LSB를 초기화 해주고 p에 써있는 size만큼 다음 block으로 넘어가는 것입니다.

여기서 -2를 &해주는 것은 -2가 11111..110이기 때문에 p의 size만 가져올 수 있습니다. (LSB는 flag)

 

Next fit

이전에 free된 block을 찾았으면 그 위치부터 다시 free된 부분을 찾는것입니다.

하지만 firtst fit 방법보다 항상 빠른것은 아닙니다. 

이미 이전에 찾았던 block이 free되면 그것은 탐색할 수 없기 때문입니다.

 

Best fit

내가 요청받은 크기의 가장 가까운 free 공간을 찾는 것입니다.

공간 효율성은 제일 좋지만 항상 탐색할 때마다 처음부터 탐색하므로 느립니다.

 

Implicit List : Allocating in Free Block

free된 공간이 요청받은 크기보다 작으면 free된 공간을 요청받은 크기만큼 잘라서 나눠야 합니다.

예를 들어 free공간이 6이고 요청받은 크기가 4이면 6을 4와 2로 나눠야 합니다.

먼저 할당되는 크기인 newsize는 짝수가 되게 round up해줍니다. (ex : 4 -> 4, 5 -> 6)

block은 항상 짝수이기 때문입니다. (4 byte, 8 byte)

현재 p의 위치에서 free한 전체공간을 읽어줍ㄴ디ㅏ. *p & -2는 정확히 size만 읽어 줍니다.

이제 할당할 크기에 flag를 1로 바꿔줘야 하기 때문에  *p = newsize | 1을 해줍니다.

이때 newsize가 oldsize보다 작으면 당연히 split을 해줘야 하기 때문에

현재 위치(p)에서 새로 할당할 크기(newsize) 만큼 이동한곳에 split한 크기가 들어갑니다.

이미 oldsize와 newsize는 LSB가 0이므로 그냥 빼기만 해주면 알아서 flag 처리됩니다.

 

Implicit List : Freeing a Block

void free_block(ptr p){
	*p = *p & -2;
}

free는 단순히 p를 인자로 받아 LSB인 flag만 0으로 바꿔주면 됩니다.

하지만 이러한 경우 예를 들어 malloc(5)를 할 경우 할당 할 수 있는 공간이 있음에도 불구하고

공간이 split되 있기 때문에 할 수 없게 됩니다.

따라서 split한 공간을 다시 합쳐줘야 합니다.

 

Implicit List : Coalescing

free를 하고 다음 block이 또 free면 서로 합쳐주는 작업입니다.

먼저 인자로 받은 포인터 p를 & -2를 해주어 flag를 0으로 표시해줍니다. (free)

p에 써있는 size만큼 이동해 next에 할당해줍니다.

현재 next는 위의 그림에서 보면 2를 가리키고 있습니다.

if((*next & 1) == 0) 는 next가 가리키고 있는 value의 LSB가 free인지 allocate인지 확인합니다.

next는 현재 size가 2이고 free이므로 if문 안으로 들어갑니다.

따라서 free인 공간을 합쳐줍니다. *p = *p + *next = 6이 됩니다.

 

하지만 이러한 방법은 항상 p의 다음 block만 확인할 수 있습니다.

p의 바로 뒤에 있는 block이 free인지 allocate인지는 확인할 수 없습니다.

 

Implicit List : Bidirectional Coalescing

block의 맨 앞에는 block의 size를 가리키는 header가 있습니다. 이를 그대로 복사해 block의 

맨 끝에 붙이는 방법입니다.

Boundary tags혹은 footer라고 부릅니다. 

이를 통해 free를 할 때 p는 바로 뒤에 있는 block을 보고 앞에 있는 block이 free인지 allocate인지

알 수 있습니다.

하지만 할당된 block에 header와 footer를 모두 표시하려니 그만큼 공간의 효율성이 떨어질 수 있습니다.

우리가 free할 공간이 노란색이라고 하면 다음 4가지 경우의 수가 가능합니다.

 

Case 1

1번째 경우 입니다.

free할 공간 앞뒤 모두 allocate이므로 그냥 단순히 자기 자신만 free해주면 됩니다.

 

Case 2

free할 공간 뒤에 있는 block이 free한 형태입니다. 

마찬가지로 뒤에 있는 block를 합쳐주면 됩니다.

 

Case 3

case 2와 반대로 free할 block 앞에 있는 것이 free한 경우 입니다.

 

Case 4

free할 공간 앞뒤가 모두 free한 경우 입니다. 

 

Disadvantages of Boundary Tags

단점 : header과 footer를 표시해주기 위해 메모리를 사용하므로 메모리 오버헤드가 발생할 수 있습니다.

 

우리는 생각해보면 block이 allocate상태이면 굳이 footer가 필요없다는 것을 알 수 있습니다.

앞에서 header의 표시를 살펴보면 LSB는 해당 block이 free인지 allocate인지 확인하는 flag를 나타내고

나머지 bit들은 size를 나타냅니다. 

우리는 flag를 포함해 총 3개의 bit가 unused하다는 것을 알 수 있습니다.

이를 이용해 앞에 있던 block이 free인지 allocate인지 확인할 수 있을 것입니다.