크래프톤 정글 WIL_Week06 Malloc Lab

pigpgw·2024년 8월 18일

크래프톤 정글 6기

크래프톤 정글

목록 보기

8/13

개요

6주차는 동적 메모리 할당기인 Malloc Lab을 구현하는 과제와 시스템 콜, 데이터 세그먼트, 메모리 단편화, sbrk/mmap을 공부하는 주차였다.

Malloc Lab 과제 구현

malloc lab 과제 구현 공식 Q&A

동적 메모리 할당기 구현 과제

mm.h에 선언되고 mm.c에 정의된 네 가지 함수를 구현

- mm_init()
- mm_malloc()
- mm_free()
- mm_realloc()

각 함수의 구체적인 요구사항

a) mm_init()
	- 다른 함수들이 호출되기 전에 실행됨
	- 초기 힙 영역 할당 등의 필요한 초기화 수행
	- 성공 시 0, 실패 시 -1 반환

b) mm_malloc()
	- 요청된 크기(size) 이상의 메모리 블록을 할당하고 그 포인터 반환
	- 할당된 블록은 힙 영역 내에 있어야 하며 다른 할당된 블록과 겹치지 않아야 함
	- 반환되는 포인터는 8바이트 정렬되어야 함 (libc malloc과 동일하게)

c) mm_free()
	- 주어진 포인터(ptr)가 가리키는 블록을 해제
	- 반환값 없음
	- 이전에 mm_malloc이나 mm_realloc으로 할당된, 아직 해제되지 않은 포인터만 처리 가능

d) mm_realloc()
	- 주어진 포인터(ptr)가 가리키는 메모리 블록의 크기를 변경
	- ptr이 NULL이면 mm_malloc(size)와 동일하게 동작
	- size가 0이면 mm_free(ptr)와 동일하게 동작
	- ptr이 NULL이 아니면, 이전에 mm_malloc이나 mm_realloc으로 반환된 포인터여야 함
	- 새 블록의 주소는 이전 블록과 같을 수도, 다를 수도 있음
	- 새 블록의 내용은 이전 블록의 내용을 유지 (크기 변경에 따라 일부만 유지될 수 있음)
	- 크기가 늘어난 경우, 추가된 부분은 초기화되지 않음

구현 시 주의사항
	- 제공된 mm.c 파일을 시작점으로 사용하여 수정
	- 필요한 경우 추가적인 private static 함수들을 정의할 수 있음
	- 표준 C 라이브러리의 malloc 구현과 비교될 예정
	- 메모리 관리의 정확성과 효율성을 고려해야 함

이 미션은 효율적이고 정확한 메모리 할당, 해제, 재할당 시스템을 구현하는 것을 목표로한다.

미션 요구사항 부가 설명

구현을 표준 C 라이브러리(libc)에서 제공하는 malloc 버전과 비교
libc malloc은 항상 8바이트로 정렬된 페이로드 포인터를 반환하므로, 여러분의 malloc 구현도 마찬가지로 항상 8바이트로 정렬된 포인터를 반환해야 함
mm_free: mm_free 루틴은 ptr이 가리키는 블록을 해제합니다. 아무것도 반환하지 않습니다. 이 루틴은 전달된 포인터(ptr)가 이전 mm_malloc 또는 mm_realloc 호출에 의해 반환되었고 아직 해제되지 않았을 때만 작동이 보장됩니다.
mm_realloc: mm_realloc 루틴은 다음과 같은 제약 조건을 가진 최소 size 바이트의 할당된 영역에 대한 포인터를 반환해야한다.

주요 테스트 항목

mdriver.c로 mm.c 패키지의 정확성, 공간 활용도, 처리량을 테스트

