[학습] Malloc lab (동적 메모리 할당)

UBIN·2023년 5월 20일
explicit listimplicit listmalloc동적 메모리 할당기
0
post-custom-banner

동적 메모리 할당

입력받을 데이터의 크기를 정확히 알 수 없을 때 충분한 공간적 여유를 가지고 미리 고정된 크기로 메모리를 할당 받을 수 있다. 하지만 설정한 크기보다 작은 데이터가 들어오게 된다면 메모리 공간이 낭비된다.

런타임시에 크기를 알 수 있는 자료구조에 대해 동적으로 필요한 만큼의 메모리만을 할당받아 사용하게 된다면 효율적으로 메모리를 관리할 수 있다.

메모리 영역은 크게 코드, 데이터, 힙, 스택 영역으로 나뉜다. 이중 동적 메모리 할당기는 힙이라고 하는 프로세스의 가상 메모리 영역을 관리한다.
스택 영역은 높은 주소 -> 낮은 주소로 확장해나가는 반면 힙 영역은 낮은 주소 -> 높은 주소로 확장해나간다. 힙의 꼭대기를 가르키는 변수가 있는데 brk라고 한다.

할당기 요구사항

  1. 임의의 요청순서 처리하기
    -> 어떠한 순서로 malloc / free를 요청하는지 알 수 없다. 즉, malloc -> free 순으로 요청이 온다는 보장이 없으니 임의의 순서를 처리할 수 있어야 한다.

  2. 요청에 즉시 응답하기
    -> 요청 순서를 변경하거나 요청을 버퍼에 저장할 수 없다.

  3. 힙만 사용하기

  4. 블록 정렬하기
    -> 어떤 종류의 데이터 객체라도 저장할 수 있는 방식으로 정렬해야한다.

  5. 할당된 블록을 수정하지 않기

할당기 구현

32bit 모드일 경우에는 주소가 항상 8의 배수인 블록을 리턴.
64bit 모드일 경우에는 주소가 항상 16의 배수인 블록을 리턴.
앞으로 구현해 나갈 할당기는 32bit 모드이다.

가용 블럭 탐색 방법

  1. first-fit
    -> 사용 가능한 블럭을 처음부터 탐색해서 크기가 맞는 블럭이 있다면 바로 선택한다.
    -> 대체로 앞부분에 작은 크기의 가용블럭, 뒷부분에 큰 크기의 가용블럭이 남기 때문에 큰 가용 블럭을 필요로 할 때에는 오래걸린다.

  2. next-fit
    -> 마지막으로 검사한 블럭부터 탐색한다.
    -> 가용블럭을 찾지 못했다면 앞에서부터 다시 검사하는것이 아닌 확장을 한다.
    -> 메모리 이용도가 낮아질 수 있다.

  3. bset-fit
    -> 처음부터 끝까지 탐색을 하고 크기가 딱 맞는 블럭을 선택한다.
    -> 메모리 이용도는 좋지만 속도가 느리다.

단편화

메모리 이용도에 대해 더 살펴보자면 단편화라는 것이 있다.
단편화는 낮은 메모리 이용도의 주요 원인이다.

내부 단편화

위에서 언급했듯이 블럭의 주소는 항상 8의 배수 또는 16의 배수를 리턴하게 된다. 일단 32bit 모드를 기준으로 설명하겠다.

현재 필요한 공간이 1~8byte라고 가정하자. Header + Footer = 8byte는 기본적으로 가져가게 되고, 8byte 정렬을 위해서 1~4byte만 필요하다고 해도 8byte의 영역을 추가로 늘려야한다.
즉, 1~4byte든 5~8byte든 총 16byte를 필요로 한다. 8byte가 데이터 저장을 위해 늘린 공간이다. 이 때 정렬을 위해 추가된 메모리가 발생하는 것을 내부 단편화라 한다.

외부 단편화

총 메모리 공간은 충분하지만 해당 공간이 연속적으로 존재하지 않아 할당할 수 없는 현상을 외부 단편화라 한다. 내부 단편화는 할당기 구현에 의존하기 때문에 예측하기 쉬운 반면 외부 단편화는 미래의 요청에 대응해야 하기 때문에 예측이 어렵다.

Implicit list

