public string DevelopmentDiary(Knowledge knowledge) {
	if (knowledge != null) {
		return "level up"
    } else {
    	return "level down"
    }
}

9.8까지 읽으려고 했는데,
CS책에서 동적 메모리 할당이 어렵다는 걸 보란듯이 강조하고 있어서
이 역시 7주차 전부터 집필하게 됐다.

CS

Bryant, R. E., & O’Hallaron, D. R. (2023). Computer systems: A programmer’s perspective (3rd ed.). Pearson.

9) 동적 메모리 할당

힙 영역

• 동적 메모리 할당기는 프로세스의 가상 메모리 중 힙 영역을 관리함. 힙은 초기화되지 않은 데이터 영역(.bss) 바로 뒤에서 시작하여 높은 주소 방향으로 성장함. 각 프로세스마다 커널이 관리하는 'brk'포인터가 힙의 최상단을 가리킴. 할당기는 힙을 다양한 크기의 블록 집합으로 관리하며, 각 블록은 할당 또는 미할당 상태임. 할당된 블록은 애플리케이션이 사용 중이고 미할당 블록은 재할당 가능함.

할당기의 종류

• 명시적 할당기: 프로그래머가 malloc/free를 호출해 블록을 할당하고 해제함. C표준 라이브러리의 malloc 패키지가 대표적임.
• 암시적 할당기(Implicity Allocator, Garbage Collector) 프로그래머가 할당만 하면, 사용하지 않는 블록을 할당기가 자동으로 감지해 해제함.

9-1) malloc과 free 함수

malloc 함수

• 정의: void* malloc(size_t size) - 최소 'size' 바이트의 메모리를 할당하고, 그 시작 주소를 반환함.
• 정렬: 반환되는 포인터는 어떤 데이터 타입이든 저장할 수 있도록 적절히 정렬돼 있음.
  • 32비트 모드: 항상 8의 배수 주소 반환
  • 64비트 모드: 항상 16의 배수 주소 반환
• 오류처리: 할당에 실패하면 'NULL'을 반환하고 'errno'를 설정함.
• 초기화: 'malloc'은 반환된 메모리를 초기화하지 않음. 초기화된 메모리는 'calloc'을 사용
• 크기 변경: 동적 메모리 할당기는 내부적으로 'sbrk'또는 mmap'을 이용해서 커널에서 힙을 확장

sbrk 함수

• 정의: void* sbrk(intptr_t incr)' - 힙의 크기를 'incr' 바이트 만큼 늘리거나 줄임
• 반환값: 성공 시 이전 brk 포인터를 반환, 실패 시 -1 반환

free 함수

• 정의: void free(void* ptr)
• malloc, calloc, realloc으로 할당한 블록의 시작 주소를 받아 해당 블록을 해제함.
• 인자가 올바른 블록의 시작 주소가 아니면 동작이 정의되지 않음.
• 반환값이 없으므로 잘못된 해제는 런타임 오류로 이어질 수 있음.

그림 예시
다음 그림은 한 워드(한 칸)가 4바이트인 메모리 블록이다.

이 블록으로 5가지 과정을 살펴볼 것이다.
(1) p1 = malloc(4*sizeof(int))
(2) p2 = malloc(5*sizeof(int))
(3) p3 = malloc(6*sizeof(int))
(4) free(p2)
(5) p4 = malloc(2*sizeof(int))

x는 할당됐다는 의미이며
진한 표시는 여기까지 할당됐다는 의미이고
o는 0으로 할당(패딩)됐다는 의미이다.

(1) p1 = malloc(4*sizeof(int))

p1
x	x	x	X

(2) p2 = malloc(5*sizeof(int))

p1				p2
x	x	x	X	x	x	x	x	x	O

5워드(20바이트)를 할당하려 했지만 32비트에서는 8의 배수 바이트만큼 할당된다.
따라서 6워드(24바이트)만큼 할당됐다.

이를 정렬 요구사항이라고 한다.

나머지는 패딩처리

(3) p3 = malloc(6*sizeof(int))

p1				p2						p3
x	x	x	X	x	x	x	x	x	O	x	x	x	x	x	X

(4) free(p2)

p1				p2						p3
x	x	x	X							x	x	x	x	x	X

메모리 할당은 해제됐지만 포인터 p2는 여전히 같은 블록을 가리키고 있다.

(5) p4 = malloc(2*sizeof(int))

p1				p2/p4						p3
x	x	x	X	x	X					x	x	x	x	x	X

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

동적 메모리 할당이 필요한 이유 중 가장 중요한 이유는 프로그램은 실행되기 전에는 특정 데이터 구조의 크기를 알 수 없는 경우가 많기 때문이다.

정적 할당의 한계

• 정적 메모리 할당(static allocation)은 프로그램이 실행되기 전에 데이터 크기가 확정되어 있어야 함.
• 만약 크기가 바뀌면, 프로그램의 소스 코드를 수정하고 다시 컴파일해야 하며, 유지보수와 확장성 측면에서 비효율적임.

동적 할당의 장점

• 동적 메모리 할당(dynamic allocation)을 사용하면 데이터 구조의 크기를 런타임에 결정할 수 있음.
• 입력받은 n의 값에 따라 배열을 동적으로 할당할 수 있음.

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

동적 메모리 할당기가 만족해야하는 엄격한 제약 조건

• 임의의 요청 순서 처리
  할당기에는 할당과 해제 요청이 어떤 순서로 들어올지에 대한 가정이 없음. 즉, 사용자는 언제든지 할당/해제 요청을 할 수 있으며, 할당기는 각 요청이 유요한지(해제 요청이 실제 할당된 블록에 대해서만 오는지) 정도만 보장하면 됨.
• 즉시 응답
  할당기는 각 요청에 대해 즉시 반응해야 하며, 요청을 지연시키거나 순서를 바꿔 처리할 수 없음. 요청을 버퍼링하거나 최적화를 위해 미루는 것은 허용되지 않음.
