CSAPP 9.9 동적 메모리 할당(808~822) 내용 정리

9.9.0. Intro

0-1. 동적 메모리 할당기와 'Heap'

• 동적 메모리 할당기는 Heap이라는 가상메모리 영역을 다양한 크기의 블록들의 집합으로 관리한다.
• 블록은 할당된 블록과 가용 블록(free block)으로 나뉜다.
• 동적 메모리 할당기는 명시적 할당기와 묵시적 할당기로 나뉜다.
• 명시적 할당기의 대표적인 예는 C의 malloc이 있다. 명시적으로 할당된 블록을 반환해줄 것을 요구한다.
• 묵시적 할당기의 대표적인 예는 Java의 garbage collector가 있다 . 더 이상 프로그램에 의해 사용되지 않는 블록을 자동 반환시켜준다.

9.9.1. malloc과 free함수

1-1. malloc

• 데이터를 포함시킬 메모리 블록의 포인터를 리턴한다.
• 32비트 모드 -> 8의 배수 주소 블록 return
• 64비트 모드(기본설정) -> 16의 배수 주소 블록 return

1-2. malloc / calloc / reallloc

• malloc : 리턴할 메모리를 초기화 하지 않는다.
• calloc : 할당된 메모리를 0으로 초기화한다.
• realloc : 이전 할당된 블록의 크기를 변경할 수 있다.

1-3. sbrk 함수

• heap의 break 포인터(Top of the Heap)에 incr를 더해 heap을 늘리거나 줄인다.

1-4. free 함수

• free(*ptr)에서 ptr은 malloc / calloc / realloc을 통해 할당된 블록의 시작을 가리켜야 킨다.
• free함수는 아무것도 리턴하지 않아 동작 확인이 어렵다.
• free를 하면 메모리는 사라지지만, 그 메모리 블록을 가리킨 포인터는 초기화되지 않는다. 이후에도 포인터는 여전히 해당 블록의 시작 주소를 가리킨다.

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

2-1. 중요 이유

: 프로그램을 실제 실행시키기 전에는 자료의 크기를 알 수 없는 경우가 빈번하기 때문에

2-2. 자료의 크기를 모르는 게 왜 문제?

• 실행 전 자료의 크기를 모르 때 우리가 선택할 수 방법은 자료의 크기를 임의로 설정해주는 것이다.
• 하지만 자료 크기를 임의 설정하는 것은 나쁜 방법이다.
  1) 임의 설정한 자료의 크기가 실제 필요한 자료의 크기보다 클 때, '메모리 낭비'가 된다.
  2) 필요한 자료의 크기가 임의 설정한 자료의 크기보다 클 떄, 임의 설정을 다시 하고 컴파일해야한다.

2-3. 해결방법

: 런타임 시, 필요한 자료의 크기를 파악한 후 동적 할당해주면 된다.
=> 배열의 최대 크기는 가용한 가상메모리 양에 한해서 제한.

9.9.3. 할당기 목표

3-1. 할당기의 목표

: 처리량 극대화와 메모리 이용도 최대화(서로 상충하는 가치)

1) 처리량 극대화

• 할당기의 처리량 : 단위 시간당 완료되는 요청의 수로 정의

2) 메모리 이용도 최대화

• 프로세스에 의해 할당된 가상메모리의 양은 디스크 내의 스왑공간의 양에 제한된다.
• 큰 크기의 메모리 블록 할당 및 반환 시 가상메모리의 크기는 유한하다는 것을 유념해야한다.

** swap : 프로그램을 많이 실행하여 물리적 메모리(RAM)의 용량이 가득차면, 하드 디스크 공간을 메모리 공간처럼 교환(swap)하여 사용한다. 이후, 메모리가 다시 여유가 생기면 하드디스크에서 메모리로 옮겨온다.

9.9.4. 단편화

: 가용 메모리가 할당 요청을 만족시키지 못하는 현상

4-1. 내부 단편화

: 할당된 블록이 데이터 자체보다 더 클 때 발생
: 내부 단편화 정도 = 할당된 블록 크기 - 데이터 크기

4-2. 외부 단편화

: 메모리 전체적으로는 할당에 필요한 공간이 충분하지만, 이 요청을 처리할 단일한 가용블록은 없는 경우
: 측정의 어려움(미래의 요청에 의존하기 때문 = 예상이 어렵다)

9.9.5. 구현 이슈

: 처리량을 극대화하면서 메모리 이용도를 최대화하기 위해 고려해야할 이슈

• 가용 블록 구성
  : 어떻게 가용 블록을 지속적으로 추적하는가?
