malloc LAB #3 : Explicit Free List

2025.04.28 - [문제풀이] - MALLOC | FREE LIST 구현기 #2

MALLOC | FREE LIST 구현기 #2

Implicit Free List에 상세 구현에 대해 다루었다. 이 글에서는, Explicit에 대해 다루겠다.

막 엄청 중요한 그림은 아니다.

실제 구현을 이루는데 있어 Implicit과 전체적인 형태는 유사하다.
진짜로, 추상적 개념 하나를 도입하고 그 개념에 대한 직접적인 다룸이 일어나는 곳에 코드를 끼워넣으면 된다.
다만 여기서 조금 더 상세한 목표를 생각했다.

LIFO : Last in First Out 형식으로 작성

• Free 한 공간이 반환되면 어디에 넣을지를 생각해야하는데, 재사용을 위해서 일부러 Free List에 앞에 넣는다.
  즉, 사용된 적이 있는 데이터가 재사용 되도록 유도하는데 있다. 이것은 지역성에 관한 부분도 충분히 만족 시킬 수 있다.
• 이렇게 되면 Free List에 추가를 직접 수행하는 함수는 Free List의 1번을 갱신하는 내용으로만 작성하면 된다.
• Fit 전략을 특별히 변경 할 필요는 없다.

신규 함수 #1 | add_freeList

void add_freeList(void *bp)
{
    NEXT_FREE(bp) = freeList_str;
    PREV_FREE(bp) = NULL;

    if (freeList_str != NULL)
        PREV_FREE(freeList_str) = bp;
    freeList_str = bp;
}

---

신규 함수 #2 | remove_freeList

void remove_freeList(void *bp)
{
    void *prev = PREV_FREE(bp);
    void *next = NEXT_FREE(bp);

    if(prev != NULL)
        NEXT_FREE(prev) = next;
    else
        freeList_str = next;

    if (next != NULL)
        PREV_FREE(next) = prev;
}

양 방향 연결리스트이지만 나는 원소를 들고 탐색하는게 아니라 냅다 그 주소에 찾아갈 수 있으니 그냥 찾아가서 이어주고 얘는 제거.

mm_init의 수정 사항 | heap_listp의 기본 시작 계수가 4에서 8로 확장되었다.

int mm_init(void)
{    // np
    if ((heap_listp = mem_sbrk(8 * WSIZE)) == (void *) - 1)
        return -1;
    PUT(heap_listp, 0); // Alignment padding
    PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); // 프롤로그 Header
    PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); // 프롤로그 Footer
    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 += (4 * WSIZE); 

    // 초기 초기화 루틴을 CHUNKSIZE / WSIZE 만큼 확장 시도를 한다.
    if(extend_heap(CHUNKSIZE/WSIZE) == NULL)
        return -1;
    return 0;
}

조금 이 부분에 대해 상세한 설명을 해주고싶은데............... um

coalence의 수정 사항 | 각 상황에 대한 Free List 추가 제거 코드 추가

static void* coalence(void *ptr)
{ // np
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(ptr)));
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr)));
    size_t size = GET_SIZE(HDRP(ptr));

    if (prev_alloc && next_alloc)
    {
        add_freeList(ptr);
        return ptr;
    }
    else if (prev_alloc && !next_alloc)
    {
        //size += GET_SIZE(HDRP(NEXT_BLKP(ptr)));
        remove_freeList(NEXT_BLKP(ptr));
        //PUT(HDRP(ptr), PACK(size, 0));
        //PUT(FTRP(ptr), PACK(size, 0));
    }
    else if (!prev_alloc && next_alloc)
    {
        //size += GET_SIZE(HDRP(PREV_BLKP(ptr)));
        remove_freeList(PREV_BLKP(ptr));
        //PUT(FTRP(ptr), PACK(size, 0));
        //PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));
        ptr = PREV_BLKP(ptr);
    }
    else
    {
        //size += GET_SIZE(HDRP(PREV_BLKP(ptr))) +
        //GET_SIZE(FTRP(NEXT_BLKP(ptr)));
        remove_freeList(PREV_BLKP(ptr));
        remove_freeList(NEXT_BLKP(ptr));

        //PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));
        //PUT(FTRP(NEXT_BLKP(ptr)), PACK(size, 0));
        ptr = PREV_BLKP(ptr);
    }
    add_freeList(ptr);
    return ptr;
}

합칠 수 있는 내용은 아예 freeList에서 제거하고, 코드가 끝나기 전 더 큰 크기로써 freeList에 추가 함으로써 오버헤드가 생길지언정 연산에 대한 복잡함을 덜 가져가는 형태로 구현되었다.

place 수정 사항 | 일단 뺀 다음 남는 공간을 다시 내려두기

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

    // 옵션으로 초과 부분을 분할하는 역할
    if((csize - asize) >= (2 *DSIZE))
    {
        //PUT(HDRP(ptr), PACK(asize, 1));
        //PUT(FTRP(ptr), PACK(asize, 1));
        remove_freeList(ptr);
        ptr = NEXT_BLKP(ptr);
        //PUT(HDRP(ptr), PACK(csize - asize, 0));
        //PUT(FTRP(ptr), PACK(csize - asize, 0));
        add_freeList(ptr);
    } 
    else
    {
        //PUT(HDRP(ptr), PACK(csize, 1));
        //PUT(FTRP(ptr), PACK(csize, 1));
        remove_freeList(ptr);
    }
    
}

재사용이 된다고 판단된 영역은 다시 add_Freelist로 추가한다.

realloc도 변경점이 있지만 제일 중요한것만 다루면 이정도.