CS:APP Malloc Lab

이 글은 2024년 4월 15일 월요일 오전 1시 41분에 최종 수정되었습니다.

들어가며

CS:APP MALLOC LAB을 구현하기 위해 알아야 할 사전 지식을 정리한 포스팅 썸네일이다. DALL·E 3로 제작했다.

크래프톤 정글 4기에서 구현해야 했던 Malloc Lab을 이해하기 위해 알아야 했던 사전 지식을 정리해본다.

---

가상 메모리

• 컴퓨터에서 프로그램이 사용하는 메모리 공간을 실제 물리적 메모리보다 크게 만들어주는 기술이다. 이를 통해 컴퓨터는 실제 메모리보다 많은 데이터를 처리한다.
• 가상 메모리는 컴퓨터의 하드디스크 일부를 마치 메모리처럼 사용하게 해준다.
• 실제 메모리는 제한적인데, 이 기술을 사용하면 마법처럼 메모리가 더 커진 것처럼 사용할 수 있다.

페이징

• 가상 메모리를 작은 조각들로 나누는 방식으모 이 작은 조각들을 '페이지'라고 부른다.
• 컴퓨터는 이 페이지들을 필요할 때마다 실제 메모리로 가져오거나 실제 메모리에서 다시 하드디스크로 옮긴다.
• 이렇게 하면, 실제 사용 데이터만 메모리에 있기 때문에 효율적인 메모리 사용이 가능하다.

왜 필요한가?

메모리를 효율적으로 사용

모든 프로그램과 데이터를 메모리에 올려두지 않고, 필요한 부분만 불러서 사용하여 메모리를 절약한다.

프로그램 간의 독립성 보장

각 프로그램이 독립된 가상 주소 공간을 갖게 함으로써, 한 프로그램의 오류가 다른 프로그램에 영향을 주지 않도록 한다.

보안 강화

프로그램이 서로의 메모리 영역에 접근하는 것을 제한하여 보안을 강화한다.

추가적으로 알면 좋은 내용

교체 알고리즘

• 실제 메모리가 가득 찼을 때, 어떤 페이지를 하드디스크로 옮겨야 할지 결정하는 방법이다.
• 가장 오랫동안 사용되지 않은 페이지를 옮기는 LRU(Least Recently Used) 알고리즘이 자주 사용된다.

스레싱(Thrashing)

• 메모리와 하드디스크 사이에 데이터를 너무 자주 옮겨야 해서, 실제 작업보다 데이터를 옮기는 데 더 많은 시간을 소비하는 현상이다.
• 이를 방지하기 위해 적절한 크기의 메모리 관리가 중요하다.

---

동적 메모리 할당

• 컴퓨터 프로그램이 실행되는 동안 필요에 따라 메모리(저장 공간)를 할당하거나 해제하는 방법이다.
• 학교에서 필요할 때마다 도서관에서 책을 빌리고, 완독 후 반납하는 것과 비슷하다.

힙(Heap)

• 프로그램에서 동적으로 메모리를 할당 받는 공간이다.
• 상자에 비유하면, 필요할 때마다 상자를 가져다가 쓸 수 있고 더 이상 필요하지 않으면 돌려놓을 수 있는 공간이다.
• 힙을 사용해서, 프로그램이 실행되는 동안 필요한 만큼 메모리를 할당 받아 쓸 수 있다.

sbrk/mmap

sbrk

• 힙 영역을 늘리거나 줄이기 위해 사용되는 함수이다.
• 마치 상자를 보관하는 창고의 크기를 조절하는 것과 같다.
• 필요에 따라 창고를 더 크게 만들거나, 너무 크면 다시 줄일 수 있다.

mmap

• 파일이나 장치와 메모리를 연결하는 데 사용한다.
• 마치 지도에 특정 장소를 표시하는 것처럼, 프로그램이 특정 파일이나 메모리 영역을 쉽게 접근할 수 있게 해준다.

malloc/free

malloc

• 메모리 할당을 요청하는 함수이다.
• 새 상자를 필요로 할 때, 창고 관리자에게 상자 하나를 달라고 요청하는 것과 같다.

