프로그램에서 메모리를 다룰 때 Stack과 Heap을 자주 접하게 된다.
둘 다 메모리 영역이지만 사용하는 방식이 다르다. 그래서 Stack Overflow와 Heap Overflow를 같은 종류의 메모리 부족 문제로 생각하기 쉽다.
실제로는 무엇이 쌓이고 있는지를 보는 것부터 시작해야 한다.
Stack에 쌓이는 것은 무엇인가
함수가 호출되면 해당 함수의 실행을 위한 정보가 필요하다.
지역 변수, 매개변수, 반환 주소와 같은 정보가 Stack Frame에 저장된다.
함수 호출 -> Stack Frame 생성 -> Stack에 저장
함수 종료 -> Stack Frame 제거
함수가 정상적으로 종료되면 해당 Stack Frame도 제거된다.
void A()
{
int value = 10;
}
A()가 호출되는 동안에는 A()의 실행에 필요한 Stack Frame이 존재하고, 함수가 끝나면 사라진다.
여러 함수가 연속해서 호출되면 호출이 끝나기 전까지 Stack Frame이 유지된다.
A()
-> B()
-> C()
C Stack Frame
B Stack Frame
A Stack Frame
Stack Overflow
문제는 함수 호출이 끝나지 않고 계속 쌓이는 경우다.
대표적인 예가 재귀 호출이다.
void Foo()
{
Foo();
}
Foo()가 자신을 다시 호출하고, 새로운 Foo()가 다시 자신을 호출한다.
Foo()
-> Foo()
-> Foo()
-> Foo()
-> ...
이때 이전 함수 호출이 끝나지 않았기 때문에 Stack Frame이 계속 생성된다.
함수 호출 증가
-> Stack Frame 증가
-> Stack 사용량 증가
-> Stack 공간 고갈
-> Stack Overflow
따라서 Stack Overflow는 단순히 메모리를 많이 사용해서 발생하는 오류라고 설명하는 것보다 Stack Frame이 계속 증가해서 Stack의 한계를 넘는 상황이라고 이해하는 것이 정확하다.
재귀 호출이 대표적인 원인이지만, 지나치게 깊은 함수 호출이나 Stack에 지나치게 큰 지역 데이터를 할당하는 경우에도 발생할 수 있다.
Heap은 다른 방식으로 사용된다
Heap은 실행 중 필요한 메모리를 동적으로 할당하기 위한 영역이다.
C++에서는 new나 malloc 등을 통해 Heap 메모리를 사용할 수 있다.
int* value = new int(10);
여기서 value라는 포인터와 new로 할당된 메모리는 같은 곳에 존재하는 것이 아니다.
Stack
value
|
v
Heap
int(10)
포인터 자체는 Stack에 존재할 수 있고, 포인터가 가리키는 동적 메모리는 Heap에 존재한다.
Heap에서 발생하는 문제
Heap은 Stack처럼 함수 호출이 끝나면 자동으로 Stack Frame이 제거되는 구조가 아니다.
프로그램이 계속해서 동적 메모리를 할당하면 Heap 사용량이 증가할 수 있다.
동적 메모리 할당
-> Heap 사용량 증가
-> 사용 가능한 메모리 감소
-> 메모리 할당 실패
이런 상황은 메모리 부족 문제로 이어질 수 있다.
또한 Heap에서는 메모리를 잘못 사용하는 문제도 발생한다.
int* value = new int(10);
delete value;
*value = 20;
delete 이후에는 해당 메모리를 더 이상 사용할 수 없다.
이런 문제는 Stack Overflow와는 다른 종류의 메모리 오류다.
따라서 Heap과 관련된 문제를 전부 Heap Overflow라고 부르는 것보다는 메모리 부족, Buffer Overflow, Use-After-Free, Memory Leak 등 실제 원인을 구분해서 보는 것이 좋다.
자료구조의 Heap과 메모리의 Heap
개발하면서 특히 헷갈리는 부분이 하나 있다.
자료구조에도 Heap이 있다.
Priority Queue를 구현할 때 사용하는 Min Heap이 대표적이다.
Priority Queue
-> Min Heap
-> 가장 작은 값을 빠르게 꺼냄
여기서 Heap은 자료구조다.
반면 Stack과 Heap을 이야기할 때의 Heap은 프로세스의 메모리 영역이다.
Stack
-> 메모리 영역
Heap
-> 메모리 영역
Min Heap
-> 자료구조
이름만 같을 뿐 서로 다른 개념이다.
다익스트라에서 Priority Queue를 사용하고 내부적으로 Min Heap을 사용한다고 해서 이것을 메모리 영역의 Heap과 같은 의미로 보면 안 된다.
Stack과 Heap을 구분하는 기준
결국 중요한 것은 어떤 데이터가 어디에 저장되고 왜 증가하는가다.
함수 호출
-> Stack Frame
-> Stack 사용량 증가
-> 한계 초과
-> Stack Overflow
반대로 동적 메모리는 다음과 같이 생각할 수 있다.
동적 할당
-> Heap 사용량 증가
-> 메모리 부족 또는 잘못된 접근
그래서 다익스트라처럼 많은 데이터를 사용하는 알고리즘에서 메모리 사용량이 증가한다고 해서 그것을 Stack Overflow라고 부르면 안 된다.
일반적인 반복문 기반 다익스트라는 함수 호출이 계속 중첩되는 구조가 아니기 때문이다.
Graph
+ Distance Array
+ Priority Queue
-> 메모리 사용량 증가
이것과
함수 호출
-> Stack Frame 증가
-> Stack 사용량 증가
는 전혀 다른 상황이다.
메모리 문제를 볼 때 중요한 것은 단순히 “메모리가 부족하다”가 아니다.
어떤 영역에 어떤 데이터가 저장되고 있으며, 그 데이터가 왜 계속 증가하고 있는지를 봐야 한다.
Stack Overflow는 Stack의 문제이고, Heap에서 발생하는 메모리 문제는 그 원인을 별도로 확인해야 한다.
그리고 자료구조의 Heap은 아예 다른 개념이다.
이 세 가지를 분리해서 생각하면 Stack과 Heap을 혼동할 일이 크게 줄어든다.