동적 메모리 할당(1) | 개요

동적 메모리 할당

• 동적 메모리 할당은 컴퓨터 프로그램의 실행 중에 추가적인 메모리 공간이을 할당하는 것을 말한다.
• 동적 메모리 할당을 사용하는 가장 큰 이유는 프로그램을 실제로 실행시키기전에 자료 구조의 크기를 정확히 알 수 없는 경우들이 있기 때문에 프로그램 실행중에 자료 구조를 메모리 상에 할당시키기 위함이다.
• 동적 메모리 할당기는 가상 메모리인 heap (힙)을 관리한다.
• 할당기는 힙을 다양한 크기의 블록들의 집합으로 관리한다.
• 각 블록은 할당되었거나 가용한 가상 메모리의 연속적인 묶음이다.

동적 메모리 할당기의 유형

• 할당기는 기본적으로 2개의 기본 유형이 있다.
  두 유형 모두 명시적으로 블록을 할당하도록 요구한다. 하지만 할당된 블록을 가용 블럭으로 반환하는 방식이 다르다.
  • 명시적 할당기 : C언어의 표준 라이브러리 stdlib에서 사용되는 malloc과 free처럼 명시적으로 메모리의 할당과 반환을 호출한다.
  • 묵시적 할당기 : 언제 프로그램이 할당된 블록을 사용하지 않고 반환하는지를 검사한다.

동적 메모리 할당기의 요구 조건

• 임의의 요청 순서 처리하기
  • 할당기는 이 후에 할당 및 반환 요청이 들어올지 모른다. 따라서 할당기는 할당과 반환 요청이 연속될지 짝이 맞춰질지 아무것도 가정할 수 없다.
• 요청에 즉시 응답하기
  • 할당기는 어떤 종류의 데이터 객체라도 메모리 할당 및 반환을 할 수 있도록 해야한다.
• 힙만 사용하기
  • 확장성을 갖기 위해서 할당기가 사용하는 비확장성 자료 구조들은 힙 자체에 저장되어야 한다.
• 블록 정렬하기 (정렬 조건)
  • 할당기는 어떠한 조류의 데이터 객체도 저장할 수 있도록 해야한다.
• 할당된 블록 수정하지 않기
  • 할당기는 가용 블록을 조작하거나 변경할 수 있다. 하지만 할당된 블록에 대해서는 수정이나 이동을 할 수 없다.

동적 메모리 할당기의 목표

• 처리량 극대화하기
  • 500개의 할당 요청과 500개의 반한 요청을 1초동안 완료하면 해당 할당기의 처리량은 초당 1,000 연산이 된다.
• 메모리 이용도 최대화하기
  • 한 시스템에 할당된 가상 메모리의 양은 디스크 내의 스왑 공간의 양에 의해 제한되므로, 가상 메모리를 효율적으로 사용하는 것은 중요하다.
  • 따라서 최고 이용도를 척도로하여 할당기가 힙을 얼마나 효율적으로 사용하는지 규정하고 확인한다.

프로그램이 할당기에게 메모리에게 할당해달라고 하는 데이터의 크기를 payload라고 한다. 프로그램이 10 의 크기를 가진 블럭(payload)을 요청하면 할당기는 free 블럭 중에서 적어도 10 의 크기를 가진 블럭을 찾아서 할당을 한다. 여기서 적어도 라고 한 이유는 할당기의 구현 방법에 따라 단편화 및 할당기의 요구조건 및 목표를 만족하기 위해 header, footer, successor, predecessor 등의 오버헤드 가 발생된다. 이런 오버헤드는 메모리의 최고 이용도를 낮춘다. 따라서 할당기를 구현하는 사람들은 불필요한 데이터를 최소한으로 만들고자 한다.

• 처리량 극대화와 메모리 이용도 최대화는 상층되는 성능 목표이기 때문에 이 둘 사이의 적절한 균형을 찾는 것이 중요하다.

단편화

나쁜 힙 이용도의 주요 이유는 단편화이다. 단편화에는 내부 단편화와 외부 단편화가 있다.

내부 단편화

• 할당된 블록이 데이터 자체보다 더 클 때 일어난다.
• 할당된 블록에서 할당을 요구한 데이터를 제하더라도 다른 메모리를 할당받을 수 있는 크기라면 해당 블록을 쪼개서 작은 두 개의 블록으로 나누는 방법 등을 통해서 내부 단편화를 해결할 수 있다.
  • 이 후 동적할당기를 c언어로 구현할 때 place()에서 이 작업을 수행한다.

외부 단편화

• 할당 요청을 만족시킬 수 있는 메모리 공간이 남아있는 가용 블럭의 크기를 모두 합쳤을 때는 충분한 크기가 존재하지만, 이 요청을 처리할 수 있는 단일 가용 블럭은 없는 경우 발생한다.
• 외부 단편화는 이 후에 어떤 크기의 데이터를 할당 요청할지 모르기 때문에 예측하기 어렵다. 따라서 할당기들은 가능한 가용 블럭의 크기를 크게 유지하고자 한다.
  • 이 후 동적할당기를 코드로 구현할 때 coalesce() 에서 인접한 두 가용 블럭을 하나의 가용 블럭으로 합치는 작업을 통해 가용 블럭의 크기를 가능한 크게 유지한다.

동적 할당기 구현시 고려 사항

• stdlib.h의 free() 를 통해 할당된 블럭을 반환하고자 하면 해당 포인터가 가리키고 있는 블럭의 크기를 어떻게 알까?
• free가 된 가용블럭들은 어디에 있는지 어떻게 알까?
• 할당 요청을 받아서 요청한 크기보다 큰 블록을 찾으면 블록에 남는 영역들은 어떻게 처리할까?
• 힙에 여러개의 가용 블럭이 있으면 할당기는 그 중 어떤 기준으로 가용 블럭을 고를까?