[Week7] WIL - 무한 코어타임 지옥

이전 주차와 비교했을때 가장 학습 내용이 어려웠던 Week7을 무사히 마치게 되었다. 학습 내용이 어렵다보니 자연스레 팀원들과 할 말이 많아졌고 코어타임 시간도 최소 2시간 이상 진행하게 되었다. 특히 첫째날 진행한 3시간 가량의 코어타임은 시간이 지나도 잊을 수 없을 것 같다... ㅋㅋ. 처음으로 동료학습에 중점을 두고 진행한 주차였던거 같은데 혼자 공부하는거에 비해 배울점이 정말 많았다. 과제 특성상 혼자 코드구현하는 시간에 투자하는 것이 도움이 될 것이라고 생각을 했었는데, 막상 다른 팀원들의 코드와 설계를 보니 나와 생각이 다른 부분들이 있어서 오히려 혼자하는 것 보다 도움이 되었던 것 같다.  

아무튼 이번주 WIL에서는 내가 Malloc_Lab을 진행하면서 도전해본 부분과, 수요코딩회에서 습득한 지식에 대해서 정리해보고자 한다.

 

핵심 역량 평가

역량	달성도	목표
문제해결 / 설계 / 구현 / 품질	80%	동적 메모리 할당에 대한 개념을 완벽히 이해하고, 성능 95점 이상의 코드를 완성한다. 속도/메모리 사용 두 개념의 트레이드오프를 고려하여 균형이 좋은 코드를 짜는것을 목표로한다.
segregated 가용 리스트 + first fit 탐색 방법과 CHUNKSIZE 조절을 통해 90점까지는 받을 수 있었다. 하지만 시간부족으로 인해 realloc 최적화나 명시적 가용 리스트에서의 최적화 방법 등 다양한 방법을 구현해보지는 못했다.
유지보수	80%	남들이 봐도 쉽게 이해할 수 있을 만큼 가독성 좋은 코드를 짜고, 주석을 달아놓는다.
함수형 매크로 이름을 기존 책에서 소개된 이름보다 더 직관적인 이름으로 수정하였다. 또 각 메서드에 대해서 주석을 달아놨다.
협업	100%	어려웠던 개념을 혼자 알고 넘어가는 것이 아니라, 팀원들과 공유한다.
학습할때마다 노션에 학습한 개념과 이슈들을 정리하고, 이를 코어타임때 팀원들과 같이 보며 공유하였다.
태도	75%	절대로 mm.c 파일 내용을 구현할 때 AI의 도움을 받지 않는다.
묵시적 가용리스트는 AI 없이 구현하게 가능했지만, 명시적 가용 리스트부터는 시간 부족으로 인해 AI의 도움을 받은 부분이 있었다.
비즈니스 이해	60%	수요코딩회에서 다른 사람이 봐도 이해가 명확히 될만한 구성으로 설계를 한다.
청중에게 실험 결과를 더 명확히 보여주기 위해서 시각자료가 있었으면 더 좋았을 것 같다.
AI 활용	80%	AI를 통해 꼬리 질문을 거듭하며 모호한 개념에 대한 이해와 응용력을 극대화한다.
수요코딩회 관련 지식을 확실하기 위해 AI의 도움을 적극적으로 받아 학습을 진행했다. 하지만 특정 개념을 오해하여 적절하지 않은 b+ 트리를 만들게 되었다.
학습 민첩성	0%	이번주는 빠르게 학습하는 것이 중요하지 않다고 생각하여 PASS. line by line으로 9.9장의 내용을 완벽하게 이해한다.
CSAPP 9.9의 내용을 이틀에 걸쳐서 깊게 공부하였다.

 

Malloc_Lab : Implicit 가용리스트에서 boundary tag의 단점을 줄이는 최적화 기법

💡 핵심 아이디어 : footer는 free block에만 있으면 충분하다!

boundary tag를 통해 이전 블록을 O(1)로 찾을 수 있지만, 모든 블록에 footer를 두면 작은 블록이 많을 때 오버헤드가 커진다. 

특히 작은 객체를 많이 malloc/free 하는 프로그램에서는 header + footer가 블록 절반을 먹을 수도 있다.

 

footer는 언제 필요할까❓

현재 블록을 free하려고 할 때 이전 블록이 free인지 확인하고, free라면 그 이전 블록의 크기를 알아내서 coalesce해야 한다. 

