동적 메모리 할당 | Malloc Lab | (3) 기초적인 할당기 작동 원리, 구현

컴퓨터 시스템 책의 9.9장에 설명되어 있는 기초적인 버전의 할당기는 다음과 같은 방식을 채택하고 있다.

블록 포맷: 묵시적 가용 리스트
배치 전략: first-fit 전략
연결 전략
1. 즉시 연결: 블록이 반환될 때마다 인접 블록을 통합
2. 인접 블록의 가용여부 확인: 경계 태그(Footer) 활용

해당 버전의 작동 원리, 코드를 이해해보자.

기초적 할당기: overview

우리가 흔히 보는 가상 메모리 그림에서 힙 공간에 돋보기를 대본다고 생각해보자.

그럼 힙 공간은 메모리 블록들의 배열로 표현할 수 있다. (이 '블록들'은 앞 포스팅에서 얘기한 묵시적 가용 리스트 등의 자료구조이다.)

힙 공간을 처음 생성할 때(init)는 최초의 힙 공간을 할당받고, 정렬 패딩, 프롤로그 헤더와 푸터, 에필로그 헤더를 세팅한다.
1. 그 다음 chunck size(일반적으로 4096 byte = 4kb) 만큼 메모리 공간을 확보해놓는다.
그 다음, 개발자가 malloc()을 요청하면 필요한 만큼의 공간이 있는지 확인하고(find_fit), 있다면 메모리 할당(place), 없다면 추가적인 힙 공간을 할당받는다.
1. 이때, find_fit을 하는 전략은 여러가지가 있다. -> first fit, next fit, best fit
2. place를 하는 전략도 그냥 할당하는 전략 or 필요한 만큼만 할당하고 그 외 부분은 새로운 가용 블록으로 분리하는 전략이 있다.
개발자가 realloc()을 요청하면, 우선 요청한 size만큼 새롭게 malloc 하고, 기존에 있던 데이터를 새롭게 할당한 블록들에 복사한다.
개발자가 free()를 요청하면, 해당 포인터의 헤더와 푸터에 접근하여 할당 여부를 1에서 0으로 바꾼다.
1. 그 후 인접 블록들을 조사하여 가용 상태라면 연결한다. 이걸 free때마다 하면 즉시 연결, 모았다가 한번에 하면 지연 연결이라고 한다.

기초적 할당기: 코드

완성된 mm.c 파일의 코드를 기반으로 보다 자세하게 이해해보자

매크로 및 상수 선언

매크로는 묵시적 가용 리스트를 조작하기 위해 미리 정의해놓은 명령어라고 보면 된다.

(매크로는 함수와 달리 전처리 때 처리되며, 코드 삽입의 형태로 파일 내부에 들어가게 된다.)

아래는 함수들을 구현하는데 쓰이는 매크로들인데, 매크로부터 보면 이해가 안된다.

때문에 함수 코드를 먼저 보면서, 특정 매크로가 나온다면 다시 올라와서 어떤 메커니즘을 지원하는지 확인해보는 걸 추천!

/* 싱글워드 (4) or 더블워드 (8) 정렬 */
#define ALIGNMENT 8

/* 정렬 기준의 배수가 되도록 반올림 */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

/* 가용 리스트 조작을 위한 기본 상수 및 매크로 정의 */
#define WSIZE 4 /* Word and head/footer size (bytes) */
#define DSIZE 8 /* Double word size (bytes) */
#define CHUNKSIZE (1<<12) /* Extend heap by this amount (bytes)*/

/* 1을 12bit 왼쪽으로 shift. 즉, CHUNKSIZE = 2^12 = 4096 bytes
많은 시스템에서 페이지 크기는 4kb. 힙 확장은 일반적으로 페이지 크기의 배수로 확장함. */
#define MAX(x, y) ((x) > (y) ? (x) : (y))

/* 헤더에 넣을 정보 생성 (만약 size=16byte, 할당되었다면 PACK(16,1) = 17) */ 
#define PACK(size, alloc) ((size) | (alloc))

/* 주소 p에 접근하여 워드를 read, write */
#define GET(p) (*(unsigned int *)(p))               
#define PUT(p, val) (*(unsigned int *)(p) = (val))

