[malloc] Explicit Free List 방식

SWjungle/#malloc

[malloc] Explicit Free List 방식 - 구현

장영 2023. 9. 12. 22:11

Explicit Free List

implicit free list가 모든 블록(할당 + free)을 탐색하며 해당 블록이 할당되었는지, 아니면 free인지 확인하며 필요한 동작을 수행했다면, explicit free list는 오직 free 블록만 탐색하게 된다. 이러한 free 블록을 탐색할 수 있도록 이중 연결 리스트로 구성되는데, 이를 통해서 앞으로만 탐색하는 것이 아니라 뒤로도 탐색하는 것이 가능해진다.
free 블록의 payload 부분은 사용하지 않는 상태로 되기 때문에 이 공간을 활용한다. 해당 블록에, 전의 free 블록의 주소로 갈 수 있는(주소값을 담고 있는) predecessor과 뒤의 free 블록의 주소로 갈 수 있는(주소값을 담고 있는) successor를 넣게 된다. 이를 통해 할당 블록은 탐색하지 않아 시간 비용을 낮출 수는 있지만, free 블록에서는 prec과 succ를 위한 공간이 추가적으로 요구되므로 메모리 활용도는 낮아진다.

address-ordered :연결리스트에 free 블록을 추가하는 방식에 따라 블록의 물리적인 순서대로 연결리스트를 구성하는 방식
LIFO : 최근에 해제된 블록을 연결 리스트의 가장 앞에 넣고 할당할 때에도 되도록 앞의 free 블록이 할당되도록 하는 방식이 있는데
전자는 단편화 방지에 좋은 반면, 후자는 탐색 시간을 상수로 만들기에 각자 장단점이 있다.

📌LIFO(후입선출)

LIFO를 이용한 explit free list에서 주의할 점은 연결리스트 안의 free 블록 순서가, 물리적인 순서와는 다를 수 있음을 알아야한다. 그리고 이 연결리스트으이 맨 끝은 프롤로그 블록이 들어가 있어 연결리스트가 끝나는 지점을 알 수 있다.

📌메모리 할당 과정

연결리스트의 처음 블록 부터 순회하며 블록의 사이즈가 할당시키기에 적절한지 탐색한다.
블록의 사이즈가 적절치 않다면 다음 블록으로 포인터를 이동시킨다.
만약 적절하다면, 즉 할당할 수 있다면
1. 해당 블록을 연결리스트에서 제거한다.
2. 할당 이후 분할이 가능하다면 분할하여 새로은 free블록을 만들고 연결리스트에 새로운 free 블록을 추가한다.(분할 시 최소 크기의 free 블록 ( header/footer/predecesoor/successor)을 만들 수 없다면 어쩔 수 없이 메모리 주소 정렬을 위해 내부 단편화를 진행한다.)
3. 메모리를 할당하고 해당 블록을 가리키는 포인터를 반환하여 해당 블록을 사용할 수 있게한다.
할당 할 수 있는 공간이 없어 연결리스트의 끝인 프롤로그 블록을 만나게 된다면 힙의 공간을 늘려서 할당한다.

📌할당 해제 과정

CASE 1 : 이전과 다음 블록 모두 할당인 경우

해당 블록을 free 시킨 후 연결리스트의 맨 처음에 추가한다. 그리고 추가된 블록의 다음이 원래 연결리스트의 맨 처임이었던 블록과 연결되도록 한다.

case 2 : 다음 블록이 free인 경우

해제 이후 다음 free 블록과 연결 시킨다. 동일하게 이 free 블록을 연결리스트의 맨 처음에 넣고 원래 연결리스트의 맨 처음이었던 블록과 연결시킨다.

case 3 : 이전 블록이 free 인 경우

해제 이후 이전 free 블록과 연결 시킨다. 동일하게 이 free 블록을 연결리스트의 맨 청므에 넣고 원래 연결리스트의 맨 처음이었던 블록과 연결 시킨다.

case 4 : 이전과 다음 블록이 모두 free인 경우

이전, 현재 헤제한 다음 블록 모두 연결 시킨다. 동일하게 이 free 블록을 연결리스트의 맨 처음에 넣고 원래 연결리스트의 맨 처음이었던 블록과 연결 시킨다.

✏️implicit free list와의 비교

전체 블록의 갯수가 아닌, free 블록 갯수에 대해서만 탐색하게 되므로 할당 시간을 줄이게 된다. 하지만 연결리스트 구성을 위해 free 블록에는 2개( 2word) 의 추가적인 메모리가 필요하다.

📌코드

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

#include "mm.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 */
    "week5",
    /* First member's full name */
    "jang hoyoung",
    /* First member's email address */
    "ghdu233213@naver.com",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""
};

/* 메크로 */
#define WSIZE 4
#define DSIZE 8
#define MINIMUM 16      /* 헤더, 푸터, 전자, 후자 초기화*/
#define CHUNKSIZE (1<<12)

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

