[프로젝트] malloc lab 프로젝트

예니·2021년 1월 21일
1

프로젝트

목록 보기
7/8
post-thumbnail

카네기 멜런 대학교의 malloc lab 프로젝트를 진행했다.
📅 기간 : 2021.01.14 ~ 2021.01.21


C언어는 malloc, free 함수로 heap 영역에 메모리를 동적으로 할당할 수 있다.
그동안 그냥 사용하던 malloc, free 함수를 직접 구현해보는 과제였다.
malloc lab 과제 설명

구현 방식에는
1. implicit free list
2. explicit free list
3. segregated free list
이렇게 세 가지가 있다.
우리는 1,2번의 방식으로 구현해봤다.

자세한 내용은 구글링하면 양질의 자료가 아주 많이 나오므로 생략한다.

내용 정리보다는 발생했던 에러들과 그것을 해결한 과정들 위주로 글을 적어보려 한다.


💡 새로웠던 점

1. #define 매크로 함수 사용

#define 으로 상수는 선언해봤지만 함수는 선언해본 적이 없고, 가능한지도 몰랐었다. 이번에는 많은 함수들을 매크로 함수로 사용했다.
매크로 함수는 일반 함수와는 달리 단순 치환만을 해주므로, 일반 함수와 완전히 똑같은 방식으로 동작하지는 않는다. 매크로 함수는 인수를 컴파일 이전에 미리 치환하기 때문에 주의할 점은 각 인수를 모두 괄호(())로 묶어줘야 한다는 점이다.

2. aws ubuntu 환경 사용

사전과제를 진행할 때도 aws ubuntu 환경을 사용했었지만, 그땐 단지 서버용이었다. 이번에는 실행 환경을 통일하기 위해 모두 aws를 이용해 ubuntu 환경에서 실습을 진행했다. 덕분에 VScode FTP simple 같은 유용한 도구도 사용해볼 수 있었다.
그동안은 코드를 작성하면 CLion 같은 IDE가 알아서 빌드해주고 실행해줬는데, 이번에는 make clean, make 명령어로 직접 컴파일했다.
다행히, 마침 듣고 있던 missing semester (MIT) 수업의 metaprogramming 강의에서 해당 부분을 다뤄줘서 이해할 수 있었다.

3. 컴퓨터 시스템 책

reading 과제로 1장을 읽을 때는 '이게 무슨 외계어지 ... ' 라는 생각만 들었는데, 이번 과제를 진행하면서 9장 가상메모리 부분을 읽으니 나름 재밌었다. 이렇게 컴퓨터 시스템 책이랑 점점 가까워져야지 !


💡 Implicit

(출처 : 카네기 멜런 대학교 강의자료)

제일 간단한 방식이고, 책에 있는 그대로 구현하면 된다.
경계 태그를 이용해서 경계와 할당/가용 여부를 판단한다. 전체 블록을 다니면서 가용 블록을 확인한다.
첫번째로 진행한 방식이라 매크로와 구조를 이해하는 것부터 힘들었다.

1. PACK, GET_SIZE, GET_ALLOC

#define PACK(size, alloc) ((size) | (alloc))
헤더, 푸터는 블록의 정보를 담고 있는 블록의 맨앞, 맨끝에 위치한 각각 4바이트를 차지하는 애들이다. (4byte == 32bit)
block의 size는 8의 배수이므로 크기에서 하위 3bit는 당연히 000이 된다. (111~001 은 7~1 이니까 얘네 있으면 나머지 생겨서 8의 배수가 될 수 없음)
그래서 하위 3bit 중 최하위 1bit는 할당여부를 나타내는 데에 사용한다.
alloc 여부는 001, 000 중 하나이므로 (앞에는 모두 0), size와 alloc의 and연산을 진행하면 size, alloc에 대한 정보를 모두 담을 수 있다.

#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
위에 적은 것처럼, size를 얻을 때는 하위 3bit를 000으로 만들고 and 연산을 진행하면 되고, 할당 여부를 얻을 때는 최하위 1bit를 0으로 만들고 and 연산을 진행하면 된다.


