3. 프로그램의 기계수준 표현

3-8. 배열의 할당과 접근

3-8-1. 기본 원리

C언어 에서의 배열 선언 T A[N](T는 자료형, N은 정수 길이)은 두 가지 효과를 갖는다.
1. $L·N$ 바이트($L$은 자료형T의 크기) 만큼의 공간을 하나의 블록(연속적인 메모리 공간)으로 메모리에 할당한다.
2. 식별자 A를 배열 시작 주소($x_A$) 포인터로 사용한다.
따라서 배열의 $i$번 원소(A[i])는 주소 $x_A+L·i$에 저장된다.

3-8-2. 포인터 연산

포인터 변수도 결국에는 주소 값을 가지는 변수이기 때문에 연산을 사용할 수 있다.
정수 연산과 다른 점이 있다면 $L$만큼을 1로 하여 연산한다.
즉 &A[3] - &A[2]은 $L$이 아니라 1이다.

3-8-3. 다중 배열

T A[N][M]은 $NM$바이트 만큼의 공간을 할당한다.
A[i][j]는 $x_a+L·(iM+j)$에 접근한다.
A[i]는 $x_a+L·(iM)$ 주소를 가리킨다.

3-8-4. 고정크기의 배열

C 컴파일러는 고정크기의 다차원 배열을 사용하는 코드에 대해 다양한 최적화를 수행할 수 있다.

// 고정 크기 배열
#define N 16
typedef int fix_matrix[N][N];

fix_matrix[i][j]의 주소는 $x_a+L·(iM+j)$로 구할 수 있다.
하지만 연속적인 인덱스에 접근해야 할 때 매 번 곱셈과 덧셈을 반복하는 것은 비효율적이다.
컴파일러는 이런 경우에 이전 인덱스를 기억해두었다가 $L$씩 더하는 방식으로 순회를 진행하도록 최적화한다.
특히 고정크기의 배열인 경우에는 그 크기 또한 컴파일 단계에서 확정할 수 있으므로 인덱스를 저장할 변수도 사용하지 않도록 최적화할 수도 있다.

3-8-5. 가변크기 배열

C는 이제 아래와 같은 가변크기 배열 할당을 허용한다.

int A[i][j];
int *A = (int *)malloc(sizeof(int)*i*j)

9. 가상메모리

프로세스는 직접 물리 메모리 주소에 접근하는 것이 아니라 프로세스 각각이 갖는 가상 주소 공간을 통해서 메모리에 접근하게 된다.
단순히 부족한 메모리 공간을 확장하기 위한 수단을 넘어 효율적인 메모리 관리, 멀티태스킹, 메모리 보호, 프로세스 격리 등 다양한 기능을 한다.
따라서 가상메모리를 이해하는 것은 시스템이 어떻게 동작하는지 이해하고, 프로그램의 성능을 향상시키고 에러를 피하는데 도움을 준다.

9-1. 물리 및 가상주소 방식

초기의 PC, 디지털 신호 처리 프로세서, 임베디드 컨트롤러 등은 물리 주소 방식을 사용한다.
하지만 대부분의 현대 프로세스들은 가상주소방식을 사용한다.
CPU는 가상주소지정으로 가상주소(VA)를 생성해서 메인 메모리에 접근한다.
물리 메모리에 접근하기 전에 메모리로 보내지기 전에 메모리 관리 유닛(MMU)가 적절한 물리주소로 번역한다.

9-3. 캐싱 도구로서의 VM

가상메모리는 디스크에 저장되며 1바이트 크기 배열로 구성된다.
디스크 안의 배열 정보는 메인 메모리로 캐시된다.
캐시는 블록 단위로 분할되어 디스크과 메인 메모리 사이를 잇는 역할을 하며 가상페이지라고 불린다.
물리메모리 또한 물리페이지(물리 프레임)로 분할되어 사용된다.
가상페이지는 언제나 셋 중 하나로 분류할 수 있다.

1. Unallocated: 할당되지 않은 페이지들. 데이터를 전혀 가지고 있지 않은 블록으로 디스크 공간을 차지하지 않는다.
2. Cached: 할당된 페이지 중 물리 메모리에 캐시된 페이지들.
3. Uncached: 할당된 페이지 중 물리 메모리에 캐시되지 않은 페이지들