/* 주소 p에 접근하여 size, allocated fields 읽기 */
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)

/* bp(block ptr)가 주어지면 header, footer의 주소를 계산 */
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

/* bp(block ptr)가 주어지면, 이전 블록과 이후 블록의 주소를 계산 */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE((char *)(bp) - WSIZE))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE))

static void *heap_listp;

함수

실제 할당기의 동작을 담당하는 함수부를 살펴보자.

가장 기본이 되는 init(), malloc(), free() 함수가 있고

이들의 수행을 위해 필요한 서브 함수 extend_heap(), coalesce(), find_fit(), place()가 있다.

mm_init()

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)); /* 프롤로그 header */
    PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1)); /* 프롤로그 footer */
    PUT(heap_listp + (3*WSIZE), PACK(0, 1)); /* 에필로그 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;
}

mm_init은 처음에 힙 공간을 할당받는 함수이다. 할당받은 공간에 최초의 가용 블록 포맷을 세팅한다.

extend_heap()

/* extend_heap() extends the heap with a new free block */
static void *extend_heap(size_t words){
    char *bp;
    size_t size;

    /* 정렬을 유지하기 위해 짝수 개의 워드를 할당 */
    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);
}

extend_heap은 적합한 블록 공간이 없을 때, 1) 새로운 힙 공간을 할당받고 2) 그곳에 블록 포맷을 세팅하는 함수이다.

words를 인자로 받고, words를 정렬 기준에 맞도록 짝수로 조정하여 최종 size를 도출한다.
이 중 페이로드(데이터)를 위한 공간은 헤더와 푸터 각 1 워드를 제외한 (size - 더블워드) 이다.
bp는 페이로드가 시작하는 지점을 가리키고 있다.

할당 과정이 끝난 이후에, 마지막으로 이전 블록이 가용(free) 상태이면 이전 블록과 연결 작업을 수행한다.

mm_malloc()

/* mm_malloc - brk 포인터를 증가시켜 블록을 할당.
항상 크기가 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;

    /* fake 요청은 무시 */
    if(size == 0){
        return NULL;
    }

    /* 오버헤드 및 정렬 요구 사항을 포함하도록 블록 크기를 조정 */
    if (size <= DSIZE){
        asize = 2*DSIZE;
    }
    else {
        asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);
    }

    /* 적합한 free list 탐색 */
    if ((bp = find_fit(asize)) != NULL ){
        place(bp, asize); // 찾은 위치에 asize 만큼 메모리 배치
        return bp;
    }

    /* No fit found. 추가 메모리 할당 및 블록 배치 */
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL){
        return NULL;
    }
    place(bp, asize);
    return bp;
}

malloc()은 실제 우리가 힙 공간의 메모리 할당 요청을 할 때 동작하는 함수이다.

우선 메모리 할당은 항상 정렬 기준을 맞춘다. 그래야 전체적인 포맷이 유지되어 검색과 할당이 용이하기 때문.

정렬 기준에 맞추기 위해 요구받은 필요한 size를 더블 워드의 배수에 맞춘 asize (adjusted size)를 계산한다.
find_fit을 통해 asize를 담을만한 free list를 탐색한다.
1. 찾았다면, place(asize)를 통해 해당 공간에 메모리 할당!
  1. 분할 전략: 남는 메모리 공간은 새로운 가용 블록으로 분할된다.
2. 못 찾았다면, extend_heap()을 통해 새로운 힙 공간 확보 -> 이후에 place()

find_fit()

static void *find_fit(size_t asize)
{
    /* First-fit search */
    void *bp;
    // 에필로그 헤더를 만날 때까지 옆 블록으로 이동하면서 순회
    for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)){
        // 할당되지 않았고, asize보다 크다면
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))){ 
            return bp;
        }
    }
    return NULL; /* No fit */
}

first fit 전략에서의 find_fit은 힙의 처음부터 끝까지 쭉 순회한다.

이 경우, 이용도 측면에서는 이득을 보지만 쓰루풋 측면에서는 손해를 볼 수 있다.

