본문 바로가기
TYLER SONGBlog
블로그 목록
CS학습

Stack: 함수 호출을 기록하는 후입선출(LIFO) 메모리 영역

스택은 프로세스 메모리 공간 중 함수 호출 정보(스택 프레임)를 저장하는 영역이며, 후입선출(LIFO) 구조로 동작한다. 함수가 호출될 때마다 스택 프레임이 push되고 반환될 때 pop되며, 이 과정이 재귀 호출 깊이나 지역 변수 크기와 맞물려 스택 오버플로우(Stack Overflow)를 일으킬 수 있다. 이 글에서는 스택의 구조, 동작 원리, 실무에서

송민성7분 읽기

1. 개념

스택(Stack)은 두 가지 층위에서 이야기할 수 있다.

  • 자료구조로서의 스택: 마지막에 들어온 데이터가 가장 먼저 나가는 후입선출(LIFO, Last In First Out) 구조. push(삽입)와 pop(제거)만 허용한다.
  • 운영체제 메모리 영역으로서의 스택: 프로세스 가상 메모리 공간에서 함수 호출 정보를 저장하는 영역. 함수가 호출될 때마다 스택 프레임(Stack Frame)이 쌓이고, 함수가 반환되면 해당 프레임이 제거된다.

이 글은 운영체제 카테고리이므로 후자, 즉 콜 스택(Call Stack)을 중심으로 설명한다. 자료구조 스택은 이 콜 스택의 동작 원리를 그대로 응용한 것이다.

프로세스의 가상 메모리는 보통 다음과 같이 배치된다.

text
높은 주소
+------------------+
|      Stack       |  ← 함수 호출, 지역 변수 (아래로 성장)
|        ↓         |
|                   |
|        ↑         |
|      Heap        |  ← malloc/new로 동적 할당 (위로 성장)
+------------------+
|   BSS / Data      |  ← 전역/정적 변수
+------------------+
|      Text         |  ← 실행 코드
+------------------+
낮은 주소

스택은 높은 주소에서 낮은 주소 방향으로 자라는 것이 일반적이며(아키텍처에 따라 다름), 힙과 서로 반대 방향으로 성장하면서 가운데 공간을 나눠 쓴다.

2. 왜 사용하는가

함수 호출은 다음 정보를 기억해야 정상적으로 되돌아올 수 있다.

  • 호출자로 돌아갈 복귀 주소(Return Address)
  • 함수의 지역 변수
  • 매개변수
  • 이전 스택 프레임의 시작 위치(Base Pointer)

이 정보들을 함수 호출 순서와 반대로 해제해야 하므로 후입선출 구조가 정확히 들어맞는다. 가장 최근에 호출된 함수가 가장 먼저 종료되고, 그 프레임이 가장 먼저 제거되기 때문이다. 힙처럼 임의의 순서로 할당/해제되는 구조로는 함수 호출-복귀 관계를 관리할 수 없다.

또한 스택은 컴파일 시점에 각 프레임의 크기를 대부분 알 수 있어서, 힙 할당보다 훨씬 빠르게 공간을 확보하고 해제할 수 있다. 포인터(스택 포인터, SP) 하나만 증감시키면 되기 때문이다.

3. 동작 원리

함수 호출 시 CPU와 컴파일러가 협력해서 스택 프레임을 구성한다. x86-64 기준 대략적인 흐름은 다음과 같다.

  1. 호출자가 인자를 레지스터 또는 스택에 준비한다.
  2. call 명령으로 복귀 주소를 스택에 push하고 함수 시작 주소로 점프한다.
  3. 피호출자(callee)가 이전 프레임 포인터(base pointer, rbp)를 스택에 저장한다(프롤로그, prologue).
  4. 스택 포인터(rsp)를 지역 변수 크기만큼 감소시켜 공간을 확보한다.
  5. 함수 실행이 끝나면 스택 포인터를 원상 복구하고 저장해둔 프레임 포인터를 복원한다(에필로그, epilogue).
  6. ret 명령으로 스택에서 복귀 주소를 pop하여 호출자로 돌아간다.

