malloc lab binary 케이스 메모리 이용률 개선하기

#MallocLab 96점 받는법

segregated free list를 적용하고, realloc을 개선한 버전을 돌려보았다.

./mdrver -V 를 돌려보자

<2의 제곱수 적용전>

위와 같은 결과를 받았다 다 좋은데 7, 8번 케이스만 메모리 활용도가 반토막 나있다!

해당 케이스는 traces 폴더의 binary.rep 과 binary2.rep 이다. 직접 파일을 까보자.

까보면

1024100
12000
24000
1
a 0 16
a 1 112
a 2 16
a 3 112
a 4 16
a 5 112
a 6 16
a 7 112
a 8 16
a 9 112
a 10 16
a 11 112
a 12 16
a 13 112
a 14 16
a 15 112
a 16 16
a 17 112
a 18 16
a 19 112
a 20 16
a 21 112
a 22 16

// 생략

f 1675
f 1677
f 1679
f 1681
f 1683
f 1685
f 1687
f 1689
f 1691
f 1693
f 1695
f 1697
f 1699
f 1701
f 1703
f 1705
f 1707

// 생략

a 9785 128
a 9786 128
a 9787 128
a 9788 128
a 9789 128
a 9790 128
a 9791 128
a 9792 128
a 9793 128
a 9794 128
a 9795 128
a 9796 128
a 9797 128
a 9798 128
a 9799 128
a 9800 128
a 9801 128
a 9802 128
a 9803 128
a 9804 128

로 되어 있다.

나의 경우에는

// size list num
#define SIZE_NUM 29  // 2**4 ~ 2**32 (byte) 4GB 까지

이런식으로 리스트를 나누었다.

그래서 해당 케이스를 돌리면

 

1. 112 size 블록을 계속 채워넣고

 

2. 112 size 블록을 듬성 듬성 free 해서 112 사이즈의 가용 블럭들이 남게되고.

 

 

3. 128 사이즈를 넣으려니 앞의 112 사이즈의 가용블록들을 지나치고 맨뒤에 128 사이즈의 블록들을 자꾸 추가하게 된다.

 

 

그래서 메모리 이용률이 반토막이 났던 것이다!!
범인 검거.

 

 

개선방안

그래서 나는 새로 malloc으로 블록을 새로 넣어줄때 size를 2의 제곱수로 변환해서 넣어줘서 해결했다.

// x 보다 한단계 더큰 2의 제곱수로 올림.
int find_next_power(int x) {
    if (x < 1) {
        return 1;
    }

    int power = 1;
    while (power < x) {
        power *= 2;
    }
    return power;
}


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

    if (size == 0) return NULL;

    if (size <= CHUNKSIZE) {                        <<<<< chunk보다 큰 2의 제곱수로 변환해주면 값이 너무 커지기 때문.
        size = find_next_power(size);                <<<<< 핵심 변경부분
    }

 

<2의 제곱수로 size up 적용 후>

96점 야호!

 

내부 단편화가 커지는 단점이 생겼지만 바이너리 부분의 외부단편화를 줄이는 이득을 취했다.

하지만 이게 진짜로 메모리의 성능을 높인것인지 단순히 채점방식때문에 높은 점수를 받은 것인지 아직 고민이 더필요하다.

 

해당 질문에 대한 나의 답 2024/04/24

내부 단편화는 증가할 수 있지만, 외부 단편화를 크게 줄일 수 있다. 외부 단편화가 준다면 관리해야 할 블럭들이 줄어든다. 즉, 검색하고, 재할당하고, 또 블럭을 저장하는 테이블도 줄일 수 있다. 

내부 단편화 >> 메모리 공간 낭비

외부 단편화 >> 메모리 효율성 감소

메모리가 할당되는 패턴마다 내부와 외부단편화 사이의 균형을 맞추는 것이 달라져서 적절한 전략을 사용해야한다. 해당 말록랩 테스트 케이스에선 데이터 크기들이 작은 경우가 많고 큰 경우에도 2의 제곱수보다 살짝 작은 사이즈들을 넣어서 모든 케이스에 대해 2의 제곱수로 늘려서 넣어주는 전략이 유용했고 높은 점수를 받는것도 합당했다.

 

 

