CSAPP : 동적 메모리 할당 (9.9)

9.9 동적 메모리 할당

 

동적 메모리 할당기(Allocator)

: 힙(heap)이라고 하는 프로세스의 가상 메모리를 관리한다.

❖ Explicit Allocator(명시적 할당기)

- application이 명시적으로 할당된 블록을 반환해 줄 것을 요구

- C의 <stdlib.h>의 malloc 패키지라고 하는 Explicit Allocator 할당기를 제공 (malloc : 할당, free : 반환)

❖ Implicit Allocator(묵시적 할당기)(=Garbage Collection)

- 할당된 블록이 더 이상 프로그램에 의해 사용되지 않고 블록을 언제 반환하는지를 할당기가 검출할 수 있을 것을 요구

- garbage collection : 자동으로 사용하지 않은 할당된 블록을 반환

 

9.9.1 malloc과 free함수

 

#include <stdlib.h>

// 메모리 할당
// returns: pointer to allocated block if OK, NULL on error
void *malloc(size_t size); 

// 메모리 할당 후 각 요소의 모든 비트를 0으로 초기화
// returns: malloc과 동일
void *calloc(size_t num, size_t size);

// 이미 할당된 블록의 크기를 변환
// returns: pointer to allocated block if OK, 
//          NULL on size가 0 and 확장하기 위한 충분한 기억장치가 없는 경우 (원래 블록이 변경되지 않음)
void *realloc(void *ptr, size_t size);

//메모리 반환

#include <stdlib.h>

void free(void *ptr);

#include <unistd.h>

// 커널의 brk포인터에 incr을 더해서 합을 늘리거나 줄임
// returns: 성공한다면 brk 값을 리턴하고, 아니면 -1를 리턴하고 errno를 ENOMEM으로 설정
void *sbrk(intptr_t incr);

9.9.2 왜 동적 메모리 할당인가?

 

가장 중요한 이유

-  프로그램을 실제 실행시키기 전에 자료 구조의 크기를 알 수 없는 경우들이 있기 때문에

 

해결 방법

 1) 들어올 수 있는 입력의 최대 크기의 정적 배열로 구성(설정한 최대크기로 부족하면 수정해서 다시 컴파일)

 2) 필요한 크기를 알고 있을 때 런타임에 동적으로 할당(가용한 가상 메모리 양에 의해서만 제한)

 

9.9.3 할당기의 요구사항과 목표

 

명시적 할당기(Explicit Allocator)들은 다소 엄격한 제한 사항 내에서 동작해야 한다.

1) 임의의 요청 순서 처리하기

2) 요청에 즉시 응답하기

3) 힙만 사용하기

4) 블록 정렬하기

5) 할당된 블록을 수정하지 않기

 

명시적 할당기의 목표

1) 처리량 극대화 하기

2) 메모리 이용도를 최대화 하기

- 최고 이용도(peak utilization)를 최대화하는 것

Uk : 이용도

maxPi : 실제로 사용하는 힙의 크기

Hk : 할당된 힙의 크기 

쉽게 말하면, 현재 할당된 것을 얼마나 쓰고 있냐를 나타낸 지표

 

9.9.4 Fragmentation(단편화)

 

가용 메모리가 할당 요청을 만족시킬 수 없을 때, 일어난다.

 

❖ Internal Fragmentation(내부 단편화)

- 필요한 메모리 이상의 메모리를 할당해서 할당된 메모리에게 비어있는 메모리가 발생

 

❖ External Fragmentation(외부 단편화)

- 할당 요청을 만족시킬 수 있는 전체적으로 공간을 모았을 때는 충분한 크기가 존재하지만, 이 요청을 처리할 수 있는 단일한 가용 블록은 없는 경우

- 미래의 메모리 수요와 관련되기 때문에 측정하기 어려움

--> 할당기들은 대개 더 작은 가용 블록들 보다는 더 적은 수의 더 큰 가용 블록들을 유지하는 방법들을 채택

 

9.9.5 구현 이슈

처리량과 이용도 사이에 좋은 균형을 갖는 실용적인 할당기가 고려할 이슈

1) 가용 블록 지속적 추적 --> 가용 블록 구성 

2) 새롭게 할당된 블록을 배치하기 위한 가용 블록 선택 방법 --> 배치

3) 새롭게 할당된 블록을 가용 블록에 배치한 후, 나머지 부분 무엇으로 채우는지 --> 분할

4) 방금 반환된 블록으로 무엇을 할 것 인지? --> 연결

 

9.9.6 묵시적 가용 리스트

- 각 블록마다 블록 사이즈와 할당 여부를 각각 저장하려면 2 Word가 필요 --> 낭비

- 더블 워드 정렬 제한 조건을 부과한다면 8byte의 배수 숫자 사이즈를 가지기 때문에 블록이 할당되면 하위 3비트가 항상 0이다.

 -> 따라서 이 자리를 블록의 할당 여부를 저장하는 flag로 사용 (할당 : 1, 반환 : 0)

 -> size word를 읽을 때 이 비트를 마스크해서 가져옴

