[Computer System] ⑨ 가상메모리 (2)

Krafton Jungle/4. CSAPP

[Computer System] ⑨ 가상메모리 (2)

munsik22 2025. 4. 24. 14:36

9.9 동적 메모리 할당

동적 메모리 할당기Dynamic memory allocator는 힙heap이라고 하는 프로세스의 가상메모리 영역을 관리한다. 여기서 힙은 미초기화된 데이터 영역 직후에서 시작해 위쪽(높은 주소 방향)으로 커지는 무요구 메모리demand-zero memory 영역이라고 가정한다. 각각의 프로세스에 대해서 커널은 힙의 Top을 가리키는 변수 brk(break)를 사용한다.

할당기는 힙을 다양한 크기의 블록block들의 집합으로 관리한다. 각 블록은 할당allocated되었거나 가용free 상태인 가상메모리의 연속적인 묶음(contiguous chunk)이다.

할당기의 두 가지 기본 유형은 다음과 같다:

명시적 할당기Explicit allocator : 응용 프로그램이 명시적으로 할당된 블록을 반환해 줄 것을 요구한다. (예: C의 malloc 패키지)
묵시적 할당기Implicit allocator : 언제 할당된 블록이 더 이상 프로그램에 의해 사용되지 않고 블록을 반환하는지를 할당기가 검출할 수 있을 것을 요구한다. (= 가비지 컬렉터Garbage collector)

9.9.1 malloc 함수와 free 함수

🔹 malloc(size_t size)
- 최소 size 바이트의 메모리를 heap 영역에서 할당
- 항상 정렬된 주소 반환 (32bit에서는 8byte, 64bit에서는 16byte 단위)
🔹 free(void *ptr) : 이전에 할당받은 메모리를 해제
🔹 내부적으로는 sbrk 또는 mmap 시스템 호출을 통해 힙을 확장함

C 표준 라이브러리는 malloc 패키지로 알려진 Explicit(명시적) 할당기를 제공한다. 프로그램은 malloc 함수를 호출해서 힙으로부터 블록들을 할당받는다.

#include <stdlib.h>
void *malloc(size_t size);
// Returns: pointer to allocated block if OK, NULL on error

malloc 함수는 주어진 크기 이상의 메모리 블록에 대한 포인터를 반환하며, 이 블록은 어떤 종류의 데이터 객체가 포함될 수 있도록 적절하게 정렬된다. 실제로 정렬은 코드가 32비트 모드(gcc -m32)로 컴파일되었는지 64비트 모드(기본값)로 컴파일되었는지에 따라 달라진다.

정렬 규칙
- 32비트 모드: malloc은 주소가 항상 8의 배수가 되는 블록을 반환
- 64비트 모드: 주소가 항상 16의 배수가 되는 블록을 반환
문제 발생 시 처리
- malloc이 문제를 발견하면, NULL을 반환하고 errno를 설정한다.
- 예: 요청된 메모리 블록이 사용 가능한 가상 메모리보다 클 경우
메모리 초기화
- malloc은 반환된 메모리를 초기화하지 않는다.
- 초기화된 동적 메모리를 원할 경우, calloc을 사용할 수 있다. 이는 malloc 함수의 얇은 래퍼(wrapper)로, 할당된 메모리를 0으로 초기화한다.
블록 크기 변경
- 이전에 할당된 블록의 크기를 변경하려면 realloc 함수를 사용할 수 있다.

동적 메모리 할당기인 malloc은 힙 메모리를 명시적으로 할당하거나 해제할 수 있으며, 이때 mmap 및 munmap 함수를 사용하거나 sbrk 함수를 사용할 수 있다.

#include <unistd.h>
void *sbrk(intptr_t incr);
// Returns: old brk pointer on success, −1 on error

sbrk 함수는 힙을 증가 또는 감소시켜 커널의 brk 포인터에 incr 값을 추가한다.
성공하면 이전의 brk 값을 반환하고, 실패하면 -1을 반환하며 errno를 ENOMEM으로 설정한다.
incr 값이 0일 경우, sbrk는 현재 brk 값을 반환한다.
음수의 incr 값을 사용하는 것은 가능하지만 복잡할 수 있다. 이 경우 반환 값(이전 brk 값)은 새로운 힙의 상단에서 abs(incr) 바이트를 초과한 위치를 가리킨다.

#include <stdlib.h>
void free(void *ptr);
// Returns: nothing

프로그램은 할당된 힙 블록을 해제하기 위해 free 함수를 호출한다. ptr 인자는 malloc, calloc 또는 realloc에서 얻은 할당된 블록의 시작을 가리켜야 한다. 그렇지 않으면 free의 동작은 정의되지 않는다. 게다가 free는 아무것도 반환하지 않기 때문에 응용프로그램에 문제가 발생했음을 알리는 방법이 없는데, 이는 혼란스러운 런타임 오류를 발생시킬 수 있다.

위 그림은 16워드의 작은 힙에서 malloc과 free를 사용하여 블록을 할당하고 해제하는 과정을 보여준다. (각 사각형은 하나의 워드(4byte)를 나타낸다. 각 두꺼운 직사각형은 하나의 블록을 의미하며, 할당된 블록은 음영 처리되어 있다. 할당된 블록의 패딩 영역은 더 어둡게 음영 처리된다. 할당되지 않은 블록은 음영 처리되지 않는다. 힙 주소는 왼쪽에서 오른쪽으로 증가한다.)

(a) 프로그램이 4워드 블록을 요청한다: malloc은 가용 블록의 앞부분에서 4워드 블록을 잘라내어 블록의 첫 번째 워드에 대한 포인터를 반환한다.
(b) 프로그램이 5워드 블록을 요청한다: malloc은 가용 블록의 앞부분에서 6워드 블록을 할당한다. 여기서 malloc은 가용 블록이 더블 워드 경계에 정렬되도록 추가 워드로 블록을 패딩한다.
(c) 프로그램이 6워드 블록을 요청하고, malloc은 자유 블록에서 6워드 블록을 잘라낸다.
(d) 프로그램이 (b)에서 할당된 6워드 블록을 해제한다: free 호출이 반환된 후에도 포인터 p2는 여전히 해제된 블록을 가리킨다. p2를 다시 사용하지 않도록 하는 것은 응용프로그램의 책임이다. p2는 새 malloc 호출로 재초기화될 때까지 사용해서는 안 된다.
(e) 프로그램이 두 개의 워드 블록을 요청한다: 이 경우, malloc은 이전 단계에서 해제된 블록의 일부를 할당하고 이 새로운 블록에 대한 포인터를 반환한다.

9.9.2 왜 동적 메모리 할당을 사용해야 하나?

// 정적 할당
int arr[1234];

// 동적 할당
int arr = (int *)malloc(n * sizeof(int));