/* 크기와 할당 비트를 통합해서 헤더와 풋터에 저장할 수 있는 값을 return */
#define PACK(size, alloc) ((size) | (alloc))

/* 인자 p가 참조하는 워드 읽어서 return */
/* 인자 p는 대개 (void*) 포인터. 직접적으로 역참조 불가 */ 
#define GET(p) (*(unsigned int *)(p))
/* 인자 p가 가리키는 워드에 val 저장 */
#define PUT(p, val) (*(unsigned int *)(p) = (val))

/* 각각 주소 p에 있는 헤더, 풋터의 size와 할당 비트를 return */
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)

/* 블록 포인터 bp가 주어지면, 각각 블록 헤더와 풋터를 가리키는 포인터 return */
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

/* 블록 포인터 bp가 주어지면, 각각 다음과 이전 블록의 블록 포인터를 return */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

/* Free List 상에서의 이전, 이후 블록의 포인터를 retutn */
#define PREC_FREEP(bp)  (*(void**)(bp))             /* 이전 블록의 bp */ 
#define SUCC_FREEP(bp)  (*(void**)(bp + WSIZE))     /* 이후 블록의 bp */ 

/* 정렬 유지 위해 가까운 배수로 반올림 */
#define ALIGN(size) (((size) + (DSIZE-1)) & ~0x7)

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

/* 함수 선언 */
static void *extend_heap(size_t);
static void *coalesce(void *);
static void *find_fit(size_t);
static void place(void *, size_t);
void remove_block(void *);

/* 전역 변수 */
static char *heap_listp;
static char *free_listp; /* free list의 맨 첫 블록을 가리키는 포인터 */ 

/* 
 * mm_init - 할당기 초기화 
 */
int mm_init(void)
{   
    /* 메모리에서 6워드 가져와 빈 가용 리스트 초기화 */
    /* padding, prol_header, prol_footer, PREC, SUCC, epil_header */
    if ((heap_listp = mem_sbrk(6*WSIZE)) == (void *)-1)
    return -1;

    PUT(heap_listp, 0);                            /* Alignment padding */
    PUT(heap_listp + (1*WSIZE), PACK(MINIMUM, 1)); /* Prologue header */
    PUT(heap_listp + (2*WSIZE), NULL);             /* prologue block안 PREC 포인터 NULL 초기화 */
    PUT(heap_listp + (3*WSIZE), NULL);             /* prologue block안 SUCC 포인터 NULL 초기화 */
    PUT(heap_listp + (4*WSIZE), PACK(MINIMUM, 1)); /* Prologue footer */
    PUT(heap_listp + (5*WSIZE), PACK(0, 1));       /* Epilogue header */
    
    free_listp = heap_listp + 2*WSIZE;           /* free_listp를 탐색의 시작점으로 지정 */

    /* heap을 CHUNKSIZE 바이트로 확장 후 초기 가용 블록 생성 */
    if (extend_heap(CHUNKSIZE/WSIZE) == NULL) 
        return -1;
    return 0;
}

/*
 * remove_block - 할당되거나 연결되는 가용 블록을 free list에서 삭제
 */
void remove_block(void *bp){
    /* free list의 첫번째 블록 삭제시 */ 
    if (bp == free_listp){ //free_list가 bp를 가리킬떄
        PREC_FREEP(SUCC_FREEP(bp)) = NULL; 
        free_listp = SUCC_FREEP(bp);    /* free list의 맨 첫 블록을 가리키는 포인터가 다음 블록 가리키도록 */
    }
    /* free list안에서 삭제시 */ 
    else{
        SUCC_FREEP(PREC_FREEP(bp)) = SUCC_FREEP(bp);
        PREC_FREEP(SUCC_FREEP(bp)) = PREC_FREEP(bp);
    }
}

/*
 * put_freeblock - 새로 반환 및 생성된 가용 블록을 free list의 첫 부분에 추가 
 */
void put_freeblock(void* bp){
    SUCC_FREEP(bp) = free_listp;//첫번쨰 정보가 들어있음
    PREC_FREEP(bp) = NULL;  // 새로들어온 친구의 이전은 null로 바꿈
    PREC_FREEP(free_listp) = bp; // 첫번쨰 정보가 이전을 가리키는 곳은 새로들어온 친구
    free_listp = bp;  // 루트에서  비피 연결
}


/*
 * coalesc - 가용 블럭 생성시 통합 
 */
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){   /* Case 1 */ // 이전 블록은 할당 상태, 다음블록은 가용상태
        remove_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){   /* Case 2 */
        remove_block(PREV_BLKP(bp));        /* 가용 상태인 직전 블록을 free list에서 제거 */ 
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        bp = PREV_BLKP(bp);
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));  
    }
    else if (!prev_alloc && !next_alloc){   /* Case 3 */
        remove_block(PREV_BLKP(bp));        /* 가용 상태인 직전 블록을 free list에서 제거 */ 
        remove_block(NEXT_BLKP(bp));        /* 가용 상태인 직후 블록을 free list에서 제거 */ 
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
        bp = PREV_BLKP(bp);
        PUT(HDRP(bp), PACK(size, 0));  
        PUT(FTRP(bp), PACK(size, 0));  
    }
    /* 연결된 새 가용 블록을 free list에 추가 */
    put_freeblock(bp);
    return bp;
}