9-3-1. DRAM 캐시의 구성

DRAM 캐시: 메인 메모리로 캐시하는 가상페이지 캐시
SRAM 캐시: L1, L2, L3 캐시 메모리로 캐시하는 메인 메모리 캐시

DRAM과 SRAM의 차이보다 디스크과 DRAM의 차이가 훨씬 더 크다.
따라서 DRAM 캐시의 미스를 줄이는 것은 중요하다.

9-3-2. 페이지 테이블

VM 시스템은 가상페이지가 DRAM 어디에 있는지, 어떤 물리 페이지를 캐싱했는지, 없다면 디스크 어디에 가상 페이지가 있고 어떤 페이지를 물리 메모리에서 제거할 것인지를 결정해야 한다.
이런 VM 시스템의 기능들은 운영체제, MMU의 주소 번역 하드웨어, 페이지테이블(가상페이지를 물리페이지로 매핑하는 자료구조. 물리메모리에 저장)의 조합으로 제공된다.

• 페이지 테이블: 페이지 테이블 엔트리(PTE)의 배열
• 페이지 테이블 엔트리: 할당 여부와 캐시된 위치(DRAM 또는 디스크) 등의 정보를 저장한다.

9-4. 메모리 관리를 위한 도구로서의 VM

VM은 메모리 관리를 단순하게 하는 목적으로도 사용된다.