* 최소 블록 크기 : 할당되거나 반환된 블록 모두 최소 블록 크기보다 더 작을 수 없다.

 

리스트의 탐색을 종료하는 데에 쓰일 크기가 0으로 할당된 블록을 마지막 블록으로 둠

 

Prologue 블록

- header와 footer로만 구성된 8바이트 할당 블록 (header와 footer는 뒤에 나옴)

- 초기화 과정에서 생성되며 절대 반환될 수 없음.

- Prologue 블록 다음에는 malloc 또는 free를 호출해서 생성된 0 또는 1개 이상의 일반 블록들이 온다.

Epilogue 블록

- 힙은 항상 끝날 때, Epilogue 블록으로 끝나며, 이것은 헤더만으로 구성된 크기가 0으로 할당된 블록

 

9.9.7 할당한 블록의 배치

Application이 k바이트의 블록을 요청할 때, 할당기는 요청한 블록을 저장하기에 충분히 큰 가용 블록을 리스트에서 검색

 

1) First fit

- list를 앞부터 탐색해서 처음 만나는 가용 블록을 선택

 

2) Next fit

- 이전에 검색이 종료된 지점에서 검색을 시작

 

3) Best fit

- 모든 가용 블록을 검색하고 가능한 블록의 크기 중에 가장 작은 크기의 블록을 선택

- 앞의 두 방식보다 더 좋은 메모리 이용도를 가짐

- 단점 : 힙을 완전히 다 검색해야함

* 힙을 모두 검색하지 않은 Best-fit -> segregated free list

 

9.9.8 가용 블록의 분할

 

할당기가 크기가 맞는 가용 블록을 찾은 후에 가용 블록의 어느 정도에 할당할지에 대해 결정을 내려야함

 

1) 찾은 가용 블록 전체를 사용

- 단점 : Internal Fragmentation(내부 단편화) 생김

 

2) 첫 번째 블록에 할당하고 나머지는 새로운 가용 블록으로 둠

- 단점 : External Fragmentation(외부 단편화) 생김

        --> 인접한 가용 블록이 False Fragmentation(오류 단편화) 현상을 유발

               인접 가용 블록들의 Coalescing(연결)이 필요

 

9.9.9 추가적인 힙 메모리 획득하기

할당기가 요청하는 크기의 블록을 찾을 수 없는 경우

1) 인접한 가용 블록을 연결해서 더 큰 가용 블록으로 만든 후 할당

2) 연결해도 블록 크기가 충분하지 않은 경우에 할당기는 sbrk 함수 호출해서 추가적인 힙 메모리를 요청해 추가 메모리를 한 개의 더 큰 가용 블록으로 변환해 할당

 

9.9.10 가용 블록 연결하기

❖ Coalescing(연결)

블록을 반환할 때, 그 다음 블록이 가용 블록이면 앞의 가용 블록의 크기를 늘림

 

- Immediately Coalescing(즉시 연결)

: Free가 불리면 즉시 실행

 

- Deferred Coalescing(지연 연결)

: Free의 퍼포먼스를 증진시키기  위해 연결이 필요한 시점까지 연결을 지연

  malloc을 하기 위해 free list를 탐색할 때, 연결

  External Fragmentation(외부 단편화)가 어떤 경계점에 도달하면 연결

 

❖ Coalescing Free Blocks : Thrashing <->  False Fragmentation 

Immediately Coalescing(즉시 연결) : 다 합쳐 놓았는데 다시 작은 공간의 요청이 들어와서 다시 나눠야한다면 Thrashing

Deferred Coalescing(지연 연결) : 쪼개진 공간 때문에 할당 불가라 False Fragmentation

 

적절한 타이밍에 Coalesce 함수를 사용해 free 블록을 합친다.

 

9.9.11 경계 태그로 연결하기

 

Boundary tags(Footer)

헤더 정보로 반환하는 블록의 다음 가용 블록과 연결하는 것은 간단 --> 이전의 블록과 연결하는 것은 ?

--> 헤더를 복사한 정보를 Footer로 블록의 끝에 추가

--> 모든 블록에 Header와 Footer를 추가한다면 경우에 따라 메모리의 반이 그 정보를 저장하는데 쓰이게 될 수도 있음

경계 태그의 최적화

--> 현재 블록 기준으로 이전 블록이 free인 경우에만 이전 블록의 footer에 있는 size 필드가 필요하다. 이전 블록이 free가 아닌 경우 footer가 필요 없음(footer가 없다면 allocated 된 것)

--> 할당된(가용하지 않은) 블록과는 연결할 필요가 없으므로 Footer가 없어도 된다.

 

출처 :

https://velog.io/@crystalhwang16/week06-malloc-lab-%EC%9A%94%EA%B5%AC%EC%82%AC%ED%95%AD%EA%B3%BC-%EB%AA%A9%ED%91%9C

https://fixed-juniper-93d.notion.site/4e5248a0c1cd4af29a15260090b59a75#953fb872520b41698f7447172b009384