크래프톤 정글 TIL : 0814

lazyArtisan·2024년 8월 14일
TIL
0

정글 TIL

목록 보기
45/147

🎯 To-do List

⌚ Today

  1. 묵시적+next fit 구현 ✅
  2. realloc 개선 ✅
  3. 13334 철로 풀기 | 이 날 못품
  4. malloc 정리글쓰기 ❌

⏳ Routine

  • 알고리즘 스터디

🍪 Someday

  • c++ 공부하기
  • 기술 면접 준비 | 경쟁 조건, 데드락 | 뮤텍스, 세마포어, 조건 변수 | 멀티프로세스와 멀티쓰레드의 차이
  • CS:APP 읽기 | 6장


📚 Journal

기록 피드백

  • 하는 과정을 일일이 적다보니까 코드 쓰다 기록 쓰다 정신이 없다. 두서없이 있는거 일일이 다 쓰면 효율도 안 좋고 기록에 아무 의미도 안 남는 것 같음. 문제도 해결과정도 최대한 일목요연하게 정리하자. (물론 까먹을 수 있으니까 가벼운 메모는 적어놓기)

내 기록의 문제점

  • 나중에 누가 봤을 때 별로 읽고 싶지 않을 정도로 불친절한 설명
  • 하나 하고 하나 쓰다보니 기록에 비효율적일 정도로 과도하게 시간 투자가 됨
  • 주간 회고의 부재로 인해 내가 무엇을 배웠고 느꼈는지 정리도 안돼있고 스스로도 와닿지 않음

이번 주차에 한 것들 정리

  • implicit
  • explicit
  • next fit
  • realloc

기타 메모

  • 기술 면접 매일 주제 하나씩 정해서 정리하는 건 좋은 것 같음. 하루 시간 배분에 꼭 집어넣자. (말하는 연습도 꼭 하자)
  • 이제까지 봤던 퀴즈 내용 정리하면 좋을 것 같음.
  • 시간 복잡도 구하는 방법 알아야 함


📦 Malloc

명시적 코드 참고했던 블로그 글 하단에 이런 내용이 적혀있길래
어? 내 묵시적 코드는 51점이었는데? 하고 해당 블로그의 묵시적 코드를 복붙해서 돌려봤더니
똑같이 51점이 나왔다.

묵시적 가용 리스트는 컴퓨터 성능에 따라 점수에 차이를 보이고
명시적은 차이를 보이지 않는다.

이유는 채점 코드를 뜯어보지 않는 이상 모를듯.

📌 묵시적+next fit 구현

1 : 개념 정리

next fit이란?

  • 마지막으로 할당됐던 블록 다음부터 가용 블록 탐색을 시작함.
  • 힙 영역 끝까지 탐색했다면 시작으로 안 돌아가고 힙 영역 늘린 다음 거기에 할당

-> 구현 방식에 따라 다름.

근데 이거 맨 처음에 적혀있던 원시적 할당기랑 성능 똑같은 거 아닌가?
생각하고 원본 repo 복붙해서 돌려봤는데 오류 뜨면서 terminated됨.
이거 원래 완성본 아니었구나..

아무튼 논리 자체는 원본 repo에 있던

void *mm_malloc(size_t size)
{
    int newsize = ALIGN(size + SIZE_T_SIZE);
    void *p = mem_sbrk(newsize);
    if (p == (void *)-1)
        return NULL;
    else
    {
        *(size_t *)p = size;
        return (void *)((char *)p + SIZE_T_SIZE);
    }
}

이거랑 똑같을듯.
메모리 효율은 쓰레기, 연산 속도는 최고.

-> 헛소리였다. 구현 방식에 따라 다르다. last_bp를 가장 최근에 alloc 혹은 free된 블록을 가리키는 것으로 생각하면 병합할 때 last_bp를 바꿔줘야 함.

2 : 구현 과정

mm_init에 last_allocp 추가해주고
fint_fit 변수만 바꿔줬더니 안됨.

extend_heap도 바꿔줘야 했음.
extend_heap에서 주소를 반환해주는 이유가
이전 영역에서 못 찾았으니까 늘려줌 +
mm_malloc한테 늘려준 영역의 첫 번째 주소에 넣으라고 보내줌
이건데
이때 last_allocp를 새로 만들어지는 (그리고 할당되는) 영역의 시작 주소로 바꿔줘야 함

이 아님. 헛소리였음.

모르겠어서 블로그를 봄. 뭔가 이상하긴 했음.
그냥 마지막 할당 블록의 다음 블록만 확인하는거면 이거 짜보는 의미가 뭐가 있음?
이라는 생각이 들었는데, 그게 아니었다.

근데 그러면 명시적으로 해줘야 하는거 아닌가?

