[시스템프로그래밍] 동적 메모리 할당

메모리는 무한한 자원이 아니고, 할당되고 관리되는 자원이라 다양한 응용 프로그램들은 메모리에 큰 영향을 받는다.

 

동적 메모리 할당

동적 메모리 할당은 프로그램이 실행되기 전에는 크기를 알 수 없는 자료구조를 위해 사용한다.

예를 들어 몇개의 숫자가 들어올지 모르는 상황에서, 무조건 max size만큼 자원을 할당해두는건, 메모리 낭비를 일으킬 수 있다.

또한 n개의 메모리를 할당했는데 그 이상으로 들어온다면 정적 메모리 할당 상태에서는 대응이 불가하다.

이를 방지하기 위해 동적 메모리할당을 사용한다.

 

동적 메모리 할당에는 직접 할당과 간접 할당이 있다.

직접 할당은 응용프로그램이 메모리를 할당하고, 반환까지 한다. malloc, free가 이 경우에 해당한다.

반면 간접하다은 편리하게 응용프로그램이 할당하지만, 반환은 응용프로그램이 하지 않아도 되는 할당 방식이다. 자바의 가비지컬렉션이 이에 해당한다.

 

할당 방법은 메모리 할당기가 메모리를 블럭단위로 제공하여 응용프로그램에 free 메모리 블럭을 나눠주는 방식이다.

 

프로세스의 메모리는 다음과 같다.

우리는 heap영역에 있는 메모리를 사용할 것이다.

만약 우리가 사용해야하는 메모리가 저 구간을 넘어간다면, 할당기는 sbrk 함수를 통해 추가적인 힙 메모리를 운영체제에게 요청한다.

운영체제는 brk + 증가된 사이즈를 반환한다.

 

Malloc

메모리 할당을 요청하는 함수이다. 

성공 시, 요청한 size 바이트의 메모리 블록의 포인터(가장 앞 부분의 주소)를 반환한다.

실패시 null을 리턴한다.

 

free

free는 할당되었던 메모리를 가용블록으로 바꾸는 것이다.(이제 그만 쓰겠다는 뜻)

해당 함수는 이렇게 생긴 free 블록의 가장 앞 포인터를 반환한다.

 

realloc

realloc은 블록 P의 크기를 변경하고, 새 블록의 포인터를 리턴한다.

이때 새 블록의 내용은 이전블록, 새블록 크기 중 적은 크기까지는 변함없이 유지된다.( 3인 블록을 5로 늘리면 모두 유지, 5인 블록을 3으로 줄이면 3블럭까지는 내용 유지)

 

이들을 사용한 예시를 보자

sizeof(int)는 int라는 자료형의 크기를 나타낸다. 

따라서 n*sizeof(int)는 n개의 정수를 넣을 수 있는 공간을 할당하는 것이다.

위에서는 먼저, malloc을 사용하여 n개의 정수를 만들었다.

그 다음 n+m개의 정수를 담을 수 있는 배열로 변환하기 위해서 realloc 하였다.

마지막으로 free(p)를 통해서 할당받았던 블록을 가용블록으로 전환하였다.

 

메모리는 워드 단위로 주소가 지정된다.

하나의 워드는 여러개의 블록 덩어리로 구성된다.

위 예시에서 4,5,6블록을 할당한 후, 크기가 5인 p2 워드를 free 하여 가용블록으로 만들었다.

이후 크기가 2인 p4 블록이 p2가 free된 구간으로 할당되었다.

 

제한사항

응용프로그램은 위의 기능을 구현하기 위한 다양한 제한사항이 존재한다.

랜덤의 순서로 들어오는 할당, free 요청을 즉시 대응해야한다.

 

할당 프로그램은 블록의 갯수를 조정할 수 없으며, 블록은 프리메모리에만 할당해야한다.

 

이 프로그램의 목표는 크게 두가지이다.

 

지역성 -> 시간적으로 인접하여 할당된 구조체와 유사한 객체들은 공간상으로 인접해야한다.(가까워야한다)

견고성 -> 메모리 참조가 유효한 포인터에 대해서 수행되어야한다

 

