동적 메모리 할당(Dynamic memory allocation), malloc 함수 구현 (malloc lab)

메모리는 한정된 자원이다. 기술이 많이 발전했지만, 아무리 메모리가 많아도 부족한 자원이라는 것도 사실인 듯 하다. 그래서 개발에 있어서 메모리 관리(Memory management)는 여러가지 핵심요소 중 하나다.

 

오늘은 동적메모리 할당에 대해 정리해보고, C를 통해 Malloc을 구현한 것을 정리하고자 한다.

대부분의 내용은 Computer system(Randal E. Bryant)에 있는 내용이다. (진짜 좋은 책인데 번역이 ....  )

---

정적 메모리 할당 (static memory allocation)

동적 메모리 할당에 앞서 대응되는 개념으로 정적 메모리 할당이라는 단어를 사용할 것 같았다. 찾아서 잠깐 간단히 설명...

프로그램이 실행되기 위해서는, 프로그램 구성 요소들 (코드와 다양한 변수등의 데이터, 인스트럭션 등)이 메모리로 올려져야 함. 이때, 올려지는 메모리 중 프로그램의 코드가 존재하는 코드 영역이 있고, 전역, 정적 변수들이 있는 데이타 영역이 있음. 이러한 영역에 할당되는 경우, 정적 메모리 할당이라고 말하는데 그이유는 메모리가 컴파일 단계에서 확정되어 올려지기 때문임, 해당 메모리 영역은 프로그램이 종료시까지 할당된 상태로 유지된다. 

참고로 코드영역, 데이터영역은 낮은 주소에 위치함.

---

동적 메모리 할당과 malloc

프로그램 런타임(실행 중)에 메모리를 필요한 만큼 할당받는 것을 의미. 할당 뿐만 아니라 다쓰고 반납까지 가능. 필요한 만큼만 받고 또 필요한 때에 사용하고 반납해서 메모리를 효율적으로 사용 할 수 있는 것이다. 

프로그램 실행시 메모리가 얼마나 필요할지 가늠이 어려운 상황에서, 정적으로 미리 메모리를 할당 받아 버리면 프로그램 종료시까지 실제로 필요 이상의 메모리를 차지하는 문제가 있다. 이런 상황에서 효과적으로 사용할 수 있다. 

 

이러한 동적 메모리 할당과 반환은 힙영역에서 이루어진다. 힙 영역은 주소 기준으로 미초기화영역(uninitialized data) 바로 위부터 시작되며 위로 확장된다. 할당받은 부분이 반환되면 다시 줄어들기도 가능.. 하기 그림 참조하면 좋을 것 같다. 하기 그림은 메모리 세그멘트 구조를 대략적으로 나타낸 그림이다. 각 세그먼트는 서로에게 불가침의 영역이다. 

 

C에서 동적 메모리는 malloc() 계열의 라이브러리 함수를 할당받아 사용한다. 

할당을 해주는 malloc, 할당을 해제하여 사용에서 가용으로 다시 변경시키는 free 함수가 있다. 

동적 메모리에서 중요한 포인트는 사용이 끝나면 반드시 해당 메모리 영역을 명시적으로 반납해야한다. 반납하지 않으면 해당 메모리는 사용 불가하며, 사용하지 않는 공간을 무언가가 계속 차지하고 있어서 낭비되는 현상을 메모리 누수(memory leak)라고 한다.

 

힙 영역과 메모리 할당기 (Allocator)

힙 영역은 다양한 크기의 블록들의 집합들로 관리된다. 각 영역은 아래 그림 처럼 할당이 되어있거나, 할당되어 있지 않은 가용 블록의 상태로 존재한다. 블록 내부의 기본 단위를는 word라고 부른다. 흰색이 가용블록..

힙 영역을 블록단위로 관리하는 도구를 메모리 할당기라고 부른다. 

 

할당기 역할 간단히 설명..