• 힙만 사용
  할당기의 내부 데이터 구조는 반드시 힙 영역에 저장해야 하며, 전역 변수나 정적 배열 등은 사용할 수 없음. 단 스칼라(단일값 - 3, 'A', true) 변수는 예외적으로 허용
• 블록 정렬
  할당된 블록은 어떤 타입의 데이터도 저장할 수 있도록 정렬되어야 함. 예를 들어 64비트 시스템에서는 16바이트 정렬이 필요함
• 할당된 블록 불변
  이미 할당된 블록은 할당기가 임의로 이동시키거나 수정할 수 없음.
• 할당기의 목표
  동적 메모리 할당기는 다음 두 가지 목표 사이에서 균형을 추구해야 함.
  • 처리량 극대화
    단위 시간당 할당 및 해제 요청을 최대한 많이 처리하는 것, 속도를 높이는 것.
  • 메모리 활용률 극대화
    할당된 메모리(페이로드)의 총합이 힙 전체 크기에 대해 최대가 되도록 하는 것
    
    
  • 두 가지 목표가 상충되는 이유
    처리량을 극대화하면 메모리 활용률이 떨어질 수 있고, 반대로 활용률을 높이려면 처리량이 저하될 수 있음. 단순히 힙의 끝에서만 메모리를 할당하면 매우 빠르지만, 메모리 해제된 블록을 재사용하지 않기 때문에 비효율적으로 됨.

9-4) 단편화

동적 메모리 할당에서 메모리 활용률을 떨어뜨리는 주요 원인 중 하나. 힙에 사용되지 않는 메모리가 존재하지만 실제 할당 요청을 만족시키지 못하는 상황에서 발생.

내부 단편화

• 할당된 블록 내부에서 실제 필요한 메모리보다 더 많은 공간이 할당되어 사용하지 않는 부분이 남는 현상
  • 원인
    정렬 요구사항: 32비트 시스템에서 5바이트를 요청하면 8바이트로 할당되어 3바이트가 남음
    최소 블록 크기, 패딩, 관리 오버헤드로 인해 실제 요청보다 큰 블록이 할당됨.*
  • 특징
    내부 단편화는 주로 이전의 할당 요청 패턴에 따라 결정되며 계산이 비교적 쉬움.

* 최소 블록 크기, 패딩, 관리 오버헤드로 인해 실제 요청보다 큰 블록이 할당됨.

• 최소 블록 크기
  메모리 할당기는 너무 작은 블록을 만들지 않기 위해 최소 블록 크기를 정해둠.
  어떤 시스템에서 최소 블록 크기가 16바이트면 1바이트만 요청해도 16바이트가 할당됨.
  정렬 요구사항(정렬 조건)을 맞추고, 관리 정보(헤더, 푸터)를 저장하기 위함임

  • 정렬 요구사항
    정렬 요구사항 때문에 실제로 요청한 크기보다 더 큰 블록을 할당해야 할 때가 많음.
    정렬을 맞추기 위해 쓸모없는 공간인 '패딩'을 생성

  • 관리 오버헤드
    할당기는 각 블록의 크기, 사용 여부 등을 기록하기 위해 헤더, 푸터와 같은 관리 정보*를 블록에 저장함.
    관리 오버헤드는 사용자가 실제로 쓸 수 없는 공간임.

* 관리 정보
를 알기 전에 먼저 payload부터 알아야 한다.
 - payload: 동적 메모리 할당 시 malloc()이 반환하는 영역
 payload 앞뒤에 할당기를 위한 관리정보가 숨어 있음
 
[ 헤더 ][ payload ][ 푸터 ]

 - 헤더: 블록의 크기, 할당 여부 등 관리 정보가 저장됨
 - 푸터: 헤더와 동일한 정보 (일반적으로 '가용 블록(free block)'에서만 사용)

즉, 양쪽에서 블록 정보를 쉽게 파악할 수 있게 해줌

외부 단편화

• 힙 전체에 사용할 수 있는 메모리는 충분하지만, 연속적으로 큰 블록이 없어 할당 요청을 만족시키지 못하는 현상
  • 원인
    여러 크기의 블록이 할당되고 해제되는 과정에서 힙에 여러 개의 작은 free 블록이 흩어져 있어 큰 할당 요청이 들어오면 실패함.
  • 특징
    외부 단편화는 free 블록들이 연속적이지 않을 떄 발생하며, 실제로는 메모리가 남아있어도 할당이 불가능해짐.

예시

메모리를 4블록씩 할당한다고 할 때
다음과 같은 프로세스들이 있다고 하면

프로세스 A (1블록)
프로세스 B (2블록)
프로세스 C (4블록)
프로세스 D (8블록)

과정(괄호는 할당됐지만 빈 공간임)

1) 프로세스 A 실행

A	(A)	(A)	(A)

2) 프로세스 B 실행
프로세스 A의 빈 공간(A)이 3블록이지만 해당 메모리에 할당 불가능 (내부단편화)

A	(A)	(A)	(A)	B	B	(B)	(B)

3) 프로세스 C 실행

A	(A)	(A)	(A)	B	B	(B)	(B)	C	C	C	C

4) 프로세스 B 종료 (할당 해제)

A	(A)	(A)	(A)					C	C	C	C

5) 프로세스 D 실행
메모리에 남는 블록이 8블록이지만, 연속적인 블록이 아니므로 프로세스 D 실행 불가능(외부단편화)

A	(A)	(A)	(A)					C	C	C	C

위 관점은 프로세스의 관점에서 본 것이고, 힙의 관점에서 메모리 할당 받는 것 역시 동일하다.

9-5) 구현 이슈

할당기를 구현할 떄 가장 간단한 방법은 할당받을 때마다 시작 주소를 크게 만들어 관리하는 것이다. 다만, 블록들을 재사용하지 않기 때문에 메모리 이용도가 매우 나쁘다.

• 실용적인 할당기들이 고려해야 할 이슈

1. 가용 블록 구성: 어떤 식으로 힙 내의 free 블록들을 관리할 것인가
2. 배치: 새로 할당 요청이 들어왔을 때 어떤 가용 블록에 할당할 것인가
3. 블록 분할: 큰 free 블록에 작은 요청이 들어왔을 때, 남는 공간을 어떻게 처리할 것인가?
4. 블록 병합: free가 호출되어 블록이 해제될 때 인접한 free 블록과 병합할 것인가

