[week05] Malloc Lab 회고

쏭웬·2023년 9월 13일

목록 보기

7/11

91점

이번주도 어떻게 지나갔는지 모르겠지만 지나고보니 말록랩을 마무리했다. 91점이라는 멋진 점수를 얻게되어서 기쁘다. 버디는 구현하지 못했지만 핀토스를 할 때의 내가 할 수 있을 거라 믿고 일단 넘어간다.

MALLOC LAB

Implicit free list

메모리 공간의 처음부터 블록들을 탐색하면서 블록이 할당됐는지 아닌지 확인하는 방식이다. 헤더의 남는비트를 이용해서 ALLOC을 체크한다. 포인터로 연결되어 있지 않고 그냥 현재 블록 사이즈 체크해서 다음블록 순차적으로 확인하는 방법이라 구현이 간단하지만 당연히 시간이 더 걸린다.

기본 (FIRSTFIT)

⌨️ 소스코드

53점

이건 책에 코드가 그대로 적혀있다. 그대로 적혀있는걸 타이핑 하는데도 Segmentation Fault 늪에 빠졌었다. 여기서 Seg fault 99% 확률로 오타때문에 발생한다. 이걸 하면서 과제 자체를 이해하고 세부적인 함수랑 친해질 수 있었다. 이것만 해도 53점..!

NEXTFIT

static void *next_fit(size_t asize) {
    void *bp;
    for (bp = cur_p; GET_SIZE(HDRP(bp)) > 0 ; bp = NEXT_BLKP(bp)) { // 에필로그 헤더까지 
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
            cur_p = bp;
            return bp;
        }   
    }

    bp = heap_listp;
    for (bp = heap_listp; bp!=cur_p ; bp = NEXT_BLKP(bp)) { // 처음부터 
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
            cur_p = bp;
            return bp;
        }
    }
    return NULL;
}

기존엔 나보다 큰 free 블록을 메모리의 처음부터 찾았다면 이번엔 마지막에 할당된 애 다음부터 찾는 방식이다. 초반에 free된 애들이 많을 땐 빠를 수 있지만 최악의 경우는 firstfit보다 안좋다. 하지만 이 과제에선 next-fit으로만 바꿔줘도 바로 80점이 나온다. 이걸 보면 대부분의 경우는 next-fit이 더 효율이 좋나보다.

Explicit free list

⌨️ 소스코드

free 블록만 '명시적으로' 연결리스트로 관리하는 방식이다. free-block만 있으니까 속도도 빨라진다.(=처리량이 높아진다) free-block은 페이로드 부분이 비어있으니까 거기에 next_free랑 prev_free 위치를 적어두는 방식으로 만든다. 과제 안내를 보면 새로운 구조체를 만들지 말라고 해서 헤드를 가리키는 포인터를 이용해 간단한 연결리스트를 구현했다.

캐시 지역성

새롭게 free된 블럭은 리스트의 맨 앞에 추가된다. 그 이유는 한번 참조했던 메모리 주소는 다시 참조할 가능성이 높아 cpu 캐시에 저장될 확률이 높아서이다. 아무래도 메모리에서 값을 가져오는 것 보다 캐시에서 가져오는 게 더 빠르기 때문에 LIFO 방식으로 리스트를 구현하는 게 좋다고 한다.

고생했던 부분

#define PREP(bp) (* (char **)(bp))
#define SUCP(bp) (* (char **)(bp + WSIZE))

지금 너무 쉬운데 그땐 이런 더블포인터 역참조가 너무 어려웠다. 포인터가 가리키는 곳의 값을 가져와야 하는 게 핵심. *(char *) 은 1바이트만 가져와져서 안된다. 대충 4바이트 자료형이면 * 하나만 붙여도 다 된다.

(char **) 가능
(long *) 가능
(unsigned int *) 가능 (그냥 int도 될것 같다)

realloc 개선

  size_t old_size = GET_SIZE(HDRP(bp)); // 기존 블록의 사이즈
  if (old_size-DSIZE >= size) {
    return bp;
  } 

  size_t need_size = size -(old_size - DSIZE); 
  if (!GET_ALLOC(HDRP(NEXT_BLKP(bp))) && GET_SIZE(HDRP(NEXT_BLKP(bp)))>=need_size)
  {
    delete_block(NEXT_BLKP(bp));
    size_t now_size = GET_SIZE(HDRP(bp)) + GET_SIZE(HDRP(NEXT_BLKP(bp)));
    PUT(HDRP(bp), PACK(now_size, 1));
    PUT(FTRP(bp), PACK(now_size, 1));
    return bp;
  }

