[CSAPP] 9.9 Dynamic Memory Allocation(동적 메모리 할당)

9.9 Dynamic Memory Allocation(동적 메모리 할당)

• 로우 레벨의 mmap과 munmap 함수를 사용하여 가상 메모리의 영역을 만들고 삭제하는 것이 가능하지만, 동작 중(런타임에) 가상 메모리를 얻고싶을 때는 동적 메모리 할당자(ex. malloc 함수)를 쓰는 것이 더 편리하고 portable(이식성이 좋다)하다. 
• 동적 메모리 할당자(allocator)는 heap으로 알려진 프로세스의 가상 메모리 영역을 유지한다. (아래 그림 참고)

• 상세 내용은 시스템마다 다르지만 일반성의 손실 없이 힙은 uninitialized data area(초기화되지 않은 데이터 영역)의 끝 부터 시작하여 위쪽(높은 주소)로 증가하는 demand zero 메모리 영역이라 가정한다. 
• 각 프로세스에서 커널은 힙의 맨위를 가리키는 변수 brk(break)를 유지한다.
• 할당자(allocator)는 힙을 다양한 크기의 블록 모음으로 유지한다.
• 각 블록은 할당되거나 사용 가능한 가상 메모리의 연속적인 청크이다.
• 할당된 블록이 응용프로그램에서 사용하기 위해 명시적으로 예약되어진다.
• 사용 가능한 블록을 할당할 수 있고 사용 가능한 블록은 응용 프로그램에 의해 명시적으로 할당될 때까지 사용 가능한 상태로 유지된다.
• allocator(할당자)는 두 가지 기본 스타일로 제공된다. (명시적 할당자, 암묵적 할당자)
  • 두 스타일 모두 응용프로그램이 블록을 명시적으로 할당해야 한다. 
  • 두 가지 스타일은 할당된 블록을 프리하는 책임이 어느 쪽에 있는지에 따라 다르다.
• 명시적 할당자(Explicit allocators)는 어플리케이션이 할당된 블록을 명시적으로 프리해야 한다.
  • 예를 들어, C 표준 라이브러리에는 malloc 패키지라는 명시적 할당기가 있다. C 프로그램은 malloc 함수를 호출하여 블록을 할당하고 free 함수를 호출하여 블록을 프리한다. C++의 new와 delete 호출도 유사하다.
• 반면 암묵적 할당자(Implicit allocators)는 할당된 블록이 더 이상 사용되지 않을 때 할당기가 블록을 자동으로 해제(프리)한다.
  • 암묵적 할당기는 가비지 컬렉터(garbage collector)로도 알려져 있으며, 사용되지 않는 할당된 블록을 자동으로 해제하는 프로세스를 가비지 컬렉션이라고 한다. 예를 들어, Lisp, ML, Java 등 고급 언어는 가비지 컬렉션을 사용하여 할당된 블록을 해제한다.
• 이번 섹션의 나머지 부분은 명시적 할당자의 디자인과 구현에 대해 논의한다.
• 암묵적 할당자에 대해서는 9.10 섹션에서 다룰 예정이다.

9.9.1 The malloc and free Functions

#include <stdlib.h>
void *malloc(size_t size);
	/*Returns: pointer to allocated block if OK, NULL on error*/

• C 표준 라이브러리는 malloc 패키지라는 명시적 할당자를 제공한다.
• 프로그램은 malloc 함수를 호출하여 힙에서 블록을 할당한다.
• malloc 함수는 바이트 크기 이상의 메모리 블록을 반환하며, 이 블록에 포함될 수 있는 모든 데이터 객체에 적합하게 정렬된 포인터를 반환한다.
• 실제로 정렬은 코드가 32비트 모드(gcc -m32)에서 실행되는지 64비트 모드(기본값)에서 실행되는지에 따라 다르다.
• 32비트 모드에서 malloc은 항상 8의 배수인 주소를 갖는 블록을 반환하고, 64비트 모드에서는 항상 16의 배수인 주소를 갖는 블록을 반환한다.
• 만약 malloc이 문제를 발견하면(예: 프로그램이 사용 가능한 가상 메모리보다 큰 메모리 블록을 요청하는 경우) NULL을 반환하고 errno를 설정한다.
• malloc은 반환된 메모리를 초기화하지 않는다. 초기화된 동적 메모리를 필요로하는 응용 프로그램은 malloc 함수의 래퍼 인 calloc을 사용할 수 있다. 이 함수는 할당된 메모리를 0으로 초기화한다.
• 이전에 할당된 블록의 크기를 변경하려는 응용 프로그램은 realloc 함수를 사용할 수 있다.