9-6) 암시적 가용 리스트 (Implicit Free List)

가장 단순한 동적 메모리 할당기 구현 방식 중 하나로, 힙의 모든 블록(할당/미할당)을 한 줄로 나열하고, 각 블록의 헤더(및 푸터)에 블록의 크기와 할당 여부를 저장하여 free 블록을 '암시적'으로 관리함.

블록 구조 와 조직 방식

• 블록 포맷
  • 각 블록은 헤더(header), 페이로드(payload), 패딩(padding), 푸터(footer)로 구성됨
  • 헤더에는 블록의 크기와 할당 여부가 저장됨.
  • 푸터는 free 블록에서만 사용되며, 헤더와 동일한 정보를 저장해 블록의 뒤에서부터도 정보를 확인할 수 있게 함.
• 암시적 가용 리스트(impicit free list)
  • free 블록만 별도로 리스트로 관리하지 않고, 힙의 모든 블록을 순차적으로 탐색하며 free 블록을 찾음.
  • free 블록의 시작 위치를 따로 저장하지 않고, 헤더의 정보를 이용해 다음 블록으로 이동함.
  • free 블록을 명시적으로 연결하지 않으므로 '암시적'이라고 부름.

'X'	8/0	O	16/1	X	X	'X'	32/0	O	O	O	O	O	O	O	16/1	X	X	X	'0/1'

* 4바이트 당 1워드(1블록)
* O는 가용 블록, X는 할당된 블록
* 할당된 블록(회색)보다 더 어둡게(어두운 회색) 표현된 부분은 따옴표 표시함. (패딩 부분이라고 추측한다.)
* 더블워드(8바이트) 정렬 제한조건

그럼 이제 헤더를 좀 더 자세히 살펴보자.

위 그림에서 16/1로 할당된 블록을 들여다보면

16/1	X	X	'X'

위와 같이 표현되어 있다.
여기서 헤더를 좀 더 뜯어서 보면

16/1이라고 되어 있다. 이를 n/m이라고 할 때 n, m은 다음과 같다.
n: 사용된 바이트의 크기
m: 블록이 할당되었는지 여부 (0 - 미할당 // 1 - 할당)

n은 사용된 바이트의 크기로 더블워드 정렬 제한조건이기 때문에 항상 8의 배수를 가진다.
위 블록에서는 쉽게 표현하기 위해서 16으로 나타냈지만, 컴퓨터는 이를 이진수로 표현한다.
따라서
16은 10000이라는 이진수로 표현할 수 있다.
마찬가지로 8은 1000, 24는 11000으로 나타낸다.
여기서 알 수 있듯이 주소를 나타낼 때 하위의 3비트는 항상 사용하지 않는 공간이 된다.
따라서 이 공간에 다른 정보를 저장할 수 있고, 마지막 비트에 할당 여부에 대한 정보를 저장한다.

1. 0x00000018 | 0x1 = 0x00000019
2. 0x00000028 | 0x0 = 0x00000028
의 표현에 대한 이해

추가적인 설명을 하자면, 1은 24바이트를 갖는 할당된 블록이고, 2는 40바이트의 가용 블록이다.

우선 16진수를 2진수로 쉽게 읽는 방법에 대해서 생각해보자.
16진수에서 각 자릿수는 이진수의 네 자릿수와 같다.
무슨 말이냐면

각 자릿수에 알파벳을 붙혔을 때
0xABCDEFGH를 A:0000 B:0000 C:0000 D:0000 E:0000 F:0000 G:0000 H: 0000
이라고 생각하면 된다.

0x00000000는 0000 0000 0000 0000 0000 0000 0000 0000과 같다.
0x'8'0000000은 '1000' 0000 0000 0000 0000 0000 0000 0000이다.
0x000'8'0000은 0000 0000 0000 '1000' 0000 0000 0000 0000이며
0x0000000'9'는 0000 0000 0000 0000 0000 0000 0000 '1001'이다.

즉 0x00000018은 G 영역이 1이고, H 영역이 8이니 G: 0001, H: 1000이다.
0000 0000 0000 0000 0000 0000 0001 1000 이라는 이진수가 된다.
|는 비트연산 or이고 0x00000018 | 0x1을 하면
0000 0000 0000 0000 0000 0000 0001 1001가 된다.
즉, 하위 3비트 중 마지막 비트가 1이므로 할당된 블록이다.

마찬가지로 0x00000028은 G 영역이 2, H 영역이 8이므로 G: 0010, H: 1000이다.
0000 0000 0000 0000 0000 0000 0010 1000이라는 이진수가 된다.
0x00000028 | 0x0 = 0x00000028
즉, 0000 0000 0000 0000 0000 0000 0010 1000
마지막 비트가 0이므로 가용 블록이다.

'X'	8/0	O	16/1	X	X	'X'	32/0	O	O	O	O	O	O	O	16/1	X	X	X	'0/1'

다시 표로 돌아와서
헤더의 각 자리 n은 다음 헤더의 위치를 나타낸다고 볼 수 있다.
두 번째 칸의 헤더 8/0에서 8바이트를 4바이트(1워드)로 나누면 2이고, 2칸 뒤에는 16/1이 존재한다.
16/1에서도 16을 4로 나누면 4이고 4칸 뒤에 32/0이 있다.

힙의 시작부터 끝까지, 각 블록의 헤더(크기)를 읽어 다음 블록의 시작 위치를 계산하며 이동한다.
즉, 가용 블록은 헤더 내 필더에 의해 묵시적으로 연결이 된다.

• 장점

  • 구조가 단순하여 구현이 쉽고, 메타데이터 오버헤드가 적음(포인터 필요 없음)
  • 블록의 크기 정보만으로 힙 전체를 순회할 수 있음.

• 단점

  • free 블록을 찾기 위해 힙 전체를 순차적으로 탐색해야 함. 탐색 시간이 할당/해제 요청 수에 비례해 증가(선형 시간)
  • free 블록이 많아질수록 성능 저하가 심해짐.

추가적으로, 표 처음에 있는 'X'는 사용하지 않는 부분이다. 왜냐하면 더블워드 정렬 제한 조건 아래 payload 부분이 더블워드 부분에 정확하게 걸치게 하기 위해서이다.
(C의 포인터 역시 payload가 시작하는 부분의 주소를 반환하도록 설계돼있다.)

이해가 안된다면 그림을 보자
진한 검은색 줄은 더블워드 경계이다.
그리고 빨간색 줄(payload)의 왼쪽 끝이 항상 더블워드 경계에 걸쳐있는 것을 알 수 있다.

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

할당기가 메모리 블록을 할당할 때 free list(가용/여유 블록 목록)에서 어떤 블록을 선택할지 결정하는 정책을 placement policy(배치 정책)이라고 함.

1. First Fit(최초 적합)

• 동작 방식: free list의 시작부터 순차적으로 탐색하여 요청한 크기 이상인 첫 번째 free 블록에 할당함.
• 장점
  • 구현이 간단하고 빠름
  • 대체로 큰 free 블록이 리스트의 끝에 남게 되어, 큰 요청을 처리하기 쉬움
• 단점
  • 리스트 앞 부분에 작은 찌꺼기 free 블록이 많이 남을 수 있어, 큰 블록 탐색 시 시간이 오래 걸릴 수 있음.

2. Next Fit(다음 적합)

• 동작 방식: 이전 탐색이 끝난 지점부터 free list를 탐색하여 요청한 크기 이상인 첫 번째 free 블록에 할당함. 한 바퀴를 돌면 리스트의 처음으로 돌아감.
• 장점
  • 리스트 앞부분에 작은 블록이 많이 쌓이는 현상을 완화함.
  • first fit에 비해 탐색 시간이 줄어들 수 있음.
• 단점
  • 일부 연구에 따르면, 메모리 활용률이 first fit보다 떨어질 수 있음.

3. Best Fit(최적 적합)

• 동작 방식: free list 전체를 탐색하여, 요청한 크기 이상이면서 크기 차이가 가장 작은 free 블록에 할당함.
• 장점
  • 내부 단편화를 최소화할 수 있음
  • 일반적으로 메모리 활용률이 가장 높음
• 단점
  • free list 전체를 매번 탐색해야 하므로, 탐색 비용이 큼(느림)
  • 암시적 free list 등 단순 구조에서는 비효율적

실제 할당기에서 적용

• 단순 암시적 free list에서는 first fit이나 next fit이 주로 사용됨
• best fit은 탐색 비용이 커서, 실제로는 여러 크기별 free list(분리 리스트)와 조합해 근사적으로 구현함.

9-8) 가용 블록의 분할

