[CSAPP] 9-9 동적 메모리 할당(Dynamic Memory Allocation)

CSAPP 9-9 동적 메모리 할당(Dynamic Memory Allocation).pdf

2.06MB

나머지 9.9의 자세한 내용은 pdf 파일을 참고해주세용~

Intro

• 동적 메모리 할당기는 힙 (heap)이라는 프로세스의 가상메모리 영역을 관리한다.
• 커널은 힙의 꼭대기를 가리키는 변수 brk("break")를 사용
• 할당기는 힙을 다양한 크기의 블록들의 집합으로 관리

메모리 구조 잠깐 정리

• Code 영역(.text) : 실행할 프로그램의 작성한 코드들이 담긴다.
• Initialized Data 영역 (.data) : 초기화된 전역 변수 및 정적 변수가 저장되는 공간
  • ex) int x = 10;
• Uninitialized Data 영역 (.bss) : 초기화되지 않은 전역 변수 및 정적 변수가 위치하는 영역
  • ex) int x;
• Heap 영역 : 동적으로 할당되는 메모리 공간
  • 프로그램이 실행되는 동안, 런타임에 필요할 때 메모리를 동적으로 할당하기 위해 사용한다.
  • 힙의 꼭대기를 brk(break)라는 변수를 가리켜서 사용한다
  • ex) int *ptr = malloc(10 * sizeof(int));
• Stack 영역 : 함수 호출과 로컬(지역) 변수들을 저장하는 공간, 함수가 종료되면 이 데이터는 스택에서 제거
  • 스택은 위에서 아래로 자란다.
  • ex) 함수의 지역 변수, 함수의 호출 스택

(참고) 메모리에서 힙과 스택의 차이

특징	힙(heap)	스택(stack)
메모리 관리	프로그래머가 직접 할당하고 해제해야 함	함수 호출 시 자동으로 할당/해제됨
속도	느림 (동적 할당이므로 시스템 호출 필요)	매우 빠름 (컴파일러가 관리)
메모리 크기	제한 없음 (시스템 메모리만큼 할당 가능)	제한적 (스택 크기는 일반적으로 고정)
단편화	단편화 발생 가능	단편화 없음
수명	프로그래머가 직접 관리	함수의 호출이 끝나면 자동으로 해제됨

할당기 유형 2가지

명시적인 할당기

• 명시적으로 할당된 블록을 반환해 줄 것을 요구한다.
• C언어 malloc 패키지 활용
  • malloc 함수를 호출해서 블록을 할당
  • free 함수를 호출해서 블록을 반환

묵시적 할당기

• 언제 할당된 블록이 더 이상 프로그램에 의해 사용되지 않고 블록을 반환하는지를 할당기가 검출할 수 있을 것을 요구
• 가비지 컬렉터 (garbage collector)
  • 자동으로 사용하지 않은 할당된 블록을 반환시켜주는 작업 : 가비지 컬렉션
  • java 가비지 컬렉터

9.9.1 malloc과 free 함수

#include <stdlib.h> 
void *malloc(size_t size);

정렬

• malloc은 gcc의 컴파일 모드에 따라 다르다.
  • 32 bit : 8의 배수인 블록을 리턴
  • 64 bit : 16의 배수인 블록을 리턴
• 워드는 얼마나 큰가?
  • 3장에서 인텔이 4바이트 객체를 더블 워드라고 말했지만 이번 절에서는 워드는 4바이트 객체이고 더블 워드는 8바이트 객체로 가정한다. 일반적인 용어와 일관성을 가진다.

동적 할당 메모리의 종류

• malloc : 블록 내에 포함될 수 있는 어떤 종류의 데이터 객체에 대해서 적절히 정렬된 최소 size바이트를 갖는 메모리 블록의 포인터를 리턴
  • malloc 문제를 만날 시에 null 리턴 후 errno를 설정
  • malloc은 리턴하는 메모리를 초기화하지 않는다.
• calloc : 할당된 메모리를 0으로 초기화
• realloc : 이전에 할당된 블록의 크기를 변경

sbrk 함수

• malloc 같은 동적 메모리 할당기는 mmap과 munmap 함수를 사용해서 명시적으로 힙 메모리를 할당하거나 반환한다.
  • mmap : 가상 메모리 영역에서 페이지 단위로 할당(대용량 메모리 할당 또는 파일 입출력에 적합하다)
  • munmap () 함수로 할당 해제
• mmap과 munmap 대신 sbrk 함수를 사용 할 수 있다.
• #include <unistd.h> void *sbrk(intprt_t incr);
• sbrk 함수는 커널의 brk 포인터에 incr을 더해서 힙을 늘리거나 줄인다.
• 성공하면 brk 값을 리턴하고, 아니면 -1을 리턴하고 errno를 ENOMEM으로 설정
• 만일 incr이 0이면, sbrk는 현재의 brk 값을 리턴

