[TIL] WEEK06 - CS:APP 9장

묵시적(Implicit) 형변환
컴파일러에 의해 '자동으로 형변환'이 이루어지는 것
표현 범위가 작은 데이터 타입 -> 큰 데이터 타입으로의 변환만 허용함
ex) int a + float b => int형은 float형으로 묵시적 형변환이 이루어짐

명시적(Explicit) 형변환
사용자가 '직접 데이터의 타입을 변경'하는 것
표현 범위가 넓은 데이터 타입 -> 작은 데이터 타입으로의 변환도 허용 (값 손실)

9.9 동적 메모리 할당

추가적인 가상 메모리를 런타임에 획득할 필요가 있을 때, 동적 메모리 할당을 한다.
동적 메모리 할당기는 프로세스의 가상 메모리 영역인 Heap을 관리한다.

[자세한 내용은 시스템마다 다름]
힙 영역은 미초기화된 데이터 영역 직후에 시작해 높은 주소 방향(위쪽)으로 커지는 ‘무요구 메모리 영역’이라 가정하자. 각각의 프로세스에 대해, 커널은 힙의 top을 가리키는 변수 brk를 사용한다.

메모리 할당기는 힙을 다양한 크기의 블록 단위로 관리한다.

할당된 블록
응용하기 위해 명시적으로 보존
응용에 의해 명시적 or 메모리 할당기 자신에 의해 묵시적으로 반환될 때까지 할당된 채로 남아있음

가용한 블록
할당을 위해 사용 가능
응용이 명시적으로 할당할 때까지 가용한 상태로 남아있음

[할당기의 기본 유형]

명시적 할당
응용 프로그램이 명시적으로 할당된 블록을 반환해줄 것을 요구

ex) malloc & free

묵시적 할당 = 가비지 컬렉터
언제 할당된 블록이 더 이상 사용되지 않고, 블록을 반환하는지 할당기가 검출할 수 있을 것을 요구

가비지 컬렉션: 자동으로 사용하지 않는 할당된 블록을 반환시켜주는 작업 (c는 지원 안 함)

9.9.1 malloc과 free 함수

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

void* malloc(size_t size);

malloc은 블록 내 포함될 수 있는 어떤 종류의 데이터 객체에 대해 적절히 정렬된 최소 size 바이트를 갖는 메모리 블록의 포인터를 리턴한다. (32bit mode의 경우 8의 배수, 64bit mode의 경우 16의 배수의 주소)

만약 size가 0이거나 가용한 가상메모리보다 더 큰 크기의 메모리 블록을 요청하는 경우, 할당에 실패해 Null을 리턴하고 errno를 세팅한다.

malloc은 할당하는 공간을 초기화하지 않고, 쓰레기 값으로 채워지지만,
만약 0으로 초기화한 동적 메모리를 원한다면 -> calloc

void* calloc(size_t size);

이전에 할당된 블록의 크기를 변경하려면 -> realloc

void* realloc(void* p, size_t size);

malloc같은 동적 메모리 할당기는 mmap & munmap 함수를 사용해 ‘명시적’으로 힙 메모리를 할당/반환하거나, sbrk 함수를 사용할 수 있다.

void* sbrk(intptr_t incr);

sbrk 함수
: 커널의 brk(heap top을 가리키는 포인터)에 incr을 더해 힙을 늘리거나 줄인다.

• 성공 시: 이전의 brk값 리턴(이전부터 채워야 하니까)
• 실패 시: -1 return, errno = ENOMEM 설정
  [incr을 음수로 할당하면? 리턴 값이 새로운 heap top을 지나 abs(incr)을 가리키기 때문에 복잡해짐]

동적 할당을 해준 후, 프로그램들은 할당된 힙 블록을 free 함수를 호출해 반환해야 한다.

free(void *ptr);

여기서 ptr 인자는 malloc/calloc/realloc에서 획득한 할당된 블록의 ‘시작’을 가리켜야 함
그렇지 않은 경우, free의 동작은 정의되지 않는다, 아무것도 리턴하지 않기 때문에 뭔가 잘못되었다는 것을 알릴 수 없다..

9.9.2 왜 동적 메모리 할당인가?

동적 메모리 할당을 사용하는 이유?
: 프로그램을 실행시키기 전까지 자료구조의 크기를 알 수 없는 경우들이 있기 때문