#include <unistd.h>
void *sbrk(intptr_t incr);
/*Returns: old brk pointer on success, −1 on error*/

• malloc와 같은 동적 메모리 할당기는 mmap 및 munmap 함수를 사용하여 명시적으로 힙 메모리를 할당하거나 해제 할 수 있다.
• 또는 sbrk 함수를 사용할 수도 있습니다.
• sbrk 함수는 커널의 brk 포인터에 incr을 추가하여 힙을 확장하거나 축소한다.
• 성공하면 이전 brk 값을 반환하고 그렇지 않으면 -1을 반환하고 errno를 ENOMEM으로 설정한다.
• incr이 0이면 sbrk는 현재 brk 값을 반환합니다.
• 음수의 incr로 sbrk를 호출하는 것은 가능하지만 위험한 방식이다.
  • 왜냐하면 반환 값 (이전 brk 값)은 힙의 새로운 맨 위에서 abs(incr) 바이트를 가리키기 때문이다.

#include <stdlib.h>
void free(void *ptr);
/*Returns: nothing*/

• 프로그램은 메모리를 할당받을 때 malloc, calloc 또는 realloc 함수를 사용하고, 할당받은 메모리 블록을 해제할 때 free 함수를 사용한다.
• 그러나 free 함수의 ptr 인자는 반드시 malloc, calloc, realloc 함수로 할당된 메모리 블록의 시작 부분을 가리켜야 한다.
• 그렇지 않으면 free 함수의 동작이 정의되지 않기 때문에 런타임 오류를 일으킬 수 있다.

• 그림 9.34는 C 프로그램의 16 워드 작은 힙을 관리하는 malloc과 free의 구현 방법을 보여준다. 각 상자는 4 바이트 워드를 나타낸다. 진한 선의 사각형은 할당된 블록(음영)과 빈 블록(음영 없음)을 나타낸다. 처음에 힙은 더블워드 경계에 맞추어 정렬된 16 워드 빈 블록으로 구성된다.
  • (a) 프로그램은 4 워드 블록을 요청한다. Malloc은 빈 블록의 앞부분에서 4 워드 블록을 조각내어 블록의 첫 번째 워드를 가리키는 포인터를 반환한다.
  • (b) 프로그램은 5 워드 블록을 요청한다. Malloc은 빈 블록의 앞부분에서 6 워드 블록을 할당한다. 이 예에서 malloc은 빈 블록이 더블워드 경계에 맞추어 정렬되도록 블록을 추가로 패딩한다.
  • (c) 프로그램은 6 워드 블록을 요청하고 malloc은 빈 블록에서 6 워드 블록을 조각내어 반환한다.
  • (d) 프로그램은 그림 9.34(b)에서 할당된 6 워드 블록을 해제한다. free 함수가 반환한 후에도 포인터 p2는 여전히 해제된 블록을 가리킨다. p2를 다시 사용하지 않고 malloc의 새로운 호출로 초기화하기 전까지는 이것은 애플리케이션의 책임이다.
  • (e) 프로그램은 2 워드 블록을 요청한다. 이 경우 malloc은 이전 단계에서 해제된 블록의 일부를 할당하고 이 새로운 블록을 가리키는 포인터를 반환한다.

#include "csapp.h"
#define MAXN 15213