이렇게 하면 next-fit 아닌거 아님?

이렇게 하면 더 next-fit 아닌거 아님?

-> CSAPP를 다시 들춰보니 next fit은 first fit과 비슷하지만 검색을 리스트의 처음에서 시작하는 대신, 이전 검색이 종료된 지점에서 검색을 시작한다 라고 되어 있었음.

애초에 개념이 이게 이거다! 라고 딱 정해져 있는게 아니다보니까 어떻게 구현해도 '이전 ~이 종료된 지점'만 들어가면 대충 되는듯.

참고 블로그를 바꿔봤다.

아니 last_bp 왜 이렇게 많음;
답지 베껴야 되나? 생각이 들었는데
함수들의 실행 과정을 전부 정리해보면 도움도 되고
직접 구현하는데 도움도 될 것 같아서 그거 먼저...
아니다 너무 돌아가는 길인가?

(일단 while 두 번 도는 건 last_bp에서 힙 영역 끝까지 탐색했다가 가용 블록 못 찾으면 힙 영역 처음부터에서도 탐색해준다는 거라는 사실은 알았음.)

3 : 새 마음 새 출발

묵시적만 구현되어 있는 버전으로 되돌리고 다시 시작

원래 함수들까지 어떻게 돌아가는지 정리하면서 명확하게 뭐 할지 정리하려다가 과투자같아서 안 함.
그냥 읽으면서 뭐 필요하겠다~ 생각하자.

할당만 추적하면 앞쪽에 free가 되던 말던 신경 안쓰고 뒤로 전진하기만 하긴 함.
그래도 그냥 하자.

아 이게 그 말이었구나. 그럼 병합했을 때도 추적해야할듯?

병합 추적했더니 바로 성공했다 ㅋㅋ 나이스

4 : next fit 변경 사항 정리

mm_init()

힙 영역 처음을 가리키도록 last_allocp 초기화.
if 문 앞으로 가도 정상 작동한다.

mm_malloc

할당해준 후에 last_allocp로 할당 추적

find_fit

last_allocp부터 탐색 시작

병합해준 후에 추적 바꿔주기 (이러면 결국 가장 최근에 free된 블럭도 추적하게 됨)

📌 realloc 개선하기

아예 어떻게 해야할지 감조차 안 잡힌다.
우선 기존 realloc을 분석해보자.

free하고 malloc하면 된다고 생각함

void *mm_realloc(void *ptr, size_t size)
{
    void *oldptr = ptr;
    void *newptr;
    size_t copySize = GET_SIZE(HDRP(oldptr));

    // free하기
    mm_free(ptr);

    if (newptr == NULL)
        return NULL;

    // 새로 할당할 size에 맞는 가용 블록 찾아서 할당
    newptr = mm_malloc(size);
    // size가 0이거나 음수이면 NULL 반환
    if (newptr == NULL)
        return NULL;
    mm_malloc(size);

    // 재할당하려는 블록의 크기가 기존 블록의 크기보다 작을 경우,
    // 실제로 복사할 크기를 size로 제한
    if (size < copySize)
        copySize = size;
    memcpy(newptr, oldptr, copySize);
    return newptr;
}

실패함.

코드를 잘 짰는지는 모르겠지만, 애초에 로직 자체가 틀린듯.
옮기려는 범위가 원래 범위와 겹치면 (조금밖에 안 움직이면) 원본 데이터가 오염되어서 복사가 원하는대로 이루어지지 않을 수 있을듯.

다른 방법을 생각해야 한다.

원래 이런건

int temp, a, b;
temp = a;
a = b;
b = temp;

이런게 정석인데,
메모리 단계에서 이루어지는 작업이다보니 어떻게 할 수도 없고 참...

결국 다른 사람 코드를 봤는데, 로직은 마음에 안 들지만 (케이스 하나만 커버하는게 너무 지엽적인 것 같음)
memmove를 쓰면 오류가 해결된다는 정보가 있어서 시도해봤는데 역시 안됨.

void *mm_realloc(void *ptr, size_t size)
{
    void *oldptr = ptr;
    void *newptr;
    size_t copySize = GET_SIZE(HDRP(oldptr));

    if (newptr == NULL)
        return NULL;

    // free하고 병합시킨 가용 블록부터 탐색하고 할당
    mm_free(ptr);
    oldptr = last_allocp;
    newptr = mm_malloc(size);

    // 재할당하려는 블록의 크기가 기존 블록의 크기보다 작을 경우,
    // 실제로 복사할 크기를 size로 제한
    if (size < copySize)
        copySize = size;
    memmove(newptr, oldptr, copySize);
    return newptr;
}

코드 계속 꼬라보고 다듬다가 이쯤에서 포기하고 gpt한테 한 번 맡겨봤는데
이전 로직으로 되돌려놔버림.

