[Malloc] Explicit Free Lists 명시적 가용 리스트

bongf·2022년 5월 12일
0

정글

목록 보기
9/20

사용 이유

  • 묵시적 가용리스트를 사용하면 (implicit free list) 블록 할당 시간이(fist fit 전제) 전체 힙 블록의 수에 비례하기 때문에 블록 수가 사전에 정해져 있고, 작은 특별한 케이스가 아니라면 적합하지 않다.
  • 기존에 implicit free list를 사용하면 모든 블럭을 (할당된 블록 포함) 탐색하며 찾아야 한다.
  • 가용리스트를 이중 연결리스트로 만들어서 (prev, next 갖는) 할당할 블록을 찾을 때 first fit을 적용한다면 free block만 탐색하면 된다.
    • 전체 블록 수에 비례 -> free 블록 수 비례로 시간 단축
  • free block에는 body가 필요하지 않기 때문에 이 부분에 prev, next 포인터를 넣을 수 있다.
  • coalescing을 위해 boundary tag는 여전히 필요하다 (헤더와 풋터에 블록의 사이즈와 할당 여부를 입력하는 방식)
    • 이전/다음 블록이 할당되어 있는지 사이즈는 얼마인지 바로 알 수 있다

가용블럭의 최소 사이즈

  • 4WORD
  • header, footer, prev, next 각 1WORD 씩

가용블록에서 할당

  • 출처 : Carnegie Mellon University 강의 자료

정해야 할 정책

  • 새롭게 만든 free block을 어디에 둘 것인가
  • 1) LIFO (후입 선출)
    • 가장 마지막에 들어간 것이 가장 먼저 나도록
    • 힙에 요청 사이즈만큼의 블록 할당 할 수 없을 때 extend를 해서 힙을 늘리고 새로운 가용블록을 할당하므로 이 블럭이 앞에 오면 빨리 찾을 수 있다는 것으로 이해했다.
    • 주소로 정렬되었을 때보다 단편화가 크다.
      • first-fit 이므로 더 큰 블록이 앞에 왔을 때 그곳에 바로 할당해버리기 때문에
  • 2) 주소기반 정렬
  • LIFO 기반으로 구현

extend_heap

static void *extend_heap(size_t words)
{
    char *bp;
    size_t size;

    /* Allocate an even number of words to maintain alignmnet */
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
    if ((long)(bp = mem_sbrk(size)) == -1)
        return NULL;

    PUT(HDRP(bp), PACK(size, 0));         /* Free block header  */
    PUT(FTRP(bp), PACK(size, 0));         /* Free block footer  */
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */

    /*Coalesce if the previous block was free */
    return coalesce(bp);
}
  • size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE; 정렬 정책을 준수해야 하므로 요청 사이즈 words가 2로 나눠 떨어지도록 맞춰준다.
  • if ((long)(bp = mem_sbrk(size)) == -1) return NULL; 힙이 해당 사이즈를 할당할 수 있다면 (없으면 NULL)
  • 가용 블록으로 만들어야 하므로 Allocated bit를 0으로 설정해서 사이즈를 헤더와 풋터에 넣고
  • 새로운 블록의 다음 블록을 에필로그 블록으로 만든다
  • colesce를 해준다.

find_fit(aszie)

  • 할당된 사이즈에 맞는 찾기 
static void *find_fit(size_t asize)
{
    /* First-fit search */
    void *bp;

    for (bp = free_listp; GET_ALLOC(HDRP(bp)) == 0; bp = NEXT_FRBLKP(bp))
    {
        if (asize <= GET_SIZE(HDRP(bp)))
            return bp;
    }
    return NULL;
}
  • 현재 free_list의 마지막 블럭을 프롤로그 footer로 설정했기 때문에 할당 되어 있다. 여기까지 탐색하기 위해 GET_ALLOC(HDRP(bp)) == 0 조건을 적어준다.

remove_free_block()

  • free list에서 해당 bp의 블록 제거 

