[OS운영체제] 묵시적 가용 리스트(Implicit Free List)

[OS운영체제] 묵시적 가용 리스트(Implicit Free List)

 

묵시적 가용 리스트(Implicit Free List)는 할당된 블록과 가용 블록을 헤더(Header)와 풋터(Footer)라는 워드에 저장함으로써 간단히 구분하는 방식이다.

 

동적 메모리 할당 malloc함수를 malloc lab을 통해 직접  C언어로 구현해 보았다.

함수 구현에는 묵시적 가용 리스트(Implicit Free List), 명시적 할당 리스트(Explicit Free List), 분리 가용 리스트(Segregated Free List)가 있다.

먼저 묵시적 할당 리스트를 이용한 malloc 함수를 구현해 보았다.

 

 

 

코드

 

1. 매크로 및 기본 코드

• 1 word를 4byte로 하고, 2 word를 기본 alignment로 한다.
• 2 word = 8 byte alignment이므로, 크기의 값이 저장된 헤더와 푸터의 값은 최소 8 이상이다. 즉 2진수로 나타냈을 때 하위 3자리는 000이다. 이 3자리의 가장 오른쪽 한자리를 이용하여 할당여부를 체크한다. 할당 1, 가용 0.
• GET_SIZE 함수의 경우 2진수의 아래 3자리를 제외한 값이 사이즈를 나타내므로 이 값을 반환한다.
• GET_ALLOC의 경우 하위 3자리의 값만 가져간다. 이 때 가장 오른쪽 값이 1인지 0인지로 할당 여부를 확인힌다.

 

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"

/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8

/* Basic constants and macros */
#define WSIZE       4     /* Word and header/footer size (bytes)*/
#define DSIZE       8     /* Double Word size (bytes)*/
#define CHUNKSIZE (1<<11) /* Extend heap by this amount (bytes) */

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

/* Pack a size and allocated bit into a word */
#define PACK(size, alloc) ((size) | (alloc))

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

/* Read the size and allocated fields from address p */
#define GET_SIZE(p)  (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)

/* 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)

// #define EFRP(bp) ((char *)(bp) + WSIZE) // Explicit FRee pointer

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

static char * heap_listp; // points to the prologue block or first block
// static char * root; // explicit free lists를 위한 root
static void *extend_heap(size_t);
static void *coalesce(void *);
static void *find_fit(size_t);
static void place(void *, size_t);
static void *find_nextp;

 

2.  mm_init

• mm_init 함수에서 Prologue header, Prologue footer, Epilogue header를 위해 1 word(4 byte)씩 할당하였고 2 word(8 byte) alignment 를 맞추기 위해 제일 앞에 padding을 추가하였다.

/* 
 * mm_init - initialize the malloc package.
 */
int mm_init(void)
{
    /* Create the initial empty heap*/
    if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
        return -1;
    PUT(heap_listp, 0);
    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 */
    heap_listp += (2*WSIZE); //  Prologue header와 footer 사이로 포인터 위치 옮김
    find_nextp = heap_listp;

    /* Extend the empty heap with a free block of CHUNKSIZE bytes */
    if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
        return -1;
    return 0;
}

 

3. extend_heap

• 처음엔 2 word alignment를 맞추기 위한 코드이다.
• mem_sbrk 함수는 제일 끝 지점 mem_brk에서부터 heap size를 extend하고 새롭게 할당된 영역의 시작포인트인 원래 mem-brk를 old_brk로서 반환한다.
• extend 후 external fragmentation으로 남아있던 가용 블록을 합쳐준다.

 

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

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

    /* Allocate an even number of words to maintain alignment */
    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);
}

void *mem_sbrk(int incr) 
{
    char *old_brk = mem_brk;

    if ( (incr < 0) || ((mem_brk + incr) > mem_max_addr)) {
	errno = ENOMEM;
	fprintf(stderr, "ERROR: mem_sbrk failed. Ran out of memory...\n");
	return (void *)-1;
    }
    mem_brk += incr;
    return (void *)old_brk;
}

 

4. mm_malloc

• 2 word alignment를 맞춘다.
• find_fit 함수를 통해 적절한 가용 블록을 찾아 place스 함수를 통해 할당한다.
• 적절한 가용 블록이 없으면 extend_heap 함수를 통해 힙의 크기를 늘려준다.

 