이 과정에서 재귀 호출이 깊어지면 스택 프레임이 계속 쌓이고, 스레드에 할당된 스택 영역의 한계를 넘으면 스택 오버플로우(Stack Overflow)가 발생해 세그멘테이션 폴트(Segmentation Fault) 같은 오류로 이어진다.

각 스레드는 독립적인 스택을 가진다. 프로세스 안의 스레드들이 힙과 전역 데이터는 공유하지만 스택은 스레드마다 별도 영역에 할당되기 때문에, 스레드 개수가 많아지면 스택 영역이 차지하는 전체 메모리도 무시할 수 없는 크기가 된다.

4. 코드 예제

4-1. 자료구조로서의 스택 구현 (Python)

콜 스택의 push/pop 원리를 그대로 구현한 예시다.

python
class Stack: def __init__(self): self._items: list = [] def push(self, item): self._items.append(item) # 리스트 끝에 추가, O(1) 상환 def pop(self): if not self._items: raise IndexError("pop from empty stack") return self._items.pop() # 리스트 끝에서 제거, O(1) def peek(self): if not self._items: raise IndexError("peek from empty stack") return self._items[-1] def is_empty(self) -> bool: return len(self._items) == 0 def size(self) -> int: return len(self._items) if __name__ == "__main__": s = Stack() s.push("main() 호출") s.push("foo() 호출") s.push("bar() 호출") print(s.peek()) # bar() 호출 (가장 최근에 push된 항목) print(s.pop()) # bar() 호출 - 반환되며 스택에서 제거 print(s.pop()) # foo() 호출 print(s.size()) # 1

4-2. 재귀 호출과 콜 스택의 실제 동작 확인

재귀 호출이 깊어질 때마다 스택 프레임이 쌓이는 것을 파이썬의 재귀 제한과 함께 확인할 수 있다.

python
import sys sys.setrecursionlimit(1000) # 기본값은 보통 1000, 필요 시 조정 가능 def factorial(n: int, depth: int = 0) -> int: print(f" " * depth + f"factorial({n}) 호출, 현재 스택 깊이 근사치: {depth}") if n <= 1: return 1 result = n * factorial(n - 1, depth + 1) print(f" " * depth + f"factorial({n}) 반환") return result print(factorial(5))
python
import sys def infinite_recursion(n: int) -> int: return infinite_recursion(n + 1) try: infinite_recursion(0) except RecursionError as e: # 파이썬 인터프리터 자체의 콜 스택 한계에 도달하면 # 실제 OS 스택 오버플로우 전에 RecursionError로 안전하게 막아준다. print(f"RecursionError 발생: {e}")

4-3. 스레드 스택 크기 확인 및 조정 (Shell / Python)

shell
# 현재 셸 프로세스의 스택 크기 제한 확인 (리눅스/macOS 기준) ulimit -s # 예: 8192 (KB 단위, 즉 8MB)
python
import threading def deep_recursion(n: int): if n == 0: return deep_recursion(n - 1) # 기본 스레드 스택 크기보다 큰 값을 지정해서 # 깊은 재귀에서도 스택 오버플로우가 나지 않도록 조정한다. threading.stack_size(64 * 1024 * 1024) # 64MB로 설정 t = threading.Thread(target=deep_recursion, args=(9000,)) t.start() t.join() print("정상 종료")

5. 시간 복잡도 또는 성능 특성

연산시간 복잡도비고
push (함수 호출)O(1)스택 포인터 증감만으로 처리
pop (함수 반환)O(1)스택 포인터 복원만으로 처리
peek (최상단 접근)O(1)임의 위치 접근은 불가, 최상단만 O(1)
임의 인덱스 접근불가능스택은 최상단 외 접근을 허용하지 않는 것이 원칙