정확성: mm.c에 구현된 메모리 할당 및 해제 함수들(mm_malloc, mm_free, mm_realloc 등)이 올바르게 작동하는지 확인
공간 활용도: 여러분의 할당기가 메모리를 얼마나 효율적으로 사용하는지 평가합니다. 이는 실제로 사용되는 메모리와 할당된 전체 메모리의 비율을 측정
처리량: 여러분의 할당기가 얼마나 빠르게 작동하는지 측정. 초당 수행할 수 있는 메모리 작업의 수를 계산

책에 주어진 기본 코드 뜯어보기

책에는 기본적인 묵시적 리스트 방식중 하나인 first_fit 코드가 기본적으로 제공되어 있었다. 하지만 기본 코드는 완전하지 않은 코드로 말 그대로 프로그램이 동작은 가능하여 최소한의 점수를 받을 수 있는 정도의 코드만 주어져있었다. 아직 c언어가 익숙하지 않았고 매크로도 잘 모르기에 책에 주어진 코드를 먼저 공부하였다.

매크로 정리

#define WSIZE 4             /* 워드 크기 (바이트) */
#define DSIZE 8             /* 더블 워드 크기 (바이트) */
#define CHUNKSIZE (1<<12)   /* 힙을 이만큼 확장 (4096 바이트) */

/* 최대값을 구하는 매크로 */
#define MAX(x, y) ((x) > (y) ? (x) : (y))  // x가 y보다 크면 x를, 그렇지 않으면 y를 반환

/* 크기와 할당 비트를 하나의 워드로 묶는 매크로 */
#define PACK(size, alloc) ((size) | (alloc))  // size의 하위 3비트와 alloc 비트(0 또는 1)를 비트 OR 연산으로 결합

/* 주소 p에서 워드를 읽고 쓰는 매크로 */
#define GET(p) (*(unsigned int *)(p))  // 주소 p에서 4바이트(워드) 값을 읽어옴
#define PUT(p, val) (*(unsigned int *)(p) = (val))  // 주소 p에 4바이트(워드) 값 val을 씀

/* 주소 p의 헤더 또는 푸터에서 크기와 할당 비트를 읽어오는 매크로 */
#define GET_SIZE(p) (GET(p) & ~0x7)  // 하위 3비트를 0으로 만들어 순수한 크기 정보만 추출
#define GET_ALLOC(p) (GET(p) & 0x1)  // 최하위 비트만 추출하여 할당 여부 확인 (0: 가용, 1: 할당)

/* 블록 포인터 bp를 받아 그 블록의 헤더와 푸터의 주소를 계산하는 매크로 */
#define HDRP(bp) ((char *)(bp) - WSIZE)  // bp에서 4바이트 앞(헤더 위치)의 주소 반환
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)  // bp에서 블록 크기만큼 뒤로 간 후 8바이트 앞(푸터 위치)의 주소 반환

/* 블록 포인터 bp를 받아 이전 블록과 다음 블록의 주소를 계산하는 매크로 */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))  // 현재 블록의 크기만큼 뒤로 가서 다음 블록의 bp 반환
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))  // 이전 블록의 푸터에서 크기를 읽어 그만큼 앞으로 가서 이전 블록의 bp 반환

mm_init

int mm_init(void)
{
    // 빈 힙 생성
    if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *) -1) return -1;
    // 첫 번째 워드를 0으로 
    PUT(heap_listp, 0);
     // 두 번째 워드에 프롤로그 헤더를 설정. PACK(DSIZE,1)는 크기가 DSIZE(더블 워드 크기, 보통 8바이트)이고 할당된 상태(1)임을 나타냄
    PUT(heap_listp + (1*WSIZE), PACK(DSIZE,1));
    // 세 번째 워드에 프롤로그 푸터를 설정. 헤더와 동일한 값을 가짐
    PUT(heap_listp + (2*WSIZE), PACK(DSIZE,1));
    // 네 번째 워드에 에필로그 헤더를 설정. 크기 0, 할당 상태 1을 나타냄
    PUT(heap_listp + (3*WSIZE), PACK(0,1)); 
     // heap_listp를 프롤로그 블록 다음으로 이동시킴., 이제 첫 번째 가용 블록을 가리키게 됨
    heap_listp += (2*WSIZE);
    if (extend_heap(CHUNKSIZE/WSIZE) == NULL){
        return - 1;
    }
    return 0;
}

