컴퓨터 시스템 : CSAPP 9장 정리 - 9.9 동적 메모리 할당 9.9.6~9.9.11

9.9.6 묵시적 가용 리스트

블록 구조

그림 9.35 간단한 힙 블록의 포맷

힙에 저장되는 각 블록은 헤더(header), 페이로드(payload), 그리고 필요에 따라 패딩(padding)으로 구성된다.

• 헤더에는 블록 전체 크기와 할당 여부 비트를 함께 저장한다.
• 블록 크기는 항상 8의 배수이므로, 하위 3비트 중 하나를 할당 여부 표시용으로 사용한다.
  • 예를 들어, 크기가 0x18인 블록이 할당되어 있다면, 헤더 값은 0x19가 된다.

묵시적 자유 리스트 개념

묵시적 가용 리스트 방식은 명시적인 포인터 없이 블록들을 순차적으로 탐색하면서 가용 블록을 찾는 구조다.

• 블록의 크기 정보를 이용해 다음 블록의 위치를 계산한다.
• 힙 전체를 한 블록씩 순회하면서 가용 블록을 찾는다.
• 가용 블록은 헤더에 기록된 할당 여부를 통해 판별한다.

장점과 단점

장점:

• 구조가 간단하다.
• 포인터를 따로 저장하지 않으므로 공간을 절약할 수 있다.

단점:

• 검색 성능이 떨어진다. 전체 힙을 선형 탐색해야 하므로 가용 블록을 찾는 데 시간이 많이 걸릴 수 있다.
• 큰 힙에서는 할당 시간이 매우 느려질 수 있다.

예시

• 책의 그림 9.36은 힙에 블록들이 어떻게 배치되어 있는지 보여준다.
• 할당된 블록은 음영 처리되어 있고, 헤더에는 (크기/할당여부) 형식으로 정보가 기록된다.

묵시적 자유 리스트는 구현이 단순하지만 성능 문제 때문에 실제 시스템에서는 잘 쓰이지 않고, 주로 학습용이나 간단한 할당기 구현에 사용된다.

---

9.9.7절 "할당된 블록 배치 (Placing Allocated Blocks)"

애플리케이션이 동적 메모리를 요청했을 때, 할당기가 가용 블록 중 어느 것을 선택해 해당 요청을 만족시킬지를 결정하는 배치 정책(placement policy)에 대해 설명한다.

동작 방식

• 애플리케이션이 k 바이트를 요청하면, 할당기는 가용 리스트에서 이 요청을 수용할 수 있는 충분히 큰 가용 블록을 찾는다.
• 이 탐색 방식은 선택한 배치 정책에 따라 달라진다.

---

대표적인 배치 정책

1. First Fit (최초 적합)
   • 가용 리스트의 앞에서부터 탐색하여 처음으로 맞는 블록을 선택한다.
   • 장점: 큰 블록은 리스트 끝에 남겨둘 가능성이 높다.
   • 단점: 리스트 앞부분에 작은 블록 조각(splinters)이 남아 탐색 성능 저하 발생.
2. Next Fit (다음 적합)
   • First Fit과 유사하지만, 매번 리스트의 처음부터가 아니라 이전 탐색이 끝난 위치에서부터 다시 시작한다.
   • 장점: 앞부분에 작은 조각들이 쌓이는 문제를 완화할 수 있으며 속도가 빠르다.
   • 단점: 메모리 사용 효율성은 First Fit보다 낮을 수 있다.
3. Best Fit (최적 적합)
   • 모든 가용 블록을 검사해, 요청을 만족하는 가장 작은 블록을 선택한다.
   • 장점: 메모리 사용 효율성이 가장 높다.
   • 단점: 전체 힙을 완전히 탐색해야 하므로 성능이 떨어질 수 있다. 특히 묵시적 가용 리스트 같은 단순 구조에선 비효율적이다.

배치 정책	탐색 방식 설명	장점	단점
First Fit	자유 리스트의 처음부터 순차 탐색, 조건에 맞는 첫 블록에 할당	구현이 간단하고 빠름	앞부분에 작은 블록 조각(splinters)이 쌓일 수 있음
Next Fit	이전 탐색 종료 지점부터 다음 블록부터 탐색, 순환적으로 진행	First Fit보다 속도 개선 가능성 있음	메모리 단편화 심화 가능성 있음
Best Fit	전체 리스트 탐색, 요청을 만족하는 가장 작은 블록 선택	메모리 공간 효율성이 가장 높음	전체 힙을 탐색해야 하므로 속도 저하 발생 가능

---

9.9.8절 "자유 블록 분할 (Splitting Free Blocks)"

기본 개념

• 할당기는 적절한 가용 블록을 찾으면, 그 전체를 사용할지, 아니면 분할(split)해서 사용할지를 결정한다.
• 전체 사용은 구현이 간단하고 빠르지만, 내부 단편화(internal fragmentation)를 초래할 수 있다.
• 내부 단편화는 요청한 크기보다 더 큰 블록을 통째로 할당하면서 낭비되는 공간이다.

분할 전략

• 적절한 블록 분할을 통해 낭비를 줄일 수 있다.
• 예를 들어, 요청 크기가 작고 가용 블록이 충분히 크다면:
  • 요청된 크기만큼만 할당 블록으로 만들고,
  • 남은 부분은 새로운 가용 블록으로 분리한다.
• 이때 남은 조각이 너무 작으면 분할하지 않고 전체를 할당하기도 한다.

그림 9.37 세 블록 할당 요청을 만족시키기 위한 free 블록 쪼개기

 

