WEEK06 - TIL 동적 메모리 할당

9.9 동적 메모리 할당

가상 메모리 영역을 저수준의  mmap & munmap함수를 이용해 생성/삭제할 수 있지만, 추가적인 가상메모리를 런타임에 획득할 필요가 있을 때, "동적 메모리 할당기를 사용하는 것을 좀 더 편리하고 호환성이 좋다고 생각"

 

동적 메모리 할당기는 힙(heap) 프로세스의 가상메모리 영역을 관리.

→ 일반화의 오류를 범하지 않는 한도에서 힙이 미초기화된 데이터 영역 직후에 시작해서 위쪽(높은 주소 방향)으로 커지는 무요구 메모리 영역이라고 가정

→ 커널은 힙의 꼭대기를 가리키는 변수 brk(break)를 사용

 

할당기는 두 개의 기본 유형이 가능. 두 유형 모두 응용이 명시적으로 블록을 할당하도록 요구하며, 어떤 엔트리가 할당된 블록을 반환하기 위해 무엇이 사용되어야 하는지에 차이가 난다.

1. 명시적인 할당기

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

[ex. c표준 라이브러리의 malloc 패키지 → malloc 함수를 호출해 블록을 할당하고 free 함수를 호출해 블록을 반환

2. 묵시적 할당기

= 언제 할당된 블록이 더 이상 프로그램에 의해 사용되지 않고 블록을 반환하는지를 할당기가 검출할 수 있을 것을 요구

묵시적 할당기는 가비지 컬렉터 (garbage collector)라고 불리며 자동으로 사용하지 않은 할당된 블록을 반환시켜주는 작업을 가비지 컬렉션이라고 한다.

 

9.9.1 malloc과 free함수

malloc패키지는 명시적인 할당기를 제공. 프로그램은 malloc 함수를 호출해 힙으로부터 블록들을 할당받음

malloc 함수는 블록 내 포함될 수 있는 어떤 종류의 데이터 객체에 대해 적절히 정렬된 최소 사이즈 바이트를 갖는 메모리 블록의 포인터를 리턴

실제 구현에서 정렬은 코드가 32/64bit냐에 따라 다른데, 32는 malloc 주소가 항상 8의 배수인 블록을 리턴하고, 64에서는 항상 16의 배수이다.

동적 메모리 할당기인 malloc은 mmap과 munmap 함수를 사용해 힙 메모리를 할당하거나 반환 또는 sbrk 함수를 사용할 수 있다.

 

- sbrk(), brk()은? 메모리 할당시 호출되는 시스템 콜

int brk(void *addr);

brk()는 addr주소 위치에 program break(현재 프로세스의 data segment의 끝부분 바로 다음 자리)를 설정한다.

program break의 위치를 옮김으로써 메모리를 할당하거나 반환, 성공시 brk는 0을 반환하고 실패시 -1을 반환한다.

void *sbrk(intptr_t increment);

sbrk()는 program break에 increment만큼 더한 뒤 그만큼 할당된 메모리를 변경한다. 만약 increment가 음수면 할당된 메모리는 error

성공시 sbrk는 이전 program break 주소를 반환하며(새로 메모리가 할당되었을 때 이전 program break는 할당된 메모리의 시작위치) 실패시 (void *)-1을 반환한다.

 

brk(), sbrk() 두 함수의 차이점은 program break를 설정하는가와 증가시키냐의 차이다.
또한 sbrk()함수에 increment의 인자를 0으로 설정한 후 호출하게되면 현재 program break의 위치를 void* 형 포인터로 반환함을 알 수 있다.

 

 

 

 

= (d)에서 free를 통해 (b)에서 할당된 6워드를반환해주는데, 이때 포인터 p2는 여전히 malloc된 블록을 가리킨다는 점에 유의!

 

p2가 새로운 malloc 콜에 의해 다시 초기화될 때까지 p2를 사용하지 않는 것은 응용의 책임이다~

 

 

= (e)에서 2워드 블록을 요청하는데, malloc은 이전 단계에서 반환된 블록의 부분을 할당하여 새로운 블록의 포인터를 리턴한다.

 

 

 

 

 

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

동적 메모리 할당을 사용하는 가장 중요한 이유는, 프로그램을 실제 실행시키기 전에 자료 구조의 크기를 알 수 없는 경우들이 있기 때문

- 배열을 정해진 크기로 사용해 할당하는 것은 나쁜 방법이 될 수 있다. 만약 사용자가 더 큰 파일을 읽으려고 할 때, 정적 배열을 사용하였다면, 유일한 대책은 프로그램을 더 큰 값을 사용해 다시 컴파일 하는 것

- 고정된 배열 크기가 있다는 것은 작은 규모에선 문제가 되지 않을 수 있으나, 수백만 라인의 코드와 수많은 사용자가 있는 큰 규모의 SW 제품에서는 관리하는데 어려움이 될 수 있다.

→ 더 나은 방법은 배열을 런타임에 동적으로 할당하는 것!

 

9.9.3 할당기 요구사항과 목표

명시적 할당기들은 다소 엄격한 제한사항 내에 동작

 

~요구사항~

1. 임의의 요청 순서 처리하기

= 응용프로그램은 각각의 가용 블록이 이전의 할당 요청에 의해 현재 할당된 블록에 대응되어야 한다는 제한사항을 만족하면서 임의의 순서로 할당과 반환요청을 할 수 있음. 따라서 할당기는 할당과 반환 요청의 순서에 대해서는 아무 가정도 할 수 없다.

2. 요청에 즉시 응답하기

= 할당기는 블록들을 이들이 어떤 종류의 데이터 객체라도 저장할 수 있도록 하는 방식으로 정렬

3. 힙만 사용하기

= 확장성을 갖기 위해 할당기가 사용하는 비확장성 자료 구조들은 힙 자체에 저장되어야 한다.

4. 블록 정렬하기 (정렬 요건)

= 할당기는 블록들을 이들이 어떤 종류의 데이터 객체라도 저장할 수 있는 방식으로 정렬해야 함

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

= 할당기는 가용 블록을 조작하거나 변경할 수만 있음. 특히 일단 블록이 할당되면 이들을 수정하거나 이동하지 않음. 그래서 할당된 블록들을 압축하는 등의 기법들은 허용이 안됨!

 

~목표~

1. 처리량 극대화하기

= n번의 할당과 반환 요청의 배열이 주어졌을 때 할당기의 처리량을 최대화하려고 하며, 이것은 단위 시간당 완료되는 요청의 수로 정의.

= 일반적으로 할당과 반환 요청들을 만족시키기 위해 평균 시간을 최소화 해 처리량을 최대화 함

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

= 한 시스템에서 모든 프로세스에 의해 할당된 가상메모리의 양은 디스크 내의 스왑 공간의 양에 의해 제한된다.

= 가장 유용한 단위는 최고 이용도 (peak utilization)

 

9.9.4 단편화

나쁜 힙 이용도의 주요 이유는 '단편화'라고 알려진 현상 = 가용 메모리가 할당 요청을 만족시키기에는 가용하지 않았을 때 일어난다. 두 종류의 단편화가 있는데, 내부/외부 단편화이다.

 

- 내부 단편화

= 할당된 블록이 데이터 자체보다 더 클 때 일어남.

ex. 할당기의 구현이 요청한 데이터보다 더 큰 할당된 블록들에 최소 크기를 부여할 수도 있다. 즉, (b)처럼 할당기는 정렬 제한사항을 만족시키기 위해 블록의 크기를 증가시킬 수도 있다.

→ 내부 단편화는 정량화하기가 간단하다. 단순히 할당된 블록의 크기와 이들의 데이터 사이의 차이의 합. 시간상 어디서든 내부 단편화의 양은 이전에 요청한 패턴과 할당기 구현에만 의존

 

- 외부 단편화

= 할당 요청을 만족시킬 수 있는 메모리 공간이 전체적으로 공간을 모았을 때 충분한 크기가 존재하나, 이 요청을 처리할 수 있는 단일한 가용블록은 없는 경우에만 발생함.

ex. (e)의 요청이 2워드가 아니라 8워드였으면, 이 요청은 힙에 8개의 가용워드가 남아 있는데도 커널에서 추가적인 가상메모리를 요청하지 않고는 만족시킬 수 없다.

 

외부 단편화는 내부 단편화보다 훨씬 더 측정하기가 어려움. → 이전 요청의 패턴과 할당기 구현에만 의존하는 것이 아니라 미래의 요청 패턴에도 의존하기 때문.

ex. k번의 요청 후, 모든 가용 블록들이 4워드 크기를 갖는다고 하자. 이후의 할당 요청들이 4워드와 같거나 작으면 외부 단편화는 일어나지 않으나, 한 개 이상의 요청이 4워드보다 큰 블록들을 요청하면 힙은 외부 단편화가 발생할 수 있다!

 

∴ 외부 단편화가 측정하기 어렵고 예측하기 불가능하기에 할당기들은 대개 많은 수의 더 작은 가용 블록들보단 더 적은 수의 큰 가용 블록들을 유지하려는 방법들을 택함

 

9.9.5 구현 이슈

고려해야 할 이슈

 

1. 가용 블록 구성

= 어떻게 가용 블록을 지속적으로 추적하는가?

2. 배치

= 새롭게 할당된 블록을 배치하기 위한 가용 블록을 어떻게 선택하는가?

3. 분할

= 새롭게 할당한 블록을 가용 블록에 배치한 후 가용 블록의 나머지 부분들로 무엇을 할 것인가?

4. 연결

= 방금 반환된 블록으로 무엇을 할 것인가?

 

9.9.6 묵시적 가용 리스트

모든 실용적인 할당기는 블록 경계를 구분하고, 할당된 블록과 가용 블록을 구분하는 데이터 구조를 필요로 하며 대부분의 할당기는 이 정보를 블록 내에 내장한다.

 

= 한 블록은 1워드 헤더, 데이터, 추가적인 패딩으로 구성. 헤더는 '블록 크기'와 '블록이 할당/가용 상태'인지를 인코딩

 

데이터 다음에는 사용하지 않는 패딩이 따라올 수 있는데, 이들의 크기는 가변적이다. 패딩을 위한 할당기 전략의 일부분이거나 정렬 요구사항을 만족하기 위해 필요할 수 있다.

 

그림 9.36과 같은 구조를 '묵시적 리스트'라고 부르는데, 그것은 가용 블록이 헤더 내 필드에 의해서 묵시적으로 연결되기 때문이다. 할당기는 간접적으로 가용 블록 전체 집합을 힙 내의 전체 블록을 다니면서 방문할 수 있다. 특별히 표시한 마지막 블록이 필요하다는 점에 유의!

→ 그림에서 종료하는 헤더에는 할당 비트가 세트되어 있고, 크기는 0을 갖는다.

 

묵시적 가용 리스트의 장점: 단순성

묵시적 가용 리스트의 단점: 할당된 블록을 배치하는 것과 같은 가용 리스트를 탐색해야 하는 연산들의 비용이 힙에 있는 전체 할당된 블록과 가용 블록의 수에 비례한다는 것.

 

시스템의 정렬 요구조건과 할당기의 블록 포맷 선택이 할당기에 최소 블록 크기를 결정한다는 것을 깨닫는 것이 중요!

할당되거나 반환된 블록 모두 이 최소값보다 더 작을 수 없다.

 

9.9.7 할당한 블록의 배치

어플리케이션이 k바이트의 블록을 요청할 때, 할당기는 요청한 블록을 저장하기에 충분히 큰 가용 블록을 리스트에서 검색. 할당기가 이 검색을 수행하는 방법은 배치 정책에 의해 결정. 이 정책은 first fit, next fit, best fit이 주로 사용.

 

- first fit

= 가용 free 리스트를 처음부터 검색해서 크기가 맞는 첫 번째 가용 블록을 선택

= 장점: 리스트의 마지막에 가장 큰 가용 블록들을 남겨두는 경향이 있다는 점

= 단점: 리스트의 앞부분에 작은 가용 블록들을 남겨두는 경향이 있어 큰 블록을 찾는 경우에 검색 시간이 늘어난다.

- next fit

= first fit과 비슷하나 검색을 리스트의 처음에서 시작하는 대신, 이전 검색이 종료된 지점부터 검색 시작

= first fit에 대한 대안으로, 이전 검색에서 가용 블록을 발견했다면 다음 검색에서는 리스트의 나머지 부분에서 원하는 블록을 찾을 가능성이 높다는 아이디어에서 착안한 방법

= first fit에 비해 매우 빠른 속도를 갖는데, 리스트의 앞부분이 많은 작은 크기의 조각들로 구성되면 특히 더 이런 성향을 보임. 그러나 일부 연구 결과에선 next fit이 first fit보다 최악의 메모리 이용도를 갖는다고 한다.

- best fit

= 모든 가용 블록을 검사하며 크기가 맞는 가장 작은 블록을 선택

= best fit이 일반적으로 앞선 두 개 보다 더 좋은 메모리 이용도를 갖지만, 묵시적 가용 리스트 같은 단순한 가용 리스트 구성을 사용해서는 best fit을 사용하는 단점은 힙을 완전히 다 검색해야 한다는 점

 

9.9.8 가용 블록의 분할

할당기는 크기가 맞는 가용 블록을 찾은 후에 가용 블록의 어느 정도를 할당할지 정책적 결정을 내려야 함. 한 가지 옵션은 이 가용 블록 전체를 사용하는 것.

간단하고 빠르지만, 큰 단점은 내부 단편화가 생긴다는 것 → 만일 배치정책으로 인해 크기가 잘 맞는다면 일부 추가적인 내부 단편화는 수용할 수도 있으나, 크기가 잘 맞지 않다면 할당기는 대개 가용 블록을 두 부분으로 나누게 됨

첫 번째 부분은 할당한 블록이 되고, 나머지는 새로운 가용 블록이 된다.

 

9.9.9 추가적인 힙 메모리 획득

한 가지 옵션은 메모리에서 물리적으로 인접한 가용 블록들을 합쳐서(연결해서) 더 큰 가용 블록을 만들어보는 것. 그러나 이렇게 해도 충분히 큰 블록이 만들어지지 않거나 가용 블록이 이미 최대로 연결되었다면, 이 할당기는 sork 함수를 호출해서 추가적인 힙 메모리를 요청함.

할당기는 추가 메모리를 한 개의 더 큰 가용 블록으로 변환하고, 이 블록을 가용 리스트에 삽입한 후에 요청한 블록을 이 새로운 가용 블록에 배치

 

9.9.10 가용 블록 연결하기

할당기가 할당한 블록을 반환할 때, 새롭게 반환하는 블록에 인접한 다른 가용 블록들이 있을 수 있는데, 인접 가용 블록들을 오류 단편화(false fragmentation)라는 현상을 유발할 수 있으며, 이때는 작고 사용할 수 없는 가용 블록으로 쪼개진 많은 가용 메모리들이 존재.

위 그림은 (헤더인 1워드 제외 데이터)3워드의 데이터를 갖는 두 개의 인접한 블록들. 4워드를 이후에 요청하면 두 개의 가용 블록 전체의 크기는 요청을 만족시킬 정도로 충분히 크지만 실패!

→ 오류 단편화를 극복하기 위해 실용적인 할당기라면, 연결(coalescing)이라는 과정으로 인접 가용 블록들을 통합해야 함.

할당기는 블록이 반환될 때마다 인접 블록을 통합해서 즉시 연결을 선택할 수 있고 또는 일정 시간 후에 가용 블록들을 연결을 선택할 수 있음.

즉시 연결은 간단해 상수 시간 내에 수행할 수 있지만, 일부 요청 패턴에 대해 블록인 연속적으로 연결되고 잠시 후에 분할되는 쓰래싱(메모리 영역에 접근하게 될 때, 메모리에 페이지 부재(=페이지 폴트(Page fault)율이 높은 것을 의미)의 형태를 유발할 수 있다.

 

9.9.11 경계 태그로 연결하기

헤더를 사용하는 묵시적 가용 리스트가 주어진다면, 유일한 옵션은 현재 블록에 도달할 때까지 전체 리스트를 검색해 이전 블록의 위치를 기억하는 것. == 검색 시간이 상수가 될 수 없음

경계 태그 기법은 상수 시간 전에 이전 블록을 연결하게 해준다.

이 기법은 각 블록의 끝 부분에 풋터(footer - 경계 태그)를 추가하는 것으로, 이 풋터는 헤더를 복사한 것. 만약 각 블록이 이와 같은 풋터를 포함하게 되면, 할당기는 시작 위치와 이전 블록의 상태를 자신의 풋터를 조사해서 결정할 수 있으며 이건 항상 현재 블록의 시작 부분에서 한 워드 떨어진 곳에 위치.

 

~할당기가 현재 블록을 반환할 때 가능한 모든 경우~

1. 이전과 다음 블록이 모두 할당

2. 이전 블록은 할당 상태, 다음 블록은 가용 상태

3. 이전 블록은 가용 상태, 다음 블록은 할당 상태

4. 이전 블록과 다음 블록 모두 가용 상태

 

경계 태그 기법은 여러가지 유형의 할당기와 가용 리스트 구성에도 일반화될 수 있지만, 잠재적인 단점이 존재.

각 블록이 헤더와 풋터를 유지해야 하므로, 만일 응용이 많은 작은 크기의 블록을 다룬다면 상당한 양의 메모리 오버헤드가 발생할 수 있다.

풋터가 할당된 블록에 있을 필요를 없애는 경계 태그를 영리하게 최적화하는 방법이 존재하는데, 현재 블록을 메모리에 있는 이전과 다음 블록과 연결하려 할 때, 만일 이전 블록이 가용한 경우에만 이전 블록의 풋터에 size 필드가 필요하다는 점을 기억할 수 있다. 현재 블록의 추가적인 하위 비트들 중 하나에 이전 블록의 할당/가용 비트를 저장하려 한다면, 할당된 블록들은 풋터가 필요 없어지고, 추가적인 공간을 테이터를 위해 사용할 수 있을 것

but! 가용 블록은 여전히 풋터를 필요로 한다는 점에 유의해야 함

 

일단 끘!! 🤩