즉, 이전 블록을 뒤에서 찾기 위함이다. 

여기서 잘 생각해보면... 

 

이전 블록이 allocated라면❓

- 그 블록과 합칠 일이 없다.

- 그 블록 크기를 footer로 읽을 필요도 없다.

즉, 이전 블록이 free일 때만 footer가 필요하다.

➡️ footer는 free block에만 있으면 충분하다.

 

문제

이전 블록이 free라면 그냥 footer에서 정보를 읽으면 된다.

근데 그 전에 이전 블록이 free인지 allocated인지를 알아야하는데 어떻게 확인해야할까?

- allocated 블록에서 footer가 빠지는 것을 가정.

 

해결 방법

블록의 마지막 3개 비트는 사용하지 않고, 이 중 가장 마지막 비트는 현재 블록의 할당 여부를 나타내는 데 사용한다고 했었다.

이 다음 비트를 이전 블록의 정보를 담는데 사용하는 것이다.

        alloc = 1 (현재 블록 할당됨)
          |
          v
0x....0 0 1
        ^
        |
     prev_alloc = 0 (이전 블록 free)

 

prev_alloc bit를 get/set하기 위한 매크로

/* prev_alloc bit get */
#define GET_PREV_ALLOC(p) (GET(p) & 0x2)

/* prev_alloc bit set */
#define SET_PREV_ALLOC(p) (PUT(p, GET(p) | 0x2))

설명한 것처럼 0x2 주소(뒤에서 2번째 비트 주소) 값을 or 연산자를 통해 get/set 한다.

 

구현할 때 고려한 점

1️⃣ 어떤 블록을 malloc 해서 allocated로 만들 때

- 그 블록의 다음 블록 header의 prev_alloc을 1로 변경(할당됨 표시)

 

2️⃣ 어떤 블록을 free 할 때

- 그 블록의 다음 블록 header의 prev_alloc을 0으로 변경(free 표시)

 

3️⃣ coalesce 해서 블록들이 합쳐질 때

- 합쳐진 큰 free block의 footer를 새로 써야 한다.

- 그 다음 블록 header의 prev_alloc을 0으로 변경

 

📊 성능 확인

성능 확인을 하기 전에 나는 이번 최적화를 통해 메모리 효율 점수가 더 올라갈 것이라고 예상했다.

메모리 효율 점수는 [ 현재 할당된 payload / 총 heap 크기 ] 로 계산되는데, 4바이트 절약으로 인해 총 heap크기가 감소할 것이고, 이로인해 메모리 효율 점수가 높아질 것이라고 판단했기 때문이다.

size = 9
기존:        [header 4B][  9B 페이로드  ][footer 4B]  = 블록 24B 필요
footer 제거: [header 4B][  9B 페이로드  ]             = 블록 16B로 충분

 

1. 일반 Implicit 가용 리스트 - first fit 탐색

메모리 효율 51 + 처리량 13 = 64

2. footer 최적화 Implicit 가용 리스트 - first fit 탐색

메모리 효율 51 + 처리량 12 = 64

예상했던 것과 달리 점수차이가 거의 없었다.

처음에는 implicit + first-fit 방식의 한계 때문이라고 생각했다.

하지만 그렇더라도 처리량이 떨어져지는 것 외에 메모리 효율이 그대로인 것이 도저히 이해가 가지 않았다.

문제에 대한 정답은 trace(테스트 케이스)에 있었다.

 

Align과 block의 크기

요청한 size가 16이라고 가정해보자.

size = 16
기존:        [header 4B][  16 페이로드  ][footer 4B]  = 블록 24B 필요
footer 제거: [header 4B][  16 페이로드  ][padding 4B] = block align으로 인해 블록 24B 필요

위 예시를 보면 footer가 없지만, 블록 주소를 8의 배수로 고정하기 위해서 padding을 4B만큼 채워 넣는다.

즉, size가 8의 배수인 경우에는 align 조건으로 인해 기존 방식과 같은 크기의 블록을 할당받는다.

문제는 과제의 trace의 대부분은 전부 8의 배수 크기를 할당하고 있다는 것이다.

따라서 기존 방식과 메모리 효율은 그대로이면서, 처리율은 감소한 방식이 되어버렸다.

 

비록 결과가 좋지 못했던 방식이었지만, 설계한 내용을 구현하고 왜 문제를 해결하지 못했는지 분석하면서 많은 것을 배울 수 있었던 의미 있는 시간이었다.