전체코드

펼쳐보기 👇

https://github.com/T3rryAhn/MallocLab/blob/segregated_free_list/mm.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 "mm.h"

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.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 */
    "team1",
    /* First member's full name */
    "Terry Ahn",
    /* First member's email address */
    "t3rryahn.dev@gmail.com",
    /* 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

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)

#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

/*
 * macro
 */

#define WSIZE 4             // word size (bytes)
#define DSIZE 8             // double word size (bytes)
#define CHUNKSIZE (1 << 12)  // increase heap size to 4KB (4096 bytes) 메모리 페이지 크기가 4KB.

#define MAX(x, y) ((x) > (y) ? (x) : (y))

// pack a size and allocated bit into a word
#define PACK(size, alloc) ((size) | (alloc))  // size + block available. OR 연산으로 헤더에 넣을 정보를 만듬 사이즈 + 가용여부(끝 3자리).

// Read and write a word at address p
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (int)(val))

// Read the size and allocated fields from address p
#define GET_SIZE(p) (GET(p) & ~0x7)  // 00000111 의 보수(~) 를 취해서 11111000 을 가져와 AND 연산을 통해 블록 사이즈만 가져오겠다.
#define GET_ALLOC(p) (GET(p) & 0x1)  // 00000001 과 AND 연을 통해 헤더에서 가용여부만 가져오겠다.

// Given block ptr bp, compute address of its header and footer
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

// Given block ptr bp, compute address of next and previous blocks
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

// 가용리스트 명시적 주소 읽기 prev/next 블록이 가리키는 곳으로 가는 이중포인터 //byte 형식의 주솟값을 가르키는 포인터로 변환해서 바이트 단위로 연산하겠다.
#define PREV_FREE_P(bp) (*(char **)(bp))
#define NEXT_FREE_P(bp) (*(char **)(bp + WSIZE))

// size list num
#define SIZE_NUM 29  // 2**4 ~ 2**32 (byte) 4GB 까지

// list
static char *heap_listp;  // 힙 포인터
void *seg_free_list[SIZE_NUM];

// function prototype
int mm_init(void);
void mm_free(void *bp);
void *mm_malloc(size_t size);
void *mm_realloc(void *bp, size_t size);
static void *extend_heap(size_t words);
static void *find_fit(size_t asize);
static void *coalesce(void *bp);
static void place(void *bp, size_t asize);
static void add_block_to_freelist(void *bp);
static void remove_block(void *bp);

int find_list_index(size_t size);
int find_next_power(int x);

/*
 * mm_init - initialize the malloc package.
 */
int mm_init(void) {
    // seg_free_list 초기화
    for (int i = 0; i < SIZE_NUM; i++) {
        seg_free_list[i] = NULL;
    }

    if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1) {
        return -1;
    }
    PUT(heap_listp, 0);                             // padding for 2 word 배수
    PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1));  // prologue header
    PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1));  // prologue footer
    PUT(heap_listp + (3 * WSIZE), PACK(0, 1));      // epilogue header

    return 0;
}

/*
 * exxtend_heap 힙을 특정 사이즈만큼 증가. 새 가용 블록 만들기
 */
static void *extend_heap(size_t words) {
    char *bp;
    size_t size;
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;

    bp = mem_sbrk(size);
    if (bp == (void *)-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);
}

// find list index 집어넣을 사이즈에 적합한 리스트 찾기
int find_list_index(size_t size) {
    int index = 0;
    size = (size > 4) ? size : 4;

    while ((1 << (index + 4)) < size && index < SIZE_NUM - 1) {
        index++;
    }

    return index;
}

// 가용블록 병합 함수. 앞뒤 가용블럭과 free한 블럭 합치기
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) {
        remove_block(PREV_BLKP(bp));
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        bp = PREV_BLKP(bp);
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }
    // 다음 블록과 병합
    if (!next_alloc) {
        remove_block(NEXT_BLKP(bp));
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }

    add_block_to_freelist(bp);
    return bp;
}

