프로그램과 호출스택

폰뉴만 아키텍처의 프로그램이 동작하는 방식을 이해하기 위해 호출스택을 알아야 한다. 호출스택이란 함수가 호출되는 과정에서 데이터가 스택의 형태로 쌓이고(push) 팝되는 영역을 말한다. 프로그램의 메모리는 다음의 세 가지 영역으로 나누어진다.

• 정적 영역 : 프로그램이 실행을 시작할 때 일정 크기가 할당되어 프로그램이 끝날 때까지 유지되는 메모리 영역으로 주로 전역변수나 정적 변수가 저장되는 영역이다. 프로그램 코드 상에 나타나는 리터럴(상수값)도 여기에 저장된다.

• 스택 영역 : 함수의 매개변수와 지역변수들이 저장되는 영역이다.  스택은 함수가 호출될 때 그 함수의 매개변수와 지역변수를 저장할 영역이 할당되고 그 영역은 함수가 리턴될 때 팝된다. 함수가 호출되고 거기서 다른 함수가 또 호출되면 스택이 푸시된다.

• 힙 영역 : 동적 할당 메모리가 할당되는 메모리 영역이다. 공유 메모리라고도 부르는데 이 영역은 여러 프로그램들이 같이 사용하는 영역으로 동적으로 할당되었다가 다 사용하고 나서 해지할 수 있는 영역이다. 

정적 영역은 너무 많이 사용하면 프로그램이 로드할 때 메모리 요구량이 많아진다. 또한 이 영역은 프로그램이 종료될 때까지 계속 차지하고 있게 되므로 전역변수나 정적 변수는 꼭 필요한 경우만 사용하는 것이 좋다. 그러므로 (C 언어의) 큰 배열을 전역으로 할당하는 것은 삼가하는 것이 좋다.

힙 영역은 정적이나 스택에 비해 상대적으로 큰 메모리를 사용할 수 있다. 그러나 공유하는 영역이므로 사용이 끝나면 반납을 해야 한다. 동영상 플레이라든가 집중적인 트래픽이 발생하는 시기 등 메모리 요구량이 일정 시간 동안 크게 증가하는 경우라면 힙 영역에 할당하여 사용하고 다 사용한 후에는 반납(해지)하는 것이 좋은 방식이다. 오랜 시간 돌아가고 있는 프로그램이 메모리를 할당하고 해지하지 않은 채 또 다른 메모리를 추가적으로 할당하기를 반복하면 힙 영역이 바닥나는 상황이 생길 수 있다. 이런 현상을 "메모리 리크"라고 한다. 

마지막으로 스택 영역은 프로그램의 실행 과정에서 함수의 호출과 반환에 따라 푸시 팝 되는 영역이다. 프로그램의 실행은 명령문 단위로 CPU의 패치 사이클에 의해 하나씩 가져다 동작하는데, 그 안에서 제어의 흐름이 goto나 jump에 의해 다른 곳으로 이동할 수 있다. 이것은 다음 명령문의 주소를 계산하는 로직을 통해 처리된다. 그런데 현대 프로그램의 실행에서 이에 못지 않게 중요한 것이 함수여서 함수의 시작부로 이동했다가 리턴하면 호출한 다음 문장으로 돌아오는 제어의 이동이 많이 사용된다. 프로그램의 실행이란 이러한 제어의 흐름이나 함수 호출 관계가 어떻게 바뀌느냐에 따라 다양한 경로와 계산을 수행하고 다른 결과가 나오게 된다.

이러한 함수의 호출에 따라 지역변수와 매개변수의 메모리 영역이 할당되어야 한다. 한 함수에 대해 할당되는 영역을 스택프레임이라고 하고 이들은 그 함수가 동작하는 동안에만 유지되고 함수의 반환 시에 사라진다. 또한 함수 안에서 다른 함수를 호출할 수 있고 그 경우 제일 마지막에 호출된 함수가 가장 먼저 반환하므로 프레임들은 스택 형태로 쌓이게 된다. 다음 C 프로그램의 예제에서 스택이 어떻게 바뀌는가를 살펴보자. 

이 프로그램을 디버깅해 보면 19번 줄에서 실행을 시작하고 스택은 main 프레임만 가지고 있다. scanf 함수를 호출하고 돌아와서 20번 줄로 넘어가면 gcd의 계산을 위해 함수를 호출하므로 그 함수의 첫 줄로 들어가게 된다.  13번 줄에 해당하는 명령문이 다음에 실행되는데, 이 때 매개변수 a, b가 넘겨져야 되고 지역변수 result를 위한 메모리가 할당되어야 한다. 이것이 gcd 함수의 프레임이다. 그리고 그것은 두번째 스택 그림처럼 main 위에 쌓인다. 그리고 a가 b보다 작으면 두 수를 바꾸기 위해 14번 줄에서 swap이 불려질 것이고 역시 swap 함수의 프레임이 쌓인다. (세번째 그림) 그리고 나서 swap 계산이 끝나고 gcd까지 반환을 하면 그 값을 매개변수로 해서 printf가 불려진다. 이 때는 그림과 같이 swap과 gcd가 차례로 팝되고 main 위에 다시 printf 프레임이 쌓일 것이다. 

