CSAPP - 동적 메모리 할당

동적 메모리 할당

프로그램을 실행 시키기 전에는 자료 구조의 크기를 알 수가 없는 경우가 존재하는데
추가적인 가상메모리를 획득할 필요가 있을 때
런타임에 메모리를 할당하는 것을 동적 메모리 할당이라고 한다.

큰 사이즈의 고정된 배열의 크기를 사용할 수도 있겠지만
고정된 배열보다 더 큰 사이즈가 들어오면 할당할 수 없는 상태인 단편화의 문제가 생길 수 있고
큰 규모의 소프트웨어 제품에서는 관리 하는데에 어려움을 초래할 수 있기 때문에
들어 올 값을 알고 있을 시점인 런타임 때에 할당하는 것이 좋은 방법이다.

각각의 프로세스에 대해서, 커널은 힙의 꼭대기를 가르키는 변수 brk (break)를 사용합니다.
할당기는 힙을 다양한 크기의 블록들의 집합으로 관리합니다.

명시적 할당기

명시적 할당기 : 명시적으로 할당된 블록을 반환해 줄 것을 요구
C 표준 라이브러리는 malloc 패키지라고 하는 명시적 할당기를 제공한다.
malloc 함수를 호출해서 블록을 할당하며 free 함수를 호출해서 블록을 반환합니다.

묵시적 할당기

묵시적 할당기 : 할당된 블록이 더 이상 사용되지 않을때
블록을 언제 반환하는지를 할당기가 검출 할 수 있을 것을 요구
묵시적 할당기는 가비지 컬렉터(garbage collector)라고 알려져 있으며,
자동으로 사용하지 않은 할당된 블록을 반환시켜주는 작업을 가비지 컬렉션이라고 부른다.
Java, Javascript 등의 고급 언어들은 할당된 블록들을 반환시키기 위해서 가비지 컬렉션을 사용한다.
그렇다고 해당 언어들이 가비지 컬렉션이 무조건 된다고 보면 안된다.
전역변수 등의 사용하는 방법에 따라서 메모리 누수가 발생 할 수 있음을 유의하는 것이 좋다.

할당기의 요구사항과 목표

1. 임의의 요청 순서로 처리하기
2. 요청에 즉시 응답하기
3. 힙만 사용하기
4. 블록 정렬하기
5. 할당된 블록을 수정하지 않기

이러한 제한 사항을 가지고 작업하기 위해서 할당기 개발자는
처리량과 메모리 이용도를 최대화 하려는 상충되는 성능 목표의
적절한 균형을 찾아서 달성하기 위해 노력해야 한다.

메모리 관련 함수

malloc 함수

C 표준 라이브러리는 malloc 패키지로 알려진 명시적인 할당기를 제공한다.
malloc 함수는 블록 내에 포함될 수 있는 어떤 종류의 데이터 객체에 대한
적절히 정렬된 최소 size 바이트를 갖는 메모리 블록의 포인터를 리턴한다.
32비트 모드에서는 8의 배수인 블록을, 64비트 모드에서는 16의 배수인 블록을 리턴함

가용한 가상메모리보다 더 큰 크기의 메모리 블록을 요청하는 경우 NULL을 리턴하고 errno를 설정

malloc은 리턴하는 메모리를 초기화 하지 않고 calloc을 사용하면 메모리를 초기화 할 수 있다.
mmap 함수와 munmap 함수를 사용해서 명시적으로 힙메모리를 할당하거나 반환하며
또는 sbrk 함수를 사용할 수 있다.

mmap 함수

mmap 함수를 사용하면 파일을 프로세스의 가상 메모리에 매핑할 수 있다.
mmap 함수는 매핑할 메모리의 위치와 크기를 인자로 받는다.
메모리에 매핑된 데이터는 파일 입출력 함수를 사용하지 않고 직접 읽고 쓸 수 있다는 장점이 있다.

munmap 함수

munmap 함수는 mmap 함수를 사용해 매핑한 메모리 영역을 해제합니다.
메모리 매핑이 해제된 메모리 영역에 다시 접근하려고 하면 오류가 발생하므로 주의해야 합니다.

sbrk 함수

sbrk 함수는 커널의 brk 포인터에 incr을 더해서 힙을 늘리거나 줄인다.
성공하면 brk 값을 리턴하고 실패하면 -1을 리턴하고 errno를 ENOMEM으로 설정

free 함수