2. HDRP, FTRP, NEXT_BLKP, PREV_BLKP

#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
bp는 data의 시작 지점을 가리킨다.
블록의 크기에 대한 정보는 헤더, 푸터에 담겨있으므로 헤더나 푸터로 이동해서 정보를 구해야한다.


3. coalesce 함수

(출처 : 카네기 멜런 대학교 강의자료)

블럭이 가용블럭이 될 때, 앞뒤 블럭의 상태를 살펴서 연결해줘야 한다.
위의 네가지 케이스가 발생할 수 있다.
이때 2번 케이스에서 헷갈린 점이 있었다. 코드를 보자.

    else if(prev_alloc && !next_alloc){
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0)); 
    }

다음 블럭과 합친 것이므로 PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));가 되어야할 줄 알았는데 FTRP를 HDRP를 이용해서 구하므로 그냥 PUT(FTRP(bp), PACK(size, 0));로 적어줘도 됐다.

3,4번 케이스의 경우, PUT 이전에 bp를 이전 블럭으로 옮겨주면 PUT을 2번과 똑같이 적을 수 있다.


4. malloc 함수

    if (size <= DSIZE){
        asize = 2*DSIZE;
    }
    // 8바이트 넘는 요청 : 오버헤드 바이트 내에 더해주고 인접 8의 배수로 반올림
    else{
        asize = DSIZE * ((size+(DSIZE)+(DSIZE-1))/DSIZE); // 8 더하고 (헤더, 푸터), 8의 배수로 올림 
    }

size를 8바이트 정렬로 만들어주는 작업 부분의 코드이다.
#define ALIGN(size) (((size) + (ALIGNMENT - 1) & ~0x7)) 매크로에 ALIGN을 정의해뒀으므로 이 매크로를 이용하면 더 간단하게 아래와 같이 단 한 줄로 바꿀 수 있다.

asize = MAX(DSIZE + ALIGN(size), 2*DSIZE);

5. extend_heap 함수

size = (words % 2) ? ((words + 1) * WSIZE) : (words * WSIZE);

인자로 받은 words가 홀수면 인접 2의 배수로 올리고, 짝수면 그냥 둬서 size를 구한다. 근데 코드를 살펴보니 extend_heap을 호출하는 과정에서 인자로 절대 홀수가 들어가지 않는 것을 발견했다. 즉, 위의 코드를 삭제해도 전혀 문제가 없다.


6. find-fit 함수

  1. First-fit