static void remove_free_block(void *bp)
{
	if(PREV_FRBLKP(bp))
        NEXT_FRBLKP(PREV_FRBLKP(bp)) = NEXT_FRBLKP(bp);
    else
        free_listp = NEXT_FRBLKP(bp);
    PREV_FRBLKP(NEXT_FRBLKP(bp)) = PREV_FRBLKP(bp);
}
  • 이전 free 블록이 있다면 이전 free 블록의 다음 free블록을 현재 bp의 다음 free블록으로 연결한다.
  • 이전 free 블록이 없다면 bp의 다음 free 블록을 free_listp(루트)로 지정
  • bp의 next free 블록의 prev를 bp의 prev free block으로 둔다.

place(bp, asize)

static void *find_fit(size_t asize)
{
    /* First-fit search */
    void *bp;

    for (bp = free_listp; GET_ALLOC(HDRP(bp)) == 0; bp = NEXT_FRBLKP(bp))
    {
        if (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) < WSIZE * 4)
    { /* 블록 크키가 작아 다른 블록 할당할 수 없을 때(not split) */
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
        remove_free_block(bp);
    }
    else
    { /* 블록 크기가 다른 블록을 할당할 수 있을 만큼 클 때(split) */
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        remove_free_block(bp);

        csize -= asize;
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(csize, 0));
        PUT(FTRP(bp), PACK(csize, 0));
        coalesce(bp);
    }
}
  • bp에 aszie(정렬된 크기로 들어옴) 를 할당하고 자 할 때
  • 가용블록에서 asize 만큼 빼고 새로운 블록으로 할당할 수 없다면 원래 블록 만큼 할당한다. (remove from free list)
  • 가용블록에서 asize 만큼 빼고 새로운 블록으로 할당할 수 있다면 요청온 만큼 asize 할당하고(&free list에서 지우고) 잔여만큼을 새 가용블록으로 둔다(coalesce)

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);
}
  • allocated 비트를 1로 두고 coalesce한다

mm_malloc()

  • implicit 가용리스트를 사용할 때와 같다 
void *mm_malloc(size_t size)
{
    size_t asize;
    size_t extendsize;
    char *bp;

    /* Ignore spurious requests */
    if (size == 0)
        return NULL;

    /* Adjust block size to include overhead and alignmnet reqs. */
    if (size < DSIZE)
        asize = 2 * DSIZE;
    else
        asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);

    /* Search the free list for a fit */
    if ((bp = find_fit(asize)) != NULL)
    {
        place(bp, asize);
        return bp;
    }

    /* No fit found. Get more memory and place the block */
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL) 
        return NULL;
    place(bp, asize);
    return bp;
}

mm_init()

{
    /* Create the initial empty heap. */
    if ((heap_listp = mem_sbrk(6 * WSIZE)) == (void *)-1)
        return -1;

    PUT(heap_listp, 0);                                /* Alignment padding */
    PUT(heap_listp + (1 * WSIZE), PACK(2 * WSIZE, 1)); /* Prologue header */
    PUT(heap_listp + (2 * WSIZE), PACK(2 * WSIZE, 1)); /* Prologue footer */
    PUT(heap_listp + (3 * WSIZE), PACK(0, 1));         /* Epilogue header */
    heap_listp += (2 * WSIZE);                         /* 포인터를 Prolouge 헤더 바로 다음으로 옮긴다 */
    free_listp = heap_listp;
    if (extend_heap(4) == NULL){ 
        return -1;
    }
    /* Extend the empty heap with a free block of CHUNKSIZE bytes */
    if (extend_heap(CHUNKSIZE / WSIZE) == NULL) /* 최대 할당 크기를 넘었을 때 */
        return -1;
  
    return 0;
}
  • 이렇게 되면 초기 할당 크키가 6이 되어야 한다. 4가 되면 에러.
  • 왜 초기 할당 크기를 6으로 해야 할까. 6도 되고 8도 된다.

coalesce()