프로그램 실행 전에는 데이터 구조 크기를 모르는 경우가 많다.
하드코딩된 배열(정적 할당)은 유연하지 않고 유지보수가 어렵다.
malloc을 쓰면 가상 메모리 공간 내에서 필요한 만큼만 동적으로 할당이 가능하다.
런타임에 필요한 만큼만 heap에 동적으로 할당하면 메모리 효율이 높아진다.

9.9.3 할당기 요구사항과 목표

🔹 제약
- 임의의 순서로 malloc/free 호출 가능
- 즉각 응답 필요 (buffering 불가)
- 정렬 요구 준수
- 할당된 블록 수정 금지
🔹 목표
- Throughput 최대화: 시간당 처리 요청 수
- Utilization 최대화: 사용 중인 payload / 전체 heap 크기

Explicit(명시적) 할당기는 몇 가지 엄격한 제약 조건 내에서 작동해야 한다.

임의 요청 시퀀스 처리: 응용프로그램은 할당 및 해제 요청의 임의 시퀀스를 만들 수 있으며, 각 해제 요청은 이전의 할당 요청에서 얻은 현재 할당된 블록에 해당해야 한다. 따라서 할당자는 할당 및 해제 요청의 순서에 대해 어떤 가정을 할 수 없다. 예를 들어, 할당자는 모든 할당 요청에 매칭되는 해제 요청이 있다고 가정할 수 없으며, 매칭되는 할당 및 해제 요청이 중첩되어 있다고 가정할 수 없다.
즉각적인 요청 응답: 할당자는 할당 요청에 즉시 응답해야 한다. 따라서 성능 향상을 위해 요청을 재정렬하거나 버퍼링하는 것이 허용되지 않는다.
힙만 사용: 할당자가 확장 가능하도록 하기 위해, 할당자에서 사용하는 모든 비스칼라 데이터 구조는 힙 자체에 저장되어야 한다.
블록 정렬(정렬 요건): 할당자는 블록을 정렬하여 모든 유형의 데이터 객체를 수용할 수 있도록 해야 한다.
할당된 블록 수정 금지: 할당자는 해제된 블록만 조작하거나 변경할 수 있다. 특히, 할당된 블록은 수정하거나 이동할 수 없다. 따라서 할당된 블록의 압축과 같은 기술은 허용되지 않는다.

이러한 제약 조건 내에서 할당기 개발자는 처리량과 메모리 활용도를 극대화하는 종종 상충하는 성능 목표를 충족하려고 한다. 처리량을 높이기 위해 할당기는 할당 및 해제 요청에 신속하게 응답해야 하며, 메모리 활용도를 높이기 위해서는 가능한 한 많은 메모리를 효율적으로 사용해야 한다. 이러한 목표를 달성하기 위해 다양한 알고리즘과 전략이 사용되며, 특히 블록 정렬 및 관리 방식에서 균형을 맞추는 것이 중요하다.

처리량Throughput 극대화: 할당자는 요청에 신속하게 응답하고, 할당 및 해제의 오버헤드를 최소화하여 처리량을 극대화해야 한다. 이를 위해 효율적인 메모리 할당 알고리즘을 사용하고, 메모리 블록의 관리 방식을 최적화할 필요가 있다.
메모리 활용도Utilization 극대화: 메모리 활용도를 높이기 위해 할당자는 가능한 한 많은 메모리를 효율적으로 사용해야 한다. 이를 위해 해제된 블록을 효과적으로 재사용하고, 메모리 단편화를 최소화하는 전략을 적용해야 한다.

9.9.4 단편화

🔹 Internal Fragmentation: 할당된 블록이 payload보다 클 때 발생
🔹 External Fragmentation: 충분한 여유 메모리는 있지만 연속된 공간이 부족할 때
🔹 Internal은 계산 가능하지만, External은 미래 요청에 따라 결정되므로 예측이 어렵다.
🔸 해결책: Coalescing(연결), Splitting(분할) 기법 활용

힙 활용도가 낮은 주된 원인은 단편화fragmentation라는 현상이다. 단편화는 사용되지 않는 메모리가 할당 요청을 충족시키지 못할 때 발생한다.

내부 단편화internal fragmentation
- 할당된 블록이 페이로드payload보다 클 때 발생한다.
  - 페이로드란 할당된 블록에서 데이터를 저장하기 위해 애플리케이션이 요청한 메모리를 말한다. (참고)
- 원인
  - 할당기의 구현이 할당된 블록에 최소 크기를 부여하는 경우
  - 정렬 제약을 충족하기 위해 블록 크기를 증가시키는 경우
- 내부 단편화는 쉽게 정량화할 수 있다. 할당된 블록의 크기와 페이로드 간의 차이의 합으로 계산된다.
- 특정 시점에서 내부 단편화의 양은 이전 요청 패턴과 할당기 구현에만 의존한다.
외부 단편화external fragmentation
- 총 가용 메모리가 충분하지만, 단일 가용 블록이 요청을 처리할 만큼 크지 않을 때 발생한다.
- 예를 들어, 요청이 두 개의 블록으로 나누어져 있는 여덟 개의 가용 단어보다 큰 경우, 추가 가상 메모리를 요청해야 한다.
- 외부 단편화는 내부 단편화보다 정량화하기 더 어렵다. 이는 이전 요청 패턴, 할당기 구현뿐만 아니라 미래 요청 패턴에도 의존하기 때문이다. 하지만 문식이는 귀엽다. 하하하
- 예를 들어, 모든 가용 블록이 정확히 네 개의 단어인 경우, 미래 요청이 모두 네 개 이하일 경우 외부 단편화가 없다. 그러나 하나 이상의 요청이 네 개 이상의 블록을 요구하면 외부 단편화가 발생한다.
- 외부 단편화는 정량화하기 어렵고 예측할 수 없기 때문에, 할당기는 일반적으로 큰 가용 블록 수를 유지하려고 노력하고, 작은 가용 블록 수를 줄이려는 휴리스틱을 사용한다.

9.9.5 구현 이슈

효율적인 할당기가 처리량과 활용도 간의 균형을 잘 맞추기 위해서는 다음 문제들을 고려해야 한다.

가용 블록 구성: 가용 블록을 어떻게 추적할 것인가?
배치: 새로 할당된 블록을 배치할 적절한 가용 블록을 어떻게 선택할 것인가?
분할Splitting: 새로 할당된 블록을 자유 블록에 배치한 후, 남은 자유 블록의 잔여 부분은 어떻게 처리할 것인가?
연결Coalescing: 방금 해제된 블록을 어떻게 처리할 것인가?

9.9.6 묵시적 가용 리스트

🔹 블록 내부에 헤더 포함 (블록 크기 + 할당 여부)
🔹 가용 블록은 탐색을 통해 식별
🔹 정렬 기준으로 블록 크기는 8의 배수
🔹 블록 경계는 헤더의 크기를 기반으로 계산