int array[MAXN];

int main()
{
	int i, n;

	scanf("%d", &n);
	if (n > MAXN)
		app_error("Input file too big");
	for (i = 0; i < n; i++)
		scanf("%d", &array[i]);
	exit(0);
}

• 프로그램에서 동적 메모리 할당을 사용하는 가장 중요한 이유는, 종종 프로그램이 실제로 실행될 때까지 특정 데이터 구조체의 크기를 모르기 때문이다.
• 예를 들어, C 프로그램을 작성하도록 요청받아 stdin에서 한 줄에 하나의 ASCII 정수 목록을 읽어 C 배열에 저장해야하는 경우가 있다.
  • 정수 n이 입력된 다음에 array에 n번 저장되는 형식이다. 
• 위 코드를 작성하는 가장 간단한 접근 방법은 미리 하드 코딩 된 최대 배열 크기로 정적 배열을 정의하는 것이다.
• 이렇게 하드 코딩된 크기로 배열을 할당하는 것은 종종 좋은 아이디어가 아니다.
• MAXN의 값은 임의적이며 기계에서 실제 사용 가능한 가상 메모리 양과는 관련이 없다.
• 더욱이, 이 프로그램을 사용하는 사용자가 MAXN보다 큰 파일을 읽고 싶어한다면, 유일한 대안은 MAXN의 값을 더 크게하여 프로그램을 다시 컴파일하는 것이다.
• 이 간단한 예제에서는 문제가 되지 않지만, 하드 코딩된 배열 경계의 존재는 수백만 줄의 코드와 많은 사용자를 가진 대규모 소프트웨어 제품에서 유지보수의 악몽이 될 수 있다. (다시 수정하려면 매우 복잡)
• 더 나은 접근 방법은 n 값이 입력된 후 런타임에 동적으로 배열을 할당하는 것이다.
• 이 접근 방식으로 배열의 최대 크기는 사용 가능한 가상 메모리 양으로 제한되는 장점이 있다.
• 따라서 동적 메모리 할당은 유용하고 중요한 프로그래밍 기술이다.
• 그러나 할당자(allocator)를 올바르고 효율적으로 사용하기 위해서는 프로그래머들이 그 작동 방식에 대한 이해가 필요하다.
• 할당자의 부적절한 사용으로 인해 발생할 수 있는 몇 가지 끔찍한 오류에 대해서는 9.11 절에서 논의할 것.

9.9.3 Allocator Requirements and Goals(할당기에 요구사항과 목표)