성능지표 역시 두가지가 있다.

처리량

처리량은 단위 시간동안 완료한 요청의 수이다.

alloc와 free 함수를 처리하는 시간을 최소화하여야 throughput을 극대화 할 수 있다.

 

최대 메모리 이용율

메모리를 효율적으로 관리하였는가에 대한 지표이다.

현재 힙의 크기가 Hk라고 하고, k개의 요청 후에 최대 메모리 이용율은 

위와 같다. 현재 힙의 크기 대비 얼마나 많은 메모리를 할당할 수 있었는지(할당된 메모리가 최대인 시점에)를 보여준다.

 

단편화

단편화는 메모리 사용율을 크게 저하한다. 현재 할당된 영역 때문에 빈공간을 제대로 활용을 못할 때 발생한다.

 

내부 단편화

내부 단편화는 블록의 크기와 데이터 크기간의 차이로 발생한다.

예를 들어 내가 가지고 있는 데이터가 5인데, 8인 블록을 할당받으면 3만큼은 비어있게된다.

내부단편화는 주로 데이터 이외에 정렬을 위해 바이트를 추가하거나, 헤더 등의 오버헤드 때문에 발생한다.

 

외부 단편화

외부 단편화는 위와 같이 전체 free 메모리를 합쳐보면 수용이 가능하지만 free 블록 각각의 크기가 할당을 원하는 데이터의 크기보다 작아서 발생한다.

외부 단편화의 경우 예측 불가한 미래의 요청패턴에 의해 결정되기때문에 측정이 어렵다.

 

구현할 때에는 해당 블록의 크기가 얼마인지? 가용블록을 어떻게 관리할지? 남는 공간은 어떻게 관리할지 등을 고려해야한다.

 

free 블럭 관리하기(간접리스트)

일반적으로 다음과 같이 블록의 헤더에 블록의 사이즈를 저장한다. 이를 위해서 매 할당 블록마다 추가적으로 1워드가 소요된다.

 

 

간접 리스트

간접 리스트 방식은 헤더의 크기 정보를 이용하여 모든 블록을 연결하는 방식이다.

 

일단, 헤더의 구조를 보자. 

헤더에는 블록의 크기와 할당 여부를 나타내는 마지막 비트가 존재한다.

마지막 비트를 활용하기 위해서 블록의 크기는 항상 짝수를 유지한다.(사이즈가 짝수 -> 마지막 비트는 무조건 0, 근데 헤더의 마지막 비트가 1이다? -> 그럼 할당된 블록이라는 뜻임)

 

free 블록 찾기

 

<최초할당>

위 코드는 최초할당 방식이다. 최초할당은 처음부터 검색을 시작해서, 맨 처음 크기가 맞는 블록을 할당하는 방식이다.

while문을 통해서 해당 조건에 맞는 블록을 찾을때까지 p값을 갱신한다.

 

p<end는 현재 값이 힙의 마지막에 있진 않은지(그럼 끝났으니까 -> 할당 가능 블록 없음)을 확인한다.

그 다음 *p & 1을 통해서 할당 여부를 체크한다. 마지막 비트가 1이면 할당된 값이므로, 이 값이 1이면 할당되었다고 판단한다.

또한 *p<=len을 통해서 현재 할당을 원하는 값보다 해당 블록이 작으면 1을 반환한다. 

여기서 *p를 블록의 크기라고 생각할 수 있는 이유는 ((*p&-2)를 하지 않은 이유) 이미 *p & 1로 할당되지 않은 블록(헤더 값이 짝수다-> 마지막 비트가 0이다)를 증명했기 때문이다.

 

마지막으로 while문 안에 들어왔다는 것은 지금 보는 블록이 할당 가능한 블록이 아니라는 뜻이므로, p값에 현재 탐색한 블록의 헤더값에 -2를 and 연산하여 더해서 p값을 다음 블록의 가장 앞 주소로 이동시킨다.

여기서 -2는 1111111110이다. 따라서 p값과 이 값을 and 연산하면, 할당된 블록의(사이즈는 짝수인데, 할당을 의미하기 위해 마지막 비트를 1로 만들어둔) 사이즈를 알 수 있다.

 