메모리 할당기를 초기화

mem_sbrk를 사용하여 초기 빈 힙을 생성 (4워드 크기).
정렬 패딩, 프롤로그 블록 (헤더와 푸터), 에필로그 헤더를 설정
heap_listp를 프롤로그 블록 바로 다음으로 이동시킴
extend_heap을 호출하여 CHUNKSIZE 바이트만큼 힙을 확장
초기화에 성공하면 0을, 실패하면 -1을 반환

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

이 함수는 주어진 블록을 해제하고 인접한 가용 블록들과 병합

해제할 블록의 크기를 가져옴
블록의 헤더와 푸터를 '가용' 상태로 표시 (할당 비트를 0으로 설정).
coalesce 함수를 호출하여 인접한 가용 블록들과 병합

malloc

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 = next_fit(asize)) != NULL) {
        place(bp, asize);
        recent_allocate = bp;
        return bp;
    }

    /* 적합한 블록을 찾지 못한 경우, 힙을 확장하고 블록 할당 */
    extendsize = MAX(asize,CHUNKSIZE);
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
        return NULL;
    place(bp, asize);
    recent_allocate = bp;
    return bp;
}

요청된 크기의 메모리 블록을 할당

요청된 크기를 정렬 요구사항에 맞게 조정
next_fit을 사용하여 적합한 가용 블록을 찾음
적합한 블록을 찾으면 place 함수를 호출하여 블록을 할당
적합한 블록을 찾지 못하면 힙을 확장하고 새 블록을 할당
최근 할당된 블록의 포인터를 업데이트하고 할당된 블록의 포인터를 반환

extend_heap

static void *extend_heap(size_t words){
    char *bp;
    size_t size;
    // 요청된 워드 수가 홀수인 경우, 짝수로 만들어 8바이트 정렬을 보장 8의 배수 권장
    size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;
    // mem_sbrk(size)를 호출하여 힙을 확장
    // 실패시 -1을 반환하므로, 이. ㅕㅇ우 NULL을 반환하고 함수를 종료함
    if ((long)(bp = mem_sbrk(size)) == -1){
        return NULL;
    }
    // 블록의 헤더 위치를 계산
    PUT(HDRP(bp),PACK(size,0));
    // PACK(size, 0)은 블록 크기와 할당 상태(0 = 가용)을 패키징 합니다.)
    PUT(FTRP(bp),PACK(size,0));
    // PUT은 계산된 값을 헤더에 저장
    PUT(HDRP(NEXT_BLKP(bp)),PACK(0,1));

    return coalesce(bp);
}

워드 단위의 메모리로 힙을 확장하고 초기화

요청된 크기를 더블 워드 정렬에 맞게 조정
mem_sbrk를 사용하여 힙을 확장
새로 확장된 영역에 가용 블록의 헤더와 푸터를 설정
새 에필로그 헤더를 설정
이전 블록과 새 블록을 병합하기 위해 coalesce를 호출

realloc

void *mm_realloc(void *ptr, size_t size)
{
    void *oldptr = ptr;
    void *newptr;
    size_t copySize;
    
    // 케이스 1: ptr가 NULL인 경우, 새 메모리를 할당
    if (ptr == NULL)
        return mm_malloc(size);
    
    // 케이스 2: size가 0인 경우, 메모리를 해제
    if (size == 0) {
        mm_free(ptr);
        return NULL;
    }
    
    // 새로운 크기로 메모리를 할당 
    newptr = mm_malloc(size);
    if (newptr == NULL)
        return NULL;
    
    // 복사할 데이터의 크기를 결정 (헤더와 푸터 제외)
    copySize = GET_SIZE(HDRP(oldptr)) - DSIZE;
    if (size < copySize)
        copySize = size;
    
    // 데이터를 새 위치로 복사
    memcpy(newptr, oldptr, copySize);
    // 이전 메모리 해제
    mm_free(oldptr);
    return newptr;
}