/* 
 * 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;      /* Adjusted block size */
    size_t extendsize; /* Amount to extend heap if no fit */
    char *bp;
    /* Ignore spurious requests */ 
    if (size == 0)
        return NULL;

    /* Adjust block size to include overhead and alignment reqs. */
    if (size <= DSIZE)
        asize = 2 * DSIZE;
    else
        asize = DSIZE * ( ( size + (DSIZE) + (DSIZE-1) ) / DSIZE); // '/'연산자는 '몫'!, 중간 DSIZE는 header와 footer

    /* 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) // extend_heap은 인자가 WORD 단위로 들어감
        return NULL;
    place(bp, asize);
    return bp;
}

 

5. mm_free

• 할당된 블록을 가용 블록으로 바꾸는 함수이다. 가용 블록으로 만든 후 coalesce 함수를 통해 합쳐준다.

 

/*
 * mm_free - Freeing a block does nothing.
 */
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);
}

 

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

    if (prev_alloc && next_alloc)
    { /* Case 1 */
        return bp;
    }

    else if (prev_alloc && !next_alloc)
    { /* Case 2 */
        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 3 */
        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);
    }

    else
    { /* Case 4 */
        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);
    }
    find_nextp = bp;
    return bp;
}

 

7. mm_realloc

• realloc 함수는 새로운 메모리 주소에 할당한 후 기존의 할당된 블록을 가용블록으로 만들어 주는 함수이다.

 

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free, 사이즈를 줄이거나 늘리는 함수 !
 */
void *mm_realloc(void *ptr, size_t size)
{
    void *oldptr = ptr;
    void *newptr;
    size_t copySize;
    
    newptr = mm_malloc(size);
    if (newptr == NULL)
      return NULL;

    // copySize = *(size_t *) ((char *)oldptr - SIZE_T_SIZE); // 원래 들어있던 코드 틀림
    copySize = GET_SIZE(HDRP(oldptr));

    if (size < copySize) // oldptr 사이즈가 새로 만들 newptr의 size보다 더 작은 경우
      copySize = size;
      
    //memcpy(destination, source, num)
    memcpy(newptr, oldptr, copySize); // newptr 위치에 oldptr 주소로부터 copySize 만큼 복사하기 
    mm_free(oldptr);
    return newptr;
}

 

8. find_fit (first-fit)

• 가용 블록을 찾는 함수이다. 항상 제일 처음을 가리키는 포인터 heap_listp부터 시작한다.

 

// first_fit
static void *find_fit(size_t asize)
{
    /* first-fit search */
    char *bp;

    // Search from next_fit to the end of the heap
    for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
    {
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
        {
            // If a fit is found, return the address the of block pointer
            return bp;
        }
    }

    return NULL; /* No fit */
}

 

8-2. find-fit (next-fit)

 

• first-fit이 아닌 next-fit을 이용하면 가용 리스트의 더 빠른 검색이 가능해진다.
• 할당된 블록 다음블록부터 찾는다.

 

// next_fit
static void *find_fit(size_t asize)
{
    /* first-fit search */
    
    char *new_bp;
    new_bp = find_nextp;

    // Search from next_fit to the end of the heap
    for (; GET_SIZE(HDRP(find_nextp)) > 0; find_nextp = NEXT_BLKP(find_nextp))
    {
        if (!GET_ALLOC(HDRP(find_nextp)) && (asize <= GET_SIZE(HDRP(find_nextp))))
        {
            // If a fit is found, return the address the of block pointer
            return find_nextp;
        }   
    }
    for (find_nextp = heap_listp; find_nextp != new_bp; find_nextp = NEXT_BLKP(find_nextp))
    {
        if (!GET_ALLOC(HDRP(find_nextp)) && (asize <= GET_SIZE(HDRP(find_nextp))))
        {
            // If a fit is found, return the address the of block pointer
            return find_nextp;
        }
    }
    return NULL; /* No fit */
}

 

9. place

• 가용 블록에 할당하는 함수이다.

 

static void place(void *bp, size_t asize)
{
        size_t csize = GET_SIZE(HDRP(bp));
    if ((csize - asize) >= (2 * DSIZE)) // Header와 footer를 포함하여 최소 4 word 필요 !
    {
        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));
    }
}