free 함수의 *bp 인자는 malloc, calloc, realloc에서 획득한
할당된 블록의 시작을 가리켜야한다. 그렇지 않다면 free의 동작은 정의되지 않는다.
아무것도 리턴하지 않아서 잘못된 사실도 알려주지 않아서 사용에 주의해야 한다.

메모리 단편화

가용 메모리가 할당 요청을 만족시키기 어려울 때를 말한다.
단편화에는 내부 단편화와 외부 단편화가 있다.

내부 단편화는 주기억장치 내 사용자 영역이 실행 프로그램보다 커서
프로그램의 사용 공간을 할당 후 사용되지 않고 남게 되는 현상을 말한다. 

외부 단편화는 전체적으로 여러 가용 공간을 모았을 때는 충분한 크기가 존재하지만
할당 할 수 있는 단일한 가용블록은 없는 경우에 발생한다.
외부 단편화가 측정하기 어렵고 예측하기 불가능하기 때문에
할당기들은 적은 수의 더 큰 가용 블록을 유지하려는 방법들을 채택한다.

할당한 블록의 배치 정책

검색을 수행하는 방법은 배치 정책에 의해 결정된다.
이 정책에는 first fit, next fit, best fit이 주로 사용된다.

1. first fit : 가용 리스트를 처음부터 검색해서 크기가 맞는 첫 번째 가용 블록을 선택

2. next fit : first fit과 비슷하지만 이전 검색이 종료된 지점에서 검색해서 블록을 선택
   first fit보다 매우 빠른 속도를 가지지만 최악의 메모리 이용도를 갖는다.

3. best fit : 모든 가용 블록을 검사하며 크기가 맞는 가장 작은 블록을 선택
   다른 두 정책에 비해 좋은 메모리 이용도를 보이지만 힙을 완전히 다 검색 해야된다는 단점이 있다.
   이 정책의 단점을 개선한 것이 복잡한 다단 가용 리스트(segregated free list) 입니다.

블록 검사 방법

1. Implicit

implicit 방법은 순차적으로 모든 블록을 검사하는 선형적인 방법
처음 블록부터 차례대로 검사하는 first-fit방식보다 next-fit 방식을 사용하면 성능이 매우 향상 됩니다.

heap의 가장 처음에는 16바이트 크기를 맞춰주기 위해 initial block(4바이트)을 설정 해주고
다음엔 힙의 처음과 끝을 알 수 있게 하는 Prologue Block(8바이트)과, Epliogue Block(4바이트)을 설정 해주고 블록의 포인터(Block pointer)를 활용하여 탐색합니다.
Block pointer와 할당된 메모리의 주소가 같아 바로 반환하여 사용자에게 메모리가 저장된 위치를 바로 알려줄 수 있어 해당 위치로 잡습니다.

2. Explicit

할당이 해제 되어있는 블록들을 연결리스트로 관리해서 모든 블록을 검사하지 않고, 할당이 해제된 블록들만 검사, implicit에서 개선된 방법이지만 impicit에 next-fit 방식의 성능과 유사

implicit 방식에서 달라진 점은 가장 처음 블록에 header와 footer 이외에 prev & next block pointer가 추가 되었습니다. 해당 정보들을 이용하여 해제된 블록들을 연결리스트의 형태로 관리 합니다. 가장 앞 블록은 할당이 되어있는 블록으로 연결리스트에 들어가 있어 연결리스트의 끝점을 나타내는 역할을 수행합니다. 성능적인 측면에서는 LIFO 방식이, 단편화를 방지하기 위해서는 ordered-list 방식이 좋습니다.

3. Seglist

할당이 해제되어있는 블록들을 사이즈별(대부분 2의 n제곱 단위로)로 모아 여러개의 연결리스트 포인터를 힙에 저장하여 관리하는 방법, explicit에서 개선된 방법

할당이 해제된 블록을 유사한 사이즈의 블록들이 모여있는 리스트에서 찾기 때문에 빠른 속도로 찾을 수 있어 가장 성능이 좋습니다.

묵시적&명시적 가용리스트

1. 묵시적 가용리스트

힙을 연속된 할당 및 가용 블록의 배열로 구성한 것을 묵시적 가용리스트 라고 한다.

묵시적 가용리스트의 장점은 단순성이다.
묵시적 가용리스트의 단점은 탐색에 필요한 연산 비용이
힙에 있는 전체 할당된 블록과 가용 블록의 수에 비례한다.

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