할당기가 free list에서 요청 크기보다 큰 free 블록을 찾았을 때 할당하는 방법

1. 전체 사용

   • 구현이 쉽고 빠르지만, 남는 공간이 낭비되어 내부 단편화가 심해짐

2. 분할

   • 필요한 크기만큼만 할당하고 나머지 부분을 새로운 free 블록으로 나눔.
   • 내부 단편화를 줄이고 남은 공간을 이후 할당 요청에 재사용함.
   • 보통 남는 부분이 최소 블록 크기 이상일 떄만 분할함.

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

할당기가 free block을 병합해도 충분히 큰 free block이 없거나 이미 모든 free block이 최대한 합쳐진 상태라면, 즉 적당한 크기의 free block을 찾지 못했을 경우

• 할당기는 커널에 추가 힙 메모리를 요청함.
  • 시스템 콜 'sbrk'를 일반적으로 사용함.
    • 'sbrk' 함수는 힙의 크기를 지정한 바이트만큼 늘려주고, 새로 할당된 영역의 시작 주소를 반환함.
  • 할당기는 새로 얻은 메모리 영역을 하나의 큰 free block으로 만들어 free list에 추가함.
  • free list에 추가된 새로운 free block에 대해 요청된 크기만큼 할당을 진행함.

9-10) 가용 블록 연결하기(Coalescing Free Blocks)

인접한 free 블록드를 하나로 합쳐서 단편화를 줄이는 기법

coalescing이 필요한 이유

• 메모리 할당과 해제가 반복되면, 힙에는 여러 개의 작은 free 블록이 흩어지게 되고, 오류 단편화*를 유발할 수 있음.
• 이 상태에서 큰 블록을 할당하려고 하면, 전체 free 메모리의 합은 충분해도 연속된 큰 free 블록이 없어 할당에 실패함.
• coalescing은 '인접한' free 블록을 하나로 합쳐서, 더 큰 free 블록을 만들어 이러한 문제를 해결함.

* 오류 단편화(false fragmentation): 실제로 충분한 가용 메모리가 있지만, 여러 개의 작은 블록들로 나뉘어 있어서 단일 큰 블록 요청을 만족시킬 수 없는 상황

coalescing 정책

• 즉시 병합: 블록이 해제될 때마다, 인접한 free 블록이 있으면 즉시 병합함.

  • 장점: 항상 free 블록이 최대한 크게 유지되어 단편화가 줄어듦
  • 단점: 일부 패턴에서는 병합과 분할이 반복되어 오버헤드가 커질 수 있음.

  (ex. 같은 크기의 블록을 반복적으로 할당/해제할 때)

1. 초기 상태 (24바이트 = 6워드짜리 free 블록)

'X'	24/0	O	O	O	O	O	'0/1'

2. 2워드 할당

'X'	8/1	X	16/0	O	O	O	'0/1'

3. 2워드 해제

'X'	8/0	O	16/0	O	O	O	'0/1'

4. 병합

'X'	24/0	O	O	O	O	O	'0/1'

5. 2워드 할당

'X'	8/1	X	16/0	O	O	O	'0/1'

6. 2워드 해제

'X'	8/0	O	16/0	O	O	O	'0/1'

7. 병합

'X'	24/0	O	O	O	O	O	'0/1'

...