• 프로세스의 가상 메모리 영역인 heap을 사용/관리한다.
• 명시적: 응용 프로그램이 할당&반환 (ex. malloc/free)
• 묵시적: 응용 프로그램이 할당, 반환은 하지 않는다
  • 이는 더 이상 사용되지 않는 블록을 검출할 수 있어야 함 (ex. 가비지 컬렉션(자동 할당/반환))

9.9.3 할당기 요구사항과 목표

• 임의의 요청 순서 처리
  : 요청이 발생하는 순서와 상관없이 임의의 요청 순서를 처리할 수 있어야 한다.
  요청이 동시에 발생할 수 있고, 우선순위가 다를 수 있으니까
  예를 들어 a, b, c 순으로 할당을 해도 free는 a, b, c 순으로 하지 않아도 됨
• 요청에 즉시 응답
  : 요청이 발생하면 즉시 응답해 할당된 메모리 블록의 주소를 반환해야 한다.
  이 때 지연이나 대기 시간 없이 신속한 응답을 해야 함
• 힙만 사용
  : 명시적 할당기는 메모리 할당에 heap만 사용해야 한다.
  힙=동적 메모리 할당을 위해 운영체제가 제공하는 메모리 영역, 할당된 메모리는 사용 후 해제해야 함
• 블록 정렬
  : 할당된 메모리 블록은 특정한 정렬 규칙을 따라야 한다.
  일반적으로 메모리 블록은 특정 크기의 배수에 해당하는 주소로 정렬되어야 한다 -> 메모리 접근 성능 최적화
• 할당된 블록 수정x
  : 이미 할당된 블록을 수정하는 것을 금지, 다른 요청에 재할당하기 위한 안정성 보장을 위함

-> 이렇게 제한사항이 빡빡하지만, 처리량/메모리 이용도 최대화를 목표로 가진다

• 처리량 극대화 = 빠른 시간 내 많은 요청 처리
• 메모리 이용도 극대화 = 가상 메모리는 ‘유한’한 자원, 최대한 많이 넣을수록 좋음
  -> 그런데 처리량과 메모리 이용도는 상충관계(trade off)로, 균형을 잘 잡아서 만들어야 한다.

9.9.4 단편화

단편화 -> 메모리 사용 효율이 떨어지는 이유

단편화가 심해지면 메모리가 충분히 남아있음에도 불구하고, 사용하지 못 하는 경우가 생김

1. 내부 단편화: 할당된 블록이 데이터 자체보다 큰 경우
   할당은 받았지만, 할당된 블록이 더 크기 때문에 사용되진 않지만 할당은 되어버린, 사용할 수 없는 블록이 생김
   [발생 이유?: 정렬 제한사항을 만족하기 위해 or 할당정책에 의한 오버헤드]

2. 외부 단편화: 메모리 공간이 전체적으로 봤을 땐 충분하지만, 요청을 처리할 단일 가용 블록은 없는 경우
   외부 단편화의 여부는 미래 요청 패턴에 의존하기 때문에 측정이 어렵다.

9.9.5 구현 이슈

처리량과 메모리 이용도를 좋은 균형으로 맞추기 위해 고려할 사항

• 가용 블록 구성: 어떻게 가용 블록을 지속적으로 추적할 지 (묵시 or 명시)
• 배치: 새로 할당된 블록배치를 위해 가용블록을 어떻게 선택할 지
• 분할: 새로 할당한 블록을 배치하고, 남은 부분을 무얼 할 지
• 연결: 방금 반환된 블록으로 무얼 할 지

9.9.6 묵시적 가용 리스트

모든 할당기는 블록 경계를 구분하고, 할당/가용 블록을 구분하는 데이터 구조가 필요하다.
일반적으로 이 정보를 블록 내에 내장한다. = 추가적인 1개의 블록(header)을 사용해 블록 앞에 크기를 저장하는 방법

묵시적 가용 리스트(Implicit Free List)
: header에 block size, allocated(할당)/free(가용), payload(데이터), padding이 있음
block size가 있기 때문에 다음 블록의 header 위치가 어디 있는지 ‘묵시적’으로 가리키기 때문에 묵시적 가용 리스트 = 가용 블록이 헤더 내 필드(block size)에 의해 묵시적으로 연결되어 있다.

