묵시적 가용 리스트(Implicit Free List)
Implicit Free List는 메모리 할당 및 해제 시 데이터 블록 사이즈와 할당 가능한 블록 사이즈를 기록하는 묵시적 연결 리스트입니다. 이 기법에서는 각 블록의 헤더에 2진 비트를 사용하여 블록의 할당 여부와 블록 크기를 표시합니다.
구체적으로, 메모리 할당 시, 요청한 크기보다 큰 최소 블록을 찾습니다. 해당 블록이 충분히 크다면, 필요한 크기로 나누고 할당 표시를 변경한 후 할당한 메모리 블록의 시작 포인터를 반환합니다. 메모리 해제 시, 할당 해제할 블록을 찾은 후 해당 블록의 할당 비트를 지웁니다.
하지만 이 방법은 외부 단편화가 발생할 가능성이 높습니다. 블록 크기가 일치하지 않는 경우, 사용할 수 없는 작은 공간이 생성되며 이러한 공간은 다른 작은 블록을 할당하기 위해 남겨집니다. 따라서 명시적 연결 리스트 기법과 같은 다른 기법과 비교할 때, 공간 낭비가 발생할 가능성이 높습니다.
Implicit Free List는 구현하기 쉽고, 상대적으로 적은 오버헤드를 가지므로 작은 프로그램에서는 잘 작동합니다. 그러나 대규모 시스템에서는 명시적 연결 리스트나 다른 기법과 같은 더 효율적인 메모리 할당 및 해제 기법을 고려해야 합니다
Malloc-Lab
Implicit Free List 방식을 이용한 malloc 구현 방법은 크게 다음과 같은 단계로 이루어집니다.
- 초기화(init) : 메모리 힙(heap) 영역을 할당하고, 초기 블록(header)을 설정합니다.
- 할당(malloc) : free 블록 중 충분한 크기의 블록을 찾습니다.
- 분할(splintering) : free 블록이 필요한 크기보다 큰 경우, 할당하고자 하는 크기만큼 블록을 나눠줍니다.
- 사용 : 할당받은 메모리를 사용합니다.
- 해제(free) : 할당된 블록을 free 블록 중 첫 번째 블록으로 추가합니다.
간단히 살펴보면, 메모리 힙을 초기화하고, 할당하고자 하는 메모리 크기에 해당하는 free 블록을 찾아내는 것입니다. 만약 해당하는 블록이 충분한 크기가 아니라면, 블록을 나누어 할당할 수 있는 크기로 나누어줍니다. 이후, 할당받은 메모리를 사용하다가 해제할 경우 해당 블록을 free 블록 중 첫 번째 블록으로 추가해줍니다.
Implicit Free List 방식은 구현이 간단하고 효율적입니다. 그러나 힙 내부에서 free 블록의 위치를 파악하기 어렵기 때문에, 외부에서 메모리 할당을 계속하다보면 메모리 단편화 현상이 발생할 수 있습니다. 또한, free 블록이 나란히 위치하게 되면 이를 통합해주어야 하므로 추가적인 연산이 필요합니다. 이러한 단점을 보완하기 위해 Explicit Free List 방식이 개발되었습니다
malloc함수를 묵시적 가용 리스트(Implicit Free List)를 활용해 직접 C언어로 구현해 보았습니다
/*
* mm-naive.c - The fastest, least memory-efficient malloc package.
*
* In this naive approach, a block is allocated by simply incrementing
* the brk pointer. A block is pure payload. There are no headers or
* footers. Blocks are never coalesced or reused. Realloc is
* implemented directly using mm_malloc and mm_free.
*
* NOTE TO STUDENTS: Replace this header comment with your own header
* comment that gives a high level description of your solution.
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"
/*********************************************************
* NOTE TO STUDENTS: Before you do anything else, please
* provide your team information in the following struct.
********************************************************/
team_t team = {
/* Team name */
"ateam",
/* First member's full name */
"Harry Bovik",
/* First member's email address */
"bovik@cs.cmu.edu",
/* Second member's full name (leave blank if none) */
"",
/* Second member's email address (leave blank if none) */
""};
/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8 // 할당되는 메모리 블록의 크기를 8의 배수로 정렬하기 위한 상수
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7) // size를 8의 배수로 정렬하는 매크로 함수
#define SIZE_T_SIZE (ALIGN(sizeof(size_t))) // size_t 타입 변수의 크기를 8의 배수로 정렬한 크기입니다
#define WSIZE 4 // 워드와 더블워드의 크기를 각각 4바이트와 8바이트로 정의한 매크로 상수
#define DSIZE 8
#define CHUNKSIZE (1 << 12) // 힙 확장을 위한 기본 크기 (= 초기 빈 블록의 크기)
#define MAX(x, y) ((x) > (y) ? (x) : (y)) //x와 y 중 더 큰 값을 반환하는 매크로 함수
#define PACK(size, alloc) ((size) | (alloc)) // size와 할당 비트를 결합, header와 footer에 저장할 값
#define GET(p) (*(unsigned int *)(p)) // 주소 p에 위치한 값을 읽어옵니다 (포인터라서 직접 역참조 불가능 -> 타입 캐스팅)
#define PUT(p, val) (*(unsigned int *)(p) = (val)) // 주소 p에 값을 저장합니다
#define GET_SIZE(p) (GET(p) & ~0x7) // 주소 p에 위치한 메모리 블록의 크기를 반환 사이즈 (~0x7: ...11111000, '&' 연산으로 뒤에 세자리 없어짐)
#define GET_ALLOC(p) (GET(p) & 0x1) // 주소 p에 위치한 메모리 블록의 할당 여부를 반환
#define HDRP(bp) ((char *)(bp) - WSIZE) // Header 포인터
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // Footer 포인터
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE))) // 다음 블록의 포인터
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) // 이전 블록의 포인터
static char *heap_listp; // 초기 힙 메모리 공간의 포인터를 저장하는 전역 변수
static void *extend_heap(size_t words); // 개수의 워드 크기만큼 힙 메모리 공간을 늘리고, 새로운 블록을 만들어 반환
static void *coalesce(void *bp); // 현재 블록 bp와 인접한 블록이 비어있으면 하나의 큰 블록으로 병합
static void *find_fit(size_t asize); // 요청한 크기 asize에 맞는 비어있는 블록을 찾아 반환
static void place(void *bp, size_t asize); // bp 블록에 asize 크기만큼의 메모리를 할당
int mm_init(void)
{
// 초기화를 위해 4 워드 크기의 힙 공간을 할당합니다.
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *) -1)
return -1;
// 블록을 할당하기 위해 Prologue Header와 Footer를 설정합니다.
PUT(heap_listp, 0);
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1));
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1));
// Epilogue Header를 설정합니다.
PUT(heap_listp + (3 * WSIZE), PACK(0, 1));
// 힙 시작점 주소를 Prologue Header 이후로 변경합니다.
heap_listp += (2 * WSIZE);
// 초기 힙 확장을 시도합니다.
if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
return -1;
return 0;
}
static void *extend_heap(size_t words)
{
char *bp;
size_t size;
// 요청한 워드 수에 기반하여 메모리 크기를 계산합니다.
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
// mem_sbrk 함수를 사용하여 힙 확장을 시도합니다.
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL;
// 새 블록의 헤더와 푸터를 설정합니다.
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
// Epilogue Header를 설정합니다.
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
// 인접한 블록이 free 블록이면 coalesce 합니다.
return coalesce(bp);
}
void *mm_malloc(size_t size)
{
size_t asize;
size_t extendsize;
char *bp;
// 할당할 크기가 0인 경우 NULL을 반환합니다.
if (size == 0)
return NULL;
// 요청한 크기에 기반하여 할당할 블록의 크기를 계산합니다.
if (size <= DSIZE)
asize = 2 * DSIZE;
else
asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
// 할당 가능한 free 블록을 찾습니다.
if ((bp = find_fit(asize)) != NULL) {
// 찾은 블록에 할당을 진행합니다.
place(bp, asize);
return bp;
}
// 할당 가능한 free 블록을 찾지 못한 경우 힙을 확장합니다.
extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
return NULL;
// 확장한 힙에 새로운 블록을 할당합니다.
place(bp, asize);
return bp;
}
void mm_free(void *bp)
{
size_t size = GET_SIZE(HDRP(bp));
// 블록의 헤더와 푸터에 할당 상태를 변경하여 free로 설정합니다.
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
// 인접한 free 블록이 있는 경우 병합(coalesce)을 수행합니다.
coalesce(bp);
}
static void *coalesce(void *bp)
{
// 이전 블록과 다음 블록의 할당 여부와 크기를 가져옵니다.
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
if (prev_alloc && next_alloc) {
// 이전 블록과 다음 블록이 모두 할당되어 있으면 병합하지 않고 현재 블록을 반환합니다.
return bp;
}
else if (prev_alloc && !next_alloc) {
// 이전 블록은 할당되어 있고 다음 블록은 할당되어 있지 않으면 다음 블록을 현재 블록에 통합합니다.
// 현재 블록의 크기를 증가시키고, 헤더와 푸터를 업데이트합니다.
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
}
else if (!prev_alloc && next_alloc) {
// 이전 블록은 할당되어 있지 않고 다음 블록은 할당되어 있으면 이전 블록을 현재 블록에 통합합니다.
// 이전 블록의 크기를 증가시키고, 헤더와 푸터를 업데이트합니다.
// 이전 블록의 주소를 현재 블록으로 변경합니다.
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
}
else {
// 이전 블록과 다음 블록이 모두 할당되어 있지 않으면 이전 블록과 다음 블록을 현재 블록에 통합합니다.
// 이전 블록과 다음 블록의 크기를 추가하여 현재 블록의 크기를 증가시키고, 헤더와 푸터를 업데이트합니다.
size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
}
return bp;
}
void *mm_realloc(void *ptr, size_t size)
{
void *oldptr = ptr;
void *newptr;
size_t copySize;
newptr = mm_malloc(size);
if (newptr == NULL)
return NULL;
copySize = GET_SIZE(HDRP(oldptr));
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize);
mm_free(oldptr);
return newptr;
}
static void *find_fit(size_t asize)
{
void *bp;
// 가용 블록을 탐색하면서 요청한 크기보다 크거나 같은 가용 블록을 찾습니다.
for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
return bp;
}
}
return NULL;
}
static void place(void *bp, size_t asize)
{
size_t csize = GET_SIZE(HDRP(bp));
if ((csize - asize) >= (2*DSIZE)) {
// 남은 공간이 분할 가능한 최소 블록 크기(DSIZE)보다 크면 블록을 분할합니다.
// 현재 블록을 할당된 상태로 표시하고 크기를 asize로 설정합니다.
// 남은 공간을 가진 새로운 가용 블록을 생성합니다.
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
bp = NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(csize-asize, 0));
PUT(FTRP(bp), PACK(csize-asize, 0));
}
else {
// 남은 공간이 분할 가능한 최소 블록 크기(DSIZE)보다 작으면 전체 블록을 할당합니다.
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}Implicit Free List를 이용해 malloc을 구현하면서 어려웠던 점은 몇 가지가 있었습니다.
첫째로, 각 블록의 헤더와 푸터를 어떻게 관리할지에 대한 고민이 있었습니다. 특히, 블록의 크기와 할당 여부를 헤더와 푸터에 모두 저장해야 했는데, 이 과정에서 메모리 정렬에 대한 이해도 필요했습니다.
둘째로, free 메모리 블록의 연결 리스트를 관리하는 과정에서, 이전 블록과 다음 블록을 어떻게 찾아서 연결해야 할지에 대한 고민이 있었습니다. 특히, free 블록의 크기가 일정하지 않기 때문에 이를 어떻게 처리할지에 대한 고민이 필요했습니다.
셋째로, 할당된 블록을 반환하면서, 이전 블록과 다음 블록이 free 상태인 경우 이를 합쳐서 단편화를 해소해야 했습니다. 이 때, 합쳐진 블록의 크기와 할당 여부를 적절하게 업데이트해 주어야 했습니다.
Implicit Free List를 이용해 malloc을 구현하면서 느낀 점은, 메모리 할당과 해제에 대한 기본적인 이해가 중요하다는 것이었습니다. 또한, 메모리 단편화에 대한 이해도 필요하다는 것을 느꼈습니다. 이를 통해 malloc과 free 함수의 동작 방식을 이해할 수 있었고, 이를 기반으로 메모리 할당 및 해제 관련 문제를 해결할 수 있는 능력을 기를 수 있었습니다