가용블럭 외에도 할당된 블럭까지 포함하여 탐색을 진행한다. 모든 블럭을 탐색하기 때문에 속도가 느리다. 처음부터 탐색하는 first-fit 방식이 아닌 마지막 검사한 블럭부터 탐색하는 next-fit 방식으로 성능을 향상 시킬 수 있다.

구현하기에 앞서 다음 함수들을 살펴보자.

void mem_init(void) {
	// 20MB 길이의 영역을 할당 받고 시작 주소 초기화
    if ((mem_start_brk = (char *)malloc(MAX_HEAP)) == NULL) {
	fprintf(stderr, "mem_init_vm: malloc error\n");
	exit(1);
    }

    mem_max_addr = mem_start_brk + MAX_HEAP;
    mem_brk = mem_start_brk;
}

힙 영역으로 최대 20MB까지 쓸 수 있도록 제한을 두고 시작한다.

void *mem_sbrk(int incr) {
    char *old_brk = mem_brk;

    if ( (incr < 0) || ((mem_brk + incr) > mem_max_addr)) {
	errno = ENOMEM;
	fprintf(stderr, "ERROR: mem_sbrk failed. Ran out of memory...\n");
	return (void *)-1;
    }
    mem_brk += incr;
    return (void *)old_brk;
}

힙 영역의 끝을 가르키는 포인터 mem_brk가 있다. 힙 영역을 확장시킬때마다 증가량 만큼 이동시켜준다.

// 블럭의 값 얻기
#define GET(p)      	(*(unsigned int *)(p))
// 블럭에 값 쓰기	
#define PUT(p, val) 	(*(unsigned int *)(p) = (val))	

// ~011 과 & 연산을 하면 블럭 size 얻음
#define GET_SIZE(p)		(GET(p) & ~0x7)	
// 1과 & 연산을 하면 할당 여부 얻음
#define GET_ALLOC(p)    (GET(p) & 0x1)

// char* 형으로 선언한 이유 WSIZE byte만큼 이동하기 위해
// int* 형으로 선언했다면 WSIZE를 빼주면 16byte를 이동하게 됨

// bp에서 4byte 앞으로 이동. 즉, 1칸 앞으로
#define HDRP(bp)		((char *)(bp) - WSIZE)
// bp에서 (size - 8)byte만큼 뒤로 이동. 즉, (size - 8) / 4칸 뒤로
#define FTRP(bp)        ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)	

// bp에서 현재 블럭 사이즈만큼 뒤로 이동 -> 현재 블럭의 header로 가서 사이즈 얻어오면 됨
#define NEXT_BLKP(bp)   ((char *)(bp) + GET_SIZE(((char *)(bp)-WSIZE)))
// bp에서 이전 블럭 사이즈만큼 앞으로 이동 -> 이전 블럭의 footer로 가서 사이즈 얻어오면 됨
#define PREV_BLKP(bp)   ((char *)(bp) - GET_SIZE(((char *)(bp)-DSIZE)))

구현 이슈

  1. find-fit
    -> 가용블럭을 어떻게 찾을 것인가

  2. place
    -> 선택된 가용블럭에 메모리를 어떻게 배치 할 것인가

  3. coalesce
    -> 가용블럭들끼리의 병합은 어떻게 할 것인가

implicit - first fit 코드

// 첫 블럭을 가르키는 포인터
static char *heap_listp;