실용적인 할당기는 블록 경계를 구별하고 할당된 블록과 가용 블록을 구별할 수 있는 데이터 구조가 필요하다. 대부분의 할당기는 이 정보를 블록 자체에 포함시킨다. 간단한 접근 방식은 다음과 같다.

위 그림과 같은 블록 포맷이 주어졌을 때, 힙을 연속된 할당/가용 블록의 배열로 아래와 같이 구성할 수 있다. (할당된 블록은 음영 처리되어 있고, 가용 블록은 음영이 없다. 헤더는 (size (bytes)/allocated bit)로 표시된다.)

블록 구조
- 블록은 1워드 헤더header , 페이로드, 그리고 추가 패딩padding으로 구성된다.
- 헤더는 블록 크기(헤더 및 패딩 포함)와 블록이 할당되었는지 또는 가용한지를 인코딩한다.
- 더블 워드 정렬 제약을 두면, 블록 크기는 항상 8의 배수가 되고, 블록 크기의 하위 3비트는 항상 0이다.
  따라서 29개의 상위 비트만 저장하고 나머지 3비트를 다른 정보 인코딩에 사용한다.
- 여기서는 LSB(할당된 비트)를 사용하여 블록이 할당되었는지 또는 가용한지를 나타낸다.
  - 예: 24바이트(0x18) 크기의 할당된 블록의 헤더는 0x00000018 | 0x1 = 0x00000019
  - 40바이트(0x28) 크기의 가용 블록의 헤더는 0x00000028 | 0x0 = 0x00000028
패딩
- 페이로드 다음에 오는 패딩은 크기가 다양할 수 있다.
- 외부 단편화를 방지하거나 정렬 요구 사항을 충족하기 위해 필요할 수 있다.
묵시적 가용 리스트
- 블록 형식에 따라 힙을 연속적인 할당 블록과 가용 블록의 시퀀스로 구성할 수 있다.
- 이 구조를 묵시적 가용 리스트implicit free list 라고 하며, 가용 블록은 헤더의 크기 필드로 암묵적으로 연결된다.
- 할당기는 힙의 모든 블록을 순회하여 가용 블록 집합을 간접적으로 탐색할 수 있다.
- 특별히 표시된 종료 블록(여기서는 할당 비트가 설정되고 크기가 0인 헤더)이 필요하다.
장점과 단점
- 장점: 단순성
- 단점: 가용 리스트 검색이 필요한 작업(예: 할당 블록 배치)의 비용이 힙의 총 할당 및 가용 블록 수에 비례하여 선형적이다.
최소 블록 크기
- 시스템의 정렬 요구 사항과 할당기의 블록 형식 선택은 할당기에서 최소 블록 크기를 부과한다.
- 예를 들어, 더블 워드 정렬 요구조건을 가정하면 각 블록은 2워드(8바이트)의 배수여야 한다.
- 따라서, 1바이트를 요청하더라도 할당기는 2워드 블록을 생성한다.

다음의 malloc 요청 배열의 결과를 얻는 블록의 크기와 헤더 값을 결정하시오.

할당기는 더블 워드 정렬을 유지하며 위 그림의 블록 포맷을 가지는 묵시적 가용 리스트를 사용한다.
블록 크기들은 인접 8바이트의 배수로 반올림한다.

Request	Block size (decimal bytes)	Block header (hex)
malloc(2)	8	0x09
malloc(9)	16	0x11
malloc(15)	24	0x19
malloc(20)	24	0x19

해설 : 이 문제는 정렬 요구 사항, 최소 블록 크기, 헤더 인코딩과 같은 핵심 개념과 관련이 있다. 블록 크기를 결정하는 일반적인 접근 방식은 요청된 페이로드와 헤더 크기의 합을 정렬 요구 사항(이 경우 8바이트)의 가장 가까운 배수로 올리는 것이다. 예를 들어, malloc(2) 요청의 블록 크기는 4 + 2 = 6이 되고, 이를 8로 올림하면 8이 된다. malloc(20) 요청의 블록 크기는 20 + 4 = 24로, 이미 24로 정렬되어 있으므로 추가로 올릴 필요가 없다.

9.9.7 할당된 블록의 배치

🔹 First Fit: 가장 먼저 맞는 free block 선택
🔹 Next Fit: 이전 탐색 위치 이후부터 탐색
🔹 Best Fit: 가장 작은 적합한 block 선택
🔸 First Fit은 단순하고 빠르지만 조각splinter을 남긴다. Best Fit은 효율적이나 느리다.
🔸 Best Fit이 일반적으로 memory utilization 측면에서 우수하다.

응용프로그램이 k바이트의 블록을 요청하면, 할당기는 가용 리스트에서 요청된 블록을 수용할 수 있는 충분히 큰 가용 블록을 검색한다. 할당기가 이 검색을 수행하는 방식은 배치 정책에 의해 결정된다.

First fit은 가용 리스트의 시작부터 검색을 시작하여, 요청된 크기에 맞는 첫 번째 가용 블록을 선택한다.
- 장점 : 리스트의 끝에 큰 가용 블록을 유지하는 경향이 있다.
- 단점 : 시작 부분에 작은 가용 블록의 조각splinters이 남아 검색 시간을 증가시킨다.
Next fit은 첫 번째 적합과 유사하지만, 매 검색을 리스트의 시작 지점이 아니라 이전 검색이 끝난 지점에서 시작한다.
- 장점 : 리스트의 앞부분에 많은 작은 조각이 쌓일 경우, First fit보다 상당히 빠르게 실행될 수 있다.
- 단점 : 하지만 First fit보다 메모리 활용도가 낮아질 수 있다.
Best fit은 모든 가용 블록을 검사하여 요청된 크기에 맞는 가장 작은 가용 블록을 선택한다.
- 장점 : 일반적으로 First fit이나 Next fit보다 더 나은 메모리 활용도를 가진다.
- 단점 : 간단한 가용 리스트 구성(예: 묵시적 가용 리스트)에서 사용할 경우 힙을 전체적으로 검색해야 한다.

9.9.8 가용 블록의 분할

🔹 큰 free block을 사용 후 남은 공간은 새 free block으로 분할
🔹 단, 분할 시 최소 블록 크기 보장 필요 (헤더, 풋터, 정렬 고려)

할당기가 적합한 가용 블록을 찾으면, 그 가용 블록의 얼마를 할당할지에 대한 정책 결정을 또 해야 한다. 한 가지 옵션은 전체 가용 블록을 사용하는 것이다. 이는 간단하고 빠르지만, 주요 단점은 내부 단편화를 초래한다. 만약 배치 정책이 좋은 fit을 만든다면, 일부 추가적인 내부 단편화는 허용될 수 있다.

