그래서, 스택이랑 힙이 뭔데?
CS를 공부하면서 초반에 막혔던 부분이 스택과 힙이다. C언어는 배워서 알고리즘 문제는 풀 수 있었지만 컴파일러 뒷 단에서 어떤 일이 일어나는지 전혀 몰랐다. 그래서 C언어로 작성된 예제를 가지고 스택과 힙이 뭔지 알아보자.
메모리의 구조
우리가 사용하는 메모리는 어떻게 생겼을까? 당연히 초록색 반도체 모양 말고 추상화된 모형을 물어본거다. 메모리 공간을 주소값의 높고 낮음을 기준으로 다음과 같은 그림을 그려볼 수 있다.
크게 4가지로 나누면 주소가 낮은 순서대로
- 코드 영역
- 데이터 영역
- 힙 영역
- 스택 영역
으로 나눌 수 있다.
코드 영역은 실행할 프로그램의 코드가 저장되는 영역으로, CPU는 여기에 저장된 명령어를 하나씩 가져가서 처리한다.
데이터 영역은 프로그램의 전역 변수(global variable)와 정적 변수(static variable)이 저장되는 영역으로, 프로그램이 시작되는 때에 생성되며 프로그램이 종료되면 없어진다.
힙 영역은 사용자가 직접 관리할 수 있는 영역으로, 사용자에 의해서 동적으로 할당되고 해제된다. 이때 할당 순서는 낮은 주소부터 높은 주소로 할당된다.
스택 영역은 프로그램 함수의 지역 변수(localvariable)와 매개변수(parameter)가 저장되는 영역으로, 함수가 호출되면 할당, 함수가 종료되면 해제된다. 다른 메모리 영역과 구분되는 스택 영역만의 특징은 '스택(stack)'구조라는 것이다. 스택 구조는 나중에 들어간 데이터가 먼저 나오는 구조(LIFO; Last In, First Out)로 push로 데이터를 저장하고 pop을 통해 스택의 제일 상단에 있는 데이터를 꺼낸다. 이때 할당 순서는 높은 주소부터 낮은 주소로 할당된다.
첫번째 예제
다음은 $n$번째 피보나치 수를 구하는 간단한 c 프로그램이다.
#include <stdio.h>
int n;
int fib(int k) {
if(k<=1) return 1;
return fib(k-1) + fib(k-2);
}
int main() {
scanf("%d", &n);
printf("%d", fib(n));
}
해당 코드에서 각 변수의 주소값을 알아보기 위해 조금의 코드를 더 추가하자.
#include <stdio.h>
int n;
int fib(int k) {
printf("parameter k(%d): %p\n", k, &k);
if(k<=1) return 1;
return fib(k-1) + fib(k-2);
}
int main() {
scanf("%d", &n);
printf("%d\n", fib(n));
printf("global variable n: %p\n", &n);
printf("function fib: %p", &fib);
}
그러면 프로그램을 실행시키고 3을 입력해 fib(3)의 값을 계산하는 과정을 살펴보자.
3
parameter k(3): 0x16da0b138
parameter k(2): 0x16da0b108
parameter k(1): 0x16da0b0d8
parameter k(0): 0x16da0b0d8
parameter k(1): 0x16da0b108
3
global variable n: 0x1023fc018
function fib: 0x1023f7e0c%
fib(3)은 3이므로 결과는 잘 출력된다. 변수들의 주소값들을 살펴보면 전역변수 n과 함수 fib의 주소는 낮은 반면, 매개변수 k의 주소는 상대적으로 높은 것을 볼 수 있다. k는 스택 공간에 저장되므로 가장 나중에 저장된 것이 낮은 주소값을 갖는다.
// main에서 fib(3) 호출됨(메모리 할당), fib(2), fib(1) 호출
parameter k(3): 0x16da0b138
// fib(3)에서 fib(2) 호출됨(메모리 할당), fib(1), fib(0) 호출
parameter k(2): 0x16da0b108
// fib(2)에서 fib(1) 호출됨(메모리 할당), 값 1 반환(메모리 반환)
parameter k(1): 0x16da0b0d8
// fib(2)에서 fib(0) 호출됨(메모리 할당), 값 1 반환(메모리 반환)
parameter k(0): 0x16da0b0d8
// fib(3)에서 fib(1) 호출됨(메모리 할당), 값 1 반환(메모리 반환)
parameter k(1): 0x16da0b108
이와 같은 순서로 호출되고 해제를 반복하며 나중에 저장된 값이 낮은 주소값을 갖도록 저장되는 모습을 볼 수 있다.
+) 전역변수 사용을 자제해야하는 이유
위에서 보았듯 전역변수는 데이터 영역에 저장되어 프로그램의 실행과 함께 생성되고 프로그램의 종료와 함께 해제된다. 즉, 프로그램이 실행 중일때는 메모리를 해제할 수 없다. 자유로운 메모리의 할당과 해제가 되지 않으면 메모리를 비효율적으로 이용하게 되므로 전역변수 사용을 자제하는 것이다.
두번째 예제
재밌는 예제를 하나 더 살펴보자.
두 개의 배열을 하나는 malloc, 하나는 지역변수로 선언하여 각각 힙 영역과 스택 영역에 저장되도록 하자. 스택 영역에 저장되는 배열은 과연 주소가 높은 값부터 저장될까?
#include <stdio.h>
#include <stdlib.h>
int main() {
int* arr_heap = malloc(3*sizeof(int)); // heap에 저장
int arr_stack[3]; // stack에 저장
printf("%p %p %p\n", arr_heap, arr_heap+1, arr_heap+2);
printf("%p %p %p\n", arr_stack, arr_stack+1, arr_stack+2);
}
실행결과는 다음과 같다.
0x102048020 0x102048024 0x102048028
0x16ddbf100 0x16ddbf104 0x16ddbf108
재밌게도 스택에 저장된 배열의 주소값이 힙에 저장된 배열의 주소값보다 높기는 하지만, 같은 배열에서는 인덱스에 따른 주소 순서가 같음을 확인할 수 있다. 덕분에 *(arr+1)을 arr[1]처럼 안전하게 사용할 수 있음이 보장된다.