1. 초기에 설정된 힙영역이 있음. 해당 영역에서 메모리가 할당이 되었다가 해제가 되었다가 사용됨. 이에 따라 메모리 중간중간에 사용가능한 공간들이 생기게 된다.

2.  특정 사이즈의 메모리 할당 요청시 그때 그때 메모리 곳곳에 있는 할당 가능한 블록들을 탐색하며 요청받은 사이즈에 맞는 가용블록을 찾아준다. 혹은 가용블록이 없으면 힙영역을 위로 확장시켜서 새로운 주소로 할당 해주는것이 할당기의 역할.  

 

할당기(allocator)는 두가지 타입이 존재한다. Implicit(묵시적), Explicit(명시적) 할당기. 

• Explicit Allocator - 명시적으로 malloc, free 를 통해 공간 할당 및 해제하는 방식으로 메모리를 관리한다. C 표준 라이브러리인 Malloc이 대표적인 예시이다.
  - Implicit free list - 메모리 할당 과정에서 현재 사용 가능한 Free block 들을 탐색하는 방식을 채택한다. 
  - Explicit free list - 현재 사용가능 한 Free block들을 별로의 자료구조 형태로 관리하는 방식을 채택한다. Malloc시에 적합한 사이즈의 블록을 탐색하는 시간을 줄일 수 있는 장점이 있다. 

 

• Implicit Allocator - 묵시적으로 사용자가 할당받고 free하지 않은 애들을 자동(?)적으로 정리해줌. 가비지 컬렉터 같은 예시가 있다.

두 가지 타입 모두 결국에는 응용 프로그램이 명시적으로 블록들을 할당하도록 요청해야 하긴한다...

 

할당기의 기본 요구사항과 목적 (requirements & Goal) - 간단히 알아보겠다. (자세히는 책보길 추천 pdf도 있다는.. )

• Handling arbitrary request sequences - 메모리를 할당 받고, 반환에는 순서가 랜덤임. 랜덤한 request에 대응 가능할 것
• Making immediate responses to requests - 요청에 즉각적으로 반응할 것 (할당, 반환 해주거나, 불가능 하다는 메세지)
• Using only the heap - 힙 영역 내에서 이뤄져야함.
• Aligning blocks (alignment requirement) - 메모리 정렬 조건에 맞추어 할당되어야 한다. 간단히 이해하고자 한다면 최소 할당 기본단위가 있다고 생각해도 구현에 어려움은 없다.
  (더 보기)alignment requirements에 관해 궁금한 점이 있어서 문의한 내용 (안 궁금하면 skip해도 됨)
  

  alignment가 왜 꼭 되어야 하는가라는 이유에 관해서는 다른 개념들과 복합적으로 얽혀있다. malloc 함수 자체를 구현하기 위한 필수조건이라기보다. 다른 기타 Hardware, CPU 요구 사항 혹은, 메모리 access를 위한 효율성 개선 목적이 반영되어 있다. Alignment requiremet에 대해 의문 점이 있었다. 정렬 제한조건은 보통 Double word로 제한되어 있었는데, 단지 구현 너머의 하드웨어적인 이유가 있지 않을까 궁금했다. 전산학 대학원 조교님께 문의드렸고 하기와 같은 답변을 얻을 수 있었다. 

  alignment가 왜 꼭 되어야 하는가라는 이유에 관해서는 다른 개념들과 복합적으로 얽혀있다. malloc 함수 자체를 구현하기 위한 필수조건이라기보다. 다른 기타 Hardware, CPU 요구 사항 혹은, 메모리 access를 위한 효율성 개선 목적이 반영되어 있다.Alignment requiremet에 대해 의문 점이 있었다. 정렬 제한조건은 보통 Double word로 제한되어 있었는데, 단지 구현 너머의 하드웨어적인 이유가 있지 않을까 궁금했다. 전산학 대학원 조교님께 문의드렸고 하기와 같은 답변을 얻을 수 있었다. 

  

  질문 내용

  

  바쁘신 조교님의 귀한 답변..

   

  ---