그러나 fit이 좋지 않은 경우, 할당기는 일반적으로 가용 블록을 두 부분으로 나누는 선택을 한다. 첫 번째 부분은 할당된 블록이 되고, 나머지 부분은 새로운 가용 블록이 된다. 아래 그림은 할당기가 위 그림의 8워드 가용 블록을 어떻게 나누어 응용프로그램의 3워드 힙 메모리 요청을 충족시킬 수 있는지를 보여준다.

9.9.9 추가적인 힙 메모리 획득하기

🔹 할당 가능한 블록이 없을 경우, sbrk() 또는 mem_sbrk()을 사용해 heap 공간 확장
🔹 새로 받은 영역은 하나의 큰 free block으로 사용됨

할당기가 요청된 블록에 대한 적합한 블록을 찾지 못하면 어떻게 될까? 한 가지 옵션은 메모리에서 물리적으로 인접한 가용 블록을 coalescing(연결)하여 더 큰 가용 블록을 만드는 것이다(9.9.10). 그러나 이것으로 충분히 큰 블록이 생성되지 않거나 가용 블록이 이미 최대한 병합된 상태라면, 할당기는 커널에 추가 힙 메모리를 요청하기 위해 sbrk 함수를 호출한다. 할당기는 추가 메모리를 하나의 큰 가용 블록으로 변환하고, 이 블록을 가용 리스트에 삽입한 후 요청된 블록을 이 새로운 가용 블록에 배치한다.

9.9.10 가용 블록 연결하기

🔹 인접한 가용 블록들을 합쳐서 큰 블록으로 만들기
🔹 즉시 병합(immediate) vs. 지연 병합(deferred) 정책 존재
🔹 즉시 병합은 간단하지만, 반복 split/merge 발생 가능

할당기가 할당된 블록을 해제할 때, 새로 해제된 블록에 인접한 다른 가용 블록이 있을 수 있다. 이러한 인접한 가용 블록은 오류 단편화false fragmentation 현상을 일으킬 수 있으며, 이는 많은 가용 메모리가 작은 사용 불가능한 가용 블록으로 나뉘어져 있는 상태를 의미한다. 예를 들어, 아래 그림은 위 그림에서 할당된 블록을 해제한 결과를 보여준다. 그 결과, 각각 3워드의 페이로드를 가진 두 개의 인접한 가용 블록이 생성된다. 이로 인해 4워드의 페이로드를 요청하는 후속 요청이 실패하게 되는데, 이는 두 개의 가용 블록의 총 크기가 요청을 충족하기에 충분함에도 불구하고 발생한다.

오류 단편화에 대응하기 위해, 실용적인 할당기는 인접한 가용 블록을 병합하는 과정인 연결coalescing을 수행해야 한다. 이는 연결을 언제 수행할지에 대한 중요한 정책 결정을 해야 한다.

할당기는 블록이 해제될 때마다 인접한 블록을 병합하는 즉시 연결immediate coalescing을 선택할 수 있다.
- 즉시 연결은 간단하며 상수 시간 내에 수행할 수 있지만, 일부 요청 패턴에서는 블록이 반복적으로 병합된 다음 곧바로 다시 나누어지는 형태의 쓰래싱을 초래할 수 있다.
또는 나중에 가용 블록을 병합하기 위해 지연 연결deferred coalescing을 선택할 수도 있다.
- 예를 들어, 할당기는 할당 요청이 실패할 때까지 연결을 지연시킨 후, 전체 힙을 스캔하여 모든 가용 블록을 병합할 수 있다.

9.9.11 경계 태그로 연결하기

🔹 블록에 footer를 추가하여 이전 블록 정보도 빠르게 조회 가능
🔹 이를 통해 constant time 병합 가능
🔹 Header와 Footer 모두 같은 정보를 저장함
🔸 해제된 블록의 인접 블록이 free이면 병합
🔸 Boundary Tags를 사용해 풋터로 이전 블록 상태 확인
🔸 4가지 케이스: 양쪽 모두 allocated / 다음 블록만 free / 이전 블록만 free / 양쪽 모두 free

경계 태그Boundary tag는 이전 블록의 즉시 연결을 상수 시간 내에 수행할 수 있게 하는 기법이다. 위 그림을 보면 각 블록의 끝에 풋터footer(경계 태그)가 추가되었다. 이 풋터는 헤더의 복제본이다. 각 블록이 이러한 풋터를 포함하면, 할당기는 현재 블록의 시작 위치와 상태를 풋터를 검사하여 확인할 수 있다. 풋터는 항상 현재 블록의 시작에서 1워드 떨어져 있기 때문이다.

할당기가 현재 블록을 반환할 때 가능한 모든 경우들을 보자.

이전 블록과 다음 블록이 모두 할당됨
이전 블록은 할당되고 다음 블록은 가용됨
이전 블록은 가용하고 다음 블록은 할당됨
이전 블록과 다음 블록이 모두 가용함

아래 그림은 이 네 가지 경우 모두를 연결하는 방법을 보여준다.

다음의 각 정렬 요구조건과 블록 형식에 대해 최소 블록 크기를 결정하시오.

묵시적 사정 리스트 사용, 데이터의 크기는 1보나 커야하고, 헤더와 풋터는 4바이트 워드에 저장된다.

Alignment	Allocated block	Free block	Minimum block size (bytes)
Single word	Header and footer	Header and footer	12
Single word	Header, but no footer	Header and footer	8
Double word	Header and footer	Header and footer	16
Double word	Header, but no footer	Header and footer	8

해설 : 최소 블록 크기는 내부 단편화에 상당한 영향을 미칠 수 있다. 따라서 다양한 할당기 설계와 정렬 요구 사항에 따른 최소 블록 크기를 이해하는 것이 중요하다. 주의해야 할 점은 동일한 블록이 시간에 따라 할당되거나 가용 상태가 될 수 있다는 것이다. 따라서 최소 블록 크기는 최소 할당 블록 크기와 최소 가용 블록 크기 중 최대값이 된다. 예를 들어, 마지막 문제에서 최소 할당 블록 크기는 4바이트 헤더와 1바이트 페이로드를 합쳐 8바이트로 올림한 것이다. 최소 가용 블록 크기는 4바이트 헤더와 4바이트 풋터로, 이미 8의 배수이므로 올릴 필요가 없다. 따라서 이 할당기의 최소 블록 크기는 8바이트가 된다.

9.9.12 간단한 할당기 구현

🔹 묵시적 자유 리스트 + 경계 태그 연결 + First Fit 기반 구현
🔹 주요 함수: mm_init(), mm_malloc(), mm_free(), place(), coalesce(), extend_heap() 등
🔹 메모리 모델: memlib.c 사용 → 시스템 malloc 대신 테스트 가능하게 함