• 지연 병합: 해제 시에는 병합하지 않고, 필요할 때(할당 실패) 전체 힙을 순회하며 여러 free 블록을 한 번에 병합함.
  • 장점: 불필요한 병합을 줄여 오버헤드를 낮출 수 있음.
  • 단점: 할당 실패 시 전체 힙을 순회해야 하므로, 그 순간의 오버헤드가 큼.

1. 초기 상태 (24바이트 = 6워드짜리 free 블록)

'X'	24/0	O	O	O	O	O	'0/1'

2. A(2워드) 할당

'X'	8/1	X	16/0	O	O	O	'0/1'

3. B(2워드) 할당

'X'	8/1	X	8/1	X	8/0	O	'0/1'

4. C(2워드) 할당

'X'	8/1	X	8/1	X	8/1	X	'0/1'

5. B(2워드) 해제

'X'	8/1	X	8/0	O	8/1	X	'0/1'

6. C(2워드) 해제

'X'	8/1	X	8/0	O	8/0	O	'0/1'

7. D(4워드) 할당 (순회)

'X'	8/1	X	8/0	O	8/0	O	'0/1'

8. 병합

'X'	8/1	X	16/0	O	O	O	'0/1'

7. 재순회 및 D(4워드) 할당

'X'	8/1	X	16/1	X	X	X	'0/1'

* 병합 시 발생하는 오버헤드란?
 - 즉시 병합: 불필요한 메모리 연산이 빈번히 발생하여 성능 저하를 유발함.
 - 지연 병합: 전체 힙을 탐색하기 때문에 O(n)의 시간복잡도가 발생함. 실시간 시스템에서는 오류 초래.

9-11) 경계 태그(boundary tag)로 연결하기

동적 메모리 할당기에서 free 블록의 병합을 효율적으로 처리하기 위해 고안된 대표적인 블록 구조

• 블록의 헤더와 푸터

  • 블록별로 앞부분에는 헤더와 푸터가 위치함
    • 할당된 블록(allocated): 보통 헤더만 존재함.
    • 가용 블록(free): 헤더와 푸터 모두 존재함.
  • 헤더와 푸터에는 블록의 크기와 할당 여부가 저장됨.
  • 이 구조를 boundary tag라고 부름.

• 필요한 이유

  • free 블록이 해제될 때, 인접한 블록이 free인지 효율적으로 확인하고, 즉시 병합할 수 있음.
  • 블록의 헤더만으로는 앞쪽 블록의 상태를 알 수 없지만, 푸터를 사용하면 바로 앞 블록의 정보를 읽을 수 있음.

• 블록 병합

  • 할당기가 free를 호출하면 해당 블록의 앞/뒤 인접 블록이 free인지 헤더와 푸터로 즉시 확인 가능함.
  • 4가지 경우가 있음(앞/뒤 할당됨, 앞과 병합, 뒤와 병합, 앞/뒤와 병합)
  • boundary tag 기법을 통해 free 블록의 인접 블록 상태를 확인할 수 있기 때문에 상수 시간 O(1)에 병합이 가능함.

• 장점

  • 빠르고 효율적인 블록 병합, 외부 단편화 감소

• 단점

  • 푸터로 인해 free 블록의 오버헤드가 증가함.

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

할당기 기본 설계 / memlib.c

memlib.c에 대한 심오한 설명이 있는데, AI는 해당 내용에 대해서 요약하지 않길래 직접적으로 물어봤다.

memlib.c
실제 시스템의 메모리 할당 동작을 흉내내는 모의 라이브러리

• 동적 메모리 할당기 개발을 위한 테스트 환경 제공
  실제 운영체제의 힙 확장 시스템 콜(sbrk - /*set break*/ 등)을 직접 사용하지 않고도, 메모리 할당기의 동작을 안전하게 실험할 수 있도록 합니다.
• 메모리 힙 영역의 추상화
  내부적으로 큰 배열을 힙(heap)처럼 사용하며, 프로그래머가 원하는 만큼 힙을 확장할 수 있게 합니다. 실제 힙 확장과 유사하게 동작하지만, 시스템 자원에 영향을 주지 않습니다.

주요 변수 및 함수

• 주요 변수
  • mem_heap: 힙의 시작 주소를 가리키는 포인터
  • mem_brk: 현재 할당된 힙의 마지막 바이트 다음을 가리키는 포인터 (즉, 힙의 끝)
  • mem_max_addr: 할당 가능한 힙의 최대 주소(한계)
• 주요 함수
  • void mem_init(void):
    힙을 초기화합니다. 내부적으로 큰 배열을 할당하고, mem_heap, mem_brk, mem_max_addr를 적절히 설정합니다.
  • void *mem_sbrk(int incr):
    실제 시스템의 sbrk와 비슷한 역할을 하며, 힙을 incr 바이트 만큼 확장합니다. 확장에 성공하면 새로 할당된 영역의 시작 주소를 반환하고, 실패하면 오류를 반환합니다. 힙을 줄이는 동작(음수 incr)은 지원하지 않습니다.

기본 상수와 매크로

기본 상수

• WSIZE: 워드(word) 크기(4바이트)
• DSIZE: 더블 워드(double word) 크기(8바이트)
• CHUNKSIZE: 힙을 확장할 때 한 번에 요청하는 기본 크기(예: 4096바이트)
• MINBLOCKSIZE: 블록의 최소 크기(헤더, 푸터, 페이로드, 정렬 등을 고려)

매크로

• PACK(size, alloc): 크기와 할당 비트를 합쳐 헤더/푸터에 저장할 값을 만든다.
• GET(p): 포인터 p가 가리키는 워드의 값을 읽는다.
• PUT(p, val): 포인터 p가 가리키는 워드에 val을 쓴다.
• GET_SIZE(p): 포인터 p가 가리키는 헤더/푸터에서 블록 크기만 추출한다.
• GET_ALLOC(p): 포인터 p가 가리키는 헤더/푸터에서 할당 비트만 추출한다.
• HDRP(bp): 페이로드 포인터 bp에서 헤더의 위치를 계산한다.
• FTRP(bp): 페이로드 포인터 bp에서 푸터의 위치를 계산한다.
• NEXT_BLKP(bp): 다음 블록의 페이로드 포인터를 계산한다.
• PREV_BLKP(bp): 이전 블록의 페이로드 포인터를 계산한다.

