- [CS] 동적 메모리 할당(DYNAMIC MEMORY ALLOCATION), malloc/free C언어로 구현하기 (CS:APP 이론정리)2022년 12월 02일 20시 43분 47초에 업로드 된 글입니다.작성자: nickhealthy
동적 메모리 할당
C 프로그머들은 대개 추가적인 가상메모리를 런타임(runtime)에 획득할 필요가 있을 때, 동적 메모리 할당기(dynamic memory allocator)를 사용하는 것이 저언어(e.g. mmap, munmap 함수) 를 사용하는 것보다 간편하다고 생각했다.
동적 메모리 할당기는 프로세스의 가상메모리의 힙(heap) 영역을 관리하는데, 힙 영역은 uninitialized data 영역 직후에 시작해서 주소가 올라가는 방향으로 힙의 사이즈는 커진다. 즉, 주소값이 커짐으로서 힙의 크기도 늘어나는 것이다. 아래 이미지는 리눅스 프로세스의 가상메모리 구조인데, 각각의 프로세스에 대해서 커널은 힙의 꼭대기를 가리키는 변수 brk를 사용해서 heap의 꼭대기를 가리키도록 한다. 즉, 힙의 최대 크기를 가리키는 것과 같다.
프로세스의 가상 메모리 할당기는 heap을 다양한 사이즈의 블록들의 모음으로 관리한다. 각각의 블록은 가상 메모리에서 연속적으로 이어지는 메모리들의 덩어리라고 생각할 수 있고, 이 각각의 블록은 할당(allocated) 상태이거나 가용(free) 상태이다.
allocated block, 즉 할당된 블록이란 사용처가 정해진 메모리 블록이다. 응용프로그램이 사용하기 위해서 명시적으로 블록을 할당하도록 요구한다.
free block, 즉 가용 블록이란 이 역시 말그대로 가용 (= 사용 가능한) 메모리 블록이다. 즉 아직 어떤 값이 할당되지 않은 상태이기 때문에 할당될 수 있는 상태의 블록이다.할당된 블록이 해제(free)되면 가용 블록이 되고, 가용 블록이 할당(allocate)되면 할당된 블록이 된다. 방금 할당된 블록이 해제되면 가용 블록이 된다고 했는데 해제에는 두 가지 방법이 있고, 할당기는 이 해제 방법에 따라 명시적 할당기와 묵시적 할당기로 구분된다.
동적 메모리 할당이 필요한 이유
결국 메모리를 낭비하지 않고, 수정하기 위해 재컴파일 하는 상황을 피하기 위해서이다.
명시적 할당기 / 묵시적 할당기
명시적 할당기는 명시적으로 블록을 할당하고, 명시적으로 블록을 해제 한다. 동적 메모리 할당에 사용되는 C언어의 malloc 패키지가 명시적 할당기에 해당한다.(malloc으로 할당 & free로 해제) 반면, 묵시적 할당기는 명시적으로 블록을 할당하고, 별도로 블록을 해제하지는 않는다. 대신 할당기는 사용되지 않는 할당된 블록을 자동으로 탐지해서 해제를 해준다. JAVA와 같은 프로그래밍 언어에서 가비지 컬렉터(garbage collector) 등이 묵시적 할당기에 해당한다.
동적 메모리 할당 - malloc, calloc, realloc
#include <stdlib.h> void *malloc(size_t size);malloc 함수는 위와 같이 사용한다. 함수 앞에 void *를 통해 예측할 수 있듯이 malloc 함수는 heap에 블록을 할당한 후, 할당된 블록을 가리키는(블록의 가장 첫 바이트를 가리키는) 포인터를 반환한다. 만약 메모리 부족 등으로 할당에 실패할 경우에는 NULL을 반환한다. malloc 함수는 반환하는 메모리를 초기화하지는 않으며, 메모리 할당과 함께 메모리를 초기화 하고 싶은 경우 malloc 함수와 비슷한 calloc 함수를 사용하면 된다. 또한 이미 할당된 메모리의 크기를 변경하고 싶은 경우 relloc 함수를 사용하면 된다.
동적메모리 할당기가 메모리를 할당하는 과정
malloc 함수는 인자로 할당할 바이트 크기(size)를 받는다. 하지만 1바이트 할당 요청을 받는다고 1바이트를 할당하고, 2바이트 할당을 요청 받는다고 2바이트를 할당하는 식으로 메모리를 할당하는 것이 아닌, 메모리 정렬에 따라 메모리를 할당한다. 본 포스팅에서는 double-word 정렬을 기준을 가정하였다. 아래 정리가 잘된 블로그가 있다.
메모리 얼라인먼트(Memory Alignment)
메모리 얼라인먼트는 레퍼런스마다 데이터 구조 얼라인먼트(Data Structure Alignment), 데이터 얼라인먼트(Data Alignment) 등으로 불리기도 하며, 위키피디아에서는 다음과 같이 개요가 작성되어 있습니
minusi.tistory.com
힙 메모리 사이즈 조절 - sbrk
malloc 함수와 같은 동적 메모리 할당기는 mmap 함수와 munmap 함수를 사용하여 heap 메모리에 명시적으로 할당할 수도 있고, sbrk 함수를 사용할 수도 있다. 위에서 커널의 변수 brk는 힙의 꼭대기를 가리키는 포인터라고 했는데, sbrk 함수는 이 brk 포인터의 값에 incr 값을 더함으로서 heap 영역의 크기를 늘리거나 줄인다.
#include <unistd.h> void *sbrk(intptr_t incr);sbrk 함수는 성공적으로 heap의 사이즈를 늘린 경우에는 기존 brk 값(아래 그림의 oldbrk)을 리턴하고, 수행에 실패할 경우 -1을 리턴하고, errno을 ENOMEM으로 설정한다.
할당된 메모리 해제 - free
malloc, calloc, realloc 등으로 할당된 메모리를 해제할 때는 free 함수를 호출한다.
#include <stdlib.h> void free(void *ptr);free 함수는 해제할 블록의 주소값의 첫 바이트를 가리키는 포인터 (malloc, calloc, realloc에서 리턴받은 포인터 값)를 인자로 받는다. 다른 곳을 가리키는 포인터를 받으면 아무것도 하지 않는다. free 함수는 성공해도, 실패해도 아무런 값도 리턴해주지 않기 때문에 알 수 없는 런타임 에러를 만들어내므로 주의해야 한다.
malloc과 free 함수로 블록을 할당하고 해제하는 과정
아래 그림을 통해 블록이 할당되고 해제되는 과정을 더 잘 이해할 수 있다. 아래 그림에서 각각의 정사각형은 1워드 (=4바이트)를 의미하고, 굵은 테두리의 직사각형은 하나의 블록을 나타낸다. 하얀 정사각형은 가용(free) 상태, 하늘색 정사각형은 할당(allocated) 상태를 의미한다. 진한 하늘색 정사각형은 패딩으로 할당된 상태를 의미한다.
위 그림에서 힙은 총 18개의 가용 블록이 어떻게 malloc 함수를 통해 할당되고, free 함수를 통해 해제되는지를 보여준다. 여기서 중요한 점은 malloc은 할당한 블록의 첫번째 블록을 가리키는 포인터를 반환한다는 것과(위 그림에서 p1, p2, p3, p4 포인터의 위치에 주목), 정렬을 맞추기 위해 패딩 데이터가 추가된다는 것이다. 위 그림의 (b)에서 malloc에는 (4*5 = )20바이트를 요청했지만 정렬을 맞추기 위해 추가 4바이트로 블록을 패딩한 것을 알 수 있다.
할당기의 조건(Requirements)과 목표
명시적 할당기에는 아래의 엄격한 제약사항이 적용된다.
▪️ 임의의 요청 순서 처리 :
이전 할당 요청에 의해서 할당상태가 된 블록에 대해서만 해제 요청을 할 수 있다는 제약 사항만 잘 지킨다면 할당 요청과 해제(free) 요청은 무작위로 와도 상관이 없다. 따라서 할당기는 할당 요청이 언제 오고, 해제 요청이 언제 올지에 대해서 추측하지 않는다. 즉, 프로그래머가 신경써서 할당과 해제를 해야 한다!▪️ 요청에 즉시 응답 :
할당기는 요청에 대해 즉시 응답하므로 요청받은 순서를 바꾸거나, 성능을 향상하기 위해 버퍼를 두지 않는다▪️ heap 메모리 영역만 사용
▪️ 블록 정렬 :
할당기는 어떤 데이터 타입도 저장할 수 있도록 블록을 정렬해야 한다.▪️ 할당된 블록을 수정하지 않음 :
할당기는 오로지 가용(free) 블록만을 수정할 수 있으므로, 일단 블록이 할당상태가 되고 나면 이를 옮기거나 수정하지 않는다.할당기의 목표는 처리량(쓰루풋;throughput)과 메모리이용도(memory utilization) 사이의 최적의 지점을 찾는 것이다. 처리량의 정의는 단위시간당 처리가 완료되는 요청의 개수이다. 처리량을 최대화 하려면 요청을 처리하는 평균 시간을 최소화하면 된다. 처리량과 메모리 이용도를 동시에 올리기는 어렵기 때문에 둘 다 최대로 만들수는 없고 둘 사이의 최적의 지점을 찾아야 한다.
메모리 단편화(Fragmentation)
단편화는 heap 메모리 이용도를 떨어뜨리는 주범으로서, 메모리가 가용상태임에도 불구하고 할당 요청을 처리하기 위해 사용될 수 없는 상황을 의미한다. 쉽게 정리하자면 메모리 공간이 작은 조각들로 나눠져서 공간은 있지만 할당은 불가능한 상태, 같은 말로 메모리 공간은 있지만 공간이 낭비되는 상황을 메모리 단편화라고 한다. 단편화에는 내부 단편화(internal fragmentation)와 외부 단편화(external fragmentation)가 존재한다.
내부 단편화는 프로세스가 필요한 양보다 더 큰 메모리 공간이 할당돼서 메모리 자원이 낭비되는 상태. e.g. 저장해야 하는 데이터는 1바이트인데 4바이트 블록이 할당
할당기가 부과하는 블록의 최소 사이즈가 할당 요청된 데이터(payload)의 크기보다 더 커서 발생하기도 하고, 할당기가 블록의 정렬을 맞추기 위해 (패딩으로) 블록의 크기를 증가 시켜서 발생할 수도 있다.
- 어떤 크기로 일정하게 나눈 상황에서(페이징기법) 프로세스가 나누었던 공간을 다 사용하지 못하고 안에 내부 빈공간이 발생하는 것을 내부 단편화라고 한다.
출처: 카네기멜론대학교 동적메모리 할당 강의자료 - 내부 단편화 부분 외부 단편화는 각각의 가용 블록들을 모두 합치면 필요한 데이터 이상이지만, 필요한 데이터 이상인 단일 블록이 없을 때 발생한다. 아래 그림에서 가용상태의 블록 (하얀 블록)은 모두 7개이지만, 6개 블록 할당 요청이 들어와도 어떠한 단일블록(이어진 블록)도 6보다 작기 때문에 이를 할당할 수 없다. 이러한 상황을 외부 단편화라고 한다.
출처: 카네기멜론대학교 동적메모리 할당 강의자료 - 외부 단편화 부분 외부 단편화는 앞으로 어떤 요청이 들어올지에 따라서 발생할 수도, 안할 수도 있다. 위의 상황에서 5개 블록 할당 요청과 2개 블록 할당요청이 순서대로 들어왔다면 아무런 외부 단편화 문제도 생기지 않았을 것이다. 이처럼 외부단편화의 발생 여부는 미래의 할당 요청에 따라 달려있기 때문에 수치화하고 예측하기가 어렵다. 이 때문에 대부분의 할당기들이 휴리스틱을 사용해서 많은 수의 자잘한 블록보다는 적은 수의 큰 블록들을 유지하려고 한다.
* 휴리스틱: 체계적이면서 합리적인 판단이 굳이 필요하지 않은 상황에서 사람들이 빠르게 사용할 수 있게 보다 용이하게 구성된 간편추론의 방법이다.
단편화의 해결 방법
페이징 기법
- 메모리를 일정 크기로 쪼개어 메모리를 할당하는 기법
- 외부 단편화를 해결할 순 있지만(중간중간에 공백이 생기는 단점을 해결), 내부 단편화가 발생할 수 있다. 예를 들어 프로세스 데이터의 크기가
- 하지만 일정 크기로 메모리를 나누었기 때문에 메모리 중간중간 남는 공간은 없다.
세그먼테이션 기법
- 프로세스가 필요한 크기만큼 메모리를 할당하는 기법
- 내부 단편화를 해결할 수 있지만 외부 단편화가 생기는 단점이 존재한다. 내부 단편화는 생길 수가 없다. 왜냐하면 프로세스가 필요한 크기만큼 메모리 자원을 할당해줘서 더 크게 할당하지 않았기 때문에
구현 이슈
직접 동적 메모리 할당기를 만들어본다고 하면 어떤 것들을 고려해야 할까? 동적메모리할당기의 목표 - 처리량과 메모리이용도 사이의 최적의 지점을 찾는다는 관점에서 아래의 사항들을 반드시 고려해야 해야 하고, 남은 포스팅에서는 아래의 각각의 사항들을 어떻게 처리하는지에 대해서 살펴 볼 것이다.
▪️ 가용 블록 구성(Free block organization) : 가용 블록들을 찾아내서 할당해야 할텐데, 어떻게 가용블록을 구성(조직)해놓아야 할까?
▪️ 할당한 블록의 배치(Allocate Blocks Placement) : 블록을 새로 할당할 때 가장 할당하기 적절한 위치를 어떻게 고를 것인가?
▪️ 가용 블록의 분할(Free Blocks Spliting) : 가용 블록의 일부를 할당한 후 남은 부분은 어떻게 분리할 것인가?
▪️ 가용 블록 연결(Coalescing Free Blocks) : 새로 해제된 블록들을 기존의 가용 블럭들과 어떻게 연결시킬 것인가?가용 블록 구성(Free block organization) - 묵시적 가용 리스트 (implicit free lists).ver
할당기는 할당된 블록과 가용 블록을 구별할 수 있는 블록의 경계가 필요하다. 그리고 대부분의 할당기들은 이런 경계가 될 수 있는 정보들을 블록 자체에 끼워넣는다. 블록 내에 저장해야 하는 정보(payload) 뿐 아니라 1 워드짜리(=4바이트) 헤더를 붙여서 블록의 크기와 할당 여부를 표시하고, 필요한 경우 정렬을 맞추기 위한 패딩도 포함한다. 아래의 그림으로 이러한 구조를 표현할 수 있다.
출처: 카네기멜론대학교 동적메모리 할당 강의자료 위 그림에서 빨간색 부분이 4바이트 크기의 헤더이다. 4바이트의 32비트 중 29비트는 블록의 사이즈를 표현하기 위해 사용되고 마지막 세바이트 중 가장 오른쪽 한 비트(그림에서 a로 표현된 부분)는 할당 유무를 나타낸다. 이 값이 1이면 할당이 된 상태, 0이면 가용 상태이다. 참고로 블록의 사이즈는 블록의 헤더, payload, 패딩 모든 것을 포함한 블록 전체 크기를 의미한다.
묵시적 가용리스트의 이름이 '묵시적' 가용리스트인 이유는 이렇게 헤더에 블록의 크기가 나와있기 때문에, 직접적으로(or 명시적으로) 다음 블록의 주소가 나와있지는 않더라도 (현재 주소 + 블록 크기)로 다음 블록의 시작점을 계산할 수 있기 때문이다. 아래 그림을 참고해보면 보다 이해가 쉽다. 그림에서 헤더의 n/m은 사이즈/할당유무 를 나타낸다. 위의 화살표를 보면 헤더를 통해서 다음 블록의 시작점으로 이동하며 순회(traverse)할 수 있다.
CS:APP 9.9 Dynamic Memory Allocation 위 그림이 묵시적 가용 리스트의 구조이다. 가용 블록들은 마치 연결리스트와 같이 연결되어있고, 그 방법은 '묵시적'인 방법이다. 다음 블록을 가리키는 포인터가 블록 내에 직접 존재하는 것이 아닌, 블록의 사이즈를 통해서 계산해 나가는 간접적이고 묵시적인 방법이다. 그런데 위 구조에서 새로운 1워드 짜리 블록들이 보인다. 바로 힙의 맨 앞과 맨 끝에 있는 블록이다. 힙의 첫 블록은 사용되지 않는 블록으로 정렬을 맞추기 위해 필요하고, 맨 마지막 블록은 끝 블록이라는 것을 알려주기 위한 블록으로 크기는 0이고 할당된 상태를 가진 블록이다.
이렇게 묵시적 가용 리스트를 구성하면 간단하다는 장점이 있지만, 사용할만한 가용블록을 찾기 위해서 계속 순회하면서 가용리스트를 검색해야 하는 비용이 든다는 단점이 있다. 할당블록과 가용블록을 합쳐서 모두 N개의 블록이 있다고 하면 O(N)의 선형 시간이 든다.
시스템의 정렬 조건 (본 포스팅에서는 더블워드 정렬)과 묵시적 가용리스트의 블록 형식은 블록의 최소 사이즈를 결정한다. 저장할 데이터 (+ 필요하다면 패딩) 이외에도 최소한 4바이트 헤더는 가져야 한다는 것은 블록의 최소 사이즈는 8바이트라는 것이다. 만약 응용프로그램이 1바이트 할당만 요청하더라도 할당기는 8바이트, 즉 2-word 블록을 할당할 것이다.
* 참고: 패딩은 '메워넣기' 라는 뜻을 의미하며, 여기서 패딩의 크기는 가변적이다. 패딩이 존재하는 이유는 여러가지 이유가 있는데, 예를 들어 '외부 단편화'를 극복하기 위해서 또는 정렬 요구사항을 만족시키기 위해 존재할 수도 있다.
할당한 블록의 배치(Placement)
응용프로그램이 k바이트의 블록을 요청하면 할당기는 k만큼을 할당할 수 있을만한 적절한 가용 블록을 검색한다. 적절한 가용 블록을 찾기 위한 방법은 배치정책(placement policy)에 의해 결정된다. 이 정책에는 first fit, next fit, best fit이 존재한다.
배치의 방법
first fit방법은 리스트의 맨 처음부터 탐색을 시작해 크기가 맞는(크기가 k이상, 가용 상태) 첫 번째 가용 블록을 선택한다.
Next fit방법은 first fit과 비슷하지만 탐색을 처음부터 시작하는 대신, 이전에 검색이 종료된 지점에서 검색을 시작한다.
Best fit은 처음부터 끝까지 멈추지 않고 가용 블록을 탐색하여 크기가 맞는 가장 작은 블록을 선택한다.방식에 따른 장점과 단점
first fit의 장점은 리스트의 뒷 부분에 있는 사이즈가 큰 가용 블록들을 사용하지 않고 유지하고 있을 가능성이 크고, 단점은 리스트의 앞부분에 작은 가용 블록들이 남아 있을 가능성이 있다는 것이다.
next fit의 장점은 이전 탐색에서 가용 블록을 발견했다면 다음 탐색에 있어서 리스트의 나머지 부분은 원하는 블록을 찾을 가능성이 높다는 아이디어에서 나왔다. 따라서 이전 가용 블록을 찾아낸 자리에서 탐색을 시작해 더 빠르게 가용 블록을 찾아낼 수 있다. 단점은 first fit에 비해 메모리 이용도가 떨어지게 된다.
best fit의 장점은 앞의 두 방법들에 비해 메모리 이용도가 높다는 것이고, 단점은 탐색에 시간이 오래걸린다는 것이다.가용 블록의 분할(Spliting)
할당기가 요청받은 만큼 할당할 위치를 찾고나면, 이제 얼마나 할당할 것인가를 결정해야 한다. 할당할 크기는 2word이고, 할당할 위치의 가용 블록은 8 word 짜리인데, 이 8 word 전체를 할당할 수는 없다. 남는 6-word 크기의 메모리는 내부 단편화를 유발한다. 메모리는 결국 유한한 자원이므로 남는 6word를 소중히 아껴써야 하기 때문이다.
할당기는 대개 가용 블록을 두 부분으로 나누게 된다. 첫 번째 부분은 할당한 블록이 되고, 두 번째 부분은 새로운 가용 블록이 된다. 아래 그림을 보자. 첫 번째 이미지에서 32/0 헤더를 가진 8-word 크기의 가용 블록이 있다. 할당기가 응용프로그램으로부터 3-word(12bytes) 블록을 요청받으면, 할당기는 헤더를 포함해(1-word) 4-word를 할당할 자리를 찾는다. 32/0 의 헤더를 가진 이 가용 블록에 4워드를 할당하면, 이 32/0 의 8워드 블록은 16/1 헤더를 가진 4워드 블록과 16/0 헤더를 가진 4워드 블록으로 나뉜다.
* 참고: 할당된 블록은 색칠된 것이고, 가용(free) 블록은 색칠되지 않은 것이다. 헤더는 (size (bytes) / allocated bit)로 라벨 되어진다.
추가 heap 메모리가 필요할 때
만약 할당기가 요청한 블록을 찾을 수 없다면 어떻게 해결할 수 있을까? 한 가지 방법은 메모리에서 물리적으로 인접한 가용 블록들을 합쳐서(연결해서) 더 큰 가용 블록을 만들어 보는 것이다. 하지만 이렇게해도 블록을 할당할 수 있는 가용 블록이 아무것도 없다면, 할당기는 sbrk 함수를 호출함으로서 커널에 heap 메모리를 추가로 달라고 요청한다. 할당기가 추가로 메모리를 받으면 이를 하나의 가용 블록으로 변형하고 가용 리스트 안에 이 블록을 삽입한 다음 블록을 할당한다.
가용 블록 연결(Coalescing Free Blocks)
할당기가 할당된 블록을 해제 할때, 새로 해제된 블록의 좌우에는 다른 가용 블록들이 있을 수 있다. 아래 그림을 보자. p가 가리키는 4-word 크기의 블록을 해제했을 때 우측에도 2-word 크기의 가용 블록이 있다. 이렇게 4개짜리 가용 블록과 2개짜리 가용 블록이 붙어있는 상태에서 5-word를 할당하려고 할 때 할당할 수 있는 블록이 없다. 이를 오류 단편화(false fragmentation)라고 한다. 분명 4개짜리와 2개짜리 가용블록을 붙이면 (연결하면; coalesce 하면) 6-word 짜리 가용 블록이 될 수 있음에도 이를 연결하지 않아 필요한 블록을 할당하지 못하는 문제가 생기는 것이다. 이러한 오류 단편화를 해결하기 위해 할당기들은 coalescing이라고 불리는 방법으로 인접한 가용 블록들을 병합한다.
위에서 오류 단편화를 해결하기 위해 연결이라는 과정으로 인접 가용 블록들을 통합해야 한다고 했는데, 이 과정에서는 언제 연결을 수행해야 할지에 관한 중요한 정책 결정을 내려야한다.
경계 태그로 연결하기(Coalescing with Boundary Tags)
해제하려고 하는 블록을 '현재블록'이라고 할때, 현재블록의 다음 블록이 가용 블록인 경우는 간단하게 연결할 수 있다. 현재 블록을 해제 한 후 다음 블록의 헤더를 체크하여 할당 상태가 0이라면 (즉, 가용 블록이라면) 헤더에서 블록의 크기를 확인 한 후 현재 블록의 헤더에 이 크기를 더해준다. 아래 그림에서 기존의 헤더에서 블록 크기가 4였고, 인접한 다음 가용블록의 크기가 2 이므로, 현재 블록의 헤더에 블록크기를 4+2 = 6으로 업데이트해주면, 기존의 크기가 2였던 가용 블록은 '논리적으로' 사라지게 되는 것이다.
출처: 카네기멜론대학교 동적메모리 할당 강의자료 그런데, 현재 블록의 다음 블록이 아니라 이전 블록이 가용 블록인 경우에는 그리 간단하지 않다. 우선 왼쪽 블록이 가용블록인지 아닌지를 보고 판단할만한게 없다. 결국 가용 리스트를 처음부터 현재 블록을 만날 때까지 다 탐색하는 수 밖에 없다. 결국 블록을 해제하는데 선형 시간이 드는 것이다.
이를 해결하기 위해 'boundary tags' 라는 방법이 고안됐다. 블록의 맨 끝에 푸터(footer)를 붙이는 것이다. 이 footer가 바로 boundary tags 이다. 푸터의 내용은 헤더의 내용과 동일하게 블록의 크기 + 할당 정보이다. 헤더와 동일한 내용의 푸터를 블록 끝에 붙임으로서 할당기는 이전 블록이 시작하는 위치와 할당 상태를 알아낼 수 있게 된다.
출처: 카네기멜론대학교 동적메모리 할당 강의자료 현재블록을 해제하고 인접한 가용 블록과 연결하려 할 때, 4가지의 경우가 존재한다.
출처: 카네기멜론대학교 동적메모리 할당 강의자료 1. 현재 블록의 이전 블록, 다음 블록 모두 할당된 상태
2. 현재 블록의 이전 블록은 할당된 상태, 다음 블록은 가용상태
3. 현재 블록의 이전 블록은 가용 상태, 다음 블록은 할당된 상태
4. 현재 블록의 이전 블록, 다음 블록 모두 가용 상태이제 블록은 boundary tag를 가지고 있다고 생각하고, 위의 네 가지 경우에서 어떻게 블록들이 연결 되는지를 살펴보자. 자료로 사용된 그림에서 a는 할당된 상태, f는 가용 상태를 나타낸다.
1. 현재 블록의 이전 블록, 다음 블록 모두 할당된 상태
인접한 블록들이 모두 할당된 상태이므로 연결이 수행되지 않는다. 현재 블록의 헤더와 푸터의 할당 여부를 표시하는 비트값만 바뀜으로서 논리적으로 블록이 할당 상태에서 가용 상태로 바뀐다.
CS:APP 9.9 Dynamic Memory Allocation Figure 9.4 2. 현재 블록의 이전 블록은 할당된 상태, 다음 블록은 가용상태
다음 블록이 가용 상태이므로 다음 블록과 연결한다. 현재 블록의 헤더가 그대로 연결된 블록의 헤더가 되고, 다음 블록의 푸터가 연결된 블록의 푸터가 된다. 이 헤더와 푸터의 값은 현재블록의 크기 + 다음 블록의 크기 값으로 바뀌고, 할당 상태도 0으로 바뀐다. 아래 그림에서 현재 블록의 크기가 n, 다음 블록의 크기가 m2 였으므로 연결된 새 가용블록의 크기는 n+m2 이다.
CS:APP 9.9 Dynamic Memory Allocation Figure 9.4 3. 현재 블록의 이전 블록은 가용 상태, 다음 블록은 할당된 상태
이전 블록이 가용 상태이므로 이전 블록과 연결한다. 이전 블록의 헤더가 그대로 연결된 블록의 헤더가 되고, 현재 블록의 푸터가 연결된 블록의 푸터가 된다. 이 헤더와 푸터의 값은 현재블록의 크기 + 이전 블록의 크기 값으로 바뀌고, 할당 상태도 0으로 바뀐다. 아래 그림에서 현재 블록의 크기가 n, 이전 블록의 크기가 m1 였으므로 연결된 새 가용블록의 크기는 n+m1 이다.
CS:APP 9.9 Dynamic Memory Allocation Figure 9.4 4. 현재 블록의 이전 블록, 다음 블록 모두 가용 상태
이전 블록과 다음 블록 모두 가용 상태이므로 이전 블록과 다음블록 모두 연결한다. 이전 블록의 헤더가 그대로 연결된 블록의 헤더가 되고, 다음 블록의 푸터가 연결된 블록의 푸터가 된다. 이 헤더와 푸터의 값은 현재블록의 크기 + 이전 블록의 크기 + 다음 블록의 크기 값으로 바뀌고, 할당 상태도 0으로 바뀐다 (이 경우 헤더와 푸터는 이미 가용 상태이므로 따로 할당상태를 바꿀 필요는 없다). 아래 그림에서 현재 블록의 크기가 n, 이전 블록의 크기가 m1, 다음 블록의 크기가 m2 였으므로 연결된 새 가용블록의 크기는 n+m1+m2 이다.
CS:APP 9.9 Dynamic Memory Allocation Figure 9.4 위의 과정을 살펴본 것과 같이 boundary 태그를 사용함으로서 블록을 해제하는 시간은 O(1)의 상수 시간로 매우 짧다. 하지만 boundary tag를 이용하는 방법에도 단점이 있는데, 블록에 헤더와 푸터를 모두 사용함으로서 데이터를 제외한 다른 부분들이 메모리에서 차지하는 양(=memory overhead)이 너무 커진다는 것이다. 작은 블록들이 여러 개 있는 경우에는 정도가 더 심하다. 이를 해결하는 최적화 방법은 현재 블록을 메모리에 있는 이전과 다음 블록과 연결하려고 할 때, 만일 이전 블록이 가용한 경우에만 이전 블록의 풋터에 있는 size 필드가 필요하다는 점이다.
1. CMU malloc lab 강의 자료 (ppt)
2. Computer Systems: A Programmer's Perspective, 3/E (CS:APP3e)
3.[CS] 동적 메모리 할당 - malloc /free C 언어로 구현하기 part 1. 이론 (📖CS:APP)
이전글이 없습니다.댓글