static void *coalesce(void *bp)
{
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))) || PREV_BLKP(bp) == bp;
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); 

    size_t size = GET_SIZE(HDRP(bp));

    /* If the previous block is free, then coalesce the current block (bp) and the previous block */
    if (!prev_alloc && next_alloc) { /* Case 2 */
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        bp = PREV_BLKP(bp);
        remove_free_block(bp);
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }
    else if (prev_alloc && !next_alloc){ /* Case 3 */
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        remove_free_block(NEXT_BLKP(bp));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }
    else if (!prev_alloc && !next_alloc){ /* Case 3 */
        size += GET_SIZE(HDRP(PREV_BLKP(bp)))
              + GET_SIZE(HDRP(NEXT_BLKP(bp)));
        remove_free_block(PREV_BLKP(bp));
        remove_free_block(NEXT_BLKP(bp));
        bp = PREV_BLKP(bp);
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }
    /* case 1  : insert into free blocks*/
    insert_free_block(bp);
    return bp;
}

할 것

[ ] next-fit
[ ] 블록 삭제해보기
[] 더 작을 때 split 할지 안할지

  • 안하면 free 할 때 더 큰 블록 얻을 수 있다. (향후에 큰 request 왔을 때 좋다)
  • 하면 뒤에 작은 block 요청이 왔을 때 이득.
  • 그런데 어떤 요청들이 올 것인지 예측할 수 없다.
  • 만약 implict 할때 split 안하면 점수는?

init

  • 모르겠는 것

    • 왜 root를 heap 안에 두는 것인지? (따로 두면 안되나? 어쨌든 힙 안에 할당해야 해서)

  • 왜, free list 초기화 할 때, root에 해당하는 것 하나 두고, 그 뒤에 하나 더 블록을 붙일까? 함 보자 어떻게 구현했는지

  • root를 만들 때 왜, pointer 2개를 구현하는지? root는 next만 있으면 되는 거 아닌가?

    • 그러면 블록 경계 기껏 패딩해서 맞춰둔 것이 흐트려진다
    • 그러면 padding 없애고, 기존에 이것이었다면, 이렇게 가꾸면 되는 것 아닌가?
    • 돌려보고 해보자
    • heap의 시작 포인터의 데이터 값이 꼭 null 일 필요가 있나?
      • 상관 없는 것 같다. 기존 implict list로 구현한 코드에 padding 값에 데이터 넣어도 점수는 똑같이 나온다

  • 왜 prologu footer 뒤에 root free block 을 안두고, prologue header 뒤에 두나 생각했는데 이전에 짜둔 로직이 이제 payload 시작점을 prologue header, footer 사이에 두잖아. 거기서 이제

  • 왜 안되는지 모르겠으나, padding 없이 prologue를 맨 앞에 두면 안된다 자리수를 맞춰준다 하더라도

  • 일단 나는 padding 없어지고 프롤로그 헤더를 땡기면 왜그런지 몰라도 오류나서 패딩 그대로 만들어두고 루트 프리 노드에는 헤더와 풋터는 만들어주지 않았다. 그냥 next 포인터만 만들어주고 싶었는데 더블 워드 경계를 지켜야 해서 prev 포인터도 만들어 줬다.

매크로

#define NEXT_FREE(bp) (*(void **bp)) 는

  • bp는 2차원 포인터로 캐스팅하고 이것의 *bp니까 어쨌든 bp에 담긴 값이고 이것을 2차원 포인터로 캐스팅 했으니까 이것또한 어떤 것의 주소라는 말이 된다.

mm_malloc

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

    /* Ignore spurious requests */
    if (size == 0)
        return NULL;

    /* Adjust block size to include overhead and alignmnet reqs. */
    if (size < DSIZE)
        asize = 2 * DSIZE;
    else
        asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);

    /* Search the free list for a fit */
    if ((bp = find_fit(asize)) != NULL)
    {
        place(bp, asize);
        return bp;
    }

    /* No fit found. Get more memory and place the block */
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL) 
        return NULL;
    place(bp, asize);
    return bp;
}