free

• 할당된 메모리를 해제하는 함수이다.
• 사용이 끝난 상자를 창고에 돌려놓는 것과 같다.
• 이렇게 해서 다른 사람이나 프로그램도 그 상자를 사용할 수 있게 된다.

추가적으로 알면 좋은 내용

메모리 누수

• 프로그램이 사용을 마친 메모리를 제대로 해제하지 않으면 그 메모리는 다시 사용할 수 없게 되어 결국 프로그램이 더 많은 메모리를 사용할 수 없게 되는 상황이다.
• 마치 상자를 빌려 사용하고 반납하지 않아서, 창고에 더 이상 상자를 놓을 공간이 없는 상태와 비슷하다.

프래그먼테이션 (파편화)

• 메모리가 작은 조각으로 나뉘어져 있어, 사용할 수 있는 충분한 메모리가 있음에도 불구하고 큰 메모리 할당 요청을 만족시키지 못하는 상황이다.
• 마치 창고에 큰 상자를 놓을 자리가 충분히 있음에도 불구하고, 작은 상자들로 인해 그 자리가 사용 불가인 것과 같다.

---

프래그먼테이션(파편화)

• 메모리 관리에서 자주 사용되는 용어로, 메모리가 작은 조각들로 나뉘어져서 연속적인 큰 메모리 영역을 확보하기 어려워지는 현상이다.
• 동적 메모리 할당과 밀접하게 연관되어 있는데, 이는 프로그램이 메모리를 할당하고 해제하는 과정에서 발생한다.

두 가지 형태의 프래그먼테이션

내부 파편화(Internal Fragmentation)

• 할당된 메모리 블록 내에 사용되지 않는 공간이 발생하는 현상이다.
• 예를 들어, 메모리를 할당할 때 요청된 크기보다 약간 더 큰 블록이 할당되어 남는 공간이 생길 때, 이 공간은 그 블록 내에서는 다른 용도로 사용할 수 없으므로 낭비되는 메모리가 된다.
• 프로그램이 100바이트를 요청했지만, 메모리 할당 시스템이 최소 단위가 128바이트인 블록을 할당한다면, 남은 28바이트는 내부 파편화로 인해 낭비된다.

외부 파편화(External Fragmentation)

• 할당되지 않은 메모리 공간이 작은 조각들로 나뉘어져 있어, 충분한 총량의 메모리가 있음에도 불구하고 큰 블록을 할당할 수 없는 상황이다.
• 이러한 파편화는 메모리 할당과 해제가 반복될수록 심화될 수 있으며, 결국에는 메모리의 효율적 사용을 방해한다.
• 예를 들어 1000바이트의 메모리가 필요한데, 500바이트짜리 두 개의 빈 공간이 서로 떨어져 있어서 하나의 1000바이트 공간을 할당할 수 없는 경우 이에 해당된다.

프래그먼테이션을 줄이기 위한 방법

메모리 합병(Coalescing)

• 인접한 가용 메모리 블록들을 하나의 큰 블록으로 합치는 과정이다.
• 외부 프래그먼테이션을 줄이는 데 도움이 된다.

무료 메모리 블록(Free Memory Blocks)

• 프로그램이 사용하고 난 후에 다시 시스템에 반환한, 현재 할당되지 않고 사용 가능한 메모리 영역이다.
• 메모리를 효율적으로 관리하기 위해서는 이러한 가용 메모리 블록들을 잘 관리해야 한다.
• 가용 블록 목록(Free List)이라는 구조를 사용해서, 사용 가능한 메모리 블록들을 추적하고 관리가 가능하다.

메모리 할당 알고리즘 개선

퍼스트 핏(First Fit), 베스트 핏(Best Fit), 워스트 핏(Worst Fit) 등 다양한 알고리즘이 메모리 할당 효율성과 프래그먼테이션 문제를 다루기 위해 사용될 수 있다.