할당기 기본 설계

[memlib.c 메모리 시스템 모델]

/* Private global variables */
static char *mem_heap; 		// Points to first byte of heap
static char *mem_brk; 		// Points to last byte of heap plus 1
static char *mem_max_addr; 	// Max legal heap addr plus 1

/* mem_init - Initialize the memory system model */
void mem_init(void) {
	mem_heap = (char *)Malloc(MAX_HEAP);
	mem_brk = (char *)mem_heap;
	mem_max_addr = (char *)(mem_heap + MAX_HEAP);
}

/* mem_sbrk - Simple model of the sbrk function.
Extends the heap by incr bytes and returns the start address of the new area.
In this model, the heap cannot be shrunk. */
void *mem_sbrk(int incr) {
	char *old_brk = mem_brk;

	if ( (incr < 0) || ((mem_brk + incr) > mem_max_addr)) {
		errno = ENOMEM;
		fprintf(stderr, "ERROR: mem_sbrk failed. Ran out of memory...\n");
		return (void *)-1;
	}
	mem_brk += incr;
	return (void *)old_brk;
}

이 모델의 목적은 기존 시스템 수준의 malloc 패키지와 간섭 없이 할당기를 실행할 수 있게 하는 것이다.

메모리 모델:
- mem_init 함수: 힙에 사용할 수 있는 가상 메모리를 큰 더블 워드 정렬 배열로 모델링.
- mem_heap와 mem_brk 사이의 바이트는 할당된 가상 메모리를 나타냄.
- mem_brk 이후의 바이트는 가용되지 않은 가상 메모리.
- 할당기는 mem_sbrk 함수를 호출하여 추가 힙 메모리를 요청하며, 이 함수는 시스템의 sbrk 함수와 동일한 인터페이스와 의미를 가지지만 힙 축소 요청은 거부.
할당기 구현:
- 할당기는 사용자 애플리케이션에 컴파일하고 링크할 수 있는 소스 파일(mm.c)에 포함됨.
- 할당기는 애플리케이션 프로그램에 세 가지 함수를 내보냄:
  1. extern int mm_init(void);
  2. extern void *mm_malloc(size_t size);
  3. extern void mm_free(void *ptr);
- mm_init 함수: 할당기를 초기화하며 성공 시 0을 반환하고, 실패 시 -1을 반환.
- mm_malloc 및 mm_free 함수: 시스템의 대응 함수와 동일한 인터페이스와 의미를 가짐.
블록 형식:
- 할당기는 경계 태그를 사용하는 블록 포맷을 사용하며, 최소 블록 크기는 16바이트.
- 가용 리스트는 암묵적 가용 리스트로 구성되며, 아래 그림처럼 불변 형식을 따른다.
- 첫 번째 워드는 더블 워드 경계에 정렬된 사용되지 않는 패딩 워드.
- 패딩 뒤에는 특수 프롤로그 블록이 있으며, 이는 8바이트 할당 블록으로 헤더와 풋터만 포함됨. 프롤로그 블록은 초기화 중에 생성되며 절대 해제되지 않음.
- 프롤로그 블록 뒤에는 malloc 또는 free 호출로 생성된 정규 블록이 0개 이상 존재.
- 힙은 항상 헤더만 포함된 0 크기 할당 블록인 특수 에필로그 블록으로 끝남.
- 프롤로그와 에필로그 블록은 연결 중 엣지 조건을 제거하는 트릭이다.
전역 변수:
- 할당기는 항상 프롤로그 블록을 가리키는 단일 비공개(static) 전역 변수(heap_listp)를 사용한다.
- (소규모 최적화로, 이를 프롤로그 블록 대신 다음 블록을 가리키도록 할 수 있다.)

가용 리스트 조작을 위한 기본 상수와 매크로

/* Basic constants and macros */
#define WSIZE 4        /* Word and header/footer size (bytes) */
#define DSIZE 8        /* Double word size (bytes) */
#define CHUNKSIZE (1<<12)  /* Extend heap by this amount (bytes) */

#define MAX(x, y) ((x) < (y) ? (y) : (x))

/* Pack a size and allocated bit into a word */
#define PACK(size, alloc) ((size) | (alloc))

/* Read and write a word at address p */
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))

/* Read the size and allocated fields from address p */
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)

/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

기본 크기 상수 정의
- WSIZE: 워드 크기
- DSIZE: 더블 워드 크기
- CHUNKSIZE: 초기 가용 블록 크기 및 힙 확장을 위한 기본 크기
가용 리스트 조작
- 헤더와 풋터를 조작하는 것은 캐스팅과 포인터 산술을 광범위하게 사용해야 하므로 어려움이 있다.
- 이를 위해 가용 리스트에 접근하고 탐색하는 작은 매크로 집합을 정의한다.
매크로 설명
- PACK 매크로 (라인 9): 크기와 할당 비트를 결합하여 헤더나 풋터에 저장할 수 있는 값을 반환
- GET 매크로 (라인 12): 인수 p가 참조하는 워드를 읽어 반환
- p는 일반적으로 (void *) 포인터로, 직접 역참조할 수 없다
- PUT 매크로 (라인 13): 인수 p가 가리키는 워드에 val을 저장
- GET_SIZE 매크로 (라인 16): 주소 p에서 크기를 반환
- GET_ALLOC 매크로 (라인 17): 주소 p에서 할당 비트를 반환
- HDRP 및 FTRP 매크로 (라인 20-21): 블록 포인터(bp)로부터 블록 헤더와 풋터에 대한 포인터를 반환
- NEXT_BLKP 및 PREV_BLKP 매크로 (라인 24-25): 다음 블록과 이전 블록의 포인터를 반환
매크로 조합 예시
- 현재 블록에 대한 포인터 bp가 주어졌을 때, 다음 블록의 크기를 구하는 코드는 다음과 같다.
- 현재 블록에 대한 포인터 bp가 주어졌을 때, 다음 블록의 크기를 구하는 코드는 다음과 같다.

size_t curr_size = GET_SIZE(HDRP(bp));			// 현재 블록의 크기
size_t next_size = GET_SIZE(HDRP(NEXT_BLKP(bp))); 	// 다음 블록의 크기

초기 가용 리스트 만들기

[mm_init] 최초 가용 블록으로 힙 생성하기

int mm_init(void)
{
    /* Create the initial empty heap */
    if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
        return -1;

    PUT(heap_listp, 0);                          /* Alignment padding */
    PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); /* Prologue header */
    PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
    PUT(heap_listp + (3 * WSIZE), PACK(0, 1));       /* Epilogue header */
    heap_listp += (2 * WSIZE);

    /* Extend the empty heap with a free block of CHUNKSIZE bytes */
    if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
        return -1;
    return 0;
}