• Not modifying allocated blocks - 할당받은 블록이 다른 요청에 의해 수정되거나 영향받으면 안됨
• 할당과 반환요청에 들어가는 평균 시간을 최소화해서 처리량을 최대화 해야한다.
• 단편화를 최소화해서 힙영역의 이용도를 최대화시켜야 한다. 

단편화 (Fragmentation)

어려운 개념이 아니다. 말 그대로 메모리가 가용가능한 메모리가 한곳에 모여있는 것이 아니라, 파편화 되어 떨어진 위치에 존재하게 되고 이에 따라 메모리의 효율적인 사용이 어려워지는 개념이다. 동적 메모리 할당 과정에서 구조적, 필연적으로 발생할 수 밖에 없다. 단편화의 이유를 알아두고 어떤 알고리즘마다 단편화에 얼마나 취약하고, 단편화에 취약해지는 만큼 트레이드 오프로 얻는 이점은 무엇인지 이해하는 것이 중요하다.  

내부 단편화는 메모리를 할당받는 과정에서 정렬제한 조건등의 이유로 필요한만큼보다 더 얻게 되는 경우 잉여 메모리공간이 생기는 것을 의미 

외부 단편화는 할당 요청받은 사이즈 이상의 가용블록이 힙영역에 존재하지만, 파편화 된 상태로 존재해서 사용이 불가능한 상황을 의미한다. 

 

Explicit Allocator인 Malloc, free 구현 ( w/ Implicit Free list)

Implicit Free list(묵시적 가용리스크)를 사용하는 Malloc 을 구현을 위해 어떤 기능들이 있어야 하고 어떤 부분이 고려되어야 하는 부분이 아래와 같다.

 

1. 힙 영역의 시작과 끝 부분 및 각 가용블록의 경계표시, 블록의 사이즈, 할당여부 표기법

2. 할당가능 블록 탐색 및 배치

3. 할당시 가용리스트 분할

4. 할당 불가능시에 추가 힙 영역 획득

5. 인접한 가용리스트의 끼리의 연결

 

 

1. 힙 영역의 시작과 끝 부분 및 각 가용블록의 경계표시, 블록의 사이즈, 할당여부 표기법

묵시적 가용리스트의 불변하는 형식

힙 영역은 Prologue block과 Epiloge block으로 경계가 구분된다. 

각각의 블록은 블록 사이즈 정보와 가용여부가 표기되어있는 header와 footer로 경계가 구분된다.

header와 footer는 각 1word 이며, 사이즈/가용 여부가 명시되어 있다. 

할당 상태

가용 상태

 

2. 할당 가능 블록 탐색 및 배치

묵시적 가용 리스트의 경우 가용리스트를 따로 관리하지 않고, 때마다 요청 블록 size와 맞는 블록을 탐색해서 찾는다.

방법은 다양하지만 교과서에는 3가지 방법이 소개되어 있다. First fit / Next fit / Best fit 

 

Fisrt fit - 힙 시작점부터 탐색한다. 요청에 맞는 첫 번째 블록발견시 채택하는 아이디어

Next fit - 마지막으로 가용블록을 발견한 지점부터 탐색을 시작하면 확률적으로 유리하다는 아이디어

Best fit - 전체를 탐색하는 아이디어

 

Next fit은 확률적인 접근이다. 실제로 구현해보니 first fit보다 개선된 것을 확인할 수 있었다.

Best fit의 경우 힙 전체를 검색해야하는 단점이 있다. 다만, 가장 알맞는 사이즈의 블록을 찾을 수 있기 때문에 메모리 이용도는 다른 방법보다 우수하다.  

 

 

3. 가용 블록의 분할

발견한 가용블록이 크기가 큰 경우 두가지 옵션이 있다.

1. 그대로 채택한다. 