이 함수는 이미 할당된 메모리 블록의 크기를 조정

ptr가 NULL이면 새로운 메모리를 할당
size가 0이면 기존 메모리를 해제하고 NULL을 반환
새로운 크기로 메모리를 할당
복사할 데이터의 크기를 결정합니다 (헤더와 푸터 제외).
데이터를 새 위치로 복사
이전 메모리를 해제하고 새 메모리의 포인터를 반환

coalesce

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

     /* 케이스 1: 이전과 다음 블록이 모두 할당된 경우 */
    if (prev_alloc && next_alloc) {        
        return bp;
    }
     /* 케이스 2: 이전 블록은 할당되고 다음 블록은 가용한 경우 */
    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));
    }
    /* 케이스 3: 이전 블록은 가용하고 다음 블록은 할당된 경우 */
    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);
    }
    /* 케이스 4: 이전과 다음 블록이 모두 가용한 경우 */
    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);
    }
    recent_allocate = bp;
    return bp;
}

경계 태그 연결을 사용하여 가용 블록을 병합

현재 블록의 이전 블록과 다음 블록의 할당 상태를 확인
네 가지 경우에 따라 블록을 병합
- 케이스 1 : 이전과 다음 블록이 모두 할당된 경우
  - 병합하지 않음
- 케이스 2 : 이전 블록은 할당되고 다음 블록은 가용한 경우
  - 현재 블록과 다음 블록을 병합
- 케이스 3 : 이전 블록은 가용하고 다음 블록은 할당된 경우
  - 이전 블록과 현재 블록을 병합
- 케이스 4 : 이전과 다음 블록이 모두 가용한 경우
  - 이전, 현재, 다음 블록을 모두 병합
병합된 블록의 헤더와 푸터를 업데이트
recent_allocate 포인터를 업데이트하고 병합된 블록의 포인터를 반환

place

place - 요청한 블록을 가용 블록의 시작 부분에 배치하고, 나머지 부분의 크기가 최소 블록 크기와 같거나 크다면 분할

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

요청한 블록을 가용 블록의 시작 부분에 배치하고, 필요한 경우 분할

현재 가용 블록의 크기를 확인
요청한 크기를 할당하고 남은 공간이 최소 블록 크기(2*DSIZE) 이상이면
- 요청한 크기의 블록을 할당
- 남은 공간에 새 가용 블록을 생성
그렇지 않으면 전체 블록을 할당
할당된 블록의 헤더와 푸터를 업데이트

정리

구현 시도 정리

묵시적 리스트로 구현했고 묵시적 리스트에 다양한 메모리 할당 정책을 시도했다.

First_fit

static void *fist_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;
}

realloc 개선 후

void *mm_realloc(void *bp, size_t size) {
    size_t old_size = GET_SIZE(HDRP(bp));
    size_t new_size = size + (2 * WSIZE);   // 2*WISE는 헤더와 풋터

    // new_size가 old_size보다 작거나 같으면 기존 bp 그대로 사용
    if (new_size <= old_size) {
        return bp;
    }
    // new_size가 old_size보다 크면 사이즈 변경
    else {
        size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
        size_t current_size = old_size + GET_SIZE(HDRP(NEXT_BLKP(bp)));

        // next block이 가용상태이고 old, next block의 사이즈 합이 new_size보다 크면 그냥 그거 바로 합쳐서 쓰기
        if (!next_alloc && current_size >= new_size) {
            PUT(HDRP(bp), PACK(current_size, 1));
            PUT(FTRP(bp), PACK(current_size, 1));
            return bp;
        }
        // 아니면 새로 block 만들어서 거기로 옮기기
        else {
            void *new_bp = mm_malloc(new_size);
            place(new_bp, new_size);
            memcpy(new_bp, bp, new_size);  // 메모리의 특정한 부분으로부터 얼마까지의 부분을 다른 메모리 영역으로 복사해주는 함수(old_bp로부터 new_size만큼의 문자를 new_bp로 복사해라!)
            mm_free(bp);
            return new_bp;
        }
    }
}