static void *find_fit(size_t asize){
    first fit (for)
    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;

first-fit은 맨처음부터 찾다가 사이즈 맞는 블럭을 발견하면 할당한다.

  1. Next-fit
    if((next_ptr > (char *)bp) && (next_ptr < NEXT_BLKP(bp))){
        next_ptr = bp;
    }

coalesce 함수에 위 코드를 추가해준다.
연결 과정에서 next_ptr이 연결된 블럭 중간에 남아있을 수 있기 때문에 이 경우, 블럭의 시작 지점으로 ptr을 당겨줘야하기 때문이다.

    char *bp = next_ptr;
    for(; GET_SIZE(HDRP(next_ptr)) > 0; next_ptr = NEXT_BLKP(next_ptr)){
        if (!GET_ALLOC(HDRP(next_ptr)) && (asize <= GET_SIZE(HDRP(next_ptr)))){
            return next_ptr;
        }
    }

    for (next_ptr = heap_listp; next_ptr < bp; next_ptr = NEXT_BLKP(next_ptr)){
        if (!GET_ALLOC(HDRP(next_ptr)) && (asize <= GET_SIZE(HDRP(next_ptr)))){
            return next_ptr;
        }
    }
    return NULL;
  • 위 for문 : next_ptr에서 시작해서 끝까지 찾아서 맞는 블럭이 있으면 할당한다.
  • 아래 for문 : 위 for문에서 못찾았다면 처음부터 next_ptr까지 검사해서 찾으면 할당한다.

💡 Explicit

(출처 : 카네기 멜런 대학교 강의자료)

Explicit free list 방식에서는 가용블럭끼리 double linked-list로 만들어서 관리한다.

#define PREDP(bp)    (*(char **)(bp))
#define SUCCP(bp)    (*(char **)(bp + WSIZE))

가용블럭을 헤더, 이전 가용 블럭(PRED), 다음 가용 블럭(SUCC), 푸터 의 구조로 만든다.
위와 같이 가용블럭들을 연결해주는 PREDP, SUCCP 매크로를 정의해서 사용한다.

이 방식에서는 1. 가용블럭이 malloc될 때, 가용리스트에서 제외시켜주는 과정2. 블럭이 free될 때, 가용리스트에 연결해주는 과정이 추가적으로 필요하다.


1. 가용블럭이 malloc될 때, 가용리스트에서 제외시켜주는 과정

이 과정을 진행해주는 byeBlock 함수를 새로 만들고, 기존에 사용하던 place 함수에 byeBlock 과정을 추가해준다.

static void byeBlock(void *bp){
    if(PREDP(bp) == NULL){
        free_listp = SUCCP(bp);
    }
    else{
        SUCCP(PREDP(bp)) = SUCCP(bp);
    }
    if(SUCCP(bp) != NULL)
        PREDP(SUCCP(bp)) = PREDP(bp);
}

byeBlock 함수의 코드는 위와 같다.
free_listp는 가용리스트의 맨앞 블럭을 가리키고 있는 포인터이다.
가장 먼저 맨앞 블럭인지 아닌지를 확인하고, 그 안에서 맨뒤 블럭인지 아닌지를 확인해서 각 분기에 맞게 연결 상태를 바꿔준다. 앞쪽에 있는 블럭을 형, 뒤쪽에 있는 블럭을 동생으로 생각하면, 나 자신이 사라질때 형에게 동생을 맡기고, 동생에게 형을 연결시켜준다고 생각하면 이해하기 쉽다.

place함수에서는 블럭이 할당될 때마다, byeBlock함수를 실행해주면 된다.


2. 블럭이 free될 때, 가용리스트에 연결해주는 과정

이 과정은 블럭을 free한 후 실행되는 coalesce함수에서 진행된다.
찾아보면 나오는 많은 자료에서 그림으로 표현하는데, 그림은 많이 복잡하다.
그냥 간단히 생각하면, 연결해줄 때 원래 가용리스트에 있던 블럭이면 그건 빼주고 연결을 통해 합쳐진 가용블럭의 맨앞 위치를 가용리스트에 넣어주면 된다.

가용리스트에 새로 넣어주는 과정은 연결 과정 이후 진행하는데, 아래와 같다.

// 가리키고 있는 애가 있을 때와 없을 때로 분기 
    if (free_listp == NULL){ // 가리키고 있는 애 없을 때는 맨처음에 그냥 넣음 
        free_listp = bp;
        PREDP(bp) = NULL;
        SUCCP(bp) = NULL;
    }
    else{ // 가리키고 있는 애 있을 때는 연결 상태 바꿔줘야지, 이거 순서 매우 중요함 ! (free listp 덮어쓰지 않도록)
        SUCCP(bp) = free_listp;
        PREDP(free_listp) = bp;
        PREDP(bp) = NULL;
        free_listp = bp;
    }

free_listp가 가리키고 있는 블럭이 없다면 가용리스트가 비어있는 상태이므로, free_listp가 이 블럭을 가리키게 하고, 별도의 연결과정은 필요없다.
가용리스트가 비어있는 상태가 아니라면, 연결 상태를 바꿔줘야한다.
이때, free_listp가 가리키고 있는 블럭을 바꾸는 과정을 가장 나중에 진행해야 한다.

이외의 과정은 모두 implicit과 동일하다.


0개의 댓글