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

 

 

 

메모리는 무한하지 않고, 많은 소프트웨어들이 메모리에 큰 영향을 받는다.

 

당장 백준 사이트에서 그래프 알고리즘 문제를 풀 때도 메모리를 효과적으로 사용하지 못하면 알고리즘을 제대로 작성했어도 맞았습니다를 받을 수 없다.

 

가상 메모리.. 캐시... 메모리에도 여러 종류가 있다.

다른 메모리들은 컴퓨터구조나 운영체제를 공부하면서 배우기로 하고, 이번에는 동적 메모리에 대해 자세히 살펴보자.

 

 

 

---

 

 

 

 

 

 

C를 공부하면서 배웠듯 동적 메모리는 Heap 메모리 부분에 할당된다.

 

malloc과 free 함수를 사용해 메모리를 할당받고 반환한다.

자바에서는 Garbage Collection이 있어 반환에 신경쓰지 않아도 되지만, C에서는 메모리를 사용한 후 반납 해 줘야 한다.

 

 

 

 

 

 

프로그램이 돌아갈 때 메모리를 살펴보면 위와 같은 구조를 확인할 수 있다.

 

.text 메모리에는 CPU가 fetch한 명령어들이 저장된다.

.data 메모리에는 초기화 된 전역 변수들이 저장된다.

.bss 메모리에는 선언만 되고 초기화되지 않은 전역 변수들이 저장된다.

 

.bss 메모리 위에 heap 메모리가 위치한다.

 

brk 포인터가 heap 메모리의 top을 가리키고 heap 메모리가 부족 할 때 sbrk 함수를 호출해 brk 포인터를 늘려 heap 메모리의 크기를 증가시킨다.

 

heap 메모리 위에는 OS가 제공하는 라이브러리 중 prinf 같이 자주 사용하는 라이브러리를 올려 프로세스들이 공유해서 사용하도록 되어 있다.

 

그 위에는 스택 메모리가 위치한다.

스택 메모리는 아래로 성장하기 때문에 힙 메모리와 충돌이 발생할 수 있다.

 

 

 

 

 

malloc 함수를 사용해 메모리를 할당하는 예시를 살펴보자.

 

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

메모리가 막대 모양이라면 위와 같은 상황을 생각할 수 있다.

 

malloc 과 free 함수를 직접 구현해야 한다면, 어떻게 해야 성능을 끌어올릴 수 있을까?

 

 

 

 

1. 내부 파편화

 

 

 

메모리를 할당할 때 사용자가 요청한 메모리만큼만 할당되지는 않는다.

 

heap 메모리를 유지하고 정렬을 위한 바이트가 추가되거나, 할당 정책에 따른 오버헤드 때문에 위의 그림과 같이 내부 파편화가 발생할 수 있다. (파편화된 메모리의 크기도 측정할 수 있다)

 

실제로 요청한 데이터의 크기는 payload 의 크기지만 양 옆에 파편화된 메모리가 추가로 할당됐다.

 

 

 

 

2. 외부 파편화

 

메모리 블럭 그림에서 확인했었다.

메모리를 연속적으로 할당해야 하지만, 그 만큼의 할당 가능한 공간이 없을 때 발생한다.

 

미래의 요청 패턴에 의해 결정되기 때문에 파편화된 메모리의 크기를 측정할 수 없다.

 

 

파편화 외에도 고려 할 점이 많다.

 

free 함수를 구현 할 때는 얼마만큼의 메모리를 반환할 지 어떻게 판단해야 할까?

사용할 수 있는 블럭들을 어떻게 관리해야 할까?

...

 

"메모리 블럭을 어떻게 관리해야 하는가?" 라는 큰 틀에서 최적화를 위해 필요한 요소들을 하나씩 생각해보자.

 

 

malloc 으로 할당되는 메모리를 디자인 해 보자.

앞 뒤로 파편화된 메모리들을 최대한 활용한다고 생각하면.. 

 

 

 

 

앞 부분을 헤더로 사용해 할당된 데이터의 크기를 표시하고, 그 후 payload 와 파편화 메모리가 위치하도록 하면 free 시 반환해야 하는 메모리의 크기를 바로 알 수 있다.

 

 

 

 

 

1. 이 아이디어에서 좀 더 나아가 LinkedList 형식으로 메모리를 관리한다면?

 

현재 블럭에서 현재 블럭의 사이즈만큼 더하면 다음 블럭이 위치한 곳으로 이동할 수 있는 방식으로..

주소 대신 앞서 설계한 헤더를 가리키도록 하면 블럭들을 좀 더 쉽게 찾을 수 있다.

 

 

2. 이미 할당된 블럭은 연결하지 않고 사용 가능한 블럭들만 연결하면 좀 더 좋은 성능을 낼 수 있다.

 

3. 크기 마다 별도로 가용 리스트를 만들면 성능이 더 좋아진다.

 

4. 사용 가능한 블럭들 내부에 포인터를 사용하고, 크기를 키로 사용해 균형 트리 자료구조를 만들면 성능이 더 더 좋아진다. (실제 malloc 함수가 사용하는 전략이다)

 

 

총 4가지 방법이 있다. 하나하나 살펴보자.

 

 

 

---

 

 

 

 

1. 간접 리스트 방식 (Implicit List)

 

 

 

각 블럭이 비어있는지 할당 된 상태인지 구분이 필요하다.

추가 비트를 사용해 a가 1이면 할당됐음을, a가 0이면 비어 있는 블럭으로 처리하자.

 

 메모리를 할당 할 때 어떻게 할당하는지도 중요한 문제이다.

 

처음 부분부터 탐색을 시작해 적당한 크기의 블럭을 찾으면 해당 위치에 할당하는 방식이 떠오르는데, 이대로 사용해도 괜찮을까?

 

 

 

 

 

 

 

 

 

 

 

최초 할당 방식을 코드로 표현하면 위와 같다.

-2와 & 연산을 수행하는데 -2의 2의 보수 표현을 사용해 크기를 구하기 위해서이다.

 

메모리의 크기를 고려하지 않고 첫 번째로 만나는 블럭으로 할당되기 때문에 성능은 좀 떨어진다.

성능을 끌어올리기 위해 모든 블럭을 탐색한 후 가장 근접한 크기의 블럭으로 할당하는 방법을 사용 할 수도 있는데, 공간은 효과적으로 사용할 수 있지만 최초 할당 방법보다 느려진다.

 

적당한 방법을 고안해보자.

 

이 외에도 free 함수를 수행했을 때 반환된 메모리를 메모리 블럭에 반영하거나 내부 파편화를 최대한 줄이면서 메모리 블럭을 다루는 등 해결해야 하는 여러 문제가 있다.

 

malloc lab에서 위의 문제를 어떻게 해결하는지 생각해보자.