./mdriver -v 로 전체 테케를 정확히 측정하여 공간 활용도와 처리량 확인 필요

first_fit을 구현후 realloc을 개선하고 다른 방법들도 구현해보면 좋은 경험이 될 것 같아 best_fit과 next_fit을 시도하였다. next_fit은 주변에서 구현한 사람들이 많았기에 먼저 best_fit을 구현해보았다.

best_fit

best_fit은 말 그대로 데이터와 크기가 가장 일치하는 가용 공간을 찾아서 할당하는 것이다. 당연히 가장 적합한 가용 공간을 찾기 위해서는 전체를 순회해야하기에 처리량은 느리겠지만 공간 활용도는 다른 방법에 비해 좋을것이라고 생각했다.

static void *best_fit(size_t asize) {
    void *bp;
    void *best_bp = NULL;
    // 64비트 시스템에서 표현할 수 있는 가장 큰 값으로 초기화하여 첫 번째로 찾은 적합한 블록이
    // 무조건 이 값보다 작게 되어 업데이트가 가능하게 함
    size_t min_size = 18446744073709551615; 

    // 힙을 순회하면서 가장 적합한 블록을 찾기
    for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
            // 현재 블록이 요청 크기보다 크거나 같고, 지금까지 찾은 것 중 가장 작은 블록일때 업데이트
            if (GET_SIZE(HDRP(bp)) < min_size) {
                min_size = GET_SIZE(HDRP(bp));
                best_bp = bp;
            }
        }
    }
    // best_bp를 NULL로 초기에 선언해서 찾지 못한 상태라면 NULL반환
    return best_bp;
}

./mdriver -v 로 전체 테케를 정확히 측정하여 공간 활용도와 처리량 확인 필요

realloc 개선후

void *mm_realloc(void *ptr, size_t size)
{
    // 기존 블록의 크기를 가져옵니다 (헤더에서 크기 정보를 읽음)
    size_t old_size = GET_SIZE(HDRP(ptr));
    
    // 새로운 크기를 계산합니다 (요청된 크기 + 헤더와 푸터 크기)
    size_t new_size = size + (2 * WSIZE);

    // 새 크기가 기존 크기보다 작거나 같으면 현재 블록을 그대로 사용
    if (new_size <= old_size){
        return ptr;
    }
    else {
        // 다음 블록의 할당 상태를 확인
        size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr)));
        // 현재 블록과 다음 블록의 크기 합을 계산
        size_t current_size = old_size + GET_SIZE(HDRP(NEXT_BLKP(ptr)));

        // 다음 블록이 가용 상태이고, 현재 블록과 다음 블록의 크기 합이 새로운 크기보다 크거나 같으면
        if (!next_alloc && current_size >= new_size){
            // 현재 블록과 다음 블록을 합쳐서 하나의 할당된 블록으로 만듦
            PUT(HDRP(ptr), PACK(current_size, 1));
            PUT(FTRP(ptr), PACK(current_size, 1));
            return ptr;
        }
        else {
            // 새로운 크기의 메모리 블록을 할당
            void *new_bp = mm_malloc(new_size);
            
            // 새 블록에 적절한 크기를 설정 (내부 단편화 처리)
            place(new_bp, new_size);
            memcpy(new_bp, ptr, new_size);
            mm_free(ptr);
            return new_bp;
        }
    }
}