초기 가용 리스트 만들기

1. 힙 초기화 및 프롤로그/에필로그 블록 등록
   • 할당기는 먼저 힙에 4개의 워드(16바이트 - 정렬 패딩, 프롤로그 블록, 에필로그 블록)를 할당함.

• extend_heap 함수를 통해 초기 블록 생성 및 힙 확장

2. 초기 가용 블록 생성
   • 프롤로그와 에필로그 사이에 실제로 사용할 수 있는 첫 번째 가용 블록 생성
   • 일반적으로 CHUNKSIZE(4096바이트)만큼 힙을 확장하여 하나의 큰 free block 생성
   • 이 블록의 헤더와 브터를 각각 free 상태로 초기화
3. 추가 공간 형성
   • 새로 생긴 블록의 헤더와 푸터를 free로 설정
   • 블록 끝에는 새로운 에필로그 헤더 추가
   • 필요한 경우 이전 블록과 병합 수행

블록 반환과 연결

1. 블록 반환의 기본 과정
   • 블록 반환은 'free' 함수를 통해 이루어짐.
   • 반환할 블록의 헤더와 푸터를 'free' 상태로 표시함. (헤더와 푸터의 할당 비트를 0으로 설정)
   • 반환된 블록이 인접한 가용 블록과 물리적으로 붙어 있다면, 이들을 하나의 더 큰 가용 블록을 병합함.
   • bp는 반환할 블록의 페이로드 포인터
2. 블록 연결 기법
   • 병합은 반환된 블록과 인접한 free 블록을 하나로 합치는 작업
   • 병합을 통해 외부 단편화를 줄이고 더 큰 블록 할당이 가능하도록 함.
   • boundary tag 기법을 사용하면 헤더와 푸터를 통해 상수 시간에 이전/다음 블록의 상태를 확인하고 병합함.

블록 할당

1. 요청 크기 조정

   • 사용자가 malloc으로 요청한 크기를 헤더/푸터 오버헤드와 정렬 요구 사항을 반영하여 조정함.
     (더블 워드 정렬을 맞추고, 헤더, 푸터 오버헤드를 더해 최소 블록 크기를 보장함.)

2. 적합한 가용 블록 탐색

   • 프리 리스트에서 적절한 가용 블록을 찾음

3-1. 블록 배치 및 분할

• 찾은 가용 블록이 요청 크기보다 충분히 크다면, 앞 부분에 조정된 크기의 블록을 할당하고 남은 부분이 최소 블록 크기 이상이면 새로운 free block으로 분할함.

3-2. 할당 실패시

• 적합한 free block이 없음면 힙을 확장하여 새로운 큰 free block을 만들고 다시 할당함.
• extend_heap 함수로 힙을 늘리고, 새로 생긴 free block에 대해 위 배치 과정을 반복함.

custom allocator

주요 함수 및 동작

• 힙 초기화('mm_init')
  • 힙을 초기화하고, prologue block과 epilogue block*을 설정
  • 첫 번째 free 블록을 생성
• 블록 할당('mm_malloc')
  • 정렬과 오버헤드 고려하여 실제 할당 크기 계산
  • first-fit 방식으로 적절한 free 블록 탐색
  • 적합한 free 블록이 있으면, 필요 시 splitting(분할) 후 할당
  • 적당한 free 블록이 없으면, 힙을 확장(커널에 sbrk 등으로 요청)하여 새로운 free 블록 생성 후 할당
• 블록 해제('mm_free')
  • 해당 블록의 헤더/푸터를 free로 표시
  • 인접 free 블록과 즉시 병합하여 단편화 감소
• 블록 병합('coalesce')
  • 앞/뒤 블록의 헤더/푸터를 확인해 free 상태면 하나의 큰 free 블록으로 병합
  • 네 가지 케이스(앞/뒤, 할당/해제)에 따라 처리
• 블록 탐색('find_fit')
  • 힙의 시작부터 끝까지 순차적으로 free 블록을 탐색(First-fit)
• 블록 분할('place')
  • 요청 크기보다 큰 free 블록을 할당할 때, 남는 부분이 최소 블록 크기 이상이면 splitting하여 새로운 free 블록 생성

X unused	8/1 prologue	8/1 prologue	8/1	X	16/0	O	O	O	0/1 epilogue

* boundary tag ( prologue / epilogue block )
prologue block: 힙의 시작에 8바이트(헤더+푸터)짜리의 항상 할당된 블록
 - 실제 블록을 해제할 때 이전 블록이 없는 경우를 고려할 필요가 없음

epilogue block: 힙의 끝에 0바이트(헤더)짜리의 항상 할당된 블록

• 실제 블록을 해제할 때 다음 블록이 없는 경우를 고려할 필요가 없음

이 두 가지 블록을 통해 경계 조건을 단순화시켜준다.

여기서 또 궁금했던 건 헤더는 4바이트인데 왜 0바이트라고 하는지 궁금했다.

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

명시적 가용 리스트는 오직 free 블록만을 별도의 연결 리스트로 관리함.

• 각 free 블록의 payload 부분에 이전/다음 free 블록을 가리키는 포인터(이전(pred), 다음(succ))를 저장함.
• 할당된 블록은 이 리스트에 포함되지 않음
• 이 구조를 사용하면 할당기에서 가용 블록 탐색, 삽입, 삭제 연산이 훨씬 빨라짐.

명시적 가용 리스트의 구조

• 각 free 블록의 payload에 두 개의 포인터(이전(pred), 다음(succ))이 들어감.
• 이중 연결 리스트로 구현하는 것이 일반적임
• 삽입/삭제는 상수 시간(O(1))에 가능함.

| header | pred | succ | ... (나머지 payload) ... | footer |

주요 연산
삽입: 새로 반환된 free 블록을 리스트의 앞에 추가
삭제: 할당 시 해당 free 블록을 리스트에서 제거