쓸모없는 기계 버리고 블로그 봤는데

	void *realloc(void *oldptr, size_t size) {
 
    size_t asize = MAX(ALIGN(size) + DSIZE, MINSPACE);
    
    if(size <= 0) { // edge case 1
        free(oldptr);
        return 0;
    }    
 
    if(oldptr == NULL) return malloc(size); // edge case 2
 
    size_t oldsize = GET_SIZE(HDRP(oldptr)); 
    if(asize == oldsize) return oldptr; // edge case 3
 
    if(asize <= oldsize) { // have to shorten
        size = asize;
 
        if(oldsize - size <= MINSPACE) return oldptr; // set min val (24)
 
        PUT(HDRP(oldptr), PACK(size, 1)); // new block with new size
        PUT(FTRP(oldptr), PACK(size, 1)); 
        PUT(HDRP(NEXT_BLKP(oldptr)), PACK(oldsize - size, 1));
        free(NEXT_BLKP(oldptr)); // free old block
 
        return oldptr;
    }
 
    void *newp = malloc(size); // re malloc
    if(newp == NULL) return 0;
 
    if(size < oldsize) oldsize = size;
    
    memcpy(newp, oldptr, oldsize); // copy memory
    free(oldptr);
 
    return newp;
}

https://13months.tistory.com/547
이 사람 코드 좀 잘 짠듯
realloc할 사이즈에 따라서 경우의 수를 나눴다.

  1. 0보다 작으면 기존 블록 free하고 끝
  2. oldptr이 NULL이었으면 malloc(size) 해주고 거기에 넣는듯 (그냥 return NULL 해도 될듯?)
  3. 복사해야할 길이가 원래 길이보다 DSIZE(묵시적일 때. 헤더+푸터 사이즈)만큼 보다도 더 작으면 사이즈 줄이고 뒤쪽 블록은 free시키기 (푸터 생략시킨거 좋은듯)
  4. 3가지 경우가 아니면 평범하게 realloc
size_t asize = MAX(ALIGN(size) + DSIZE, MINSPACE);

이것도 코드 덜 써도 되고 직관적이고 좋은듯 (나는 MINSPACE 선언을 안 해놔서 DSIZE로 바꿈)

여기에 위에 지엽적이라고 했던 사람 코드까지 합치면 더 좋을듯? 합쳐보자.

if(newp == NULL)
        return 0;

이 부분은 필요 없음. (최소한 내 코드에선) 위에서 if (size <= 0) 를 이미 걸렀으면 mm_malloc이 NULL을 반환하는 경우 없음.

void *mm_realloc(void *ptr, size_t size)
{
    size_t asize = MAX(ALIGN(size) + DSIZE, DSIZE);

    if (size <= 0) // 사이즈가 0보다 작으면 free하고 끝
    {
        mm_free(ptr);
        return 0;
    }

    if (ptr == NULL) // 굳이 안해줘도 되긴 할듯?
        return mm_malloc(size);

    size_t oldsize = GET_SIZE(HDRP(ptr));
    if (asize == oldsize) // 사이즈가 같다면 아무 일도 x
        return ptr;

    if (asize <= oldsize) // 기존보다 줄어드는데
    {
        size = asize;
        // 여유 크기가 최소 블록 사이즈보다 작다면
        if (oldsize - size <= DSIZE)
            return ptr;
        // 여유 크기가 최소 블록 사이즈보다 크다면
        // 헤더, 푸터 바꿔주고 여유 공간을 가용 블록으로 바꾸기
        PUT(HDRP(ptr), PACK(size, 1));
        PUT(FTRP(ptr), PACK(size, 1));
        PUT(HDRP(NEXT_BLKP(ptr)), PACK(oldsize - size, 1));
        mm_free(NEXT_BLKP(ptr));

        return ptr;
    }

    void *newp = mm_malloc(size);
    if (size < oldsize)
        oldsize = size;
    memcpy(newp, ptr, oldsize);
    mm_free(ptr);

    return newp;
}

이상하게 내장 함수 이름(malloc, free)을 그대로 가져다 써놓은 부분이 있어서 고치느라 귀찮았다.

돌아가긴 하는데 점수가 그대로임...

합쳐보려고 했는데 합쳐도 바뀔 거 없을 것 같아서 여기서 그만.

⚔️ 백준

📌 13334 철로

이 날 저녁부터 다음 날 오전까지
수많은 시간 초과를 내고
열심히 헛소리를 늘어놓으며 풀어보려고 노력했지만... (다음 TIL에 계속)

profile
lazyArtisan
이전 포스트

크래프톤 정글 TIL : 0813

다음 포스트

크래프톤 정글 TIL : 0815

0개의 댓글