. 9.9.2 왜 동적 메모리 할당인가? / 9.9.3 할당기 요구사항과 목표
본문 바로가기
프로그래밍 공부/CSPP

9.9.2 왜 동적 메모리 할당인가? / 9.9.3 할당기 요구사항과 목표

by 불냥이_ 2021. 1. 15.

우선 정수를 하나씩 입력받는 함수를 만들어보자.

1 #include "csapp.h"
2 #define MAXN 15213
3
4 int array[MAXN];
5
6 int main()
7 {
8 int i, n;
9
10 scanf("%d", &n);
11 if (n > MAXN)
12 app_error("Input file too big");
13 for (i = 0; i < n; i++)
14 scanf("%d", &array[i]);
15 exit(0);
16 }

 

이 함수는 시작할 떄, 15213칸의 array를 선언한다. 

만약 정수를 10개만 입력하고 싶다면 15203칸이 낭비될 것이고, 15214개의 정수를 입력하고 싶다면 성립되지 않는다.

/* 이것이 stack메모리 인가? */

 

그렇기에 우리는 유동적으로 메모리를 할당할 수 있도록 해야한다.

1 #include "csapp.h"
2
3 int main()
4 {
5 int *array, i, n;
6
7 scanf("%d", &n);
8 array = (int *)Malloc(n * sizeof(int));
9 for (i = 0; i < n; i++)
10 scanf("%d", &array[i]);
11 free(array);
12 exit(0);
13 }

이렇게 하면 입력하는 정수의 갯수에 대해서 정확히 그에 해당하는 메모리를 할당함으로서 효율적으로 메모리를 관리할 수 있게된다.

 

 

이제 명시적 할당기(Explicit allocators)의 제한사항에 대해서 알아보자. 

 

1. 임의의 요청순서 처리하기

 할당기 자체는 응용프로그램이 어떠한 순서로 할당/반환 요청을 하는지 알 수 없으며, 할당들어왔던 것이 꼭 반환될 것이라고 가정할 수 없다. 즉, 할당 요청이 들어온다면 (이것이 반환된다거나, 다음 할당도 동일한 사이즈가 들어온다는 등의) 어떠한 가정을 하지 않고 그 할당 요청에만 대응해야한다. (그리디 알고리즘?)

 

2. 요청에 즉시 응답하기

 할당기는 할당/반환 요청이 들어왔을 때, 즉시 그 요청을 시행해야한다.

 

3. 힙만 사용하기

 확장성을 갖기 위해서 할당기가 사용하는 비혹장성 자료 구조들은 힙 자체에 저장되어야한다. (확장성이란 무엇인가?)

 

4. 블록 정렬하기

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

 

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

 할당기는 가용 블록을 조작하거나 변경할 수는 있지만, 일단 블록이 할당되면 수정하거나 이동하지 않는다.

 

 

할당기가 얼마나 힙을 효울적으로 사용하는지를 규정하는 방법 중에서 가장 유용한 단위는 최고 이용도peak utilization이 있다.

 

그림 2. 힙의 이용도

간단하게 말하면, 이용도U = ( 실제로 사용하는 힙의 크기maxPi ) / ( 할당된 힙의 크기Hk ) 이다.

즉, U = 1이면 낭비되는 것이 없이 힙을 온전히 그대로 사용하고 있고, U=0 이라면 (이럴 경우가 있으면 안되겠지만) 실제로 사용되는 힙이 없음에도 불구하고 힙이 할당되어 있는 것이다. 

 

 

댓글