9.9 동적 메모리 할당

동적 메모리 할당이 뭐하는 지랑 명시적 할당기, 묵시적 할당기에 대해 얘기한다

• 명시적 할당기:

  • malloc패키지 같은 거 말한다

  • 응용이 명시적으로 할당된 블록을 반환해 줄 것을 요구한다

• 묵시적 할당기:

  • 가비지 컬렉터 같은거다

  • 할당된 블록이 언제부터 사용 안되고 블록이 반환되는지 검출을 요구한다

9.9.1 malloc과 free함수

malloc 함수는 32비트에선 8의 배수인 블록 리턴한다

64 비트에서는 16 배수로 리턴하고 말이다

malloc은 문제 발생시 NULL 반환하고 errno¹ 설정한다

malloc은 리턴하는 메모리 초기화하지도 않는다
따로 메모리 초기화 해주거나 calloc 써야 한다
calloc은 리턴시 메모리 초기화 해준다
realloc은 할당된 메모리 크기 변경용이다

sbrk 함수라는 것도 나온다

sbrk 함수는 커널의 brk 포인터에 incr을 더해서 힙을 늘리거나 줄인다
성공시 이전의 brk값 리턴, 아니면 -1 리턴하고 errno를 ENOMEM으로 설정한단다
incr이 0이면 걍 현재 brk값 이턴하고

음수도 incr로 가능하지만 복잡해 진다고 한다

free 함수를 사용할 때에는 할당된 블록의 시작을 가리켜야 함
아니면 작동안하는데 이놈은 작동안해도 아무말 없어서 눈치채기 어렵다

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

메모리가 얼마나 필요한지 모르는 경우 있어서 쓴다 ㅇㅇ

9.9.3 할당기 요구사항과 목표

명시적 할당기는 제한이 걸려있다

제한사항

• 임의의 요청 순서 처리하기

  • 어느때나 요청 처리 가능해야 한다

  • 어느 순서에만 받고 이런 거 없다

• 요청에 즉시 응답하기

  • 어떤 종류의 데이터 객체라도 저장 가능하게 정렬해야 한다

  • 요청의 순서를 바꾸거나, 요청을 버퍼에 모아 두는 등의 재정렬/지연 처리는 허용되지 않는다

• 힙만 사용하기

  • 자료 구조들은 힙 자체에 저장해야만 한다

• 블록 정렬하기

  • 어떤 종류의 데이터…? 뭐야 시발 요청에 즉시 응답하기랑 왜 똑같은 내용이야

  • CSAPP 번역 오륜가 보다 ㄹㅇ 얼탱이 없네 돈받고 뭐하냐?

  • 어떤 종류의 데이터 객체라도 저장 가능하게 정렬해야 한다

  • 여기가 어디든 상관없이 정렬이다

• 할당된 블록을 수정하지 않기

  • 한번 할당된 블록을 수정하거나 이동시키면 안된다 압축도 금지다

목표

1. 처리량 극대화하기

뭐, 당연한거다
많이 처리해야 이득일테니까

1. 메모리 이용도를 최대화하기

이것도 당연한 것 같다
자원은 유한하니까 말이다

9.9.4 단편화

단편화에 대해 나온다

대강 말하자면 블록 효율적으로 못쓰는 현상이라 보면 된다

TIL에 정리했다

9.9.5 구현 이슈

구현하는 상상 해보면 몇가지 궁금증이 생긴다 한다

어떻게 가용 블록을 추적하고

배치할 블록을 어떻게 선택하고

가용 블록 빈부분은 어찌하며

반환받은 블록은 어디다 써야 하는가 말이다

음… 솔직히 공부해서 좀 안다

그래도 설명하기는 쉽지 않다

그러니 더 알아보았da-ze

9.9.6 묵시적 가용리스트

묵시적 가용 리스트, 암시적 가용 리스트라는 이름으로 정리해 봤었다

블록의 헤더에 포함된 정보로 블록끼리 묵시적으로 연결되어서 이렇게 부른다

장점

• 구현간단하다

• 뭐 딱히 저장 할 게 없어 메모리 오버헤드가 적다

단점

• 힙에 블록 수 많을수록 효율 구려진다 (할당된 블록까지 포함해 전부 탐색해야 함)

• 가용 블록이 적을 경우 이게 더 심해져 일반적 용도의 할당기로는 비효율적

9.9.7 할당된 블록의 배치

할당된 블록을 배치하는 방법에 대해 나오는데…

first fit, next fit, best fit이 나온다

상당히 익숙하다…

한번 다뤘던 주제니 말이다
메모리 할당 정책은 이미 다뤘었다

그러니 대강 다루겠다

처음부터 검색하는 법 = first fit

그전 검색 끝난 지점에서 검색 시작 = next fit

전부 훑으며 가장 최적화된 블록 검색 = best fit

9.9.8 가용블록의 분할

가용블록과 필요 메모리 크기 차이가 크면 분할한다

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

요청받은 블록 안보이면 인접한 애들 합쳐 큰 거 만든다고 한다

그래도 안되면 추가 힙 메모리 요청하고 뭐

9.9.10 가용 블록 연결하기

블록들 연결하는 법이다