2. 필요한 부분만 잘라서 쓰고, 나머지 부분은 가용블록으로 변경한다. 

(1의 경우 내부 단편화에 조금 더 취약하다.)

 

4. 할당 불가능시에 추가 힙 영역 획득

기존 힙 영역에 할당 가능한 가용블록이 없는 경우 힙영역을 상단으로 확장시켜서 추가로 메모리를 할당 받는다.

sbrk 라는 함수를 활용한다. sbrk함수는 heap 영역의 최상단에 위치한 ptr를 incr 만큼 이동시키는 함수이다. 

/* 
 * mem_sbrk - simple model of the sbrk function. Extends the heap 
 *    by incr bytes and returns the start address of the new area. In
 *    this model, the heap cannot be shrunk. (실제 모델에서는 축소도 가능)
 */
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;
}

5. 인접한 가용리스트의 끼리의 연결

4가지 case가 있다,

case 1. 앞, 뒤 모두 가용 블록이 아닌 경우 ->연결 불가능

case 2. 뒷 부분이 가용블록인 경우 -> 뒷 부분과 연결

case 3. 앞 부분이 가용블록인 경우 -> 앞 부분과 연결

case 4. 앞, 뒤부분 모두 가용블록인 경우 ->세 영역 결합.

전체 구현 C 코드 (Next-fit으로 구현, first-fit은 주석처리)

#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 */
    "team 6",
    /* First member's full name */
    "Kim, Jinyoung",
    /* First member's email address */
    "@naver.com",
    /* Second member's full name (leave blank if none) */
    "Ahn, solomon,   Lee jae yeol",
    /* Second member's email address (leave blank if none) */
    "@naver.com"
};

/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

/* Basic constants and macros */
#define WSIZE 4  /* size of word, head, footer */
#define DSIZE 8   /* Double word size */
#define CHUNKSIZE (1<<12) /*Extend heap by this amount(bytes)*/

//2^12 bytes = 4KB 
#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 btr bp, compute address of its header and fotter */
#define HDRP(bp)   ((char *)(bp)-WSIZE)
#define FTRP(bp)   ((char *)(bp)+ GET_SIZE(HDRP(bp)) - DSIZE)
/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
/* Basic constants and macros - end */


/* Private global variables */
static char *heap_listp;
static char *next_listp;
static void *extend_heap(size_t words);
static void *coalesce(void *bp);

/* 
 * 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);                          /*alignment padding*/
    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(DSIZE,1));  /*Epilogue header*/
    heap_listp += (2*WSIZE);

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

// first fit 주석처리 
// static void *find_fit(size_t asize)
// {
//     /*first-fit search - find from starting point */
//     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; /*no fit*/

    
// }

    
static void *find_fit(size_t asize)
{
    /*Next-fit search*/
    if (next_listp==NULL){next_listp=heap_listp;}
    void *bp;
    /*search from last points to end of the free*/
    for (bp=next_listp; GET_SIZE(HDRP(bp)) >0; bp=NEXT_BLKP(bp)){
        if(!GET_ALLOC(HDRP(bp))&&(asize <= GET_SIZE(HDRP(bp)))){
            next_listp=bp;
            return bp;
        }
    }

    for (bp=heap_listp; HDRP(bp) != HDRP(next_listp); bp=NEXT_BLKP(bp)){
        if(!GET_ALLOC(HDRP(bp))&&(asize <= GET_SIZE(HDRP(bp)))){
            return bp;
        }
    }
    return NULL; /*no fit*/
}



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


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));
    void*temp=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);
        if (temp==next_listp){
            next_listp=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);
        if (temp==next_listp){
            next_listp=bp;
        }
    }
    next_listp=bp;
    return bp;
}

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;
    
    /* Initialize free block header/footer and the epilogue header */
    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);

}

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

    /*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_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);
}


/*
 * 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 = GET_SIZE(HDRP(oldptr));

    if (size < copySize)
      copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}