int mm_init(void) {
    if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
        return -1;

    PUT(heap_listp, 0);
    PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1));
    PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1));
    PUT(heap_listp + (3 * WSIZE), PACK(0, 1));
    
    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;
    
    if ((long)(bp = mem_sbrk(size)) == -1)
        return NULL;
        
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0,1));
    
    return 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) {
        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 if (!prev_alloc && !next_alloc) {
        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_malloc(size_t size) {
    size_t asize;
    size_t extendsize;
    char *bp;

    if (size == 0)
        return NULL;

    if (size <= DSIZE)
        asize = 2 * DSIZE;
    else
        asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);

    if ((bp = find_fit(asize)) != NULL) {
        place(bp, asize);
        return bp;
    }

    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
        return NULL;
        
    place(bp, asize);

    return bp;
}

static void *find_fit(size_t asize) {
    void *bp = heap_listp;

    while (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)) {
        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 {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

void mm_free(void *ptr) {
    size_t size = GET_SIZE(HDRP(ptr));
    PUT(HDRP(ptr), PACK(size, 0));
    PUT(FTRP(ptr), PACK(size, 0));
    coalesce(ptr);
}

먼저 mm_init 함수를 실행해보자. (extend_heap 함수를 실행하기 전까지)
1칸당 4byte의 크기를 가진다.

mm_init 함수를 마저 실행하면 기본으로 설정되어있는 CHUNKSIZE = 4KB 공간을 확장하게 된다.
현재의 힙의 끝 brk가 확장될 블럭의 포인터가 된다.
하지만 이후의 예시를 들기 위해 4KB가 아닌 40byte를 늘린다고 가정하자.

이 상태에서 11byte의 공간을 할당받아보자. 8byte 정렬을 위해 데이터를 위한 공간은 16byte가 되고 header와 footer를 포함해서 총 24byte의 공간을 할당받게 된다.

find_fit을 통해 heap_listp부터 쭉 검사하면서 40 / 0 블럭을 선택하게 된다.
8byte정렬을 위해 header, footer 포함 블럭은 16, 24, 32 .... 의 크기를 갖게 된다.
40에서 24를 할당 받을 때 남는 공간은 16으로 최소 블럭크기를 만족한다.
만약 최소 블럭크기를 만족하지 못할 때 즉, 32byte를 할당 받게 된다면 필요한 크기는 32이지만 40전체를 사용해야 한다. 이것이 내부 단편화이다.

외부 단편화를 해결하기 위한 coalesce 작업은 extend_heap()과 free()를 할 때마다 실행하게 된다. 좌우 블럭을 살피며 가용여부를 확인 후 적절한 위치로 블럭포인터를 옮긴 후 반환하게 된다.

이제 next_fit 방식을 살펴보자. 간단하다.
first_fit의 경우 heap_listp가 항상 처음을 가리키고 있다. 이 포인터를 coalesce 함수를 실행하고 bp를 반환하기 전에 heap_listp = bp로 갱신해주면 된다.

implicit - next fit 코드

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) {
        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 if (!prev_alloc && !next_alloc) {
        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);
    }
    
    heap_listp = bp;

    return bp;
}

이러면 마지막으로 검사했던 블럭부터 끝까지 검사하며 적절한 크기의 가용블럭을 찾지 못했을 때 extend_heap()을 실행하게 된다.

best-fit도 간단하다. 처음부터 끝까지 검사하면서 가장 크기가 알맞는 블럭을 캐싱해뒀다가 반환하면 된다.

implicit - best fit 코드

static void *find_fit(size_t asize) {
    void *bp = heap_listp;
    void *bestfit_bp = NULL;

    while (GET_SIZE(HDRP(bp)) != 0) {
        bp = NEXT_BLKP(bp);

        if (!GET_ALLOC(HDRP(bp)) && asize <= GET_SIZE(HDRP(bp))) {
            if (bestfit_bp == NULL || (GET_SIZE(HDRP(bp)) - asize) < (GET_SIZE(HDRP(bestfit_bp)) - asize))
                bestfit_bp = bp;
        }
    }
    
    return bestfit_bp;
}

Explicit list

전체 블록을 탐색하는게 아닌 가용블럭만 탐색하는 것이다.
아래 그림과 같이 블럭의 빈 공간에 다른 가용 블럭을 가르키는 포인터를 만들어 두는 것이다.

bp의 역참조에는 이전 가용블럭의 주소
bp + WSIZE의 역참조에는 다음 가용블럭의 주소

explicit list - LIFO

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"

static void place(void *, size_t );
static void *find_fit(size_t );
static void *coalesce(void *);
static void *extend_heap(size_t );
static void insert_free_block(void *);
static void delete_free_block(void *);

team_t team = {
    /* Team name */
    "WEEK06-TEAM07",
    /* First member's full name */
    "박유빈",
    /* First member's email address */
    "a44121078@gmail.com",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""
};

#define ALIGNMENT           8
#define ALIGN(size)         (((size) + (ALIGNMENT - 1)) & ~0x7)
#define SIZE_T_SIZE         (ALIGN(sizeof(size_t)))

#define WSIZE               4
#define DSIZE               8
#define CHUNKSIZE           (1<<12)
#define MAX(x, y)           ((x) > (y) ? (x) : (y))
#define PACK(size, alloc)   ((size) | (alloc))
#define GET(p)              (*(unsigned int *)(p))
#define PUT(p, val)         (*(unsigned int *)(p) = (val))

#define GET_SIZE(p)         (GET(p) & ~0x7)
#define GET_ALLOC(p)        (GET(p) & 0x1)

// implicit에서 새로 추가된 매크로 함수
#define GET_PRED(bp)        (*(void **)(bp))
#define GET_SUCC(bp)        (*(void **)((char *)(bp) + WSIZE))

#define HDRP(bp)            ((char *)(bp) - WSIZE)  //
#define FTRP(bp)            ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
#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;

int mm_init(void) {   
    if ((heap_listp = mem_sbrk(8 * WSIZE)) == (void *)-1)
        return -1;

    PUT(heap_listp + (0 * WSIZE), 0);
    PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1));
    PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1));
    PUT(heap_listp + (3 * WSIZE), PACK(2 * DSIZE, 0));
    PUT(heap_listp + (4 * WSIZE), NULL);
    PUT(heap_listp + (5 * WSIZE), NULL);
    PUT(heap_listp + (6 * WSIZE), PACK(2 * DSIZE, 0));
    PUT(heap_listp + (7 * WSIZE), PACK(0, 1));

    heap_listp += (2 * DSIZE);

    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;

    if ((long)(bp = mem_sbrk(size)) == -1)
        return NULL;

    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));

    return 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) {
        delete_free_block(NEXT_BLKP(bp));
        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) {
        delete_free_block(PREV_BLKP(bp));
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }
    else if (!prev_alloc && !next_alloc) {
        delete_free_block(PREV_BLKP(bp));
        delete_free_block(NEXT_BLKP(bp));
        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);                   
    }

    insert_free_block(bp);
    return bp;
}

