활성화 레코드와 스택 오버플로우

서버란·2024년 8월 31일
자료구조

CS 지식

목록 보기
1/25

메모리 구조와 함수 실행

프로그램이 실행될 때 메모리는 크게 코드 영역, 데이터 영역, 힙 영역, 스택 영역으로 나뉩니다. 함수가 호출될 때마다 스택 영역에 활성화 레코드(Activation Record)가 저장됩니다. 이는 함수 호출과 실행과 관련된 중요한 정보를 기록한 것입니다.

1. 활성화 레코드(Activation Record)

활성화 레코드는 스택 영역에 저장되며, 스택 프레임(Stack Frame)이라고도 불립니다. 각 함수가 실행될 때마다 해당 함수의 실행 상태를 기록하는데, 함수가 종료되면 이 레코드는 삭제됩니다.

활성화 레코드에 기록되는 정보

  • 리턴 값: 함수가 완료되었을 때 호출한 함수로 반환할 값.
  • 파라미터: 함수가 호출될 때 전달된 인자들.
  • 지역 변수: 함수 내부에서 선언된 변수들.
  • 복귀 주소(Return Address): 함수가 끝난 후 다시 돌아갈 코드 위치.

예시

코드 복사
int sum(int a, int b) {
    int result = a + b;  // 이 함수가 실행될 때 스택에 활성화 레코드가 기록됨
    return result;
}

함수 호출과 활성화 레코드

함수 내에서 또 다른 함수를 호출할 수 있으며, 이때 호출된 함수의 활성화 레코드가 스택에 추가됩니다. 만약 A 함수가 실행 중에 B 함수를 호출하면 다음과 같은 일이 발생합니다:

  • A 함수의 활성화 레코드가 스택에 저장됩니다.
  • B 함수의 활성화 레코드가 새로 추가됩니다.
  • B 함수의 실행이 끝나면, A 함수의 활성화 레코드를 다시 불러와 A 함수의 실행을 이어갑니다.

이 과정을 통해 각 함수는 자신이 실행되던 상태를 잃지 않고 실행을 이어갈 수 있습니다.

2. 스택 메모리와 Stack Overflow

스택 영역은 제한된 메모리 자원입니다. 함수가 재귀적으로 무한히 호출되면 활성화 레코드가 스택에 계속 쌓여서 Stack Overflow가 발생할 수 있습니다.

Stack Overflow가 발생하는 경우
재귀 함수가 너무 많이 호출되면 스택이 넘쳐서 더 이상 활성화 레코드를 저장할 공간이 없어집니다.

int sum(int n) {
    if (n == 1) return 1;  // 기저 사례
    return sum(n - 1) + n;  // 재귀 호출
}

위 예시에서 sum 함수는 기저 사례(n == 1)가 있어야 재귀 호출이 멈추는데, 만약 n이 매우 큰 값이라면 스택에 활성화 레코드가 계속 쌓여 Stack Overflow가 발생할 수 있습니다.

Stack Overflow가 발생하지 않는 경우
재귀 호출이 없는 일반 함수는 한 번 실행된 후 스택에서 제거되므로 무한 반복하더라도 Stack Overflow가 발생하지 않습니다.

while(true) {
    sum(3, 4);  // 함수 실행 후 스택에서 제거됨
}

이 경우 함수가 계속 실행되더라도, 함수가 끝나면 스택에서 활성화 레코드가 삭제되기 때문에 Stack Overflow는 발생하지 않습니다.

3. 기저 사례와 재귀 함수

재귀 함수를 설계할 때 기저 사례(Base Condition)가 중요합니다. 기저 사례가 없으면 재귀 호출이 무한히 반복되면서 Stack Overflow가 발생할 수 있습니다. 기저 사례를 통해 함수의 재귀 호출을 멈추도록 해야 합니다.

기저 사례가 없는 재귀 함수의 문제

int infiniteRecursion(int n) {
    return infiniteRecursion(n - 1);  // 기저 사례가 없음
}

위 함수는 종료 조건이 없어서 계속해서 자기 자신을 호출하게 되고, 결국 스택이 가득 차서 Stack Overflow가 발생합니다.

4. 활성화 레코드의 한계

활성화 레코드는 한정된 스택 메모리 자원을 사용합니다. 예를 들어, 재귀 함수가 4000번 이상 호출되면 Stack Overflow가 발생할 수 있습니다. 이를 피하려면 재귀 함수 대신 반복문을 사용하는 방법을 고려해야 합니다.

5. 힙 메모리와 Heap Overflow

활성화 레코드는 스택 영역에서 관리되지만, 프로그램에서 힙 영역은 동적 메모리 할당에 사용됩니다. 힙 메모리도 제한된 자원이며, Heap Overflow가 발생할 수 있습니다. 이는 힙 메모리를 할당받고 반환하지 않으면 발생하는 문제입니다.

int[] largeArray = new int[Integer.MAX_VALUE];  // 큰 메모리 할당 시 Heap Overflow 가능

만약 프로그램이 힙 메모리를 계속해서 할당하고 반환하지 않으면 힙도 가득 차서 프로그램이 비정상 종료될 수 있습니다. 이 문제는 특히 동적 메모리 할당을 많이 사용하는 C, C++ 같은 언어에서 흔히 발생하며, 자바에서는 new 키워드를 사용해 객체를 생성할 때 발생할 수 있습니다.