왜냐하면 작은 블록이든 큰 블록이든 앞에서부터 할당하기 때문에, 할당과 반환을 반복하다보면 앞에 애매한 빈 공간이 많이 생기게 되기 때문이다. 따라서 나중에는 큰 블록 할당 요청이 들어올 경우 매번 뒤쪽까지 탐색해야 하므로 시간복잡도 측면에서 손실이 발생한다.

place()

// 분할 전략: 필요한 만큼만 할당하고 남은 부분은 가용 블록으로 분할
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)); // 필요한 부분을 제외한 나머지는 free로 분리
        PUT(FTRP(bp), PACK(csize-asize, 0));
    }
    else {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));        
    }
}

place는 해당 free list에 요청받은 size를 할당하고, 분할 전략에 따라 남은 공간은 새로운 가용 블록으로 분리하는 함수이다.

mm_free()

/* 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); // 즉시 연결
}

free는 해당 가용 공간의 할당여부를 1 -> 0로 바꿔준다.

그 다음 즉시 연결 전략에 따라 바로 coalesce()를 수행하고 있다.

coalesce()

static void *coalesce(void *bp)
{
    // GET_ALLOC: 해당 주소의 마지막 비트 반환 -> 헤더 or 푸터라면, 할당됐으면 1, 아니면 0 반환됨
    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문에서 0은 false, 그 외 숫자는 true로 인식
    if (prev_alloc && next_alloc){              /* Case 1. 이전 & 다음 not free */
        return bp;
    } 
    else if (prev_alloc && !next_alloc){        /* Case 2. 다음 블록 free */
        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. 이전 블록 free */
        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. 이전 & 다음 free */
        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);
    }
    return bp;
}

앞 뒤 인접 블록을 조사한 다음, 가용 블록이라면 현재 블록과 합쳐 더 큰 하나의 블록으로 만드는 과정이다.

mm_realloc()

/*
 * mm_realloc - mm_malloc 및 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));
    // copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
    if (size < copySize)
      copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}

realloc은 우선 새로운 공간을 malloc으로 할당받고, 이전 메모리 공간에 있던 데이터를 그대로 옮겨오는 전략을 취하고 있다.

결과

위와 같은 설계로 할당기를 구현했을 때 총점 53점이 나왔다. (ubuntu 환경 기준)

utilization(이용도)은 높지만 throughput(처리량)은 많이 낮은 것을 확인할 수 있다.

'Computer Science > 컴퓨터 구조 (Computer Architecture)' 카테고리의 다른 글

가상메모리 \| (1) 개발자 코드가 물리 메모리에 닿는 과정 (2)	2023.11.14
동적 메모리 할당 \| Malloc Lab \| (4) 할당기 배치 전략 개선 (next fit) (0)	2023.11.14
동적 메모리 할당 \| Malloc Lab \| (2) 과제 소개 (0)	2023.11.11
동적 메모리 할당 \| Malloc Lab \| (1) Malloc은 어떻게 구현되는가? (2)	2023.11.10
동적 메모리 할당 \| 기본 개념, 메모리 누수, 단편화 (1)	2023.11.04

잔잔한 물결로 파도 만들기

동적 메모리 할당 | Malloc Lab | (3) 기초적인 할당기 작동 원리, 구현

기초적 할당기: overview

기초적 할당기: 코드

매크로 및 상수 선언

함수

mm_init()

extend_heap()

mm_malloc()

find_fit()

place()

mm_free()

coalesce()

mm_realloc()

결과

'Computer Science > 컴퓨터 구조 (Computer Architecture)' 카테고리의 다른 글

티스토리툴바

동적 메모리 할당 | Malloc Lab | (3) 기초적인 할당기 작동 원리, 구현

기초적 할당기: overview

기초적 할당기: 코드

매크로 및 상수 선언

함수

mm_init()

extend_heap()

mm_malloc()

find_fit()

place()

mm_free()

coalesce()

mm_realloc()

결과

'Computer Science > 컴퓨터 구조 (Computer Architecture)' 카테고리의 다른 글

'Computer Science/컴퓨터 구조 (Computer Architecture)' Related Articles

티스토리툴바

기초적 할당기: overview