정적 영역은 프로그램 시작할 때 한번 주소가 정해지면 종료 시까지 변함이 없는 주소값을 가지고, 동적할당되는 힙 영역의 객체들은 할당을 요청하면 운영체제가 주소를 주고 그 주소로 사용하다가 다 쓰고 나면 그 주소로 반환한다. 그에 비해 스택 영역의 지역변수는 함수의 호출관계에 의해 메모리가 할당되고 해지되므로 훨씬 이해하기 어렵고 또한 가장 변화무쌍한 영역이다. 스택이 어떻게 쌓여있고 거기에 어떤 값이 들어있는가가 프로그램의 디버깅에서 가장 중요한 정보다. 그러므로 여기서는 스택 프레임이 어떤 값을 가지고 어떻게 변화하는가를 좀더 자세하게 살펴보려고 한다. 다음 그림은 매개변수를 빨간색, 지역변수를 초록색으로 표시한다.

여기에 실제 값을 넣어서 생각해 보자. x, y에 각각 8과 15가 입력되었다고 가정해 보자. swap에 전달되는 매개변수는 주소인데, 여기서는 1080과 1084라고 가정한다. swap의 반환 후에는 a, b의 값이 바뀜을 볼 수 있다.

컴파일러는 gcd의 코드를 번역하다가 a를 만나면 gcd 스택 프레임의 첫번째 매개변수 주소를 a 대신에 넣어 (로드 또는 스토어) 명령문을 생성한다. a의 주소는 스택 프레임 시작 주소와 같을 것이다. 그런데 스택 프레임이 몇번째로 쌓일지는 실행할 때가 되어야 알 수 있으므로 스택 프레임의 시작 주소를 알 수가 없다. 그래서 컴파일러는 스택프레임의 주소를 나타내는 레지스터 fp를 이용해서 a의 주소를 표현한다. 즉 컴파일러가 만든 명령문에서 지역변수나 매개변수는 fp +- 알파의 형태로 주소가 표기된다.

swap의 경우 주소를 저장하는 두 개 매개변수가 생기고 이 주소는 gcd가 가진 a와 b의 주소가 들어갈 것이다. 이것도 컴파일러는 현재 프레임의 시작주소 fp를 기준으로 상대주소를 계산하여 명령문에 넣게 된다. 즉 스택프레임에는 매개변수가 먼저 나타나고 그 다음에 지역변수가 쌓이게 된다. 배열이나 객체의 참조 등을 고려하여 스택이 어떤 값을 가지고 있을지를 그려보는 것은 프로그램의 실행을 이해하는데 매우 중요한 작업이다. 다음은 위의 프로그램을 배열에 대해 확장한 것으로 여기서 gcd를 계산하는 부분의 스택 변화는 다음과 같다.

이 그림에서 스택은 gcd_arr 함수 내에서 (b)~(f)까지 푸시와 팝을 n번 반복하게 된다. 이와 같이 스택의 변화는 프로그램의 실행 동안 아주 많은 회수의 푸시와 팝을 반복한다. 그리고 배열의 값이 어떻게 전달되는가를 값으로 살펴보면 다음과 같다. gcd_arr은 main이 가진 배열의 주소를 arr로 넘겨받게 되는데 이 주소도 자신의 fp로부터 상대 주소로 계산한다. 그 주소에 [0]. [1] 같은 인덱스에 따라 값을 계산하여 배열 변수의 주소를 계산한다. (컴파일러의 최대 관심은 주소를 계산하여 메모리에서 값을 레지스터로 가져오는 것이다)

우리는 이것을 포인터라고 하고 위와 같이 화살표 형태로 많이 표현한다. 여기서 각 포인터는 스택 내의 다른 프레임의 값을 가리키는 주소가 된다. 포인터는 힙 영역에 있는 객체의 주소가 될 수 있다. 위의 15번 줄을 int array[] = (int*)malloc(sizeof(int)*5);라고 쓰면 이 주소는 힙 영역에 할당될 것이고 그렇게 되면 gcd_arr에 전달되는 주소도 힙 영역을 가리키게 된다.

C 언어는 포인터가 정적, 스택, 동적 영역을 모두 가리킬 수 있다. 어디있는 객체든, 무슨 데이터타입이든 가리킬 수 있고 배열이 포인터로 취급된다는 점도 중요한 특징이다. (자바는 참조는 객체만 가리킬 수 있고 모든 객체는 힙 영역에 있다. 그래서 스택이 훨씬 간단해진다.)

자바로 넘어가기 전에 C의 구조체 자료구조가 스택에 어떻게 나타나는지 예제를 하나 살펴보자.

1	typedef struct {
2 	   int value;
3 	   Node* next;
4 	} Node;
5 	Node* create_node() {
6 	   Node* node = (Node*)malloc(sizeof(Node));
7 	   scanf(“%d”, &node->value);
8 	   node->next = NULL;
9 	   return node;
10 	}
11	Node* create_list(int n) {
12	   int i; Node *head, *node;
13         head = node = create_node();
13	   for (i=1; i<n; i++) {
14            node->next = create_node();
15            node = node->next;
16         }
17	   return head;
18	}
19 	int max_list(Node* node) {
20 	   int m=node->value;
21	   while (node->next != NULL) {
22            node = node->next;
23 	      if (node->value > m) 
24		 m = node->value;
25	   return m;
26	}
27	void main() {
28 	   Node* list;
29 	   list = create_list(5);
30	   printf(“max = %d\n”, max_list(list));
31	}

다음 그림은 create_list 함수가 첫번째 노드를 만든 후 두번째로 create_node를 불렀을 때 스택의 상태와 거기서 리턴해서 돌아온 후의 스택 상태를 보여준다. 이와 같이 스택은 실행 중 특정 시점의 프로그램의 상태를 스냅샷으로 보여줄 수 있는 유용한 정보다.

참고: 스택과 힙 - 메모리 관리