#include <stdlib.h>
void free(void *ptr);

• 프로그램들은 할당된 힙 블록을 free 함수를 호출해서 반환
• ptr 인자는 malloc, calloc, realloc에서 획득한 할당된 블록의 시작을 가리켜야 한다.

malloc과 free를 사용해서 블록을 할당하고 반환시키기

• (a) 4워드 블록 요청
  • 이 블록의 첫 번째 워드를 가리키는 포인터 리턴
• (b) 5워드 블록 요청
  • 더블 워드 경계에 정렬되도록 하기 위해 블록에 추가적인 워드를 패딩
  • 총 6워드 요청( 5워드 + 1(패딩) )
• (c) 6워드 블록 요청
• (d) p2 반환
  • p2가 새로운 malloc 콜에 의해 다시 초기화될 때까지 p2를 사용하지 않음
• (e) 워드 블록 요청
  • 이전 단계에서 반환된 블록의 부분을 할당하고 새로운 블록의 포인터를 리턴

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

동적 메모리 할당을 사용하는 이유

프로그램 실행전에 자료구조의 크기를 알 수 없는 경우들이 있기 때문

#inclue  "csapp.h"
#define MAXN 15213

int array[MAXN];

int main()
{
    int i ,n;
    scanf("%d", &n);
    if (n > MAXN)
        app_error("Input file too big");
    for (i=0; i<n; i++)
        scanf("%d",&array[i]);
    exit(0);
}

위 방법은 MAXN 값을 임의로 정했기 때문에 실제 사용한 메모리 크기와는 무관함 또 MAXN보다 큰 파일을 읽으려면 MAXN 값을 수정해서 다시 컴파일 해야함

#include "csapp.h"

int main(){ 
int *array, i, n; 
scanf("%d", &n); 
array = (int *)Malloc(n * sizeof(int)); 
for(i = 0; i < n; i++) 
    scanf("%d", &array[i]); 
free(array);
exit(0);

9.9.3 할당기 요구사항과 목표

명시적 할당기의 제한사항

임의의 요청 순서 처리하기

• 할당기는 할당과 반환 요청의 순서에 대해서는 아무 가정도 할 수 없다.
• 요청 순서에 관계없이 처리되어야 한다. malloc과 free가 연속된다는 보장이 없다.
• 할당과 반환 요청이 언제 어떻게 올 지 모르니 요청 오는대로 처리할 수 있어야함

요청에 즉시 응답하기

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

힙만 사용하기

• 확장성을 갖기 위해서는 할당기가 사용하는 힙 자체에 저장되어야 한다.

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

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

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

• 가용 블록을 조작하거나 변경할 수만 있다.
• 이미 블록이 할당되면 이들을 수정하거나 이동하지 않는다.

=> 이러한 제한사항들로 인해 처리량과 메모리 이용도를 최대화하려는 종종 상충되는 성능 목표를 달성하기 위해 노력한다.

목표

목표 1) 처리량 극대화 하기

• 할당과 반환 요청들을 만족시키기 위한 평균 시간을 최소화해서 처리량을 최대화한다.

목표 2) 메모리 이용도를 최대화 하기

• 최고 이용도(peak utilization)

9.9.4 단편화

나쁜 힙의 이용도의 주요 이유는 단편화이다. 가용 메모리가 할당 요청을 만족시키기에는 가용하지 않았을 때 일어난다. 내부 단편화와 외부 단편화가 있다.

내부 단편화

• 할당된 블록이 데이터 자체보다 더 클 때 일어난다.
  • 할당기의 구현이 요청한 데이터보다 더 큰 할당된 블록들에 최소 크기를 부여할 수 있다. 정렬 제한사항을 만족시키기 위해 블록의 크기를 증가시킬 수 있다.
  • • ex) 진한 파랑색 부분의 패딩 바이트
• 내부 단편화는 정량화하기 간단하다.
  • 할당된 블록의 크기와 이들의 데이터 사이의 차이의 합
  • 내부 단편화의 양은 이전에 요청한 패턴과 할당기 구현에만 의존한다.

외부 단편화

• 메모리 공간이 전체적으로 공간을 모으면 충분한 크기가 존재하지만, 이 요청을 처리할 수 있는 단일한 가용블록이 없는 경우에 발생한다.
• 예를 들어
  • 2워드가 아니라 8워드에 대해서였다면 힙에 8개의 가용 워드가 남아 있는데도 커널에서 추가적인 가상 메모리를 요청하지 않고는 만족시킬 수 없었다.
• 외부 단편화는 내부 단편화보다 훨씬 더 측정하기 어렵다.
  • 이전 요청의 패턴과 할당기 구현에만 의존하는 것이 아니라 미래의 요청 패턴에도 의존하기 때문