• 명시적 할당자는 다음과 같은 엄격한 제약 사항 내에서 동작해야 한다:
  • 임의의 요청 시퀀스 처리:
    • 응용 프로그램은 allocate 및 free 요청의 임의의 시퀀스를 수행할 수 있다. 그러나 각 free 요청은 이전 allocate 요청으로부터 얻은 현재 할당된 블록에 해당해야 한다. 따라서 할당자는 allocate 및 free 요청의 순서를 스스로 가정할 수 없다. 
  • 즉각적인 요청 응답:
    • 할당자는 allocate 요청에 즉시 응답해야 한다. 따라서 할당자는 성능을 향상시키기 위해 요청을 재정렬하거나 버퍼링할 수 없다.
  •  힙(heap)만 사용:
    • 할당자가 확장 가능하려면, 할당자에서 사용되는 모든 비스칼라 데이터 구조는 힙 자체에 저장되어야 합니다.
  •  블록 정렬(정렬 요구 사항)
    • 할당자는 블록을 정렬하여 모든 유형의 데이터 개체를 보유할 수 있도록 해야 한다.
  •  할당된 블록 수정 금지:
    • 할당자는 할당된 블록을 수정하거나 이동할 수 없다. 따라서 할당된 블록을 압축하는 기술과 같은 기술은 허용되지 않는다. 이러한 제약 조건 내에서 할당자의 작성자는 처리량을 최대화하고 메모리 활용을 극대화하는 데에도 노력한다.
    • 목표 1: 처리량 최대화.
      • 일련의 n allocate 및 free 요청이 주어지면, allocate 및 free 요청을 만족하는 평균 시간을 최소화하여 할당자의 처리량을 최대화하고자 한다. 예를 들어, 할당자가 1 초에 500 개의 allocate 요청과 500 개의 free 요청을 완료하면, 처리량은 초당 1,000 개의 작업이다. 일반적으로, 최악의 경우 allocate 요청의 실행 시간이 free 블록 수에 비례하고, free 요청의 실행 시간이 상수인 할당자를 개발하는 것은 그리 어렵지 않다.
    •  목표 2 : 메모리 이용도 최대화.
      • 단순한 프로그래머들은 가상 메모리가 무한한 자원이라고 잘못 생각하기도 한다. 사실상 시스템의 모든 프로세스에서 할당하는 가상 메모리의 총량은 디스크의 swap space의 양으로 제한된다. 좋은 프로그래머는 가상 메모리가 효율적으로 사용되어야 함을 알고 있다. 이는 특히 큰 메모리 블록을 할당하고 해제할 수 있는 동적 메모리 할당기의 경우 더욱 중요하다. 힙을 사용하는 할당기가 힙을 효율적으로 사용하는 방법은 여러 가지가 있다. (아래는 딥한 내용 패스 권장)
      • 우리는 경험상, 최대 이용도(peak utilization)라는 지표가 가장 유용하다고 생각한다. 이전과 마찬가지로, n개의 할당 및 해제 요청 순서가 주어진다고 가정하자. 응용 프로그램이 p 바이트의 블록을 요청하면, 결과로 얻은 할당 블록은 p 바이트의 페이로드를 갖는다. Rk 요청이 완료된 후, 현재 할당된 블록의 페이로드 합을 나타내는 집계 페이로드 Pk와 현재 힙의 크기를 (단조적으로 감소하지 않는) Hk로 정의한다. 그런 다음, 첫 번째 k + 1 요청에 대한 최대 이용도인 Uk는 아래와 같이 정의된다. 할당기의 목적은 전체 시퀀스에 걸쳐 최대 이용도 Un-1을 최대화하는 것이다. 

 

swap이란?

- 시스템에 메모리가 부족할 경우에 하드 디스크의 일부 공간을 활용하여 계속 작업을 도와주는 영역.

(메인 메모리 공간 부족을 위한 임시 방편)

- 하드 디스크의 일부를 RAM처럼 사용할 수 있게 만드는 것.

- 프로그램을 많이 실행하여 메모리가 부족하면, 메모리 상에 적재된 프로그램 중 지금 당장 필요하지 않은 프로그램 데이터를 하드 디스크에 옮겨 메모리 공간을 확보하는 것

 

페이로드(payload)는 사용에 있어서 전송되는 데이터를 뜻한다. 페이로드는 전송의 근본적인 목적이 되는 데이터의 일부분으로 그 데이터와 함께 전송되는 헤더와 메타데이터와 같은 데이터는 제외한다.

여기서는 (allocated block) 의미

9.9.4 Fragmentation(단편화)

• 힙 사용 효율이 떨어지는 주요 원인은 사용하지 않는 메모리가 할당 요청을 충족시키기 위해 사용 불가능한 경우인 단편화(Fragmentation) 문제이다.
• 내부 단편화(Fragmentation)와 외부 단편화(Fragmentation) 두 가지 형태의 단편화(Fragmentation)가 있다.
  • 내부 단편화는 할당된 블록이 페이로드보다 큰 경우 발생합니다. 이는 여러 가지 이유로 발생할 수 있다.
    • 예를 들어, 할당자 구현에서 요청된 페이로드보다 큰 최소 블록 크기를 부과하는 경우, 또는 Figure 9.34(b)에서 본 것처럼 블록 크기를 정렬 제약 조건을 충족하기 위해 증가시키는 경우(패딩).
  •  내부 단편화는 간단하게 계산할 수 있다. 할당된 블록의 크기와 페이로드 간 차이의 합이다. 따라서 언제든지 내부 단편화의 양은 이전 요청 패턴과 할당자 구현에만 의존한다.
