[CSAPP] 9.9 Dynamic Memory Allocation

해롱그·2023년 9월 6일

CS

목록 보기

2/4

동적 메모리 할당

heap

stack과는 달리 사용자가 직접 관리하는 메모리 영역

int *a;		// stack에 저장
a = (int*)malloc(sizeof(int)*10);	// heap에 저장

1행에서는 int형 포인터 변수 a를 선언했고, 이건 일반적인 포인터형 변수이므로 stack 영역에 저장된다.
malloc() 함수는 특정 크기의 메모리 블록을 동적으로 할당한다. 이 메모리 블록은 heap 영역에 할당되고, 2행에서는 int형(4byte) 10개의 공간만큼을 할당했다.
a <= 4*10(40 byte)
그 영역에 대한 주소값을 리턴하여 a라는 변수에 저장한다.

이 때 중요한 것은 사용자가 직접 heap 영역에 메모리를 할당하여 데이터를 사용한 후에 더 이상 해당 메모리 블록이 필요하지 않은 경우, 무조건 사용자가 직접 할당된 메모리를 해제해줘야 한다. 그렇지 않으면 프로그램을 종료해서 메모리 공간은 계속 할당된 상태로 남아있어 다른 프로그램이 사용할 수 없게 된다.

free(a);	// 메모리 해제

이렇게 하면 해당 메모리 블록은 반환되어 다시 사용 가능한 상태가 되며 메모리 누수를 방지할 수 있다. free() 함수를 호출한 이후에는 더 이상 해당 메모리 블록을 접근하거나 수정할 수 없다. 메모리 블록에 접근하려고 하면 정의되지 않은 동작 or 오류가 발생할 수 있다.

mmap (Memory Mapping)

유닉스 및 유닉스 계열 운영 체제에서 사용되는 시스템 콜 중 하나이다. mmap을 통해 파일을 메모리에 매핑하거나 메모리를 할당하고 파일과 메모리 간 데이터를 주고 받을 수 있다.

쉽게 말하자면, 파일 또는 기타 데이터를 메모리에 매핑하는 기술이다. 파일을 메모리에 ‘불러오는’ 것으로 생각할 수 있다. 메모리 매핑을 통해 파일을 읽고 쓰거나, 파일의 내용을 메모리에서 직접 조작할 수 있다.

간단한 예를 들어보자.

mmap을 사용하여 텍스트 파일을 메모리에 매핑하면, 파일의 내용을 메모리에 load한다. 그런 다음 메모리에서 파일 내용을 수정하거나 검색할 수 있다. 이것은 파일을 읽고 쓰는 작업을 더 빠르고 효율적으로 수행할 수 있게 해주며, 대용량 파일의 처리에 특히 유용하다.

mmap은 주로 파일 I/O와 메모리 관리에서 사용되며, 시스템 프로그래밍 및 특정 응용 프로그램에서 자주 사용된다. mmap을 통해 다른 프로세스 간 메모리를 공유하는 작업을 수행할 수 있는다. 프로세스 A가 파일을 메모리에 매핑하면 프로세스 B도 같은 메모리에 접근하여 파일의 내용을 읽고 쓸 수 있다. 이는 프로세스 간 통신(IPC) 및 데이터 공유에 사용된다.

각각의 프로세스는 독립된 주소 공간을 가지게 된다. 주소 공간은 논리적인 3개의 segment로 분할된다. 프로세스 메모리는 기본적으로 다른 프로세스 메모리와 공유되지 않는다.

요약하면 mmap은 파일 또는 데이터를 메모리에 매핑하여 데이터를 효율적으로 읽고 쓰는데 사용되는 기술이다.

malloc