기존의 mm_realloc() 함수는 무조건 새로운 공간을 할당받는 경우였는데 원래 realloc()은 뒷블록이 여유가 있으면 그 블록을 합쳐서 넘겨주는 방식이다. 그 부분을 앞에 추가했다. 뒤에는 else 붙여서 그대로 치면 된다. 이걸로 2점 올렸던 것 같다.

Segregated Fit

⌨️ 소스코드

firstfit, nextfit은 속도는 빠르지만 메모리 효율이 낮다. 그에 비해 bestfit은 속도는 느리지만 메모리 효율이 좋다. 적당히 속도도 빠르고 메모리 효율도 좋은 방식이다. Segregated Fit은 두개의 장점을 적절히 섞은 그런 방식이다! free-block-list를 크기에 맞춰서 여러개 만들어 놓는다. (리스트 배열) 보통은 log2(N)의 결과에 따라 어떤 배열 인덱스의 리스트에 들어갈지 정한다. 속도와 효율을 둘다 챙길 수 있어서 이 방식으로 했을 때 가장 최고점이 나왔다.

vs Simple Segregated storage

심플방식은 해당 블럭에 나를 할당하고 나서 남은 부분을 free-list로 되돌려놓지 않는 점이 fit과 다르다. 일단 segregated 방식 자체가 외부단편화는 필연적일 것 같다. 작은 크기들이 많이 있더라도 큰크기의 블럭이 없으면 힙 영역을 늘려주기 때문이다. 하지만 심플 방식은 할당하고 남은 부분을 돌려주지 않기 때문에 내부 단편화도 심하다.

매직 코드

  if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
    return -1;

init()할 때 할당이 불가능할 경우 바로 return 해주는 코드 추가해서 2점 올렸다.

번외

묵시적 할당 vs 명시적 할당

위에 적었던 명시적 리스트, 묵시적 리스트와는 다른 개념이다. 언어나 프로그램이 어떻게 메모리를 관리하는지에 따라 나뉘는데 묵시적은 프로그램이 알아서 하는 경우고 명시적은 프로그래머가 명시적으로 할당과 해제를 해주는 방식이다. C랑 C++이 대표적인 명시적 할당 언어이고, 자바와 파이썬이 묵시적 할당 언어이다. 묵시적할당을 도와주는게 가바지 컬렉터다. 가비지 컬렉터는 메모리가 저장되는 곳과 별개로 메모리에 메모리를 관리하기 위한 영역(가바지컬렉터)이 있는 것 같다.

가비지 컬렉션의 기본은 객체가 몇번 참조됐는지 일일이 세고 (참조계산) 0인 경우 메모리를 해제하는 방법인데 이는 순환참조 문제가 있어서 잘 안쓰고 Generational Garbage Collection와 같은 여러 다른 방법들이 있다.

과제의 의미

예쁜칼

정마담 예쁜 칼이야 조심해서 만지라

C언어는 피곤하다.
코치님이 항상 말씀하셨고 레드블랙트리부터 웹서버를 하는 지금까지 나도 쭉 느끼고 있다. 그 무엇보다 효율을 겁나 좋다. 하지만 거기까지 가기위해 너무나 많은 길을 걸어야 한다. 하나라도 실수하면 바로 터진다. 오타 아니면 컴파일 에러 거의 없다. 왜 C언어가 점점 입지를 잃어가는지 알 것 같다. 규모가 커질 수록 컴퓨터가 아닌 사람에게 정확성을 맡기는 게 좀 리스크가 있는 것 같다.
우리가 쓰는 코드들이 메모리에 어떻게 저장되는지 경험해봐라
흔한 예시지만 이차원배열 순회할때 행-열 순서로 할지 열-행 순서로 하는지에 따라 속도 차이가 현저하다. 꼭 C언어가 아니더라도 데이터를 다룰 때 메모리 구조를 생각해보자. 속도를 개선하고 싶을 때 도움이 될 수도 있을 것이다.