• 외부 단편화는 충분한 빈 메모리가 있어도 한 개의 빈 블록으로 요청을 처리할 수 없는 경우 발생한다.
  • 예를 들어, Figure 9.34(e)에서의 요청이 2 word 대신 8 word라면, 8 개의 free word가 힙에 남아 있더라도 추가 가상 메모리를 요청하지 않고는 요청을 처리할 수 없다. 이 문제는 이 8 개의 word가 두 개의 빈 블록에 분산되어 있기 때문입니다.
•  외부 단편화는 내부 단편화보다 훨씬 어려우며, 이전 요청 패턴과 할당자 구현뿐만 아니라 미래 요청 패턴에도 의존하기 때문이다.
  • 예를 들어, k번째 요청 후 모든 빈 블록이 정확히 4 word 크기인 경우, 이 힙이 외부 단편화를 겪고 있는지 여부는 미래 요청 패턴에 따라 다르다. 모든 미래의 할당 요청이 4 word보다 작거나 같은 블록을 요청하면 외부 단편화가 없다. 그러나 하나 이상의 요청이 4 word보다 큰 블록을 요청하면 힙은 외부 단편화를 겪게 된다. (Figure 9.34(e) 그림 참고)

9.9.5 Implementation Issues

• 가장 간단한 할당자는 바이트의 큰 배열과 초기에 첫 번째 바이트를 가리키는 포인터 p로 힙을 구성한다. 크기 size 바이트를 할당하기 위해서는 malloc은 현재 p 값(주소)을 스택에 저장하고 p를 size만큼 증가시킨 다음 이전 p 값을 호출자(caller)에게 반환한다. free는 아무 작업도 수행하지 않고 caller에게 반환한다.
• 이러한 단순한 할당자는 각 malloc과 free가 소수의 명령어만 실행하기 때문에 처리량은 매우 좋을 것이다.
• 그러나 할당자는 어떤 블록도 재사용하지 않으므로 메모리 이용률은 극도로 나쁠 것이다. 처리량과 이용률 간의 균형을 더 잘 맞출 수 있는 실용적인 할당자(allocator)는 다음과 같은 문제를 고려해야 한다.
  • 빈 블록 구성 방법(Free block organization): 빈 블록을 어떻게 추적할까?
  • 배치(Placement): 새로 할당된 블록을 넣을 적절한 빈 블록은 어떻게 선택할까?
  • 분할(Splitting): 어떤 빈 블록에 새롭게 할당된 블록을 넣은 후 남은 빈 블록은 어떻게 처리할까?
  • 병합(Coalescing): 방금 해제된 블록은 어떻게 처리할까?
• 이 장의 나머지 부분에서는 이러한 문제를 더 자세히 살펴볼 것. 배치, 분할 및 병합의 기본 기술은 다양한 빈 블록 구성 방식에서 공통적으로 사용되므로 이러한 기본 개념을 소개할 것.

9.9.6 Implicit Free Lists(묵시적 리스트 방식)

