CSAPP 책은 쌩으로 읽는다면 이해하기 매우 어렵습니다.
따라서 소단원만 그대로 따라가되, 내용을 이해하기 쉽게 재구성했습니다.
9.9.5 구현 이슈
할당기의 구현에서 발생할 수 있는 이슈들에 대해서 설명한다.
설명을 위해 생각할 수 있는 가장 단순한 할당기를 만들어보자.
1. 가장 단순한 할당기 만들기
힙은 하나의 커다란 바이트의 배열이라 생각하면 된다.
이 배열의 맨 앞을 가리키는 포인터를 p라고 가정한다.
size 바이트를 요청하면, 동작은 아래 방식으로 진행된다.
malloc은 현재 포인터 p를 스택에 저장한다.- p를 size 크기만큼 증가시킨다.
- 저장해두었던 원래 p의 값을 반환한다.
즉, 그 위치에 메모리를 할당한 것처럼 사용한다.
이렇게 하면 메모리를 쉽게 할당할 수 있다.
free는 아예 고려하지 않고, 무조건 메모리에 할당하기만 한다.
2. 가장 단순한 할당기의 문제점
이 할당기의 처리량은 매우 빠르다.
각 malloc이나 free가 적은 수의 명령어들만을 실행하기 때문이다.
그러나 메모리 이용도 측면에서는 최악이다.
이미 할당했던 메모리는 다시 사용할 수 없고, 남은 공간이 아무리 많아도 쓸 수 없는 경우가 생기기 때문이다.
결국, 프로그램이 금방 메모리를 다 써버리게 된다.
3. 실용적인 할당기를 만들기 위해 고려해야 하는 것들
따라서 처리량과 이용도 사이에서 좋은 균형을 갖는 실용적인 할당기를 만들기 위해서는 다음과 같은 것들은 고려해야 한다.
1) 가용 블록 구성
사용하고 있지 않은 블록들(가용 블록)을 지속적으로 확인해야 한다.
그래야 새로운 메모리 요청이 들어왔을 때, 기존 블록을 재사용할 수 있다.
2) 배치
메모리를 할당할 때, 어떤 가용 블록에 할당할지 잘 선택해야 한다.
예로, 첫 번째로 맞는 블록을 고를 수도 있고, 가장 작은 블록을 고를 수도 있다.
3) 분할
만약 요청한 크기보다 가용 블록이 훨씬 클 수 있다.
이 경우 요청한 크기만큼 잘라서 주고, 남은 공간은 따로 가용 블록으로 남겨야 한다.
4) 연결
메모리를 반환할 때, 주변에 가용 블록이 있다면 합쳐서 더 큰 블록을 만든다.
이를 통해 메모리 단편화를 줄일 수 있다.
4. 묵시적 가용 리스트 (Implicit Free List)
위 고려점들은 묵시적 가용 리스트라고 불리는 간단한 구조에서 많이 사용된다.
묵시적 가용 리스트는 블록들 사이를 별도의 포인터 없이 연결하는 방식이다.
앞으로 소개할 기법들은 이 묵시적 가용 리스트를 기반으로 설명된다.