// 가용리스트 추가 함수
static void add_block_to_freelist(void *bp) {
    int seg_list_index = find_list_index(GET_SIZE(HDRP(bp)));

    PREV_FREE_P(bp) = NULL;

    if (seg_free_list[seg_list_index] == NULL) {
        NEXT_FREE_P(bp) = NULL;
    } else {
        NEXT_FREE_P(bp) = seg_free_list[seg_list_index];
        PREV_FREE_P(seg_free_list[seg_list_index]) = bp;
    }

    seg_free_list[seg_list_index] = bp;
}

// block을 free 할때 가용리스트 업데이트
static void remove_block(void *bp) {
    int seg_list_index = find_list_index(GET_SIZE(HDRP(bp)));

    if (PREV_FREE_P(bp)) {
        NEXT_FREE_P(PREV_FREE_P(bp)) = NEXT_FREE_P(bp);
    } else {
        seg_free_list[seg_list_index] = NEXT_FREE_P(bp);
    }

    if (NEXT_FREE_P(bp)) {
        PREV_FREE_P(NEXT_FREE_P(bp)) = PREV_FREE_P(bp);
    }
}

/*
 * find fit  // first fit search
 */
static void *find_fit(size_t asize) {
    void *bp = NULL;
    int index = find_list_index(asize);

    while (index < SIZE_NUM) {
        for (bp = seg_free_list[index]; bp != NULL; bp = NEXT_FREE_P(bp)) {
            size_t current_size = GET_SIZE(HDRP(bp));
            if (asize <= current_size) {
                return bp;
            }
        }
        index++;
    }

    return NULL;
}

/*
 * place 가용블록에 데이터를 넣고 필요하다면 나머지 부분이 최소 블록크기와
 * 같거나 크면 분할하는 함수
 */
static void place(void *bp, size_t asize) {
    size_t csize = GET_SIZE(HDRP(bp));
    remove_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));

        coalesce(bp);
    } else {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

// x 보다 한단계 더큰 2의 제곱수로 올림.
int find_next_power(int x) {
    if (x < 1) {
        return 1;
    }

    int power = 1;
    while (power < x) {
        power *= 2;
    }
    return power;
}

/*
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */
void *mm_malloc(size_t size) {
    size_t asize;
    size_t extendsize;
    char *bp;

    if (size == 0) return NULL;

    if (size <= CHUNKSIZE) {
        size = find_next_power(size);
    }

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

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

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void *bp, size_t size) {
    size_t asize;

    if (size <= 0) {
        mm_free(bp);
        return 0;
    }

    if (bp == NULL) {
        return mm_malloc(size);
    }

    size_t oldsize = GET_SIZE(HDRP(bp));

    if (size <= DSIZE) {  // malloc 할 때 처럼 블록의 size를 정형화
        asize = 2 * DSIZE;
    } else {
        asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
    }

    // 변경할 사이즈가 기존보다 작을때
    if (oldsize - DSIZE >= asize) {
        return bp;
    }

    // if next block is free and
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t next_size = GET_SIZE(HDRP(NEXT_BLKP(bp)));

    if (!next_alloc && (oldsize + next_size >= asize)) {
        remove_block(NEXT_BLKP(bp));
        PUT(HDRP(bp), PACK(oldsize + next_size, 1));
        PUT(FTRP(bp), PACK(oldsize + next_size, 1));
        return bp;
    }

    size_t prev_alloc = GET_ALLOC(HDRP(PREV_BLKP(bp)));
    size_t prev_size = GET_SIZE(HDRP(PREV_BLKP(bp)));

    if (!prev_alloc && (oldsize + prev_size >= asize)) {
        remove_block(PREV_BLKP(bp));
        bp = PREV_BLKP(bp);
        memmove(bp, NEXT_BLKP(bp), asize);
        PUT(HDRP(bp), PACK(oldsize + prev_size, 1));
        PUT(FTRP(bp), PACK(oldsize + prev_size, 1));
        return bp;
    }

    // 기존 realloc
    oldsize -= DSIZE;

    void *newp = mm_malloc(size);
    if (newp == NULL) {
        return 0;
    }

    memcpy(newp, bp, oldsize);
    mm_free(bp);
    return newp;
}