장점

• free 블록만 탐색하므로, 블록 탐색 속도가 빨라진다.
• 삽입/삭제가 상수 시간에 가능하여, 할당기 전체 성능이 향상된다.

단점

• free 블록에 포인터 공간이 추가로 필요하므로 최소 블록 크기가 커지고 내부 단편화 가능성이 증가한다.

명시적 가용 리스트 관리법

1. 후입선출 (LIFO)
   가장 최근에 삽입된 free 블록을 가장 먼저 할당하는 구조

   • 예시
     free list: A-B-C 이고 D가 해제됐을 때
     free list: D-A-B-C로 바뀜
   • 사용 이유
     • 리스트의 맨 앞의 포인터만 바꿔서 넣으면 되므로 O(1) 시간에 처리 가능
     • 최근에 해제된 블록이 다시 재사용될 가능성이 높음

2. 주소 순으로 리스트 관리 (오름차순)
   리스트 내의 각 블록의 주소는 다음 블록의 주소보다 작다.

   • 단점
     • 블록을 반환할 때 적당한 블록을 찾기 위해 선형 시간을 사용해야 함.

9-14) 분리 가용 리스트

여러 개의 프리 리스트를 두고 블록 크기별로 분류하여 관리하는 기법. 각 리스트는 비슷한 크기의 블록들만 포함하며 크기 클래스라고 부름.

• 사용 이유
  암시적/명시적 프리 리스트는 모든 크기의 가용 블록을 하나의 리스트에 넣어 관리함. 이 방식은 할당 요청이 들어올 때마다 전체 리스트를 탐색해야 하므로, 가용 블록이 많아질수록 할당 시간이 선형적으로 증가함.

• 구현 및 동작 방식

  • 크기 클래스 정의
    • 크기 클래스는 다양한 방식으로 나눌 수 있음. (구간별, 거듭제곱 단위)
    • 작은 블록은 세밀하게, 큰 블록은 넓은 구간으로 묶는 방식을 자주 사용함.
  • 할당 시 동작
    • 요청 크기에 맞는 크기 클래스의 리스트를 선택함.
    • 해당 리스트에서 적합한 블록을 찾음.
    • 없으면 더 큰 크기 클래스의 리스트를 순차적으로 탐색함.
  • 반환 시 동작
    • 반환되는 블록의 크기에 맞는 리스트에 삽입함.

• 장점과 단점

  • 장점
    • 할당 속도 향상: 리스트 탐색 범위가 줄어들어 평균적으로 더 빠른 할당이 가능
    • 단편화 감소: 크기별로 관리하므로, 적합한 크기의 블록을 더 쉽게 찾을 수 있음.
  • 단점
    • 관리해야 할 리스트의 개수가 늘어나 구현이 복잡해짐
    • 크기 클래스 구간을 어떻게 나누느냐에 따라 성능이 달라짐.

간단한 분리 저장 장치

동작 방식

• 할당
  • 요청된 크기에 맞는 size class의 free list를 확인합니다.
  • 해당 리스트에 블록이 있으면, 가장 앞에 있는 블록을 통째로 할당합니다.
  • 리스트가 비어 있으면, 운영체제로부터 새로운 큰 메모리 덩어리를 받아 동일한 크기의 블록들로 쪼개어 free list에 추가함.
• 반환
  • 반환되는 블록을 해당 크기 클래스의 free list의 앞에 추가합니다.

특징

• 블록 분할/병합 없음
  • free list의 블록은 항상 같은 크기이므로, 할당 시 블록을 쪼개거나, 반환 시 인접 블록을 합치지 않습니다.
• 헤더/푸터 불필요
  • 블록 크기가 고정이므로, 블록의 크기를 따로 저장할 필요가 없습니다.
  • free 블록에는 다음 free 블록을 가리키는 포인터만 있으면 됨.