./mdriver -v 로 전체 테케를 정확히 측정하여 공간 활용도와 처리량 확인 필요

Next_fit

Next Fit은 동적 메모리 할당에 사용되는 알고리즘 중 하나로, First Fit 알고리즘의 변형
최근 할당된 위치에서부터 순차적으로 탐색 주어진 크기(asize)에 맞는 가용 메모리 블록을 탐색

구현 시도 이유

“점수가 잘 오른다”라는 소식에 시도

로직 설명

검색 범위 : recent_allocate부터 힙의 끝까지 검색
코드 구조 : 순수한 next fit 알고리즘
메모리 탐색 방식 : 최근 할당된 위치에서부터 순차적으로 탐색
단점 : 하지만 최근에 할당했던 블록 이전의 공간은 검색하지 않음

Next Fit 함수 코드 설명

static void *next_fit(size_t asize) {
    void *bp;

    if (recent_allocate == NULL) {
        recent_allocate = heap_listp;
    }

    for (bp = recent_allocate; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
            recent_allocate = bp;
            return bp;
        }
    }

    return NULL;
}

코드 설명

초기 검색 위치 설정
```
if (recent_allocate == NULL) {
    recent_allocate = heap_listp;
}
```
- 만약 recent_allocate가 NULL이면(아직 할당이 없었다면), 힙의 시작 위치로 설정
메모리 블록 검색
```
for (bp = recent_allocate; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
```
- recent_allocate부터 시작하여 힙의 끝까지 순회
- GET_SIZE(HDRP(bp)) > 0는 현재 블록의 크기가 0보다 큰지 확인합니다(힙의 끝이 아닌지 확인).
- NEXT_BLKP(bp)로 다음 블록으로 이동
적합한 블록 찾기
```
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
    recent_allocate = bp;
    return bp;
}
```
- !GET_ALLOC(HDRP(bp)): 현재 블록이 할당되지 않았는지 확인
- asize <= GET_SIZE(HDRP(bp)): 요청된 크기가 현재 블록 크기 이하인지 확인
- 조건이 만족되면, recent_allocate를 현재 블록으로 업데이트하고 해당 블록을 반환

결과

그렇다면 Next_fit의 부족한 부분을 어떻게 해결할까?

"이전에 할당했던 위치는 확률상 할당 가능한 공간이 적어서 검색을 배제한다” 라는 방법에서 나온 next_fit을 진행 후 가용 공간이 없다면 배제했던 공간을 탐색하여 처리량이 조금 늘어날지라도 공간 활용도는 높일수 있지 않을까라는 생각으로 Next_fit의 장점과 First_fit의 장점을 이용해서 적용해보면 어떨까라는 생각으로 시도

Next_fit + first_fit 방식 적용

로직 설명

검색 범위
- Next Fit 단계: recent_allocate부터 힙의 끝까지 검색
- First Fit 단계: 힙의 시작부터 원래의 recent_allocate까지 검색
코드 구조
- 두 개의 분리된 루프로 Next Fit과 부분적 First Fit 구현
메모리 탐색 방식
- 최근 할당 위치에서 시작하여 순차적으로 탐색 후, 필요시 힙의 처음부터 재탐색
장점
- Next Fit의 지역성 활용으로 빠른 할당 가능
- First Fit 단계를 통해 전체 메모리 공간 활용도 향상
단점
- 순수한 Next Fit보다 평균 검색 시간이 길어질 수 있음
- 구현이 더 복잡하고 메모리 사용량이 약간 증가할 수 있음

Next_fit + first_fit 코드 설명