• 실제 할당기(allocator)는 할당된 블록과 빈 블록을 구분할 수 있는 데이터 구조가 필요하다. 대부분의 할당기는 이 정보를 블록 자체 내부에 포함한다.
• 위 그림 9.35을 봐보자.
• 이 경우 블록은 한 워드(header), payload, 그리고 추가적으로 패딩이 포함 될 수 있다.
• 일반적인 방법으로는 추가적으로 1블록을 사용하여 블록 앞에 블록의 크기를 저장하는 방법이 있다.
• 이때 추가적으로 사용되는 1워드를 헤더(header)라고 부른다.
• 헤더는 블록 크기(헤더와 패딩을 포함한 크기)와 할당되었는지 여부를 인코딩한다.
• 더블 워드 정렬 제약 조건을 적용하면 블록 크기는 항상 8의 배수이며 블록 크기의 3개의 최하위 비트는 항상 0이다.
  • 왜 하위 3비트는 항상 0인가?
    먼저 우리가 기억하는 건 아래 두 가지
    1. 헤더는 1 word로 4byte의 크기 4byte는 32비트
    2. 더블 워드 정렬로 블록의 크기는 항상 8의 배수
    헤더의 32비트에는 블록의 사이즈가 저장된다.
    하위 비트 세 개 1 1 1(2) 은 십진수로 나타내면 최대 7까지만 나타낼 수 있다.
    그렇기 때문에 8의 배수가 헤더에 저장되면 4번째 비트부터 변화(1처리)를 주어야 한다.                                      따라서 하위 3개 비트는 항상 0이다.                                                                                                                       이 하위 세개 중 가장 오른쪽을 Allocated(1) / free(0) 여부 기록용으로 사용된다. 나머지 두 개는 다른 정보 인코딩에 쓰인다. 
• 따라서 우리는 블록 크기의 29개의 최상위 비트만 저장하면 된다. 
  • 예를 들어, 크기가 24(0x18)[16 + 8]바이트인 할당된 블록이 있다면, 해당 블록의 헤더는 다음과 같습니다.
  • 0x00000018[블록 크기] | 0x1 [가용 상태 여부] = 0x00000019
  • 마찬가지로 크기가 40(0x28)[16 * 2 + 8]바이트인 빈 블록의 헤더는 다음과 같다.
  • 0x00000028[블록 크기] | 0x0 [가용 상태 여부] = 0x00000028
• 헤더 다음에는 애플리케이션이 malloc을 호출할 때 요청한 payload가 따라온다.
• Payload 다음에는 사용되지 않는 패딩(chunk)도 따라올 수 있다.
  • 패딩이 필요한 이유는 다양하다. 예를 들어, 패딩은 할당기가 외부 단편화(external fragmentation)를 극복하기 위한 전략의 일부일 수 있고, 정렬 요구 사항을 충족시키기 위해 필요할 수도 있다.

• 그림 9.35의 블록 형식을 사용하면 위 그림 9.36에서 볼 수 있듯이 연속된 할당된 블록과 빈 블록의 시퀀스로 힙(heap)을 구성할 수 있다.
• 이 구성을 묵시적 빈 블록 리스트(implicit free list)이라고 부른다. 빈 블록들이 헤더의 크기 필드를 통해 묵시적(암시적)으로 연결되어 있기 때문이다. 
• 특별한 마지막 블록([0/1])이 필요하다는 점에 유의하자. 위 그림은 할당된 비트가 1로 설정되고 크기가 0인 힙의 마지막 헤더이다. (9.9.12절에서 볼 것처럼 할당된 비트를 설정하는 것이 빈 블록 통합을 간단하게 만든다.) 이를 에필로그 헤더(epilogue header)라 부른다.
• 묵시적 빈 블록 리스트(implicit free list)의 이점은 단순성이다. 그러나 상당한 단점은 빈 리스트 검색과 같은 모든 작업의 비용이 힙에 할당된 총 블록 수에 선형적이라는 것이다.
• 시스템의 정렬 요구사항과 할당기의 블록 형식 선택은 할당기의 최소 블록 크기를 부과합니다. 할당된 또는 빈 블록은 이 최소 크기보다 작을 수 없다. 예를 들어, 이중 워드 정렬 요구사항을 가정한다면, 각 블록의 크기는 두 개의 워드(8바이트)의 배수이어야 한다. 따라서 Figure 9.35의 블록 형식은 최소 블록 크기를 두 개의 워드로 하나는 헤더를 위한 워드이고, 다른 하나는 정렬 요구사항을 유지하기 위한 것이다. 심지어 응용 프로그램에서 1바이트를 요청하더라도 할당기는 여전히 두 워드 블록(8바이트)을 만들어 낸다.