[책리뷰] 컴퓨터 밑바닥의 비밀: ch3.4 메모리 힙 영역

이 글은 책 컴퓨터 밑바닥의 비밀 chapter 3.4의 내용을 읽고 요약한 글입니다. 

 

3.4.1 힙 영역이 필요한 이유

• 프로그래머가 수명 주기를 포함하여 완전히 직접 제어할 수 있는 매우 큰 메모리 영역
• 어떻게 힙 영역에 메모리를 할당하고 해제하는지 구현

3.4.2 malloc 메모리 할당자 직접 구현하기

• 메모리 할당자는 적절한 크기의 메모리 영역을 제공하기만 하고 무엇을 저장할지 신경쓰지 않음
  • integer, floating number 등 신경쓰지 않고 단순한 바이트의 연속에 지나지 않음
  • 커다란 배열 형태

힙 영역 위에서 두가지 문제 해결

1. malloc 함수 구현
   1. 메모리 영역을 요쳥하면 힙 영역에 가능한 메모리 영역 찾아 요청자에게 반환
2. free 함수 구현
   1. 메모리 영역의 사용이 완료되었을 때 메모리 영역을 반환하는 방법 구현

 

3.4.3 주차장에서 메모리 관리까지

주차장에 비유하여 표현하면 2가지 목표를 만족시켜야 함

1. 주차할 위치를 빠르게 찾음. 요청된 크기를 만족하는 여유메모리를 빨리 찾음
2. 주차장 사용률 극대화. 메모리를 요청할 때 가능한 많은 메모리 할당 요청을 만족시켜야 함

4가지 문제점

1. 메모리 조각의 할당 상태 추적
2. 단일 메모리 할당 요청의 요구사항을 만족하는 사용 가능한 메모리 조작이 매우 많을 때 할당 기준
   1. 6바이트 요청했는데 여유 메모리 공간이 16, 32, 8 바이트 일때
3. 16바이트 메모리를 요청해야 하는데 여유 메모리 조각의 크기가 32바이트라서 16바이트가 남는 경우
4. 사용 반환된 메모리를 어떻게 처리해야 하나?

3.4.4 여유 메모리 조각 관리하기

• 위의 4가지 문제점들 중 1번 해결을 위한 방법으로 linked list로 메모리 사용정보를 기록하는 방식

2가지 정보를 기록

• 메모리 조각의 크기를 기록한 숫자 - header라고 하며 32비트
  • 메모리 조각이 비어있는지 알려주는 설정값(flag) - 1비트
• 할당 가능한 메모리 조각을 payload라고 함 (메모리 주소)

3.4.5 메모리 할당 상태 추적하기

한조각은 4바이트

• 16/1: 할당된 메모리 조각 크기가 16바이트를 의미
• 32/0 : 여유 메모리 조각이 32 바이트
• 0/1: 끝을 표시하는 특수한 표시로 4바이트

이 방식으로 메모리 조각의 여유/할당 상태 파악 및 추적할 수 있음

3.4.6 어떻게 여유 메모리 조각을 선택할 것인가: 할당 전략

• 4바이트 메모리를 요청받을 때 요구사항을 충족하는 여유 메모리가 두조각이 있음
  • 8/0, 32/0 중 어떤것을 반환할 것인가? 다양한 할당 전략 방식이 있음

메모리 할당 전략 방식

1. 최초 적합 방식

• 제일 앞부터 탐색하다가 가장 먼저 발견된 요구사항을 만족하는 항목을 반환
• 단순하지만, 처음부터 사용가능한 메모리 조각을 찾으므로 앞부분에 작은 메모리 조각이 많이 남을 가능성이 높음

2. 다음 적합 방식

• 최초 적합 방식과 유사하지만 메모리를 요청할 때 처음부터 검색하는 대신 적합한 여유 메모리 조각이 마지막으로 발견된 위치에서 시작한다는 점이 다름
• 탐색 시작 위치가 달라져, 더 빠르게 여유 메모리 조각을 탐색할 수 있음
• 단점: 메모리 사용률은 최초 적합 방식에 미치지 못한다는 것이 연구로 밝혀짐

3. 최적 적합 방식

• 사용 가능한 메모리 조각을 모두 찾은 후 요구 사항을 모두 만족하면서 크기가 가장 작은 조각 반환
• 메모리를 더 잘 활용한다는 장점이 있음
• 사용가능한 모든 메모리 조각을 탐색하기 때문에 빠르지 않음

실제로는 더 복잡한 원리로 적합한 방식을 찾아 할당

3.4.7 메모리 할당하기

• 12바이트 메모리를 요청했을 때 적절한 여유 메모리 조각이 12 바이트라고 가정
  • 헤더인 4바이트를 제외한 나머지 크기

• 할당된 것으로 표시하고 머리 정보 뒤에 따라오는 메모리 조각의 주소를 요청자에게 반환하면 됨

• 위는 이상적인 경우로 12바이트 메모리를 요청했을 때 찾아낸 여유 메모리 조각의 크기가 더 큰 경우가 대부분
• 아래와 같이 찾아낸 메모리 조각이 32바이트라면? 메모리가 낭비되고 내부 단편화(fragmentation) 발생함

내부 단편화의 예

• 이 문제를 해결하기 위해 여유 메모리 조각을 두개로 분할하여 앞부분은 할당한 후 반환하고 뒷부분은 좀 더 작은 크기의 새로운 여유 메모리 조각으로 만듦

3.4.8 메모리 해제하기

• 사용자가 메모리를 요청할 때 얻은 주소를 ADDR이라고 가정
• free(ADDR)을 호출하면 매개변수인 ADDR에서 머리 정보 크기인 4바이트를 빼는 것으로 메모리 조각의 머리 정보 얻을 수 있음
• 머리 정보에서 얻은 할당 설정값을 여유 메모리로 바꾸면 해제가 완료됨

메모리 해제 시 중요한 점 하나

• 해제되는 메모리 조각과 인접한 메모리 조각이 여유 메모리 조각일 때 단순히 해제 여부만 기록하면 아래 상황 발생

• 해제된 메모리 조각에 인접한 아래쪽 메모리 조각도 비어있음
• 메모리를 해제 할 때 둘을 합치는게 나을까? 그대로 두는게 나을까?

그대로 두는 경우

• 20 바이트 요청이 오는 경우 두 조각 중 어느 것도 요구사항을 만족시키지 못함

메모리를 해제 할 때 메모리 조각을 병합할 때

1. 즉시: 비교적 간단하지만 부담이 발생. 하지만 간단해서 여전히 이 전략을 많이 선택
2. 요구사항을 충족하는 여유 블록을 찾을 수 없을 때: 실제 메모리 할당자가 선택하는 전략

3.4.9 여유 메모리 조각을 효율적으로 병합하기

• 해제하는 메모리 조각의 위 아래가 모두 비어있다면? 아래는 헤더 정보로 알 수 있지만 위의 정보는 어떻게 알 수 있나?

• 메모리 조각 끝에 footer 정보를 추가

• 조각의 꼬리 정보는 그 다음에 위치한 조각의 머리 정보와 인접해 있어 현재 조각의 머리 정보에서 4바이트를 빼면 이전 조각의 꼬리 정보를 획득할 수 있음

• header와 footer 정보는 메모리 조각을 doubly linked list로 만듦