동적 메모리 할당
동적으로 메모리를 할당하는 가장 중요한 이유는, 프로그램을 실제 실행시키기 전에는
자료 구조의 크기를 알 수 없는 경우들이 있기 때문인데, 예를 들자면
어떤 배열에 값을 입력하기 전에 정적으로 선언해주는 경우이다.
#define 15213
...
...
int array[MAX]만일 사용자가 MAX보다 더 큰 파일을 읽으려고 한다면 에러가 발생하고,
이를 해결하기 위해서는 MAX에 더 큰 값을 지정하여 다시 컴파일 해야한다.
미리 n값을 알 수 있다면 배열을 런타임에 동적으로 할당하는 것이 더욱 유용하고 효율적인 방법이라고 알려져있다.
동적 메모리 할당기는 힙(Heap)이라고 하는 프로세스의 가상메모리 영역을 관리한다.
동적 메모리 할당기 요구사항과 목표
-
묵시적 할당기 : 자동으로 사용하지 않은 할당된 블록을 반환 시켜주는 형태
-> 가비지 컬렉터(Gabage Collector)라고 알려져 있음 -
명시적 할당기 : 응용 프로그램이 명시적으로 할당된 블록을 반환해 줄 것을 요구하는 형태
-> 쉽게 말하자면 직접 할당 및 해제를 해주어야 하는 것인데,
예를 들어 C에서 malloc을 호출해서 블록을 할당하고, free 함수를 통해 직접 블록을 반환하는 형태이다.
할당기 요구사항
1. 임의의 요청 순서 처리하기 및 요청에 즉시 응답 : 할당과 반환 순서에 상관없이 순차적으로 요청에 응답해야한다. (할당 및 해제)
2. 블록 정렬하기(정렬요건) : 할당기는 블록들이 어떤 종류의 데이터 객체라도 저장할 수 있는 방식으로 정렬해야 함
3. 힙만 사용하기 : 할당기가 사용하는 비확장적인 자료 구조들은 힙 자체에 저장되어야 함
4. 할당된 블록을 수정하지 않기 : 일단 블록이 할당되면 임의로 이들을 수정하거나 이동하지 않아야 함
할당기 목표
메모리(가상메모리)는 무한하지 않다. 가상메모리의 크기는 디스크 내의 스왑 공간의 양에 의해 제한되므로
최대한 많은 양의 데이터를 적재하기 위해, 할당과 해제를 통해 적절한 균형을 맞춰주어야 한다.
구현 이슈
- 힙 영역을 늘릴 수 있어야 한다.
- 가용 블록 여부를 알 수 있어야 한다.
- 새롭게 할당하기 위해 적절한 가용 블록을 선택할 수 있어야 한다.
- 블록을 할당한 후 남는 부분들을 처리해야 한다.
- 할당이 해제된 블록을 적절하게 합쳐야 한다.
단편화 문제
힙 이용도를 낮추는 주된 원인은 단편화 (fragmentation) 현상 때문인데,
두 종류의 단편화가 존재한다.
- 내부 단편화 (internal fragmentation)
- 외부 단편화 (external fragmentation)
- 내부 단편화
- 내부 단편화는 할당된 블록(Payload)이 데이터보다 클 때 발생하게 된다.
- 외부 단편화
- 할당 요청을 만족시킬 수 있는 메모리 공간이 전체적으로 공간을 모았을 때는
충분한 크기가 존재하지만, 이 요청을 처리할 수 있는 단일한 가용블록이 없는 경우이다.
How to Work on the Lab
CMU의 malloc-lab project에서 구현해야 하는 기능은 다음과 같다.
int mm_init(void);
void mm_malloc(size_t size);
void mm_free(void ptr);
void mm_realloc(void ptr, size_t size);
1. mm_init(void)
malloc 혹은 realloc을 호출하기 전에 init을 호출하여 초기 힙 할당과 같은 필수적인 초기화를 수행하는 역할.
초기화 수행 과정에서 문제가 있다면 -1, 그렇지 않다면 0을 리턴하도록 구성해야 한다.
2. *mm_malloc(size_t size)
최소 size 바이트를 갖는 메모리 블록을 할당하고, 포인터를 리턴하는 역할
할당된 전체 블록은 힙 영역 내에 존재해야 하며, 다른 할당된 블록과 겹치지 않아야 한다.
추가적인 특성으로는 malloc은 리턴하는 메모리를 초기화 해주지 않는다.
(초기화한 동적 메모리를 원한다면 calloc을 사용할 수 있음)
만약 malloc을 호출하고 문제가 발생했을 경우에는 NULL을 리턴하고 errno를 설정한다.
(예를 들면, 프로그램이 가용한 가상 메모리보다 더 큰 메모리 블록을 요청하는 경우)
3. mm_free(void ptr)
ptr이 가리키는 블록을 해제하는 역할. ptr
아무것도 반환하지 않음.
4. void mm_realloc(void ptr, size_t size)
이미 할당된 메모리의 블록을 늘리거나 줄이기 위한 역할
이어지는 포스팅에서는 묵시적 할당기(implicit)와 명시적 할당기(explicit)를 구현하는 방법을 작성한다.