• 빠른 동작
  • 할당과 반환이 모두 상수 시간(O(1)에 수행됨.

장점

• 매우 빠른 할당과 반환: 리스트 앞/뒤에 추가하거나 꺼내는 작업만 하면 됨.
• 오버헤드 최소화: free list가 여러 개지만, 필요한 크기의 free 블록이 없으면 다른 리스트의 블록을 사용할 수 없음.
• 블록 크기 추적 불필요: 주소만 보면 어떤 size class인지 알 수 있습니다.

단점

• 내부 단편화: 요청 크기보다 큰 블록이 할당되어 남는 공간이 낭비될 수 있음.
• 외부 단편화: free list가 여러 개지만, 필요한 크기의 free 블록이 없으면 다른 리스트의 블록을 사용할 수 없음.
• 블록 병합 불가: 인접한 블록을 합칠 수 없어, 특정 패턴에서는 심각한 외부 단편화가 발생할 수 있음.

분리 맞춤

동적 메모리 할당기에서 여러 개의 free list를 크기별로 분리해 관리하는 기법
메모리 할당/반환의 효율성을 높이고, 단편화를 줄이기 위해 널리 쓰임.

동작 방식

• 크기 클래스: 전체 블록 크기 범위를 여러 구간으로 나누고, 각 크기 클래스마다 별도의 free list를 둠.
• 할당
  • 요청 크기에 맞는 크기 클래스의 free list를 선택함.
  • 해당 리스트에서 first-fit 방식 등으로 블록을 찾음
  • 없다면 더 큰 크기 클래스의 리스트를 순차적으로 탐색
  • 적합한 블록이 없으면, 운영체제로부터 새로운 메모리를 받아 해당 리스트에 추가함.
• 반환
  • 반환되는 블록의 크기 맞는 free list에 블록을 삽입함.
  • 필요하다면 인접 블록과 병합 후, 다시 알맞은 리스트에 넣음.
• 블록 분할/병합
  • 할당 시 큰 블록을 쪼개어 일부만 할당하고, 남은 부분은 다시 적절한 리스트에 넣음.
  • 반환 시 인접한 free 블록과 병합하여 더 큰 블록을 만들고, 해당 크기 클래스 리스트에 넣음.

장점

• 할당/반환 속도가 빠름
• 단편화 감소
• 실제 best-fit에 가까운 메모리 활용

단점

• 크기 클래스 구간 설정이 어렵고, 잘못 설계 시 단편화가 심해질 수 있음.
• 리스트 개수가 많아지면 관리가 복잡함.

버디 시스템

잠이 올 땐 쉬면서 공부하자..!

운영체제나 메모리 할당기에서 동적 메모리 할당을 호율적으로 처리하기 위해 고안된 메모리 관리 기법
주로 파워-오브-투 크기의 블록 단위로 메모리를 관리하며 빠른 할당 해제와 효율적인 병합이 특징임.

핵심 원리

• 메모리 전체를 2의 거듭제곱 크기의 블록으로 나눔.
• 각 크기별로 free list를 유지함.
• 요청된 크기보다 같거나 큰 블록들 중 가장 작은 2의 거듭제곱 크기 블록을 할당함.
• 블록 분할: 큰 블록에서 필요한 크기보다 크면, 두 개의 같은 크기 블록(버디)로 계속 분할함.
• 블록 병합: 블록이 반환될 때, 그 블록의 "버디"가 free 상태면 두 블록을 합쳐 더 큰 블록으로 만듦.

동작 과정

• 할당
  • 요청 크기를 만족하는 가장 작은 2의 거듭제곱 크기를 찾음 (ex. 18KB => 32KB 블록)
  • 해당 크기의 free block이 없으면, 더 큰 블록을 찾아 계속 반으로 쪼갬(split)
  • 최종적으로 원하는 크기의 블록을 할당하고, 남은 버디 블록은 free list에 추가
• 해제
  • 반환되는 블록의 "버디"(같은 크기의 블록)가 free 상태인지 확인
  • 버디가 free면 두 블록을 병합하여 상위 크기의 블록으로 만듦
  • 이 과정을 반복하여 더 큰 블록까지 병합 가능

버디 찾기

• 버디 블록의 주소는 자신의 주소와 블록 크기를 XOR 연산하면 쉽게 계산할 수 있음.

장점

• 빠른 할당/해제: 분할과 병합이 모두 O(logN) 시간에 가능
• 효율적인 병합: 항상 버디만 확인하면 되므로, 외부 단편화가 적음
• 구현이 비교적 단순: 각 크기별 free list만 관리하면 됨

단점

• 내부 단편화: 요청 크기보다 큰 2의 거듭제곱 블록이 할당되므로 남는 공간이 발생할 수 있음.
• 블록 크기 제한: 2의 거듭제곱 단위로만 할당 가능하므로 다양한 크기의 요청에 최적화하기 어렵다.

10) 가비지 컬렉션

가비지 컬렉션이란?

• 프로그래머가 직접 free를 호출하지 않아도, 더 이상 참조되지 않는 힙 블록을 자동으로 해제하는 메모리 관리 기법
• malloc으로 할당한 후 참조가 끊긴 블록을 프로그램이 종료하기 전 자동으로 회수함.

10-1) 가비지 컬렉터 기초

기본 원리

• 힙에 할당된 블록 중에서 더 이상 도달할 수 없는 블록을 찾아 자동으로 해제하는 역할을 함.

가비지 컬렉터는 방향성 도달 그래프로 메모리를 고려함.

• 노드: 힙에 할당된 각 블록
• 엣지: 한 블록이 다른 블록을 가리키는 포인터
• 루트 노드: 스택, 전역 변수, 레지스터 등 힙 외부에서 시작하는 포인터
• 도달 가능: 루트에서 포인터를 따라 도달할 수 있는 블록
• 가비지: 루트에서 도달할 수 없는 블록

정확한 컬렉션 vs 보수적 컬렉션

• JAVA, ML 등 타입 정보가 명확한 언어에서는 정확한 가비지 컬렉션이 가능하다.
• C, C++처럼 포인터와 데이터 구분이 어려운 언어에서는 보수적 가비지 컬렉션이 필요하다.
  • 보수적 컬렉터는 '포인터처럼 보이는 값'을 모두 포인터로 간주하고, 실제로는 데이터인 값을 포인터로 오인해 도달 가능하다고 판단할 수 있다.
  • 가비지가 실제로 해제되지 않고 남을 수 있지만, 잘못된 해제가 발생하지는 않는다.

가비지 컬렉터 동작 방식

• malloc 패키지와 통합되어 동작함.
• malloc이 메모리 할당에 실패하면 가비지 컬렉터를 호출하여 사용하지 않는 블록을 free로 반홤함.
• 컬렉터가 반환한 후에도 할당에 실패하면 운영체제에 새 메모리를 요청함.

10-2) Mark & Sweep 가비지 컬렉터

Mark & Sweep 방식은 가장 널리 사용되는 가비지 컬렉션 방법 중 하나로, 두 단계로 동작함.

1. 표시 단계
   • 모든 루트에서 시작하여, 포인터를 따라가며 도달 가능한 모든 힙 블록을 표시함.
   • 루트는 전역 변수, 스택 변수, 레지스터 등 힙 외부에서 힙을 가리키는 포인터를 의미함.
   • 힙은 그래프 구조로 모델링할 수 있으며, 루트에서 시작해 포인터를 따라가면 도달 가능한 블록을 모두 찾을 수 있음.
2. 쓸기 단계
   • 힙 전체를 선형으로 순회하며, 표시되지 않은 블록을 free하여 메모리로 반환함.
   • 표시된 블록은 표시를 해제하여 다음 컬렉션을 준비함.

• 특징 및 장점
  • 블록을 이동시키지 않고, 단순히 표시와 해제로만 동작하므로 C언어와 같이 포인터 산술이 자유로운 환경에서도 사용 가능함.
  • 정확한 컬렉션이 힘든 C 언어에서는 포인터처럼 보이는 값도 모두 포인터로 간주하는 보수적 방식으로 동작함.
• 한계
  • 컬렉션 시점에 프로그램이 일시적으로 멈춤.
  • 도달 가능성 판별이 완벽하지 않으면 일부 가비지가 남을 수 있다.