[WIL] 크래프톤 정글 6주차 - Malloc Lab

이번 주차는 CMU(Carnegie Mellon University)의 Malloc lab을 진행하는 주간이었다.

 

이 과제를 통해 malloc의 실제 동작 방식을 이해하고 free한 block을 어떤 방식으로 관리하고 할당해주는 지 배워보는 시간을 가졌다.

Malloc 동작 방식의 종류

출처 : https://dean30.tistory.com/44

1. implicit free list(묵시적 가용 리스트)

- 묵시적 가용 리스트는 모든 블록을 헤더와 풋터를 통해 간접적으로 연결된 것처럼 보이도록 하는 방식으로 블록들을 관리한다.

 

- 헤더와 풋터에는 같은 정보가 들어가는데, 그 안에는 해당 블록의 크기, 블록의 할당 여부 등이 들어있다.

 

- 블록의 크기를 통해 다음 블록의 주소를 얻어낼 수 있으므로 묵시적으로 연결되었다고 보는 것이다.

2. explicit free list(명시적 가용 리스트)

- 명시적 가용 리스트는 모든 블록을 관리하는 것이 아닌, 가용(free) 블록만을 관리하는 리스트이다.

 

- 블록 안의 payload가 담겨야하는 부분을 가용 블록을 사용하고 있지 않으므로 이 부분에 다음 가용 블록을 가리키는 포인터와 이전 가용 블록을 가리키는 포인터를 넣어서 double linked list를 통해 가용 블록들을 관리하는 기법이다.

가용 블록 할당 방식

- 가용 블록을 할당하는 데에는 기본적으로 3가지 알고리즘이 존재한다.

 

1. first fit : (명시적이면 linked list의 맨 앞에서, 묵시적이면 heap의 맨 앞에서) 앞에서부터  순서대로 탐색하며 요청한 데이터가 들어갈 수 있는 크기의 가용 블록을 찾으면 해당 블록에 바로 할당시켜주는 방식

 

2. next fit : 이전에 탐색을 완료한 지점부터 탐색을 시작하여 요청한 데이터가 들어갈 수 있는 크기의 가용 블록을 찾으면 해당 블록에 바로 할당시켜주는 방식(first fit보다 빠르지만 memory 이용량은 적을 수 있음)

 

3. best fit : heap의 처음부터 끝까지 탐색하여 가장 크기가 잘맞는 가용 블록에 할당시켜주는 방식(속도가 가장 느리지만, 메모리 이용량은 최상)

 

- 추가적으로 worst fit이라는 알고리즘도 존재한다.

 

이 방식은 가장 큰 가용 블록에 할당을 해줌으로써 할당 뒤, 분리하는 작업을 통해 외부 단편화를 최소화시킬 수 있는 방식이다.

실제 구현

implicit free list 구현

first fit 방식의 점수

 

- 처음 점수를 측정했을 때, 나보다 점수가 낮은 사람이 없었다. 그래서 하드웨어 차이라고 생각하여 코치님께 문의한 결과, chat gpt4는 하드웨어의 성능에 따라 점수가 달라질 수 있다고 하였고, 다른 코치님께서는 이 과제가 시행된게 2003년이기 때문에 하드웨어가 코드에 영향을 미칠 정도는 아닐 것이라고 답변해주셨다.(2003년이 지금보다 하드웨어가 훨씬 안좋았음)

 

- 하지만, 같은 코드를 다른 동료의 노트북에서 돌렸을 때에는 점수가 더 높게 나온 것을 확인했었다.

 

심지어 점수가 더 낮게 나온다고 하는 (M1, M2 칩을 탑재한)맥북에서도 나보다 점수가 높게 나왔었다.

 

하드웨어 좋은 사람들은 first fit으로만 구현해도 70점대를 찍은 경우도 있었다.

 

- 따라서 CPU나 램의 용량에 따라 점수가 낮게 나오는 것이라고 결론을 내렸다.

next fit 방식의 점수

- next fit을 처음 구현했을 때, 단순히 이전에 할당한 주소를 저장시켜줘서 그 부분부터 탐색을 시작했더니 다음과 같은 에러들이 무수히 떨어졌다.

 

- 검색을 통해 오류가 발생하는 이유를 찾아냈다.

 

startP를 통해 이전에 할당받았던 위치를 가리켰는데, 만약 해당 블록이 free되어서 이전 블록과 coalescing(블록이 합쳐지는 과정)이 된다면 startP는 가용 블록의 한가운데를 가리키게 되므로 오류가 발생하는 것이었다.

 

- 따라서 coalesce 함수 내에서 coalescing이 완료되면 해당 블록의 시작 주소를 startP로 바꿈(완벽한 next fit은 아니지만 그럴듯 하게 만들어지긴 함)

 

- 최종적으로 나온 next fit 방식의 점수는 다음과 같다.

explicit free list

- 명시적 가용 리스트에서는 할당해주는 알고리즘을 first-fit과 LIFO 방식을 결합하여 사용했다.

 

first fit은 묵시적 가용 리스트와 똑같은 방식이고, LIFO 방식은 가장 최근에 반환된 가용 블록이 linked list의 맨 앞에 오도록 하는 방식이다.

 

이 방식을 사용하면 best fit과 비슷한 효율이 나오면서, first-fit의 속도를 가질 수 있다고 한다.

 

- 하지만 이렇게 해도 점수가 높게 나오지 않아 컴퓨터의 사양을 확인해보니 알고 있던 사양과 다른 것을 확인했고, 이 때문에 점수가 낮게 나온 것을 알게 되었다.(램이 8기가 인줄 알았지만 4기가 + CPU : 인텔 i5 7세대)

누가 내 램을 옮겼을까?

(바로 노트북 주문을..)

 

- 최종적으로 같은 윈도우 환경인 동료의 컴퓨터에서의 점수는 다음과 같이 나왔다. 

 

 

합격선인 80점을 넘은 것을 확인했고, 다사다난한 한 주를 보냈다...

 

코드와 주석이 있는 깃허브 : https://github.com/Yeon-junLee/malloc-lab/blob/main/mm.c