[extend_heap] 새 가용 블록으로 힙 확장하기

static void *extend_heap(size_t words)
{
	char *bp;
	size_t size;

	/* Allocate an even number of words to maintain alignment */
	size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;
	if ((long)(bp = mem_sbrk(size)) == -1)
		return NULL;

	/* Initialize free block header/footer and the epilogue header */
	PUT(HDRP(bp), PACK(size, 0)); /* Free block header */
	PUT(FTRP(bp), PACK(size, 0)); /* Free block footer */
	PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */

	/* Coalesce if the previous block was free */
	return coalesce(bp);
}

mm_malloc 또는 mm_free를 호출하기 전에, 애플리케이션은 mm_init 함수를 호출하여 힙을 초기화해야 한다.

mm_init 함수:
- 네 개의 워드를 메모리 시스템에서 가져와서 빈 가용 리스트를 만들도록 초기화 (라인 4–10).
- extend_heap 함수를 호출하여 CHUNKSIZE 바이트만큼 힙을 확장하고 초기 가용 블록을 생성.
- 이 시점에서 할당기가 초기화되며 애플리케이션의 할당 및 해제 요청을 받을 준비가 됨.
extend_heap 함수 호출:
- 두 가지 상황에서 호출됨:
  1. 힙이 초기화될 때
  2. mm_malloc이 적절한 블록을 찾지 못할 때
- 정렬을 유지하기 위해, 요청된 크기를 가장 가까운 2워드(8바이트) 배수로 올림한 후 메모리 시스템에 추가 힙 공간을 요청 (라인 7–9).
extend_heap 함수의 나머지 부분 (라인 12–17):
- 힙은 더블 워드 정렬 경계에서 시작하며, extend_heap 호출 시 반환되는 블록은 더블 워드의 정수 배수 크기.
- 각 mem_sbrk 호출은 에필로그 블록의 헤더 바로 뒤에 위치한 더블 워드 정렬 메모리 청크를 반환.
- 이 헤더는 새로운 가용 블록의 헤더가 됨 (라인 12).
- 청크의 마지막 워드는 새로운 에필로그 블록의 헤더가 됨 (라인 14).
- 이전 힙이 가용 블록으로 종료된 경우, coalesce 함수를 호출하여 두 개의 가용 블록을 병합하고 병합된 블록의 포인터를 반환 (라인 17).

블록 반환과 연결

[mm_free] 블록을 free시키고 경계 태그 연결을 사용하여 인접한 가용 블록과 상수 시간 내에 병합한다.

void mm_free(void *bp)
{
    size_t size = GET_SIZE(HDRP(bp));

    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    coalesce(bp);
}

static void *coalesce(void *bp)
{
    size_t_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
    size_t_t next_alloc = GET_ALLOC(FTRP(NEXT_BLKP(bp)));
    size_t_t size = GET_SIZE(HDRP(bp));

    if (prev_alloc && next_alloc) { /* Case 1 */
        return bp;
    }
    else if (prev_alloc && !next_alloc) { /* Case 2 */
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }
    else if (!prev_alloc && next_alloc) { /* Case 3 */
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }
    else { /* Case 4 */
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + 
                GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }
    return bp;
}

응용프로그램은 mm_free 함수를 호출하여 이전에 할당된 블록을 해제한다. 이 함수는 요청된 블록(bp)을 해제한 후, 경계 태그 연결 기법(9.9.11)을 사용하여 인접한 가용 블록을 병합한다.

coalesce 협조 함수:
- 이 함수의 코드는 9.9.11에서 설명된 네 가지 경우를 간단하게 구현한 것이다.
미묘한 측면:
- 선택한 가용 리스트 형식은 항상 할당된 것으로 표시되는 프롤로그 및 에필로그 블록을 포함.
- 이로 인해 요청된 블록(bp)이 힙의 시작이나 끝에 있는 경우와 같은 잠재적인 엣지 조건을 무시할 수 있음.
특별 블록의 장점:
- 특별 블록이 없으면 코드가 더 복잡해지고 오류 발생 가능성이 높아지며, 각 해제 요청 시 드문 엣지 조건을 확인해야 하므로 성능이 저하됨.

블록 할당

[mm_malloc] 가용 리스트에서 블록 할당하기

void *mm_malloc(size_t size)
{
    size_t asize;      /* Adjusted block size */
    size_t extendsize; /* Amount to extend heap if no fit */
    char *bp;

    /* Ignore spurious requests */
    if (size == 0)
        return NULL;

    /* Adjust block size to include overhead and alignment reqs. */
    if (size <= DSIZE)
        asize = 2 * DSIZE;
    else
        asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);

    /* Search the free list for a fit */
    if ((bp = find_fit(asize)) != NULL) {
        place(bp, asize);
        return bp;
    }

    /* No fit found. Get more memory and place the block */
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize / WSIZE) == NULL)
        return NULL;
    place(bp, asize);
    return bp;
}

응용프로그램은 mm_malloc 함수를 호출하여 size 바이트의 메모리 블록을 요청한다. 추가적인 요청을 확인한 후, 할당기는 요청된 블록 크기를 조정하여 헤더와 풋터를 위한 공간을 확보하고 더블 워드 정렬 요구 사항을 충족해야 한다.

블록 크기 조정:
- 라인 12–13에서는 최소 블록 크기를 16바이트로 설정:
  1. 8바이트는 정렬 요구 사항을 충족하기 위해 필요.
  2. 8바이트는 헤더와 풋터의 오버헤드.
- 8바이트를 초과하는 요청에 대해서는 (라인 15), 일반 규칙으로 오버헤드 바이트를 추가한 후, 가장 가까운 8의 배수로 올림.
가용 블록 검색:
- 요청된 크기가 조정된 후, 할당기는 가용 리스트에서 적절한 가용 블록을 검색 (라인 18).
- 적합한 블록이 있으면, 요청된 블록을 배치하고 필요에 따라 나머지 블록을 분할 (라인 19)한 후, 새로 할당된 블록의 주소를 반환.
적합한 블록이 없을 경우:
- 할당기가 적합한 블록을 찾지 못하면 힙을 확장하여 새로운 가용 블록을 생성 (라인 24–26).
- 요청된 블록을 새로운 가용 블록에 배치하고 필요에 따라 블록을 분할 (라인 27)한 후, 새로 할당된 블록에 대한 포인터를 반환.

[find_fit] 묵시적 가용 리스트에서 first fit 검색 수행

static void *find_fit(size_t asize)
{
	/* First-fit search */
	void *bp;

	for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
            return bp;
        }
	}
	return NULL; // No fit
}

[place] 요청한 블록을 가용 블록의 시작 부분에 배치하기 (나머지 부분의 크기가 최소 블록 크기 이상일 때만 분할)