• 장점: 구조도 간단하고 구현도 편함
• 단점: 가용 리스트 탐색시 전체 블록들을 순회해야 한다

명시적 가용 리스트(Explicit Free List)
: 묵시적 가용 리스트의 payload 안에 pred/succ가 있어서 다음 가용 리스트의 위치를 편하게 알 수 있음
그러나 일반적으로 블록들에 포인터/헤더/풋터까지 포함을 해야 함 -> 내부 단편화/블록의 크기 증가

1. header
: 추가 사용되는 1워드, 블록 크기와 할당/가용 상태를 인코딩함
만약 더블워드(8byte) 정렬 제한조건을 설정하면 블록 크기는 항상 8의 배수다.
그럼 블록 크기의 하위 3비트는 항상 0 (= 8이 이진수로 1000이니까)
이래서 상위 29비트만 저장하고 나머지 3비트는 다른 정보를 인코딩한다

예를 들어 블록 크기로 24바이트를 가진 할당 블록의 헤더는?
: 0x00000018 | 0x1 = 0x00000019

블록 크기: 0x00000018 = 24의 16진수 표기법 -> 2진수 표기법 = 0001 1000
할당된 블록: 0x1 = 1의 16진수 표기법 -> 2진수 표기법 = 0000 0001
|은 OR 연산 진행 -> 0001 1001 = 0x00000019

또 다른 예로 40바이트를 가진 가용 블록의 헤더는?
0x00000028 | 0x0 = 0x00000028

2. payload
: 헤더 다음으로 오는, malloc을 불렀을 때 요구한 data

3. padding
: payload 다음으로 오는, 사용하지 않는 padding 공간으로 가변적이다.
외부 단편화를 극복/정렬 요구사항을 만족하기 위한 공간

->위와 같은 포맷으로 힙을 연속된 [할당/가용 블록의] 배열로 구성하면 = 묵시적 리스트

9.9.7 할당한 블록의 배치

메모리 할당을 요청할 때 할당기는 요청한 메모리를 저장하기에 충분히 큰 가용 블록을 검색한다.
검색을 수행하는 방법은 배치 정책에 의해 결정

1. First-Fit: 리스트를 처음부터 검색해 크기가 맞는(들어갈 수 있는) 첫 번째 가용블록 선택

• 장점: 리스트의 마지막 부분에 가장 큰 가용 블록들을 남겨두는 경향
• 단점: 리스트의 앞 부분에 작은 가용 블록들을 남겨두는 경향 -> 큰 블록 공간을 찾을 때 검색 시간이 늘어남

2. Next-Fit: First-Fit과 비슷하지만 검색을 리스트의 처음에서 시작하는 대신, 이전 검색이 종료된 시점에서 검색 시작 -> First-Fit에 비해 매우 빠른 속도지만, 최악의 메모리 이용도를 가짐

3. Best-Fit: 모든 가용 블록들을 검사하면서 크기가 맞는 가장 작은 블록 선택

9.9.8 가용 블록의 분할

크기가 맞는 가용 블록을 찾은 다음 어느정도 할당할 지 결정을 내려야 함
블록 전체를 사용하면 간단하겠지만, 내부 단편화 문제가 발생할 수 있다.
그래서 가용 블록을 할당 블록과, 새로운 가용 블록으로 분할한다.

만약 24/0(6칸) 블록이 있는데, 이 때 24바이트(6)를 필요로 한다면 문제가 없지만,
8바이트(2)를 필요로 한다면? 나머지 16바이트(4)에서 내부 단편화 문제가 발생한다.

그래서 8바이트(2)를 할당하고, 나머지 16바이트(4)를 분할해서 새로운 가용 블록(4칸)을 생성해 메모리 효율성을 높인다.

9.9.9 추가적인 힙 메모리 할당

만약 요청한 크기의 블록을 찾을 수 없다면? 두 가지 해결 방법이 있다.

1. 물리적으로 인접한 가용 블록들을 합쳐서(연결해서) 더 큰 가용 블록을 만드는 방법
-> 이래도 충분한 크기가 만들어지지 않거나, 이미 최대로 연결된 상태라면 2번 방법으로 해결