static void insert_free_block(void *bp) {
    GET_SUCC(bp) = heap_listp;

    if (heap_listp != NULL)
        GET_PRED(heap_listp) = bp;

    heap_listp = bp;
}

static void delete_free_block(void *bp) {
    if (bp == heap_listp)
    {
        heap_listp = GET_SUCC(heap_listp);
        return;
    }

    GET_SUCC(GET_PRED(bp)) = GET_SUCC(bp);

    if (GET_SUCC(bp) != NULL)
        GET_PRED(GET_SUCC(bp)) = GET_PRED(bp);
}

void *mm_malloc(size_t size) {
    size_t asize;
    size_t extendsize;
    char *bp;

    if (size == 0)
        return NULL;

    if (size <= DSIZE)
        asize = 2 * DSIZE;
    else
        asize = DSIZE * ((size + 2 * DSIZE - 1) / DSIZE);

    if ((bp = find_fit(asize)) != NULL) {
        place(bp, asize);
        return bp;
    }

    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
        return NULL;

    place(bp, asize);

    return bp;
}

void mm_free(void *ptr) {
    size_t size = GET_SIZE(HDRP(ptr));
    PUT(HDRP(ptr), PACK(size, 0));
    PUT(FTRP(ptr), PACK(size, 0));
    coalesce(ptr);
}

static void *find_fit(size_t asize) {
    void *bp = heap_listp;

    while (bp != NULL) {
        if ((asize <= GET_SIZE(HDRP(bp))))
            return bp;
        bp = GET_SUCC(bp);
    }

    return NULL;
}

static void place(void *bp, size_t asize) {
    size_t csize = GET_SIZE(HDRP(bp));

    delete_free_block(bp);

    if ((csize - asize) >= (2 * DSIZE)) {
        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));
        insert_free_block(bp);
    }
    else {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

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;
}

가용블럭들만 이중연결리스트로 묶어 관리하는 방식이다.
새로운 가용블럭이 생기면 맨 앞에 추가해주는 LIFO으로 구현하였다.

https://github.com/krafton-jungle/KJ2B-W05-07/blob/week06/carrotcookie/Week06/carrotcookie/mm.c

profile
UBIN
ubin
이전 포스트

[학습] AVL-Tree, B-Tree

다음 포스트

[Pintos] Project3 Stack Growth 6/20

post-custom-banner

0개의 댓글