다 공부한 내용 나오는 거라 여기까지는 얕게 다뤘다

메모리 분할, 병합

9.9.11 경계 태그로 연결하기

메모리 쭉읽으며 헤더를 뒤져보는 건 시간 낭비다

이를 해결한 방법은

블록의 끝에 푸터(footer)라는 경계 태그를 설정하는 걸로

이를 통해 바로 앞의 메모리를 읽어 할당된 상태인지 아닌지 확인 금방하게 한다

상당히 끝내주는 방식이지만 단점도 존재한다

헤더와 풋터를 유지해야 하므로 작은 블록의 경우 헤더와 풋터 만으로 꽉꽉 차버려서

작은 크기 블록 여러 개 다루려면 비효율적이 되어버린다
-> 실제 메모리 저장하는 공간이 헤더와 풋터때문에 줄었기에 더 많은 블록이 필요함

이에 대한 최적화 방법이 존재한다

여기가 조금 어려웠다

이전 블록 할당 여부를 현재 블록의 헤더 하위 비트에 기록하는거다
그게 무슨 말이냐?

a,b 블록이 있고 a를 할당할 때에 a할당 여부를 b헤더의 하위비트에 기록하는 거다
그러면 a에 푸터를 만들 필요가 없다

그치만 가용 블록에는 푸터가 있어야 추적가능하다는 건 염두에 두어야 하기에 문제가 완벽히 해결되지는 않는다

9.9.12 종합 설계: 간단한 할당기의 구현

할당기 만드는 법 나온다

여기는 각자 읽고 만들어보자

설명하는 건 의미 없는 거 같다

책 베끼는 거니까

9.9.13 명시적 가용리스트

명시적 가용 리스트도 다뤘다

무슨 방법이냐면 가용 블록들을 리스트로 저장하는 방식이다
보통은 저장된 블록들을 이중 연결 리스트로 연결해 사용한다
할당 시간을 전체 블록 수에서 가용 블록 수로 줄일 수 있다

사소한 단점으로는 가용 블록들에 포인터, 헤더, 풋터 다 들어가야 한다는 거다
따라서 최소 블록 크기가 커지고 내부 단편화 가능성도 높아진다

그치만 묵시적 가용 리스트 보다는 낫다

9.9.14 분리 가용 리스트

분리 가용 리스트도 다뤘다

착실한 예습 ㅇㅈ?

설명하기 좀 귀찮은데 대충 가용 리스트 여러개 운용하는 방식이다

“1-2바이트”, “3-4바이트”, “5-8바이트”, …, “1025-2048바이트”, “2049-4096바이트”, “4097바이트 이상” 등등 이런식으로 범위를 나누고 각 구간마다 블록 넣어 관리하는 방식이라 볼 수 있다

fisrt fit방식으로도 best fit만큼의 포텐을 뽑을 수도 있는 방식이다

그리고 자주 쓰이는 대표적 변형이 2가지 있다

단순 분리 저장

말그대로 단순하다

범위의 최대 크기의 블록들만 저장하는 거다

“17-32” 바이트의 경우 32바이트 블록만 저장한다 볼 수 있다

절대 분할안하고 걍 첫 블록 통째로 할당해서 준다

장점

포인터 조작으로 할당, 헤제 다해서 속도가 무척 빨라지고
헤더에 크기, 할당비트 같은 것도 저장할 필요 없다

간단하고 무척 좋다

단점

분할도, 병합도 하지 않아 내부/외부 단편화가 심각할 수 있다

필요보다 큰 걸 주어 내부 단편화

자른 걸 합치지 않기에 외부 단편화

이러한 단점떄문에 극단적으로 속도가 중요한 경우나 블록 크기 몇개로 제한된 경우외에는 사실상 안쓰인다

분리 맞춤

좀 더 유연하다

가용 리스트 범위별로 두고 범위안에 속하는 다양한 크기 블록 유지하는 방식이다

요청 크기에 해당하는 범위를 찾아 first fit으로 찾고 없으면 다음 더 큰 범위에서 찾는 방식이다

장점

속도와 메모리 효율의 균형이 좋다

실제로 malloc 구현할때도 쓰며 현대 할당기들의 주된 방식이다

단점

사이즈별로 나뉘어 있어 서로 빌려 쓰기 어렵고 사이즈 클래스 튜닝을 상황에 맞춰 해야한다

버디 시스템

얜 좀 특이한 방식으로 분리 가용 리스트의 일부라고 볼 수 있다

모든 블록 크기를 2의 거듭제곱으로 제한하고, 각 크기 ($2^k$)마다 별도 가용 리스트를 유지한다

이후 요청된 크기는 다음 큰 $2^k$로 올림하여 할당하고 없으면 한단계 위의 블록을 반으로 갈라 할당하고 하나는 그 리스트에 넣는거다

예)
26바이트 블럭 요구 했는데 32바이트 블럭 없고 64바이트 가용블록 존재시
64비트 32/32로 나누어 하나는 32바이트 리스트에 넣고 하나는 할당하는 방법

장점

검색과 병합이 매우 빠르다

포인터만으로 전부 가능하니 말이다

단점

단편화가 무척 심해진다

---