Coalesce

  • // size_t PREV_ALLOC = GET_ALLOC(HDRP(PREV_BLK(bp))) || PREV_BLK(bp) == bp; 하는 값의 의미는 뭐지 //PREV_BLK(bp) == bp: epilogue block을 만났을 때. Extend했을 때 epilogue를 만나는 유일한 경우
    • 자기 자신이 epilouge 일 때로 이해했다.

coalesce는 언제?

  • extend하고 이제 새 free 생겼으니까 앞뒤로 연결해주기
  • 원래 가용블럭에 일부를 할당하고, 나머지 블럭이 충분히 커서 그 블럭에 free 선언할 때
  • 이미 할당한 공간을 0으로 바꾸자고 요청왔을 때 free 후 coalesce
  • 이미 할당된 공간을 더 큰 곳으로 바꾸자고 요청왔을 때, 근데 다음 블록이 할당되있어, 혹은 다음블럭 합쳐봤자 원하는 사이즈 안돼.
  • 그러면 이제 새로운 블록에 할당을 해야 되니까 기존에 할당된 것을 free -> coalesce

coalesce 문제

  • 만약 caoalesce에 앞에 prologue 오면? 할당된 상태라고 되기 때문에 coalesce 문제 문제없음
  • 만약 coalesce 하려는 블록 뒤에 epliolgue 오면? 할당된 상태라고 하기 때문에 문제 없음

궁금

  • LIFO 가 왜 좋은 거야?
    • extend 했을 때는 이해 크니까.
    • 근데 원래 가용 블록 쪼갰을 때는?
    • 블록 사이즈 변경 요청 왔을 때 이해
  • 할당은 언제 하는 거지?
  • implicit list 를 사용할 떄는 extend를 하면 큰 가용블럭이 생기고 이를 쪼개 쓰는 느낌이었는데
  • explicit는 언제 새로운 가용 블럭이 생기는 거지?
    • 똑같이 explict 하면 새로운 가용 블럭이 생기는데 이를 coalesce 과정에서 연결해 주는 것
  • - // size_t PREV_ALLOC = GET_ALLOC(HDRP(PREV_BLK(bp))) || PREV_BLK(bp) == bp; 하는 값의 의미는 뭐지 //PREV_BLK(bp) == bp: epilogue block을 만났을 때. Extend했을 때 epilogue를 만나는 유일한 경우
  • free list의 마지막이 뭐길래 GET_ALLOC(HDRP(bp)) == 0; 으로 free list를 탐색하지?

이해 안갔던

  • root를 새 블럭에 연결하는 것이 아니라, 새 블럭의 next를 root로 만드는 것이었다. 그렇게 한다면 가용블록 탐색할 때 아니면 새로 할당하기 위해 가용 블록 탐색할 때나 coalesce 하기 위해 탐색 할 때 다음 블록이 할당 되어 있나 안되어있나 알 수 있다.

내용

free 블럭 삽입

static void insert_free_block(void *bp)
{   
    NEXT_FRBLKP(bp) = free_listp;
    PREV_FRBLKP(free_listp) = bp;
    PREV_FRBLKP(bp) = NULL;
    free_listp = bp;
}

bp의 next로 root를 두고
bp의 prev는 null로 둔다.
root의 prev를 bp로 둔다
루트를 bp로 설정한다

  • 처음에 root만 (초기 가짜 free block (en

case 1

  • prev_alloc && next_alloc
    NEXT_FRBLKP(bp) = free_listp;
    PREV_FRBLKP(free_listp) = bp;
    PREV_FRBLKP(bp) = NULL;
    free_listp = bp;

case 2

  • prev가 가용, next는 할당 되어 있다
profile
bongf
spring, java학습
이전 포스트

[Malloc] 키워드 정리

1개의 댓글

comment-user-thumbnail
김희산
2022년 10월 31일

init 함수안에 if (extend_heap(4) == NULL){
return -1;
}
이걸 함으로서 82점에서 85점이 되는데 왜 그렇게 되는지 잘모르겠습니다.. 어떤거 때문에 저 코드를 넣으셨는지 궁금합니다.

답글 달기