• 책의 그림 9.37은 크기 8 워드짜리 자유 블록을 3 워드 요청을 위해 분할하는 예시를 보여준다.
• 그림에서 음영 처리된 부분은 할당된 블록이며, 나머지는 가용 블록이다.

---

9.9.9절 "추가 힙 메모리 요청 (Getting Additional Heap Memory)"

언제 추가 메모리를 요청하는가?

• 할당기가 적당한 크기의 가용 블록을 찾지 못할 경우 다음과 같은 두 가지 대안을 고려한다:
  1. 인접한 가용 블록들을 병합(coalescing) 하여 더 큰 블록을 생성한다.
  2. 그래도 충분한 크기의 블록이 없으면, 커널에 새로운 힙 메모리 요청을 한다.

sbrk 함수 사용

• 추가 메모리 요청은 sbrk 시스템 호출을 통해 이루어진다.
• sbrk(n)은 프로세스 힙의 크기를 n바이트만큼 늘려준다.
• 이로써 힙 끝에 새로 확보된 공간은 하나의 큰 가용 블록으로 변환된다.

과정 요약

1. sbrk 호출로 새 힙 메모리 확보.
2. 확보된 메모리를 하나의 가용 블록으로 초기화.
3. 이 자유 블록을 가용 리스트에 삽입.
4. 해당 블록 중 일부를 요청된 크기만큼 할당.

---

CSAPP 3판의 9.9.10절 "자유 블록 병합 (Coalescing Free Blocks)"

왜 병합이 필요한가?

• 블록을 해제(free)하면 그 블록의 앞뒤에 다른 가용 블록이 존재할 수 있다.
• 이처럼 힙에 많은 자유 블록이 흩어져 있으면, 전체 가용 공간은 충분해도 큰 블록 하나로 사용이 불가능한 경우가 발생한다. 이를 "false fragmentation(가짜 단편화: 책은 오류 단편화)"라고 한다.
• 예: 3 워드짜리 가용 블록이 2개 연속해 있어도, 4 워드를 요청하면 실패한다.

병합(coalescing) 방식

가용 블록이 해제되면, 인접한 다른 가용 블록들과 병합할 수 있다. 이때 두 가지 주요 정책이 존재한다:

1. 즉시 병합 (Immediate Coalescing)
   • 매번 free 호출 시점에 바로 인접 블록과 병합을 수행한다.
   • 장점: 단편화를 즉시 줄일 수 있음.
   • 단점: 반복적인 할당과 해제가 있을 경우, 쓸데없는 병합과 분할이 반복될 수 있음.
2. 지연 병합 (Deferred Coalescing)
   • free 할 때는 병합하지 않고, 나중에 필요해질 때 (예: 할당 실패 시) 한꺼번에 힙을 순회하며 병합한다.
   • 장점: 성능 향상 가능.

요약

• 병합은 false fragmentation 방지를 위해 필수적이다.
• 병합 정책(즉시 vs 지연)은 성능과 단편화 간의 절충이 필요하다.
• 실전에서는 상황에 따라 적절한 병합 전략을 선택하거나 혼합해서 사용하기도 한다.

---

CSAPP 3판의 9.9.11절 "경계 태그를 이용한 병합(Coalescing with Boundary Tags)"

가용 블록 병합을 상수 시간에 수행할 수 있도록 하는 경계 태그(boundary tag) 기법을 설명한다.

왜 경계 태그가 필요한가?

• 다음 블록과의 병합은 현재 블록의 헤더를 통해 바로 접근 가능하므로 간단하게 처리된다.
• 반면, 이전 블록과의 병합은 블록에 명시적으로 이전 블록의 포인터가 없다면 전체 힙을 순회해야 하므로 시간이 선형으로 걸린다.

경계 태그(Boundary Tags) 구조

그림 9.39 경계 태그를 사용하는 힙 블록의 포멧

• 해결책: 각 블록의 끝에 푸터(footer)를 추가한다.
  • 푸터는 헤더와 동일한 정보(블록 크기 및 할당 여부)를 담는다.
• 현재 블록에서 한 워드만 뒤로 가면 이전 블록의 푸터에 접근할 수 있다.
• 푸터를 통해 이전 블록의 시작 위치와 상태를 바로 알 수 있어 상수 시간 병합이 가능하다.

병합 케이스 (Figure 9.40 기준)

1. 이전, 다음 모두 할당됨
   → 병합 없음. 현재 블록만 자유 상태로 전환.
2. 이전 할당, 다음 가용
   → 현재 블록과 다음 블록 병합. 새로운 크기로 헤더와 푸터 갱신.
3. 이전 가용, 다음 할당
   → 이전 블록과 현재 블록 병합. 헤더와 푸터 갱신.
4. 이전, 다음 모두 가용
   → 세 블록 모두 병합. 이전 블록의 헤더와 다음 블록의 푸터를 갱신.

장점과 단점

• 장점: 상수 시간 병합 가능. 다양한 할당기 구조에 쉽게 일반화 가능.
• 단점: 각 블록에 푸터 추가로 메모리 오버헤드 발생.
  특히, 작은 블록이 많은 경우 오버헤드가 심각해질 수 있다.

최적화 방법

• 할당된 블록에는 푸터를 생략할 수 있음.
• 대신, 현재 블록의 헤더에 이전 블록의 상태(할당 여부)를 인코딩하여 보존.
• 이렇게 하면 가용 블록만 푸터를 가지게 하여 오버헤드를 줄일 수 있다​.