[시스템 프로그래밍] 가상메모리[1] - 동적 메모리 할당

 

 

 

 

 

🧐 동적 메모리 할당

프로그램이 실행되기 전에는 그 크기를 알 수 없는 메모리 영역을 런타임 시에 획득하기 위해 동적 메모리 할당을 사용합니다.

 

동적 메모리 할당기는 힙(heap)이라고 하는 프로세스의 가상메모리 영역을 관리합니다.

 

자세한 내용은 시스템마다 다르지만, 일반화의 오류를 범하지 않는 한도에서, 힙 영역이 초기화되지 않은 데이터 영역 이후부터 시작하여 위쪽(주소가 증가하는 방향)으로 커지는 메모리 영역이라 가정하겠습니다.

 

각각의 프로세스에 할당되는 가상 메모리에 대하여, 커널은 힙 영역의 꼭대기를 가리키는 포인터(brk ptr)를 사용합니다.

 

 

메모리 할당기는 힙을 다양한 크기의 블록 단위로 관리합니다.

 

메모리를 할당하는 방법에는 명시적(Explicit)으로 할당하는 방법과 묵시적(Implicit)으로 할당하는 방법이 있습니다.

 

 

명시적 할당

응용 프로그램이 할당하고, 반환합니다.
예를 들어 C 프로그램의 malloc과 free가 이에 해당합니다.

 

 

 

묵시적 할당

응용 프로그램이 할당하지만, 직접 반환하지는 않습니다.
이를 위해서는 더 이상 프로그램에 의해 사용되지 않는 블록을 검출할 수 있어야 합니다.

예시로는 자바에서의 가비지 컬렉터가 있으며, 자동으로 사용하지 않는 할당된 블록을 반환시켜주는 작업을 가비지 컬렉션이라 부릅니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 malloc

C 표준 라이브러리는 malloc 패키지로 알려진 명시적인 할당기를 제공합니다.

프로그램은 malloc 함수를 호출해서 힙으로부터 블록들을 할당받습니다.

#include <stdlib.h>

void * malloc(size_t size);

malloc 함수는 블록 내에 포함될 수 있는 어떤 종류의 데이터 객체에 대해서 적절히 정렬된 최소 size 바이트를 갖는 메모리 블록의 포인터를 반환합니다.

실제 구현에서 코드가 32비트 모드인 경우 주소는 8의 배수, 64비트 모드인 경우 16의 배수입니다.

 

만약 size가 0 이거나 할당에 실패한 경우 NULL을 반환하며 errno를 세팅합니다.

 

malloc은 리턴하는 메모리를 초기화하지 않습니다.

만약 초기화되길 원한다면 calloc을 사용할 수 있습니다.

 

이전에 mallioc을 통해 할당된 블록의 크기를 변경하고 싶은 경우 realloc 함수를 사용할 수 있습니다.

#include <stdlib.h>

void * realloc(void * p, size_t size);

realloc은 블록 p의 크기를 변경하고, 새 블록의 포인터를 리턴합니다.

새 블록의 내용은 이전 블록과 새 블록의 크기 중 작은 블록의 크기까지는 변함없습니다.

 

 

 

 

 

 

 

 

 

 

🧐 sbrk

malloc같은 동적 메모리 할당기는 mmap과 munmap 함수를 사용하여 명시적으로 힙 메모리를 할당하거나, 혹은 sbrk 함수를 사용할 수 있습니다.

#include <unistd.h>

void * sbrk(intptr_t incr);

sbrk 함수는 커널의 brk 포인터에 incr을 더해서 힙을 늘리거나 줄입니다.

 

성공한다면 이전의 brk 값을 리턴합니다.

실패한다면 -1을 리턴하고 errno를 ENOMEM으로 설정합니다.

 

 

 

 

 

 

 

 

 

 

🧐 free

프로그램들은 할당된 힙 블록을 free 함수를 호출해서 반환합니다.

#include <stdlib.h>

void free(void * ptr);

ptr 인자는 malloc, calloc, realloc에서 획득한 할당된 블록의 시작을 가리켜야 합니다.

그렇지 않은 경우 free의 동작은 정의되지 않습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 예시

힙 영역을 다음과 같이 가정하겠습니다.

각 블록은 워드 단위이다.

 

 

 

아래 그림은 C 프로그램에 대하여 16 워드의 작은 힙을 malloc과 free가 어떻게 관리하는지를 보여줍니다.

(예시를 위해 메모리는 워드 단위로 주소가 지정된다고 하겠습니다.)

 

동일한 색의 워드들은 하나의 블록을 이룬다.

 

 

 

 

 

 

 

 

 

 

🧐 할당기 요구사항

명시적 할당기들은 아래와 같은 요구사항을 만족해야 합니다.

할당된 블록의 갯수와 크기는 조정할 수 없습니다.

임의의 순서로 들어오는 요청 처리

응용 프로그램은 각각의 가용 블록이 이전의 할당 요청에 의해 현재 할당된 블록에 대응되어야 한다는 제한사항을 만족하면서 임의의 순서로 할당과 반환요청을 할 수 있습니다.
따라서 할당기는 할당과 반환 요청의 순서에 대해 아무런 가정을 할 수 없습니다.