추가적인 힙 메모리 획득

할당기가 요청한 블록을 찾을 수 없다면 sork 함수를 호출하여 추가적인 힙 메모리를 요청한다.
할당기는 추가 메모리를 한 개의 더 큰 가용 블록으로 만들고 가용 리스트에 삽입한 후에
요청한 블록을 새로운 가용 블록에 배치한다.

가용 블록의 분할

할당기가 크기가 맞는 가용 블록을 찾았을 경우 어느 정도를 할당할지에 대해 결정해야한다.
가용 블록 전체를 사용하는 정책을 사용하면 간단하고 빠르지만 큰 단점으로 내부 단편화가 생긴다.
그렇게 되는 것을 막기 위해 할당할 블록을 만들고 나머지 영역은 가용 블록으로 만들어 주면 된다.

가용 블록의 연결

할당기가 할당한 블록을 반환할 때 새롭게 반환되는 블록에 인접한 다른 가용 블록이 있을 수 있다.
추가적으로 할당할 때 인접한 블록을 연결(coalescing)하면 사용할 수 있지만 현재는 나눠진 작고 사용할 수 없는 블록의 상태가 되고 이것을 오류 단편화(false fragmentation) 라고 한다.

경계 태그

오류 단편화를 해결하기 위해 경계태그로 연결 해주면 된다.
경계 태그는 기존의 header와 footer를 추가하여
이전 블록 사이즈와 할당여부를 파악하기 용이하도록 만들어준다.
이 방법은 상수 시간에 이전 블록을 연결해준다.
하지만 작은 크기의 블록 사이즈를 여러개를 할당한다면
많은 header와 footer의 사용으로 인해 상당한 양의 메모리 오버헤드가 발생할 수 있다.
다행히 풋터가 할당된 블록에 있을 필요를 없애는 경계 태그를 영리하게 최적화 하는 방법으로
이 단점을 해결할 수 있다.

2. 명시적 가용 리스트

가용 블록들을 일종의 명시적 자료구조로 구성하는 것

가용 블록의 본체는 프로그램에서 필요하지 않기 때문에
이 자료 구조를 구현하는 포인터들은 가용 블록의 본체 내에 저장될 수 있다.
가용 블록 내에 pred(predecessor)와 succ(successor) 포인터를 포함하는
이중 연결 가용 리스트로 구성될 수 있다.

이중 연결 가용 리스트를 사용하면 first fit 할당 시간을 전체 블록 수에 비례하는 것에서
가용 블록의 수에 비례하는 것으로 줄일 수 있다.
그렇지만 블록을 반환하는 시간은 가용 리스트 내에서
어떤 정책으로 블록을 정렬하는냐에 따라 비례하거나 상수 시간을 가질 수 있다.

접근법 1 : 리스트를 새롭게 반환한 블록들을 리스트의 시작 부분에 삽입해서 후입선출(LIFO) 순으로 유지

LIFO 순으로 first fit 배치 정책을 사용하면, 할당기는 대부분의 최근에 사용된 블록들을 먼저 조사한다.
이 경우 블록의 반환은 상수 시간에 수행된다. 만일 경계 태그를 사용하면 연결도 상수 시간에 수행할 수 있다.

접근법 2 : 리스트를 주소 순으로 관리하기

블록의 반환은 적당한 선행블록을 찾는 데 선형 검색 시간을 필요로 한다.
절충은 주소 순서를 사용하는 first fit이 LIFO 순서를 사용하는 경우보다
best fit의 이용도에 근접하는 더 좋은 메모리 이용도를 가진다는 것

명시적 가용리스트의 단점

일반적으로 가용 블록들이 충분히 커서
모든 필요한 포인터뿐만 아니라 헤더, 추가적으로 푸터까지 포함해야 한다는 점,
최소 블록 크기가 커지고 잠재적인 내부 단편화의 가능성 증가

3. 분리 가용 리스트

분리 저장장치(segregated storage)는 다수의 가용 리스트를 유지하며,
각 리스트는 거의 동일한 크기의 블록을 저장

1. 간단한 분리 저장장치

주어진 크기의 적절한 가용 리스트를 검색해서 블록 전체를 할당
가용 블록들은 할당 요청을 만족시키기 위해 절대로 분할하지 않음

어떤 크기 클래스가 {17~23}로 정의되었다면 가용 리스트는 전적으로 32의 블록으로 구성
블록을 할당하고 반환하는 것이 모두 빠른 상수시간 연산
메모리 블록 내의 분할과연결이 불가하기에 블록당 오버헤드가 거의 없음