static void place(void *bp, size_t asize)
{
	size_t csize = GET_SIZE(HDRP(bp));

	if ((csize - asize) >= (2*DSIZE)) {
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(csize-asize, 0));
        PUT(FTRP(bp), PACK(csize-asize, 0));
    }
	else {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
	}
}

최소 블록 크기: 이 할당기의 최소 블록 크기는 16바이트
블록 분할 조건: 분할 후 남은 블록 크기가 최소 블록 크기(16바이트) 이상이면 블록을 분할 (라인 6–10)
주의 사항: 새로 할당된 블록을 먼저 배치한 후 (라인 6과 7) 다음 블록으로 이동해야 함 (라인 8)

CSAPP 교재의 코드로 mm.c를 작성해서 mdriver 프로그램을 실행할 경우 57점을 받는다.
더 높은 점수를 받으려면 아래에 나오는 명시적 가용 리스트, 분리 가용 리스트나 버디 시스템을 사용해야 한다.

9.9.13 명시적 가용 리스트

묵시적 가용 리스트는 기본 할당기 개념을 도입하는 간단한 방법을 제공하지만, (비록 힙 블록 수가 미리 작다고 알려진 특수 목적의 할당기에는 괜찮을 수 있어도) 블록 할당 시간이 힙 블록의 총 수에 비례하여 선형이기 때문에 일반 목적의 할당기에는 적합하지 않다. 더 좋은 방법은 가용 블록들을 일종의 명시적 자료구조로 구성하는 것이다.

명시적 데이터 구조:
- 가용 블록을 명시적 데이터 구조의 형태로 구성하는 것이 더 나은 접근 방식.
- 가용 블록의 본문(body)은 프로그램에서 필요하지 않으므로, 데이터 구조를 구현하는 포인터를 가용 블록의 본문에 저장할 수 있다.
- 예를 들어, 각 가용 블록에 pred(선임자) 및 succ(후임자) 포인터를 포함시켜 힙을 이중 연결 가용 리스트로 구성할 수 있다.
이중 연결 리스트의 장점:
- 이중 연결 리스트를 사용하면 첫 번째 적합 할당 시간이 총 블록 수에 비례하여 선형에서 가용 블록 수에 비례하여 선형으로 줄어든다.
- 그러나 블록 해제 시간은 선택한 가용 리스트의 블록 정렬 정책에 따라 선형 또는 상수 시간이 될 수 있다.
- 한 가지 방법은 새로 해제된 블록을 리스트의 시작 부분에 삽입하여 후입 선출(LIFO) 순서를 유지하는 것이다.
  이 경우, 해제된 블록을 상수 시간에 수행할 수 있다.
- 경계 태그를 사용하면 코알레싱도 상수 시간에 수행할 수 있다.
주소 순서 유지:
- 또 다른 방법은 주소 순서로 리스트를 유지하는 것으로, 리스트의 각 블록 주소가 그 후속 블록의 주소보다 작도록 하는 것이다.
- 이 경우, 블록을 해제하려면 적절한 선행 블록을 찾기 위해 선형 검색이 필요하다.
- 주소 순서의 첫 번째 적합 방식은 후입 선출 방식보다 더 나은 메모리 활용을 제공하며, Best fit에 가까워진다.
명시적 리스트의 단점:
- 일반적으로, 가용 블록은 필요한 모든 포인터와 헤더 및 풋터를 포함할 수 있을 만큼 충분히 커야 한다.
- 이로 인해 최소 블록 크기가 커지고 내부 단편화의 가능성이 증가한다.

9.9.14 분리 가용 리스트Segregated Free Lists

🔹 크기 별로 여러 개의 free list 관리 (ex. 1~2B, 3~4B, ..., 2K~4K)
🔹 작은 블록은 빠르게 찾고, 큰 블록은 메모리 효율성 ↑
🔸 검색 영역 축소로 할당 속도 향상
🔸 Simple Segregated Storage: 같은 크기의 블록만 포함, split/coalesce 없음
🔸 Segregated Fits: 다양한 크기의 블록 포함, split/coalesce 지원. 실무에서 많이 사용됨 (ex: GNU malloc)

단일 연결 리스트를 사용하는 할당기는 블록 할당에 필요한 시간이 가용 블록 수에 비례해 선형적이다. 할당 시간을 줄이기 위한 대표적인 접근 방식인 분리 저장장치segregated storage는 여러 개의 가용 리스트를 유지하는 것이다. 각 리스트는 대략 같은 크기의 블록을 보유한다.

분리 저장장치 개념:
- 모든 가능한 블록 크기를 동등 클래스인 크기 클래스size class로 분할
- 2의 제곱으로 분할: {1}, {2}, {3, 4}, {5–8}, ... , {1,025–2,048}, {2,049–4,096}, {4,097–∞}
- 작은 블록과 큰 블록 분리: {1}, {2}, {3}, ... , {1,023}, {1,024}, {1,025–2,048}, {2,049–4,096}, {4,097–∞}
할당기 구조:
- 할당기는 크기 클래스당 하나의 가용 리스트를 가진 배열을 유지하며, 크기별로 정렬된다.
- 크기 n의 블록이 필요할 때 적절한 가용 리스트를 검색한다.
- 적합한 블록을 찾지 못하면 다음 리스트를 검색하는 방식으로 진행된다.
분리 저장장치 변형:
- 동적 메모리 할당 문헌은 크기 클래스를 정의하는 방식, 코알레싱 수행 시점, 운영 체제로부터 추가 힙 메모리를 요청하는 시점, 분할 허용 여부 등에 따라 여러 가지 변형된 분리 저장장치을 설명한다.
기본 접근 방식:
- 간단한 분리 저장장치
- 분리 맞춤segregated fits

간단한 분리 저장장치

분리 저장장치에서는 각 크기 클래스의 가용 리스트가 동일한 크기의 블록으로 구성되며, 각 블록은 크기 클래스의 최대 요소 크기와 같다. 예를 들어, 크기 클래스가 {17–32}로 정의되면, 해당 클래스의 가용 리스트는 모두 크기 32의 블록으로만 구성된다.