모든 할당 요청에 즉시 응답

요청 순서를 변경하거나 요청을 버퍼등에 저장할 수 없습니다.

블록은 프리 메모리에서만 할당해야 합니다.

블록들은 모든 주소맞춤 요건을 만족하도록 정렬해야 합니다.

리눅스 컴퓨터의 GNU malloc에서는 8 혹은 16바이트의 정렬을 사용합니다.

프리 메모리만을 관리하고 수정할 수 있습니다.

일단 할당된 블록들은 이동할 수 없습니다.

 

 

위와 같은 요구사항들을 만족하면서, 더 좋은 성능을 내기 위해 처리량과 메모리 이용도를 최대화하기 위하여 노력해야 합니다.

 

이상적으로는 malloc과 free 수행 시 (언제나 가능한 것은 아니지만) 상수 시간이 걸려야 하며,

공간 활용도를 높이기 위해 파편화(fragmentation)를 최소화해야 합니다.

 

 

 

 

 

 

🧐 성능 지표 1 : Throughput(처리량)

malloc과 free 요청들이 다음과 같이 주어진다고 하겠습니다.

$R_0,\; R_1,\; ...,\; R_k, \;...,\; R_{n-1}$

 

처리량은 단위 시간(1 초)동안에 완료한 요청의 수 입니다.

예를 들어 5000번의 malloc과 5000번의 free를 10초 동안에 수행하는 경우, 처리량은 `1000 operations / second` 입니다.

 

 

 

 

 

 

 

🧐 성능 지표 2 :  최대 메모리 이용률(Utilization)

malloc과 free 요청들이 다음과 같이 주어진다고 하겠습니다.

$R_0,\; R_1,\; ...,\; R_k, \;...,\; R_{n-1}$

총 데이터 $P_k$ : 요청 $R_k$ 가 처리된 후, 총 데이터 $P_k$ 는 현재 할당된 데이터들의 합입니다.

현재 힙의 크기 $H_k$

최대 메모리 이용률 :
k개의 요청 후 최대 메모리 이용률은 $U_k = \frac{(max_{i \leq k} P_i)}{H_k}$ 입니다.

 

 

 

 

 

 

🧐 Fragmentation(파편화)

메모리 사용의 효율이 떨어지는 이유는 파편화(fragmentation)로 인하여 발생합니다.

 

파편화는 내부 파편화와 외부 파편화로 구분할 수 있습니다.

 

 

👉 Internal Fragmentation (내부 파편화)

일부 블록에서 내부 파편화는 블록 크기와 데이터 크기 사이의 차이로 인하여 발생합니다.

즉 할당된 블록이 데이터 자체보다 더 큰 경우에 발생합니다.

단편화 == 파편화

 

내부 파편화는 힙 자료구조를 유지하고, 정렬을 위해 바이트를 추가하거나 할당 정책에 의 한 오버헤드 (블록을 나누지 않는 경우)때문에 발생합니다.

이전에 요청한 패턴에 의해서만 영향을 받으며 따라서 측정하기 용이합니다.

 

 

 

 

 

 

 

 

👉 External Fragmentation (외부 파편화)

할당 요청을 만족시킬 수 있는 메모리 공간이 힙 전체를 합쳤을 때에는 존재하지만, 해당 요청을 처리할 수 있는 단일 가용블록이 존재하지 않는 경우에 발생합니다.

 

예를 들어 다음과 같은 상황이 외부 파편화의 예시입니다.

해당 경우 malloc(6)의 경우, 전체 힙의 가용 공간의 총 합은 7인 반면, 가용한 단일 블럭의 최대 크기가 5이므로 할당할 수 없는 상태에 놓여있습니다.

 

외부 파편화는 내부 파편화와 달리 미래의 요청에 의하여 결정되기 때문에 측정이 어렵습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 malloc과 free 구현 시 고려사항

• 가용블록을 지속적으로 추적하고 관리할 수 있어야 합니다.
• 가용블록보다 작은 크기의 구조체를 할당할 때, 남는 공간을 어떻게 할 것인지 고려해야 합니다.
• 할당을 위한 가용 블록은 어떻게 선택해야 할 지 고려해야 합니다.
• 반환된 블록을 가용 블록으로 어떻게 관리해야 할 지 고려해야 합니다.
• 얼마만큼 free 시켜야 하는지 알 수 있어야 합니다.

 

 

 

 

 

 

 

 

 

 

🧐 free 블럭 관리하기

Free 블럭을 관리하는 방법으로는 다음과 같은 것들이 있습니다.

간접(묵시적) 리스트 방식 (Implicit List):

블록의 크기 정보를 이용하여 모든 블록을 연결합니다.

직접(명시적) 리스트 방식 (Explicit List):

가용 블록끼리만 포인터로 연결합니다.

구분 가용 리스트 방식 (Segregated Free List)
일정한 구간의 크기별로 나누어, 해당 크기 내의 가용 리스트를 각각 유지하는 클래스를 만들어서 운영합니다.

크기로 정렬된 블록 방식