• 배치
  : 새롭게 할당할 가용 블록은 어떻게 선택하는가?
• 분할
  : 가용 블록에 메모리 할당한 후 가용 블록의 나머지부분으로 무엇을 할 수 있나?
• 연결
  : 블록을 반환하고 무엇을 할 것인가?

9.9.6. 묵시적 가용 리스트

글의 플로우를 음미하며 읽어보자. 최대한 술술 읽히도록 노력했다.

6-1. 동적 할당기

: 할당기는 할당된 블록과 가용 블록을 구분하는 데이터 구조(묵시적 가용 리스트 or 명시적 가용 리스트)를 필요로 한다.

6-2. 블록

• 헤더(1워드)
  : 블록 크기(최소 블록 크기 조건에 따름), 할당 여부
  : 마지막 3비트는 다른 정보를 인코드하기 위해 남겨둔다.

• 데이터
  : malloc이 요구한 데이터

• 패딩
  : 패딩의 존재 이유
  1) 외부 단편화 극복
  : (내 생각) 데이터 할당 시 조금 씩 남는 메모리가 쌓여 요구한 데이터 크기에 충분한 만큼 쌓이게 되지만 단일한 가용 블록은 존재하지 않는 상황이 발생할 수 있다. 따라서 패딩을 통해 조금씩 남는 메모리들을 모두 할당시켜버리면 외부 단편화를 극복할 수 있다.
  2) 정렬 요구사항 만족

6-3. 묵시적 리스트

: (내 생각) 위 그림을 보면 알 수 있듯이 각 블록의 헤더에 파일 크기를 보고 암묵적으로 다음 블록의 위치를 파악할 수 있기 때문에 묵시적 연결이라고 말한다.

1) 장점

: 단순성

2) 단점

: 할당 블록과 가용 블록의 헤더를 모두 확인해서 할당되어 있는 지 확인해봐야 하기 때문에 탐색에 있어서 전체 블록 수에 비례한다.

9.9.7. 구현

7-1. 배치

: k바이트의 블록 요청 시, 할당기는 요청 블록의 데이터 크기에 충분한 가용 블록을 리스트에서 검색한다.

• First Fit
  : 가용 리스트를 처음부터 검색하여 크기가 맞는 첫번째 가용 블록 선택
  : 장점 - 리스트의 마지막에 가장 큰 가용 블록을 남긴다.
  : 단점 - 리스트의 앞에 작은 가용 블록들을 남긴다 => 검색시간 늘어난다(크기가 맞지도 않은데 헤더 정보를 다 확인해야해서)

• Next Fit
  : 이전 검색이 종료된 지점에서 검색 시작
  : 장점 - First Fit 보다 빠름
  : 단점 - First Fit 보다 안좋은 메모리 이용도

• Best Fit
  : 모든 가용 블록을 검사하여 크기가 맞고 가장 작은 블록 선택
  : 장점 - 앞의 두 배치 방식 보다 메모리 이용도 좋음
  : 단점 - 힙을 모두 검색해야한다

7-2. 분할

: 크기가 맞는 가용 블록을 찾고 나면 가용 블록의 어느 정도를 할당할 지 결정하는 과정
: 총 2 옵션이 존재한다.

• 블록 전체 할당
  : 간단하고 빠르지만 내부 단편화가 크다.
• 할당 블록과 나머지(새로운 가용 블록)로 나누기

7-3. 연결

: 할당기가 할당한 블록을 반환할 때, 인접한 가용 블록들이 있다면 그 블록들과 연결할 수 있다.

1) 가용 블록 연결

• 언제 연결을 수행하는가에 따라 두 가지 연결로 나뉜다.
  1) 즉시 연결
  : 블록 반환 때 마다 연결
  2) 지연 연결
  : 일정 시간 후 전체 힙을 검색해서 모든 가용 블록 연결
  : 일부 빠른 할당기에서 종종 사용한다.

2) 경계 태그로 연결

: 각 블록의 끝 부분에 푸터(footer, 경계태그) 추가한다.
: 푸터는 헤더를 복사한 것이다.
: 반환할 블록의 인접한 가용 블록의 푸터에 블록 사이즈를 갱신해주는 것으로 쉽게 연결할 수 있는 방법이다. (CSAPP 821page 그림 9.40 참고)

7-4. 추가 힙 메모리 획득 (sork함수)

: 할당기가 요청한 블록을 찾을 수 없을 때 두 옵션이 있다.
: 모든 가용 블록을 물리적으로 연결하여 큰 가용 블록을 만든다.
: 그래도 블록 보다 데이터 크기가 크면, 추가적인 힙 메모리를 요청(sork 함수)할 수 있다.