1. 최초 합(First Fit) 알고리즘: 첫 번째로 충분히 큰 메모리 블록을 선택하여 할당한다.
2. 최적 합(Best Fit) 알고리즘: 가장 적게 남는 공간을 가지게 할 수 있는 가장 작은 메모리 블록을 선택하여 할당한다. 이는 외부 파편화를 줄이는 데 도움이 될 수 있지만, 검색 시간이 길어질 수 있다.
3. 최악 합(Worst Fit) 알고리즘: 가장 큰 메모리 블록을 선택하여 할당. 이는 내부 파편화를 증가 시킬 수 있다.

각 알고리즘은 특정 상황에서 유리할 수 있으나, 메모리 할당과 해제가 반복될 때 파편화 문제를 완전히 해결할 수는 없다. 따라서, 메모리 관리 전략을 효율적으로 설계하고, 필요에 따라 적절한 메모리 할당 알고리즘을 선택하는 것이 중요하다.

함께 알면 좋은 개념들

가비지 컬렉션(Garbage Collection)

• 사용되지 않는 메모리 자원을 자동으로 회수하는 기술이다.
• 메모리 누수를 방지하고 메모리 사용 효율을 높이는 데 유용하다.

메모리 풀(Memory Pooling)

• 비슷한 크기의 메모리 요청을 처리하기 위해 미리 할당된 메모리 블록의 풀을 사용하는 기법이다.
• 이는 내부 단편화를 줄이고 메모리 할당 및 해제의 성능을 향상시킬 수 있다.

컴팩션(Compaction)

• 메모리의 사용되지 않는 부분들을 조밀하게 만들어, 연속된 메모리 공간을 생성하는 과정이다.
• 이를 통해 외부 단편화를 줄일 수 있다.

---

메모리 할당 정책

• 프로그램에서 동적 메모리 할당을 요청할 때 사용할 수 있는 여러 가지 방법이다.
• 주로 사용되는 정책에는 first fit, next fit, best fit 등이 있다.
• 이 정책들은 메모리 블록을 할당할 때 선택할 수 있는 공간을 어떻게 찾아내고 결정 하는지에 대한 방법을 제시한다.

First Fit (첫 번째 맞춤)

• 설명: 메모리의 시작 부분부터 검사를 시작해, 요청 크기를 수용할 수 있는 첫 번째 가용 메모리 블록 할당 방식이다.
• 장점: 간단하고 구현하기 쉽다.
• 단점: 메모리의 앞 부분에 작은 가용 블록들이 많이 생겨 메모리 단편화를 야기할 수 있다.

Next Fit (다음 맞춤)

• 설명: first fit과 비슷하지만, 마지막으로 메모리를 할당한 위치부터 검색을 시작하는 방식이다.
• 장점: 메모리 전체에 할당 작업을 더 고르게 분포시킬 수 있어, first fit보다 메모리 단편화 문제를 다소 완화할 수 있다.
• 단점: 여전히 단편화 문제가 발생할 수 있으며, 할당된 메모리 블록 사이에 남는 공간을 효율적으로 사용 못할 수 있다.

Best Fit (최적 맞춤)

• 설명: 요청된 크기와 가장 잘 맞는(가장 작은 차이를 가진) 무료 메모리 블록을 찾아 할당하는 방식이다.
• 장점: 메모리를 아주 효율적으로 사용할 수 있으며, 필요한 크기에 가장 근접한 블록을 사용하기 때문에 낭비를 최소화할 수 있다.
• 단점: 모든 무료 블록을 검사해야 하므로 할당 작업 시간이 길어질 수 있으며, 매우 작은 무료 블록들이 많이 생겨 나중에 큰 메모리 요청을 처리하기 어려울 수 있다.

같이 알면 좋은 연관 개념들

메모리 단편화 (Fragmentation)

• 메모리가 작은 블록들로 나뉘어져, 큰 블록의 메모리 요청을 만족 시키기 어려운 상태를 말한다.
• 내부 단편화와 외부 단편화로 구분될 수 있다.

내부 단편화 (Internal Fragmentation)