힙 할당(malloc, 파이썬의 객체 생성 등)은 가용 블록을 탐색하고 메타데이터를 갱신해야 하므로 스택 할당보다 일반적으로 느리다. 반면 스택은 포인터 연산 하나로 끝나기 때문에 함수 호출이 빈번한 프로그램에서 성능상 이점이 크다. 다만 이는 스택 프레임 크기가 컴파일 시점에 결정 가능한 경우에 해당하며, 가변 길이 배열(VLA)처럼 런타임에 크기가 정해지는 경우는 예외적으로 처리된다.

6. 실무 사용 사례

  • 재귀 알고리즘의 반복문 전환: 트리 순회, DFS(깊이 우선 탐색) 등을 재귀로 구현하면 코드는 간결하지만 입력 크기가 커지면 스택 오버플로우 위험이 있다. 실무에서는 명시적 스택 자료구조를 사용한 반복문 방식으로 바꿔 이 문제를 피한다.
  • 디버깅 시 스택 트레이스(Stack Trace) 분석: 프로그램이 예외를 던지면 콜 스택 정보를 출력하는데, 이는 각 스택 프레임에 저장된 호출 정보를 역순으로 나열한 것이다. 장애 분석 시 이 스택 트레이스를 읽고 어느 함수 호출 체인에서 문제가 발생했는지 추적한다.
  • 스레드 풀 설계 시 스택 크기 산정: 스레드를 대량으로 생성하는 서버(예: 스레드 기반 웹 서버)에서는 스레드당 기본 스택 크기(리눅스 기본값은 보통 8MB)를 곱한 값이 전체 메모리에 큰 영향을 준다. 스레드 수가 많다면 스택 크기를 줄여서 메모리를 절약하기도 한다.
  • 컴파일러 최적화(Tail Call Optimization): 꼬리 재귀(Tail Recursion) 형태의 함수를 컴파일러가 반복문으로 변환해 스택 프레임 누적을 막는 최적화 기법이다. 다만 파이썬 인터프리터는 이 최적화를 지원하지 않는다.

7. 주의할 점

  • 스택 오버플로우는 예측 가능한 지점에서만 안전하게 처리된다: 파이썬은 RecursionError로 잡을 수 있지만, C/C++처럼 런타임이 감지하지 않는 언어에서는 세그멘테이션 폴트로 프로세스가 강제 종료된다.
  • 스택에 큰 데이터를 올리지 않는다: 지역 변수로 큰 배열이나 구조체를 선언하면 스택 프레임 크기가 커져 오버플로우 가능성이 높아진다. 큰 데이터는 힙에 할당하는 것이 안전하다.
  • 스레드 스택은 스레드마다 별도로 존재한다: 한 스레드의 지역 변수를 다른 스레드에서 접근하면 정의되지 않은 동작(Undefined Behavior)이 발생한다. 스레드 간 데이터 공유는 힙이나 명시적 동기화 메커니즘을 사용해야 한다.
  • 재귀 깊이는 입력 크기에 비례해서 커질 수 있다: 정렬되지 않은 트리나 링크드 리스트를 재귀로 순회하면 입력 크기만큼 스택 깊이가 늘어난다. 입력 크기가 예측 불가능하다면 반복문 기반 구현을 우선 고려해야 한다.
  • `sys.setrecursionlimit`을 무작정 늘리는 것은 근본 해결책이 아니다: 재귀 제한을 늘려도 실제 OS 스택 크기를 초과하면 인터프리터가 죽는 세그멘테이션 폴트로 이어질 수 있다. 스레드 스택 크기(threading.stack_size)도 함께 고려해야 한다.

8. 핵심 정리

  • 스택은 후입선출(LIFO) 구조를 가지는 프로세스 메모리 영역으로, 함수 호출 시 스택 프레임을 push하고 반환 시 pop한다.
  • push/pop 연산은 스택 포인터 증감만으로 처리되어 O(1)이며, 힙 할당보다 빠르다.
  • 스택은 스레드마다 독립적으로 할당되며, 기본 크기를 초과하면 스택 오버플로우가 발생한다.
  • 재귀 알고리즘 설계 시 입력 크기와 스택 깊이의 관계를 항상 고려해야 하며, 필요하면 반복문이나 명시적 스택 자료구조로 대체한다.
© 2026 Tyler Song