<다음할당>

first-fit과 유사하지만, 이전 검색에서 종료된 위치에서 검색을 시작함. 이게 단편화 성능은 더 나쁘다

 

<최적할당>

리스트를 검색해서 가장 근접한 크기의 블록을 선택 -> utilization 가장 좋다.

대부분의 단편화를 개선하지만, 성능은 나쁨

 

free 블록 할당

만약 할당된 공간이 필요한 공간보다 크다면 -> 해당 블록을 쪼갠다.

 

 

위 경우, 크기가 6인 블럭을 할당받았지만, 4만큼만 필요하므로 블록을 쪼개서 나머지 2개의 블록은 free를 유지하도록 했다.

 

 

구현 코드는 위와 같다.

일단, 새로 할당할 사이즈를 계산한다. len만큼 할당할 것인데, 할당할 블록의 사이즈는 무조건 짝수여야한다. 또한 len보다 큰 짝수이어야하므로, len에 1을 더해서 오른쪽으로 한번 밀고, 다시 왼쪽으로 한번 밀어 짝수올림을 해준다.

old size는 현재 할당하려는 블록의 사이즈이다. -2와 and연산을 하여 실제 사이즈를 구한다.

이제 새로운 블록의 사이즈를 *p에 넣어야하므로, newsize|1 을 해준다.(마지막 비트를 1로 만들어 할당되었음을 표시)

그 다음 뒤에 남은 free 블럭의 사이즈를 남기기 위해서 P + newsize를 하여 해당 free 블럭(크기가 2인 블럭)의 맨 앞으로 이동한 다음, 해당 위치에 oldsize-newsize를 한 값을 넣어 사이즈를 표시한다.(이때 oldsize와 newsize는 모두 짝수이므로, 끝 비트는 무조건 0이다. 따라서 끝 비트를 0으로 만드는, 즉 빈 블럭임을 표시하는 작업은 하지 않는다.)

 

블록 free 시키기

가장 간단하게는 그냥 마지막 비트만 0으로 세팅하면 된다.

하지만 방금 free 처리한 블럭 뒤에도 free가 있어 총 6사이즈의 데이터를 저장할 수 있게 되었는데, 두 블럭이 현재 나누어져 있으므로 할당기는 할당 블록을 찾지 못한다는 문제가 발생한다.

 

이를 방지하기 위해 결합을 한다.

먼저, *p & -2를 통해서 맨 마지막 비트를 0으로 만든다.(free임을 표시)

그 다음 p와 *p를 더해서 다음 블럭으로 이동한다. 이 블럭이 만약 free 블럭이면, *P에 *next(다음 블럭의 사이즈)를 더해 저장하면

 

위와 같이 두 free 블럭을 병합할 수 있다.

 

하지만 위의 방식은 오직 뒤에 있는 블럭과만 병합이 가능하다.

양방향 연결

이를 위해 나온 것이 양방향 연결이다. 

이전의 방식에는 헤더에만 사이즈를 표시하는 영역을 넣었지만, 이 방식에서는 footer에도 사이즈를 표시하는 영역을 넣는다.

이렇게 하면 추가적인 공간이 소요되지만, 중요하고 일반적인 기법이다.

 

상수 소요시간 연결법

 

다음은 여러가지 경우의 수에서 결합을 어떻게 하는지 살펴보겠다.

이 경우, 앞, 뒤 영역이 모두 할당된 상태이므로, 따로 병합하지 않는다.

 

여기서는 free한 블럭의 뒷부분이 free상태이므로, 이를 병합하였다. 이 블럭의 사이즈는 n+m2이다.

 

free한 블럭의 앞 블럭이 가용블럭이다. 이 경우 footer를 사용하여 병합하였을 것이다.

역시 사이즈는 m1+n이다.

 

여기는 양쪽 다 가용블럭이다. 이 경우 header, footer을 모두 사용해서 병합한다.

사이즈는 n+m1+m2이다.

 

 

출처

충남대 김형신교수님 시스템프로그래밍 강의자료

http://eslab.cnu.ac.kr

ESLAB | Home