2. sbrk 함수를 호출해 추가적인 힙 메모리를 요청하는 방법
-> 할당기는 추가 메모리를 한 개의 더 큰 가용 블록으로 변환해 가용 리스트에 삽입한 후, 요청한 블록을 새로운 가용 블록에 배치한다.

9.9.10 가용 블록 연결하기

블록을 할당/반환하다보면 작고 사용할 수 없는 가용 블록으로 쪼개진 많은 가용 메모리들이 존재할 수 있다 (=오류 단편화)
예를 들어,

|8/0|   |16/1|—|—|—|16/0|   |   |   |16/1|—|—|—|0/1|

이 상태에서 16/1을 반환하면? 각각 3워드의 데이터를 갖는 인접한 16/0, 16/0 블록들이 생긴다.
근데 이 때 4워드를 요청하면? 가용블록 전체의 크기는 요청을 만족할 정도로 크지만, 할당에 실패한다.

오류 단편화를 극복하기 위해 ‘연결’과정으로 인접 가용 블록들을 통합(coalescing)해야 한다.
이건 언제 연결을 해야 할 지 결정해야 함

1. 즉시 연결
: 블록이 반환될 때마다 인접 블록을 통합하는 것
-> 간단하고, 상수 시간 내 수행이 가능하지만 일부 요청 패턴에 대해 블록을 연결하고 바로 잠시 후에 분할되는 쓰레싱 형태를 유발할 수 있다. 예를 들어 위 상태에서 16/1을 반환하고 즉시 연결을 하면 32/0이 되지만, 이 다음에 3워드를 할당하면? 또 이전과 같은 형태로 분할되게 됨

2. 지연 연결
: 일부 할당 요청이 실패할 때까지 연결을 지연하고, 이후에 전체 힙을 검색해 모든 가용 블록들을 연결하는 것

9.9.11 경계 태그로 연결하기

반환하려고하는 블록(현재 블록)의 다음 가용 블록을 연결하는 것은 쉽고 효율적이다.
-> 현재 블록의 헤더가 다음 블록의 헤더를 가리키고 있어서 다음 블록이 가용 가능한 지 판단할 수 있음

이 때 이 둘을 연결한다면, 현재 블록의 헤더의 크기에 다음 블록의 크기가 더해진다.

근데 이전 블록이 가용 가능한 상태라면? 어떻게 연결할까?
일반적으로 방법을 생각해보면, 현재 블록에 도달할 때까지 전체 리스트를 검색해서 이전 블록의 위치를 기억하는 방법이 있다. 근데 이는 시간 소모가 크다 (= 각각의 free 호출이 힙의 크기에 비례하는 시간을 소모한다는 걸 의미)

이 문제를 해결하기 위해 경계태그(footer)가 고안됐다. (footer: 헤더를 복사한 것, 4byte를 차지)
footer는 가용 블록을 효율적으로 찾기 위해 사용된다. 근데 생각해보면 이건 오히려 메모리 사용에 방해된다.

예를 들어, 4바이트의 데이터를 할당받는다고 해보자.
그럼 header와 footer를 포함해 12바이트를 바이트를 필요로 한다.
이는 매우 비효율적이며, 작은 크기의 블록을 다룰 땐 상당량의 오버헤드가 발생하고 header와 footer가 할당된 블록의 절반을 차지할 수도 있다.

아무튼, 할당기가 현재 블록을 반환할 때 가능한 모든 경우의 수는 4가지다.

1. 이전 블록과 다음 블록이 모두 할당 상태 = coalescing 발생x
   현재 블록이 할당에서 가용 상태로 변경

2. 이전 블록은 할당 상태, 다음 블록은 가용 상태 = 현재와 다음 블록 coalescing
   현재 블록과 다음 블록의 footer가 두 블록의 크기를 합한 것으로 갱신

3. 이전 블록은 가용 상태, 다음 블록은 할당 상태 = 현재와 이전 블록 coalescing
   이전 블록의 header와 현재 블록의 footer가 두 블록의 크기를 합한 것으로 갱신

4. 이전 블록과 다음 블록이 모두 가용 상태 = 현재와 이전/다음 블록 모두 coalescing
   이전 블록의 header와 다음 블록의 footer가 세 블록의 크기를 합한 것으로 갱신