malloc()은 size 만큼 메모리를 동적으로 할당하기 위해서 사용하며, 호출에 성공한 뒤 할당된 메모리 영역을 가리키는 포인터를 리턴한다.
malloc이 문제를 만나면 (ex. 프로그램이 사용 가능한 가상 메모리보다 큰 메모리 블록을 요청한 경우), NULL을 리턴하고 errno를 설정한다. malloc은 반환된 메모리를 초기화하지 않는다.
초기화된 동적 메모리를 사용하려는 응용 프로그램은 malloc 함수 주위에 얇은 래퍼인 calloc을 사용할 수 있다. 이는 할당된 메모리를 0으로 초기화한다. 그리고 이전에 할당된 블록의 크기를 변경하려는 응용 프로그램은 realloc을 사용할 수 있다.
malloc()을 이용하여 할당된 메모리 영역은 자동으로 clear되지 않으므로 더 이상 사용하지 않는 메모리 영역은 반드시 free()를 이용해서 clear 해줘야 한다! 그렇지 않을 경우 메모리 누수가 일어날 수 있다.
malloc과 같은 동적 메모리 할당자는 mmap 및 munmap 함수를 사용하여 힙 메모리를 명시적으로 할당 또는 해제하거나 sbrk 함수를 사용할 수 있습니다.