static void *next_fit(size_t asize)
{
    void *bp;

    // 초기화: recent_allocate가 NULL이면 힙의 시작점으로 설정
    if (recent_allocate == NULL) {
        recent_allocate = heap_listp;
    }

    // Next Fit 단계: recent_allocate부터 힙의 끝까지 검색
    for (bp = recent_allocate; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
            recent_allocate = bp;
            return bp;
        }
    }

    // First Fit 단계: 힙의 시작부터 원래의 recent_allocate까지 검색
    for (bp = heap_listp; bp < recent_allocate; bp = NEXT_BLKP(bp)) {
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
            recent_allocate = bp;
            return bp;
        }
    }

    // 적합한 블록을 찾지 못한 경우
    return NULL;
}

코드 설명

초기화

if (recent_allocate == NULL) {
    recent_allocate = heap_listp;
}

recent_allocate가 NULL이면 힙의 시작점으로 초기화

Next Fit 단계
```
for (bp = recent_allocate; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
    if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
        recent_allocate = bp;
        return bp;
    }
}
```
- recent_allocate부터 힙의 끝까지 순회
- GET_SIZE(HDRP(bp)) > 0: 현재 블록이 힙의 끝이 아닌지 확인
- !GET_ALLOC(HDRP(bp)): 블록이 할당되지 않았는지 확인
- asize <= GET_SIZE(HDRP(bp)): 요청 크기가 블록 크기 이하인지 확인
- 조건 만족 시 recent_allocate 업데이트 후 블록 반환

First Fit 단계

힙의 시작(heap_listp)부터 원래의 recent_allocate까지 순회
Next Fit 단계 실패 시에만 실행

for (bp = heap_listp; bp < recent_allocate; bp = NEXT_BLKP(bp)) {
    if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
        recent_allocate = bp;
        return bp;
    }
}

주요 특징

지역성 활용: recent_allocate를 사용하여 최근 할당 위치부터 검색
효율적인 검색: Next Fit으로 빠른 할당 시도 후, 필요 시 First Fit 사용
메모리 활용도 개선: 전체 힙을 검색하여 가용 블록 찾기 가능
단편화 감소: First Fit 단계를 통해 이전에 사용하지 않은 영역도 검색

결과

업로드중..

개선 후 결과

공간 활용도 (Utilization)
- 예상대로 Next Fit + First Fit이 더 높음 (43 vs 42)
  
  전체 힙을 검색함으로써 더 적합한 블록을 찾을 수 있기 때문에 공간 활용도가 예상대로 높게 나옴
처리량 (Throughput)
- 예상대로 순수 Next Fit이 더 빠름 (40 vs 39)
  
  이는 순수 next_fit의 검색 범위가 제한적이어서 next_fit + first_fit 보다 더 빠르게 할당하여 처리량이 예상대로 빠르게 나왔습니다.

문제점

Next Fit + First Fit은 Next Fit 의 단점(특정 영역에 치우친 할당, 전체 메모리를 고려하지 않는 문제)과 First Fit의 단점(힙의 처음부터 탐색)을 극복하고자 시도 그러나 이 방식도 상황에 따라 순수한 Next Fit이나 First Fit보다 성능이 떨어질 수 있는 문제가 있음

마치며

테스테케이스의 상황에 따라 점수도 달라질 수 있고 어떤 가용리스트를 적용하는지 또는 어떤 탐색 방법을 적용하는지에 그리고 어떠한 상황인지에 따라 달라진다는걸 알게되었다. 상황에 맞는 방법을 찾아 적용하는게 중요하다고 생각하여 여러가지 방법들을 적용해 보았다 사실 realloc이나 여러가지 부분을 더 손보고 싶었지만 주어진 시간이 한정되어 있어서 그렇게 진행하지 못하여서 아쉬움이 많았다. 짧은 시간이었지만 얻어가는게 많았고 팀원들과 폭발적으로 성장하여서 후회는 없다고 생각한다.

pigpgw

https://www.pigpgw.cloud 로 이전합니다~

이전 포스트

크래프톤 정글 WIL_Week05 Red-Black Tree

다음 포스트

크래프톤 정글 WIL_Week06 Malloc Lab