정리

  • 활성화 레코드(Activation Record)는 함수가 실행될 때 스택에 저장되는 함수 실행 상태 정보입니다.
  • 스택 영역에 활성화 레코드가 저장되며, 재귀 함수의 호출이 많아지면 Stack Overflow가 발생할 수 있습니다.
  • 기저 사례는 재귀 호출을 안전하게 멈추기 위한 조건이며, 이를 잘 설정해야 Stack Overflow를 방지할 수 있습니다.
  • 힙 영역에서는 Heap Overflow가 발생할 수 있으며, 동적 메모리 할당 시 이를 조심해야 합니다.

Q1: 재귀 함수에서 기저 사례가 없으면 어떤 문제가 발생하나요?

답변:
재귀 함수에서 기저 사례(Base Case)가 없으면 함수가 무한히 자기 자신을 호출하게 되어 Stack Overflow가 발생합니다. 기저 사례는 재귀 호출을 멈추는 조건으로, 이를 설정하지 않으면 함수는 종료되지 않고 계속해서 스택에 활성화 레코드가 쌓이게 됩니다. 스택은 메모리가 한정되어 있으므로, 재귀 호출이 계속되면 결국 메모리가 부족해져 Stack Overflow 오류가 발생하게 됩니다.

예를 들어, 기저 사례가 없는 재귀 함수:

int infiniteRecursion(int n) {
    return infiniteRecursion(n - 1);  // 종료 조건이 없으므로 무한히 호출됨
}

위 함수는 계속해서 자기 자신을 호출하여 Stack Overflow가 발생합니다.

Q2: 반복문을 사용해 재귀 함수를 대체할 때 성능 면에서 어떤 차이가 있을까요?

답변:
반복문을 사용해 재귀 함수를 대체할 때 성능 면에서 차이가 발생하는 이유는 스택 메모리 사용과 관련이 있습니다.

  • 재귀 함수: 재귀 호출 시마다 활성화 레코드가 스택에 저장되므로, 함수 호출이 많아질수록 스택 메모리 사용이 증가합니다. 이는 스택 오버헤드(메모리 사용 및 호출 비용)를 발생시켜 성능에 부정적인 영향을 미칠 수 있습니다. 특히 깊은 재귀는 Stack Overflow의 위험을 동반합니다.

  • 반복문: 반복문은 스택을 사용하지 않고, CPU 레지스터나 기본 메모리에서 직접 실행되므로, 스택에 추가적인 메모리 할당이 필요하지 않아 더 효율적입니다. 반복문은 재귀의 오버헤드 없이 동일한 작업을 수행할 수 있어 더 빠르고 메모리 효율적입니다.

따라서, 재귀 호출이 깊은 문제는 반복문으로 대체하는 것이 성능 면에서 더 유리할 수 있습니다. 예를 들어, 큰 n 값을 처리하는 피보나치 수열 문제는 반복문을 사용하면 스택 메모리 오버헤드가 없기 때문에 더 빠르고 안전하게 처리할 수 있습니다.

Q3: Heap Overflow와 Stack Overflow는 각각 어떤 경우에 발생하며, 차이점은 무엇인가요?

답변:
Heap Overflow와 Stack Overflow는 둘 다 메모리 부족으로 발생하는 오류이지만, 발생하는 영역과 원인이 다릅니다.

Heap Overflow:

  • 발생 원인: 힙 메모리는 동적 메모리 할당을 위해 사용되며, 프로그래머가 객체를 동적으로 생성할 때 활용됩니다. 만약 힙 메모리가 가득 차거나 할당된 메모리를 반환하지 않으면 Heap Overflow가 발생할 수 있습니다. 자바에서는 new 키워드를 사용해 객체를 생성할 때 힙 메모리가 사용됩니다.

예시:

int[] largeArray = new int[Integer.MAX_VALUE];  // 너무 큰 메모리 할당 시 Heap Overflow 발생 가능

발생 시점: 힙 메모리가 가득 차서 더 이상 동적 메모리를 할당할 수 없을 때 발생합니다.

Stack Overflow:

발생 원인: 스택 메모리는 함수 호출 시마다 활성화 레코드가 저장되는 영역입니다. 재귀 호출이 지나치게 깊어지면 스택에 활성화 레코드가 계속 쌓여 Stack Overflow가 발생할 수 있습니다.

예시:

int recursive(int n) {
    return recursive(n - 1);  // 기저 사례가 없어 무한 재귀 호출
}
  • 발생 시점: 스택 메모리가 가득 차서 더 이상 새로운 활성화 레코드를 저장할 수 없을 때 발생합니다.

차이점:

  • Heap Overflow는 객체 생성 시 발생하며, 힙 메모리의 부족으로 인한 오류입니다.
  • Stack Overflow는 함수 호출 시 스택 메모리가 부족해 발생하며, 주로 재귀 함수의 과도한 호출로 발생합니다.
profile
서버란
백엔드에서 서버엔지니어가 된 사람
다음 포스트

Stack 자바 직접구현

0개의 댓글