/* 
 * expend_heap - malloc package 초기화
 *               1. 힙 초기화시
 *               2. mm_malloc이 적당한 fit을 못찾았을 때, 정렬 유지 위해 호출
 */
static void *extend_heap(size_t words)
{
    char *bp;
    size_t size;

    /* 정렬 유지 위해 짝수 word 할당 */
    size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;
    if ((long)(bp = mem_sbrk(size)) == -1)
    return NULL;

    /* 가용 블럭의 헤더, 푸터 와 epilogue 헤더 초기화 */
    PUT(HDRP(bp), PACK(size, 0));         /* Free block 헤더 */
    PUT(FTRP(bp), PACK(size, 0));         /* Free block 푸터 */
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue 헤더 */

    /* 이전 블록이 가용됬을 때 통합 */
    return coalesce(bp);
}

/* explicit free list */
/* first-fit 검색 */
static void *find_fit(size_t asize)
{
    void *bp;

    /* 가용 리스트에서 맞는 블록 검색 */
    for (bp = free_listp; GET_ALLOC(HDRP(bp)) != 1; bp = SUCC_FREEP(bp)){
        if(asize <= GET_SIZE(HDRP(bp))){
            return bp;
        }
    }
    return NULL ;  
}

/* 
 * place - 맞는 블록 찾으면 할당기는 요청한 블록을 배치, 옵션으로 추가 부분 분할
 */
static void place(void *bp, size_t asize)
{
    size_t csize = GET_SIZE(HDRP(bp));

    /* 할당될 블록이므로 free list에서 삭제 */
    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));

        /* 가용 리스트에 블럭 추가 */
        put_freeblock(bp);
    }
    else
    {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

/* 
 * mm_malloc - size 바이트의 메모리 블록 요청
 *             brk pointer를 증가시켜 블록 할당        
 */
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 /* 8바이트 넘는 요청에 대해 오버헤드 바이트 추가, 인접 8의 배수로 반올림 */
        asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);
    
    /* 적절한 가용 블록을 가용 리스트에서 검색 */
    if ((bp = find_fit(asize)) != NULL){
        /* 맞는 블록 찾으면 할당기는 요청한 블록을 배치, 옵션으로 추가 부분 분할 */
        place(bp, asize);
        /* 새로 할당한 블록의 포인터 return */
        return bp;
    }

    /* 적절한 가용 블록을 가용 리스트에서 찾지 못하면, 힙을 새로운 가용 블록으로 확장 */
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
        return NULL;
    /* 요청한 블록을 새 가용 블록에 배치, 필요시 블록을 분할 */
    place(bp, asize);
    /* 새로 할당한 블록의 포인터 return */
    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 - 동적 할당된 메모리 내용 유지하며 할당된 메모리 크기 변경
 */
void *mm_realloc(void *bp, size_t size)
{
    void *oldptr = bp;  /* 크기를 조절하고 싶은 블록의 시작 포인터 */ 
    void *newptr;       /* 크기 조절 후 새 블록의 시작 포인터 */
    size_t copy_size;    /* 복사할 블록 크기 */

    newptr = mm_malloc(size);
    if (newptr == NULL)
        return NULL;

    copy_size = GET_SIZE(HDRP(oldptr));

    /* 원래 메모리 크기보다 적은 크기를 realloc하면 크기에 맞는 메모리만 할당 */
    if (size < copy_size)
        copy_size = size;
    
    memcpy(newptr, oldptr, copy_size);  /* 새 블록에 복사할 블록 크기만큼 복사 */
    mm_free(oldptr);                    /* 이전 블록을 free */
    return newptr;
}

저작자표시

'SWjungle > #malloc' 카테고리의 다른 글

[malloc] budy메모리 할당 (2)	2023.09.14
[malloc] segregated free list 방식 - 구현 (0)	2023.09.13
[Malloc] Implicit Free List방식-구현 (1)	2023.09.11
[malloc] 동적 메모리 할당 (0)	2023.09.08

현재글[malloc] Explicit Free List 방식 - 구현

Today :
Yesterday :

일	월	화	수	목	금	토
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31

장영

[malloc] Explicit Free List 방식 - 구현

Explicit Free List

'SWjungle > #malloc' 카테고리의 다른 글

'SWjungle/#malloc'의 다른글

티스토리툴바

[malloc] Explicit Free List 방식 - 구현

Explicit Free List

'SWjungle > #malloc' 카테고리의 다른 글

'SWjungle/#malloc'의 다른글

관련글

티스토리툴바