동적 메모리 할당

김현진·2022년 5월 13일

9.9.1 malloc과 free 함수

malloc이란 c의 동적 메모리할당, dynamic memory allocation을 의미하며, 컴퓨터의 가상메모리(virtual memory), 즉 heap을 관리한다. 메모리를 할당시키고 프리(free)시키며 메모리를 정확하고, 효율적이고, 빠르게 관리하는 것이 핵심이다.

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

프로그램을 실행시키기 전까지는 얼마만큼의 메모리가 필요한지 모르기 때문이다.

적은 메모리를 할당하면 프로그램 에러가 생기는데, 그렇다고 처음부터 너무 많은 메모리를 할당하면 메모리가 낭비된다. 따라서, 런타임에 필요한 크기가 주어질 때마다 메모리를 동적으로 할당하게 된다.

동적 메모리 할당에는 두 가지 유형이 있다.

명시적 할당기
- 응용이 명시적으로 할당된 블록을 반환해줄 것을 요구
- C 표준 라이브러리는 malloc 패키지를 제공
묵시적 할당기
- 가비지 컬렉터(garbage collector)
- 할당기가 자동으로 사용하지 않은 할당된 블록을 반환시키는 작업을 가비지 컬렉션이라고 부름
- List, ML, 자바에서 사용

9.9.3 할당기 목표

할당기는 할당기 처리량과 메모리 최고 이용도 간 균형을 찾으려고 한다.
시간 당 처리하는 요청을 극대화하면서도, 메모리를 효율적으로 사용해야 한다.

이를 위해 이용도(peak utilization)라는 지표를 사용한다. 힙을 얼마나 효율적으로 쓰고 있는지를 측정하는 척도이다.

9.9.4 단편화

할당된 부분들은 얼마든지 연속적으로 붙어있거나 떨어져있을 수 있다.

이 상황에서 5워드 데이터를 넣으려고 하면 실패하게 되는데,
총 공간을 계산해봤을 때 충분한 메모리가 있음에도, 빈 공간들이 연속적이지 않아 할당할 수 없는 상황을 External Fragmentation(외부 단편화) 라고 한다.

외부단편화를 해결하기 위해서 메모리를 동일한 크기로 잘라서 그 동일한 크기로 할당하게 되는 방법을 생각해보자. 그러면 그 빈 공간들은 생기지 않게 된다. 반면 들어오는 데이터보다 필요 이상으로 데이터를 할당하게 되어, 할당된 데이터 내에 빈 공간이 생기게 되는데 이를 Internal Fragmentation(내부 단편화) 라고 한다.

9.9.5 구현이슈

이러한 단편화 현상을 방지하기 위해 고려해야 될 점이 있다.

가용 블록 구성: 할당할 메모리의 크기와 위치 등
배치: 가용 블록의 선택, 배치 공간 찾기
분할: 가용 블록의 나머지를 활용
연결: 반환된 블록의 관리

9.9.6 묵시적 가용리스트

이러한 사항을 고려하면서 메모리 관리를 효과적으로 하고자 block(블록) 이라는 단위를 사용한다.

Header: 블록의 시작점. 블록 사이즈와 할당 여부를 표시한다. 워드가 8byte이므로 마지막 세 비트(000)은 비어있게 되는데, 이 자리를 활용하여 블록의 할당(001) 또는 해제(000)를 표시하는 데 사용한다.
Payload: 실제 데이터가 들어가는 부분. 워드 단위로 반올림하여 저장한다.
Padding(optional): 사용하지 않는 공간. 정렬할 때의 조건에 맞추기 위해서 또는 외부단편화를 극복하기 위해서 등의 이유로 패딩을 붙여줄 수 있다.
Footer: 블록의 끝점. header의 정보와 동일한 정보를 갖는다.
Previous or Next free block pointer: 이중 연결리스트의 형태로 가용리스트를 관리하는 방식을 사용할 때 구성하는 항목. 가용리스트에는 할당이 해제된 블록의 포인터들이 저장되어 있다.
block pointer: header 칸의 바로 뒤 주소. 이를 활용하여 메모리가 저장된 위치를 찾는다.

9.9.7 할당한 블록의 배치

First fit
list를 앞부터 탐색해서 처음 만나는 가용 블록을 선택
Next fit
이전에 검색이 종료된 지점에서 검색을 시작
Best fit
모든 블록을 탐색하여 가장 적절한 블록 선택

9.9.8 가용 블록의 분할(Splitting)

배치 공간을 찾은 후, 가용 블록을 얼마나 활용할지 판단해야 한다.

가용 블록 전체 사용
간단하고 빠르지만, 내부 단편화가 생긴다.
남은 부분으로 새로운 가용 블록 구성
내부 단편화가 줄어들지만, 인접 가용블록의 오류 단편화가 생긴다.
인접한 가용 블록을 병합해주지 않으면, 충분한 메모리가 있음에도 불구하고 할당하지 못하게 된다. 따라서 Coalescing(연결)이 필요하다.

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

할당기가 요청하는 크기의 블록을 찾을 수 없는 경우

Coalescing으로 더 큰 가용 블록으로 만든 후 할당
sbrk 함수 호출하여 힙 메모리 요청

9.9.10 가용 블록 연결하기(Coalescing)

Immediately Coalescing(즉시 연결)
블록이 반환될 때마다(Free) 이전 블록을 통합
쓰레싱 가능성 있음

Deferred Coalescing(지연 연결)
할당 요청이 실패할 때까지 연결을 지연. Free의 퍼포먼스를 증진시키기 위해 연결이 필요한 시점까지 연결을 지연

Coalescing은 다음 네 가지 case를 가진다.

case1: 앞 뒤 모두 할당 되었을 때 -> 그냥 독립적인 블록
case2: 앞은 프리 뒤는 할당 -> 앞에 블록과 합쳐준다.
case3: 앞은 할당 뒤는 프리 -> 뒤에 블록과 합쳐준다.
case4: 앞 뒤 모두 프리 -> 앞뒤 블록과 합쳐준다.

9.9.11 경계 태그로 연결하기

반환된 블록을 다음 가용블록과 연결하는 것은 header를 이용하면 간단하다. 반면 이전의 블록과 연결하는 것은 상수시간 내에 불가. 따라서 Footer를 추가하여 이전 블록 상태 쉽게 조사할 수 있도록 한다.

Implicit, Explicit, Segreagated

Implicit은 모든 block을 연결시킨다.
그래서 탐색하는데 블록 갯수만큼의 연산이 필요하다.

Explicit은 모든 free block을 연결시킨다.
그래서 탐색하는데 프리 블록의 갯수만큼의 연산이 필요하다. 이 때 프리 블록들은 이중리스트로 연결되어있어야한다. 새로운 블록을 stack처럼 맨 앞으로 LIFO 구조로 연결 시킬 수 있고, 블록의 주소값 순서로 정렬시켜 연결시키는 방법이 있다.