struct name
{
    int     age;
    char    name[25];
};
int main()
{           
    char *org_name;
    struct name *myname;
    int i;
                       
    // org_name 에 char 이 25만큼 들어갈수 있는
    // 메모리 공간을 할당.                                                
    // malloc 는 할당된 메모리 영역의 포인터를 리턴해주므로
    // org_name 은 malloc 를 이용해 할당된 영역의 포인터를 가리킨다.
    org_name = (char *)malloc(sizeof(char)*25);
                                                                               
    // myname 역시 마찬가지로 struct name 이 2개 만큼 들어갈수
    // 있는 메모리 공간을 할당.
    myname = (struct name *)malloc(sizeof(myname)*2);

brk, sbrk

메모리 관리를 위한 system call

brk
프로세스의 데이터 섹션의 끝 위치를 조절하는 시스템 호출이다. 이를 통해 프로세스는 힙 메모리 영역을 조절하고 확장 또는 축소할 수 있다.

sbrk
현재의 프로세스 데이터 섹션 끝 위치에 대한 주소를 반환하거나 수정한다. 주로 동적 메모리 할당을 위해 사용되는데, sbrk를 사용하여 프로그램은 힙 메모리 영역의 크기를 동적으로 확장하거나 축소할 수 있다.

이러한 호출은 메모리 할당 및 해제를 관리하는데 사용되며, 특히 동적 메모리 할당과 관련된 함수인 malloc 및 free와 같은 C 표준 라이브러리 함수의 구현에 사용될 수 있다. 이러한 호출을 직접 사용하는 대신 C 또는 다른 고수준 언어에서 제공하는 메모리 관리 함수를 사용하는 것이 더 안전하고 편리하다.

동적 메모리 할당의 이유

프로그램이 동적 메모리의 할당을 사용하는 가장 중요한 이유는 프로그램이 실제로 실행될 때까지 특정 데이터 구조의 크기를 알지 못하기 때문이다.

Fragmentation

힙 활용도가 떨어지는 주요 원인으로 알려져있는 fragmentation은, 힙 영역에 메모리가 남아있으나 블록을 할당하기 어려운 상황. 즉, 공간이 파편화되는 현상을 말한다.
memory utilization이 좋지 않으면 단편화를 야기한다.

내부 단편화 (Internal Fragmentation)

malloc에서 할당해준 블록이 실제로 정보를 담을 블록보다 공간이 큰 경우에 양옆으로 자잘한 공간이 남아서 발생하는 현상이다.
이는 힙 자료구조를 관리하는 과정에서 오버헤드가 발생해서 일어난다.

위 그림에서 진한 하늘색으로 칠해진 영역이 비어있다고 생각해보자. 현재 할당된 블록은 두꺼운 라인인 6칸짜리 블록인데, p2에서 실제로 데이터가 들어가는 영역(payload) 은 int 5칸이다. 따라서 이 경우에는 할당된 블록의 공간을 전부 사용하지 않으니 내부 단편화가 일어난다.

그림에서는 p2의 마지막 칸에 진한 하늘색이 칠해져있는데 비어있는걸까?
NO. p2의 일부이다. p2는 int 사이즈로 5칸을 요청했으나 현재 작업하는 컴파일러가 32비트 모드이기 때문에 할당기 주소는 8바이트의 배수에 맞게 배치되어야 한다. 하지만 현재 전체 블록 크기는 4byte(int 사이즈)*5=20byte로, 한 칸을 더 붙여줘야 24byte로 8의 배수가 된다.
이렇게 실제 데이터에는 들어가지 않으나 블록 사이즈를 조정하기 위해 추가적으로 덧대는 블록을 padding이라고 한다.

내부 단편화는 정량화하기에 간단하다.
이는 단순히 할당된 블록의 크기와 페이로드 간의 차이의 합이다. 따라서 어느 시점에서든 내부 단편화 양은 이전 요청의 패턴과 할당기의 구현에만 의존한다.

외부 단편화

할당 요청을 만족시킬 수 있는 충분한 총 free 메모리가 있지만 정렬이 되어있지 않아 할당하지 못하는 경우에 발생하는 현상을 말한다.

위 그림에서 e의 요청이 두 단어가 아닌 여덟 단어에 대한 것이었다면 어떻게 되었을까?
두 개의 free 블록(heavy rectangle)에 걸쳐 여덟 개의 자유 단어가 있음에도 불구하고 커널로부터 추가적인 가상 메모리를 요청하지 않으면 만족시킬 수 없다.

외부 단편화는 미래의 요청 패턴에 달려 있기 대문에 측정하기 더 어렵고 예측이 불가능하기 때문에 정량화하기 어렵다. 때문에 할당자는 일반적으로 작은 free 블록을 많이 남겨놓는 것보다 큰 free 블록을 적게 유지하려고 시도하는 휴리스틱을 사용한다.

Implementation Issues

처리량과 이용도 사이에 좋은 균형을 갖는 실용적인 할당기는 다음 이슈들을 고려해야 한다.

① free block organization: free block을 어떻게 추척할까?
② placement: 새로 할당된 블록을 배치할 적절한 free block을 어떻게 선택할까?
③ splitting: 새로 할당된 블록을 일부 free block에 배치한 후, 나머지 free block은 어떻게 해야할까?
④ coalescing: 이제 막 해방된 블록은 어떻게 할까?

① 가용 블록 구성

implicit free list (묵시적 가용 리스트)

implicit 방법은 할당된 블록과 free 블록이 모두 연결되어 있다.
실용적인 할당기는 블록 경계를 구분하고, 할당된 블록과 free 블록을 구분하는 데이터 구조를 필요로 한다.
대부분의 할당기는 이 정보를 블록 내에 내장한다.

위 그림은 implicit 리스트의 한 블록의 구조이다. 이 경우에 한 블록은 1워드 header, 데이터, 추가적인 padding으로 구성된다.

힙을 연속된 블록의 배열로 구성하면 아래와 같은 그림으로 구성된다.
두번째 블록의 8/0은 free 블록이 8byte 있다는 뜻이고, 그 다음 16/1은 할당된 블록 16byte 있다는 뜻이다. 16/1 바이트의 마지막 진한 파란색의 블록은 padding을 나타낸다.

explicit free list (명시적 가용 리스트)

ecplicit 방법은 free 블록끼리만 연결되어 있다.

② 할당한 블록의 배치

응용 프로그램이 k바이트의 블록을 요청하면, 할당자는 요청된 블록을 보유할 수 있을 정도의 크기로 자유 블록을 검색한다.
할당자가 이 검색을 수행하는 방식은 배치 정책에 의해 결정된다.

first-fit
처음부터 탐색하고 처음 크기가 맞는 첫 가용 블록을 선택한다.
👍🏻 장점: 리스트의 끝 부분에 큰 가용 블록을 갖게 되는 경향이 있습니다.
👎🏻 단점: 리스트의 앞 쪽에 작은 가용 블록 조각을 남겨두는 경향이 있습니다. 그렇기 때문에 더 큰 블록을 찾는 시간이 증거한다.
next-fit
first-fit과 유사하지만 목록의 처음에서 각 검색을 시작하는 대신 이전 검색이 중단된 시점에서부터 검색을 시작한다.
지난 번에 어떤 자유 블록에서 적합을 발견하면 나머지 블록에서 다음 번에 적합을 발견할 가능성이 높다는 아이디어에서 고안되었다.
👍🏻 장점: first-fit보다 훨씬 더 빨리 실행될 수 있으며, 특히 리스트의 앞 쪽에 작은 조각들이 흩어져있는 경우엔 더 그렇다.
👎🏻 단점(까진 아니지만..): 해당 지점에서 마지막까지 찾지 못했다면, next fit도 결국 처음 포인트부터 찾아야 하는 경우가 발생한다.
best-fit
모든 가용 블록을 검사해서, 크기에 맞는 가용 블록 중 가장 작은 블록을 선택한다.
👍🏻 장점: 가장 크기에 맞는 블록을 찾기 때문에 메모리 활용도가 높다.
👎🏻 단점: 시간이 오래 걸린다.

③ 가용 블록의 분할

할당자가 적합한 자유 블록을 찾아냈다면, 가용 블록의 어느 정도를 할당할 것인가에 대한 다른 정책 결정을 내려야 한다.

가용 블록 전체 할당
비록 간단하고 빠르기는 하지만, 주된 단점은 내부 단편화를 도입하는 것이다. 배치 정책이 적합성을 잘 나타내는 경향이 있다면, 일부 추가적인 내부 단편화는 허용될 수 있다.
둘로 나눠 할당
만약 적합성이 좋지 않다면, 할당자는 일반적으로 가용 블록을 두 부분으로 분할하는 것을 선택할 것이다.
첫 번째 부분은 할당된 블록이 되고, 나머지 부분은 새로운 가용 블록이 된다.

+ 추가 힙 메모리 가져오기

할당자가 요청된 블록에 대한 적합성을 찾기 못하면 어떻게 될까?
한 가지 방법은 메모리(다음 섹션)에서 물리적으로 인접한 가용 블록을 병합하여 더 큰 가용 블록을 생성하는 것이다.

그러나 이것이 충분히 큰 블록을 산출하지 못하거나 이미 가용 블록이 최대로 병합된 경우 할당자는 *sbrk 함수를 호출하여 커널에 추가 힙 메모리를 요청한다.
할당자는 추가 메모리를 하나의 큰 자유 블록으로 변환하고 자유 목록에 블록을 삽입한 다음 요청된 블록을 이 새로운 자유 블록에 배치한다.

*sbrk?
유닉스 운영 체제에서 사용되는 시스템 콜 중 하나로, 프로세스의 데이터 섹션 크기를 변경하는 데 사용된다. 메모리 할당자가 sbrk 함수를 호출하여 추가 힙 메모리를 요청하는 경우, 이것은 운영 체제에 의해 할당된 가상 메모리 공간을 확장하고 이 확장된 공간을 할당자에게 제공한다.

sbrk 함수 호출을 통해 추가 힙 메모리를 할당하는 것은 프로세스의 힙 영역을 동적으로 확장하는 방법 중 하나이다. 이러한 동적 메모리 확장은 메모리 할당자가 메모리 부족 상황을 해결하는 데 사용한다.

④ 가용 블록 병합하기

free block 병합
인접한 free block을 합체하는 작업을 해줌 (coalescing)
boundary tags 병합
allocator는 병합을 어떻게 구현할까? free로 만들려고 하는 블록을 current block이라고 할 때, current block의 header는 그 다음 block의 header를 가리키고 있다. 그래서 그 블록이 free인지 아닌지를 체크하고 free라면 현재 header의 사이즈에 이 블록을 더해서 합친다.

next block이 아닌 prev block 이라면 어떻게 해야할까?
heap을 처음부터 스캔하는 방법이 있지만 현재 블록이 heap 내에서 뒷쪽에 위치한다면 그 시간은 비례해서 증가할 것이다. (효율 X)

이를 해결하기 위한 방법으로 경계 태그(boundary tags)를 설명하겠다. 기존의 header와 동일한 형태(동일한 4byte에 들어있는 값도 header와 동일)를 블록 끝에도 붙이는데, 이를 footer라고 한다.
사실 footer는 메모리 입장에서보면 비효율적인 녀석이다. header랑 모양도, 내용도 똑같은데 굳이 하나 더 만들 이유가 무엇일까?.. 하지만 free 블록을 효율적으로 찾는 관점에서 보면 완전히 쓸모없는 녀석은 아닌거다.
최종적으로 만들어지는 블록의 모양은 이렇다.
즉시 병합: free block 사용될 때마다 병합 호출
지연 병합: 필요할 때까지 병합을 연기함으로써 성능을 개선