• 할당된 메모리 블록 내부에 사용되지 않는 공간이 생기는 것을 말한다.
• 예를 들어, 10바이트가 필요하지만 16바이트 블록이 할당되면, 6바이트는 낭비된다.

외부 단편화 (External Fragmentation)

• 충분한 총 무료 공간이 있음에도 불구하고 큰 메모리 요청을 만족 시킬 수 없는 상태이다.
• 할당되지 않은 메모리 공간이 작은 조각으로 나뉘어져 있다.

메모리 병합 (Coalescing)

• 메모리 해제 시점에 인접한 무료 메모리 블록들을 하나의 큰 블록으로 병합하는 과정이다.
• 이는 외부 단편화를 줄이는 데 도움이 된다.

Garbage Collection (가비지 컬렉션)

• 프로그램이 더 이상 사용하지 않는 메모리를 자동으로 회수하는 기능이다.
• 이는 메모리 누수를 방지하고 메모리 사용 효율을 높이는 데 도움이 된다.

---

Implicit free list와 Explicit free list

• 동적 메모리 할당에 대한 개념으로 프로그램이 메모리를 효율적으로 관리하고 할당하기 위해 사용하는 방법이다.
• 메모리 관리 방식을 선택할 때, 메모리의 효율성과 할당 및 해제의 속도, 그리고 구현의 복잡성을 고려해야 한다.

Implicit Free List (묵시적 가용 리스트)

정의

• 암시적 가용 목록은 할당되지 않은 메모리 블록(즉, 가용 블록)을 추적하는 방법이다.
• 메모리는 여러 개의 블록으로 나뉘어 있으며, 각 블록은 할당된 블록과 가용 블록으로 구분된다.
• 암시적 목록에서는 모든 블록(할당된 블록과 가용 블록)이 연속적으로 메모리에 나열되며, 각 블록의 헤더에는 블록의 크기와 할당 여부가 표시된다.

작동 방식

• 메모리를 할당하거나 해제할 때, 프로그램은 이 목록을 순차적으로 탐색하여 적절한 크기의 가용 블록을 탐색한다.
• 이 방법은 구현이 간단하지만, 적절한 블록을 찾기 위해 메모리 전체를 탐색해야 해서 효율성이 떨어질 수 있다.

Explicit Free List (명시적 가용 리스트)

정의

• 명시적 가용 목록은 가용 메모리 블록들만을 연결 리스트로 관리하는 방식이다.
• 이 방식에서는 가용 블록들이 포인터를 사용하여 서로 연결되어 있으며, 할당된 블록은 이 리스트에 포함되지 않는다.

작동 방식

• 메모리 할당 요청이 있을 때, 프로그램은 명시적 가용 목록을 통해 빠르게 가용 블록을 검색할 수 있다.
• 블록이 할당되면, 해당 블록은 가용 목록에서 제거되고, 블록이 해제되면 목록에 다시 추가한다.
• 명시적 목록은 가용 블록을 더 빠르게 찾을 수 있게 하지만, 블록을 목록에 추가, 삭제하는 추가 작업이 필요하다.

같이 알면 좋은 개념

메모리 단편화

• 메모리 할당과 해제가 반복될 때, 메모리에 작은 크기의 사용되지 않는 공간(단편화)이 발생할 수 있다.
• 이는 메모리를 비효율적으로 사용하게 만들며, 큰 블록을 할당하려 할 때 문제가 될 수 있다.

메모리 할당 정책

• first fit, next fit, best fit 등의 메모리 할당 정책을 사용한다.
• 메모리 단편화를 최소화하고 메모리 사용 효율을 최대화할 수 있다.

---

마치며

여기까지 Malloc Lab 구현을 위해 알아야 하는 사전 지식들을 다뤄봤다. 사실 이것들만 가지고 Malloc Lab을 구현할 수 있다라고 말할 수는 없지만 그래도 이러한 개념들이 머릿 속에 있을 때 구현이 더 쉬워지는 건 자명한 사실이었다.

 

혹시라도 이 글을 보는 SW사관학교 카이스트 정글 또는 크래프톤 정글러는 화이팅하시길 바라며 이만 글을 마친다.