1. 링킹을 단순화한다.
   프로세스들이 실제 물리 메모리 어디에 저장할지와 관계없이 동일한 기본 메모리 포맷을 사용하도록 해준다. [[#3-7-1. 런타임 스택|예시]]
2. 로딩을 단순화한다.
   리눅스 로더는 실행파일과 공유 목적파일들을 메모리에 로드하기 위해, 실제로 파일들을 읽어들이고 메모리에 적치하는 것이 아닌, 단순히 PTE가 이 파일들의 위치를 가리키게 한다.(메모리 매핑, 리눅스의 mmap)
3. 공유를 단순화한다.
   운영체제는 C프로그램에서 커널과 표준 라이브러리 코드를 각 프로세스에서 별도로 포함시키지 않고, 동일한 물리페이지들로 매핑해 한 페이지를 공유하게 한다.
4. 메모리 할당을 단순화한다.
   프로그램이 추가 힙 공간을 요구할 때, 물리 메모리에서 주소가 연속된 페이지를 찾을 필요 없이 연속적인 가상메모리 페이지를 할당하고 임의의 물리 페이지로 각각 매핑한다.

9-5. 메모리 보호를 위한 도구로서의 VM

사용자 프로세스는 읽기 전용 코드를 수정할 수 없어야 하며,
커널 코드나 데이터 역시 읽거나 수정할 수 없어야 한다.
또한 다른 프로세스의 사적 메모리에 접근할 수 없어야 한다.
VM을 통해 별도의 가상 주소공간을 제공하면 이런 분리가 쉬워진다.
PTE에 허가 비트를 추가해서 접근을 제어하는 방식이 가능해진다.

9-6. 주소의 번역

9-8. 메모리 매핑

9-9. 동적 메모리 할당

동적 메모리 할당기는 가상메모리의 힙(heap) 영역을 관리한다.
할당기는 힙을 다양한 크기의 블록들로 나누어 관리한다.
각 블록은 할당되었거나 가용한(free) 가상메모리의 연속적 묶음이다.

할당기는 크게 두 종류가 있다.

1. 명시적인 할당기
   프로그램이 명시적으로 할당된 블록을 반환(free)해 줄 것을 요구한다.
   예를 들어, C에서는 블록을 반환하기 위해 free함수를 사용한다.
2. 묵시적 할당기
   할당된 블록이 더 이상 프로그램에 의해 사용되지 않은지를 할당기가 검출하고 반환한다.
   가비지 컬렉터라고도 불리며, 사용하지 않는 블록들을 반환하는 작업을 가비지 컬렉션이라고 부른다.

9-9-1. malloc과 free함수

C 프로그램은 malloc함수를 호출해서 힙으로부터 블록들을 할당받는다.
malloc함수는 요청된 size 이상의 메모리 블록의 포인터를 리턴한다.
32비트 모드(gcc -m32)에서 항상 8의 배수인 주소를 리턴하며, 64비트 모드에서는 16의 배수인 주소를 리턴한다.(정렬 제한사항)

32비트 모드 기준으로 주소를 2진법으로 표현했을 때 마지막 세 자리가 000이라는 의미이다.

free함수는 블록의 시작 주소를 인자로 받아 블록을 반환하며, 인자가 블록의 시작 주소가 아닌 경우 아무런 동작도 하지 않는다.

9-9-2. 왜 동적 메모리 할당인가?

가장 중요한 이유는 프로그램을 실제 실행시키기 전에는 자료 구조의 크기를 알 수 없는 경우들이 있기 때문이다.

9-9-3. 할당기 요구사항과 목표

명시적 할당기에 요구되는 사항:

1. 임의의 요청 순서 처리하기
   응용프로그램은 임의의 순서로 할당/반환을 요청하기 때문에 할당기는 어떤 순서의 요청이든 대응할 수 있어야 한다.
2. 요청에 즉시 응답하기
   따라서 처리 속도를 위해 요청의 처리 순서를 바꾸거나 버퍼로 처리를 지연시킬 수 없다.
3. 힙만 사용하기
4. 블록 정렬하기
   블록들을 어떤 종류의 데이터 객체라도 저장할 수 있는 방식으로 정렬해야 한다.
5. 할당된 블록을 수정하지 않기
   가용 블록만 조작하거나 변경할 수 있으며, 할당 블록들은 수정하거나 이동시켜서는 안된다.
   따라서 할당 블록들을 압축하는 기법들은 허용되지 않는다.

성능 좋은 할당기는 처리량과 메모리 이용도를 최대화한다.

1. 처리량
   단위 시간당 완료되는 요청의 수
2. 메모리 이용도
   메모리는 유한하므로 효율적으로 이용해야 한다.
   가상 메모리라고 할지라도 프로세스들의 가상메모리의 총 합은 디스크 내의 스왑 크기를 넘을 수 없다.
   이용도를 측정할 단위 중 하나로 최고 이용도가 있다.
   할당/반환 요청을 순서대로 $R_0, \;R_1,\;...,\;R_k, \;..., \;R_{n-1}$
   라고 할 때 최고 이용도는 현재 힙의 크기 중 최고 데이터의 양의 비율로 나타낸다.
   $U_k=\frac{max_{i≤k}\;P_i}{H_k}$
   $U_k$는 요청 $R_k$가 완료된 후의 최고이용도
   $H_k$는 요청 $R_k$가 완료된 후의 힙의 크기[^1]
   $P_i$는 요청 $R_i$가 완료된 후의 데이터의 총 크기
   할당기의 목적은 $U_{n-1}$를 최대화하는 것이다.

처리량과 이용도는 서로 상충관계에 있으므로 할당기 설계에서 적절한 균형을 찾는 것이 중요하다.

[^1]: 단조 증가 가정. 힙의 최대 크기로 정의하면 단조 증가 가정을 완화할 수 있다.

9-9-4. 단편화

가용 메모리가 할당 요청을 수행할 수 없는 상황을 단편화라고 한다.
단편화는 두 가지 종류로 분류된다.

1. 내부 단편화
   여러가지 이유로 할당된 블록이 데이터 크기보다 더 큰 경우를 말한다.
   내부 단편화가 발생한 부분은 데이터를 저장하지 않음에도 할당을 위해 사용할 수 없다.
   할당기의 최소 블록 크기보다 더 작은 데이터 블록을 요청했을 때 등에 일어날 수 있다.
   할당기는 [[#9-9-1. malloc과 free함수|정렬 제한사항]]을 만족시키기 위해 데이터보다 블록 크기를 증가시킬 수 있기 때문이다.
   내부 단편화는 (할당된 블록들의 크기)-(데이터들의 크기)로 구할 수 있어 정량화가 간단하다.
   또한 내부 단편화의 크기는 이전 요청들과 할당기의 구현 방식에만 의존한다.
2. 외부 단편화
   외부 단편화는 전체 가용 공간은 할당에 충분한 크기이지만, 이 요청을 처리할 수 있는 하나의 가용 블록은 없는 경우를 말한다.
   외부 단편화가 발생하면 필요한 크기 이상의 가용 블록이 존재하지 않으므로 추가 힙 공간을 요청(힙 경계brk 확장)해야 한다.
   이전에 할당받았던 블록을 반환하는 때 등에 일어날 수 있다.
   외부 단편화는 측정하기 어려우며 미래 요청들에도 의존한다.
   예를 들어, 현재 가용 블록들이 모두 4워드[^2] 크기를 가진다고 하면 외부 단편화의 발생 여부는 미래에 4워드보다 큰 블록을 요청하는지에 따라 달라질 수 있다.

외부 단편화는 예측하기 어렵기 때문에 할당기들은 보통 가용 블록들의 크기를 크게 유지하려는 방법을 사용한다.

[^2]: 가상 메모리에서 워드는 4바이트, 더블 워드는 8바이트

9-9-5. 구현 이슈

항상 요청한 크기만큼 힙을 증가시키고 그 이전 힙 경계 주소를 반환하는 간단한 할당기를 생각해볼 수 있다.
이 할당기는 처리량은 매우 좋지만 이용도는 매우 나쁠 것이다.
처리량과 이용도 사이에 좋은 균형을 유지하는 할당기는 다음 이슈들을 고려해야 한다:

1. 가용 블록 구성: 어떻게 가용 블록들을 지속적으로 파악하는가
2. 배치: 새로 할당할 블록을 배치할 가용 블록을 어떻게 선택하는가
3. 분할: 배치 후 가용 블록의 남는 부분들을 어떻게 처리하는가
4. 연결: 막 반환된 블록으로 어떤 작업을 할 것인가(주로 인접한 가용 블록과)

아래에서는 위의 이슈들의 간단한 구현인 묵시적 가용 리스트를 중심으로 설명한다.

9-9-6. 묵시적 가용 리스트

가용 블록 구성을 구현하기 위해

1. 블록 경계를 구분하고
2. 할당된 블록과 가용 블록을 구분하기 위한 자료 구조가 필요하다.

이를 가용 리스트라고 한다. 대부분의 할당기는 이 정보를 블록 내에 저장한다.

그 중에서도 간단한 구현인 묵시적 가용 리스트는 메모리 블록을 데이터, 패딩에 덧붙여 1워드 길이의 헤더를 포함한다.
헤더는 블록의 크기(헤더와 패딩을 포함한 전체 블록)와 가용 여부에 대한 정보 등을 담게된다.

헤더의 한 가지 간단한 예로 위와 같은 구조를 생각할 수 있다.
32비트 모드를 가정할 때 블록의 크기는 최대 1워드이다.
그러나 정렬 제한사항을 고려하면 할당기는 블록의 크기를 8의 배수로 유지[^3]하므로 블록 크기(2진법)의 하위 3비트는 항상 0이다.
그러므로 하위 3비트는 다른 정보를 위해 사용한다.
이 예시에서는 하위 1비트에 할당/가용 여부를 표시하는 비트로 사용하였다.

[^3]: 데이터를 보관하는 payload의 시작 주소는 8의 배수여야 한다. 헤더의 크기가 4바이트임을 감안하면, 헤더를 포함한 블록의 시작주소(=이전 블록의 끝 주소)는 8n-4여야 한다. 따라서 할당기는 블록의 크기가 8의 배수가 되도록 패딩한다.

가용 리스트도 이름처럼 추상적 자료형인 리스트의 일종이다.
묵시적 가용 리스트는 리스트를 구현하는데 있어 배열이나 연결리스트와 다르게 블록 자신의 크기와 가용 부를 표시함으로써 다음 가용 블록의 위치를 묵시적으로 알린다.

최소 블록 크기는 시스템의 정렬 요구사항과 할당기의 블록 포맷 선택에 의존한다.
예시: 정렬 요구사항을 더블 워드(8바이트), 블록 포맷을 묵시적 가용 리스트라고 하면 최소 블록 크기는 데이터 4바이트, 헤더 1바이트, 패딩 3바이트로 8바이트가 된다.

9-9-7. 할당한 블록의 배치

할당기가 요청받은 블록을 저장하기 위해 가용 블록을 검색하는 방법을 배치 정책이라고 한다.

• First Fit: 가용 리스트를 처음부터 검색해서 크기가 맞는 첫 번째 가용 블록을 선택
  + 장점: 큰 가용 블록을 뒷쪽에 두는 경향이 있어 자연스레 작은 가용 블록을 선택할 가능성이 높아진다. (이용도)
  + 단점: 작은 가용 블록이 앞쪽에 있으므로 검색 횟수가 늘어난다. (처리량)
• Next Fit: 리스트의 처음이 아닌 이전 검색 종료 지점에서 검색을 시작
  - 장점: 이전 검색 지점 이후에서 조건에 맞는 블록을 선택할 가능성이 높아 First Fit에 비해 빠르다. (처리량)
  - 단점: 메모리 이용도가 First Fit보다 낮아질 수 있다. (이용도)
• Best Fit: 모든 가용 블록을 검색해 크기가 맞는 가장 작은 가용 블록을 선택
  - 장점: 메모리 이용도가 좋다. (이용도)
  - 단점: 묵시적 가용 리스트에서는 힙의 모든 블록(가용/할당 블록 모두)을 검색해야 한다. (처리량)

아래에서는 할당 블록까지 검색하지 않을 수 있도록 단순화한 best-fit 정책인 분리 가용 리스트 조직 segregated free list organizations에 대해서 설명한다.

9-9-8. 가용 블록의 분할

할당기가 블록을 배치할 가용 블록을 찾은 후에는 가용 블록의 어느 정도를 할당할 것인지 결정해야 한다.

1. 충분히 작은(good fit) 가용 블록을 선택한 경우
   가용 블록 전체를 사용할 수 있다.
   내부 단편화가 생기지만 수용할 수 있다.
2. 크기가 큰 경우(fit is not good)
   가용 블록을 나누어 할당한다.
   전체를 할당하는 경우 내부 단편화가 생긴다.

9-9-9. 추가적인 힙 메모리 획득하기

배치할 블록을 찾을 수 없다면, 우선 인접한 가용블록들을 합쳐서(연결) 더 큰 가용 블록들을 만들어 본다.
이미 모두 연결돼있거나 충분히 큰 블록이 만들어지지 않으면 sork함수를 호출해서 추가적인 힙 메모리를 요청한다.

9-9-10. 가용 블록 연결하기

블록을 반환했을 때, 인접한 가용 블록이 있다면 하나의 연결된 가용블록으로 볼 수 있다.
하지만 실제로는 가용블록이 나누어져 있어 배치에 실패하는 경우가 생길 수 있고 이를 가성 단편화(false fragmetation)라고 한다.

가성 단편화를 극복하기 위해 할당기는 가용블록들을 합칠 수 있다(연결 coalescing).

• 즉시 연결
  블록이 반환될 때마다 인접 가용 블록들을 연결
• 지연 연결
  반환 후 적절한 때에 가용 블록들을 연결
  예시: 할당 요청이 실패하는 경우 모든 가용블록들을 검색하여 연결

즉시 연결은 간단하며 상수 시간($O(1)$)에 수행할 수 있는 장점이 있지만
할당-반환을 반복하는 프로그램에서는 연결과 분할을 반복하는 등 일부 요청 패턴에서 쓰래싱이 발생할 수 있다.
빠른 할당기들은 지연 연결을 주로 사용하지만 아래에서는 설명을 위해 즉시 연결을 가정한다.

9-9-11. 경계 태그로 연결하기

반환하는 블록(현재 블록)의 다음 블록이 가용 블록인지 확인하려면 헤더에서 블록 크기만큼 이동하면 된다.
하지만 이전 블록이 가용 블록인지 확인하기 위해서는 헤더만 있는 묵시적 가용 리스트라면 처음부터 블록들을 검색해보는 방법밖에 없다.[^4]

이를 위해 경계 태그라는 기법이 등장하였다.
경계 태그는 헤더와 동일한 내용을 블록 끝에 풋터로 추가하는 것으로, 블록 앞 1워드만을 읽어 이전 블록이 가용 블록인지 확인할 수 있다.
다만 각 블록마다 헤더와 풋터를 유지해야 하므로 메모리 오버헤드가 심해진다.
풋터는 이전 블록이 가용 블록일 경우 크기를 알려주는 목적으로 사용되므로, 이전 블록이 가용 블록인지 여부를 헤더에 저장하고, 가용 블록이 아닌 경우(할당 블록인 경우)에는 풋터를 사용하지 않는 방식으로 최적화할 수 있다.

[^4]: 이전으로 워드 크기씩 헤더를 찾아가는 방법을 떠올릴 수 있지만, 헤더를 통해 블록 크기만큼 이동하는 컨텍스트가 없다면 헤더를 찾더라도 헤더인지 데이터인지를 판단할 수 없다.

9-9-12. 종합 설계: 간단한 할당기의 구현

9-9-13. 명시적 가용 리스트

지금까지 묵시적 가용 리스트를 통해 할당기의 개념을 소개하였다.
그러나 묵시적 가용 리스트는 블록 할당 시간이 전체 힙 블록의 수에 비례하기 때문에[^5] 범용 할당기에 적합하지 않다.
보통 명시적 자료구조로 가용 리스트를 만드는 것이 좋은 방법이다.

가용 블록은 프로그램에서 사용하지 않기 때문에 가용 블록의 리스트를 구현하기 위해 가용 블록 내의 공간을 사용할 수 있다.
그림은 명시적 가용 리스트의 간단한 예시로, 가용 블록 안에 이전/다음 가용 블록의 주소를 저장해 이중 연결 리스트로 구성했다.
명시적 가용 리스트를 사용하면

• 장점: first fit 할당 시간을 전체 힙 블록 수에 비례했던 것에서 가용 블록의 수에 비례하는 것^6으로 줄일 수 있다.
• 단점: 최소 블록 크기가 커지므로 내부 단편화 가능성이 높아진다. 가용 블록들이 포인터, 헤더, 풋터를 저장할 수 있을만큼 커져야 하므로 그 보다 작은 공간은 패딩에 포함시키기 때문이다.

다만 first fit 배치 정책을 사용할 때의 반환 시간과 이용도는 블록 정렬 정책에 의해 달라진다.

1. 후입선출로 정렬하기
   이중 리스트를 스택처럼 후입선출 식으로 유지한다.
   즉, 새롭게 반환되는 블록을 리스트의 시작 부분에 삽입한다.
   first fit 배치 정책을 같이 사용하면, 최근에 반환된 블록 순으로 검색하게 된다.
   반환이 상수 시간에 수행되며 [[#9-9-10. 가용 블록 연결하기|연결]]도 상수 시간에 수행할 수 있다.
2. 주소 순으로 정렬하기
   이중 리스트를 가장 가까운 가용 블록의 주소를 가리키도록 구성한다.
   반환을 위해서는 반환 위치를 우선 탐색해야 하므로 반환시간이 가용 블록에 비례한다.
   대신 first fit 배치 정책에서 후입선출로 정렬한 경우보다 더 좋은 메모리 이용도를 가진다.[^7]

[^5]: 가용 블록의 수를 N, 할당 블록의 수를 M이라고 한다면 묵시적 가용 리스트의 블록 할당 시간은 $O(N+M)$이다.

[^7]: [[#9-9-7. 할당한 블록의 배치]]에서 알 수 있듯 first fit의 장점은 뒷 부분에 크기가 큰 가용 블록이 배치된다는 점에서 발생한다. 후입 선출로 정렬하였을 때에는 크기와 관계 없이 반환된 순으로 정렬되므로 이런 장점이 사라진다.

9-9-14. 분리 가용 리스트

앞서 알아본 모든 가용 블록들을 하나의 연결 리스트로 사용하는 방법을 단일 연결 가용 블록 리스트라고 한다.
이는 할당 시간이 비례^6하므로 할당 시간을 줄이기 위해 분리 저장장치 segregated storage를 사용하는 경우가 많다.
분리 저장장치 방식은 가용 리스트를 비슷한 크기(크기 클래스size class) 별로 여러 개로 나누어 사용한다.
크기 클래스를 나누는 방식 예시로는 2의 제곱 단위로 나누는 방법

또는 더 세분하여 크기가 작은 블록들은 각자의 크기 클래스에, 큰 블록들은 2의 제곱으로 나누는 방법
$\{1\},\;\{2\},\;\{3\},\;...\;,,\;\{1023\},\;\{1024\},\;\{1025-2048\},\;\{2049-4096\},\;\{4097-∞\}$
등이 있다.
각 크기 클래스마다 크기 순으로 정렬된 가용 리스트를 가지게 된다.

9-9-14-1. 간단한 분리 저장장치

분리 저장장치의 예시로 간단한 분리 저장장치를 들 수 있다.
각 크기 클래스의 가용 블록 크기는 모두 클래스의 최대 크기이다.
예를 들어 2의 제곱으로 클래스를 구분하면 가용 블록은 1, 2, 4, 8, 16...의 크기만을 갖는다.

• 할당: 적절한 가용 리스트를 찾아 블록을 분할하지 않고 전체를 할당한다.
  리스트가 비어있으면 (다음 크기를 검색하는 것이 아니라)힙 공간을 추가로 요구해 해당 클래스 만큼의 블록으로 분할해 리스트를 채워넣는다.
• 반환: 해당 크기 가용 리스트의 맨 앞에 채워넣는다.
• 장점
  - 할당과 반환이 상수시간에 이루어진다.
  - 리스트 마다 블록들의 사이즈가 같아 분할/연결이 필요 없기 때문에 오버헤드가 거의 없다.
  - 메모리 블록이 동일한 크기로 나눠져 있으므로 블록의 주소만 알면 크기를 알 수 있다.
  - 연결이 없으므로 헤더, 풋터가 필요하지 않다.
  - 할당과 반환이 모두 리스트의 헤드에만 삽입하므로 이중 연결 리스트가 필요 없다.
  - 블록 내에 필요한 정보는 후임자를 가리키는 포인터 뿐이므로 최소 블록 크기가 1워드이다.
• 단점
  - 블록을 분할하지 않으므로 내부 단편화에 취약하다.
  - 극단적인 외부 단편화가 발생할 가능성이 있다.[^8]

[^8]: 할당과 반환을 반복하는 프로그램이 요청하는 블록의 크기를 점점 키워가는 경우, 작은 크기 클래스의 블록들은 가용상태로 남아있으나 연결되지 않으므로 사용할 수 없다. 즉, 외부 단편화가 유발된다.

9-9-14-2. 분리 맞춤 Segregated Fits

분리 맞춤은 리스트들이 다양한 크기의 블록을 가질 수 있다.
분리 맞춤 방식의 분리 저장장치는 묵시적 가용 리스트에도 적용될 수 있다.
다음은 분리 맞춤의 간단한 예시이다.

• 할당: 크기에 맞는 가용 리스트를 first-fit 방식으로 검색한다.
  찾을 수 없으면 다음 크기의 가용 리스트를 검색한다.
  블록을 찾으면 블록을 분할하고 나머지를 크기에 맞는 가용 리스트에 넣는다.
  적절한 크기의 가용 블록이 없으면 추가 힙 공간을 요청한다.
• 반환: 블록을 연결하고 연결된 블록을 해당 크기의 가용 리스트에 넣는다.
• 장점
  - 힙의 특정 부분(해당 크기 클래스)만 검색하므로 검색 시간이 줄어든다. (처리량)
  - 분리 가용 리스트에서 first-fit 검색 방식은 best-fit 검색 방식과 유사하므로 이용도가 개선된다. (이용도)

9-9-14-3. 버디 시스템

버디 시스템은 크기 클래스가 2의 제곱인 경우에 사용할 수 있는 분리 맞춤(segregated fits) 방식이다.

• 할당: 해당 크기 클래스의 리스트에서 가용 블록을 찾아 할당한다. 만약 비어있다면 더 큰 클래스에서 찾아 해당 크기가 될 때까지 이분할한다. 분할할 때마다 나머지 절반(버디 buddy)을 해당 가용 리스트에 넣는다. 최초의 블록의 크기는 힙 공간 전체일 것이다.
• 반환: 할당과 반대로, 반환할 블록과 버디들을 할당된 버디를 만날 때까지 연결한다. 버디는 현재 블록의 크기만큼을 주소에 더해 찾을 수 있다.
• 장점
  - 빠른 검색과 연결
• 단점
  - 블록 크기가 2의 제곱으로 고정되어 있으므로 내부 단편화에 취약하다.
  그러므로 어떤 프로그램의 블록 크기가 2의 제곱으로 고정되어 있을 때 사용하면 효과를 얻을 수 있다.