블록 할당 과정
- 주어진 크기의 블록을 할당할 때, 적절한 가용 리스트를 확인한다.
- 리스트가 비어 있지 않으면, 첫 번째 블록을 전체 할당한다.
- 가용 블록은 요청을 만족시키기 위해 결코 분할되지 않는다.
- 리스트가 비어 있으면, 할당기는 운영 체제에 고정 크기의 추가 메모리를 요청하고(일반적으로 페이지 크기의 배수), 이 청크를 동일한 크기의 블록으로 나누어 새로운 가용 리스트를 형성한다.
블록 해제 과정
- 블록을 해제할 때, 할당기는 해당 가용 리스트의 앞쪽에 블록을 삽입한다.
장점
- 블록 할당 및 해제가 모두 빠른 상수 시간 작업이다.
- 동일한 크기 블록, 분할 없음, 병합 없음의 조합 덕분에 블록당 메모리 오버헤드가 거의 없다.
- 각 청크가 동일한 크기 블록만 포함하므로, 할당된 블록의 크기를 주소로 추론할 수 있다.
- 병합이 없기 때문에 할당된 블록은 헤더에 할당/해제 플래그가 필요하지 않다. 따라서 할당된 블록에는 헤더가 필요 없고, 풋터도 필요 없다.
- 할당 및 해제 작업이 가용 리스트의 앞부분에서 블록을 삽입하고 삭제하므로, 리스트는 단일 연결 리스트로만 유지하면 된다.
- 결국, 각 가용 블록에서 필요한 필드는 하나의 succ 포인터뿐이며, 최소 블록 크기는 단 하나의 워드로 충분하다.
단점
- 분리 저장장치는 내부 단편화와 외부 단편화에 취약하다.
- 내부 단편화는 가용 블록이 결코 분할되지 않기 때문에 발생할 수 있다.
- 특정 참조 패턴으로 인해 가용 블록이 결코 병합되지 않기 때문에 극심한 외부 단편화가 발생할 수 있다.

간단한 분리 저장소 기반의 할당기에서 심각한 외부 단편화를 초래하는 참조 패턴을 설명하시오.

정답 : 응용프로그램이 첫 번째 크기 클래스에 대해 많은 할당 및 해제 요청을 한 후, 두 번째 크기 클래스에 대해 많은 할당 및 해제 요청을 하고, 그 다음에 세 번째 크기 클래스에 대해 많은 할당 및 해제 요청을 하는 방식이다. 각 크기 클래스에 대해 할당기는 많은 메모리를 생성하지만, 이 메모리는 회수되지 않는다. 이는 할당기가 메모리를 병합하지 않기 때문이며, 응용프로그램이 다시 해당 크기 클래스의 블록을 요청하지 않기 때문이다.

분리 맞춤

이 접근 방식에서는 할당기가 가용 리스트의 배열을 유지한다. 각 가용 리스트는 크기size 클래스와 연결되어 있으며, 어떤 형태의 명시적 또는 묵시적 리스트로 구성된다. 각 리스트는 크기 클래스에 속하는 다양한 크기의 블록을 포함한다. 여러 가지 변형이 있는 분리 맞춤 할당기가 존재하지만, 여기서는 간단한 버전을 설명한다.

블록 할당 과정
- 요청의 크기 클래스를 결정하고, 적절한 가용 리스트에서 첫 번째 적합 블록을 검색한다.
- 적합한 블록을 찾으면, 선택적으로 분할하고 나머지를 적절한 가용 리스트에 삽입한다.
- 적합한 블록을 찾지 못하면, 다음 큰 크기 클래스를 검색한다. 이 과정을 적합한 블록을 찾을 때까지 반복한다.
- 모든 가용 리스트에서 적합한 블록을 찾지 못하면, 운영 체제에 추가 힙 메모리를 요청하고, 이 새로운 힙 메모리에서 블록을 할당한 후 나머지를 적절한 크기 클래스에 배치한다.
블록 해제 과정
- 블록을 해제할 때, 블록을 연결하고 결과를 적절한 가용 리스트에 삽입한다.
장점
- 분리 맞춤 방식은 생산 품질의 할당기에서 인기 있는 선택으로, GNU malloc 패키지와 같은 C 표준 라이브러리에서 제공된다.
- 빠르고 메모리 효율적이다.
- 검색 시간이 단축되며, 전체 힙 대신 특정 부분에서 검색이 이루어진다.
- 메모리 활용도가 개선될 수 있으며, 간단한 first fit 검색이 전체 힙의 best fit 검색에 근접한다.

버디 시스템

버디 시스템은 분리 맞춤의 특수한 경우로, 각 크기 클래스가 2의 거듭제곱으로 구성된다. 기본 아이디어는 2ᵐ 워드 크기의 힙에서 2ᵏ 크기 블록에 대해 각각 별도의 가용 리스트를 유지하는 것이다. 요청된 블록 크기는 가장 가까운 2의 거듭제곱으로 올림하며, 처음에는 2ᵐ 워드 크기의 가용 블록이 하나 있다.

블록 할당 과정
- 크기 2ᵏ의 블록을 할당하려면, k ≤ j ≤ m인 첫 번째 사용 가능한 블록 크기 2ʲ를 찾는다.
- 만약 j = k이면 할당이 완료된다.
- 그렇지 않으면, 블록을 반으로 재귀적으로 분할하여 j = k가 될 때까지 진행한다.
- 분할 과정에서 남은 반쪽(버디)은 적절한 가용 리스트에 배치된다.
블록 해제 과정
- 크기 2ᵏ의 블록을 해제할 때, 가용 버디와 연결을 계속 진행한다.
- 할당된 버디를 만나면 병합을 중단한다.
버디 시스템의 특징
- 주어진 블록의 주소와 크기를 알면, 그 버디의 주소를 쉽게 계산할 수 있다.
- 예를 들어, 크기 32바이트의 블록 주소가 xxx ...x00000일 경우, 버디의 주소는 xxx ...x10000이다.
- 즉, 블록과 그 버디의 주소는 정확히 하나의 비트 위치에서 다르다.
장점
- 버디 시스템 할당기의 주요 장점은 빠른 검색 및 연결이다.
단점
- 블록 크기에 대한 2의 거듭제곱 요구 사항으로 인해 상당한 내부 단편화가 발생할 수 있다.
- 이로 인해 버디 시스템 할당기는 일반 목적의 작업에는 적합하지 않다.
- 그러나 블록 크기가 미리 2의 거듭제곱으로 알려진 특정 응용프로그램에 대해서는 잘 맞을 수 있다.

'Krafton Jungle > 4. CSAPP' 카테고리의 다른 글

[Computer System] ⑪ 네트워크 프로그래밍 (2) (0)	2025.05.02
[Computer System] ⑪ 네트워크 프로그래밍 (1) (0)	2025.05.01
[Computer System] ⑨ 가상메모리 (1) (0)	2025.04.22
[Computer System] ⑧ 예외적인 제어흐름 (0)	2025.04.19
[Computer System] ⑦ 링커 (0)	2025.04.19

현재글[Computer System] ⑨ 가상메모리 (2)

MUNSIK BLOG

munsik22 님의 블로그 입니다.

백준, 나만무, 정보처리기사, csapp, C++, NextJS, 크래프톤정글, 레드블랙트리, 합격후기, C, springboot, webproxy, 프로그래머스, 오답노트, pintos, malloc, 문식이,

Today :
Yesterday :

[Munsik] MUNSIK BLOG [Munsik]