[운영체제] 메모리 구조 (재귀호출 vs 반복문)
재귀에서 탈출조건(적절하게 빠져나오는 구문?)이 없으면 스택오버플로우가 발생한다. why? 스택에서 뭔 문제가 있겠지!! 스택이 존재하는 메모리 구조를 더 이해해두기 위해 포스팅한다.
메모리 구조
https://blog.naver.com/zzaxowns/222611286857 (참고블로그! 여기 더 자세하게 설명되어있는듯한..)
프로그램이 운영체제로부터 할당받는 대표적인 메모리 공간은 다음과 같다.
코드(Code) 영역
실행할 프로그램의 코드가 저장되는 영역이다.
프로그램이 시작하고 끝날 때까지 메모리에 계속 남아 있는다.
컴파일된 기계어가 들어가게 된다.
CPU는 코드 영역에 저장된 명령어를 하나씩 가져가서 처리한다.
데이터(Data) 영역
프로그램의 전역 변수와 정적 변수, 문자열 상수가 저장되는 영역이다.
프로그램이 시작하고 끝날 때까지 메모리에 계속 남아 있는다.
힙(Heap) 영역
사용자가 직접 관리할 수 있고 해야만하는 영역이다.
힙 영역은 사용자에 의해 메모리 공간이 동적으로 할당되고 해제된다.
malloc()/new 연산자를 통해 할당하고, free()/delete 연산자를 통해서 해제가 가능하다.
런타임 시에 크기가 결정된다.
스택(Stack)영역
함수의 호출과 관계되는 지역 변수와 매개 변수가 저장되는 영역이다.
함수의 호출과 함께 할당되며 함수의 호출이 완료되면 소멸한다.
이렇게 스택 영역에 저장되는 함수의 호출 정도를 스택 프레임(stack frame)이라고 한다.
프로그램이 자동으로 사용하는 임시 메모리 영역이다.
컴파일 시에 크기가 결정된다.
Stack vs Heap
Stack과 Heap은 OS/컴퓨터 구조에서 빈번하게 비교되는 주제이다.
-> 메모리 구조상 Stack이 커지면 Heap이 작아지고, Stack이 작아지면 Heap이 커지는 구조이다.
그렇다면 할당 속도는 누가 더 빠를까?
Stack은 이미 할당 되어 있는 공간을 사용하므로 포인터의 위치만 바꿔주는 단순한 CPU Instruction이다.
하지만 Heap에서의 할당은 동적인 메모리 영역으로 고려해야하는 요소가 많아 Stack보다 많은 CPU Instruction을 필요로 한다.
결론은 Stack이 할당 속도가 훨씬 빠르다.
하지만 Stack의 공간이 작아 모든 응용에서 사용할 수는 없다.
Overflow
Overflow가 생기는 이유는 Stack과 Heap에 채워지는 메모리 주소의 방향이 달라서이다.
Stack은 주소값이 위에서부터 채워진다. 반면, Heap의 주소값은 아래에서부터 채워져 내려온다.
이때, 두 메모리 영역의 주소가 겹치게 되면 Overflow가 발생한다.
Heap Overflow
Heap이 아래에서부터 주소값을 채워져 올라가다 Stack 영역을 침범한 경우이다.
Stack Overflow
Stack 영역이 Heap을 침범한 경우이다.
재귀호출 VS 반복문
먼저! 메모리 Stack은
- 함수의 호출과 관계되는 지역변수와 매개변수가 저장되는 영역이다.
- 함수의 호출과 함께 할당되며 함수의 호출이 완료되면 소멸한다.
반복문
- 메모리: 메모리 Heap을 사용
- 속도: 빠름
- 무한 루프는 CPU 사이클을 반복적으로 사용한다.
- 코드 길이가 길어지고 변수 사용이 많아진다. (가독성이 떨어짐)
재귀호출
- 메모리: Stack 메모리를 사용
- 속도: 느림
- 무한 재귀는 Stack Overflow(스택 오버플로우)를 일으킴.
- 코드의 길이도 짧고 변수가 적다.(가독성이 높아짐)
프로그램에 재귀를 짜게되면 우선, 하나의 함수가 끝나지 않았는데 또 다시 함수를 호출해 스택이 쌓인다. 메모리의 Stack 영역의 크기는 한정적이고, 크기를 넘어서게 되면 Overflow가 발생한다.
변수가 적다?
변수가 적어서 편하다는 의미는 변수의 메모리가 적어진다는 의미가 아니라
변경 가능한 상태인 변수를 줄여 프로그램 오류가 발생할 수 있는 가능성을 줄여준다는 의미