그러나 중요한 단점으로는 내부, 외부 단편화에 취약하다는 점이 있다.

2. 분리 맞춤(segregated-fit)

가용 리스트의 배열을 관리, 각 가용 리스트의 크기는 size 클래스에 연관
명시적 또는 묵시적 리스트로 구성
블록을 할당하기 위해 요청된 크기 클래스를 결정하고 크기가 맞는 블록을 위해 해당 가용 리스트를 first-fit 방식으로 검색한다. 만일 블록을 찾으면 블록을 분할하고, 나머지를 적당한 가용 리스트에 삽입
맞는 블록을 찾지 못하면 다음 크기의 클래스를 위한 가용 리스트를 검색하고 블록을 찾을 때까지 반복
가용 리스트 어느 곳에서도 맞는 블록을 찾지 못하면 추가적인 힙 메모리를 운영체제에 요청하고 새 힙 메모리에서 이 블록을 할당하며 나머지를 적절한 크기의 클래스에 배치
블록을 반환하기 위해서 적절한 가용 리스트에 배치하고 연결
분리 맞춤 방식은 C표준 라이브러리에서 제공되는 GNU malloc 패키지 같은 수준의 할당기에서 선택됨
빠르고 메모리 관리가 효율적이기 때문,
검색 시간이 줄어드는데 전체 힙이 아니라 힙의 특정 부분으로만 제한되어 메모리 이용도를 개선
first-fit 검색이 전체 힙을 best-fit 검색하는 것을 단순화 한 것이라 좋다.

4. 버디 시스템

각 크기 클래스가 2의 제곱인 특수한 경우의 분리 맞춤 방식

버디 시스템 할당기의 중요한 장점은 빠른 검색과 연결이다.
주요 단점은 블록 크기가 2의 제곱이라는 것은 상당한 내부 단편화를 유발 할 수 있다.
그래서 블록 크기가 사전에 2의 제곱이라고 알려진 경우에는 일정 효과를 거둘 수 있다.

작동원리

1. 요청된 메모리를 수용할 수 있는 최소한의 2의 제곱 블록의 크기를 찾는다.
   ex) 요청 메모리가 34K~64K라면 64K(2의 6제곱) 크기의 블록에 할당 해야함
2. 해당 블록이 없다면 해당 크기를 수용할 수 있는 (2의 7제곱 이상의) 첫번째 가용 블록을 찾고 그 블럭을 적정한 크기 64K(2의 6제곱)가 나올때 까지 재귀적으로 1/2 분할 해서 할당 한다.
3. 추가적으로 할당할 경우 분할하지 않아도 1번의 조건을 만족하는 블록 크기가 있다면 바로 맞는 위치에 할당
4. 없다면 최소한의 요청된 사이즈보다 재귀적으로 2배 더 큰 블록을 찾아서 2번 조건과 같이 실행

아래의 그림과 설명은 버디 시스템을 사용했을 경우에 작동원리 예시이다.

t = 0: 1024K 할당할 수 있는 블록을 만든다.
t = 1: 프로그램 A가 34K ~ 64K 크기의 메모리를 요청한다.
t = 2: 프로그램 B가 66K ~ 128K 크기의 메모리를 요청한다.
t = 3: 프로그램 C가 35K ~ 64K 크기의 메모리를 요청한다.
t = 4: 프로그램 D가 67K ~ 128K 크기의 메모리를 요청한다.
t = 5: 프로그램 C가 메모리를 해제한다.
t = 6: 프로그램 A가 메모리를 해제한다.
t = 7: 프로그램 B가 메모리를 해제한다.
t = 8: 프로그램 D가 메모리를 해제한다.

가비지 컬렉션(garbage collection)

자동으로 힙 저장장치를 반납하는 과정을 가비지 컬렉션이라고 한다
주기적으로 가비지 블록을 식별하고 가용 리스트로 돌려주기 위해 적절하게 free를 홈출
Java, ML, Perl, Mathmatica 같은 현대 언어 시스템에서 중요한 부분을 차지

가비지 컬렉터(garbage collector)

더 이상 프로그램에서 사용하지 않는 블록들을 자동으로 반환하는 동적 저장장치 할당기

참고문헌

1. CSAPP
2. 버디 메모리 할당
3. emplam27님의 블로그