Stack

자료구조에서의 Stack

기본적으로 Stack은 쌓인 것이라는 뜻이다. 말 그대로 자료구조에서도 데이터를 쌓는 구조를 Stack이라고 부르는데, 쓰레기통에 쓰레기를 넣는다고 생각해보자.
쓰레기를 당연히 위에 넣지 아래에 들쑤시고 넣는 사람은 없을 것이다. 만약 잘못 버려서 꺼내려면 위에서부터 꺼내게 된다.
자료구조에서의 Stack도 마찬가지로 위에서부터 넣고 위에서부터 뺀다. 이를 FILO(First In Last Out)방식이라 부른다.

메모리에서의 Stack

시스템에서 Stack을 쓰는 가장 큰 이유는 FILO구조의 특성때문이다. 예시를 한번 보자.

#include <stdio.h>

int add(int a,int b){
	return a+b;
}

int foo(){
	int a=3,b=4;
	return add(a,b);
}

int bar(){
	printf("%d",foo());
	return 0;
}

함수는 pc(program counter)를 통해 한줄씩 실행한다. 먼저 bar()함수가 실행되고 그 다음줄인 printf에서 foo함수를 호출한다.
foo함수로 들어갈때 시스템은 다시 돌아갈 주소를 저장하는데 이때 스택이 이용된다. 스택에 돌아갈 주소를 쌓고 foo함수를 한줄씩 실행한다.
그런데 add함수가 또 호출된다. 다시한번 시스템은 돌아갈 주소를 저장한다. 이때 스택에 다시 쌓고 add함수로 들어간다. 대충 스택을 왜 쓰는지 감이 올것이다.
add함수가 끝나고 돌아가면 스택에서 foo함수로 돌아가기 위한 주소를 꺼내서 돌아간다. 그리고 foo함수에서도 bar함수로 돌아가기 위해 스택에서 주소를 꺼내 돌아간다.
이것이 컴퓨터가 스택을 사용하는 이유이다.
정확히는 함수를 호출하는 관계에서 돌아갈 주소와 함수에 전달하기 위한 인자(x86)를 전달하는 용도로 쓰인다. 그 외에도 지역변수나 지역상수를 저장하는데도 사용된다.

나중에 gdb를 이용해 위의 함수를 분석해보면 이해하기 쉬울것이다.

Stack operation

Stack은 메모리 안에 있기때문에 공간마다 메모리 주소가 부여되어있다. 그리고 이 메모리 주소를 참조하기 위해 SP(Stack Pointer), BP(Base Pointer)라는 것이 사용되는데 SP는 스택에서 가장 위부분, BP는 특정한 구역(스택프레임)의 아래부분을 나타낸다. 그래서 SP부터 BP까지 구역을 정하고 사용한다.
위에 그림에서 RSP가 SP, RBP가 BP를 나타내고 초록색 영역이 이전함수(caller)에서 사용한 스택구역(스택프레임), 파란색 영역이 현재함수(callee)에서 사용하는 스택프레임이다.
참고로 사진에서 high address가 위에 있는데 우리가 생각하는 개념으로는 low address가 위에 있어야 하는게 맞다. 사진이 굉장히 불편하다. 그래도 사진대로 이해하면 아래로 쌓아 나가는 방식이다.

PUSH

PUSH는 어떤 값을 스택에 넣겠다는 뜻이다. 그래서 스택에 위에 하나씩 쌓게되며 이때 SP(Stack Pointer)는 감소한다(low address가 위방향이다!).

POP

POP은 PUSH의 반대연산으로 스택에서 값을 꺼내겠다는 뜻이다. 마찬가지로 SP는 증가한다.(high address가 아래방향이다!).